【技術メモ】LevelDB超入門
【技術メモ】LevelDB
LevelDB入門 (基本編)
- 掲載日：2014/05/05
yosuke-furukawa.hatenablog.com
LevelDBとは?
- key-value型のデータストアの一つ
- Googleが開発、2011年に公表。C++で書かれている。
- Google がIndexedDB実装用に、SQLiteよりもIndexedDBに向くKey-Value型の軽量データストアとして開発
- ChromeのIndexedDB 実装のためのbackend
- InfluxDBもRiakもバックエンドはLevelDB
LevelDBの特徴
- keyとvalueが任意のバイト列
- データはkeyでソートされて格納
- 比較関数でソート順序変更
- シンプルな操作、 Put(key, value), Get(key), Delete(key)
- 複数の変更をatomicに処理
- 書き込み中でもread可能
- データを自動的に圧縮（圧縮ライブラリ：Snappy）
- OSの操作を抽象化してカスタマイズ可能
LevelDBは何に向くのか
- LevelDBをバックエンドとした独自のデータストアを作る、という使われ方が多い
- 例：InfluxDB
- keyにtimestampを付けて、LevelDB内部で時系列順にソート
- 順番にReadするsequential readとwriteヘビーに利用
- 例：Riak
- 例：ChromeのIndexedDB
- 構造が非常にシンプルで軽量なので、クライアントサイドのバックエンドとしても使える
- まさにSQLiteの代替
- Node.js
- Node.jsは、ブラウザでもサーバサイドでも動作できる
- Node.jsでLevelDBが流行っている理由としてはこのポータブルかつモジュラーなところ
- クライアントサイドでもサーバサイドでも同じインタフェースで永続化できる
アーキテクチャ
- write時にはLogとSorted Tableに書き込み
- read時にはcacheを通してLog、Sorted Table、Cacheから値を読み取り
Log file
- LevelDBへのwrite処理は、Logとインメモリのストア先（memtable）に書込
- Logに書きだされたデータは、一定サイズを超えるとファイル（SST）に出力
- read処理は、LogとSSTの2つのデータ構造から読込
- SSTに入っているデータ：書込から一定時間が経過したデータ
- Logに入っているデータ：新しいデータ
- この他に、読み込みを高速化するためにCache領域
- Cache領域はアプリケーションに依存して大きさ調整が可能
String Sorted Table (SST)
- SSTは、keyでソートされたエントリを保存
- SSTは、Level毎にまとまって階層化
- ここがLevelDBの由来
- Logが一定量貯まると最も若いストア先（Level-0）にデータを移動
- Level-0がいっぱいになると、Level-0からLevel-1にデータを移動
- Levelが増えるほど保存できる容量が増える仕組み
- 雑に言えば、 Level-1だと大体10MB保存できて、Level-2だと100MB、Level-3だと1GBと10倍ずつ増加
Bloom filter
- キーがどのLevelに存在するかを教えてくれるフィルター
- キーからハッシュを使って、そのLevelにデータが存在する可能性をO(1)で計算
- Bloom filterの特徴はFalse Positive
- 「存在しない」の応答時は、確実に存在しない
- 「存在する」の応答時は、実際にLevel内を探索するまで不明
- 明らかに無駄なLevelを排除することで探索範囲の枝刈りをするしくみ
基本操作 Put
- key と valueを入れると、一旦その値をLogと memtableに書出
- memtableに入れた情報は、書込上限に達するとLevel-0のSSTに書出
- Level-0がいっぱいになったらLevel-1に書出、以下階層的に。
基本操作 Get
- メモリ、Level-0、Level-1、Level-2、、、と検索してヒットしたらその値を返却
- 検索する際にBloom filterを使って無駄な検索の枝刈り
基本操作 Delete
- 基本的に論理削除で、削除フラグを立てるだけ
- 次のLevelに値を移動する時に物理削除
- 論理削除にすることで、削除コストとindexの再作成コストを減らす
