Cicada：Dependably Fast Multi-Core In-Memory Transactions

Cicada: Dependably Fast Multi-Core In-Memory Transactions
https://www.cs.cmu.edu/~hl/papers/cicada-sigmod2017.pdf

SIGMOD2017で発表されている。現状の分散OLTPのアーキテクチャをうまくまとめて、欠点をうまくカバーアップし、言って見れば次世代MVCCの一つの形を提示している。その上で、現在世界最高のパフォーマンスを叩き出している。現時点で世界最速DB（ただし自称）。

現状の分散OLTPは大きな流れは、SILO/Foedus/MOCC/等のOCC系、すなわち2PLをベースにした実装で理論上はmonoversionでのserializableの実現を行っている方式と、Hekaton/HyPer/Bohm/ERMIAといったMVCC系、すなわちMVTOの派生をベースにしてmultiversionでのserializableの実現を行っている方式の二つがある。

現在のところはOCC系の方が若干優位で、ベンチマークも含めてパフォーマンスがでている。MVCC系は劣勢ではある。そんな中で、CicadaはMVCC系のリファレンス実装として提示され、OCC系を上回るパフォーマンスを出している。

まず、論文のOCC/MVCCのまとめを再整理し、Cicda自体の中身も整理する。以下の記述は論文を参照しながら自分の意見も書いているので、Cicadaの論文通りではない。なお、以降は、論文を片手に読むことを強く推奨する。最低限の前提はMVCCとMVTO。

■OCC/MVCCまとめ
整理はChapter2になる。

□Optimistic Concurrency Control
基本的に3phaseアプローチで、read phaseで共有メモリーからreadとローカルメモリーへのwriteを実行、次のvalidation phaseでconsistencyをチェック、最後のwrite phaseでコミットを実行する。実行後に他のtransaction(注：以下tx)から値が見える。(注：ただしglobalな非同期barrierのepochを設定している場合は実際は4phase)

最近のOCCは1-version-in-placeのアーキテクチャになっていて、GCをきわめてライトにしている。なお、read-only用にconsistent snapshotは準備する（ただし、少しだけstaleにはなる）。またwriteはin placeだがメモリー上は別の場所を確保し、古い値はそのままGCする。

Strength
・Lock free read
Validation phaseで多少時間をとるが、基本的にreadはwriteにブロックされない。当然concurrencyも上がる。特にmany-core/in memoryでは、uncommittedではあってもlocalに値がcacheされるので、cache missが減る。また 1-version-in-placeはオーバーヘッドが少ないので、特に競合がない状態では高いパフォーマンスを出す。（注：このあたりは同じくreadはロックしないとはいえ、versionサーチで手間取るMVCCよりも原理的に高速）

Weakness
・Frequent aborts
楽観処理なので当然競合が上がればabort率はあがる。また1VCCだと最新versionだけが扱われるので、ますますコンフリクトを起こす。abortはコストが高い。CPUは食うし、キャッシュラインが汚れる。さらにOCCだとオーバーヘッドがない分どんどんretryするので、さらにヒドイことになる。

今のところはちょっと有効な手立てがない。TicTocはtransaction orderを柔軟に変更することでabortを抑えているが、concurrentな更新があると以前のversionへのアクセスができなくなる。

Read-only snapshotは抜本的な解決にならない。r-wなtxでは当然使えない。また得られるメリットが10%向上程度なので、そもそもOCCの低いオーバーヘッドには見合わない。snapshotの作成インターバルが1secぐらいの粗い粒度なのでstalenessが高く、利用価値が薄い。

・Extra reads
あんまり知られてない欠点。ロックしないのでread phaseで同時書き込みが可能になる。in-place updateの場合、何もしないと、パーシャルライトを読んだり、repeatリードで違う値を拾ったり、可変長データで不正アクセスしたりするので、そうしないように リードするときにローカルコピーをとる。これはextra readになりレコードセットが大きい場合はコストになる。

・Index contention
新しいレコードを生成する（write）とき、indexに登録して、当然コミットされるまでは他から見えないようにロックをとる。このearly index updateはユニークキー制約の保証の仕組みになるし、indexの変更を現在は走っているtxに見せるときに簡潔に処理できる。しかし、abortされるような変更があったりする場合は競合が発生する。いずれにしろ、read phaseでのindex updateはそもそもglobal updateを避けよという原則に反するので、いろいろ問題。

基本的にOCCの弱点はそもそも1VCC由来。OCCはコア間の通信削減に有用だし、ハイスピードなin-memory DBには重要。高いabort率もメモリー競合・キャッシュラインが汚れなければコストを最小化できる。Extra readsは1VCC固有の問題。Index contentionもそもそもearly index updateをしなければよい。（・・・とはいえ、それでパフォーマンスがでるか？という問題もある。）

□Multi-Version Concurrency Control

複数のversionを利用してコンフリクトを回避する。仮に更新があったとしても、前のversionを利用したtxが可能。version の管理はtimestamp(以下ts)を利用して行う。tsのアサインはtxの開始時点で行われる。各versionのwrite timestampはversionが有効(valid)になった時を示し、read timestampはそのversionが無効(invalid)になったか、または有効(valid)のままであるかを特定する（注：と論文には書いてあるが、ここでの無効と言うのはそのts以前のwriteは無効と言う意味で、そのまま有効というのは単にリードしてまっせという意味だと思う。普通にはread txがそのversionを読んだ時に「読んでるよ」のマークとしてtsをおく）tsを利用してvisibleな利用可能なversionを特定する。versionのtsはtxの開始時点のものか、またはcommit時点のものか、どちらかを利用する。

Strength
コンフリトが少ない。更新処理があっても別に関係なくレコードにアクセスすることが可能。

Weakness
弱点はmulitiversionのオーバーヘッド。以下

1. Computation and storage overhead of searching and storing multi-version records
特にIn memoryな高スループットな環境では、searchとstoreのコストはCPUを食う。storeの空間コストも大きい。大抵のMVCCではlistや配列の中のversionのsearchに間接参照利用する。これはキャッシュミスやワーキングセットがCPUキャッシュに乗らない場合は特にハイコストになる。最近のMVCCでは最後のversionでは間接参照を利用せずにin placeでの処理を行う方式もあるが、これは1-VCCと同じくextra readの問題を引き起こす。

2. Large footprint
multiversionなのでfootprintが大きくなる。ワーキングセットが大きければキャッシュヒット率は下がるし、処理のパフォーマンスも落ちる。頻繁にGCすることでfootprintを小さくすることもできるが、効率よくやる必要がある。

3. Writes to the shared memory
大抵のMVCCでは共有メモリーに書き込むが、これはメニーコア環境では悪手。

4. A bottleneck at timestamp allocation
tsの発行に、centralizedな方式で、atomicにshared counterを増やす形をとるとワークロードの競合状態に関係なくパフォーマンスに制約を発生させる。1-VCCよりも桁違いに悪くなる。今後のメニーコア環境ではますます悪化する。

以上の問題点は現在のMVCCでは部分的に解決はしている。しかし、MVCCのベースのオーバーヘッドはやはり大きく、low-contentionでは1-VCC-OCCの後塵を拝し、競合環境でも1-VCCを一貫して上回るというパフォーマンスを見せるには至っていない。

あとは付随的に
2.3 Constrained Parallel Execution
2.4 Hardware Transactional Memory
にまとめているが省略する。

以上はCicadaの論文における1-VCCとMVCCのPros-Consの分析になる。MVCCの弱点については、これらの弱点を一気にCicadaが解決するぜ、って話の前振りなのでちょっとくどい感じもするが、全体的に概ね合っていると思う。1-VCC(というかOCC)との比較で言えばOCCの軽さ＋エンジニアリングが、MVCCの重さ＋理論的なabort率の低さの合計を上回っているのが現状。

■Cicada本体

以降Chapter3以降は、上記のMVCCの弱点を補う形で、割とMVTO的な実装とそれにまつわる若干のエンジニアリングを提供している。またベンチマークも同様に提示している。以下、この実装(cicada)についての解説になる。

個人的に2017年現在のメニーコア・大規模メモリーを前提とした大規模OLTPのMVCCベースの参照実装としては「一つのモデル」になると思っている。もちろん、これがそのまま商用ベースになるとは思えないが、ただ今後の大規模OLTPを見るのであればチェックしておくべきポイントは提示されていると思う。

パフォーマンス・ベンチはTPC-C/YCSBの鉄板。MVTO(MVCC)ライクの素直な実装での比較としては意味があるので、そういう風に見るべきだと思う。以下ポイントごとに

■Design

・Multi-Clock Timestamp Allocation

tx開始時点にtsを決定する。tsはどのversionが使われるかの決定に利用し、serialization orderの確定に利用される。tsはsoftware clockで発行される。

tsのアサインはボトルネックになりやすいのでそれを排除する。メニーコア環境下でのハードウェアでの時刻同期は高コストになりやすい。各ワーカースレッドがローカル・クロックを持ちts発行前に時刻をインクリメントする。実装はTime Stamp Counterを利用し、各ローカルでのインクリメント幅（最大・最小）のみを保証している。もっとも早い時刻への同期をone-side(注：スレッド間のbarrierは取らない)でできるようにしている。

tsの発行は以下の3要素による
・ローカルの現在時刻
・クロックのブースト(abort時点でのスレッドあたりのクロックのブースト量)
・スレッドID（タイ・ブレーカー）
ローカル時刻にブーストを加えて、64bitのtsを作成し、下位56bit をとってスレッドIDの8bitを加える。

各スレッドは二種類のts（wtsとrts）をもつ。wtsは上記の発行時刻利用する。rtsは全てのスレッドのwtsの最小値(min_wts)から1を引いたもので、これをリーダー(leader)スレッドが定期的に更新する。なお、同様にmin_rtsも計算され、これはGCに使われる。read-writeのtxはthread.wtsをtsとして利用し、read onlyのtxはthread.rtsを利用する。特段にread-setをvalidateしたり、追跡はしない。
先行または同時に走るread-writeのtxのtsがmin-wtsとローカルのthread.rtsの間にあるようにして（see no earlier than min_wts and later than thread.rts）整合性を保つ。

Cicadaでは時刻同期は多少甘くても許容する。tsの物理時間での順序保証は想定しない、ユニーク＋単調増加であればよく、加えてスレッドID suffixと時刻の単調増加を持っていれば良い。

とはいえ、問題もあって、早すぎるtsは、競合writeのabort率があがる（注：スレッド間でtsの乖離が大きくなると同時刻のスパンがひろがりすぎる。だから競合になりやすい。）。なので、時刻異常訂正にlong-lastingとshort-livedの仕組みを利用する。(注：早い奴はそのまま生かして、遅い奴を一方的に修正、という意味だと思う)　以下の手法を利用

1 One-sided synchronization
各スレッドがround-robinで他のスレッドの時刻を見て自身の時刻よりも早ければ、そちらに時刻を合わせる。
プロトコルはcache coherencyなものを利用する。タイミングは100μsごと。これは遅いものを早いものに合わせるので、早すぎるものは修正できない。全部のスレッドで行うのでそれなりに有効。

2 Temporary clock boosting
abort発生時に、クロックブーストを行なって他に遅れている時間分＋アルファで時刻を進める。

時刻は基本的にwrap-roundなので一回りすると元に戻る。その時は意図的に新しいversionを挿入して時刻をリセットしてセットし直す。だいたい10日に一回。read-onlyの場合は関係ない。かつ、このwrap-roundの回数をeraとして記憶しておく。（全順序確保）

基本的にCicadaはスレッド間を超えたexternal consistencyは保証しない。（注：OCSRではない。serializableではある）あるスレッドのコミット後に、別スレッドでのコミットが前の時刻で来ることはありうる。ただ、これは滅多に問題にならない。dependencyがある場合は、厳密にorderingされる。external consistencyについてはmin_wtsがコミット済みのtsよりも大きくならないと（注：コミットされているものが先のtsを持つことを保証する。）アプリ側にコミット成功を通知しないことで対応している。これは100 μsぐらい遅れるけど、その程度を遅らせる処理は他にもあるので許容する。
causal consistencyだけであれば、先行するtxの最大のtsよりも時刻をインスタントに進めてtsを発行すればこと足りる。

・ Multi-Version Execution

データレイアウトは拡張可能な配列で二層構造のページになっていて、各レコードは配列のインデックス(レコードID)でアクセスする。各レコードのversionは単方向リストの構造でheadノードから始まりversionノードが続いている。headはinlined versionの場合がある。

各versionの構成は以下
1. wts : versionを作成したwrite txのts
2. rts : コミットした（またはする予定）のread txのtsの最大のもの
3. レコード本体
4. コミットステータス（validationの結果）
5. NUMAのnodeIDとかversionサイズとかのアロケート情報

この単方向リストはheadから順にwtsでソート済み（注：論文に図があるのでそっち参照）

versionがreachableになるのは、validation phaseで version listに追加(install)された時点から。フィールドはrtsとstatus以外はimmutable。rtsはリードにより更新される。statusは最初はPENDINGでwrite phaseに入ってCOMMITTEDか ABORTになる。削除はゼロ・レングスのversionにしてdeleteのコミット時にDELETEDになりGC対象になる。

各txはtx.tsを持っていて、version listを最新のものから遡ってスキャンして、使う対象versionにアクセスする。自分より新しいtsのversionは無視(注：このへんがMVCCの面目躍如)する。(v.wts>tx.tsでハネて、もっとも最新のものをみつけて)それからstatusを確認。PENDINGならspin-wait。ABORTであれば一つ前のversion、COMMITEDならそのversionで確定。これが要するにそのtxからのvisibleなversionになる。(注：ということはcommit済みのものだけでなくdirtyだが possibly committedなものを読んでいるということ。)

PENDINGがblockになるけど、まぁ時間がvalidationの時間だけで短いし、そもそもearly consistency checkを通っているので、COMMITTEDの可能性が高いので、投機的に無視するのはちょっとリスクがある。もちろんabortされることはあるがこれで投機的に実行するとCascading abortになる。なので、他のMVCCと違って、投機実行はせずにspin-waitsする。
(注：PENDINGは普通にabortの可能性がある(validationに時間がかかっているのはそういうこと)ので、投機的にabortとしてretryの方がスループットが出ると言うのが他の実装の話で、Cicada的にはこれはどうよ？と言う問題提起。後段になるがCicadaでは事前にpre-validationするので、この段階でのabort率は低い。)

Cicadaはversionサーチの間に、パフォーマンス上げるために、いかにもabortされるだろってtxをearly abortさせる。writeでvisible version vについてv.rts＜= tx.tsのチェックをする。そうでなければabortする。
(注：v.wts＜tx.ts＜v.rtsでabort。普通にMVTO)

Cicadaはread-own-writeもサポートしている。スレッドローカルなversionについては同じレコードであれば、同一txからはアクセス可能。スレッドローカルなhash tableを持っていてローカルversionへのポインタを
持っている。(注:このポインタっつーのがよくわからん。原文はpointerでmeta dataに対してってことなのだが・・実装見ないとよくわからん)

・Best-Effort Inlining

best-effort inliningでオーバーヘッドと競合のコスト抑えている。(注：head nodeが単純にarrayに順に配置されている＝inlined。これはなるほど、と思う。) txはまずheadのinlined version用に事前にアロケートされた場所を利用しようとする。inlineを利用するかどうかはレコードへのwriteが行われるときに決定される。まず最初にUNUSED ならCASでPENDINGにして、成功したらinlined versionを作成する。失敗したら non-inlineのversion作成。inlineは小さなデータ(216byte)のみで利用する。大きなデータだとメリットが薄くなる。

可能な限りInline化する。条件は
1. read txがinlineでないversionをvisibleとして読む
2. そのversionは十分早い。v.wts＜min_rts
3. かつinline化されてない
その場合はread txだけどRMWして同じレコードだけどinlne化する

inline化の競合を避けるために、inline化は滅多にまたは全く変わらないread-intensiveなレコードに限定する。もしwriteが多ければむしろオーバーヘッドが高いのでメリットが薄いし、そもそもreadされないのであればパフォーマンス向上に意味がない。

・Serializable Multi-Version Validation

1. Pending version installation
まず先にPending versionとしてwriteをinstall。wtsでソート

2. Read timestamp update
必要であればreadされているすべてのversionのrtsの更新。v.rts>=tx.tsの保証

3. Version consistency check
(a) readされるレコードセットの、今まで見えていたversionが現在でも見えているversionで　かつ、(b)writeされるレコードセットの今見えているversion vが v.rts＜=tx.ts (注：追い越し禁止)を満たす、ことを確認。
(注：MVTOプロトコルそのもの)

pending versionのinstallは同じvisible versionを共有し、かつtx.tsよりもあとのtsをもつconcurrentなtxをブロックする(注：早い方を先に書く)。もし、visible versionを共有していてもtx.tsよりも前のtsであれば、自身のpending versionはそのままinstallし、自身をabortにするかまたはconcurrentな方をabortすれば良い。これはearly abortと同じで、今見えているversionについて v.rts＜=tx.tsを満たせない場合に現在のtxをabortさせる。
（注1：visible versionを共有ということはr-w r-wでのw-wの競合になる。w-wだけであればMVでは競合にならないがr-wはRFなので普通にorderが競合。一応後述で単純writeでちゃんと区別していてRMW以外も考慮ずみ）（注2 : 処理フロー図だとwtsのソートがPENDING installationの前にあるけど、これは他のconcurrentなtxの結果がinstallされているのでそれを見るということだと思う。自身のwriteはsort段階ではまだinstallされていない、ので、abortするべきものはすれば色々汚れない）

read timestamp updateは、その他のtxにこのversionはtx.tsと同じくらい「遅れて」見られていると言うことを通知している。(注：validation時点で最遅＝最近のtsのnotify)

validation checkについては(a)今見えているversionより新しいversionはないこと、と(b)該当txが早すぎるversionをコミットしないことを保証している。特に後者はRMWじゃなくて単純writeのconcurrencyも向上させる。(注：単純writeとはblind writeを指すと思う。write concurrency向上は単にブロックしないってことでいいかと。ただしこの部分は他のMVCOO系とは違う部分なので重要。)

validationの後は、logにtxのts, read, write, insertのセットを渡す。logに失敗すればabortできるし、アプリがコミット済みtxを保持できるかどうか次第だがretryでlogすることも可能。(注：one-shot requestが前提。)

roll backの場合はversionがすでにできている場合にのみstatusをABORTにする。そうでなければGC。
特にABA問題(注：CASで別スレッドが参照先を変えてしまう問題)もない。同じようにrecord IDも再利用される。

read timestamp updateはwriteが条件付き(conditional)なので速い。rtsがtx.tsよりも遅かったら別に更新する必要もない(注：そもそも前のversionを読んでいるので意味ない)。28コアマシンで単一レコードに対して秒間23億の更新が可能で、これは条件付きでないただのatomicなfetch and addsが秒５千５百万しか処理できなかったことと対照的。

・Optimizations for Efficient Validation

Validationの効率化は以下の通り。総じて、MVCCの弱点を認識した上で、細かい手当をしかるべき形でやっている。いろいろ参考になると思う。

1. Sorting the write set by contention

validationの前にやってabortの負担の減らす手段。valdiationでは、最新（listの最初の）のversionのwtsを見る。これが大きい（新しい）ほど競合の可能性が高い。よってこれを降順にpartial sortしておく。この場合Top-kは総数nの場合は、n log kで終わる。このソートにより多数のpending versionをinstallしたり、相当のメモリーにアクセスする前にconflictを検出することができる(contention-aware validation)

これはOCCではできないか、またはやってもコストが高くつく。SILO/TicToc/Foedus/MOCCではvalidation phaseのロックでデッドロックを避けるためにすべてのwrite setでグローバルでのソートが必要になる。これでは柔軟なロックの順序(flexible locking order)を許容することができず、全ソートにn log nかかってしまう。Cicadaはデッドロックがないので、この制限がなくpending versionのinstallはtxのts、すなわちdependncy cycleを避ける形で優先処理される。

2. Early version consistency check

write setのソートの後に実行される。これはvalidation checkの version consistency checkと同じで、GCにかかるようなversionがinstallされる前に大抵のabortを検出する。これはTicTocのpreemptive abortを真似たもの。

上記の二つの最適化は、低競合状態では別段パフォーマンス向上につながる訳ではなく、不必要なオーバーヘッドでしかない。なので、直近のtxがコミットされるような状態ではこのステップは両方ともオミットされる。（実装では一行で五つ(5 in a row)コミットがあればオミット）

3. Incremental version search

version searchのコストを下げる。pending version installにしても　version consistency checkにしても version listをトラバースする必要があり、これはread phaseでも同じことをやるので重複している。こういうversion searchはローカルのCPUキャッシュにない新規に挿入されたversionを渡り歩かないといけないため高コストになる。このsearchの繰り返しのコストを低減するため、read phaseでの最初のversion searchの時点でtx.tsの直後のwtsを持つlater_versionを記憶しておく。このlater_versionは新しいversionが次のversion searchでヒットした時に更新される。version listがwtsの降順でソートされているので、現在のtxをabortできるような新しいversionはversion listの中ではlater_versionの次に現れることが保証される。なので少なくともversion searchの繰り返しはlater_versionからはじめて問題ない。(注：これはなかなかよくできている細工だと思う。)

・Indexing

Cicadaではindexとストレージは分離している。primary indexを含むすべてのindexはテーブルとは別のデータ構造になっている。64bitのレコードIDをindexとして持っており、レコード本体や生のポインタは持っていない。Cicadaのこのmultiversion indexesは以下の二つの問題、すなわちphantom回避とindex競合の低減を解決する。

1. Avoiding Phantom

index node validationの一種で回避する。index nodeに全部wtsとrtsをつける。range query, delete, insertとともに validationの前にindexが変わったかどうか判断できる。Cicadaの場合は標準のtable構造をそのまま利用できる。(注：要するに本体でのデータ構造でのチューニングメソッドをそのまま利用している)

2. Low index contention

OCCがread phaseでindex構造を変化させるのと違って、Cicadaではスレッドローカルでのindex nodeのwriteをtxのvalidationが終わるまで繰り延べる。これは自分のindex更新にread-own-writeの仕組みを利用することで達成している。あと一応single-version用のindexもCicadaはサポートしているがindex updateの繰り延べをやらないとindexでの競合が起きる。（注：まぁ確かにabort連発の場合は事前にindexを更新するのは賢くないのでdeferredの手はある。とはいえrecoveryとかそういう話もあるので、そうそう簡単かというとそうでもない気がする）

・Durability and Recovery

使っているのは、並列log書き込みと CheckPoint(CP)。CPはtransaction-consistent checkpointingが使えるといいなというレベル。（Low-overhead asynchronous checkpointing in main-memory database systems. 　 K. Ren, T. Diamond, D. J. Abadi, and A. Thomson. 2016）

基本的なデザインは以下参考Fast databases with fast durability and recovery through multicore parallelism. W. Zheng, S. Tu, E. Kohler, and B. Liskov. 2014

（注：ということでCALC(Checkpointing Asynchronously using Logical Consistency)がよいのでは、という提案になっているけど、個人的にはWBLの方が全然よさげなんで、ここでは省略。CALCはconsistent snapshotを特定のコミットのタイミングをトリガーにしてとる感じの手法。）

基本的にNUMAノード単位の複数スレッド単位でloggerスレッドがredo logを作る。validationが終わったら、loggerにlog record(write/insertのnew version のwtsとdate)を送る。loggerはlog fileにappend(スレッド単位に存在)する。それからversionのstatusをCOMMITTEDにマークし直す。普通のブロックデバイスならgroup commitでamortize(まぁ均等償却ってことでしょう)するが、NVMならbyte addressで直書きして低レイテンシーで行う。この場合はgroup commitのような手法は用いない。

checkpointについては別スレッドで動く。各テーブルをpartitioningしてその単位で、スレッドごとのcheck point fileに最新のcommitted versionを保存する。この処理はロック無しで非同期に行われる。安全なメモリーアクセスを確保するために、checkpointerはmin_rtsのメンテナンスに参加し、min_rtsの更新がわかるようにthread.rtsの更新する。（注：min_rts以前のものを触る）

recoveryは最新のcheckpointとredo logから行い、メモリー上にレコードの最新versionがinstallされているようにする。削除については全部の復旧が終わった後に最新のtsでdeletedレコードを作り直す。

(注：このあたりはわりといろいろやれることがまだまだ有るように見える。NVMが前提であるので、WBLあたりがかなり有効だと思う。)

Space management
redo logはchunk化されている。checkpointの生成単位でmin_wtsよりも古いckeckpointと古いlogが破棄される。

・Rapid Garbage Collection

GCはフットプリントを小さく保つために、割と回数多めでconcurrentに行う

1. Frequent garbage collection

通常のDBでは 数十msで行うが、それではMVCCではworking setがでかくなりすぎる。

例）80ms (Siloは40ms [EBR : Epoch Based Reclaimation] )でGCとして、YCSBのwrite-intesiveなケースでtxあたり800byteの書き込みを想定する。TPSで3.5Mのパフォーマンスで、txあたり1KBのstale recordができる。これでworking setは 80ms x 1KB x 3.5M/s だと凡そ280MB。これではCPUのキャッシュサイズに乗らない。stale recordが場所を取りすぎる。

よってCicadaではEBRとQSBRの派生手法を利用する。回収対象のversionをcoarse-grainedではなく fine-grainedで行う。

・最初のステップで各スレッドは最後のtxでコミットされた新しいversionのmetadataを記録する。
・visibleではなくなったversionはゴミになる。
・各スレッドは各versionへのポインターとv.wtsのコピーをまとめてキューに放り込む
・それから各スレッドがquiescent stateに入りフラグをセットする。(10 μsごと)
・リーダースレッドがフラグが立つを見るたびに全てのフラッグをリセットしてmin_wtsとmin_rtsを単調増加させる。その値がグローバルなthread.wtsとthread.rtsの最小値として各スレッドに保存される。
・quiescent終了後、各スレッドはローカルのGCキューを見て、キューの最初のアイテムが v.wts＜min_rtsかどうか判断する。もしそうなら全部、回収可能。現在・将来のtxはv以降のversionを使うから。
・チェックに失敗すれば、それ以降のキューは見る必要がないv.wtsはキューの中では単調増加なので。

2. Concurrent garbage collection

複数スレッドで異なったレコードのversionの回収が可能。
レコード単位で、GCロックとminimum write timestamp(record.min_wts)(注：レコードlistの終端)を持つ小さなデータ構造を本体とは別に持っていて、GC対象になるときにフェッチされる。
・GCロックに成功 -> 失敗した場合はGCで競合しているのでfailで良い
・(v.wts) > (record.min_wts) -> vについてのdanglingはないので、version listの残りをvからデタッチして、record.min_wtsを更新、GCロックを行って、GC対象にする。
・最後に、デタッチされたversion listのversionローカルメモリーに返却

・Contention Regulation

Early abortやearly version consistencyを講じてもabortは発生する。

Backoff

単純に失敗したtxをsleepしてリトライする。そもそもbackoffの時間はワークロード・システムによって最適解が様々。Cicadaはグローバルなコーディネートによるmaximum back-off timeを利用するrandomized backoffを使ってる。

リーダースレッドは5msごとに各スレッドのコミットされたtxの数を総計しスループットを算出する。直近の期間とその前の期間でのスループットの変化（スループットの変化を、変化させたmaximum back-off timeで割って勾配を見る）を見て、正（負）なら0.5 μsの固定量を増やす（減らす）。ゼロまたはUndefinedの場合は方向はランダムに決定。

以降は実際のベンチマークになる。論文を直接参照で。

■最後に、serializabilityの証明
Appendix Aより

ただ証明もってきても仕方がないので、MVTOと比較する。まずMVTOのpropertyを持ってきておく。

Property1.For each Ti, there is a unique timestamp ts(Ti); That is, ts(Ti)= ts(Tj)iff i = j.
TSの定義。注意すべきは別段startimeにはしていない。順序があれば良い。

Property2.For every rk(xj)∈H, wj(xj)成立しない。

(Case 2) Suppose tx′ reads a committed version v′′ that is earlier than v.
tx already passed the version consistency step by observing v, so tx′ also observes v, which makes tx′ fail the version consistency check step because v, not v′′, is the current visible version.
This again makes a contraction to the assumption that tx′ is committed.
では、仮にtx’がvよりもっと前のv’’を読むとすると・・・txがvを読んでいるので、tx’もvを読む。vがvisible versionなので、tx’がvalidationが通らない　->成立しない

(Case 3) Suppose tx′ reads a committed version v′′ that is later than v.
We substitute tx and tx′ with tx′ and tx′′. Reapplying this lemma reaches Case 1 or Case 2 in finite steps, precluding the existence of v′′ if tx′ is committed.
最後にtx’がvより遅いv’’を読むとすると、txとtx’をtx’とtx”に置き換えていくと結局前の二つのケースになり、
tx’がコミットするとv”が存在ことができない

Consequently, this makes a contradiction to the assumption that tx′ is committed.
Therefore, no such tx′ exists. v is the visible version to tx.
従って、そう言うtx’は存在しない。

上記より、tk(rj)について読んでいないxiのversionがあったとして
(j.wts) < (i′.wts) < (k.ts)のi’が存在しないため
ts(Ti) < ts(Tj) or (b) ts(Tk) < ts(Ti) となりProperty3は満たす。

Property4については
Property4. If rj(xi) ∈ H, i != j, and cj ∈ H, then ci < cj.
これはCicadaはci < tj_start_timestamp <cjなので成立する

よってCicadaはMVTOのPropertyはすべて満たす。
したがって、Cicadaが上記のProperty以外の制約を課さないのであれば、スケジューリングパワーはMVTOと同等である。

個人的にちょっと、そこで問題になったのは以下の条件。
The pending version installation step blocks concurrent transactions that share the same visible version and have a higher timestamp than (tx.ts). If a concurrent transaction using the same visible version has a lower timestamp than (tx.ts), it may proceed to install its own pending version, aborting either this transaction itself or that concurrent transaction. Similar to early aborts, this step aborts the current transaction if the current visible version v fails to satisfy (v.rts) <= (tx.ts)
自身が早い（相手がより大きいtsをもつ＝遅い）場合は、相手をブロック(block)して、自分をinstall。そうでない場合、自分をinstallして自分自身かまたは相手をabortする、という制約だが、これは、自分より早い場合はそのまま書ける。ただし相手をブロックする。ブロックされた側から見ると、”自分”が追い越しのinstallになるので、かつ相手（”自分”）がinstall済みになるので、それがコミットされるとすると自分をabortする羽目になる。また、自分が遅い場合は、相手をinstallさせて、自分を一旦installさせて、自分か相手をabortする。これは相手が追い越しになるので、相手がタイミングによってはabortになる。r-w r-wの競合になるので、それを解決する。

この時、後側のwriteをblindとするとr-w-wでwは競合にならないので、「見なかったことにする」のであれば実はserializableになる。visible versionの割り当てを強制しないのであれば、制約にならないが、強制割り当て（書くときには確認＝blind write禁止）をするのであれば、serialization空間は狭くなる。論文では明確ではないが、途中明示的にblind writeに言及している（ように見える）：Note that the latter check uses the currently visible version to increase the concurrency of write-only (not RMW) operations that do not depend on the previous record data. ので、そうではないと思われるので、制約になっていない。よって問題ではない。すなわち、MVTOと同等と思われる。

なお、最後の定理、すなわち
THEOREM 1. Any schedule for committed transactions in Cicada is equivalent to the serial schedule that executes the committed transactions in their timestamp order.

PROOF. A committed transaction creates at most one version for a record.
By Lemma 1, each version’s write timestamp following the transaction’s timestamp is unique within a record.
With Lemma 2, every committed transaction reads the uniquely determined visible version of the record as it would in the serial schedule.
Therefore, any schedule of committed transactions in Cicada is equivalent to the serial schedule.
これは問題ない。