一致的後端和UX：新算法如何幫助？-css教學-PHP中文網

許多現代數據庫使用最先進的算法來消除一致性和性能之間的權衡。當然，如果沒有適當的解釋，我們不希望您輕信我們的說法。因此，在本文的最後一部分，我們將深入探討其中一些數據庫背後的技術細節。通常，這些技術細節的唯一信息來源是研究論文，因此本文的目的是用更簡單的術語解釋這些系統。由於這些系統在現實中要復雜得多，因此如果您想了解更多信息並喜歡閱讀研究論文，我們將在文本中提供鏈接。

簡介

在本系列文章的第一部分和第二部分中，我們解釋了分佈式數據庫如何使用不同的副本分發負載和/或為不同區域的用戶提供服務。為了總結一下，對於新讀者來說，副本只是數據的副本。此副本可以位於同一位置以實現冗餘，也可以位於另一個位置以向這些位置的用戶提供更低的延遲。擁有可以處理讀寫操作的多個副本具有強大的優勢，因為數據庫變得可擴展並且可以為所有用戶提供更低的延遲，無論他們身在何處。但是，您不希望每個副本對數據都有自己的解釋。您需要對數據的唯一解釋，這通常被稱為單一事實來源，而不是每個副本之間存在細微的數據差異。為了實現這一點，您需要就數據更改達成某種共識。我們需要共識。

等待共識

每個旨在保持一致性的分佈式數據庫都有多個副本，這些副本必須就事務的結果達成一致。如果發生衝突的數據更新，這些副本必須就哪個更新通過以及哪個更新不通過達成一致。這稱為“共識”。

讓我們回到我們的遊戲中來說明為什麼我們需要共識。假設我們的遊戲玩家只剩下3 個金幣，但試圖同時從兩家不同的商店購買兩件不同的物品，總預算超過剩餘的3 個金幣。這涉及兩個事務，每個事務對應一個項目/商店，我們將其表示為t1 和t2。讓我們假設商店的老闆彼此相隔千里，因此交易發生在兩個不同的副本上。如果接受兩個事務，用戶將能夠購買超出其承受能力的物品。我們如何防止用戶超支？

我們知道，這些副本需要進行通信才能就這兩個事務的最終結果達成一致。我們不知道的是他們需要多少通信。為了就哪個事務獲得優先權以及哪個事務被取消達成一致，副本1 和副本2 之間需要來回發送多少消息？

由於分佈式數據庫中的副本旨在以低延遲為世界不同地區的用戶提供服務，因此它們本質上相距甚遠。通過將數據副本放置在更靠近最終用戶的服務器上，這些用戶可以以更低的延遲進行讀取。但是，當發生寫入操作時，副本需要相互發送消息以統一更新所有重複的數據——由於這些消息在全球範圍內傳播時受到光速的限制，因此這些消息可能需要幾十毫秒的時間。很明顯，我們需要盡可能減少跨數據中心消息的數量，這樣最終用戶就不會因為全球各地的這些副本達成共識而等待。

長期以來，人們一直認為這樣做是不可能或不切實際的。但如今，已經存在多種技術可以將往返次數保持在較低水平，並將延遲控制在正常範圍內。

紐約和巴黎之間的距離為5839 公里。光從紐約傳播到巴黎，然後再返回，需要40 毫秒。

— 理論速度與現實世界速度

剩下的最重要的問題是：“我們需要執行多少次事務往返？”這個問題的答案很大程度上取決於所使用的算法。

如何達成一致？

看來，為了就某事達成共識，您至少需要四個躍點（或兩輪通信）：一輪讓每個副本知道您即將執行某些操作，然後第二輪在每個人都同意可以執行此操作後實際執行該操作。這是一種稱為分佈式兩階段提交的方法，幾乎所有分佈式數據庫都使用這種方法。讓我們來看一個比喻。假設您必須與一群人就派對的合適日期達成一致。這可能如下所示：

首先，Polly 詢問每個人是否可以在星期一參加派對；她現在知道每個人實際上都可以來參加派對。接下來，她需要讓每個人都知道派對確實將在星期一舉行，並且人們承認他們會來。

這些與兩階段提交中的兩個階段非常相似。當然，數據庫不會舉辦派對，因此這些階段具有不同的功能。在分佈式系統的情況下，這些階段稱為：

準備或請求提交：確保每個人都知道事務。在此階段，分佈式數據庫中的副本將查詢存儲在磁盤上的某種待辦事項列表（事務日誌）中，以確保服務器宕機時它們仍然知道該做什麼。
提交：實際計算結果並將其存儲

當然，一如既往，事情並非那麼簡單。此類算法有很多變體。例如，有兩階段提交的改進版本，稱為Paxos 和Raft，甚至還有許多這些變體（多Paxos/快速Paxos/…）。這些替代方案旨在解決可用性或性能問題。要了解可用性問題，只需想像一下Polly 生病或Amber 的手機沒電了。在前一種情況下，她將無法繼續擔任派對協調員的工作；而在後一種情況下，Polly 將暫時無法知道Amber 是否同意派對日期。 Raft 和Paxos 通過僅要求大多數人回答和/或在領導者或協調者宕機時自動選擇新的協調者來改進這一點。此處可以找到一個顯示Raft 工作原理的良好動畫。

就什麼達成一致？

我們可以得出結論，每個分佈式數據庫都需要2 次往返來讀寫數據嗎？不，現實比這更複雜。一方面，有很多可能的優化，另一方面，我們可能需要就多件事達成一致。

就事務的時間達成一致
就是否可以執行讀取操作達成一致

最簡單的具有多個兩階段提交輪次的示例可能是Cassandra 的輕量級事務。他們首先需要就讀取達成共識協議，然後就寫入達成共識。如果每條消息需要40 毫秒才能傳播，這意味著整個事務需要320 毫秒或更長時間——這取決於所需的“鎖”，我們將在後面解釋。

這很容易理解，但實現方面存在一些問題，因為Cassandra 從未設計為強一致性。這是否意味著強一致性數據庫甚至更慢？一點也不！現代分佈式數據庫使用多種有趣的特性來實現更好的性能。

等待鎖

我們不僅需要等待消息達成一致，而且幾乎每個分佈式數據庫還將使用“鎖”。鎖保證事務即將更改的數據不會被另一個事務同時更改。當數據被鎖定後，其他事務就無法更改它，這意味著這些事務必須等待。因此，此類鎖的持續時間對性能有很大影響。同樣，這種性能影響取決於數據庫實現的算法和優化。某些數據庫持有的鎖比其他數據庫更長，而某些數據庫根本不使用鎖。

現在我們已經了解了足夠的基礎知識，讓我們深入了解算法。

現代共識算法

我們現在知道，共識和鎖是我們需要優化的主要瓶頸。因此，讓我們回到本文的主要問題：“新技術如何將這些延遲控制在可接受的範圍內？”讓我們從這些現代算法中的第一個開始，它激發了數據庫世界其他領域的一些有趣的想法。

2010 年– Percolator

Percolator 是一個基於BigTable（谷歌構建的早期NoSQL 數據庫之一）的內部系統，谷歌使用它來對搜索索引的頁面抓取速度進行增量更新。關於Percolator 的第一篇論文發表於2010 年，它啟發了第一個受其啟發的分佈式數據庫：2013 年的FoundationDB。然後，FoundationDB 被Apple 收購，最終在2019 年發布了穩定版本，以及FoundationDB 論文。

儘管Percolator 允許谷歌顯著加快頁面抓取速度，但它最初並非作為通用數據庫構建的。它更旨在成為一個快速且可擴展的增量處理引擎，以支持谷歌的搜索索引。由於搜索索引必須可擴展，因此必須在許多機器上同時進行許多計算，這需要一個分佈式數據庫。正如我們在之前的文章中了解到的那樣，針對存儲數據的分佈式系統進行編程可能非常複雜，並且傳統上要求開發人員支付“一致性稅”以應對不可預測的數據庫行為。為了避免支付如此高的一致性稅，谷歌在構建Percolator 時採用了強一致性模型。

Percolator 的一致性模型如果沒有兩個關鍵要素是無法存在的：版本控制和時間戳預言機

要素1：版本控制

正如我們在之前的文章中提到的那樣，強一致性要求我們就事務的全局順序達成一致。版本控制是許多此類算法的關鍵要素之一，因為它可用於故障恢復、幫助複製數據以及支持稱為“快照隔離”的一致性模型。

當節點發生故障或斷開連接時，版本控制有助於故障恢復。當節點重新上線時，由於存在版本，它可以通過從能夠保存的最後一個快照開始，然後根據另一個節點中的版本重播事務來輕鬆恢復其狀態。它所要做的就是詢問另一個節點：“嘿，自從我不在以來發生了什麼變化？”如果沒有版本控制，它將必須複製所有數據，這將給系統帶來巨大的壓力。

故障恢復很棒，但最大的優勢在於此類版本控制系統可用於實現強一致性模型。如果版本控制系統保留每次數據更改的版本，我們實際上可以回到過去並針對我們數據的早期版本執行查詢。

一些聰明的人發現，這種歷史查詢功能可用於提供稱為“快照一致性”的一致性模型。快照一致性的思想是在查詢開始時選擇數據的版本，在查詢的其餘部分使用該版本的數，然後在查詢結束時寫入新版本。

這裡有一個可能的陷阱：在執行此類查詢期間，另一個查詢可能會寫入與第一個查詢衝突的數據。例如，如果兩個寫入查詢都從銀行賬戶的相同快照（賬戶上有1000 美元）開始，它們都可能花費這筆錢，因為它們沒有看到另一個查詢的寫入。為了防止這種情況，將執行一個附加事務以查看在任一查詢寫入結果之前快照的值是否已更改。如果確實發生了導致快照值更改的衝突，則事務將回滾並必須重新啟動。

但是，Percolator 仍然需要解決一個問題。不同機器上的時鐘很容易相差幾百毫秒。如果查詢的數據分佈在多台機器上（如我們最初的示例中），您不能簡單地要求兩台機器都以某個時間戳提供數據，因為它們對當前時間的理解略有不同。這是一個毫秒的問題，但是當必須處理許多事務時，幾毫秒就足以從正確的數據變為錯誤的數據。

時間同步使我們想到了Percolator 的第二個要素。

要素2：時間戳預言機

Percolator 解決時間同步問題的方案稱為時間戳預言機。 Percolator 沒有讓每個節點自己決定時間（這不夠準確），而是使用一個中心系統公開API 來提供時間戳。此系統所在的節點是時間戳預言機。當我們保留數據的多個版本時，每個查詢至少需要兩個時間戳。首先，我們需要一個時間戳來查詢快照，我們將使用它來讀取數據。然後，當我們準備好寫入時，在事務結束時，我們需要第二個時間戳來標記新數據版本。因此，Percolator 的缺點是它至少需要兩次調用時間戳預言機，如果預言機位於與調用源節點不同的區域，則會引入更多延遲。當谷歌提出他們的分佈式數據庫Spanner 時，他們解決了這個問題。

2012 年– Spanner

Spanner 是第一個提供強一致性的全球分佈式數據庫，這基本上意味著您可以獲得低延遲讀取，而無需再擔心潛在的數據庫錯誤。開發人員不再需要額外的工作來規避最終一致性造成的潛在錯誤。該論文發表於2012 年，並於2017 年作為Spanner Cloud 公開發布。

要素1：版本控制

谷歌在使用Percolator 的經驗後構建了Spanner。由於Percolator 的版本控制系統被證明有效，因此他們在Spanner 的設計中保留了這一點。此版本控制系統提供了在您願意放棄一致性的情況下進行非常快速讀取（快照讀取）的能力。在這種情況下，您可以運行查詢並為Spanner 提供結果的最大年齡。例如：“請盡快返回我的當前庫存，但數據只能是15 秒前的”。基本上，您可以為每個查詢選擇適合您用例的一致性級別，而不是放棄一致性。

要素2：TrueTime

為了消除同步機器之間時間的額外開銷，Spanner 放棄了時間戳預言機，轉而採用了一種稱為TrueTime 的新概念。 TrueTime 沒有使用一個中心系統來提供統一的時間視圖，而是試圖減少機器本身的時鐘漂移。谷歌的工程師通過實現基於GPS 和原子鐘的時間同步協議來限製本地時鐘漂移。這種同步算法允許他們將時鐘漂移限制在7 毫秒以內，但這需要由GPS 和原子鐘技術組合而成的特定硬件。

當然，仍然存在7 毫秒的潛在時鐘漂移，這意味著兩台服務器仍然可以將時間戳解釋為兩個不同的快照。這由Spanner 的第三個要素解決：提交等待。

要素3：提交等待

事實上，TrueTime API 不返回一個時間戳，而是返回一個區間n，它確定當前時間戳應該位於該區間內。準備提交後，它只需等待幾毫秒即可應對潛在的漂移，這稱為“提交等待”。這確保了將分配給寫入的時間戳是已在所有節點上通過的時間戳。這也是在商品硬件上運行Spanner 無法提供相同保證的原因，因為等待時間需要幾百毫秒。

2012 年– Calvin

關於Calvin 算法的第一篇論文發表於2012 年，來自耶魯大學的研究。與之前的方案一樣，Calvin 也包含幾個要素。儘管版本控制也是其中一部分，但其餘方法卻大相徑庭，這需要一些額外的要素才能發揮作用：確定性計算和將排序與鎖定分開。這些通常在具有傳統架構的數據庫中找不到的要素。通過更改架構並接受查詢必須是確定性的，Calvin 可以將跨數據中心消息的最壞情況數量減少到兩個。這將全局事務的最壞情況延遲大大降低，並將其降低到200 毫秒以下，或者理論上甚至低於100 毫秒。當然，為了相信這是可能的，您可能首先想知道它是如何工作的，所以讓我們來看一下該算法。

要素1：版本控制

與Percolator 和Spanner 類似，Calvin 也依賴於版本化數據。 Calvin 中的這些快照主要用於確保容錯性。每個節點都存儲不同的快照，這些快照可以被視為檢查點。斷開的節點重新上線後，只需獲取它已見證的最後一個檢查點的時間戳，然後要求另一個節點通知它該檢查點之後的所有事務。

要素2：確定性計算

許多前端開發人員都聽說過Elm 前端框架，它實現了類似於React Redux 的工作流程。 Elm 比類似的基於JavaScript 的框架具有更陡峭的學習曲線，因為它要求您學習一種新語言。但是，由於該語言是函數式的（沒有副作用），因此Elm 允許進行一些令人印象深刻的優化。關鍵在於Elm 中的函數放棄了破壞性操作以成為確定性的。您可以使用相同的輸入兩次運行相同的函數，它將始終產生相同的結果。由於它們是確定性的，因此Elm 查詢現在可以更有效地決定如何更新視圖。

與Elm 類似，Calvin 也放棄了一些東西來加快計算速度。在Calvin 的情況下，我們基本上可以說，事務的結果將相同，無論是在機器A 還是機器B 上執行。這似乎是顯而易見的，但數據庫通常並不保證這一點。請記住，SQL 允許您使用當前時間或允許所謂的交互式事務（其中用戶輸入可以在事務中間插入），這兩者都可能違反Calvin 提供的保證。

為了實現確定性計算，Calvin (1) 需要取出諸如當前時間之類的計算並對其進行預計算，以及(2) 不允許交互式事務。交互式事務是指用戶啟動事務、讀取一些數據、在中間提供一些額外的用戶輸入，然後最終進行一些額外的計算以及一些寫入的事務。由於用戶是不可預測的，因此此類事務不是確定性的。本質上，Calvin 用較小的便利性（交互式事務）換取了出色的性能。

將排序問題分開

數據庫花費大量時間協商鎖，以使其看起來像系統正在以特定順序執行”。如果所有需要的只是順序，也許我們可以將鎖定問題與排序問題分開。但這意味著您的事務必須是純淨的。

— Kyle Kingsbury

將事務排序問題與實際執行分開在數據庫領域中已經被考慮過很多次，但收效甚微。但是，當您的事務是確定性時，將排序與算法的其餘部分分開實際上變得可行。事實上，確定性計算和將排序與算法其餘部分分開的組合非常強大，因為它有助於減少鎖的持續時間並大大減少遠處節點之間的較慢通信（跨數據中心通信）。

更短的鎖持續時間

每當對一部分數據持有鎖時，這意味著使用該數據的其他查詢必須等待。因此，鎖的持續時間越短，性能就越好。下圖顯示了Calvin 中的鎖定過程概述，以及傳統分佈式數據庫可能如何執行此操作。大多數數據庫會在至少就寫入內容達成共識之前一直保持對數據的鎖定，而Calvin 只會在所有節點就順序達成一致之前保持鎖定。由於計算是確定性的，並且它們都就順序達成一致，因此每個節點都將單獨計算並得出相同的最終結果。

減少遠處節點之間的通信

除了鎖持續時間的優勢外，將排序與算法的其餘部分分開也需要更少的通信。正如前面使用Cassandra 示例所解釋的那樣，分佈式數據庫通常在其算法的許多階段都需要跨數據中心通信。在Calvin 的情況下，我們唯一需要就某事達成一致的時刻是確定順序的時刻。使用Raft 協議，這可以在兩個躍點內完成，這使得能夠為讀寫查詢實現低於100 毫秒的延遲。

再加上減少的鎖定時間，這也帶來了極高的吞吐量。最初的Calvin 論文還進行了實驗，表明這種方法在高爭用工作負載下顯著優於傳統的分佈式數據庫設計。他們在商品機器集群上每秒進行50 萬次事務的結果與在高端硬件上獲得的當前世界紀錄結果相競爭。

在任何硬件上運行

除此之外，Calvin 還具有另一個優勢：它不再需要特定硬件才能獲得此類結果。由於Calvin 可以在商品機器上運行，因此它可以在任何云提供商上運行。

2014 年– FaunaDB 的共識風格

要素1：版本控制

FaunaDB 擁有自己的分佈式事務協議，與Calvin 有一些相似之處。與前一種方法一樣，FaunaDB 的數據也是版本化的。由於版本控制不僅對一致性模型有用，而且還具有業務價值，因此FaunaDB 已將其機制升級為一等公民，最終用戶可以使用它。此功能實際上允許進行時間旅行查詢。最終用戶可以在歷史數據上執行查詢以回答以下問題：“20 天前此查詢的結果是什麼？”。這對於恢復意外覆蓋的數據、審核數據更改或只是在應用程序的功能中加入時間旅行很有用。

要素2 和3：確定性計算和分離

與Calvin 一樣，FaunaDB 也具有確定性計算，並將排序問題與算法的其餘部分分開。儘管存在相似之處，但在FaunaDB 中計算事務發生在與Calvin 不同的階段。 Calvin 利用確定性特性在設置順序後多次執行相同的事務，而FaunaDB 則在就事務順序達成共識之前只計算一次。這使我們想到了第四個要素。

要素4：樂觀計算

FaunaDB 添加了第四個要素，我們在討論快照隔離時已經看到過：樂觀計算而不是鎖定。

FaunaDB 不會鎖定，而是會在接收事務的節點中樂觀地計算事務的結果一次，然後將結果和原始輸入值添加到日誌中。 Calvin 會將需要在事務日誌中執行的查詢保存下來，而FaunaDB 會將計算結果和原始輸入值都保存在日誌中。一旦就應用結果的順序達成共識，FaunaDB 將驗證該計算的輸入數據是否已更改（感謝版本控制）。如果輸入值已更改，則事務將中止並重新啟動；如果輸入值保持不變，則結果將在所有節點上應用，無需任何額外計算。

FaunaDB 的算法具有與Calvin 相似的優點，但減少了集群中所需的計算量。

結論

在本系列文章中，我們解釋了強一致性如何幫助您更有效地構建無錯誤的應用程序。在本文的最後一部分，我們進一步解釋了革命性的想法如何為新一代分佈式數據庫提供動力，這些數據庫既一致又高效。在之前的文章中，要點是：“一致性很重要”。在本文的最後，要點包含在以下內容中：

在不久的將來，如果您閱讀到諸如以下短語：

“許多NoSQL 數據庫不提供多個文檔的原子寫入，而反過來提供更好的性能。雖然一致性是SQL 數據庫的另一個強大功能，但它會妨礙跨多個節點擴展數據庫的能力，因此許多NoSQL 數據庫放棄了一致性。”——遷移到NoSQL 的最大挑戰

請意識到，現代算法使數據庫能夠在沒有集中化的情況下提供一致性。在本文中，我們已經看到了一些執行此操作的算法和數據庫示例。基於這些算法構建的數據庫是新一代數據庫，它們不再可以用簡單的類別（如NoSQL、SQL 或甚至NewSQL）來描述。

使用基於Percolator、Spanner、Calvin 和FaunaDB 事務協議的分佈式雲數據庫，您可以擁有提供更強一致性模型的高性能分佈式數據庫。這意味著您可以構建提供低延遲的數據密集型應用程序，而無需擔心數據錯誤、性能或服務配置。在這樣的系統中，一致性是透明的，您無需作為開發人員考慮它。下次選擇數據庫時，請選擇默認情況下保持一致的數據庫。