FoundationDB 將解耦做到了極致

語言: CN / TW / HK

FoundationDB(後文均稱為 FDB) 是 09 年便開始的專案,被蘋果收購後經歷了閉源和再次開源。它是較早完整支援 ACID 事務和 Serializable 隔離級別的分散式 KV 系統。其團隊發表在 SIGMOD'21 的論文 FoundationDB: A Distributed Unbundled Transactional KeyValue Store 獲得了 industry best paper。我覺得其在 KV 儲存內部,將各個模組徹底解耦的做法(真的是非常徹底),在“雲原生”這個概念越來越被重視的現今,還是非常值得參考的。

1.整體架構

FDB 主要由 Client、Control Plane 和 Data Plane 組成。

1.1 Control Plane

Coordinators:通過 Disk Paxos Group 儲存系統的關鍵元資訊。並選出一個單例程序 ClusterController 用來監控、控制叢集中所有機器。FDB 鬆散耦合的設計原則在 Control Plane 裡也有體現,ClusterController 將一些重要的功能模組獨立出來,建立了以下三個元件:

(1)Sequencer:用於生成全域性時間戳(實際位於 Data Plane)。

(2)DataDistributor :用於監控 Failure 以及負載均衡。

(3)RateKeeper:負責保護叢集不要過載。

以上三個元件都是無狀態的,如果出現問題,重新建立一個即可。

1.2 Data Plane

Data Plane 將鬆散耦合的設計原則執行的非常徹底,主要分為以下幾個元件:

分散式事務管理器(TS):處理 in-memory transaction,它又包含了 Sequencer、Proxy 和 Resolvers 三個元件。Sequencer 負責為讀和提交分配時間戳,Proxies 負責 MVCC 讀和協調事務提交,Resolvers 檢查事務衝突。

日誌系統(LS): 為事務管理器儲存 WAL,物理上由一系列 Log-Servers 組成。Log-Servers 對外表現為高可用(replicated)、分散式的持久化 queues。

儲存系統(SS):提供持久化和讀資料服務,物理上由一系列 StorageServers 組成。每個 StorageServer 上存有多個 shards,共同組成一個分散式的 B-Tree 向外提供讀寫服務。目前StorageServer 的儲存引擎是改造優化過的 SQLite(似乎也支援了 RocksDB)。

可以看到 FDB 有非常多的角色, Scale out 可以通過 scale 相應的角色來實現。比如讀 scaling 和寫 scaling 可以分開,讀可以隨著 StorageServers 的數量線性擴充套件(隨機讀),事務提交可以通過增加更多的 Proxies、Resolvers 和 Log-Servers 來擴充套件。而在 Control Plane,每個元件分工明確,職責有限,不太可能成為單點。

2.事務系統

2.1 事務提交流程

上節的架構圖展示了事務提交的大致流程。

事務讀寫階段,Client 首先向 Proxy 傳送 Get Read Version 請求,Proxy 向 Sequencer 傳送獲取 version 的請求(比已經提交的事務的時間戳都大),Client 用這個 read version 向 SS 發起讀請求,寫請求則都 buffer 在 client 本地,Commit 時一起傳送到 Proxy。

事務提交階段:(1)Proxy 從 Sequencer 獲取 commit version。(2)Proxy 將事務資訊傳送給 range-partitioned Resolver,Resolver 使用樂觀併發控制演算法處理讀寫衝突,如果衝突事務會被標記為 aborted(client 可重試),否則開始提交。(3)Proxy 將事務資訊傳送給 LS 持久化,所有指定的 LogServers 響應成功,Proxy 通知 Sequencer 最新的 commit version,然後返回客戶端成功。 同時 StorageServers 從 LogServers 非同步拉資料回放。

可以看到,FDB 為了徹底的鬆散耦合,實現更加細粒度的儲存計算分離,不惜增加 RPC 次數。雖然整個事務流程是無鎖的,但是可以與預見其讀寫事務延遲應該會較高。另外這種將 Page Server(Storage Server)與日誌服務(LogServer)分離的設計思想,也在諸如 Azure Socrates 和華為 Tarus 等雲原生資料庫上得到應用,這樣的優點是可以分層進行優化,提供更靈活和細粒度的控制。

2.2 如何支援 serializable 隔離級別

Resolvers 模組專門處理事務衝突,採用樂觀併發控制避免鎖的使用。由於事務的提交時間戳由 Sequencer 依次分配,這個天然順序定義了一種事務依次執行的順序,所以 FDB 具備實現 strict serializability (同時滿足 Serializability 和 Linearizability) 的條件。

首先,為了保證事務的提交順序與分配的 commit version 完全一致,Proxy 將事務資訊傳送給 Resolvers 時,需要攜帶上一個 commit version(last committed version,由 Sequencer 返回給 Proxy),Resolvers 需要按照這個順序提交,這相當於給事務排序。

其次為了解決讀寫衝突,即解決不可重複讀、幻讀和 lost update 問題,Resolver 對比事務讀請求的 read version,和與其有交疊的所有 key 範圍的 last committed version ,如果 read version 比它們都大,則可以提交,否則需要回滾。因為 Resolvers 儲存了 key range -> last committed version 的對映,所以不可重複讀和幻讀都可以解決。此外讀到更新的版本會回滾,所以一定不會導致別的事務 lost update。

再者,所有 read version 能讀到所有已提交的,未來提交的肯定讀不到,因為當讀了 key1 後,key1 、 key2 被另一個事務修改(提交),該事務去讀 key2 時肯定會失敗,所以 read skew 也不可能發生。

最後,對於 write skew,假設現在有兩個球(黑、白),兩個事務分別想將他們變成同一顏色(要麼全黑、要麼全白)。T1 讀到 key1 為黑,key2 為白,於是改 key2 為黑,T2 讀 key2 為白 ,key1 為黑,於是改 key1 為白。如果不加約束,改完後還是一黑一白。對於 FDB,假設 T1 先提交, read version 為 5 , commit version 為 10。T2 read version 為 7, commit version 為 11。如果 T1 通過 validation,則 key2 的 last committed version 為 10,T2 提交時,發現其讀 key2 的版本為 7,會回滾。如果 T2 先來提交,由於 commit version 為 10 的事務還沒提交(已分配但未提交),它不能提交。 因為 write skew 會避免。write skew 產生的主要原因是讀與寫沒有互斥,FDB 通過讀時檢查是否有更新的提交(而非像 SI 一樣,只讀自己應該讀到的版本)而得知衝突進而回滾。

總之,時間戳單點分配讓 FDB 可以滿足 Linearizability,嚴格的事務衝突處理避免了各種異象,滿足了 Serializability。

3.日誌協議

事務提交是由 Proxy 發起。可以提交時,Proxy 首先根據記憶體裡的 map 確定本事務涉及 key 對應的 SS,例如下例的 1,4,6,然後找到 1,4,6 prefer 的 LS(1,4),Proxy 會廣播發送給所有 LS,但只有發向 LS1, LS4和 LS3 的包含日誌資料(這裡假設需要三副本落盤,LS3 是被挑選出來,作為高可用要求的另一個 LS),其他的都發空廣播。Proxy 收到所有 replica LS 的回覆,並且該日誌對應提交的 LSN 是最大的時候(等待比它小的事務提交完成),更新本地 current KCV(Known committed version)。

SS 以一種激進的策略主動拉取 LS 上的 redo log 回放,甚至在日誌持久化完成前。因此 SS 會拉到可能 abort 的日誌並回放(但基於可見性演算法,不可見),這部分需要 rollback。拉取回放的過程並不在提交路徑裡。FDB 聲稱因為較為激進的回放策略,因此讀延遲並不是很大(讀需要保證在此前提交的事務已經回放完成),大部分讀請求不需要等待,小部分讀請求需要等待,或者傳送到其他 replica。論文給出 Log Server 與 StorageServer 之間 delay 的實驗資料:the 99.9 percentile of the average and maximum delay is 3.96 ms and 208.6 ms。

4.Recovery

在 FDB 的寫邏輯裡,資料寫到 LogServer 多副本就算提交成功了(幾個副本可由使用者指定),StorageServer 不斷非同步拉取 LogServer 的資料回放。StorageServer recovery 和平時非同步回放日誌一模一樣,不用特殊處理。所以 FDB 不需要 Checkpoint,也不需要在 recovery 時專門去回放 checkpoint 後的資料。儘管 FDB 宣稱不需要 Checkpoint,但是 LogServer 上 Log 的 purge 依舊需要依賴 StorageServer 儲存引擎刷髒,這個代價應該是省不了,只是 recovery 速度會加快。

Transaction System Recovery 由 Sequencer 驅動,其過程如下:

(1)Sequencer 向 Coordinators(元資訊) 獲取事務系統相關配置資訊,並上一把”鎖“,表示別的 Sequencer 不能同時 Recover 這個事務系統。

(2)Sequencer 開始恢復宕機重啟的 TS 狀態,包括與該 TS 相關的所有舊的 LogServers。暫停這些 LogServers 繼續接受寫服務。並開啟新的 Resolvers、Proxies 和 LogServers。

(3)這些舊的 LogServers 停止接受寫服務,整個 TS ready 後,Sequencer 將該 TS 的資訊寫到 Coordinator,然後開始接受新的提交。

Resolvers、Proxies 是無狀態的,恢復速度很快,LogServers 的處理則稍微複雜一點,主要是需要決定 the end of redo log ,既找到一個 Recovery Version(RV),在這之前的日誌都 redo,在這之後的都 undo。如何決定 RV 呢?(1)每個 Proxy 維護了一個 KCV,代表它提交過的最大的事務 version。這個資訊會廣播給 LogServers(2)每個 LogServers 儲存了最大的已經持久化事務的 version DV。

Sequencer 傳送請求去停止 m 個 LogServers 時,獲取每個 LogServers 的 KCV 和 DV。所有LogServers 最大的這個 KCV 便是上一個 TS Epoch 的 version ,既 PEV(previous Epoch's end version)。對於當前的 Epoch,start version 是 PEV + 1。同時 Sequencer 選擇最小 DV 作為 RV,[PEV+1,RV]之間的日誌需要拷貝到新的 LogServers,因為這一段日誌其實已經在 k 個節點持久化(因為 RV 是所有舊的 LogServers 中已經持久化的最小的版本),但是可能因為 failure,沒來得及更新 KCV。

5.關鍵測試

這是蘋果內部一個叢集一個月執行的結果,這麼大時間跨度下,看起來效能還比較穩定,可以看到提交延遲還是挺高的,畢竟 RPC 巨多。

這是 FDB 擴充套件性的測試,可以看到並不能隨著機器數增多線性增長。我理解 Resolvers 存在一定程度的單點問題,雖然 Resolviers 看似可以線性擴充套件,但是如果擴充套件的越多,每個 Resolver 負責的 range 就越小,如果一個事務涉及的 keys 跨了 Resolver,兩個 Resolver 都會去處理衝突。一方面算力浪費了,另一方面,兩個 Resolvers 中一個衝突成功,一個失敗,會導致部分假成功,這種情況處理起來也挺複雜。