FoundationDB是一個開源的事務性鍵值存儲系統(tǒng)，是最早將NoSQL架構的靈活性和可擴展性與ACID事務的強大性能相結合的系統(tǒng)之一。FoundationDB架構解耦成一個內存中的事務管理系統(tǒng)、一個分布式存儲系統(tǒng)和一個內置的分布式配置系統(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ù)庫中期望的大部分內容，圖數(shù)據(jù)庫JanusGraph提供了一個基于FoundationDB層的實現(xiàn)。CouchDB正在重新構建為FoundationDB的一個層。因此，傳統(tǒng)上的應用程序可以同樣使用FoundationDB。

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

FoundationDB采取了一種激進的方法——在構建數(shù)據(jù)庫本身之前，構建了一個確定性的數(shù)據(jù)庫仿真框架，可以模擬相互作用的進程網絡和各種磁盤、進程、網絡和請求級故障和恢復，所有這些都在一個物理進程內完成。專門為此目的創(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ū)部署。對于廣域網部署提供了一種新穎的策略，避免跨區(qū)域寫入延遲，同時在區(qū)域之間提供自動故障轉移，而不會丟失數(shù)據(jù)。

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

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

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

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

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

2.1. 架構

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

控制平面

控制平面負責將關鍵系統(tǒng)元數(shù)據(jù)（即事務系統(tǒng)配置）持久化在協(xié)調器上。這些協(xié)調器形成一個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é)調事務提交。解析器檢查事務之間的沖突。日志服務器充當復制、分片和分布式持久隊列，每個隊列存儲一個存儲服務器的WAL數(shù)據(jù)。分布式存儲系統(tǒng)由多個存儲服務器組成，每個存儲服務器存儲一組數(shù)據(jù)分片，即連續(xù)的鍵范圍，并提供客戶端讀取。存儲服務器是系統(tǒng)中大部分進程，并且它們一起形成分布式B樹。每個存儲服務器上的存儲引擎是SQLite的增強版本，其中增強使范圍清除更快，將刪除推遲到后臺任務，并添加了異步編程支持。

2.1.1 讀寫分離和擴展

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

2.1.2 引導啟動

FoundationDB沒有對外部協(xié)調服務的依賴。所有用戶數(shù)據(jù)和大部分系統(tǒng)元數(shù)據(jù)都存儲在存儲服務器中。有關存儲服務器的元數(shù)據(jù)存儲在日志服務器中，并且日志服務器的配置數(shù)據(jù)存儲在所有協(xié)調器中。協(xié)調器是一個磁盤Paxos組；如果不存在集群控制器，則服務器會嘗試成為集群控制器。新選舉的集群控制器從協(xié)調器中讀取舊的LS配置，并生成新的事務服務器和日志服務器。代理從舊的LS中恢復系統(tǒng)元數(shù)據(jù)，包括有關所有存儲服務器的信息。序列器等待新的事務服務器完成恢復，然后將新的日志服務器配置寫入所有協(xié)調器。新的事務系統(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ū)范圍解析器承認，并且它們已經更新了可能提交的事務的歷史記錄，這可能導致其他事務發(fā)生沖突（即假陽性）。

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

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

2.2.3 日志協(xié)議

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

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

如果兩者都超時，客戶端可以簡單地重新啟動事務。由于日志數(shù)據(jù)已經在日志服務器上持久化，存儲服務器可以在內存中緩沖更新，并定期將數(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é)調器中讀取先前的TS配置，并鎖定此信息以防止另一個并發(fā)恢復。接下來，它恢復先前的TS系統(tǒng)狀態(tài)，包括有關舊日志服務器的信息，停止它們接受事務，并招募一組新的序列器，代理，解析器和日志服務器。在先前的日志服務器停止并啟動新的事務服務器之后，集群控制器將新的事務服務器信息寫入協(xié)調器。因為代理和解析程序是無狀態(tài)的，它們的恢復沒有額外的工作。相反，日志服務器保存已提交事務的日志，我們需要確保所有這些事務都是持久性的，并且可以由存儲服務器檢索。恢復舊日志服務器的本質是確定重做日志的結尾，即恢復版本（RV）。滾動撤銷日志本質上是在舊的日志服務器和存儲服務器中丟棄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]范圍內的日志從上一個時期的日志服務器復制到當前時期的日志服務器，以在日志服務器故障的情況下修復復制度。復制此范圍的開銷非常小，因為它只包含幾秒鐘的日志數(shù)據(jù)。

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

2.3. 復制

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

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

控制平面的系統(tǒng)元數(shù)據(jù)存儲在協(xié)調器上，使用Active Disk Paxos。只要協(xié)調器的多數(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 仿真測試

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

2.4.1 確定性模擬器

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

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

2.4.2 測試代理

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

2.4.3 故障注入

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

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

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

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

快速發(fā)現(xiàn)錯誤對于在生產之前在測試中遇到它們以及提高工程生產力都非常重要，在單個提交中立即發(fā)現(xiàn)的錯誤可以輕松地追溯到該提交。如果模擬器內部的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)）中的錯誤或對其約定的誤解可能導致FoundationDB中的錯誤。例如，一些錯誤是由于真正的操作系統(tǒng)約定比預期的要弱而導致的。

4. 評估方法

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

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

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

5. FoundationDB的核心特性

5.1. 架構設計

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

首先，將事務系統(tǒng)與存儲層分離使得計算和存儲資源能夠更加靈活地獨立部署和擴展。此外，日志服務器的引入類似于驗證副本，在一些多區(qū)域生產部署中，日志服務器顯著減少了實現(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)。這種調試方法的生產力要比正常的生產環(huán)境調試高得多。在極少數(shù)情況下，在真實環(huán)境中首次發(fā)現(xiàn)的錯誤，調試過程通常會先改進模擬的能力或準確性，直到問題在模擬中可以被重現(xiàn)，然后才開始正常的調試流程。通過模擬進行嚴格的正確性測試使FoundationDB變得極其可靠。

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

5.3. 快速恢復

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

5.4. 五秒的MVCC窗口

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

對于一些可能超過5秒的事務，很多可以分成更小的事務來處理。例如，F(xiàn)oundationDB的持續(xù)備份過程會掃描整個鍵空間并創(chuàng)建鍵范圍的快照。由于5秒的限制，掃描過程被分成了許多小的范圍，以便每個范圍可以在5秒內完成。實際上，這是一個常見的模式：一個事務創(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/.