LevelDBとは
https://github.com/google/leveldb
Googleが作った高速なkey-valueストレージライブラリ。
ChromeのIndexedDBやprometheusなどで使われている。
特徴
- Keyと任意のバイト配列のValue
- データはKeyでソートされる。ソートのための比較関数はオーバーライドできる。
- 基本的な操作はPut, Get, Delete。
- 複数の変更を一つのatomicなバッチで行える
- 一環したデータのビューを取得するために、一時的なスナップショットを作成できる
- データを前にも後ろにもイテレーションできる
- データはSnappy compression libraryで自動で圧縮される。
- ファイルシステムの操作など外部のアクティビティを仮想的なインタフェースを通して行うので、OSとのやりとりをカスタマイズできる。
制限
- SQLデータベースではない。リレーショナルなデータモデルは持てないし、SQLやインデックスにも対応していない。
- 一度に一つのプロセスしかDBにアクセスできない。
キャッシュ
- DBはファイルシステムのディレクトリに対応する名前を持ち、内容はそのディレクトリに保存される。
- 各ファイルには圧縮したブロックが保存され、良く使うものについては非圧縮のブロックがキャッシュされる。
- ソートして隣接するキーは通常、同じブロックに配置される。ディスク転送とキャッシュはブロック単位。
フィルタ
- Getの際、不要なデータを読まなくていいようにフィルタ(Bloom Filter)を用いることができる。
- 独自の比較関数(末尾のスペースを無視するなど)を使う場合、Bloom Filterを使うことができないことがあるので、その場合は独自のフィルタが必要。
レベル
- 最近の更新はログファイルに保存される。これが決められたサイズ(デフォルトでは約4MB)に達すると、sorted table(sst)に変換され、新しいログファイルが生成される。
- 現在のログファイルのコピーがメモリ(memtable)にも乗って読み取りで参照される。
- sstはキーによってソートされたエントリーを保存する。エントリーはキーの値か、削除マーカー。
- sstはレベルによってまとめられる。ログファイルから変換されると、特別なyoungレベル(level-0とも呼ばれる)に配置される。
- youngファイルの数があるしきい値(現在4つ)を超えると全てのyoungファイルを全てのlevel-1ファイルとマージし、新しいlevel-1ファイルを生成する(2MBごとに1ファイル)。
- youngレベルのファイルにはキーが重複していることがある。しかし、他のレベルでは重複しないキーの範囲がある。
- level-L(L>=1)のファイルの合計サイズが
10^L MBを超えたとき、level-Lのファイルと、level-(L+1)の全てのファイルをマージし、新しいlevel-(L+1)ファイルを生成する。 - これによって、バルク読み込み/書き込みのみを使い、コストが高いシークを最小限にして、youngレベルから大きいレベルに更新を徐々にマイグレーションすることができる。
動かしてみる
LevelDBのgo実装。
$ go get github.com/syndtr/goleveldb/leveldb
まずDBを開く。
// open
db, err := leveldb.OpenFile("/Users/sambaiz/leveldb", nil)
defer db.Close()
if err != nil {
panic(err)
}
普通に5個(key0~4)、バッチで5個(key5~9)のデータを入れて、そのうち一つを消す。
// put
for i := 0; i < 5; i++ {
if err = db.Put([]byte(fmt.Sprintf("key%d", i)), []byte(fmt.Sprintf("value%d", i)), nil); err != nil {
panic(err)
}
}
// batch
batch := new(leveldb.Batch)
for i := 5; i < 10; i++ {
batch.Put([]byte(fmt.Sprintf("key%d", i)), []byte(fmt.Sprintf("value%d", i)))
}
if err = db.Write(batch, nil); err != nil{
panic(err)
}
// delete
if err = db.Delete([]byte("key2"), nil); err != nil {
panic(err)
}
この時点でこんなファイルが生成され、
$ ls
000001.log CURRENT LOCK LOG MANIFEST-000000
000001.logの中身はこんな感じになっている。
$ od -c 000001.log
0000000 Z 221 @ 300 031 \0 001 001 \0 \0 \0 \0 \0 \0 \0 001
0000020 \0 \0 \0 001 004 k e y 0 006 v a l u e 0
0000040 o 037 = 373 031 \0 001 002 \0 \0 \0 \0 \0 \0 \0 001
0000060 \0 \0 \0 001 004 k e y 1 006 v a l u e 1
0000100 256 343 > 311 031 \0 001 003 \0 \0 \0 \0 \0 \0 \0 001
0000120 \0 \0 \0 001 004 k e y 2 006 v a l u e 2
0000140 = 006 330 341 031 \0 001 004 \0 \0 \0 \0 \0 \0 \0 001
0000160 \0 \0 \0 001 004 k e y 3 006 v a l u e 3
0000200 002 005 4 016 031 \0 001 005 \0 \0 \0 \0 \0 \0 \0 001
0000220 \0 \0 \0 001 004 k e y 4 006 v a l u e 4
0000240 d 240 344 { M \0 001 006 \0 \0 \0 \0 \0 \0 \0 005
0000260 \0 \0 \0 001 004 k e y 5 006 v a l u e 5
0000300 001 004 k e y 6 006 v a l u e 6 001 004 k
0000320 e y 7 006 v a l u e 7 001 004 k e y 8
0000340 006 v a l u e 8 001 004 k e y 9 006 v a
0000360 l u e 9 ! 233 277 371 022 \0 001 \v \0 \0 \0 \0
0000400 \0 \0 \0 001 \0 \0 \0 \0 004 k e y 2
取得するにはkeyを指定してGet()したり、Iteratorを使う。
IteratorはSeekしたり、StartやLimitを設定したり、Prefixを指定して取ってくることもできる。
// get
fmt.Println("-- get --")
for i := 0; i < 10; i++ {
var data []byte
if data, err = db.Get([]byte(fmt.Sprintf("key%d", i)), nil); err != nil {
fmt.Printf("key%d: %s\n", i, err.Error())
} else {
fmt.Printf("key%d: %s\n", i, string(data))
}
}
// iterate
fmt.Println("-- iterate --")
iter := db.NewIterator(nil, nil)
for iter.Next() {
key := iter.Key()
value := iter.Value()
fmt.Printf("%s: %s\n", string(key), string(value))
}
iter.Release()
if err = iter.Error(); err != nil {
panic(err)
}
-- get --
key0: value0
key1: value1
key2: leveldb: not found
key3: value3
key4: value4
key5: value5
key6: value6
key7: value7
key8: value8
key9: value9
-- iterate --
key0: value0
key1: value1
key3: value3
key4: value4
key5: value5
key6: value6
key7: value7
key8: value8
key9: value9