引言
微軟在2018 SIGMOD Transactions and Indexing Session 中發表了一篇名為《FASTER: A Concurrent Key-Value Store with In-Place Updates》的paper，文章提出了一種在更新密集，通路模式多表現出時間局部性，允許工作集大于記憶體，通路操作多為點讀，Blind Update以及Read Modify Write場景下的表現極佳的KV引擎，号稱單機QPS可以達到1.6億。
上面這句話其實已經說的非常清楚了，就是在這些限制下Faster很牛逼，但是上面三種操作其實限制了很多的使用場景。比如它就沒法代替LSM-Tree，BW-Tree這樣的存儲結構，因為這些結構都是支援範圍操作的，但是換來的就是上述三種操作QPS潛力有限。Redis這樣的KV系統以其豐富的接口類型讓FASTER望其項背，但工作集局限于記憶體這點注定了其高昂的TCO（就算目前雲上有不少的混合存儲産品，成本依舊高昂），且性能和Faster不在一個數量級。
嚴格的限制帶來的是強大的性能，最近我們團隊剛剛上線了稱為Cache Node的類計算節點（定位其實就類似于DAX，本質上就是加速使用者的熱點讀寫操作，雖說我在[2]這篇文章中Diss過這種模式的壞處，但顯然其帶來的好處目前來看是優于壞處的，這也告訴我們凡是切忌想當然，當然那篇文章的中心論點我仍舊不認為有什麼錯，隻不過題目略帶誇張而已），其存儲引擎暫定使用内部優化過的一個FASTER實作版本，基本性能目前看來是說的過去的。
重點Topic
這篇文章處于“ Transactions and Indexing ”中不是沒有道理的，在超過記憶體的工作集合能保持三種操作如此高的性能我認為其緩存友好，無鎖，高并發，可伸縮的index設計是一大亮點；另外一種稱為Epoch Protection 同步架構也是非常巧妙，是Faster實作擴充的重要原因；最後提出HybridLog，解決append-only log在工作集大于記憶體時帶來的性能問題。
如下是FASTER的宏觀架構：
接下來我們分别聊聊我對這三個技術點的一些了解，當然原始論文才是最好的學習資料，FASTER的代碼也是開源的，不過代碼量相比與成熟的存儲引擎來說有些過小了，看起來更像是一個prototype，當然用來學習是非常Nice的，我自己最近并沒有時間看這個代碼，是以對FASTER的了解可能并不是非常準确。
Epoch Protection
FASTER對于提升多核可擴充性遵循一個準則：不線上程間公共通路路徑上執行昂貴的同步開銷。FASTER在大多數時間中都獨立執行操作，并在一定的時機執行延遲同步。
Epoch Basic
系統維護一個原子計數器稱為，稱為current epoch，任何線程都可以遞增。每個線程中都維護着一個本地副本稱為，所有線程中的都會定期被重新整理至，每一個線程中的都被存儲在一個cache-line中，這些cache-line被一個共享Epoch表儲存。我們任務所有線程的都大于時認為已經被同步至所有線程，即它是安全的；此外引入一個稱為的記錄最大安全的Epoch，其根據共享Epoch表更新，在Epoch表更新時同步更新。
Trigger Actions
Faster增強了基本的Epoch Framework，當一個Epoch使用Trigger Actions變的安全時其可以執行任何操作。線程在本地遞增Epoch為X時可以關聯一個Action（其實就是一個回調），在未來Epoch X安全時這個回調由系統觸發。這個行為由drain list實作，drain list是一個由<epoch, action>組成的操作對清單。其實作為一個small array，在被更新是這個array被掃描，數組中使用CAS操作保證每個Action隻執行一次。注意，Epoch Protection隻有在current epoch被更新才會更新以及掃描drain list，以確定擴充性。
operation
Epoch Protection共定義了四個操作，任何線程都可以發起其中任意一個：
-
Acquire
-
Refresh
-
BumpEpoch
-
Release
下面這個例子我認為可以很好的解釋Epoch Protection到底做了是什麼事情：
Epochs with trigger actions can be used to simplify lazy synchronization in parallel systems. Consider a canonical example, where a function active-now must be invoked when a shared variable status is updated to active. A thread updates status to active atomically and bumps the epoch with active-now as the trigger action. Not all threads will observe this change in status immediately. However, all of them are guaranteed to have observed it when they refresh their epochs (due to sequential memory consistency using memory fences). Thus, active-now will be invoked only after all threads see the status to be active and hence is safe.
帶有Trigger Actions的Epoch可以簡化并行系統中的同步。一個線程原子的更新自己的Epoch時立即觸發Trigger Actions并不能保證所有的線程都觀察到這一結果，但是當所有的線程都通過Refresh觀察到更新的Epoch時就可以保證一定觀察到了Trigger Actions，這個可以使用記憶體屏障保證。
Faster 中的 Epoch Protection 可以被看作是一個同步架構，在FASTER的很多地方都被使用。例如記憶體安全垃圾收集（第 4 節）、索引伸縮（附錄 B）、circular buffer 維護和 page重新整理（第 5 節）、共享日志頁面邊界維護（第 4 節）和Checkpoint（第 6.5 節），同時為使用者操作（例如讀取和更新）提供更快的共享記憶體位置的無鎖通路。
這一節我基本是原封不動的翻譯原文。我向來是不喜歡拷貝粘貼式的寫文章的，但是原文中這部分的描述實在是惜字如金，如此有趣的系統用了寥寥小幾百字，幾乎是一筆帶過，憑借我可能不那麼職業的職業判斷，實在是認為原文沒有一個字是廢話，不敢怠慢，全段落手打，生怕錯過細節。
我認為Epoch Protection是三個Topic中了解最為困難的一個，了解了這個基本也就鐵定能了解其他兩個了。好了，來談談對
Epoch Protection
的淺薄看法吧。
首先在文章的1.2有這樣的描述：
This framework provides Faster threads with unrestricted access to memory under the safety of epoch protection. Throughout the paper, we highlight instances where this generalization helped simplify our scalable concurrent design
該架構依賴于epoch protection使得Faster線程可以無限制安全的通路位址。在整篇論文中，我們強調了這種泛化，有助于簡化擴充和并發結構的設計。
然後在2.3中我們又可以知道epoch base這樣的方案其實并不是一個新穎的東西，在BW-Tree這樣的結構上已經有了一些特化的使用，而FASTER把其擴充到一個通用的架構上，是以了解epoch base是重中之重。
文中提到的其他使用epoch base的結構都稱這種做法為
Epoch based reclaimation
，即垃圾回收。這個問題很容易闡述，在并發資料結構中我們通常會遇到一個問題，即一塊位址在被删除的時候不能直接free，原因是有可能其他線程正在通路這塊位址或者擷取了這塊位址但還沒有開始通路，如果直接free就會出現core了，問題的關鍵在于什麼時候我們可以“安全”free掉這塊位址。
有些讀者可能注意到了這其實和RCU非常類似，這裡“安全”的概念其實就是
grace period
，不過核心的實作會更加優雅，相反這裡Epoch Protection的實作就非常類似于[6]中描述的使用者态RCU。
假設線程A配置設定到一個Epoch 稱為E1，線程B配置設定到一個E2，已知E2大于E1，我們認為如果每個線程的操作是原子的，那麼E1如果和E2操作同一塊位址，E2是一定安全的，這隐含着E1的所操作的記憶體已經不被大于它的Epoch線程持有了。将删除操作帶入E1，正常操作帶入E2，那麼E1一定是可以“安全”的釋放這塊記憶體的。
按照文中的例子來說，不管是記憶體中的垃圾回收還是circular buffer 維護和 page重新整理，都隐含着其執行時必須是安全的。
我關心的是Epoch Protection Framework到底給出了怎樣的保證，從文中可以看出其保證了在每個Epoch關聯的Action執行時，其一定是“安全”的（記憶體屏障保證，先執行的一定是可見的），不會再有線程持有它所操作的位址。基于這個保證，類似于垃圾回收這樣複雜的并發操作都會被簡化。
但是問題在于這是否高效，在2.3的開頭有這樣一句話困擾了我很長時間：FASTER的準則是不線上程間公共通路路徑上執行昂貴的同步開銷，Faster的線程獨立執行操作，大部分時間沒有同步。話是這樣沒錯，一般情況下線程會執行
BumpEpoch
，然後每隔一段時間後執行
refresh
，但是看起來所有的操作都成了類似串行的狀态。
這裡我可能還是沒有了解清楚。
Hash Index
這是Faster這麼快的一個重要組成部分，最吸引我的地方在于其cache-line友好的索引設計。
Faster的hash index由2k個緩存對齊的哈希桶構成，一般來說cache的大小都是64位元組[8]，一個64位元組的buket由七個八位元組的hash buket和一個溢出指針構成：
這裡八位元組的選擇比較有意思，首先是CMPXCHG指令是支援八位元組[9]的，這意味着我們可以使用CAS對哈希桶執行無鎖操作，其實目前64位機器上實體位址隻占了48位（位址線也隻有48根），剩下16位我們可以當作其他用途（這種方案非常常見）。十六位中15位稱為tag（可有可無的），一位稱為Tentative，前者用作找到key對應的bucket，後者稱為兩階段插入的算法避免相同的key被寫入到兩個桶中。
當然可以像上面那樣玩的主要原因是因為為了cache-line友好把實際資料的位址存在了hash index中。
Hybridlog
文章其實是先從邏輯位址入手，再介紹Apeend only的log structed方案，最後才引入Hybridlog，但是我們不闡述前兩種方案。
Hybridlog解決的問題是如何把工作集擴充至記憶體之外。
思路是把位址空間看作2^48次方，這部分位址空間被分為三部分：
其中Stable存在磁盤中，Read-Only一部分在磁盤中，一部分在記憶體中，顯然Read-Only和Mutable加起來是要大于記憶體的。
讀寫的對象如果是大于Read-Only，就是就地更新，因為這部分資料一定是存在在記憶體中的；如果是大于Stable但是小于Read-Only，就會在Mutable中建立一個新的副本，修改hash index中的指向；如果小于Stable，這部分資料就需要發出異步IO從磁盤中讀取了。
這裡Read-Only的引入我認為其實就是基于Log Structed引入了一個緩存淘汰政策（類似于Second Chance FIFO），使得記憶體能夠處理的資料大于原始方案，但相比于Append only又更快。
對于Stable區域的寫操作(blind write，RMW，CRDT)也有着不同的處理方案。
關于Checkpoint也比較有趣，但是還處于初期階段，大概就是不給予WAL的recover方案，當然是沒法保留記憶體中資料的，但是可以保證一緻性這裡論文并沒有寫的很詳細。
總結
其實剛看這篇文章的時候是抱有比較大的期望的，但是看完以後認為理論上并沒有什麼創新，基本是工業上做到了極緻，當然于我來說也是收獲匪淺的。
總結一下：
優點：
- 為了支援大于記憶體的設計，先引入log structed方案，這種方案使得blind write和RMW非常高效，但是因為Append Only的低效率設計了Hybridlog，這種設計其實就是在log structed上加了一層特化的記憶體淘汰政策。
- cache-line友好的hash index帶來了極高的性能。
- 抽象出了Epoch Protection Framwork，使得這種Epoch的思想可以讓更多并發系統收益，而不是以前那樣用于特定的功能。
- API過于單一，不支援多鍵原子修改，不支援範圍操作，隻支援read，blind write，RMW
- 論文中沒有解決資料持久性，當機意味着Stable之後的資料丢失。
- 《FASTER: A Concurrent Key-Value Store with In-Place Updates》
- Don‘t Put a Cache in Front of Database
- FASTER github
- 淺談記憶體屏障，C++記憶體序與記憶體模型
- 如何評價微軟FASTER key-value 存儲引擎
- Userspace RCU的使用與原理
- 怎樣了解 Epoch based reclaimation？
- 從X86架構中cahe的組織結構引發的各種思考
- 為什麼隻有atomic_flag是保證無鎖的
- Faster review