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

ほとんど全てのRDBにおいての標準的なIndexの実装であり続けている.
非リレーショナルなDBでも利用されている.

• SSTableと同様に、B-TreeはKey-ValueのPairをKeyでSortされた状態で保持
  • そのため、Key-ValueのLookupや範囲に対するQueryを効率よく処理できる
• B-Treeは、databaseを固定サイズのBlockあるいはPageに分割する
  • このBlockのサイズは4KB程度
  • 1つのPageが1度に読み書きされる
    • この設計は下位層のハードウェアとの関係性が密になるが、diskもまた固定サイズのblockを並べることによる
  • LSM-Treeで利用されているlog-structured Indexは、databaseを通常数MB以上の可変サイズのセグメントに分割し、常にセグメントをsquentialに書き込む

B-Treeの構造について

各PageはAddressあるいは場所によって識別できるため、あるページから他のページを参照できる(disk上の話)

• Lookup
  1. 1つのPageがB-Treeのルートとなる
     • このIndex中でLookupしたい場合、出発点(Root)となる
  2. 251というkeyを探しているため、200<=key<300のrefを追う
  3. さらに、250<=key<270のrefを追う
  4. 最終的に個別のkeyが格納されているPage(leaf page)にたどり着く
     • leaf pageにはそれぞれのkeyに対する値が含まれているか、もしくはあたいがあるPageへの参照が含まれている

1Page内の子ページへの参照数は**分岐係数(Branching Factor)**と呼ばれる.(図の場合、分岐係数=6となる)

• Update

  1. 対象keyを含むleaf pageを参照
  2. 参照したpage内の値を更新してpageをdiskに書き込む

• Insert

  1. 対象keyをを含む範囲を持つleaf pageを参照
  2. 以下の分岐に分かれる
     • 参照したPageに十分なspaceがある場合
       1. そのPageに追加して、diskに書き込む
     • 参照pageに新しいkeyを受け入れるだけのspaceが存在しない場合
       1. そのPageを半分だけ埋まった2つのPageに分割
       2. 親Pageを配下にできた新しい2つのKeyの範囲に合わせて更新

B-Tree Algorithm

• n個のKeyを持つB-Treeの深さは常に、O(log n)になる
  • Treeはバランスが保たれることを保証されるアルゴリズムであるため
• Page Size 4KB で深さが 4レベルであり、分岐係数が500のTreeは最大256TBを保存できる

ビッグオー記法（Big O notation)

• O(1): 定数時間.入力データのサイズに関係なく、アルゴリズムの実行時間は一定
• O(n): 線形時間.入力データのサイズに比例して、アルゴリズムの実行時間が増加する
• O(n^2 ): 二次時間.入力データのサイズの二乗に比例して、アルゴリズムの実行時間が増加する
• O(logn): 対数時間.入力データのサイズの対数に比例して、アルゴリズムの実行時間が増加する
  • バイナリサーチ（二分探索）など
  • 対数的な成長は、線形的な成長O(n) や二次的な成長 O(n^2) などの他の複雑さの指標と比べて非常に効率的

B-Tree安全性&Performanceについて

B-Tree 耐久性の保証

• データの永続性
  • トランザクションがコミットされた後、そのトランザクションによって行われた変更は永続的に保存され、システムの障害やクラッシュが発生しても失われることはない
• 回復能力
  • システムが障害やクラッシュから回復した場合、データベースは最後にコミットされた状態に復元される必要がある
    • Write-Ahead Log（WAL(redo logとも呼ばれる)）のメカニズムを使用して実現
    • これらのログには、トランザクションの変更内容が記録されていて、障害の後にデータベースを正しい状態に復元するために使用
• データの整合性
  • トランザクションが完了すると、データベースは一貫した状態になる
  • つまり、部分的に完了したトランザクションや中断されたトランザクションによる変更は、データベースに反映されない
• ハードウェア障害の対応
  • ディスク障害やその他のハードウェアの問題が発生した場合でも、耐久性はデータの安全性を保証
    • 冗長性、バックアップ、レプリケーションなどの技術を使用して実現される

Performance

• Key全体ではなく、短縮したKeyを保存することによってPage内の領域を節約
• leaf pageがdisk上でsequantialになるように試みる実装がされている
  • 理由は、一般的にdisk上でpageがどこに配置されるかはわからない
    • そのため、keyの範囲の近くのPageが、disk上でも近くにあるかはわからない(->範囲scanのqueryに対してIO処理に時間がかかる傾向がある)
  • Treeが大きくなるに従って、この順序を保つことは困難になる傾向がある
• Treeに追加のポインタを配置
  • leaf pageの左右に隣接するpageのrefを持たせることで、keyの範囲scan時に、親Pageの参照を不要にできる

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: トランザクションが一度コミットされたら、その結果は永続的にデータベースに保存されること

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