# 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節の最後)ということで、ノードごとにバージョンと状態を持ち、もしロック状態だったら解放されるまで待つという戦略を取る。バージョンが変化した場合、再読み込みが必要ということで、ルートから読み直す。 ## 課題 並列ルックアップに対応して、大量のルックアップを効率的に行いたい。