Storage Engine(Hash Index, LSM-Tree, B-Tree)

利用可能な多くのStorage Engineがある中、開発者は開発するプロダクトに適切なStorage Engineを選択する必要がある.

Hash Index

Key-Valueの組み合わせでデータを保存するために利用されるIndex

データ構造について

in-memory HashMap(HashTable)に、全てのKeyに対してlog-structured file中のbyte offsetをmapping.
このoffsetはkeyがある格納されている最初のbyte offsetを示す.

• データ追加時
  1. log-structured file末尾に key-value を追記
  2. 書き込んだデータのoffsetをin-memory HashMapに反映
• データ参照時
  1. HashMapの対象Keyのbyte offsetを利用してseekして値を読み出す
• データの更新時
  1. データ追加時の動作を実施()
     1. log-structured fileの末尾に追記
  2. disk領域を使い切らないようにコンパクション処理
  3. mergeして新しいセグメントを作成
  4. 古いsegmentの削除

追加のみのlog-structuredについて

• メリット
  • セグメントの追記とmergeはsequentialな書き込み処理であり、ランダムな書き込みよりはるかに高速
  • 並行処理とクラッシュリカバリは、セグメントファイルが追記のみ、あるいはimmutableであれば非常にシンプル
  • 古いセグメントをmergeすることで、データファイルが時間と共にフラグメンテーションを起こすという問題を回避可能
• Hash Indexの制約
  • HashTableはメモリ内に収まらなければならない
    • HashTableはメモリ上で保持するため
    • HashTableをdisk上で管理することは可能だが、高いパフォーマンスを維持するのが困難(以下、困難な理由)
      • 大量のランダムアクセスI/Oが必要となる
      • HashTableが大きくなるとHashの衝突への対応に難しいロジックが必要になる
  • 範囲に対するQueryの効率は悪い
    • HashMapの中のKeyを全てLookUpする必要があるため

具体的なServiceには、Bitcaskがある

SSTable(Sorted String Table) and LSM-Tree(Log-Structured Merge-Tree)

Hash Index のsegment fileのフォーマットに対して

• Key-ValueのPairの並びが、KeyでSortされているという条件
• Mergeされたそれぞれのsegment中には、それぞれのKeyは重複しないという条件

を加えたもの

• Hash Indexを持つlog segmentと比較するメリット

  1. ファイルが利用可能なメモリ量より大きくなっても、segmentのmergeをシンプルに行えるようになる
  2. ファイル中の特定のkeyを探す際に、全てのkeyをmemoryに保持しておく必要がない(Important Point)
     1. 一定のkeyがわかっていれば、その情報からどこのあたりに存在するかを推測することが可能
  3. 読み取りのリクエストの処理では、要求された範囲内にある複数のキーと値のpairをscanしなければならなくなるため、それらのレコードをBlockとしてグループ化し、圧縮することができる
     1. 疎なIn-Memory Indexの各エントリは、圧縮されたブロックの開始地点を指す
     2. 圧縮は、データの領域の削除だけでなくI/Oの帯域削減にもなる

• 書き込みリクエストがどのような順番で呼び出されるかわからない状態で、どのようにKeyごとにSortしてデータを保存するのか？

  • 書き込み要求が来たら、それをインメモリのバランスドツリーデータ構造(red-blackツリーなど)に追加
    • memtable: インメモリツリー
  • memtableが何らかの閾値(通常は数MB)よりも大きくなった場合、SSTableのsegment fileとしてdiskに書き出す
    • このツリー構造はKeyでsortされたKey-Valueペアとして管理されているため効率的に書き出し可能
  • 読み取りのリクエストを処理する場合、そのkeyをmemtable中から探す
    • その次にはdisk上の最新segmentを探す
    • その次に、古いセグメントを探す
    • それでも存在しない場合、データは存在しない
  • 随時merge&compaction処理をbackground処理で時効し、segment fileの結合と上書きされた値や削除された値を破棄

様々なツリー型のデータ構造で実現は可能(red-blackツリー, AVLツリー)

SSTableの問題点

しかし、問題点としては、仮にdatabaseがクラッシュしてしまうと、直近の書き込み(diskに書き出されていないmemtableの内容)が失われてしまう.

• 上記の問題を解決するには？
  • disk上に書き込みを即座に追記する、別のログを持つ(B-Tree Based DatabaseのReDoLogみたいなもの)
    • このログはソート順にはなっていないが、クラッシュ後のmemtableのリストアを目的としたものとして利用可能
    • 一方、B-treeベースのデータベースでは、ログはトランザクションの耐久性を保証するために使用される
  • memtableがSSTableに書き出される度に、対応するログを破棄できる

SSTableのIndex構造は、HashTable時代から存在したlog-structuredファイルシステム上に構築され、**Log-Structured Merge-Tree(LSM-Tree)**と呼ばれるようになった.
ソート済みのファイルのmergeとcompactionという原理を基盤としているStorageEngineは、LSM-Treeと呼ばれる。

具体的なServiceには

• levelDB
• RocksDB
• Cassandra

などのNoSQL Databaseで利用されている.

Elasticsearch, Solrで利用されている全文検索のためのIndexEngineであるLuceneも、term dictonaryを同様の手法で保存されている.

パフォーマンス最適化

• Bloom Filter
  • 確率的なデータ構造の一つで、ある要素が集合に含まれているかどうかを高速に判定するために使用
  • Bloomフィルターは、完璧な正確さを犠牲にして、メモリ効率と速度を最適化
    • 要素が集合に含まれていないことを確実に示すことができるが、要素が集合に含まれていると示す場合、false positiveの可能性があり
• Compaction & Merge Strategy
  • サイズ層別コンパクション(Size-Tiered Compaction):
    • この戦略では、同じサイズのSSTablesが一定の数（例：4つ）に達したときに、それらのSSTablesを一つの大きなSSTableにMerge
      この方法は、書き込みが多いワークロードに適している
  • レベル層別コンパクション(Level-Tiered Compaction):
    • SSTablesは異なる階層に分けられ、各レベルでのSSTableの数やサイズには制限がある
      一つのレベルのSSTableが一定の数を超えた場合、次のレベルのSSTableとMerge
    • この方法は、読み取りが多いワークロードや、一定のディスクスペースを確保したい場合に適している
  • タイムウィンドウコンパクション(Time-Window Compaction):
    • この戦略では、データのタイムスタンプに基づいてSSTablesをMerge
      例えば、1日ごとのSSTablesを一つのSSTableにマージすることができる

B-Tree

B-Treeに関しては、こちらを参照

LSM-Tree & B-Tree 比較

	B-Tree	LSM-Tree
書き込みの増幅	diskへの書き込みが最低2回は書き込みが発生する(WAL&Page)	基本の書き込みは1回のみ
	Pageが分割された場合は、さらに書き込みが必要になる	BackgroundでCompaction&Mergeが発生するため複数の書き込みも発生するがB-Treeに比べて負荷が小さい
Write Throughput	ランダムな書き込みであるためLSM-Treeより遅い	Sequentialな書き込みであるため高速
Data Volume	フラグメンテーションのため未使用のdisk領域が生じる	圧縮率を高めることが可能であるためB-Treeに比べてファイルサイズが小さくなる
	Pageが分割されたり、行が既存のPageに収まらない場合に発生	定期的にCompaction&Mergeが行われれるため未使用領域は削除される
Index	必ず一意になること	Compaction&Mergeはbackgroundで行われるため複数segmentに存在し得る
	トランザクションの管理はkeyの範囲に対するlockを使って実装されているため直接TreeにAtatch可能

InMemory DB

Memcachedのように、インメモリのKey-Value Storeの中にはCacheだけを用途とし、マシンの再起動時にデータを失われても許容する仕様のものもあるが、
基本的に、他のInMemoryDBは耐久性を持つことを目指している

InMemoery DBの耐久性について

• バッテリー駆動のRAMや変更ログをdiskに書くこと
• 定期的にsnapshotをdiskに書くこと
• メモリ内の状態を他のマシンにReplicationすること

などによって、耐久性を実現している.
diskは永続性を持たせるために追記だけを行うログを書くだけにしか行われず、読み込みは全てmemoryから行われる.(まぁInMemoeryなので)

• Relational DB
  • VoltDB, MemSQL, Oracle TimesTen
• Key-Value Store
  • Redis, Couchbase
    • diskへの非同期な書き込みによる弱い耐久性を提供

InMemoryDBのメリット

• メモリ内の構造をdiskに書き込める形式にエンコードするオーバーヘッドが発生しないこと
  • diskから読み取りせずにすむことはそこまで大きなメリットではない
    • disk上のstorage engineであっても、十分なメモリがあれば直近で使われたdisk上のblockをOSがメモリ上にcacheしてくれるためdiskから読み取りする必要がなくなるため
• disk based Index では実装が難しいデータモデルを提供できること
  • Redisは、プライオリティキューや集合といった様々なデータ構造に対するDBのようなInterfaceを提供している

不揮発性メモリ(non-volatile memory, NVM)

InMemoryDBのアーキテクチャを拡張して、disk中心のアーキテクチャのオーバーヘッドを起こすことなく、
利用可能なメモリよう大きなデータセットをサポートする方法が示され始めている

• アンチキャッシング
  • メモリが十分にない場合、最も長く使われていないデータをメモリからdiskに退避
  • 再び退避したデータにアクセスがあった場合、メモリに読み込む

ただこのアプローチでも、indexはmemory-sizeに収まる必要はある

Etc

• 耐久性(ACID特性の一部)について
  • Atomicity: トランザクション内のすべての操作が完全に成功するか、または完全に失敗するかのどちらかであること
  • Consistency: トランザクションの実行前後でデータベースが一貫した状態を保持すること
  • Isolation: 同時に実行される複数のトランザクションが互いに影響を与えないこと
  • Durability: トランザクションが一度コミットされたら、その結果は永続的にデータベースに保存されること

ここでの「耐久性」は、システムの障害が発生した場合でも、コミットされたトランザクションの結果が失われないことを保証する性質を指す