Open5
データベース技術についてのあれこれ
daisuzzSorted String Table (SSTable)
SSTableとは
- key順にソートされた(key, value) 構造が格納されたファイルフォーマット
- Log Structured Storageの実装によく使われる
SSTableの構成
- index file
- keyと実際のデータレコードが配置されているdata fileのoffsetを保持
- B-TreeやHashTableを使って実装される
- data file
- データのkeyとvalueを保持
メリット
- keyがソート済のため、複数ファイルのマージをマージソートのアルゴリズムを使ってシンプルに行うことができる
- 探索対象のキーに近いキーから探索することができるので、全てのキーをメモリに保持しておく必要がない
daisuzzBitcask
Bitcaskとは
- ソートなしでデータを保持するLog Structuredストレージエンジン
- Riakで使用されているストレージエンジンの1つ
- バッファリングにmemtableを使用せず、データレコードを直接ログファイルに格納する
Bitcaskの構成
- 値を検索できるように、Bitcaskはkeydirと呼ばれるデータ構造を使用する
- keydirはキーと、キーに対応する最新のデータレコードへの参照を保持
- ディスク上に残っている古いデータレコードは、keydirからは参照されず、コンパクション時にGCによって回収される
- keydir はin-memory hashmapとして実装されているため、起動時にログファイルから再構築する必要がある
Bitcaskの各処理の動作
- 書き込み処理
- キーとデータレコードが順次ログファイルに追加
- 新たにログファイルに書き込まれたデータレコードのポインタをkeydirに追加
- 読み込み処理
- keydirをチェックして検索されたキーの位置を特定し、ログファイルへのポインタを辿ってデータレコードの位置を特定する
- keydir にあるキーに関連付けられた値は常に 1 つだけなので、point queryは複数の取得先のデータをマージする必要がない
- コンパクション処理
- liveレコードのみを保持し、shadowedレコードを破棄しながら、すべてのログファイルの内容は順次読まれ、マージされたのちに新しい場所に書き込まれる
- Keydir は再配置されたデータレコードへの新しいポインタで更新される
Bitcaskのメリット
- データをログファイルに直接保存するので、別のWALを管理する必要がない
- メモリ空間のオーバヘッドと書き込みのオーバヘッドの両方を減らすことができる
- シンプルでpoint queryのパフォーマンスが優れている
- 複数のバージョンのデータレコードが存在する場合でも、最新のものだけkeydirによって参照される
デメリット
- range scanができない
- keydirとlog fileの両方のデータがソートされていないため
- ユースケースによっては以下が問題になる
- 全てのkeyをメモリに保存しておかなければならない
- 起動時にkeydirを再構築しなければならない
参考文献
daisuzzWisckey
WiscKeyとは
- LSMツリーでソートされたキーを保持し、vLogs(value logs)と呼ばれるunordered append-only fileにデータレコードを保持することで、ソート処理とガベージコレクションを分離している
- Bitcaskの2つの問題を解決できる
- すべてのキーをメモリに保持する必要性
- 起動時にハッシュテーブルを再構築する必要性
WiscKeyの構成
- vLogファイルは、ソートされていないデータレコードを保持する
- キーはソートされた LSM ツリーに格納され、ログファイル内の最新のデータレコードを指す
コンパクション処理
- コンパクション中、vLog ファイルの内容はシーケンシャルに読み込まれ、マージされたのちに新しい場所に書き込まれる
- LSM Treeに格納されているポインタは、新しい場所を指すように更新される
- vLog の内容全体をスキャンしないようにするために、WiscKey はhead ポインタとtailポインタを使用して、live keyを保持するvLog セグメントの情報を保持する
- vLog のデータはソートされておらず、有効性の情報も含まれていないため、LSM Treeをスキャンしてどの値がまだ有効であるかを確認する必要がある
- ガベージコレクション中にこれらのチェックを実行すると、さらに複雑になってしまう
- 従来のLSM ツリーは、コンパクション時にキーインデックスを指定せずにファイルの内容を解決することができる
- ガベージコレクション中にこれらのチェックを実行すると、さらに複雑になってしまう
WiscKeyのメリット
- キーは関連するデータレコードよりもはるかに小さいため、キーをコンパクトにすることで効率が大幅に向上する
- 更新や削除の頻度が低く、ガベージコレクションがそれほど多くのディスク容量をfreeにしない場合に特に有用
WiscKeyのデメリット
- vLog データはソートされていないため、range scanにはランダムなI/Oが必要になる
- WiscKey では内部でSSD並列化を使用して、range scan中にブロックを並列にプリフェッチし、ランダムI/Oのコストを削減する
- ブロックの転送の点では、コストが依然としてかかる
- range scan中に 1 つのデータレコードをフェッチするためには、そのデータレコードがあるページ全体を読み込む必要があるため
参考文献
daisuzzSSD
NAND Flash Chipの構成
- Die
- 複数のPlaneで構成
- Plane
- 1 or 2つのBlockで構成
- Block
- 複数のPageで構成(64～512 Page)
- 削除の単位
- Page
- 読み書きの最小単位
daisuzzbully algorithm
bully algorithmとは
- 分散システムにおけるleader election algorithmの1つ
- 各ノードに割り当てたrankを元にリーダーを選出する
アルゴリズム
- リーダーがいないorクラッシュしたことを検知したノードが自身よりもrankの高いノードに対してelection messageを送る
- 応答があったノードの中からrankが一番高いノードに対してリーダーになったことを通知
- リーダーは他のノードに対して、自身がリーダーになったことをブロードキャストする
問題点
- split brain
- ネットワークの分割があった場合にリーダーが同時に複数ノード選ばれてしまう
- 不安定なノードがリーダーに選ばれてしまうとleader electionが何度も行われてしまう
- ノードの品質指標をノードに保持させ、leader electionのアルゴリズムにその指標を組み込むことで解決できる
bully algorithmの応用
next in line fail over
- bully algorithmのリーダー選出のステップ数を減らした方法
- 各ノードはフェイルオーバー先のノードのリストを保持
- リーダーがクラッシュしたときには、リーダーが保持していたフェイルオーバー先のノードの中からrankが１番高いノードへメッセージを送る
- メッセージを受け取ったノードは、リーダーになれる場合は他のノードにメッセージを送る