LevelDB入門 (基本編)

さて、今回は比較的新しいデータストアであるLevelDBについてまとめてみました。
LevelDBは1年ほど前からNode.js界隈ではブームが来ていて、理由がよくわかっていなかったんですが、まとめている内に分かるかなと思ってまとめました。今回はNode.js無関係でLevelDBの基礎的なことだけ調査した結果をまとめてみました。

Node.jsで使ってみる話は後に回します。

LevelDBとは?

key-value型のデータストアの一つです。

Googleの研究者である、Jeff DeanとSanjey Ghemawatが開発し、2011年に公表されました。C++で書かれており、多くのプログラミング言語でbindingsが書かれています。もちろん、JavaScript/Node.jsでも書かれています。

LevelDB は Google のBigTableをベースにしたアーキテクチャを持っていますが、Open Sourceでリリースするため、BigTableとコードを共通化していません。~~LevelDBはSQLiteを置き換えるデータストアとして開発されました。~~誤解を呼ぶ言い方なので訂正します。
Google がIndexedDBを実装する際にSQLiteで実現されようとしていましたが、それよりもIndexedDBに向くKey-Value型の軽量データストアとしてLevelDBが開発されました。SQLiteそのものを置き換える事を目的としているのではありません。

LevelDBは実際かなり広い用途で使われており、ChromeのIndexedDB 実装のためのbackendとしても使われています。
また、今話題の InfluxDBもRiakもバックエンドにはLevelDBを使っています。

LevelDBの特徴

公式ページに書かれている特徴を翻訳しました。

keyとvalueが任意のバイト列である
データはkeyでソートされて格納される
ソート順序を変えるために比較関数が提供されている
基本的な操作は Put(key, value), Get(key), Delete(key)であり、シンプル。
複数の変更をatomicな処理にすることができる
一貫したデータのviewを得るため(書き込み中でもreadできるようにするため)にtransient な snapshotを作ることができる
Snappyという圧縮ライブラリを使ってデータを自動的に圧縮する
外部のactivity (file system操作等)に対して仮想的なインタフェースを通して接続することができる。そのため、OSの操作を抽象化してカスタマイズすることができる。

アーキテクチャ

簡単なアーキテクチャは下記の図のとおりです。

write時にはLogとSorted Tableに書き込み、read時にはcacheを通してLog、Sorted Table、Cacheから値を読み取ります。

ここの細かい説明を続けていきます。

Log file

LevelDBへの全てのwrite処理はLogとインメモリのmemtableと呼ばれるストア先に書き込まれます。
Logに書きだされたデータは一定のサイズ(デフォルトは4MB)を超えるとSorted String Table (SST) と呼ばれるファイルに出力されます。

データをreadするときにはこのLogとSSTの2つのデータ構造から読み込みます。
SSTに入っているデータは書き込まれてから、一定時間が経過したデータを表しており、
Logに入っているデータは新しいデータを表しています。

またこの他に、読み込みを高速化するためにCache領域があります。Cache領域はアプリケーションに依存して大きさを調整することが可能です。

String Sorted Table (SST)

String Sorted Table は前述したとおり、keyでソートされたエントリを保存しています。
Sorted Table は Level 毎にまとまりを持っており、階層化されています。(ここがLevelDBの由来かと思われます。)

Log fileの説明にある通り、Logが一定量貯まると最も若いデータストア先であるLevel-0のストア先にデータを移動します。Level-0がいっぱいになると今度はLevel-0からLevel-1にデータを移動します。Levelが増えれば増えるほど保存できる容量が増える仕組みになっています。
雑に言えば、 Level-1だと大体10MB保存できて、Level-2だと100MB、Level-3だと1GB、Level-4だと10GBという感じに10倍ずつ増えていきます。

サイズを階層的に分けて制限することで、insertが頻出するような場面でも若いLevelはデータサイズが少ないため、インデックス作成時のコストを減らす事ができます。これにより、write操作の効率化を図っています。

Bloom filter

このままだとデータをfindする際にmemtableとLevel-0からLevel-nのデータを探索する必要があり、Levelが多いと探索する範囲が多いので不利になります。これを解決しているのがBloom filterです。簡単にいえば、キーがどのLevelに存在するかを教えてくれるフィルターです。キーが与えられた時にハッシュを使って、そのLevelにデータが存在する可能性があるかどうかをO(1)の計算量で計算してくれます。Bloom filterの特徴はFalse Positiveです。keyが存在しないって応答した時は確実にそのLevelにkeyは存在しませんが、存在する可能性があると応答した場合には本当に存在するかどうかは実際にLevel内を探索するまで不明です。明らかに無駄なLevelを排除することで探索範囲の枝刈りをしているのがこのフィルターです。

詳しい説明はこちら

ブルームフィルタ - Wikipedia

基本操作がどうやって動くか

Put

key と valueを入れると一旦その値をLogと memtableに書き出します。
memtableに入れた情報は書き込みが上限に達するとLevel-0のSSTに書き出します。

Level-0がいっぱいになったらLevel-1に書き出す、とこのように階層的に値が保存されます。

f:id:yosuke_furukawa:20140504220629p:plain

Get

メモリ、Level-0、Level-1、Level-2、、、という感じに検索してヒットしたらその値を返します。
検索する際にどこに値が存在するのかを確かめるために、Bloom filterを使って検索し、無駄な検索の枝刈りをします。

f:id:yosuke_furukawa:20140504220656p:plain

Delete

Deleteは基本的に論理削除で、削除フラグを立てるだけです、次のLevelに値を移動する時に物理的に削除します。

論理削除にすることで、削除コストとindexの再作成コストを減らす効果があります。

f:id:yosuke_furukawa:20140504220720p:plain

LevelDB性能評価

公式サイトにLevelDBとKyoto CabinetのTreeDBとSQLiteの性能比較した結果が載っています*1。

f:id:yosuke_furukawa:20140504221640p:plain

これを見てもらえると分かる通り、Randam readsはTreeDB、SQLiteとそこまで差はありませんが、順番にReadするSequential ReadとWrite処理に関してはTreeDB、SQLiteと比較して優位性があることがわかります。

じゃあLevelDBは何に向くのか

まず、アプリケーションから直接使うデータストアとして使う場合、LevelDB自身はシンプルなデータ操作しか提供していないので、リッチな機能を提供している他のデータストアとは若干レイヤーが違います。

LevelDBをバックエンドとして使う独自のデータストアを作る、という使われ方が多いです。

InfluxDBは内部的にLevelDBを利用していますが、こういった使われ方ですね。

ちなみにInfluxDBはkeyにtimestampが付くようになっているので、LevelDB内部ではkeyの順序でsortされ、時系列順に並びます。LevelDBは順番にReadするsequential readとwriteヘビーにも向くデータストアになっているため、InfluxDBのようなtimeseries DBのバックエンド向きであると言えるでしょう。

またRiakもバックエンドにLevelDBを利用しています。RiakはLevelDBに対してクラスタリングやデータ復旧といったの耐障害性、使いやすいREST APIなどなどを機能として付与し、LevelDBを分散環境でも利用できるように機能拡張された使い方だと言えます。

また、構造が非常にシンプルで軽量なので、サーバーサイドのバックエンドとしてだけではなく、クライアントサイドのバックエンドとしても使えます。ChromeのIndexedDBにも使われてますし、Objective-CやAndroid-Javaでもbindingsが存在しているところを見るとクライアントサイドの軽量永続化データストアとして使われることが多いようです。~~まさにSQLiteの代替ですね。~~

ここまで説明したところでNode.jsで流行っている理由は何となくわかったかもしれませんが、Node.jsのモジュールはjavascriptという特性上、ブラウザでもサーバサイドでも動作させることができるものが一定数存在します。Node.jsでLevelDBが流行っている理由としてはこのポータブルかつモジュラーなところで、クライアントサイドでもサーバサイドでも同じインタフェースで永続化できる点ではないかと思います。

次回はそのNode.jsでどう使うのか話します。