--- tags: 論文メモ --- # FASTER: A Concurrent Key-Value Store with In-Place Updates - [プロジェクトページ](https://www.microsoft.com/en-us/research/project/faster/) - [論文ダウンロードページ](https://www.microsoft.com/en-us/research/publication/faster-concurrent-key-value-store-place-updates/) - 紹介ブログ: [Microsoft Unveils FASTER – a key-value store for large state management - Microsoft Research Blog](https://www.microsoft.com/en-us/research/blog/microsoft-unveils-faster-key-value-store-large-state-management/) - GitHub: [Microsoft/FASTER](https://github.com/Microsoft/FASTER) ## どんなもの? メモリの容量を超えるデータを保存できる Key-Value ストア。ストレージに書き出すので耐障害性もそこそこある(そこそこを実現するオーバーヘッドがでかいが……)。 ## 先行研究と比べてどこがすごい? 書き込みが集中するワークロードに対しての性能の向上を目指した。 サポートしている書き込み操作: - Upsert (キーに紐づく値をまるっと書き換え) - Read-Modify-Write (例えば、現在の値を 1 インクリメントする) よく更新されるデータについては、メモリ上で In-Place に書き換えを行うことで、あるキーの書き換えが集中するようなワークロードで効率的に更新を行うことができる。 「7.2 Comparison to Existing Systems」では、メモリに収まる範囲において、インメモリ Key-Value ストアである Intel TBB concurrent hash map 以上のベンチマーク結果(Figure 8)を示し、スレッド数に対するスケーラビリティも高い(Figure 9 (a), (b))ことがわかる。 :::info 比較対象について Figure 8 で比較しているものは、すべて Key-Value ストアで、 Intel TBB concurrent hash map と MassTree は完全なインメモリ、 FASTER と RocksDB はストレージに書き出すタイプである。 FASTER は、一部のデータはストレージに書き出すのを遅らせることで In-Place な書き換えを行っているので、局所的な書き換えを行うワークロードではインメモリと同等の性能になるはずである。 RocksDB は書き換えについて、基本的にはメモリ上で実行されるが、ログ構造なので In-Place な書き換えを行わないことと、 7.1 にあるように Write-Ahead Log を有効化しているのでメモリ上への操作もストレージにまずログを書き出してから実行することを考えると、かなり不利になるはずである。 ::: ## 技術や手法のキモはどこ? In-Place な書き換えをスレッドセーフに行うために、 Epoch Framework によるロックを使わない同期の取り方と、 Compare-and-Swap パターンによるアトミックなメモリ操作を徹底している。このことによって、 Figure 9 においてスレッド数を増やしてもリニアなスケールを実現することができている。 また、ストレージへの書き出しを、以上のパターンを守りつつ、さらにハッシュテーブルとの親和性を保ちながら実現するために、完全なログ構造ではなく、一部で In-Place な書き換えを許可する、半ログ構造(HybridLog と呼んでいる)なデータ構造で、キーと値を保存している。 ### 1. Compare-and-Swap パターン (これは、真新しい技術ではなく、よく使われているプログラミングのパターンであるが、 Epoch の説明に必要であることと、 FASTER の高い並行処理性能を支えるキモなので説明を載せておく。) Compare-and-Swap とは、あるポインタが指す値が `comparand` のとき、そのポインタが指す値を `newValue` に置き換えるという処理である。 ```c int CompareAndSwap(int *address, int newValue, int comparand) { // 実際にはこの動作がアトミックに行われる int oldValue = *address; if (oldValue == comparand) { *address = newValue; } return oldValue; } ``` この操作は、最近の CPU では他のスレッドに割り込ませないで実行することができる(LOCK CMPXCHG 命令)ので、アトミックな操作である。 例えば、 Compare-and-Swap パターンを使って、変数 `x` をインクリメントするならば、このように書くことができる。 ```c // (このコードはイメージです。実際にはコンパイラの最適化によって、予想しない動作をするかもしれません。) int x; // 複数のスレッドから読み書きされる変数 while (1) { int oldValue = x; int newValue = oldValue + 1; if (CompareAndSwap(&x, newValue, oldValue) == oldValue) { // 書き換えに成功したので、ループを抜ける break; } else { // もし、戻り値が oldValue と違った場合、 // 他のスレッドによって書き換えられているので、もう一度やり直し continue; } } ``` ### 2. Epoch Framework データの書き換えや削除を行うときには、他のスレッドによって該当データがアクセスされていないことを保証する必要がある。これを実現する方法として、最もよく使われている方法はロックだが、ロックを使用すると、他のスレッドを停止させてしまうことがあり、スレッド数を増加させてもスケールしなくなる。 そこで、スレッドが処理を開始したときに、そのスレッドに Epoch (時代)を割り当てる。すべてのスレッドが、その Epoch 以前にいなくなったとき、その Epoch で発生した削除や変更は、安全に行うことができることが保証される。 Epoch によるガーベジコレクションの戦略の例 - [Lock-freedom without garbage collection · Aaron Turon](https://aturon.github.io/blog/2015/08/27/epoch/) - [サンプルの完全なソースコード(treiber_stack.rs)](https://github.com/crossbeam-rs/crossbeam/blob/02cc10efb351e4a6dfe4efd160dfc2169c9b455a/src/treiber_stack.rs) - [サンプルの完全なソースコード(crossbeam-epoch)](https://github.com/crossbeam-rs/crossbeam-epoch) 上記のリンク先では、スタックをポップしたときにメモリの解放をいつ行うかについて、 Epoch を用いていたが、 FASTER ではこれを一般化し、 Epoch が安全になったことをトリガーとして処理を実行する、 Epoch Framework (プログラム上では LightEpoch と呼ばれている)を導入した。これによりロックを使わずに、データの削除や、 HybridLog の Read-Only Offset の移動を安全に行う仕組みができた。 ### 3. HybridLog FASTER では、すべてメモリ上に乗っかるハッシュテーブルと、実際のキーと値のデータを持つログ構造の 2 つのデータ構造で、 Key-Value ストアを実現している。ハッシュテーブルは、そのハッシュ値が示すキーを独自の仮想アドレス形式で持っている。独自の仮想アドレスは、ストレージ上のデータとメモリ上のデータにまたがっており、このアドレスですべてのデータを指し示すことができる。 仮想アドレス空間は Figure 5 のようになっている。新しいエントリーは右端に追記される。データの更新を行う場合、そのデータが Mutable Region にあるならば、そのデータを直接書き換える。それ以外の領域にある場合は、右端に追記する。ログ構造なので、同じキーのデータが複数の箇所にあることになるが、 Mutable Region にそのキーがある場合、それが最新であり、それ以外の場所にある場合、右にあるもの(アドレスが大きいもの)が新しい。 メモリに乗せるデータ(Read-Only, Mutable)の量は、オプションで指定することができる。また、 Read-Only Region と Mutable Region の割合もオプションで指定することができる。エントリーが追記されると、指定したデータ量と割合を守るため、古いデータから順にメモリから削除され、 Stable Region となる。一度 Read-Only Region に入ったデータは、以降書き換えられることはないので、安全にストレージにコピーすることができる。 :::info Mutable Region の In-Place アップデートについて 現在の実装を見る限り、 FASTER はハッシュテーブルの書き換えについてのスレッドセーフティは保証するが、データの更新のスレッドセーフティは自分で保証する必要があるようだ。したがって、ここで Compare-and-Swap が使えないような大きいデータを扱う場合は、ロックが必要になる可能性がある。 ::: ## 議論はある? ### 1. 障害時の耐久性とパフォーマンス ストレージに書き出されているデータは、 Stable Region のすべてと Read-Only の一部だけである。したがって、障害が発生したときに、 Mutable Region にあったデータは失われることになる(ログ構造なので、書き出されているデータはある時点でのスナップショットにはなっている)。 論文で提案されていた方法: 1. Write-Ahead Log を使う - 明らかにパフォーマンスロス…… 2. 定期的に In-Place アップデートをさせないように(つまり Mutable Region をなくす)して、ストレージに書き出す - In-Place アップデートによるパフォーマンスが半減すると思われる → 耐久性を取ると、少なくとも Evaluation で示したほどの性能は出なくなる ### 2. ログのガーベジコレクション これについても、なかなか雑にしか触れられていなかった。 論文で提案されていた方法: 1. データに期限をつけて、それより前のデータを削除する - ログ構造の利点を生かしているが、使い方にかなり制約がかかる 2. ログを順番に読んで、生きているデータのみを残してログを再構成する - データベースがかなり大きくなったときに、現実的な時間で実行できるのか? # 次に読むべき論文は? - [Cache craftiness for fast multicore key-value storage](https://pdos.csail.mit.edu/papers/masstree:eurosys12.pdf) - 比較にも出てきた Masstree の論文 - Trie 木と B+ 木の組み合わせでできている[らしい](http://db-event.jpn.org/deim2017/papers/387.pdf) - 追記: [読みました](https://hackmd.azyobuzi.net/qAjkcdp8SJmuWrRJ_9nZLQ) ## その他の参考文献 - ログ構造について: [マルレク2014-2015第六回 Amazonのクラウド・データベース Amazon Aurora](https://drive.google.com/file/d/0B04ol8GVySUuX3Q3RzJqWGJMTWs/view) - RocksDB の紹介: [Under the Hood: Building and open-sourcing RocksDB](https://www.facebook.com/notes/facebook-engineering/under-the-hood-building-and-open-sourcing-rocksdb/10151822347683920) - RocksDB のベースとなっている LevelDB について: [SSTable and Log Structured Storage: LevelDB](https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/)