# Cache Craftiness for Fast Multicore Key-Value Storage
- [PDF](https://pdos.csail.mit.edu/papers/masstree:eurosys12.pdf)
- 著者による実装: [kohler/masstree-beta](https://github.com/kohler/masstree-beta)
- 比較対象: [FASTER: A Concurrent Key-Value Store with In-Place Updates](https://hackmd.azyobuzi.net/kqtulmx7S8CrgA9zQ8HULg)
## どんなもの?
- 名称: Masstree
- 速いインメモリ Key-Value Store
- 並行実行してもスケールすること
- 特にメモリアクセスの遅さに注目して、キャッシュに乗りやすい構成に
- キーの長さは可変長
- キーの範囲を指定してデータを取得することができる
- 実際のワークロードでは、キーの前方が一致することがよくあることに注目
## 先行研究との比較
### ハッシュテーブルとの比較
ハッシュテーブルは、キーに対するデータの取得が O(1) で行え、最速の方法である。しかし、例えばキーが i 以上 j 以下の範囲の値をすべて取得する、といった操作を行うのは困難である。
### B+木との比較
ロックの要らないB+木として、 PALM があったが、キーが固定長である必要があった。
## この技術の重要なポイント
### 構造
Masstreeは、Trie木(interior node)と、B+木の葉(border node)を組み合わせた木構造である(Figure 1)。各レイヤーは、1個以上の border node と0個以上の border node を持つ。
1レイヤーでキーの8バイトを表し、 interior node によって、前方が一致するキー同士が同じ枝を通る構造になっている。
border node に含まれるキーは、メモリ上の近い場所に置かれるので、キャッシュが有効に働く。また、兄弟ノード同士が二重リンクリストになっているので、範囲検索にはこれを使うことができる(これはB+木の利点)。
### 並行処理のための工夫
著者の主張によれば、 Compare-and-Swap しても、どうせメモリバリアでオーバーヘッドがあるんだし、スピンロックでもいいでしょ(4.5節の最後)ということで、ノードごとにバージョンと状態を持ち、もしロック状態だったら解放されるまで待つという戦略を取る。バージョンが変化した場合、再読み込みが必要ということで、ルートから読み直す。
## 課題
並列ルックアップに対応して、大量のルックアップを効率的に行いたい。