フリーソフト

« タスクトレイに天気予報 2 [2016/01/30 更新] | トップページ | Google C++スタイルガイド(要約版) »

Leveldb

これは google leveldbライブラリのドキュメントの日本語要約です。読みやすさを優先して省略、意訳している部分が多々あります。正確な情報については原文をご確認ください。 Kawai

原文:http://leveldb.googlecode.com/git-history/1.17/doc/index.html

GitHub:https://github.com/google/leveldb

------------

Leveldb

Jeff Dean, Sanjay Ghemawat

leveldbはkey-value型のデータストアライブラリです。keyとvalueは任意のバイト配列であり、keyでソートされてデータベースに格納されます。keyの比較はユーザ定義の比較関数に従います。

 

■データベースのオープン

leveldbデータベースの実体はファイルシステムのディレクトリです。関連ファイルはこのディレクトリに格納されます。以下はデータベースを開く例です。以下の例では、データベースが存在しない場合は新たに作成します。


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

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

データベースが存在する場合はエラーにするには、以下の行をleveldb::DB::Openの前に追加します。


  options.error_if_exists = true;

 

■ステータス

leveldbのほとんどの関数はleveldb::Status型の値を返します。この値を確認することで関数が成功したかチェックしたり、エラーメッセージを表示したりできます。


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

 

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

データベースオブジェクトをdeleteするだけです。


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

 

■リードとライト

用意されているメソッドはPutDeleteGetです。以下の例では、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をPutした直後にプロセスが死んだ場合、データベースには同じ値が複数残ることになります。これを避けるにはWriteBatchクラスを使用します。


  #include "leveldb/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はデータベースに対する更新処理のシーケンスを保持し、それらを順番通りに実行します。ちなみに上の例で、Putの前にDeleteしているのは、key1とkey2が同じだった場合に値が消えてしまうことを避けるためです。

WriteBatchは、更新処理が大量にある場合の高速化にも利用できます。

 

■同期的な書き込み

デフォルトではleveldbの書き込み処理は非同期に実行されます。つまり、Putを実行すると即座に処理が戻り、ストレージへの実際の書き込みは非同期に発生します。書き込みが終了するまで処理が戻らないようにしたい場合(同期的な書き込み)はsyncフラグをtrueにします。


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

非同期な書き込みは同期的な書き込みよりも1000倍以上も高速です。ただし非同期書き込みでは、マシンがクラッシュした場合に最後のいくつかの更新が失われてしまう恐れがあります。とはいえ、書き込み処理がクラッシュしただけでは(OSやマシンがクラッシュしない限りは)何もロスしません。更新処理はすぐにプロセスメモリからOSに送られるためです。

非同期な書き込みを安全に使う方法としては、クラッシュしたらクラッシュ後の書き込みをやり直す、あるいはN回ごとに同期的に書き込んでおき、クラッシュした時は最後に成功した同期書き込みの直後からやり直す、などがあります。

非同期書き込みの代わりにWriteBatchを使うこともできます。WriteBatchに複数の更新を入れておき、同期的に書き込みます(write_options.synctrueに設定)。同期書き込みによる余分なコストは、バッチ内の書き込み処理において徐々に清算されていきます。

 

■同時実行

データベースは同時に一つのプロセスからしかオープンできません。leveldbの実装では、誤用を防止するためOSからのロックを取得します。単一のプロセスでは、複数のスレッドから同じleveldb::DBオブジェクトを安全に共有できます。異なるスレッドから同じデータベースに書き込んだり、インテレータをフェッチしたり、Getしたりできます。leveldbが自動的に同期処理を実施するため、ユーザが同期処理を実施する必要はありません。ただし、他のオブジェクト(インテレータやWriteBatch)については、ユーザによる同期処理が必要です。より詳しい情報についてはパブリックなヘッダファイルを参照してください。

 

■インテレータ

以下の例は、データベース内のすべてのkeyとvalueのペアを出力する例です。


  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) のkeyを処理する例です。


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

逆方向にも処理できます(注意:逆方向は順方向よりも遅い)


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

 

■スナップショット

スナップショットはkey-value全体の状態の読み取り専用のビューを提供します。ある特定のバージョンのDBを読み取りたいときは、ReadOptions::snapshotにスナップショットを指定します。ReadOptions::snapshotNULL を指定した時は、現在の状態(暗黙的なスナップショット)から読み取りが実行されます。

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で開放してください。

 

■Slice型

it->key()it->value() の返り値は leveldb::Slice 型のインスタンスです。Slice は外部のバイト型配列へのポインタとその長さを保持するシンプルな構造体です。leveldb のメソッドは null 終端されたCスタイルの文字列を返しません。leveldb の key や value は '\0' を含むことができるためです。

C++スタイルの文字列や、Cスタイルのnull終端の文字列は簡単に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が使用されている間は、Silceのポインタが指している外部のバイト配列が有効であることを確実としてください。例えば、以下はバグになります。


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

スコープから出ると str が解放され、sliceが指すメモリ領域は消えてしまいます。

 

■比較器

デフォルトの比較関数では、keyは辞書順に並べられます。keyの比較方法はデータベースをオープンする際に自由に設定できます。例えば、各 key が2つの数字から構成されている場合を考えます。ひとつ目の数字でソートし、ひとつ目の数字が同じならふたつ目の数字でソートするようにするには、まずこれらのルールを表現するleveldb::Comparatorのサブクラスを定義します。


  class TwoPartComparator : public leveldb::Comparator {
   public:
    // Three-way comparison 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 methods for now:
    const char* Name() const { 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 メソッドの結果は、データベース作成時にデータベースに結び付けられ、その後データベースをオープンするたびにチェックされます。Name を変更すると、leveldb::DB::Openの呼び出しは失敗します。既存のデータベースの内容をすべて破棄してもOKな場合のみ、Name を変更してください。

事前の設計においてキーの形式を少しずつ改良していくような場合のアイデアを紹介します。例えば、各キーの後ろにバージョン番号をつけておきます(ほとんどの用途において1バイトで十分なはず)。新しいキー形式にスイッチしたいときは、 新しいキーのバージョン番号をインクリメントし、比較器における処理をキーのバージョン番号で分岐するように変更します。比較器の Name は変更なしです。

 

■パフォーマンス

include/leveldb/options.hで定義されているデフォルト値を変更してパフォーマンスをチューニングすることができます。

ブロックサイズ

leveldbは隣接したキーを同じブロックに集約します。このブロックがストレージとの転送の単位となります。デフォルトのブロックサイズは非圧縮で約4,096バイトです。データベースの内容をバルクスキャンするようなアプリケーションでは、ブロックサイズを増やしたほうがよいかもしれません。また、いろいろな場所から少しずつ読み込むようなアプリケーションでは、ブロックサイズを小さくしたほうがよいかもしれません。ブロックサイズが大きいほど圧縮が効果的となります。また、1キロバイト以下、あるいは数メガ以上のブロックを使っても大きな恩恵はありません。

圧縮

各ブロックは、ストレージに書き込まれる前に個々に圧縮されます。デフォルトの圧縮方法は "very fast" です。圧縮できなデータに対しては自動的に圧縮が無効となります。ベンチマークなどの目的で圧縮を無効にしたい場合は以下のようにします(ベンチマーク以外の目的で無効にすべきではありません)。


  leveldb::Options options;
  options.compression = leveldb::kNoCompression;
  ... leveldb::DB::Open(options, name, ...) ....

キャッシュ

データベースの内容はファイルシステム上の一連のファイルに保存されます。それぞれのファイルは一連の圧縮ブロックを保存します。options.cacheNULL 以外にすると、頻繁に使用される非圧縮ブロックのキャッシュとして使用されます。


  #include "leveldb/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;

キャッシュには非圧縮のデータが保存されることに注意してください。キャッシュサイズは、圧縮前のデータサイズを考慮して設定してください。キャッシュ処理はオペレーティングシステムのバッファキャッシュに任せることもできるし、独自のEnv実装に任せることもできます。

バルク読み出しの際は、キャッシュされたデータのほとんどが置き換えられていくため、キャッシュを無効にしたほうがよいかもしれません。キャッシュを無効にするにはインテレータのオプションを使用します。


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

Key のレイアウト

ディスク転送やキャッシュの単位はブロックです。隣接したキー(データベースのソート順に従う)は、たいてい同じブロックに置かれます。そのため、同時にアクセスされるキーは近くに置き、あまり使用されないキーはキー空間の別の領域に置くことでアプリケーションの性能を改善することができます。

例えば、leveldbのトップにシンプルなファイルシステムを実装することを考えます。格納するエントリーは以下のようなものとします。


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

ファイルメタデータをスキャンする際にファイル内容までがキャッシュされてしまわないよう、filename に一文字('/'とか)の接頭辞をつけ、file_block_idには別の文字('0'とか)をつけるなどします。

フィルタ

leveldbはディスク上にデータを保持するため、単一のGet()呼び出しで複数のディスク読み出しが実行されることがあります。オプションのFilterPolicyメカニズムを利用することで、ディスク読み出しの回数を大幅に減らすことができます。


  leveldb::Options options;
   options.filter_policy = NewBloomFilterPolicy(10);
   leveldb::DB* db;
   leveldb::DB::Open(options, "/tmp/testdb", &db);
   ... use the database ...
   delete db;
   delete options.filter_policy;

上記のコードは、Bloomフィルタ(要素が集合のメンバーであるかテストする手法のひとつ)ベースのフィルタリングポリシーをデータベースを結び付ける例です。Bloomフィルタベースのフィルタリングでは、データの何ビットかをキーごとにメモリに保持します。(上記の例では、キーごとに10ビット。)このフィルタにより、Get()によるディスク読み出しの回数を約1/100に減らすことができます。キーごとのビットを増やすと、メモリの使用量は増加しますが、読み出し回数をさらに削減することができます。作業用データがメモリに収まらず、ランダム読み出しが多いアプリケーションでは、フィルタポリシーの利用を推奨します。

独自の比較器を使っている場合は、フィルタポリシーがその比較器に適合しているか注意してください。例えば、キーを比較する際に後ろのスペースを無視するような比較器を考えます。この場合は、後ろのスペースを同様に無視するようなカスタムフィルタポリシーを用意しなくてはなりません。例を示します。


  class CustomFilterPolicy : public leveldb::FilterPolicy {
   private:
    FilterPolicy* builtin_policy_;
   public:
    CustomFilterPolicy() : builtin_policy_(NewBloomFilterPolicy(10)) { }
    ~CustomFilterPolicy() { delete builtin_policy_; }

    const char* Name() const { return "IgnoreTrailingSpacesFilter"; }

    void CreateFilter(const Slice* keys, int n, std::string* dst) const {
      // 後ろのスペースを取り除いてからビルトインのbloomフィルタコードを使う
      std::vector<Slice> trimmed(n);
      for (int i = 0; i < n; i++) {
        trimmed[i] = RemoveTrailingSpaces(keys[i]);
      }
      return builtin_policy_->CreateFilter(&trimmed[i], n, dst);
    }

    bool KeyMayMatch(const Slice& key, const Slice& filter) const {
      // 後ろのスペースを取り除いてからビルトインのbloomフィルタコードを使う
      return builtin_policy_->KeyMayMatch(RemoveTrailingSpaces(key), filter);
    }
  };

独自のフィルタポリシーを使用したい場合は、leveldb/filter_policy.hを参照してください。

 

■チェックサム

leveldbはファイルシステムに保存しているすべてのデータに対してチェックサムを保持しています。チェックサムの検証方法について2つのオプションがあります。

  • ReadOptions::verify_checksumstrue にセットすると、すべてのデータについてチェックサムの検証が強制されます。デフォルトは false です。
  • データベースをオープンする前に Options::paranoid_checkstrue にセットすると、データベースの破損が検出された場合にエラーが発生するようにできます。データベースのどの部分が破損しているかによって、データベースをオープンした際、あるいはデータベースの操作を実行した際にエラーが発生します。デフォルトでは、ストレージの一部が破損している場合でもデータベースが使用できるよう false に設定されています。

    データベースが破損した場合は(paranoid_checkstrueのときはおそらくオープンできない)、leveldb::RepairDB関数で修復できるかもしれません。

 

■おおよそのサイズ

GetApproximateSizesメソッドで、キーの範囲で使用されるファイルシステム上のおおよそのバイト数が取得できます。


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

この例では、キー範囲 [a..c) で使用されるおおよそのバイト数が sizes[0] にセットされ、キー範囲 [x..z) で使用されるおおよそのバイト数が sizes[1] にセットされます。

 

■環境

leveldbにおけるすべてのファイル操作(と他のオペレーティングシステムコール)はleveldb::Envオブジェクトを通して実行されます。ユーザによっては、独自のEnv実装によってより良い制御を提供したいと思うかもしれません。例えば、システムへの負荷を制限するため、ファイルの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によってエクスポートされた型、メソッド、関数について、プラットフォーム特有の実装を提供します。詳細はleveldb/port/port_example.hを参照してください。

また、新しいプラットフォームには、新しいデフォルトのleveldb::Env実装が必要です。leveldb/util/env_posix.hを参考にしてください。

 

■他の情報

leveldbの実装についての詳細については以下のドキュメントを参照してください。

« タスクトレイに天気予報 2 [2016/01/30 更新] | トップページ | Google C++スタイルガイド(要約版) »

技術文書」カテゴリの記事