作者：葉提
Faster實作主要分為三部分：
Epoch Protection架構，實作并發系統下全局修改，延遲同步到所有線程，簡化并發設計。faster線程在大多時候不需要同步，完全獨立執行。
支援高并發的無鎖hash 索引，是實作高吞吐的關鍵。
Hybrid Log，使用邏輯位址将記憶體和二級存儲統一起來，資料超出記憶體大小後可flush到硬碟，使其能夠支援超出記憶體大小的資料量。
Faster的限制包括：隻支援點查，不支援range query；基本隻适合update-intensive的場景；不寫wal(影響update性能)，恢複後部分資料丢失。
Instrduction
faster支援三種接口，read和兩類update: blind update和read-modify-writes(RMWs)。RMWs指在原來的value上原子更新，支援記錄的部分更新(比如隻更新value的一個字段)。faster是一個point-operation系統，在記憶體中可實作億級别的吞吐，尤其在支援超過記憶體限制的資料量下依然能保持如此高的性能。可見在設計和實作上的确做了比較大的努力和創新的。
首先為支援可擴充的線程模型，faster擴充了标準的epoch-based同步機制，通過trigger action促進全局changes延遲同步到所有線程，這個epoch架構幫助faster簡化了并發設計。
然後介紹了無鎖、高并發和cache友好的hash索引的設計，與純記憶體allocator結合使用時，就是一個記憶體的kv系統，性能和擴充性高于其它熱門的純記憶體結構。
最後介紹了HybridLog。log-structuring技術可以支援超出記憶體限制的大資料量的存儲，通過寫wal支援failure recovery，基于read-copy-update的政策，記錄的更新都是追加寫的方式寫入log中。但是這樣的方式限制了吞吐和擴充能力，in-place更新是性能的關鍵。是以，faster提出了HybridLog:記憶體與append-only log的方式結合，熱資料支援in-place更新，冷資料read-copy-update，先copy到熱資料區域再in-place更新。
faster遵循大多數case可以fast的原則，在以下三個方面做了精細的設計：
1.實作無鎖高并發的哈希索引對于記錄提供快速的point通路。
2.選擇合适的時機做耗時的操作，像hash索引擴容、checkpoint和淘汰等。
3.大多數時候可以做in-place更新。
faster在記憶體負載下的性能是遠超出于其它純記憶體系統的，而且是在支援資料量超出記憶體限制和支援熱點資料集變化的情況下。
Epoch Protection Framework
Epoch不是新概念，已被Silo、Masstree和Bw-Tree用于資源回收。faster将其擴充，成為更通用的架構，主要用于memory-safe garbage collection、hash索引表擴容、log-structured allocator的circular buffer的維護和page flushing、page邊界維護和checkpoint。
Epoch Basics
系統維護一個sharded原子計數變量E，叫做目前的epoch，每個線程都可以增加它的值。每個線程T都有一個本地的E，用Et表示。線程周期地重新整理本地的epoch值，每個線程的epoch值都儲存在sharded epoch table中。如果所有線程的本地epoch都比epoch c大，則認為c是安全的。faster額外維護了一個全局的Es，用于記錄最大的安全的epoch。對于任意線程T，都滿足Es
Trigger Actions
使用trigger action使這個架構具備當一個epoch變為安全時執行任意全局action的能力。目前的epoch從c增加為c+1時，線程額外關聯一個action，該action在epoch c變為safe時觸發。
Using
對于線程T支援4種操作：
Acquire: 為T保留一個entry，将Et設定為E
Refresh: 更新Et到E
BumpEpoch(action): 更新c到c+1，
Release: 将T的entry從epoch table中移除
使用trigger action的epoch在并行系統中可以簡化延遲同步。一個典型的例子：當共享變量status變為active時，需要調用函數active-now。線程更新自己的status到active，并将active-now作為trigger action，并不是所有線程可以立馬看到status改變，但是可以保證當線程refresh它的epoch時可以看到。是以隻有當所有線程都看到status變為active才會調用active-now。
THE FASTER HASH INDEX
faster高性能hash index的特點有concurrent、latch-free、scalable和resizable。與普通的hash table實作不一樣，不儲存key值，儲存記錄set的實體或者邏輯位址，純記憶體下是實體位址，混合存儲下是邏輯位址。
索引組織
該設計假設64位系統cache line大小為64bytes。索引有2^k個hash bucket，每個bucket的size為cache line的大小：64bytes。一個bucket包含8個entry和一個指向下一個bucket的指針。8位元組entry的設計可以使用64位原子的操作。
64位的機器上，實體位址通常小于64位，intel機器使用48位的指針。是以它這裡隻用48位來存儲位址，剩餘15位叫做tag，用于hash，一位叫做tentative bit，用于insert過程中的兩階段算法。
索引操作
hash index建立在一個保證的基礎之上：每個(offset, tag)對應唯一一個entry。address指向記錄的set，這點跟普通hash table很不一樣，hash index中不儲存key，而是指向記錄的set，将沖突放到value中解決。
支援以下操作：
finding and deleting an entry: 根據key值直接定位到bucket中的entry，先根據offet定位到對應bucket，再周遊找到比對tag的entry。删除entry使用CAS原子操作用0替代掉比對的entry。0表示是空的entry，可以使用。
inserting: tag不存在時，insert到一個新的entry。圖3(a)展示了通常的操作方式，周遊bucket中的entries找到空的entry，使用CAS将新的tag insert，但是存在兩個線程并發将相同的tag寫入的問題。如圖3(a)所示，T1從左到右周遊entry找到第5個entry并寫入g5，與此同時，T2将g3删除，然後從左到右周遊entry找到第三個entry并寫入g5。
這個問題的本質原因是線程獨立地選擇entry并且直接修改它。可以使用lock bucket的方式來解決，但是太重了。faster使用無鎖的兩階段的方式來解決，借助于tentative位，線程找到空的enty寫入新的記錄并設定tentative位，一個被設定了tentative位的entry對于讀寫是不可見的，然後再重新掃描bucket檢查是否存在相同的tag，如果存在則傳回重試，否則重置tentative位完成insert操作。圖3(b)展示了這個操作。
In-memory, Log-Structured and HybridLog
論文先講了純memory實作和純log-structered的實作，最後将兩者結合起來形成最終的HybridLog。
記錄的格式為圖2所示由8個位元組的header、key和value組成，key和value可以是定長也可以是變長的，header分為16位的meta和48位的位址，用少量的位儲存一些log-structured allocator所需要的資訊，位址用于維護記錄連結清單。
In-memory
純memory的實作中，記錄隻儲存在memory中，使用底層配置設定器像jemalloc配置設定記憶體，hash index中儲存實體位址，支援read、update and insert和delete操作：
reads：根據key定位到hash index的entry，周遊記錄list找到key值對應的記錄。
updates and inserts：支援blind update和RMW update，使用in-place更新的方式。在epoch protection下，線程可以安全的in-place更新記錄。如果entry不存在，按照上述hash index的兩階段方式寫入，如果list中找不到此記錄，使用CAS操作原子地将新記錄寫入到list的尾部。
deletes：使用CAS操作将記錄從list中移除，當entry删除時，将entry設為0，辨別entry是空閑可用的。删除記錄後，記憶體不能立馬釋放，因為可能有并發的update存在，faster使用epoch protection解決，每個線程維護一個thread-local的空閑，當epoch變為safe後可以将其釋放。
Log-Structured
純log-structered的實作中，使用邏輯位址将記憶體和磁盤統一起來，用追加log的方式将記錄寫入。可以支援大資料量存儲，論文第7章測試了性能不超過2000w的ops，也不可随着線程數scale。實作上使用兩個offset分别維護記憶體的最小邏輯位址和下一個空閑位址的offset，稱為head offset和 tail offset。記憶體配置設定總是從tail offset處配置設定，head offset與tail offset之間的空間是記憶體的容量，這裡叫做Circular Buffer，是定長pages組成的array，與實體page對應。
為實作無鎖的方式将記錄flush到磁盤上，引入了兩個狀态數組，flush-status記錄目前flush磁盤的page，closed-status決定是否page可以被淘汰。要淘汰的page必須要保證已經完全flush到磁盤了。當tail offset增大時，使用epoch機制的trigger action觸發異步io請求将page flush到磁盤，epoch安全後調用，確定所有線程在這個page上的寫都完成了，設定flush-status。
随着tail offset的增長，頭部page需要從記憶體中淘汰，需要先確定page沒有線程在通路，傳統資料庫一般使用latch pin住這個page，faster為了實作高性能，還是借助于epoch管理淘汰。
Blind update就是簡單的将新的記錄append到log的尾部。delete記錄通過header中标志位識别，資源回收時會識别。Read和RMW操作與記憶體中相似，隻是update是追加寫一條新記錄，邏輯位址跟純記憶體中的實體位址處理也不同，如果位址大于head offset，則資料在記憶體中，否則送出異步的讀請求到磁盤。
HybridLog
log-structured可以處理超出記憶體大小的資料量，但是append-only的特征會帶來一些代價：每次update都需要原子更新tail offset，拷貝資料，原子更新hash index中的邏輯位址。而且update-intensive的負載下，很快會到io瓶頸。在這種負載下，in-place更新有以下優點：
1.頻繁通路的記錄可放在更高層級的cache中
2.不同hash桶的key值通路路徑不會有沖突
3.large value的部分更新可以避免複制整個記錄
4.大多數更新不需要修改hash index
HybridLog将Log分為了三個部分：stable 磁盤部分、read-only和mutable部分。統一為一套邏輯位址，read-only和mutable都在記憶體中，其中隻有mutable部分可以原地更新，儲存hot data，read-only部分的資料更新操作需要先将其copy一份到mutable中，再在mutable中原地更新。
随着tail offset的增長，mutable頭部的資料轉換為read-only，read-only頭部的資料刷到磁盤中。可以看出比較适合更新集中的應用場景。相比log-structured，增加了read-only offset，原理和head、tail offset類似，read-only offset将可以in-place更新的mutable部分和immutable部分分開。
HybridLog記憶體部分可以看作是一個緩存，性能基本取決于它的效率。資料庫緩存和作業系統下的記憶體管理通常有fifo、clock、lru和lru的變種等，這些算法(除fifo外)都需要細粒度的統計資訊才能很好的工作，faster沒有這些overhead，比較類似Second-Chance的FIFO。
faster資料分布取決于通路模式，一段時間後熱點資料逐漸集中在記憶體中。mutable和read-only region的記憶體劃分是尤其重要的。mutable部分較大可以使記憶體性能更好，in-place更新更多，但是可能會使得mutable的部分資料也面臨淘汰的問題。較大的immutable region會導緻過多昂貴的append-only update，copy到mutable使得log較快增長。論文提到實驗得出，9:1的比例對于mutable和immutable的劃分可以有比較好的性能。
Recovery
faster将update性能放在首位，寫wal會影響update性能，是以不寫wal，程序failure後記憶體中的資料就丢了。
不過它可以恢複到consistent狀态，比如任意兩個更新請求r1和r2，是被一個線程順序送出的，恢複後可能的狀态：1. none 2. only r1 3. r1 and r2。也就是不會出現隻有r2而沒有r1的情況。
測試
論文對比了高性能的記憶體結構Masstree和Inter TBB hash map，以及兩個熱門的kv store RocksDb和Redis。
單線程下，uniform分布和zipf分布資料。faster表現最好TBB其次rocksdb表現最差。
256線程下，uniform分布達到1.1億，TBB也接近這個數值，zipf下faster可以将熱點資料集中在mutable區域，性能達到1.6億，與其它系統拉出了明顯差距。
擴充能力測試，faster在單cpu和多cpu下的scale能力都很好，masstree也不錯但是性能差很多。TBB單cpu的scale能力很好，但是多cpu下比較差。詳細的測試内容，大家可以自行檢視論文。