FASTER
論文紹介: FASTER: A Concurrent Key-Value Store with In-Place Updates
TL;DR
大量のデータがモバイル/IoT機器/ブラウザ/etc..から生成され，保存され，計算されている．これらをステートという
ステートを保持するためのストレージとしては，RDB/KVS/Streaming DBなどが使われている
どれも性能が低い．数百万Request/Sec(RPS)出れば御の字
そこで，Microsoftから高速なKVSを提案する．
Make the common case fastを設計原則とする．
Reference
FASTER: A Concurrent Key-Value Store with In-Place Updates Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, Mike Barnett 2018 ACM SIGMOD International Conference on Management of Data (SIGMOD '18), Houston, TX, USA ACM June 10, 2018
Link: https://www.microsoft.com/en-us/research/project/faster/#!publications
Abstract/Introduction
State management is an important problem for all these applications and services.
ブラウザ，サーバ，モバイルデバイスといった，エッジからのデータ量が増え続けている．
これらのデータは，それ自体はただのログであったり，何かしらの状態:ステートを表現している簡単な文字列/数値．
データはクラウド上にストレージされ，意思決定のための分析に使われることが多い
分析はオンライン/リアルタイムであることが望ましい．
i.e. ストレージがボトルネックであってはならない．
Unique characteristics of state management
Large State: メモリに載り切らない．数十億ユーザのクリックログなど．
Update-Intensively: 更新処理の比率が高い．Insert/Readは普通．
Locality: アクセスパターンが冪分布であったりと局所性が高い．
10億のユーザデータを扱っていようと，今ログイン中の1万人のデータしか更新しないはず．
Point Operations: あるKeyに対応するValueを更新/検索，というケースが殆ど．
「Keyの範囲がn~mのもの」 といったいわゆるRange Queryはあまり実行されないと仮定する．
仮にされるにしても，追加のインデックスや統計情報などを作ることで代用可能なケースが殆どだとする．
この仮定は重要．HTAPなどが盛り上がっているSIGMODの雰囲気とかなり異なると思う
KVSの現状
多くのKVSは「単なるupdate onlyでも」数百万updates/secondしか出ない．
Hot setだけに限って実行し，全データがメモリに載っていてもこの程度．
Redis/Memcachedあたりも，リカバリが弱いにも関わらず性能は低い．
と，満足いくKVSが現状ない．
分割とLocality
KVSをスケールさせるシンプルなやり方としては，パーティションやシャーディングがある．
マシンを分散させて，各ノードのメモリにデータを分割して持たせること．
しかし，実際にはLocailityがあるから，殆ど数台のマシンにアクセスが集中してしまう．
結局はその数台がボトルネックになる．
同じKeyのValueを複数のマシンにもたせて，更新をマルチマスタで受け付ける，のはもっと難しい．
分散合意のような仕組みが必要になってくる．障害復旧の仕組みも厳しい．
FASTER
以上の問題を解決するKVSとしてFASTERを提案する．
Faster follows the design philosophy of making the common case fast.
FASTERは，実験の結果，160M(1.6兆!)Ops/secの処理能力を達成した．
Interface of FASTER
Read
Blind Write: x = 1 のようなクエリ
Read Modify Write(RMW): x++, x = x*2 のような現在の値を参照し変更するクエリ
Blind WriteとRMWのインタフェースを分ける，というのはかなり重要な設計判断．
RMWはReadとBlind Writeの組み合わせでも本来は実装できるのに，分けている．
FASTERでは，Single Keyの操作しか許さず，かつRMWをアトミック処理とする，ということ．
Key Contribution
1. generic framework that facilitates epoch-based synchronization
Siloなどで使われている，近年非常に流行っている，スレッドセーフなオブジェクト再利用手法．
GC等に使われる．
# (個人的に) Contributionとは言い難い．frameworkというならそれのみで公開してほしい
2. concurrent latch-free resizable cache-friendly hash index
Concurrent Hashtableは昔からずっと研究されてきて，多くの実装が提案されてきた．
この論文では，伝統的なチェイン法(Chaining)をベースにしている
かなり細かい実装レベルでの最適化を提案している．
3. HybridLog
FASTERはログ構造化(Log-Structured)手法を採用している．
全ての書込みでバッファを追記していき，それをそのまま永続化するとログになるというもの．
ディスクI/Oが全てシーケンシャルアクセスになるので，多くのKVSが採用している．
全ての書込みがRead-Copy Update(RCU)となる．
しかし，RCUにおいてはメモリアロケーションが性能のボトルネックになる．
常に追記する，ということは，常にmallocするということ．
可能なら可能な限りIn-Place Updateをすると性能が出る．
が，In-Place updateのみだと，メモリから溢れたら対処できないし，永続化のためのログも書けない．
HybridLogは，in-placeとread-copy-updateをうまく切り替えるアルゴリズム．
Hot Recordはin-placeに，Cold RecordはRCUで処理する．
前提とするCPU命令
なお，ここから前提とするアトミック命令は以下．以下が実装されているCPU上で動くものとする．
Compare and Swap(CAS)
Fetch and Add(XADD)
Fetch and Increment
FASTER Overview
https://gyazo.com/c757c07630ecc6ffd7ffb6a25900fdd7
後で詳述するが，概要を示す
Hash Index
シンプルなチェイン法(Chainingのハッシュテーブル．
チェイン法は簡単に言うと以下
テーブルはシンプルな配列．table
ハッシュ関数にかけてインデックスiを得て，table[i]からレコードに飛ぶ．
(PHFでなければ)インデックスは衝突しうるため，レコードは線形リスト．
線形リストを走査して，Keyが一致するレコードが見つかれば終わり．
テーブル配列のサイズが重要パラメータ．
table.size() == 1のとき確定で$ O(n)かかる．うまく設計できれば平均で$ O(1)．
Hash Indexの最適化
ハッシュテーブルの各バケット(配列の要素)を，CPUキャッシュラインのサイズに揃える．
つまり64bytesにする.
異なるインデックスのエントリが同じキャッシュラインに乗っていると，False Sharing(偽共有)が起こる
同じインデックスは同じキャッシュラインに乗せてやれば，この性能劣化を防げる
各バケットは64bytesの中に複数のエントリを持つ
エントリにはそれぞれRecordsへのポインタが入っている
このへんは後述
Records
各エントリは以下のデータを持つ．
Key
KVSとしてのKey
可変長でも固定長でもOK
Value
Header
メタデータ．
前のレコード(つまりLinked Listにおける次のレコード)へのポインタ
Recordsの最適化
普通はHash Indexのほうにkeyを置くが，FASTERではエントリのほうに入っている
# 確かに，B-Treeとか，普通のインデックスだとKeyがIndexに入る．
それだと，Keyが可変長なので，Hash Indexのサイズが揃わず，キャッシュ効率が下がる．
Hash Indexは全スレッドで共用するので，キャッシュに残り続けるのが重要
Allocators
三種類書かれているが，In-memoryとAppend-onlyは既存手法で，HybridLogが本丸．
以下，三種類それぞれの説明
In-memory Allocator: メモリ上で，レコードをLatch-FreeかつIn-Placeに更新する．
つまり永続化を考えない．普通のmallocと同じ．memcached的な感じ
Append-only log structored Allocator: メモリ量より大きなデータを扱うために使う．Latch-Free．Not In-Place.
Hybrid-Log Allocator: メモリ量より大きなデータを扱うために使う．Latch-Free. Hybrid.
Contributions
この論文のContributionは以下．
1. Epoch Framework
2. Hash Index
3. HyblidLog
それぞれ説明する．
1. Epoch Framework
FASTERのkey design principleは，
avoid expensive coordination between threads in the common fast access path.
つまり，各スレッドが基本的に何の同期もなく独立に命令を実行できることを目指す．
しかし，システム全体でstateを同期する何らかの仕組みは必要となる．
あるKeyについて任意の時点で何かしらの値で合意できなければデータベースですらない．
この両者を達成するため，multi-threaded epoch protectionを使う．
Silo(SOSP'13)，Masstree(Eurosys'12)，Bw-Tree(SIGMOD'13)が使っているやつ
他のデータベースや並列処理システムに流用可能なよう一般化した．
Epoch Basics
システム全体でアトミックなカウンタ$ Eを共有する．current epochなどと呼ぶ．
あらゆるスレッドからインクリメントできる．
# ただし，インクリメントしかできない
全スレッド$ Tがスレッドローカルな$ Eのコピーを持っている．$ E_Tと記す．
適当なタイミングで更新される．つまり$ E_T \le E．
全スレッドのスレッドローカルな$ E_Tはshared epoch tableという構造体に入っている．
1スレッドあたりキャッシュラインを1つ使う(パディングする)ため，スレッドセーフ．
あるEpochの値$ cについて，$ \forall\ T: E_T > cなら，$ cはsafeと呼ぶ．
システム全体で共有する変数として，$ Eに加えて$ E_sも用意する．
これは$ cの中で最大の値．
すなわち「全スレッドの$ E_Tの最小値 -1」．
$ \forall\ T: E_s < E_T \le E
Trigger Actions
Epoch BasicsはよくあるEpochのシステムで，一般的だ．
が，「カウンタを何に用いるのか」が一般化されていなかった．
Silo(SOSP'13)ではグループコミットのために使っている．
他のデータ構造等ではQSBRとしてガベージコレクションのために使っていることが多い．
そこで，drain-listというものを作る．
これは{epoch, action} からなるリスト．
action はコールバック関数．
epoch が safe になった際に実行することを要求する．
$ E_sが更新されるたびにdrain-listを走査して， $ epoch < E_sならactionを実行する．
drain-listは配列で実装する．
action の実行時にはCompare and Swap(CAS)を用いる．
これによりコールバック関数はExactly-Onceで実行される．
さらに，Epoch Frameworkのインタフェースとして，以下を定義する．
Acquire: 新しいエントリをEpoch Tableに作り，$ Eをコピーして$ E_Tをセットする
Release: Epoch Tableから自分を削除する
Refresh: $ Eをコピーして$ E_Tをセットする．$ E_sを更新する
BumpEpooch(action): $ Eをインクリメントして，元の値$ eについて {e, action}をdrain-listに追加
たとえば，何らかのstatusをupdateするactive-nowというメソッドがあるとする．
$ Eが1とすると，
0. active-nowによりstatusをupdateする．
1. BumpEpoch(active-now)を呼び，$ E := 2とされ，{1, active-now}がdrain-listに入る
2. $ 1 < E_sになるまでは，全スレッドがRefreshしていないので，active-nowの結果が全員に受け取られた保証はない．待つ．
3. $ 1 < E_sになれば，全スレッドがこのstatusの変更を受け取れたことになるので，drain-listから削除しコールバックする．
4. 全スレッドが同じstatusを共有したまま更新ができた．
このように，Epoch Frameworkを使えば，「ある操作について，他の全スレッドが確認したあとでコールバックを実行する」ことができる．
具体的には，FASTERではこれを以下の用途で使っている．
ガベージコレクション
QSBRライクに，「新しい値(削除済みフラグなど)」を挿入してBump」->「$ E_s以下の値を削除」ができる
インデックスのリサイズ
ページのFlushに使うバッファのメンテナンス
Shared log page boundaryのメンテナンス
Checkpointing
2. Hash Index
おさらい:
FASTERのインデックスは長さ$ 2^kの配列で，各要素のサイズは64byte．
で，$ kはパラメータ．
各64byte要素のうち，7 * 8 bytesはそれぞれエントリに使われている．
最後の8bytesは，overflow pointerとして使う．
https://gyazo.com/1808a99fad1455eecf4036c9fc353bfc
最適化:
Hash Bucketが64bytes:
キャッシュラインのサイズと揃えることで偽共有(False Sharing)をなくす
Entryが8bytes:
64bitなので，エントリごとにアトミック命令が使える．
Recordへのポインタが48bit:
Intel x86ではポインタは48bitしか使わないので，64bitマシンといえども実際には48bitでいい
各Entryの余った16bitのうち，1bitをTentative Bitに使う．これはLock-Freeな挿入に必要
残り15bitをtagに使う．
これにKeyの先頭15bitを保存する．
各Entryの指すRecordに飛ばなくても，前方一致でKeyをある程度まで探すことができるのが大きい．
メモリアクセスを減らせる．
操作の例
Read(key)として，h = Hash(key)でハッシュされたインデックス$ hを得る．
kビットしかインデックスには使わない．hk = h[0..k]とする
index[hk]の64bytesが該当するhash bucket．
h[k..k+15]をtagsとして扱う．
for(int i=0; i < 64; i += 8) { return (&index[hk] + i) if (index[hk] + i).tags == key[0..15) }で検索
Insert Bug
複数のスレッドが同時にInsertを行うと，問題が起こりうる．
1. Entryの空きスロット(たとえば末尾)を探し，CASして挿入する．
2. 他のスレッドが，空きスロットを作る．
3. 他のスレッドが，その空きスロットに，同じKeyを挿入する
https://gyazo.com/1e2034a905ca4b6c0a9359032ba378fc
Insert Bug 対策
先ほど取っておいたtentative bitを使う．
tentative bitを立ててinsertする．
insertした後にもう一度bucketをscanして，同じentryが並行挿入されているか見る．
tentativeな$ g_5が発見されなければtentative bitを寝かす．
# Phantom対策として，「二回スキャン」は一般的．キャッシュフレンドリでもある．
3. HybridLog
メモリアロケータであるHyblidLogについて，おさらいすると，
メモリサイズを超えるデータを扱うので，あふれた分は永続化しなければならない
ログも書く．リカバリが出来る必要がある
これらを一体化させたLog-Strucuturedなアルゴリズムであると良さそう
だが，毎回追記をしていると，Read-Copy-Updateになるので，キャッシュ効率が悪い
という問題があった．
Logical Address Space
まず，FASTERの論理アドレス空間を定義する．
この論理アドレス空間で，メモリと二次記憶のどちらのデータもカバーする．
この空間は48bit，つまり$ 2^{48}のサイズとする．アロケータは全てこの範囲内のアドレスを返す．
論理アドレス空間の管理変数
tail offset
Logical Address(LA) 0 から，next free addressまでのオフセットを指す．
head offset
lowest logical address that is available in memory を指す．
つまり，「メモリ領域と二次記憶領域との境界」を示す．
Figure 4
https://gyazo.com/87180c683f6e5b02affe1e100497aa77
The circular buffer is a linear array of fixed-size page frames, each of size $ 2^F bytes,
that are each allocated sector-aligned with the underlying storage device,
in order to allow unbuffered reads and writes without additional memory copies.
# うーんわからん．
Allocationの操作
新しいレコードのアロケーションは常にtail offsetを更新することで行う．
tail offsetは64bitで，内訳として二つの変数を管理している(つまり32bitずつ)．
page number:
offset
各スレッドはoffsetをfetch-and-addして自分の欲しいだけのメモリ領域を得る．
もしも現在のページの空きサイズが足りないなら，page numberをfetch and addする．
page numberをfetch and addするときに，head offsetを更新して，1ページ永続化する．
永続化に関するメタデータ
永続化については更に二つの配列が必要となる．
flush-status
あるページが既に二次記憶にflushされているか，のフラグ管理をする．
closed-status
あるページをflushしてもよいか，というステータスを管理する．
あるrecordがlogとして二次記憶に追記された場合，そのrecordはimmutableである．
Epoch Frameworkとの連動
0. tail offsetを更新することでメモリ領域を確保していく．
1. tail offsetがページ境界を超えて新しいページ$ p+1に突入する．
2. BumpActionで全スレッドに対してsafetyに，このページ$ pをflushする．
これにより，$ pにまだ書込み中のスレッドの書込みが全て終了したことを保証できる．
しかし，このflush作業中に$ pを読込み中のスレッドがいないことを保証する必要がある．
伝統的なDBのやり方だと，バッファプールから二次記憶に退避するときはロックを使うのだが，当然非効率．
そこで，さらにBumpActionで closed-status配列を更新する．
$ pインデックスのフラグを立てることで，「このページはもうすぐflushされます，読めません」と示す
さらに，永続化が終わったら，head offsetを更新し，このページが二次記憶にあることを示す．
要約すると，closed-status更新-> flush -> head offset更新．
3. flush-status配列のインデックス$ pをflushedにする．
4. そうやってmallocしているとtail offsetが肥大化していく．古いpageはだいたいメモリからevictされているはずだ．
個人的に気になること
head offsetから，インメモリのページにデータが存在すると判断したとする．
しかし，closed-statusから，いまflush中のページであることが分かったとする．
このページは読んでいけないわけだが，まだflushも完了していないとする．
となると待つしかないわけだが...Latch-Freeになるのだろうか．
Enabling In-place Update
HybridLog is a novel data structure that combines in-place updates (in memory) and log-structured organization (on disk) while providing latch-free concurrent access to records.
ここまでのAllocatorのデザインは典型的なLog Structuredなもの．
Latch-Freeかつメモリ量を超えるデータを扱える．
データの永続化も必ずメモリ上で連続した領域で行われるため，シーケンシャルアクセスとなりI/O帯域も有効に使える．
しかし，実際にはコストが高い．
あらゆるupdate がtail offsetへのfetch-and-add命令を呼ぶ．
updateが増えれば，結局ページの永続化のためのI/Oがボトルネックになる．
Append Only and In-place Update
Append-Onlyだけでなく，なるべくIn-Placeに更新したい．
更新頻度を鑑みて，Hot SetはIn-placeに更新したい．
頻繁にアクセスされるデータなら，キャッシュの更新だけで済む．
レコードの一部分を更新する，という処理が出来ると良い．
ドキュメントDBなどではレコードが肥大化しがち．
Append-Onlyだと全コピーしないといけないのでコストが高い．
In-Placeに更新すれば安い．
HybridLogの提案
そこで，Appned-OnlyとIn-Place Updateを両方行えるHybridLogというものを考える．
HybridLogでは，Figure 4にさらに変更を加え，論理アドレスは三つに分割される．
https://gyazo.com/479e82f59f7aa5e1425ebff7d75b109e
stable region
二次記憶にある．
read-only region
メモリ上にあるが，Readしか許されない．
mutable region
メモリ上にあり，In-PlaceにRead/Update可能．
HybridLogの管理変数
以下の変数で管理する．新設するのは read-only offset.
tail offset
head offset
read-only offset
read-only regionを示すためのoffset
head offsetと同じく，tail offsetがページ境界を超えた際(page number更新時)に1ページずつ更新していく
Epoch Frameworkによって安全にFlushできる
read-only offsetの更新をEpoch Frameworkによって全スレッドに通知した後にflushすればよい
そうすれば，他の全スレッドはこの論理アドレスを与えられた際にはstable regionを参照するから．
flushが終わったらGCする．
実質このフラグはSec.5の closed-status配列と同じ役割になっている
read-only offsetとtail offsetの間のメモリ領域をどれだけ取るか，はアクセスパターンによって調整すればよい
実質的に二次記憶とmutable メモリとの間のキャッシュのような役割を果たしている
Updating stable or read-only regions
stable regionあるいはRead-Only Regionにあるレコードをupdateしたい場合は，Read Copy Update(RCU)する．
まず現在の値をreadする．stable regionの場合は非同期I/Oを発行する．
mutable regionに現在の値をコピーした新しいレコードを作り，それをupdateする．
Linked Listを更新することになる．
Table 1
https://gyazo.com/cf2a68f4ec1a754b397d133fad8599aa
Lost Update Anomaly
以下のようなシナリオを考える．$ T_{1..4}は全員RMW命令を使ってインクリメントをするものとする．
https://gyazo.com/d6fcd0417825b7c501e6193924774553
1. $ T_1と$ T_3はそれぞれ同じレコードへの論理アドレス$ Lを得た．
2. $ T_1はさらにread only offsetを読みだす．$ R_1とする．
3. $ R_1 < Lなのでin-place updateできそうと判断する．
4. しかしこのタイミングで，$ T_2によりread only offsetが動いた．$ R_2とする．
他のRead-Only/Stable レコードを更新した，ということ．
5. $ T_3は$ R_2を読みだす．
6. $ L < R_2 になってしまっていて，$ T_3はin-place updateはできないと判断する．
7. $ L'に新しいレコードを作る．元の値が4なら，インクリメントして，5とする．
8. $ T_1も，4を観測して5を書き込んでいる...
これはいわゆるLost Update Anomaly．
Lost Update Anomaly対策
これを回避するために，read only offsetにread lockの機能を持たせる，などがナイーブには思いつく．
そうすれば，read only offsetを読んでいるスレッドがいる間は，offsetは動かせない．
しかし，このようなロックの仕組みはコストが高い上に，read only offsetをほとんど動かせなくなってしまう．
よりベターな対策
そもそも，この例では，$ T_1がin-place updateをするという判断をしなければよい．
そこで，safe read-only offsetという新しいmarkerを作る．
このmarkerは，「全スレッドが確認したread only offsetの中で最小の値」を保持している．
このマーカーによってHyblidLogは4 regionsになる．
safe read-only regionは，安全にRCUできる．
これまでread-only regionと呼んでいたregionは fuzzy regionと呼ぶ．
fuzzy regionは，自身からはread-only regionだが，他のスレッドはmutableだと思っている可能性がある
https://gyazo.com/80099e26a1a85f2da0b00f143c6eae05
Fuzzy Region
Fuzzy Regionのおかげで，問題は解決する．
1. たとえば$ T_4が最も高いread-only offsetを観測していたとする．
2. $ T_3はread-only offsetとしてだいぶ古い値を観測している．
safe read-only offsetは，$ T_3が最後に更新している．
つまり$ T_3にはfuzzy regionはない．
3. safe read-only以下のアドレスのレコードに対する更新は，Read-Copy-Updateすればよい．
Fuzzy Regionによる処理の分岐
さらに，fuzzy regionに存在するレコードを更新するときは，以下のように分岐する．
Blind Update
もとのvalueを読まない書込み．
Read-Copy-Update方式で新しいValueを作って良い．
同時に起きたIn-Place Updateの結果が消滅する(Lost Update Anomalyが起こる)可能性がある．
あるが，起こったとしてもアプリケーションのセマンティクスに違反しない．
つまりMVSRだと言っている．
Since the updates are issued concurrently, semantics of the application must allow all possible serial orders.
この原則はSafe Read-Only regionだろうがstable regionだろうが同じ．
Read Modify Write
他のスレッドとConcurrentに実行された場合，Anomalyが起こって困る．
よって，safe and read-onlyになるまで待つしかない．
pending queue(非同期I/Oの時に使うものと同じ？)にキューイングして，後で実行する．
CRDTs
CRDTのデータタイプであることがクエリで示されている(mergeableフラグが立っている)場合．
Blind Updateの際と同じように，Read Copy Update方式で新しいValueを作る．
ここではValueに差分を書き込む．値ではない．
Readが来たら，差分をマージしていけばよい．CRDTなら結果整合性がとれる．
https://gyazo.com/d92324f85c171bfdca906fe3e0620e61
Analysis of the Hybird Log
FASTERの性能はインメモリ上の領域(stable region以外のregions)に大きく影響される．
offsetの使い方が重要となる．
要するにキャッシュアルゴリズムのような動きをしていることになる．
これまでのバッファ管理/キャッシュ操作のアルゴリズムとしては以下がある
FIFO(First in First out)
CLOCK
LRU(Least Recently Used)
LRU-K
HybridLogはSecond-Chance FIFOプロトコルに似ている．
これらのキャッシュアルゴリズムとの比較実験がSec 7.5で行われている．
Hybrid Logのサイズ
mutableやread-only regionのサイズ決定は非常に重要．
mutable regionを0にすれば，すべての更新がRCUとなる．
read-only regionの大きさは，second chanceの長さに影響する．
mutable regionでとにかくhotに更新されたレコードも，いずれはread-only regionに落ちてしまう．
このとき，fuzzy/read-only regionに長さがあれば，メモリ上にあるうちに，またRCUでmutable regionの先頭に来れる．
短いと，stable regionに落ち，二次記憶に書きだされてしまう．
しかし，read-only regionが長過ぎると，本来mutableにできたはずの領域でRCUすることになり，メモリ効率が悪い．
以上から，90:10の割合でmutable / read-only regionの長さを決定した．
この結論に至った評価実験はSec 7.4.2で行われている．
EVALUATION
https://gyazo.com/f3cd441cdb654902598acd46d21f3112
OSSとの比較
OSS公開されているハッシュテーブルとの比較．
Redisとの比較は定量評価にならない．
Redisはマルチプロセスで，ネットワーク越しにスケールすることを想定している
対してFASTERはシングルプロセス，マルチスレッドで，分散システムではない．
実験設定
データサイズがメモリに乗りきるという前提で勝負．
つまりHyblid LogのStable Regionまでアドレス空間が伸びない．
永続化されない．
56スレッドでの実験で，軒並み勝利．
Intel TBBはConcurrent HashMapのライブラリで，永続化無し．これに勝っているのは凄い．
一様分布(uniform)だとTBBもなかなか．
ジップ分布(Zipfian)だとHash Indexのキャッシュ効率が良いのか，FASTERが強い．
OSSのの比較: Varibale threads
https://gyazo.com/ef5d31db8b82f9f54b7ffb418b6504b2
スレッド数を変化させた実験．
FASTERはマルチソケット(31~60スレッド)になっても性能が落ちにくい．
https://gyazo.com/3ed6a0bfd9da3e7b9a330572d5834f43
Append-OnlyよりHyblidLogのほうが性能が圧倒的に出る．
https://gyazo.com/c0c822c86b84bb615da089e7a3a7c57c
他のキャッシュアルゴリズムとの比較．
一様分布ではほぼ差がない．
zipfianやhot-setといった分布が異なるアルゴリズムでは，FIFOには勝つが他のアルゴリズムには負けている．
mutable regionとread-only regionの二つに同じデータが入っていることがあって，キャッシュ効率が悪い．
しかし，latch-freeであることと統計情報を必要としないことから，そんなに悪くないのでは，と謳っている
#papers