Citation

@InProceedings{chandramouli2018faster,
author = {Chandramouli, Badrish and Prasaad, Guna and Kossmann, Donald and Levandoski, Justin and Hunter, James and Barnett, Mike},
title = {FASTER: A Concurrent Key-Value Store with In-Place Updates},
booktitle = {2018 ACM SIGMOD International Conference on Management of Data (SIGMOD '18), Houston, TX, USA},
year = {2018},
month = {June},
abstract = {Over the last decade, there has been a tremendous growth in data-intensive applications and services in the cloud. Data is created on a variety of edge sources, e.g., devices, browsers, and servers, and processed by cloud applications to gain insights or take decisions. Applications and services either work on collected data, or monitor and process data in real time. These applications are typically update intensive and involve a large amount of state beyond what can fit in main memory. However, they display significant temporal locality in their access pattern. This paper presents FASTER, a new key-value store for point operations. FASTER combines a highly cache-optimized concurrent hash index with a "hybrid log": a concurrent log-structured record store that spans main memory and storage, while supporting fast in-place updates of the hot set in memory. FASTER extends the standard key-value store interface to handle read-modify-writes, blind updates, and CRDT-based updates. Experiments show that FASTER achieves orders-of-magnitude better throughput - up to 160M operations per second on a single machine - than alternative systems deployed widely today, and exceeds the performance of pure in-memory data structures when the workload fits in memory.},
publisher = {ACM},
url = {https://www.microsoft.com/en-us/research/publication/faster-concurrent-key-value-store-place-updates/},
edition = {2018 ACM SIGMOD International Conference on Management of Data (SIGMOD '18), Houston, TX, USA},
}

どんなもの？

メモリの容量を超えるデータを保存できる 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)）ことがわかる。

技術や手法のキモはどこ？

In-Place な書き換えをスレッドセーフに行うために、 Epoch Framework によるロックを使わない同期の取り方と、 Compare-and-Swap パターンによるアトミックなメモリ操作を徹底している。このことによって、 Figure 9 においてスレッド数を増やしてもリニアなスケールを実現することができている。

また、ストレージへの書き出しを、以上のパターンを守りつつ、さらにハッシュテーブルとの親和性を保ちながら実現するために、完全なログ構造ではなく、一部で In-Place な書き換えを許可する、半ログ構造（HybridLog と呼んでいる）なデータ構造で、キーと値を保存している。

1. Compare-and-Swap パターン

（これは、真新しい技術ではなく、よく使われているプログラミングのパターンであるが、 Epoch の説明に必要であることと、 FASTER の高い並行処理性能を支えるキモなので説明を載せておく。）

Compare-and-Swap とは、あるポインタが指す値が comparand のとき、そのポインタが指す値を newValue に置き換えるという処理である。

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 をインクリメントするならば、このように書くことができる。

// （このコードはイメージです。実際にはコンパイラの最適化によって、予想しない動作をするかもしれません。）
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 によるガーベジコレクションの戦略の例

上記のリンク先では、スタックをポップしたときにメモリの解放をいつ行うかについて、 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 に入ったデータは、以降書き換えられることはないので、安全にストレージにコピーすることができる。

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. ログを順番に読んで、生きているデータのみを残してログを再構成する
    • データベースがかなり大きくなったときに、現実的な時間で実行できるのか？

次に読むべき論文は？

その他の参考文献