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

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

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

1. 背景信息

1.1 當(dāng)前NoSQL解決與面臨的問題

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

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

1.2 FoundationDB的由來與特點(diǎn)

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

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

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

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

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

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

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

2. 設(shè)計(jì)原則與系統(tǒng)架構(gòu)

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

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

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

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

2.1. 架構(gòu)

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

控制平面

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

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

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

2.1.1 讀寫分離和擴(kuò)展

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

2.1.2 引導(dǎo)啟動(dòng)

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

2.1.3 重新配置

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

2.2. 事務(wù)管理

2.2.1 端到端的事務(wù)處理

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

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

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

2.2.2 嚴(yán)格串行化

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

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

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

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

2.2.3 日志協(xié)議

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

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

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

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

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

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

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

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

假設(shè)日志服務(wù)器的復(fù)制度為k。一旦序列器收到超過m-k個(gè)回復(fù)，序列器就知道上一個(gè)時(shí)期已提交的事務(wù)達(dá)到了所有KCV的最大值，這成為上一個(gè)時(shí)期的結(jié)束版本（PEV）。所有此版本之前的數(shù)據(jù)都已完全復(fù)制。對于當(dāng)前時(shí)期，其起始版本為PEV +1，序列器選擇所有DV的最小值作為RV。在[PEV + 1，RV]范圍內(nèi)的日志從上一個(gè)時(shí)期的日志服務(wù)器復(fù)制到當(dāng)前時(shí)期的日志服務(wù)器，以在日志服務(wù)器故障的情況下修復(fù)復(fù)制度。復(fù)制此范圍的開銷非常小，因?yàn)樗话瑤酌腌姷娜罩緮?shù)據(jù)。

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

2.3. 復(fù)制

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

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

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

2.3.2 日志復(fù)制

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

2.3.3 存儲(chǔ)復(fù)制

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

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

2.4 仿真測試

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

2.4.1 確定性模擬器

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

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

2.4.2 測試代理

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

2.4.3 故障注入

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

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

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

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

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

2.4.5 仿真測試的局限

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

4. 評估方法

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

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

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

5. FoundationDB的核心特性

5.1. 架構(gòu)設(shè)計(jì)

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

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

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

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

5.2. 仿真測試

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

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

5.3. 快速恢復(fù)

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

5.4. 五秒的MVCC窗口

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

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

6.小結(jié)

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

【參考資料與關(guā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/.