メモリテーブル

LevelDBに対してデータをPUTすると、データはメモリ上でデータを管理するメモリテーブルへ書き込まれます。
その後メモリテーブルが一定の容量に達するとテーブルデータとしてファイルに書き込まれます。
ここではメモリーテーブルの仕組みに関して記述を行っていきます。

メモリアロケータ

メモリテーブルではメモリのアロケーションを効率的に行うために、独自のメモリアロケータを利用しています。メモリアロケータはArenaクラス(/util/arena.*)として実装されており、4KBのメモリ領域を最初に確保しておき、必要に応じてその領域を細切れにして割り当てていくといった一般的な仕組みとなっています。

スキップリスト

メモリテーブルでのデータ構造はスキップリストを利用しています。スキップリストを利用することで、データによるアクセスがあった際の検索の効率化と、メモリテーブルデータをファイルに書き込む際のキーによるソート処理の効率化を担うことが出来ます。

格納データ

前述のスキップリストの要素に対して、PUTで指定したデータを格納します。
以下に内部的に格納されるデータの構造を示します。

キーとバリュー値の長さ情報はそれぞれ圧縮された状態で格納されます。またデータのメタ情報としてシーケンス番号とデータタイプの情報が格納されます。
シーケンス番号はデータがLevelDBに格納されるたびにインクリメントされながら割り当てられる番号です。この番号によってトランザクションの管理を行います。
またLevelDBにおいてデータの削除は論理削除によって実装されているため、DELETE操作が行われると対象のキーの削除データが格納されます。そのためPUT操作かDELETE操作でのデータかを判別する為にデータタイプを格納します。