FoundationDB一個具有事務語義的分布式KV存儲，是最早的一批把NoSQL和分布式事務結合起來的資料庫系統，它提供了NoSQL的高擴充，高可用和靈活性，同時保證了serializable的強ACID語義。
這個資料庫很有意思，其對于事務/高可用/容錯的設計都非常獨特，概括來說，整體采用了松耦合的子產品化設計，系統分為了3個元件：
- in-memory 事務管理
- 分布式的storage管理
- 分布式的system configuration管理
三個元件各自獨立部署 + 配置，是以按照需求，各自provision來保證元件的可用性/擴充性。
另一個獨特的地方是，它先用了2年時間開發完成了一套基于deterministic simulation的測試架構，然後才開始做的db産品。這個測試架構将系統中所有非确定性因素用mock子產品來模拟，并可注入确定性的錯誤或事件，使得系統的運作完全可控且可複現，更容易發現bug和調試，也幫助提升新feature的開發速率。
從設計原則上，産品追求的是：提供最小的功能集合，即一個事務語義的分布式KV存儲，并不提供其他功能如query language,data model,index,schema。。。這樣反而為上層提供了靈活性，可以基于FDB建構各種類型的分布式系統。（Apple cloud/Snowflake/CouchDB...）
首先強的事務語義和最簡單的data model對于上層的應用開發來說會更加友善，早期NoSQL為了擴充性犧牲了事務能力，隻保證最終一緻性，是以應用層必須對并發控制進行處理，大大增加了開發複雜度。而FDB則加上了強的串行化事務語義，是以上層應用可以友善的建構類似全局二級索引/唯一性限制等功能，且由于底層隻是KV，是以很靈活，可以存儲各種類型的資料，semi-structure/graph…
從FDB的角度，它對上層隻提供，有序+事務+KV存儲的抽象。
基本概念
- 總體的架構是松耦合的，分為control plane + data plane
- control plane負責系統的管理和監控，使用active disk paxos 來存儲系統metadata。
- data plane負責使用者+系統資料的存儲，其中事務管理系統負責寫路徑，storage系統負責讀路徑，是解耦的，可以各自獨立擴充。
- 利用OCC + MVCC的政策來實作串行化事務。
- 使用failure -> restart -> recovery的政策來處理failure，即快速失敗快速恢複。
- 采用了類似Aurora的log is database的思路，對log進行多副本同步複制，是一種特例的quorum，所有副本都同步落盤，才認為送出成功，才能傳回用戶端！是以f+1個副本，最多可允許f個失效。
設計
paper中主要讨論了transaction/replication/fault tolerance(recovery) 三個方面
設計原則
- 子產品化分割，盡量細分且子產品之間互相解耦
例如事務系統内，其送出(write path)和讀取(read path)是可以獨立擴充的，系統中根據事務功能的不同，區分了很多角色（timestamp管理,沖突檢測,送出的協調,logging..），每個角色也可以獨立配置和擴充。而全局來看也把各個功能盡量拆分開來，減少耦合。
- 快速failure快速恢複
與一般的資料庫系統不同，它處理各種類型的failure方式都一緻，就是發現failure後重新開機整個事務系統，通過recovery機制來修複failure，是以必須做到快速檢測和快速恢複才行。生産環境中從出現問題->發現->主動shutdown->recovery，一般在5s以内。
- 确定性模拟測試系統
提升品質，使得bug可被reproduce。
對外接口是典型的key/value(get/set/getrange..)，事務機制是典型的OCC，開始時基于系統的快照做讀取+修改，所有修改在client本地緩存，結束時帶着read set/write set發起送出。由于需要緩存修改，系統對于Key/Value/事務的大小都是有限制的，這和client的緩存+in-memory的事務管理系統的緩存機制有關。
整體架構
Control plane
存儲系統一些關鍵的metadata，通過Active Disk paxos group保證高可用性，并選舉出單個的Cluster Controller，controller會建立另外幾個單執行個體程序：Data Distributor，Rate Keeper，Sequencer
Sequencer是事務系統的領頭節點，它負責建立事務系統其它服務程序
Data Distributor 負責監控Storage Server的叢集狀态，并做負載均衡
Rate Keeper 其流控作用，避免系統overload
Data plane
FDB本身針對的負載類型是OLTP + 小事務 + 讀為主 + 高并發但低沖突。其内部的3層也都是松耦合的。
TS層負責in-memory記憶體處理，由Sequencer領頭，建立Proxy / Resolver，整個TS層是無狀态的，便于發生failure時，快速整體重新開機。 （如果Sequencer重新開機了，timestamp怎麼單調遞增？）
LS層負責WAL的存儲，按照key range做分片存儲，且每個分片有多個副本。
SS層負責實際資料的存儲，和LS的分片對應，每個分片有自己的WAL日志，底層目前使用的是SQLite，後續會考慮Rocksdb。
從上面的架構圖可以看到，讀寫路徑是分離的，TS層+LS層和write path相關，而SS層和read path相關。這是其設計的核心思想，将功能盡可能細分為不同role，由不同服務程序負責，不同role各自獨立配置和擴充。例如如果想提高讀吞吐，擴充storage server，如果想提高寫吞吐，擴充Resolver/proxy/LS。
boostrap/reconfiguration
可以看到FDB内部各個元件是有着互相的關聯的：
Coordinator中存儲着系統核心metadata，包括LS Server的配置，LS Server中則存儲了Storage Server的配置。
運作中，Controller監控Sequencer，Sequencer監控Proxy / Resolver / LogSevers的狀态。
bootstrap
系統啟動時，Coordinator會選舉出Controller，後者啟動Sequencer，Sequencer則啟動另外3組程序，然後從Coordinator中擷取老的LS的配置，并從老的LS中擷取SS的配置，利用老的LS執行必要的recovery過程，完成後老的TS系統就可以退休了，新的LS的資訊寫入Coordinator中，系統完成啟動，開始對外提供服務。
reconfiguration
當TS系統發生failure或者配置變化時，Sequencer檢測到後會主動shutdown，Controller檢測到後會重新開機新的Sequencer進而形成新的TS，新的Sequencer會阻止老的TS再提供服務，然後走和bootstrap類似的recovery流程即可。
為了辨別不同的TS系統，引入了epoch的概念，任何時候新老TS交替，epoch就要+1。
事務管理
并發控制
采用了比較經典的OCC套路，思路和SQL Server Hekaton 的并發控制有些類似：
用戶端連接配接Proxy，擷取讀時間戳，Proxy向Sequencer擷取read version傳回client，client利用read version從storage server直接讀取目标版本資料，在本地做修改并緩存，事務送出時帶着read set+write set發給proxy，proxy首先向Sequencer擷取commit version，然後發送Resolver做沖突檢測，檢測失敗則傳回client，client可以重試（是以要小事務）。
Resovler也是根據Key range分片啟動多個執行個體，這樣可以并發做沖突檢測。
FDB實作的是可串行化事務，commit version的順序就是事務送出順序，是以可以認為事務需要在commit點瞬時完成，沖突檢測就是判斷在 [read version -> commit version ]之間，是否并發事務寫入了沖突的資料。從下圖可以看到，理論上Ti是在commit ts那一時刻瞬間完成了事務，是以Ti讀取到的也應該是在commit ts時刻系統的快照，而在Ti start -> Ti end這個過程中，其他事務Tj修改了Ti讀取的資料，read ts時刻看到的快照與commit ts時刻的就不再相同了，串行化被破壞。
Resolver的沖突檢測算法：
為了檢測，其内部使用skip-list維護一個LastCommit結構，即修改的key range -> commit version的一個映射，記錄某個key range最近一次的送出version，便于找到對某個key/key_range，最近一次commit_ts是否在目前事務的[read_ts, commit_ts]之間（即沖突），不沖突即用目前事務commit version更新LastCommit。
這裡有一個問題，由于是多個resovler并發檢測沖突，可能一些resolver局部認為是無沖突的，是以更新了自己維護的LastCommit結構，導緻後續不應該失敗的事務發生沖突(false-positive）。FDB認為這不是大問題，首先它面向多租戶應用，沖突較少，一般事務都會落入一個resovler。此外即使失敗後重試，新的ts的read version增長後，超過這個僞送出事務的commit ts即可。
除了read-write事務，還有read-only事務，隻擷取read version從SS讀取資料，然後client直接送出就可以，等同于在read ts瞬時完成，不需要檢測沖突。 此外在read-write事務中還允許做放松串行化要求的snapshot read，這種read不放入read-set中，不做沖突檢測。
持久化
所有Resovler傳回成功時，Proxy認為事務可以送出，向LogServer發送log做多副本同步複制，所有副本的日志都落盤後，Proxy認為事務送出成功，傳回給用戶端。同時Storage Server異步的從LS擷取log entry并apply，即使log entry還沒有落盤也會apply，采用這種激進政策來保證data和log之間的低延遲。
可串行化的并發控制使得log entry之間形成了嚴格的順序，大大簡化了log管理的邏輯，可以用version來表示LSN，針對每個key，它所面對的實際是一個有序的log entry隊列，依次apply就可以了。
Proxy寫log的流程也比較特殊：
Proxy本地有緩存一份key range -> SS的映射關系，這樣就可以知道要寫入哪些SS和對應的LS。例如上圖中，LS1 + LS4是要寫入的LS，是以把這個事務的log都寫入（形成副本），此外由于是3副本，再額外寫一個LS，其餘的LS也要發送，但隻傳遞Log Header，其中包含的最主要資訊是目前的LSN和Proxy上的KCV，即本Proxy已知的最大已送出事務，LS收到後會更新自己本地的KCV，這個KCV在recovery時會使用。
LS上的WAL -> SS和apply redo并不在commit path上，是異步持續完成，是以可以說FDB也遵循了”log is database”的思想。這種方式client做read一般可以讀到目标version的資料，如果不行就等待或者向其他副本請求，都不行的話，可以逾時後重試。
由于是異步apply，可以做batching，将一批更新緩存在SS上，批量刷盤提高IO效率。但這裡也有個問題，由于LS中在記憶體中（未送出）的entry也可能被apply，是以SS是有髒資料的，在recovery時要rollback。
Recovery
FDB做恢複是最為與衆不同的，由于其基于recovery來做failure處理，是以recovery是正常操作，需要快速恢複。
由于redo log apply是在背景持續進行的，是以本質上它将redo apply從recovery中解耦出來，等于持續在checkpointing，在recovery期間不需要做redo/undo apply，隻是确認目前的log序列需要恢複到哪個位置即可！！後續基于log -> data的過程仍然是異步。這保證了recovery的速度。
具體流程：
發現failure後，老Sequencer退出，新Sequencer啟動，并從Coordinator擷取老的TS的配置資訊，包括老的LS的位置等，同時給Coordinator加個全局鎖，避免并發recovery，然後關閉老的LS，禁止接收新的log寫入，開始恢複，恢複完成後啟動TS系統接收使用者請求。
Proxy和Resolver都是stateless的，直接重新開機就可以，隻有LogServer有log資訊，恢複如下：
由于在日常送出寫日志時，Proxy會把本地記錄的KCV廣播給所有LS(見持久化一節)，LS中就記錄了自己見過的最大的KCV。選取所有LS中KCV的最大值，在這個值之前的事務，其日志已經完全複制并落盤，且已告知Proxy，可以作為上一個epoch的終點，稱為PEV（previous epoch’s end version）。
同時每個LogServer都記錄了本地已持久化的version (DV)，選取所有DV中的最小值，作為Recovery Version(RV)，在PEV -> RV之間的日志，已持久化且不在記憶體中，但不确定是否已送出（因為proxy沒有該資訊，可能崩潰的那個沒持久化），是以這部分需要進行恢複(redo)，而 > RV的log entry，肯定沒有多副本都持久化，是以不可能送出，這部分要undo。
是以整個的recovery流程，就是将老的LS中的[PEV+1 , RV]之間的部分，copy到新的LogServer中并完成log複制即可。這樣這部分事務已成功排好隊，後續在開始接受使用者請求前，先啟動一個事務将RV之後的log對應的資料rollback，然後就可以處理使用者請求了（log已準備好繼續append）。
複制
系統中不同元件，複制政策不同
- Metadata，存儲在Coordinator中的，通過Paxos變體實作複制，是以适用于quorum政策。
- Log，存儲在LogServer中，是全量同步複制，是以允許f個失敗 (f+1個副本)。
- Storage，由于Log已同步複制，存儲就是異步複制到f+1個副本
為了做fault tolerent，storage的各個副本是有一定政策來分布到各個fault domain的，防止多個副本同時失效的情況，這個和Spanner的排程政策類似。
另外2個小的優化：
1. Transaction batching
在Proxy上為了減少與Sequencer/LS的互動成本，可以把不沖突的并發事務合并，擷取同一個commit version，并一起下發到LogServer。相當于group commit。
這個政策是可以自适應的，在系統負載不大時，為了減少延遲，可以減小patch大小，當系統重負載時，為了保證吞吐則可以加大patch。
2. Atomic operations
對于一些隻寫不讀的操作，其互相之間可以不做沖突檢測，直接擷取送出時間戳就可以，這對于某些counter類型的操作會提高效率，因為避免了從storage的一次讀，也避免了resolve confilct。
Failover
對于跨Region的高可用和failover，采用了一種巧妙的政策：
在一個region内，建立多個AZ，各個AZ之間是獨立失效的，是以整個region失效機率是很低的。region内分為Data center和Satellite site，主DC中允許TS + LS + SS，standby中的DC隻保留LS + SS，而Satellite中隻運作LS的副本，是以消耗的資源會少很多。
在primary region内，log還是同步複制的，跨region，則通過LogRouters，從主region的LS中異步拉取，同時LogRouter保證同一個log entry不會重複複制（怎麼做沒有細講）。
DC之間有有優先級，例如上圖DC1 > DC2。
每個region可以各自配置自己的複制政策：
- 選擇一個最高優先級的Satellite，做同步複制（k = 2)，如果這個satellite失效了，則再選次級satellite補上
- 選擇2個最高優先級的Satellites，做同步複制（k = 3)，如果一個satellite失效了，則fallback為選項1
- 由于前2個都是完全同步複制，是以如果有那種長尾 的網絡延遲，則commit會延遲，為此可以配置3副本，但複制時，允許一個異步複制，是以減小了長尾的機率。響應會更快些。
primary DC失效時，standy 的DC會啟動一套TS，從主region中的logserver中拉取尚未同步的日志，并根據本region的複制政策，建立Satellites上的LS副本。如果完成後，primary DC已經恢複了且滿足了複制要求，則fallback回primary DC，否則secondary DC開始提供服務。
Simulation test
這是FDB一個非常有特色的地方，很可惜這裡的很多細節我沒有搞清楚，隻知道是基于Flow的異步程式設計架構，每個process都是單線程+callback處理。雖然他們在cmu的talk中也着重講了下這個測試架構，但我聽得模模糊糊。。。基本沒體感，是以就不誤人子弟了，希望有了解的大神指導下。
總結
總的來說，FDB有幾大特色：
- 非常松耦合的系統，read/write path是分開的，每個功能元件可以獨立擴充來避免成為系統瓶頸。
- log is database，redo apply + undo和recovery解耦，減少commit path的負載
- 通過OCC + MVCC實作串行化事務，簡化log的處理
- 快速恢複，通過fast failure + fast recovery，來統一對于failure的處理方式，這個recovery路徑比較快且穩定
但缺點也很明顯：
- 有限的功能集
- 串行化事務對事務大小的限制
- 面對場景比較确定，就是可擴充的，支援小事務高并發的KV存儲，且沖突不能太多，不然重試+復原太多，影響系統吞吐。