読者です 読者をやめる 読者になる 読者になる

冥冥乃志

ソフトウェア開発会社でチームマネージャをしているエンジニアの雑記。アウトプットは少なめです。

follow us in feedly

leveldbのドキュメントを訳してみた

本家のドキュメント(Leveldb)を翻訳してみました。
長文をちゃんと最後まで訳しきるのは大学入試以来で、えいや!でニュアンスのみにしている所もあります。
また、誤訳や私の理解が追いついていないところなどもあると思いますので、その辺りは指摘していただけるとありがたいです。
前回の記事で宣言したソースは、よくよく考えてみるとJNIのReadmeのサンプル以上のことはしていないので、公開してもあまり役に立たないことに気づきました。
なお、サンプルはC++のまま記載しています。

では、以下に訳したドキュメントを。

leveldb

levelDBは永続的なキーバリューストアを提供するライブラリです。キーと値は任意のバイト列です。ユーザ定義の比較関数に従ってキーバリューストア内のキーを順序づけられます。

データベースの開始:

levelDBデータベースはファイルシステムのディレクトリに一致する名前を持っています。データベースの全てのコンテンツは、このディレクトリの中に格納されます。以下は、必要に応じてディレクトリを作成してデータベースをオープンするためのサンプルです。

#include
#include "leveldb/include.db.h"

leveldb::DB* db;
leveldb::Options options;
options.create_if_missing = true;
leceldb::Status status = leveldb::DB::Open(options, "/temp/testdb", &db);
assert(status.ok());

もし、既にデータベースが存在するときに例外を発生させたい場合は、サンプルに以下を追加して、leveldb::DB::Openを呼び出してください。

options.error_if_exists = true;

ステータス:

上記例のleveldb::Statusタイプに注意してください。このタイプの値は、leveldbのエラーに関して様々な機能を返します。結果がOKであることを確認したり、エラーメッセージを出力したりできます。

leveldb::Status s = ...;
if(!s.ok()) cerr << s.ToString() <

データベースのクローズ:

もし、データベースの作業を終了したいときは、データベースオブジェクトを削除すれば良いだけです。

... open the db as described above ...
... do something with db ...
delete db;

キーバリューストアの読み書き:

データベースはPut,Delete,Getのメソッドをデータベースの操作のために提供します。例えば、以下のコードはkey1からkey2に値を移し替えるものです。

std::string value;
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
if(s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);
if(s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);

アトミックな更新:

もし、key2の書き込みが成功してkey1の削除が完了する前にプロセスが死んでしまったら、同じ値が複数のキーはいかに格納されることに注目してください。分割不可能な更新のセットを提供するWriteBatchクラスを使うことでこのような問題をさけることができます。

#include "leveldb/include/write_batch.h"
...
std::string value;
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
if(s.ok()) {
leveldb::WRiteBatch batch;
batch.Delete(key1);
batch.Put(key2, value);
s = db->Write(leveldb::WriteOptions(), &batch);
}

WriteBatchはデータベースへの編集が作成された順序を保持し、編集はバッチ内での順序により作成されます。もし、key1とkey2が一致する場合に、Putより前にDeleteを実行したばあい、全く謝った値を削除しようとして処理を終了できないことに注意してください。
これらのアトミックな更新の恩恵を離れても、WriteBatchは、同じバッチ内の個々の置換の多くがひとまとめにされた更新となるため、更新速度がアップします。

同期的な書き込み:

デフォルトでは、全てのleveldbへの書き込みは非同期です。(OSのプロセスに書き込みをプッシュした後に返ります)これらの永続的なストレージの配下にあるOSメモリへの変換は、非同期です。syncフラグは、プッシュされた永続的なストレージへのデータ書き込みが終わるまで、書き込み処理をリターンしないように個々の書き込み処理を変更することが可能です。(Posixシステムでは、書き込み処理のリターン前にfsync(...)やfdatasync(...)やmsync(..., MS_SYNC)のいずれかの呼び出すことで実装されます。)

leveldb::WriteOptions write_options;
write_options.sync = true;
db->Put(write_options, ...);

非同期な書き込みは、同期的な書き込みよりも1000倍以上のオーダーで速いです。非同期な書き込みの難点は、マシンがクラッシュしてしまうことで最後の更新がロスとしてしまうかもしれないことです。全てのsyncがfalseの場合、書き込み処理時のクラッシュ(例えばリブートとかではなく)はロスの原因にはならないことと、OSが完了と見なす前のプロセスメモリから更新がプッシュされることに注意してください。
非同期な書き込みはしばしば安全に使われます。例えば、データベース内の非常に大きなデータをロードするとき、クラッシュ後の大きなロードをリスタートすることでロスとした更新を処理することができます。ハイブリッドなスキーマは、任意の回数の同期的な書き込みとクラッシュイベント時に、多くのロードが前回の実行で最後に完了した同期の直後からリスタートされます。(同期的な書き込みは、クラッシュのリスタート時に記述されるマーカをアップデートします。)
WriteBatchは同期書き込みとは別のものを提供します。複数の更新を同じWriteBatchに記載することができ、一緒に同期書き込みを実行できます(例えば、write_options.syncがtrueにセットされている場合)。同期書き込みの外部のコストは、バッチ内の全ての書き込みにわたって徐々に減っていきます。

並列性:

データベースは一度に一つのプロセスからオープンされます。leveldbの実装は、誤用を防ぐためにOSからのロックを取得します。シングルプロセスの中で、同じlevedb::DBオブジェクトはマルチスレッドに対して安全に共有されます。例えば異なるスレッドが、外部の同期なしに同じデータベースから書き込んだり、イテレータをフェッチしたり、Getを呼んだりできます(leveldbの実装は自動で要求された同期を実施します)。しかしながら、他のオブジェクト(イテレータやWriteBatchのような)は、外部の同期を要求します。このようなオブジェクトを二つのスレッドで共有する場合、自身のロックプロトコルを使用するためのアクセスをプロテクトする必要があります。詳細は公開されたヘッダーファイルを参照してください。

イテレーション:

以下の例は、データベース中の全てのキーと値のペアを表示するサンプルです。

leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
for(it->SeekToFirst(); it->Valid(); it->Next()) {
cout << it->key().ToString() << ": " << it->value().ToString() << endl;
}
assert(it->status().ok()); // Check for any errors found during the scan
delete it;

以下はキーのレンジがstartからlimitまでの場合のサンプルです。

for(it->Seek(start);
it->Valid() && it->key.ToString() < limit;
it->Next()) {
...
}

逆順でも可能です。(注意:逆順のイテレーションは昇順のイテレーションよりも幾分遅くなることがあります)

for(it->SeekToLast; it->Valid(); it->Prev()) {
...
}

スナップショット:

スナップショットは、キーバリューストア全体の一貫した読み込み専用のビューを提供します。ReadOptions::snapshotが非NULLであれば、特定のバージョンのDBの状態の読み込み処理を指し示します。もしReadOptions::snapshotがNULLの場合、読み込みは現在の状態のスナップショットであると暗黙のうちに処理されます。
スナップショットは通常、DB::GetSnapshot()メソッドを使って作られます。

leveldb::ReadOptions options;
options.snapshot = db->GetSnapshot();
... apply some updates to db ...
leveldb::Iterator* iter = db->NewIterator(options);
... read using iter to view the state when the snapshot was created ...
delete iter;
db->ReleaseSnapshot(options.snapshot);

スナップショットがこれ以上必要ではなくなった場合、DB::ReleaseSnapshotインタフェースを使ってスナップショットをリリースすることを忘れないでください。つまり、スナップショットの読み込みをメンテナンスすることを実装で何とかするということです。
書き込み処理は、特定の更新処理のセットを実行した直後のデータベースの状態を表すスナップショットを返すことを意味します。

leveldb::Snapshot* snapshot;
leveldb::WriteOptions write_options;
write_options.post_write_snapshot = &snapshot;
leveldb::Status status = db->Write(write_options, ...);
... perform other mutations to db ...

leveldb::ReadOptions read_options;
read_options.snapshot = snapshot;
leveldb::Iterator* iter = db->NewIterator(read_options);
... read as of the state just after the Write call returned ...
delete iter;

db->ReleaseSnapshot(snapshot);

スライス:

it->key() と it->value() の結果は、より上位ではleveldb::Sliceタイプのインスタンスを呼び出します。Sliceは、外部倍と配列へのポインタと長さを含むシンプルな構造です。Sliceの戻り値は、大きなキーと値をコピーする必要があるかもしれないstd::stringの戻り値のコストの小さい代わりとなります。付け加えると、leveldbのキーと値は'\0'バイトを含むことを許可するので、leveldbメソッドはnullで終了するC言語スタイルの文字列を返しません。
C++文字列とnullで終了するC言語スタイルの文字列は、簡単にSliceにコンバートすることができます。

leveldb::Slice s1 = "hello";
std:: string str("world");
leveldb::Slice s2 = str;

SliceはC++文字列に変換し直すことができます。

std::string str = s1.ToString();
assert(str == std::string("hello"));

Sliceの使用時は、Sliceが参照している外部バイト配列が確実に生きて呼び出すことのできる間までであることに注意してください。例えば、以下はバグとなります。

leveldb::Slice slice;
if(...) {
std::string str = ...;
slice = str;
}
Use(slice);

ifステートメントのスコープ外になったとき、sliceが見つからないため、strは破棄されストレージにバックアップされるでしょう。

コンパレータ:

前述のサンプルは、バイト列を辞書順で並び替えるデフォルトのキー順のファンクションを使用します。しかしながら、データベースのオープン時にカスタムコンパレータを指定することができます。例えば、それぞれのデータベースキーが二つの数値から成り立ち、最初の数値でソートする必要があり、二番目の数値は同値に扱う必要がある場合を仮定しましょう。最初に、以下のルールで表現されるleveldb::Comparatorのサブクラスを定義しましょう。

class TwoPartComparator : public leveldb::Comparator {
public:
// Three-way comparision function:
// if a < b: negative result
// if a > b: positive result
// else: zero result
int Compare(const leveldb::Slice& a, const leveldb::Slice& b) const {
int a1, a2, b1, b2;
ParseKey(a, &a1, &a2);
ParseKey(b, &b1, &b2);
if(a1 < b1) return -1;
if(a1 > b1) return +1;
if(a2 < b2) return -1;
if(a2 > b2) return +1;
return 0;
}

// Ignore the following method for now:
const char* Name() { return "TwoPartComparator"; }
void FindShortestSeparator(std::string*, const leveldb::Slice&) const { }
void FindShortSuccessor(std::string*) const { }
};

カスタムコンパレータを使用するデータベースを作ります。

TwoPartComparator cmp;
leveldb::DB* db;
leveldb::Options options;
options.create_if_missing = true;
options.comparator = &cmp;
leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
...

後方比較:

コンパレータのNameメソッドの結果は、データベースがクリエイトされたときに利用され、各データベースオープン時にチェックされます。もし名前を変えると、leveldb::DB::Openの呼び出しが失敗します。従って、新しいキーフォーマットと比較関数が存在するデータベースと矛盾する場合のみ名前の変更をして、存在する全てのデータベースのコンテンツを放棄してください。
しかしながら、プリプランニング時の想定を超えて徐々にキーフォーマットを進化させることができます。例えば、全てのキーの末尾にバージョン番号(1バイトで十分足ります)を格納することができます。新しいキーフォーマットへスイッチしたいときは(例えばTwoPartComparatorに3番目のオプションパートを追加します)、以下の方法がバージョン番号がキーに対してこれらを解釈する方法を決定するために使われます。

  1. 同じ名前のコンパレータを使い続けます
  2. 新しいキーのバージョン番号をインクリメントします
  3. コンパレータ関数を変更します

パフォーマンス:

パフォーマンスは leveldb/include/options.h に定義されているデフォルトの値を変更することで返ることができます。

ブロックサイズ:

leveldbは、同じブロックの中に隣接したキーが一緒にグルーピングされ、それらのブロックは永続的なストレージから変換したユニットです。デフォルトのブロックサイズは、非圧縮でおおよそ4096バイトです。データベースのコンテンツをひとまとまりでスキャンするほとんどのアプリケーションは、このサイズを増やしたいことでしょう。小さいバリューの読み込みが首都鳴るアプリケーションでは、パフォーマンスがより改善されるのであればより小さなブロックサイズにスイッチしたいことでしょう。1キロバイトよりもブロックサイズを小さくしたり、数メガバイトより大きくすることにはあまり恩恵はありません。それよりも大きなブロックサイズの圧縮の方が効果的です。

圧縮:

それぞれのブロックは、永続的なストレージに書き込まれる前に個別に圧縮されます。デフォルトの圧縮メソッドはとても速く、自動的には圧縮できないデータは自動で判別して適用しないため、圧縮はデフォルトです。レアケースとして、アプリケーションが圧縮を完全に無効にしたいのであれば、ベンチマークがパフォーマンスの向上を示すようにする必要があるでしょう。

キャッシュ:

データベースのコンテンツは、ファイルシステム上のファイルのセットに格納され、それらのファイルは圧縮されたブロックの順に格納されます。options.cacheを非NULLにすると、キャッシュは非圧縮ブロックコンテンツを何度も使うようになります。

#include = "leveldb/include/cache.h"

leveldb::Options options;
options.cache = leveldb::NewLRUCache(100 * 1048576); // 100MB Cache
leveldb::DB* db;
leveldb::DB::Open(options, name, &db);
... use the db ...
delete db
delete options.cache;

キャッシュは非圧縮データを保持することに注意してください。それは、圧縮からの削除はなく、アプリケーションレベルのデータサイズに従って大きさが決まります。(圧縮ブロックのキャッシングは、OSバッファキャッシュか、クライアントから提供されるカスタム環境の実装に配置されます)まとまった読み込みをする際に、キャッシュされたコンテンツのほとんどが存在せずにバルクリードが完了しないため、アプリケーションがキャッシングを無効にしたいケースがあります。こういうケースにはper-iteratorオプションが使えます。

leveldb::ReadOptions options;
options.fill_cache = false;
leveldb::Iterator* it = db->NewIterator(options);
for(it->SeekToFirst(); it->Valid(); it->Next()) {
...
}

キーレイアウト:

ディスクの変換とキャッシングの単位がブロックであることに注意してください。隣接したキー(データベースのソート順として)は、通常同じブロックに配置されます。したがってアプリケーションは、それぞれが互いに近く配置されたキーを使用することによって、キースペースの分割された領域内のキーが頻繁に使用においてもパフォーマンスを改善することができます。例えば、leveldbのトップにシンプルなファイルシステムを実装しているとします。エントリーのタイプは以下のように配置されているはずです。

filename -> permission-bits, length, list of file_block_ids
file_block_id -> data

これらは、一文字のfilenameキープレフィックス("/"のような)と、異なる文字のfile_block_idキー("0"のような)を要求し、メタデータをスキャンかさばるファイルコンテンツのフェッチやキャッシュする為に強制しません。

チェックサム:

leveldbは、ファイルシステム内に配置される全てのデータにチェックサムを提供します。これらのチェックサムのベリファイには、二つの独立した積極的なコントロールが提供されています。
ReadOptions::verify_checksumsをtrueにセットすると、固有の読み込みの代わりにファイルシステムからの読み込まれる全ての強制的なチェックサムによるデータの検証します。デフォルトでは、これらの検証は実施されません。
Options::paranoid_checksをデータベースの実装を作る為のデータベースをオープンする前にtrueにセットすると、内部の誤りを検出するとすぐに例外を発生します。エラーがデータベースオープン時や別の作業時に発生した場合、データベースの誤りの一部を活用してください。デフォルトでは、paranoidチェックはoffで、永続的なストレージの一部で誤りがあってもデータベースを使うことができます。
データベースに誤りがある場合(おそらくparanoidチェックを有効にしてデータベースをオープンできなかった場合)、leveldb::RepairDB関数を使用してオープン可能なデータに回復させることができます。

おおよそのサイズ:

GetApproximatesSizesメソッドを利用して、一つ以上のキーレンジにより使用されるファイルスペースの大まかなバイト数を取得することが可能です。

leveldb::Range rages[2];
ranges[0] = leveldb::Range("a", "c");
ranges[1] = leveldb::Range("x", "z");
unit64_t sizes[2];
leveldb::Status s = db->GetApproximatesSizes(ranges, 2, sizes);

上記は、size[0]に[a..c]の範囲のキーが使用するファイルシステム上の領域の大まかなバイト数がセットされ、size[1]に[x..z]の範囲のキーが使用する大まかなバイト数がセットされるでしょう。

環境:

全てのファイルオペレーション(そして、他のOSのシステムコール)は、leveldb::Envオブジェクトを経由するleveldb実装によって発行されています。洗練されたクライアントは、よりよい制御を得るためにEnv実装を提供したいと思うでしょう。例えばアプリケーションが、システム上のその他の活動上のleveldbへのインパクトを制限するために、ファイルIOのパスに不自然な遅延をもたらすかもしれません。

class SlowEnv : public leveldb::Env {
... implementation of the Env interface ...
};

SlowEnv env;
leveldb::Options options;
options.env = &env;
Status s = leveldb::DB::Open(options, ...);

ポーティング:

leveldbは leveldb/port/port.h によってエクスポートされる types/methods/functions のプラットフォーム固有の実装によって新しいプラットフォームにポートされます。より詳細は、 leveldb/port/port_example.h を見てください。
新しいプラットフォームが新しいデフォルトの leveldb::Env 実装を必要としている場合は、 leveldb/util/env_posix.h を参考にしてください。

その他の情報:

より詳細なleveldbの実装については、以下のドキュメントから見つけることができます。