Citation

@inproceedings{10.1145/3299869.3314044,
author = {Carter, Andrew and Rodriguez, Andrew and Yang, Yiming and Meyer, Scott},
title = {Nanosecond Indexing of Graph Data With Hash Maps and VLists},
year = {2019},
isbn = {9781450356435},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3299869.3314044},
doi = {10.1145/3299869.3314044},
booktitle = {Proceedings of the 2019 International Conference on Management of Data},
pages = {623–635},
numpages = {13},
keywords = {triple-store, tuple-store, graph store, schema-last, database},
location = {Amsterdam, Netherlands},
series = {SIGMOD ’19}
}

どんなもの？

LinkedIn のソーシャルグラフワークロードに耐えるためのグラフデータベース設計。ログ型でノード、エッジを記録し、ハッシュマップで索引を作成する。

設計思想（インデックス側）

  • リードを速く
    • そのために、ライターと同期を取らなくても良い仕組み（CPU の処理は 8 バイト単位でアトミックというのを利用）
    • 逆にライターは 1 プロセスのみ
  • 書き込んだらすぐに読み出せる（つまり後で集計すればいいやではない）
  • 木構造は対数オーダーで遅くなるから嫌だ
  • 「AさんはBさんについてCについてすごいと思っている」のように、単純な主語・述語・目的語ではないような構造も持ちたい。でもプロパティという形で持つと自由度があまりにも失われるので、グラフで表したい（Compound）。これについてインデックスを作成したい。

先行研究と比べてどこがすごい？

  • Graphd という似たようなものはあるけれど、 Compound を表現できない
  • L3 キャッシュミスを極限まで減らすカリカリチューニング

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

  • 単純なハッシュマップと、配列リスト（の可変長をうまくやる VList）によるシンプルな構造
  • 小さいインデックス（エッジの少ないノード）は直接、大きいものはエッジだけまとめたインデックスのような、二段構成（メモリキャッシュのため？）
  • 単純な mmap なので、ファイルシステムの恩恵を受けて、安全にリハッシュできる

どうやって有効だと検証した？

マイクロベンチマークにより、グラフが大きくなっても一定時間、12ナノミリ程度でのルックアップができることを確認した。

議論はある？

ライトの速さについてまったく頑張っていないが、ユースケース的に問題ないと主張。

次に読むべき論文は？