作者：葉提
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下比較差。詳細的測試內容，大家可以自行查看論文。