Citation

@inproceedings{10.1145/2168836.2168855,
author = {Mao, Yandong and Kohler, Eddie and Morris, Robert Tappan},
title = {Cache Craftiness for Fast Multicore Key-Value Storage},
year = {2012},
isbn = {9781450312233},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2168836.2168855},
doi = {10.1145/2168836.2168855},
booktitle = {Proceedings of the 7th ACM European Conference on Computer Systems},
pages = {183–196},
numpages = {14},
keywords = {multicore, key-value, persistent, in-memory},
location = {Bern, Switzerland},
series = {EuroSys ’12}
}

どんなもの？

  • 名称: 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節の最後）ということで、ノードごとにバージョンと状態を持ち、もしロック状態だったら解放されるまで待つという戦略を取る。バージョンが変化した場合、再読み込みが必要ということで、ルートから読み直す。

課題

並列ルックアップに対応して、大量のルックアップを効率的に行いたい。