FoundationDB是一個開源的事務性鍵值存儲系統(tǒng)，是最早將NoSQL架構的靈活性和可擴展性與ACID事務的強大性能相結合的系統(tǒng)之一。FoundationDB架構解耦成一個內(nèi)存中的事務管理系統(tǒng)、一個分布式存儲系統(tǒng)和一個內(nèi)置的分布式配置系統(tǒng)。每個子系統(tǒng)都可以獨立地進行配置，以實現(xiàn)可擴展性、高可用性和容錯性。

FoundationDB還包括了一個確定性仿真框架，用于在可能的故障情況下測試新的功能。這種嚴格的測試使FoundationDB更加穩(wěn)定，并允許開發(fā)人員以快速的節(jié)奏引入和發(fā)布新功能。

同時，F(xiàn)oundationDB提供了一個最小的、精心挑選的功能集，可以在FoundationDB上構建不同的系統(tǒng)。其強大的數(shù)據(jù)一致性、健壯性和可用性，使之成為蘋果、Snowflake和其他公司云基礎設施的基礎，用于存儲用戶數(shù)據(jù)、系統(tǒng)元數(shù)據(jù)和配置以及其他關鍵信息。

1. 背景信息

1.1 當前NoSQL解決與面臨的問題

許多云服務依賴于可擴展的分布式存儲后端來持久化應用程序狀態(tài)。這種存儲系統(tǒng)必須具有容錯性和高可用性，并且同時提供足夠強的語義和靈活的數(shù)據(jù)模型，以便快速進行應用程序開發(fā)。這些服務必須支持能夠擴展到數(shù)十億用戶，存儲的數(shù)據(jù)量為PB或EB，每秒處理數(shù)百萬個請求。

NoSQL系統(tǒng)的出現(xiàn)，提供了應用程序開發(fā)的簡便性，使得擴展和操作存儲系統(tǒng)變得簡單，并提供了容錯性，并支持各種數(shù)據(jù)模型。為了可擴展性，這些NoSQL系統(tǒng)犧牲了事務語義，而提供了數(shù)據(jù)的最終一致性，迫使應用程序開發(fā)人員考慮并發(fā)操作的數(shù)據(jù)更新問題。

1.2 FoundationDB的由來與特點

FoundationDB是在2009年創(chuàng)建的，希望成為構建高級分布式系統(tǒng)所需的基礎系統(tǒng)。它是一個有序的、事務性的、鍵值存儲，本地支持其整個鍵空間的多鍵嚴格序列化事務。它提供了一個高度可擴展的、事務性的存儲引擎，具有精心選擇的最少功能集。它不提供結構化語義、查詢語言、數(shù)據(jù)模型、二級索引或許多其他在事務性數(shù)據(jù)庫中通常找到的功能。

NoSQL模型為應用程序開發(fā)人員提供了很大的靈活性。應用程序可以將數(shù)據(jù)存儲為簡單的鍵值對，但需要實現(xiàn)更高級的功能，例如一致性二級索引和引用完整性檢查。FoundationDB默認為嚴格可序列化事務，但允許在細粒度控制下放松這些語義，以適應不需要這種事務的應用程序。

FoundationDB的流行和日益增長的開源社區(qū)之一的原因是它專注于數(shù)據(jù)庫的“下半部分”，將其余部分留給上面的無狀態(tài)應用程序來提供各種數(shù)據(jù)模型和其他功能。在FoundationDB上構建的各種層證明了這種不尋常設計的有用性。例如，F(xiàn)oundationDB記錄層添加了用戶從關系數(shù)據(jù)庫中期望的大部分內(nèi)容，圖數(shù)據(jù)庫JanusGraph提供了一個基于FoundationDB層的實現(xiàn)。CouchDB正在重新構建為FoundationDB的一個層。因此，傳統(tǒng)上的應用程序可以同樣使用FoundationDB。

測試和調(diào)試分布式系統(tǒng)與構建一樣困難。意外的進程和網(wǎng)絡故障、消息重新排序和其他非確定性的來源可能會暴露出隱含的假設，這些假設在現(xiàn)實中會被破壞，這些錯誤非常難以重現(xiàn)或調(diào)試。這些錯誤對于明確的數(shù)據(jù)庫系統(tǒng)往往是致命的。此外，數(shù)據(jù)庫系統(tǒng)的有狀態(tài)性質(zhì)意味著任何這樣的錯誤都可能導致數(shù)據(jù)損壞，但或許可能需要幾個月才能發(fā)現(xiàn)。模型檢查技術可以驗證分布式協(xié)議的正確性，但往往無法檢查實際實現(xiàn)。深層次的漏洞，只有在特定順序的多個崩潰時才會發(fā)生，對端到端測試構成了挑戰(zhàn)。

FoundationDB采取了一種激進的方法——在構建數(shù)據(jù)庫本身之前，構建了一個確定性的數(shù)據(jù)庫仿真框架，可以模擬相互作用的進程網(wǎng)絡和各種磁盤、進程、網(wǎng)絡和請求級故障和恢復，所有這些都在一個物理進程內(nèi)完成。專門為此目的創(chuàng)建了C++的語法擴展Flow。這種在模擬中的嚴格測試使得FoundationDB非常穩(wěn)定，并允許其開發(fā)人員以快速的節(jié)奏引入新的功能和發(fā)布。

FoundationDB的松耦合架構由控制平面和數(shù)據(jù)平面組成。控制平面管理集群元數(shù)據(jù)，并使用Active Disk Paxos來實現(xiàn)高可用性。數(shù)據(jù)平面由事務管理系統(tǒng)和分布式存儲層組成，前者負責處理更新，后者負責提供讀取；兩者可以獨立擴展。FoundationDB通過樂觀并發(fā)控制和多版本并發(fā)控制的組合實現(xiàn)了嚴格的串行化。

FoundationDB與其他分布式數(shù)據(jù)庫不同的一個特點是其處理故障的方法。FoundationDB不依賴于仲裁機制，而是嘗試通過重新配置系統(tǒng)來積極檢測和恢復故障。這使得我們可以在資源更少的情況下實現(xiàn)相同級別的容錯性：FoundationDB可以容忍n個故障，而只需要n+ 1（而不是2n + 1）個副本。這種方法適合于本地或大區(qū)部署。對于廣域網(wǎng)部署提供了一種新穎的策略，避免跨區(qū)域?qū)懭胙舆t，同時在區(qū)域之間提供自動故障轉(zhuǎn)移，而不會丟失數(shù)據(jù)。

2. 設計原則與系統(tǒng)架構

FoundationDB的主要設計原則是分而治之、面向故障的設計和仿真測試。

FoundationDB將事務管理系統(tǒng)（寫）與分布式存儲系統(tǒng)（讀）解耦，并獨立地擴展它們。在事務管理系統(tǒng)中，進程被分配為代表事務管理的不同方面的各種角色。此外，集群范圍內(nèi)的編排任務，如過載控制和負載平衡，也被劃分并由其他不同的角色提供服務。

對于分布式系統(tǒng)而言，故障是一種必然而非例外。為了應對事務管理系統(tǒng)中的故障，需要恢復處理所有故障：當檢測到故障時，事務系統(tǒng)主動關閉。因此，所有故障處理都被簡化為單個恢復操作，這成為了常見的、經(jīng)過充分測試的代碼路徑。為了提高可用性，F(xiàn)oundationDB努力將平均恢復時間（MTTR）最小化。在我們的生產(chǎn)集群中，總時間通常不超過五秒。

FoundationDB依賴于一種隨機、確定性的模擬測試框架，用于測試其分布式數(shù)據(jù)庫的正確性。模擬測試框架不僅暴露深層次的錯誤，而且提高了開發(fā)人員的生產(chǎn)力和FoundationDB的代碼質(zhì)量。

2.1. 架構

FoundationDB集群具有用于管理關鍵系統(tǒng)元數(shù)據(jù)和群集范圍編排的控制面板，以及用于事務處理和數(shù)據(jù)存儲的數(shù)據(jù)面板，如下圖所示。

控制平面

控制平面負責將關鍵系統(tǒng)元數(shù)據(jù)（即事務系統(tǒng)配置）持久化在協(xié)調(diào)器上。這些協(xié)調(diào)器形成一個Paxos組，并選舉出一個集群控制器。集群控制器監(jiān)控集群中的所有服務器，并維護三個進程：序列器、數(shù)據(jù)分發(fā)器和速率控制器。如果它們失敗或崩潰，則這些進程會重新啟動。數(shù)據(jù)分發(fā)器負責監(jiān)控故障并平衡存儲服務器之間的數(shù)據(jù)。速率控制器為集群提供過載保護。

數(shù)據(jù)平面

FoundationDB適用于讀多寫少、每個事務讀寫少量關鍵字、需要可擴展性的OLTP工作負載。分布式事務管理系統(tǒng)由序列器、代理和分區(qū)范圍解析器組成，所有這些都是無狀態(tài)進程。日志系統(tǒng)存儲TS的寫前日志，而單獨的分布式存儲系統(tǒng)用于存儲數(shù)據(jù)和提供讀取服務。日志系統(tǒng)包含一組日志服務器，而分布式存儲系統(tǒng)具有多個存儲服務器。序列器為每個事務分配讀取和提交版本。代理為客戶端提供多版本讀取并協(xié)調(diào)事務提交。解析器檢查事務之間的沖突。日志服務器充當復制、分片和分布式持久隊列，每個隊列存儲一個存儲服務器的WAL數(shù)據(jù)。分布式存儲系統(tǒng)由多個存儲服務器組成，每個存儲服務器存儲一組數(shù)據(jù)分片，即連續(xù)的鍵范圍，并提供客戶端讀取。存儲服務器是系統(tǒng)中大部分進程，并且它們一起形成分布式B樹。每個存儲服務器上的存儲引擎是SQLite的增強版本，其中增強使范圍清除更快，將刪除推遲到后臺任務，并添加了異步編程支持。

2.1.1 讀寫分離和擴展

上述進程被分配為不同的角色，通過為每個角色添加新的進程來進行擴展。客戶端從分片的存儲服務器中讀取，因此讀取隨著存儲服務器的數(shù)量線性擴展。通過添加更多的代理、解析器和日志服務器來擴展寫入。控制平面的單例進程（例如集群控制器和序列器）和協(xié)調(diào)器不是性能瓶頸；它們只執(zhí)行有限的元數(shù)據(jù)操作。

2.1.2 引導啟動

FoundationDB沒有對外部協(xié)調(diào)服務的依賴。所有用戶數(shù)據(jù)和大部分系統(tǒng)元數(shù)據(jù)都存儲在存儲服務器中。有關存儲服務器的元數(shù)據(jù)存儲在日志服務器中，并且日志服務器的配置數(shù)據(jù)存儲在所有協(xié)調(diào)器中。協(xié)調(diào)器是一個磁盤Paxos組；如果不存在集群控制器，則服務器會嘗試成為集群控制器。新選舉的集群控制器從協(xié)調(diào)器中讀取舊的LS配置，并生成新的事務服務器和日志服務器。代理從舊的LS中恢復系統(tǒng)元數(shù)據(jù)，包括有關所有存儲服務器的信息。序列器等待新的事務服務器完成恢復，然后將新的日志服務器配置寫入所有協(xié)調(diào)器。新的事務系統(tǒng)隨后準備好接收客戶端事務。

2.1.3 重新配置

序列器進程監(jiān)視代理，解析器和日志服務器的健康狀況。每當日志服務器或日志服務器出現(xiàn)故障，或數(shù)據(jù)庫配置更改時，序列器將終止。集群控制器檢測到序列器故障，然后啟動并引導新的事務服務器和日志服務器。通過這種方式，事務處理被分為各個時期，每個時期代表一個具有自己序列器的事務管理系統(tǒng)的生成。

2.2. 事務管理

2.2.1 端到端的事務處理

客戶端事務首先通過聯(lián)系其中一個代理來獲取讀版本（即時間戳）。代理然后請求序列器 生成至少與先前發(fā)出的所有事務提交版本一樣的讀版本，并將此讀版本發(fā)送回客戶端。然后，客戶端可以向存儲服務器發(fā)出讀取并在特定讀版本下獲取值。客戶端寫入被本地緩存而不與群集聯(lián)系，事務的數(shù)據(jù)庫查找結果與未提交的寫入組合以保留讀取。在提交時，客戶端將事務數(shù)據(jù)發(fā)送到其中一個代理，并等待提交或中止響應。如果事務無法提交，客戶端可以選擇重新啟動它。

代理以三個步驟提交客戶端事務。首先，它聯(lián)系序列器 以獲得大于任何現(xiàn)有讀版本或提交版本的提交版本。序列器通過每秒最高100萬個版本的速率選擇提交版本。然后，代理將事務信息發(fā)送到分區(qū)范圍解析器，后者通過檢查讀寫沖突來實現(xiàn)FoundationDB的樂觀并發(fā)控制。如果所有解析器都沒有沖突，則事務可以進入最終提交階段。否則，代理將事務標記為已中止。最后，提交的事務被發(fā)送到一組日志服務器進行持久化。在所有指定的日志服務器都回復代理之后，事務被視為已提交，代理將提交的版本報告給序列器然后回復客戶端。存儲服務器不斷地從日志服務器拉取變異日志，并將已提交的更新應用到磁盤上。

除了上述的讀寫事務，F(xiàn)oundationDB還支持只讀事務和快照讀取，其中的只讀事務既可以串行化（在讀取版本時發(fā)生）又高效，客戶端可以在不與數(shù)據(jù)庫聯(lián)系的情況下本地提交這些事務。FoundationDB中的快照讀取通過減少沖突來選擇性地放寬事務的隔離屬性，即并發(fā)寫入不會與快照讀取沖突。

2.2.2 嚴格串行化

FoundationDB通過將優(yōu)化并發(fā)控制與多版本控制相結合來實現(xiàn)可串行化快照隔離。回想一下，事務Tx從序列器獲取它的讀取版本和提交版本，其中讀取版本號保證不小于Tx啟動時的任何提交版本，而提交版本大于任何現(xiàn)有的讀取或提交版本號。這個提交版本定義了事務的串行歷史，并用作日志序列號（LSN）。因為Tx觀察到了所有先前提交的事務的結果，F(xiàn)oundationDB實現(xiàn)了嚴格的串行化。為了確保日志序列號之間沒有間隙，序列器在每個提交版本中返回前一個提交版本。代理將LSN和前一個LSN發(fā)送給解析器和日志服務器，以便它們可以按照LSN的順序串行處理事務。

類似地，存儲服務器按增加的LSN順序從日志服務器提取日志數(shù)據(jù)。分區(qū)范圍解析器使用類似于寫入快照隔離的無鎖沖突檢測算法，不同之處在于在FoundationDB中選擇提交版本之前進行沖突檢測。這使得FoundationDB可以高效地批量處理版本分配和沖突檢測。整個鍵空間被劃分在分區(qū)范圍解析器之間，允許并行執(zhí)行沖突檢測。只有當所有的分區(qū)范圍解析器都承認事務時，事務才能提交。否則，事務將被中止。有可能一個被中止的事務被一部分分區(qū)范圍解析器承認，并且它們已經(jīng)更新了可能提交的事務的歷史記錄，這可能導致其他事務發(fā)生沖突（即假陽性）。

在實踐中，這對于生產(chǎn)環(huán)境的工作負載來說并不是問題，因為事務的鍵范圍通常屬于一個分區(qū)范圍解析器。此外，由于修改后的鍵在多版本控制窗口后會過期，因此這樣的假陽性只會在短暫的多版本控制窗口時間內(nèi)發(fā)生（即5秒）。FoundationDB的優(yōu)化并發(fā)控制設計機制避免了獲取和釋放鎖的復雜邏輯，極大地簡化了事務服務和存儲服務之間的交互。代價是被中止的事務會浪費工作。

在多租戶的生產(chǎn)負載中，事務沖突率非常低（小于1%），優(yōu)化并發(fā)控制運行良好。如果發(fā)生沖突，客戶端可以簡單地重新啟動事務。

2.2.3 日志協(xié)議

在代理決定提交事務后，向所有日志服務器發(fā)送消息：變更被發(fā)送到負責修改鍵范圍的日志服務器，而其他日志服務器接收一個空消息體。日志消息頭包括從序列器獲得的當前和先前的LSN以及此代理的最大已知提交版本。日志服務器使日志數(shù)據(jù)持久化后，會回復給代理，如果所有副本日志服務器都已回復，并且此LSN大于當前KCV，則代理會將其KCV更新為LSN，并將重做日志從LS發(fā)送到存儲服務器不是提交路徑的一部分，而是在后臺執(zhí)行的。

在FoundationDB中，存儲服務器將非持久化的重做日志從日志服務器應用到內(nèi)存索引中。通常情況下，這發(fā)生在任何反映提交的讀版本被分配給客戶端之前，允許服務多版本讀取非常低的延遲。因此，當客戶端讀取請求到達存儲服務器時，請求的版本（即最新提交的數(shù)據(jù)）通常已經(jīng)可用。如果在存儲服務器副本上沒有可讀的新數(shù)據(jù)，則客戶端會等待數(shù)據(jù)可用，或者在另一個副本上重新發(fā)出請求。

如果兩者都超時，客戶端可以簡單地重新啟動事務。由于日志數(shù)據(jù)已經(jīng)在日志服務器上持久化，存儲服務器可以在內(nèi)存中緩沖更新，并定期將數(shù)據(jù)批量持久化到磁盤上，從而提高I / O效率。

2.2.4 事務系統(tǒng)恢復

傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)通常采用ARIES恢復協(xié)議。在恢復過程中，系統(tǒng)通過將重做日志記錄重新應用于相關數(shù)據(jù)頁面來處理從上一個檢查點開始的日志記錄。這使數(shù)據(jù)庫達到一致的狀態(tài)；在崩潰期間進行的事務可以通過執(zhí)行撤銷日志記錄來回滾。在FoundationDB中，恢復被故意地設計得非常便宜 - 沒有必要應用撤銷日志條目。這是由于一個極其簡化的設計選擇：重做日志處理與正常的日志前進路徑相同。 

在FoundationDB中，存儲服務器從日志服務器拉取日志并在后臺應用它們。恢復過程從檢測故障并招募新的事務系統(tǒng)開始。在舊的日志服務器中的所有數(shù)據(jù)被處理之前，新的TS可以接受事務。恢復只需要找到重做日志的結尾：在該點（與正常的正向操作相同），存儲服務器異步重放日志。

對于每個時期，集群控制器在幾個步驟中執(zhí)行恢復。首先，它從協(xié)調(diào)器中讀取先前的TS配置，并鎖定此信息以防止另一個并發(fā)恢復。接下來，它恢復先前的TS系統(tǒng)狀態(tài)，包括有關舊日志服務器的信息，停止它們接受事務，并招募一組新的序列器，代理，解析器和日志服務器。在先前的日志服務器停止并啟動新的事務服務器之后，集群控制器將新的事務服務器信息寫入?yún)f(xié)調(diào)器。因為代理和解析程序是無狀態(tài)的，它們的恢復沒有額外的工作。相反，日志服務器保存已提交事務的日志，我們需要確保所有這些事務都是持久性的，并且可以由存儲服務器檢索。恢復舊日志服務器的本質(zhì)是確定重做日志的結尾，即恢復版本（RV）。滾動撤銷日志本質(zhì)上是在舊的日志服務器和存儲服務器中丟棄RV之后的任何數(shù)據(jù)。圖2說明了如何由序列器確定RV。

代理請求日志服務器會搭載其KCV，即此代理已提交的最大LSN，以及當前事務的LSN。每個日志服務器保留收到的最大KCV和持久的版本，它是LogServer持久的最大LSN。在恢復過程中，序列器嘗試停止所有m個舊日志服務器，每個響應都包含該日志服務器上的DV和KCV。 

假設日志服務器的復制度為k。一旦序列器收到超過m-k個回復，序列器就知道上一個時期已提交的事務達到了所有KCV的最大值，這成為上一個時期的結束版本（PEV）。所有此版本之前的數(shù)據(jù)都已完全復制。對于當前時期，其起始版本為PEV +1，序列器選擇所有DV的最小值作為RV。在[PEV + 1，RV]范圍內(nèi)的日志從上一個時期的日志服務器復制到當前時期的日志服務器，以在日志服務器故障的情況下修復復制度。復制此范圍的開銷非常小，因為它只包含幾秒鐘的日志數(shù)據(jù)。

當序列器接受新事務時，第一個事務是一個特殊的恢復事務，它會通知存儲服務器當前RV的值，以便它們可以回滾任何大于RV的數(shù)據(jù)。當前的FoundationDB存儲引擎由一個未版本化的SQLite B樹和內(nèi)存中的多版本重做日志數(shù)據(jù)組成。只有離開多版本控制窗口（即已提交的數(shù)據(jù)）的變異才會寫入SQLite。回滾只是在存儲服務器中丟棄內(nèi)存中的多版本數(shù)據(jù)。然后，存儲服務器從新的日志服務器中拉取任何大于版本PEV的數(shù)據(jù)。

2.3. 復制

FoundationDB使用各種復制策略來容忍不同數(shù)據(jù)的失敗。

2.3.1 元數(shù)據(jù)復制

控制平面的系統(tǒng)元數(shù)據(jù)存儲在協(xié)調(diào)器上，使用Active Disk Paxos。只要協(xié)調(diào)器的多數(shù)（即大多數(shù)）處于活動狀態(tài)，就可以恢復此元數(shù)據(jù)。

2.3.2 日志復制

當代理將日志寫入日志服務器時，每個分片的日志記錄都會同步復制到k = f + 1個日志服務器上。只有當所有k都回復成功持久性后，代理才能向客戶端發(fā)送提交響應。日志服務器故障會導致事務系統(tǒng)恢復。

2.3.3 存儲復制

每個分片（即關鍵字范圍）都異步復制到k = f + 1個存儲服務器，稱為team。存儲服務器通常托管多個分片，以使其數(shù)據(jù)均勻分布在許多團隊中。存儲服務器故障會觸發(fā)數(shù)據(jù)分配器將數(shù)據(jù)從包含失敗進程的團隊移動到其他健康team中。請注意，存儲team抽象比Copysets更為復雜。

為了減少由于同時故障而導致的數(shù)據(jù)丟失的概率，F(xiàn)oundationDB確保在副本組中最多只放置一個進程位于故障域，例如主機、機架或可用區(qū)。每個團隊都保證至少有一個進程處于活動狀態(tài)，如果任何一個相應的故障域仍然可用，則不會丟失數(shù)據(jù)。

2.4 仿真測試

測試和調(diào)試分布式系統(tǒng)是一項具有挑戰(zhàn)性且效率低下的工作。對于FoundationDB來說，這個問題尤為嚴重——它的強并發(fā)控制合約的任何故障都可以在其上層系統(tǒng)中產(chǎn)生幾乎任意的損壞。因此，從一開始就采用了一種雄心勃勃的端到端測試方法：在確定性的離散事件模擬中運行真實的數(shù)據(jù)庫軟件，連同隨機生成的合成工作負載和故障注入。嚴酷的模擬環(huán)境很快會引發(fā)數(shù)據(jù)庫中的錯誤，并且確定性保證每個這樣的錯誤都可以被重現(xiàn)和調(diào)查。

2.4.1 確定性模擬器

FoundationDB從一開始就建立了這種測試方法。所有數(shù)據(jù)庫代碼都是確定性的，并且避免多線程并發(fā)（相反，每個核心部署一個數(shù)據(jù)庫節(jié)點）。下圖說明了FoundationDB的模擬器過程，其中抽象了所有的非確定性和通信源，包括網(wǎng)絡、磁盤、時間和偽隨機數(shù)生成器。FoundationDB是用Flow編寫的，這是一種新穎的C++語法擴展，添加了類似async/await的并發(fā)原語和自動取消，允許高并發(fā)代碼以確定性方式執(zhí)行。Flow提供了Actor編程模型，它將FoundationDB服務器進程的各種操作抽象成多個由Flow運行時庫調(diào)度的actor。模擬器進程能夠生成多個FoundationDB服務器，在單個離散事件模擬中通過模擬的網(wǎng)絡相互通信。生產(chǎn)實現(xiàn)是到相關系統(tǒng)調(diào)用的簡單橋接。

模擬器運行多個工作負載，通過模擬網(wǎng)絡與模擬的 FoundationDB 服務器通信。這些工作負載包括故障注入指令、模擬應用程序、數(shù)據(jù)庫配置更改和內(nèi)部數(shù)據(jù)庫功能調(diào)用。工作負載是可組合的，以測試各種功能，并被重復使用以構建全面的測試用例。

2.4.2 測試代理

FoundationDB 使用各種測試代理來檢測模擬中的故障。大多數(shù)合成工作負載內(nèi)置了斷言來驗證數(shù)據(jù)庫的合同和屬性，例如通過檢查數(shù)據(jù)中的不變量來驗證其只能通過事務原子性和隔離性來維護。斷言在整個代碼庫中用于檢查可以“本地”驗證的屬性。像可恢復性（最終可用性）這樣的屬性可以通過將建模的硬件環(huán)境（在足以破壞數(shù)據(jù)庫可用性的故障集之后）返回到應該可能恢復的狀態(tài)，并驗證集群最終恢復來檢查。

2.4.3 故障注入

模擬注入機器、機架和數(shù)據(jù)中心故障和重啟、各種網(wǎng)絡故障、分區(qū)和延遲問題、磁盤行為（例如機器重啟時未同步寫入的損壞）以及隨機化事件。這種故障注入的多樣性既測試了數(shù)據(jù)庫對特定故障的彈性，又增加了模擬中狀態(tài)的多樣性。故障注入分布經(jīng)過精心調(diào)整，以避免過高的故障率導致系統(tǒng)進入小狀態(tài)空間。FoundationDB本身通過一種高級故障注入技術與模擬器合作，使得罕見的狀態(tài)和事件更加常見，這種技術非正式地稱為“buggification”。

在其代碼庫的許多地方，模擬器允許注入一些不尋常（但不違反契約的）行為，例如在通常成功的操作中不必要地返回錯誤，注入通常很快的操作的延遲，或選擇一個異常值的調(diào)整參數(shù)等。這與網(wǎng)絡和硬件層面的故障注入相輔相成。調(diào)整參數(shù)的隨機化也確保特定的性能調(diào)整值不會意外地變得必要以確保正確性。Swarm測試廣泛用于最大化模擬運行的多樣性。每次運行都使用隨機的群集大小和配置、隨機的工作負載、隨機的故障注入?yún)?shù)、隨機的調(diào)整參數(shù)，并啟用和禁用隨機子集的buggification點。

我們已經(jīng)開源了FoundationDB的Swarm測試框架。條件覆蓋宏用于評估和調(diào)整模擬的有效性。例如，一個開發(fā)人員擔心新的代碼可能很少使用完整的緩沖區(qū)，可以添加一行 TEST(buffer.is_full())；模擬結果的分析將告訴他們有多少個不同的模擬運行達到了該條件。如果數(shù)量過低或為零，他們可以添加buggification、工作負載或故障注入功能，以確保該場景得到充分測試。

2.4.4 發(fā)現(xiàn)錯誤的延遲

快速發(fā)現(xiàn)錯誤對于在生產(chǎn)之前在測試中遇到它們以及提高工程生產(chǎn)力都非常重要，在單個提交中立即發(fā)現(xiàn)的錯誤可以輕松地追溯到該提交。如果模擬器內(nèi)部的CPU利用率低，則離散事件模擬可以以任意快的速度運行，因為模擬器可以將時鐘快進到下一個事件。許多分布式系統(tǒng)錯誤需要時間才能發(fā)現(xiàn)，并且在具有長時間低利用率的模擬中運行可以比“真實世界”端到端測試每個核心發(fā)現(xiàn)更多此類錯誤。此外，隨機測試具有令人尷尬的并行性，F(xiàn)oundationDB開發(fā)人員可以和確實會在主要發(fā)布之前“爆發(fā)”測試的數(shù)量，以期捕獲到迄今為止逃避測試過程的異常稀有的錯誤。由于搜索空間實際上是無限的，運行更多的測試會導致覆蓋更多的代碼并發(fā)現(xiàn)更多的潛在錯誤，與腳本化的功能或系統(tǒng)測試形成對比。

2.4.5 仿真測試的局限

仿真無法可靠地檢測性能問題，例如不完美的負載均衡算法。它也無法測試第三方庫或依賴項，甚至無法測試在Flow中未實現(xiàn)的一方代碼。因此，我們大多避免了對外部系統(tǒng)的依賴。最后，關鍵依賴系統(tǒng)（例如文件系統(tǒng)或操作系統(tǒng)）中的錯誤或?qū)ζ浼s定的誤解可能導致FoundationDB中的錯誤。例如，一些錯誤是由于真正的操作系統(tǒng)約定比預期的要弱而導致的。

4. 評估方法

使用合成工作負載來評估FoundationDB的性能。具體而言，有四種類型：(1) 盲寫，更新配置的隨機鍵的數(shù)量；(2) 區(qū)間讀取，從隨機鍵開始獲取配置的連續(xù)鍵的數(shù)量；(3) 點讀取，獲取n個隨機鍵；和(4) 點寫入，獲取m個隨機鍵并更新另外m個隨機鍵。通過盲寫和區(qū)間讀取來評估寫入和讀取性能，點讀取和點寫入一起用來評估混合讀寫性能。確保數(shù)據(jù)集無法完全緩存在StorageServers的內(nèi)存中。

在最大寫入吞吐量下，日志服務器的CPU利用率達到飽和狀態(tài)。對于讀取和寫入操作，增加事務中的操作數(shù)可以提高吞吐量。然而，進一步增加操作數(shù)不會帶來顯著的改變，解析器和代理的CPU利用率也可達到飽和狀態(tài)。提交請求涉及多個跳和持久化到三個日志服務器，因此延遲比讀取和讀版本高。批處理有助于保持吞吐量，但由于飽和，提交延遲會激增。

由于面向客戶的性質(zhì)，短暫的重新配置時間對于這些集群的高可用性至關重要。這些短暫的恢復時間是由于它們不受數(shù)據(jù)或事務日志大小的限制，只與系統(tǒng)元數(shù)據(jù)大小相關。在恢復過程中，讀寫事務被臨時阻塞，并在超時后重試。然而，客戶端讀取不會受到影響。導致這些重新配置的原因包括軟件或硬件故障的自動故障恢復、軟件升級、數(shù)據(jù)庫配置更改以及對生產(chǎn)問題的手動處理。

5. FoundationDB的核心特性

5.1. 架構設計

分而治之的設計原則在實現(xiàn)云部署時起到了重要的作用，使數(shù)據(jù)庫既具備可擴展性又能保持性能優(yōu)良。

首先，將事務系統(tǒng)與存儲層分離使得計算和存儲資源能夠更加靈活地獨立部署和擴展。此外，日志服務器的引入類似于驗證副本，在一些多區(qū)域生產(chǎn)部署中，日志服務器顯著減少了實現(xiàn)高可用性所需的存儲服務器（完全副本）的數(shù)量。運營人員還可以自由地將FoundationDB的不同角色部署在不同類型的服務器實例上，以優(yōu)化性能和成本。

其次，這種松耦合的設計使得可以擴展數(shù)據(jù)庫的功能，例如可以用RocksDB替換現(xiàn)有的SQLite引擎。

最后，許多性能改進可以通過將功能專門化為獨立的角色來實現(xiàn)的，例如將數(shù)據(jù)分配器和流頻控與序列器分離，添加存儲緩存，將代理分為讀版本Proxy和提交Proxy。這種設計模式實現(xiàn)了頻繁添加新功能和擴展能力的目標。

5.2. 仿真測試

仿真測試使FoundationDB能夠以小團隊保持高開發(fā)速度。這是通過縮短引入錯誤和發(fā)現(xiàn)錯誤之間的延遲時間，以及允許確定性重現(xiàn)問題來實現(xiàn)的。例如，添加額外的日志不會影響事件的確定性順序，因此可以確保精確重現(xiàn)。這種調(diào)試方法的生產(chǎn)力要比正常的生產(chǎn)環(huán)境調(diào)試高得多。在極少數(shù)情況下，在真實環(huán)境中首次發(fā)現(xiàn)的錯誤，調(diào)試過程通常會先改進模擬的能力或準確性，直到問題在模擬中可以被重現(xiàn)，然后才開始正常的調(diào)試流程。通過模擬進行嚴格的正確性測試使FoundationDB變得極其可靠。

仿真測試不斷地推動可模擬性測試的邊界，通過消除依賴并在Flow中來實現(xiàn)。例如，早期版本的FoundationDB依賴于Apache Zookeeper進行協(xié)調(diào)，已被在Flow中自行實現(xiàn)的全新Paxos替代。

5.3. 快速恢復

快速恢復不僅有助于提高可用性，還極大地簡化了軟件升級和配置更改，并使其更快速。傳統(tǒng)的分布式系統(tǒng)升級方法是進行滾動升級，以便在出現(xiàn)問題時可以回滾。滾動升級的持續(xù)時間可能會持續(xù)幾個小時到幾天。相比之下，F(xiàn)oundationDB可以通過同時重新啟動所有進程來執(zhí)行升級，通常在幾秒鐘內(nèi)完成。此外，這種升級路徑還簡化了不同版本之間的協(xié)議兼容性問題，無需確保不同軟件版本之間的RPC協(xié)議兼容性。另外，快速恢復有時可以自動修復潛在的錯誤，這類似于軟件復活技術。

5.4. 五秒的MVCC窗口

FoundationDB選擇了一個5秒的多版本并發(fā)控制窗口來限制事務系統(tǒng)和存儲服務器的內(nèi)存使用，因為多版本數(shù)據(jù)存儲在解析器和存儲服務器的內(nèi)存中，這限制了事務的大小。這個5秒的窗口對于大多數(shù)在線事務處理的使用場景已經(jīng)足夠長了。因此，超過時間限制通常會暴露出應用程序中的低效問題。

對于一些可能超過5秒的事務，很多可以分成更小的事務來處理。例如，F(xiàn)oundationDB的持續(xù)備份過程會掃描整個鍵空間并創(chuàng)建鍵范圍的快照。由于5秒的限制，掃描過程被分成了許多小的范圍，以便每個范圍可以在5秒內(nèi)完成。實際上，這是一個常見的模式：一個事務創(chuàng)建了多個任務，每個任務可以進一步劃分或在一個事務中執(zhí)行。FoundationDB在一個叫做“任務桶（TaskBucket）”的抽象中實現(xiàn)了這樣的模式，而備份系統(tǒng)在很大程度上依賴于它。

6.小結

FoundationDB是一個為了OLTP云服務而設計的分布式鍵值存儲。其主要思想是將事務處理與日志記錄和存儲分離。這種解耦的架構使得讀寫處理的分離和水平擴展成為可能。事務系統(tǒng)結合了樂觀并發(fā)控制（OCC）和多版本并發(fā)控制（MVCC），以確保嚴格的串行化。日志記錄的解耦和事務順序的確定性極大簡化了恢復過程，從而實現(xiàn)了異常快速的恢復時間和提高了可用性。最后，確定性和隨機模擬確保了數(shù)據(jù)庫實現(xiàn)的正確性。

【參考資料與關聯(lián)閱讀】

• FoundationDB. https://github.com/apple/foundationdb.
• Flow. https://github.com/apple/foundationdb/tree/master/flow.
• FoundationDB Joshua. https://github.com/FoundationDB/FoundationDB-joshua.
• Foundationdb storage adapter for janusgraph. https://github.com/JanusGraph/janusgraph-foundationdb.
• Rocksdb. https://rocksdb.org/.
• SQLite.  https://www.sqlite.org/index.html.
• CouchDB. https://couchdb.apache.org/.