文章目錄
- 0 前言
- 1 架構設計
- 1.1 設計原則
- 1.2 系統接口
- 1.3 架構
- 1.3.1 Control Plane
- 1.3.2 Data Plane
- 1.3.3 Read-Write Separation
- 1.3.4 配置變更和選舉流程
- 1.4 事務管理
- 1.4.1 端到端的事務處理流程
- 1.4.2 事務沖突檢測
- 1.4.3 日志協定
- 1.4.4 事務系統的Recovery
- 2. 模拟測試架構
- 3. 性能
- 4 總結
0 前言
FoundationDB 是蘋果公司從2009年開始，開發了十多年的分布式k/v 存儲系統。
擁有如下幾個亮點：
- 架構完全解藕，目前來看其架構可以說将解藕做到了極緻。内部主要擁有三個子系統：常駐記憶體的事務管理系統、分布式存儲系統、内置的分布式配置系統。每一個子系統都能夠獨立提供可擴充、高可用以及分區容錯的能力。
- 模拟測試架構，類似pingcap 的kaos-mesh。這個測試架構是十多年前專門為fdb 設計的，其設計經過嚴格的證明，能夠将最為嚴苛的場景中的異常模拟出來，模拟分布式/事務/存儲場景中可能出現的無數的異常。每一個fdb新特性都會通過這個模拟測試架構上的測試之後才能上線，是以 fdb 穩定性極為可靠。
- k/v API 簡單，且功能完備。能夠很好得被內建到上層應用之中(關系型、文檔型、對象存儲、圖存儲)。
因為其有好的架構設計 以及 強大的穩定性保障，是以fdb 被廣泛應用到了 蘋果内部的存儲系統之中，而且 被 snowflake 當做了自己的中繼資料存儲（雲原生數倉穩定性要求極高）。
FoundationDB 的設計目标是 稱為能夠支援各種上層應用場景的分布式存儲引擎。
原因如下兩點：
- 當時業界主流的nosql 系統為了迎合使用者的需求（應用中不一定需要關系型的資料通路模式），比如 雲服務場景對存儲系統的需求是 可擴充、高可用、支援網絡分區、同時提供一部分的資料模型，這樣能夠讓使用雲服務的使用者快速去做應用側的功能高疊代，是以 nosql 系統為了保障性能，犧牲了事務能力，僅需要提供最終一緻的一緻性模型即可，是以像是 Cassandra , CouchBase 這樣的系統他們的應用場景非常有限。
- 關系型資料庫存儲仍然占大頭，但是他們底層存儲架構設計和上層應用耦合度過高，每一個資料庫的存儲和SQL 層都是綁定的(MYSQL, ORCLE 不論是事務管理 還是 存儲， 整個系統都是高度耦合的)，底層存儲層并沒有辦法通用，對于想要做自己業務場景的資料存儲公司來說成本極高。
綜合以上兩點，蘋果公司在當時設計了足夠通用的分布式存儲引擎，整個FoundationDB的 設計 以及 代碼實作是能夠看到蘋果公司是真的在認真做一款分布式存儲底座，至少國内公司不會讓一個團隊幾年時間制作一個simulator 來證明整個産品的架構設計和穩定性都是滿足要求的。
不過因為 FoundationDB 社群建設的不是很好，像是一些技術文檔更新有版本差或者不完善(RedWood存儲引擎設計)，而且代碼注釋比較少，研究起來會費勁很多，不過并不影響它本身是一個非常值得學習的分布式事務型的k/v存儲底座。
本文通過 FDB 在 2021年 SIGMOD 發表的 FoundationDB: A Distributed Unbundled Transactional Key
Value Store 來簡單介紹一下 fdb的設計架構，這篇論文是 sigmod 的 2021的best paper。
1 架構設計
1.1 設計原則
- 分治（解藕）。将事務管理子系統獨立出來，并且為每一個子系統内部設定了不同的角色 來提供不同的事務管理能力：時間戳管理、處理事務送出、沖突檢測、事務日志管理(REDO/UNDO)等。除了事務相關的，還将分布式系統需要的 過載保護、負載均衡 以及 異常恢複 等功能 也會由獨立的角色去完成。
- 讓異常成為常态。異常情況在分布式系統中是非常常見的，fdb 的處理方式不是寫很多發生異常情況之後如何處理的的代碼邏輯，而是通過檢測到異常之後主動關閉系統。這樣就能夠将異常處理交給recover 來做，對recover 的恢複速度就提出了非常嚴苛的要求，發生異常之後的recovery 能夠盡可能少的展現在上層使用者的可用性上是非常重要的。
- 快速檢測異常并快速恢複。這個原則也是上一個 讓異常成為常态 原則的基礎。希望能夠快速檢測到異常，并且快速恢複，在 fdb 的生産叢集中 整個流程的 MTTR(Mean-Time-To-Recovery) 時間 是在 5秒之内完成的。
- 模拟測試體系。用來做fdb的可靠性驗證 以及 fdb 的開發者的工程能力 和代碼品質。
1.2 系統接口
fdb 提供了一些基操作單k/v 以及 批量k/v的接口：
- set()
- get()
- getRange()
-
clear()
事務場景，這一些操作會暫時緩存到用戶端，隻有在事務調用 commit 之後才會被持久化，為用戶端提供的是 read your write語義。
1.3 架構
一個fdb 叢集 邏輯上 主要由兩部分組成：
- Control plane。管理整個fdb 叢集的系統中繼資料。
- Data plane。處理事務 和 資料存儲。
基本形态如下：
每一個部分内部又有一些邏輯上的小元件組成，充當各自系統内部的角色。
1.3.1 Control Plane
這一部分内部主要是用來之久化系統關鍵路徑的中繼資料，比如 transaction system中 coordinator的配置資訊。
這裡簡單介紹一下 control plane 中 coordinators 的作用，它們是這一層的主要角色，監管整個叢集的各個服務運作的狀态，不同的 coordinator 之間是通過 disk paxos group 達成共識的。
每一個 coordinator 是一個 fbserver程序，包括後面提到的其他的角色，都是統一的fb程序，隻是采用的是對應角色的配置。
這一些通過 disk paxos 運作的coordinators 會選出來一個主程序(leader) 叫做 ClusterController，這個 類似leader的角色功能主要是：
- 監控整個叢集 所有在運作的服務狀态
-
選擇三個服務程序：
a. Sequencer 用于data plane 事務系統 配置設定 read 和 commit 版本（時間戳）
b. DataDistributor 使用者監控叢集服務的狀态，探測是否有異常節點 以及 監控 StorageServers 之間的資料分布情況，并做資料均衡。
c. Ratekeeper 主要為整個叢集提供流控能力，做過載保護。
選擇出來的這三個程序如果異常挂了，會由 ClusterController 重新選擇，重新制定一些 fbserver程序代替這個角色。
1.3.2 Data Plane
所有 OLTP 型的負載處理都會在這一層中。這裡 foundationdb 也采用了完全解藕的架構設計，從上面的圖中可以看到，主要分為了三個部分：
- Distributed transaction system(TS)，用于處理記憶體中的事務。
- Log system(LS)，通過 WAL(write-ahead-log) 持久化 TS 中的事務資料。
- Distributed storage system(SS)，提供 資料存儲 以及 讀能力。
TS 事務系統 中有幾個 角色比較重要：
- 一個 Sequencer，這個就是 ClusterController 選擇出來的一個角色。用于一緻性讀 以及 事務送出時配置設定時間戳。
- 多個 Proxies，為 client 提供 mvcc讀 以及 協調事務送出。
- 多個 resolvers 用于事務之間做沖突檢測。
LS 日志系統的總體角色像是提供 複制、分片、分布式持久化隊列 的能力。每一個 “持久化隊列” 儲存的事一個 StorageServe 的 WAL 資料。
SS 由多個 StorageServe 組成，這個服務程序是整個fdb 叢集中最多的，主要用于服務自用戶端的讀請求，每一個 StorageServe 會按照 range （有序的）存儲分片資料。StorageServer 核心部分就是存儲引擎了，每一個 SS 都會有一個引擎執行個體。
目前 FoundationDB 7.1 版本 支援的存儲引擎如下：
預設的存儲引擎用的是SQLite，不過FoundationDB 在其之上為适配多版本做了一些修改(SQLite 是 B-tree 存儲引擎，不支援多版本，FDB 為其支援了多版本，同時增加了更快的RangeDelete 以及 異步API 接口)；除了 SQLite 之外 還支援了 Memory , RocksDB(目前還在試驗中，沒有上生産環境)，RedWood 存儲引擎 。
可以簡單說一下 RedWood 存儲引擎是 FoundationDB 因為 SQLite的一些問題，而為自己設計的存儲引擎。因為SQLite 不支援多版本（FDB 寫入的k/v 都會帶有自己的版本，比如 同一個user key “key1" ，會有 key1-10, key1-11, key1-13等多個版本），而且因為 B-tree 的COW 更新方式對記憶體和性能都有非常大的影響，并且不能友好的支援字首壓縮。對FDB來說還是在設計上很難大幅度優化的，是以他們開發了一個适合自己場景的存儲引擎 RedWood，關于RedWood 存儲引擎的介紹後續會專門寫一篇 該引擎的設計背景以及基本實作原理。
1.3.3 Read-Write Separation
因為 FoundationDB 靈活的架構解藕，讓來自用戶端的讀寫可以被不同的元件去排程，進而實作了可擴充的讀寫分離。
來自用戶端的讀請求可以直接被 分片到某一個 SS 程序，随着 SS 服務數量的擴張，用戶端讀請求的性能也是線性增加的。
用戶端下發的寫請求則會被一系列程序處理，像是 Proxies, Resolvers 做事務送出和沖突檢測。這裡MVCC 的資料會存放到 SS 中。
在整個系統中存在的三個單例程序 ： Sequencer、DataDistributor、RateKeeper 因為隻管理中繼資料，是以并不會成為系統的性能瓶頸。
1.3.4 配置變更和選舉流程
在FDB中， 所有的使用者資料以及大多數的系統中繼資料都會被存儲到 SS中。 SS 中 每一個服務程序的中繼資料則會被持久化到 LS(Log Servers) 中，LS 的配置資料則會被放在 Coordinators 中。而 Coordinator 則使用的是 disk paxos來保持共識的，如果 Coordinator 中的 “Leader” ClusterController 異常/未選舉，則 會通過 diskpaxos 選擇一個新的 ClusterController，這個新的 “Leader” 首先會選擇一個 Sequencer 單例角色，sequencer 從 舊的 LS 讀取 LS原本的配置資訊，并生成一個新的 TS 和 LS。接下來 就是 事務系統中的 Proxies 會從 舊的 LS 讀取系統中繼資料 (包括 SS 的中繼資料) 進行恢複。 sequencer 會等到新的 TS 完成事務資料恢複 會 将新的 LS配置寫入到 所有的 coordinators 。
整個Cluster 角色選舉 從 ClusterController 開始到完成各個元件的恢複就都做完了，到此才能為用戶端提供讀寫服務。
1.4 事務管理
1.4.1 端到端的事務處理流程
事務處理從讀寫兩方面展開描述：
- 對于讀事務來說，用戶端會先從 TS 的 Proxies 中的一個擷取一個 read version（時間戳），Proxy 會和 Sequencer進行互動 并 擷取到目前系統最新送出的版本，Proxy 将擷取到的版本傳回給用戶端。用戶端可能會排程多次讀請求到 SS，并擷取到他們想要的小于等于這個版本的value資料。
- 對于寫事務來說，用戶端下發的寫請求會先緩存到用戶端本地，并不會和FDB 叢集的角色有互動。用戶端下發送出請求的時候，送出 rpc 會被發送到 Proxies 中的一個 并等待送出結果的傳回。如果送出失敗，用戶端可能會重試。
關于寫事務 中 TS 的 Proxy 送出流程如下圖，3.1, 3.2 ,3.3 共三步
- 3.1 proxy 向 sequencer 請求一個新的commit version，要比已經存在的 read version 和 commit version都大。sequencer 看起來像是一個中心授時器，能夠提供百萬級别的 版本生成能力。
- 3.2 proxy 拿到新的版本 之後會發送給 resolvers 對 commit keys sets 做沖突檢測，使用的是OCC的方式（送出的時候菜進行），主要檢測的是讀寫沖突，即是否有其他的事務在讀目前commit 得這一些keys。如果所有的resolvers 都傳回沒有沖突，則傳回給Porxy可以進行最後的送出階段；如果有沖突，則傳回Proxy目前事務終止。
- 3.3 Porxy 将送出事務發送到 LogServers 中進行持久化。一個事務在 LS 中完成送出的前提是所有的 LogServers 都向 Proxy 傳回成功，并将送出的 commited version 發送給sequencer 用于推進下一次的 commit version。 最後傳回給Client 送出成功。 于此同時，SS 會從 LogServer 異步拉取 transaction logs 進行 REDO（因為在 fdb 中 logserver 儲存的是送出成功的事務日志，是以并不是 undo log），将事務操作資料 重新執行，持久化到 SS 的本地存儲中。
1.4.2 事務沖突檢測
如上流程中，Proxy 拿到 sequencer 配置設定的大于 read version 以及 最新的 commit version的一個version 之後會将目前事務要送出的事務交給 resolvers 做沖突檢測，這裡是事務處理性能的關鍵，也是整個事務系統最為容易出現性能瓶頸的地方。FDB 這裡在 resolvers 上實作的沖突檢測算法是無鎖的，大體算法流程如下：
lastCommit 是每一個 resolver 維護的一個曆史送出記錄 ，通俗來說是一個 map（在fdb 的實作中是一個 支援多版本的skiplist，類似 rocksdb 的 WriteBatchWithIndex），儲存的是這段時間内送出的key-ranges 和 它們的commit versions 之間的映射。
對于要送出的事務 Tx 在沖突檢測中的輸入由兩部分組成： 表示要修改的key range集合，
- 1-5 行代碼 用于 中的讀 和 lastCommited 中的寫進行沖突檢測。主要從 中取出 事務
- 沒有讀寫沖突，則将目前的 中的修改的key range 添加到 lastCommitted，用于後續事務的讀寫沖突檢測。
詳細代碼實作是在
SkipList.cpp
中，每一個沖突檢測函數内部 邏輯還是比較多的，感興趣的同學可以看一下。
論文中提到每一個resolver 的 TPS 上限能夠很容易達到 280k，而且是一個fbserver 作為 resolver，實際的生産環境單機可以部署多個resolver（正常情況這種高CPU負載的肯定會部署在不同機器上，實際的key 空間經過分片之後肯定是分布在不同機器上的），這樣的單機事務能力還是比較強的。
1.4.3 日志協定
上面提到了 resolver 做沖突檢測的基本流程，這裡就到了 Proxy 日志送出的最後一步，也就是持久化事務日志到 LogServers 中。
基本過程如下圖：
- Proxy 根據事務要修改的key 查詢在 proxy 程序記憶體中的 shard map，确認這個key 所在的 StorageServer，如上要修改的key 是’a’，則确認包含 a 的range 的 storageServer 分别是 1， 4，6.
- Proxy 會和 1, 4, 6 StorageServer 建立連接配接，每一個StorageServer 會有對應的 LogServer 排程請求（前面說過，一個LogServer 可能和多個 StorageServer 對應，類似持久化隊列， SS 從 LS中取請求本地執行持久化操作）。
- Proxy 向對應的LS 發送事務處理請求。SS 1和 6 對應 LS 1，SS4 對應 LS4。同時為了保證高可用，還會将 目前請求
set a=b
- LS 1, 3, 4 在完成本地的持久化之後會向 Proxy 發送完成 rpc，Proxy 會對本地的 Know commmited version (KCV) 進行更新。
- 将 LS 中的資料持久到 SS中是異步操作。SS 會從 對應的 LS 中 拉取 redo log，SS 中的持久化方式是利用 batch commit，即 通過 redo log重放的請求會先在記憶體中進行batch，達到門檻值/時間之後才會批量送出，這樣的group commit的送出方式對 i/o 更為友好。存在的問題也很明顯，如果 StorageServer 挂了，記憶體中緩存的一部分操作就會丢失 或者 是一個事務隻送出了一半 ，是以還需要 Recovery 以及 recovery過程中的 rollback能力。
1.4.4 事務系統的Recovery
在 FDB 中，Recovery 過程成本非常低，因為其解藕架構設計 沒有 checkpoint，recovery 的時候不需要重放 redo 或者 undo log。隻需要保證一個非常簡單的原則，Recovery 的過程中對 redo log的處理流程還是和之前一樣就好了，即異步拉取 LS 中的 redo即可，完全不會對整個 Recovery的性能産生影響。
上文的 Proxy 在 LS 系統中持久化 redo log的時候也說到 SS 會異步得拉取 redo log進行本地的 group commit操作。是以如果整個事務系統進行重新開機的時候，根本不需要等到所有的 redo 都被送出到 SS中，而是重新像 1.3.4 小節中描述的，隻需要保證選擇出新的 TS 和 LS即可，過程中隻是一些配置資訊的互相互動。新的 TS 和 LS 系統 ready之後就可以接受使用者請求了， 至于 Recovery 之前 SS 沒有完成恢複的 redo log 可以重新異步得從 TS 拉取恢複就可以，這個過程是一個背景操作，對Recovery的性能不會有太大的影響。
是以FDB 這樣的解藕設計能夠提供非常快速的 recovery能力，這樣整個系統就可以将這個能力發揮出來，即出現異常之後不需要複雜的異常處理邏輯，而是快速進行Recovery，Recovery過程中恢複系統的正常執行的邏輯。
2. 模拟測試架構
FDB 利用自己編寫的一套 支援并發原語 actor model 模型 的異步程式設計架構 Flow
這個模拟測試架構并不是一個工業級落地産品，卻是擁有功能完全一樣的模拟測試系統，對于一個做分布式存儲底座的公司來說想要花費以年為機關的時間先做一個測試架構來證明後續産品的架構優勢以及穩定性是否達到預期 成本是非常高的。這一點，蘋果公司可以說是業界标杆了，是真的在做一個工業級的通用強一緻分布式存儲底座。FDB 的強大穩定性成為 snowflake 這樣公司首選。除了社群管理不夠完善之外，真的可以有很多分布式設計的細節值得學習借鑒，隻是需要去花時間深入研究代碼。
在模拟測試中，FDB 能夠利用 Flow 模型快速模拟多個 fbserver 在自己所屬的角色中利用模拟的IO ，網絡，時鐘 進行互動，進而達到和生産環境類似的運作延時/形态。
正常體系的運作過程中 會通過 Fault Injector 不斷得随機注入異常（磁盤/IO 異常，機器重新開機，網絡分區等等） + 随機 workload 能夠非常高效準确得完成在分布式場景下的各種極端運作場景的穩定性測試，發現的bug 都能被複現、進一步分析 進而修複。
而且 FDB 生産代碼開發之前是先開發的 Simulator，因為Simulator 無法覆寫到 引入的 thirdparty（不是用Flow 實作的），是以他們就拒絕引入thirdparty，完全使用自己的 Flow 實作了 rpc 系統(fbrpc)，共識系統(disk paxos) 以及 分布式配置管理系統(coordinators)。
3. 性能
這裡主要展示一下關鍵性能。
1.機器數量的增加，吞吐的變化情況如下
無論是 純讀/純寫 還是讀寫混合，性能都是随着機器數量的增加而增加。因為讀事務的鍊路比較短，clients 除了拿read version的時候和 TS 進行互動之外，帶着IO的讀請求都是 client 直接和 SS 進行互動，是以讀性能平均比寫性能好很多。2.吞吐和延時情況如下
圖a 展示了請求處理的帶寬可以随着 ops 的增加而線性增加，即吞吐是線性的。
圖b 展示了延時情況，随着ops 的增加 在10w 量級以下，讀平均延時不到1ms， GetReadVersion（Client 讀的時候會從 TS 的Proxy 上請求一個 read version）1ms 左右， GetReadVersion比Read 延時會高一些，因為它需要Proxy和 Sequencer 進行 rpc 互動，相比于讀直接和SS進行互動來說鍊路稍短一些；commit 鍊路會更長一些，涉及到持久化資料到logserver，平均延時在10w 一下的時候大概到幾個ms。
在 10w-100w以及 100w 以上的 ops情況下，這幾個操作的平均延時都會增加。對于commit來說，ops越大，其處理鍊路的複雜度會更高，尤其是 Resolvers做沖突檢測好事比較長。
3.Recovery 性能
4 總結
- FDB 極緻解藕的架構設計 為整個分布式事務型的kv存儲 性能提升和優化提供了保障。每一個角色可以單獨配置設定伺服器資源，極大得保障了不同使用者場景下的使用者性能需求：讀寫事務較多，增加 TS resovlers 服務；讀請求多，增加 StorageServers數量即可。而且利用解藕架構設計 能夠提供 Fast Recovery能力。
- 基于Flow搭建的Simulator 測試體系，極大得保障了整個FDB 服務的 穩定性。FDB給出的資料：近幾年FDB 生産環境線上部署了幾十萬個執行個體，還從來沒有發生 corruption 問題。
- 前面兩個可以說FDB最大的吸引力，後面支援的一些分布式事務型的k/v 存儲能力 都是基本功能的保障，像是 支援全球部署，SSI 隔離級别，存儲引擎(SQLite，RedWood，RocksDB 支援)等等，保障了FDB 可以作為一個生産級别的分布式kv底座。