Spanner 讀取與寫入的生命週期

Spanner 是由 Google 工程師所打造，具有同步一致性、可擴充的分散式資料庫，可支援 Google 最重要的應用程式。它的核心構想來自於資料庫與分散式系統社群，並以新的方式擴展這些構想。Spanner 把這些內部的 Spanner 服務放置在 Google Cloud Platform 供大眾使用。

由於 Spanner 必須處理 Google 重要商務應用軟體嚴苛的運作時間與資源調度需求，我們將 Spanner 從頭打造為廣泛的分散式資料庫，讓服務可擴及多部機器與多個資料中心和地區。我們利用這樣的分散性，處理大型資料集和大型工作負載的同時，仍能維持非常高的可用性。為了讓開發人員有絕佳的體驗，我們也預期要讓 Spanner 提供與其他企業級資料庫同樣嚴格的一致性保證。為支援同步一致性的資料庫撰寫軟體，比僅支援資料列等級一致性、實體等級一致性或完全無一致性保證的資料庫來得容易，也更為合理。

在此文件中，我們會詳述在 Spanner 中寫入與讀取的作業方式，以及 Spanner 如何確保同步一致性。

起點

有些資料集過大而不適合於單一機器上使用。也有一些情境是，資料集不大，但工作負載太重以至於單一機器無法處理。這表示我們需要找方法來將資料分割成片段，然後儲存在多部機器中。我們的方法是將資料庫資料表分區，成為連續的索引鍵範圍，稱為分割。單一機器可處理多個分割，也提供快速的查詢服務，可判別為某個索引鍵範圍提供服務的機器。Spanner 使用者可以看到資料如何分割，以及資料所儲存的機器的詳細資料。結果就是一個可以提供低延遲的讀取與寫入的系統，即使以非常大的規模、在沉重的工作負載下執行讀寫作業亦是如此。

我們也想確保在作業失敗的情況下，使用者仍可存取資料。為了達成這個目標，我們會將每個分割複製到不同故障網域中的多部機器。這樣一致地複製到分割的各個副本的作業是由 Paxos 演算法管理。在 Paxos 中作業時，只要分割的投票備用資源大部分都可使用，其中一個備用資源就可以被選為領導者來處理寫入作業，而允許其他備用資源處理讀取作業。

Spanner 提供唯讀交易和讀寫交易。對於不會修改資料的作業 (包含 SQL SELECT 陳述式) 而言，比較偏好使用唯獨交易類型。唯讀交易仍可提供同步一致性，根據預設在資料的最新複本上執行。但此類型交易可以在不需任何內部鎖定的情況下執行，使得執行速度更快，並能提升可擴充性。讀寫交易是用於插入、更新或刪除資料的交易，包含依序執行讀取和寫入作業的交易。雖然讀寫交易也是高度可擴充，但讀寫交易會使用鎖定，而必須由 Paxos 領導者進行協調。請注意，Spanner 用戶端可以看到鎖定狀態。

許多前代的分散式資料庫系統選擇不提供同步一致性保證，因為通常需要進行十分昂貴的跨機器通訊。Spanner 利用 Google 開發的技術 TrueTime，在整個資料庫提供同步一致性快照。就像是 1985 年左右的時光機中的通量電容器，TrueTime 正是讓 Spanner 得以實現的主因。它是一個 API，可讓 Google 資料中心中的任何機器以高精準度 (也就是在幾毫秒間) 得知確切的全球時間。這讓不同的 Spanner 機器理解交易作業的順序 (並讓順序符合用戶端觀察到的結果)，而且通常不需要任何通訊。Google 必須為其資料中心配備特殊的硬體 (像是原子鐘！)，才能讓 TrueTime 運作。產生的時間準確性比其他通訊協定 (如 NTP) 高出許多。特別是 Spanner 也指派時間戳記給所有讀取和寫入作業。在時間戳記 T1 進行的交易保證會反映所有在 T1 之前發生的寫入作業。如果某台機器需要在 T2 滿足一項讀取作業，就必須確認該機器看到的資料至少要更新到 T2。由於有 TrueTime，此判斷的費用通常不高。確保資料一致性的通訊協定雖然複雜，不過在原始的 Spanner 論文和這個有關 Spanner 與一致性的文件中，都有更詳細的討論。

實際範例

讓我們實際操作一些範例，瞭解 Spanner 如何運作：

CREATE TABLE ExampleTable (
 Id INT64 NOT NULL,
 Value STRING(MAX),
) PRIMARY KEY(Id);

在此範例中，我們有一個包含簡單整數主鍵的資料表。

Split KeyRange
0 [-∞,3)
1 [3,224)
2 [224,712)
3 [712,717)
4 [717,1265)
5 [1265,1724)
6 [1724,1997)
7 [1997,2456)
8 [2456,∞)

在上述 ExampleTable 的結構定義下，主鍵空間會分區為多個分割。例如，若 ExampleTable 中有一個資料列的 Id 是 3700，該資料列便會位於分割 8 之中。如上方詳細說明所述，分割 8 會複製到許多機器。

說明「跨多個區域與機器分佈的分割」表格

在這個範例的 Spanner 執行個體中，客戶有五個節點，而執行個體會複製到三個區域，具有編號 0-8 的九個分割，每個分割的 Paxos 領導者會以深色標示。這些分割在每個區域也有備用資源 (淺色)。在每個區域中，分割在節點間的分佈可能會有所不同，而 Paxos 領導者也不會全都位於相同區域中。這樣的彈性讓 Spanner 對於特定負載設定檔類型和故障模式而言更為完善。

單一分割寫入

假設用戶端想要在 ExampleTable 中插入新資料列 (7, "Seven")。

  1. API 層查詢擁有包含 7 的索引鍵範圍的分割。索引鍵範圍存在於分割 1。
  2. API 層會傳送寫入請求到分割 1 的領導者。
  3. 領導者會開始交易。
  4. 領導者會嘗試取得資料列 Id=7 的寫入鎖定，此為本機作業。若另一個並行的讀寫交易正在讀取這一列，則另一個交易就會有讀取鎖定，而目前的交易會遭到封鎖，直到它能取得寫入鎖定為止。
    1. 可能的狀況是，交易 A 等待交易 B 持有的鎖定，而交易 B 等待交易 A 持有的鎖定。由於兩個交易在取得所有鎖定之前，都不會解除任何鎖定，這會造成鎖死。Spanner 採用標準的「受傷等待」預防鎖死演算法，確保交易得以進行。特別是，時間較短的交易會等待時間較長的交易所持有的鎖定狀態，但時間較長的交易會「損害」(取消) 時間較長的交易要求的、由時間較短的交易所持有的鎖定。因此，我們絕不會有鎖定等待者的鎖死循環。
  5. 取得鎖定後，領導者會依據 TrueTime 指派交易的時間戳記。
    1. 此時間戳記保證會晚於任何觸及資料的修訂交易的時間。如此可確保交易的順序 (從用戶端的觀點來看) 符合資料變更的順序。
  6. 領導者會告知分割 1 備用資源有關交易和時間戳記的資訊。當大多數的備用資源都將交易變異儲存在 (分散式檔案系統中) 穩定的儲存空間後，交易便會修訂。如此可確保即使少數機器故障，仍可復原交易。(這些備用資源尚未將變異套用到備用資源的資料複本)。

  7. 領導者會等到交易的時間戳記確實在實際時間過去；這通常需要幾毫秒的時間，讓我們確定 TrueTime 時間戳記中是否有不確定因素。這就是確保同步一致性的機制：一旦用戶端得知交易的結果，系統便會保證其他讀取者都能看見交易的效果。此「修訂等待」通常會與上述步驟中的備用資源通訊重疊，所以實際的延遲成本很低。如需更多詳細資料，請參閱此文件。

  8. 領導者回應用戶端，表示交易已修訂，或者回報交易的修訂時間戳記。

  9. 在回應用戶端的同時，系統也會將交易變異套用到資料。

    1. 領導者會套用變異到資料的複本，然後解除交易鎖定。
    2. 領導者也會通知分割 1 的其他備用資源，將變異套用到資料複本。
    3. 任何應看見變異效果的讀寫或唯讀交易都會等到套用變異後再嘗試讀取資料。針對讀寫交易，由於交易必須實施讀取鎖定，此步驟將強制執行。對於唯讀交易而言，這會藉由比對讀取作業的時間戳記和最近一次套用資料的時間戳記來強制執行。

以上所有作業通常會在幾毫秒內發生。這樣的寫入作業 Spanner 所執行最便宜的寫入作業，因為只涉及單一分割。

多重分割寫入

若涉及多重分割，將需要額外的協調層 (使用標準的二階段修訂演算法)。

以包含四千個資料列的資料表為例：

1 「一」
2 「二」
... ...
4000 「四千」

假設客戶想要在一個交易中讀取資料列 1000 的值，以及將值寫入資料列 2000、3000 和 4000。系統會在讀寫交易中執行下列動作：

  1. 用戶端開始讀寫交易「t」。
  2. 用戶端對 API 層發出讀取資料列 1000 的請求，並將資料列 1000 標記為「t」的一部分。
  3. API 層尋找擁有索引鍵 1000 的分割。此索引鍵存在於分割 4。

  4. API 層傳送讀取請求至分割 4 的領導者，並將分割 4 的領導者標記為「t」的一部分。

  5. 分割 4 的領導者會嘗試取得資料列 Id=1000 的讀取鎖定，此為本機作業。若其他並行交易也在此資料列上有寫入鎖定，系統將封鎖目前交易直到取得鎖定為止。不過，此讀取鎖定不會防止其他交易取得讀取鎖定。

    1. 如同在單一分割的案例，系統會透過「受傷等待」來避免鎖死。

  6. 領導者查詢 Id 1000 的值 (也就是「一千」) 並將讀取結果傳回用戶端。


    稍後...

  7. 用戶端針對交易 t 發出「修訂」請求。此修訂請求包含 3 個變異：([2000, "Dos Mil"]、[3000, "Tres Mil"] 和 [4000, "Quatro Mil"])。

    1. 與交易相關的所有分割變成交易的參與者。在此案例中，參與者是分割 4 (處理索引鍵 1000 的讀取)、分割 7 (處理索引鍵 2000 的變異) 和分割 8 (處理索引鍵 3000 和索引鍵 4000 的變異)。

  8. 一名參與者變成協調者。在這個案例中，分割 7 的領導者變成協調者。協調者的工作是確認所有參與者的交易皆以不可分割的形式修訂或取消。也就是說，系統不會只修訂一位參與者，而取消另一個參與者。

    1. 由參與者和協調者進行的作業實際上是由這些分割的領導者機器進行。

  9. 參與者取得鎖定 (此為二階段修訂的第一階段)。

    1. 分割 7 取得索引鍵 2000 的寫入鎖定。
    2. 分割 8 取得索引鍵 3000 和索引鍵 4000 的寫入鎖定。
    3. 分割 4 確認自己仍持有索引鍵 1000 的讀取鎖定 (換句話說，鎖定不會因為機器當機或受傷等待演算法而遺失)。
    4. 每個參與者分割會將自己的鎖定集合複製到 (至少) 大多數的分割備用資源，以記錄鎖定集合，確保跨伺服器故障時仍保有鎖定。
    5. 若所有參與者成功通知協調者他們持有鎖定，則可修訂整體交易。如此可確保在某個時點，系統持有交易所需的所有鎖定，而這個時點就成為交易的修訂點，確保我們可以正確地將此交易與之前之後的交易效果進行排序。
    6. 系統也有可能無法取得鎖定 (例如，若我們瞭解使用受傷等待演算法可能會有鎖死的情況)。如果有任何參與者表示無法修訂交易，整筆交易便會取消。

  10. 若所有參與者和協調者都成功取得鎖定，協調者 (分割 7) 將決定修訂交易。它會依據 TrueTime 指定交易的時間戳記。

    1. 此修訂決策和索引鍵 2000 的變異會複製到分割 7 的成員。一旦分割 7 的大多數備用資源將修訂決策記錄到穩定的儲存空間，系統便會修訂交易。

  11. 協調者會將交易的結果傳送到所有參與者 (此為二階段修訂的第二階段)。

    1. 每個參與者領導者都會將修訂決策複製到參與者分割的備用資源。

  12. 如果系統修訂交易，協調者和所有參與者都會將變異套用到資料。

    1. 如同在單一分割的情況下，協調者或參與者的後續資料讀取者必須等待資料套用完成。

  13. 協調者領導者回應用戶端，表示交易已修訂，或者傳回交易的修訂時間戳記。

    1. 如同在單一分割的情況，在修訂等待後會將結果傳送到用戶端，以確保同步一致性。

所有作業通常在幾毫秒內發生，雖然在單一分割案例中，因為有額外的交叉分割協調，這個時間會再長一點。

強式讀取 (多重分割)

假設用戶端想要讀取 Id >= 0 和 Id < 700 的所有資料列做為唯讀交易的一部分。

  1. API 層會尋找在範圍 [0, 700) 中擁有任何索引鍵的分割。分割 0、分割 1 和分割 2 擁有這些資料列。
  2. 由於是跨多部機器的強式讀取，API 層會使用目前的 TrueTime 挑選讀取的時間戳記。這可確保兩個讀取作業都傳回相同資料庫快照的資料。
    1. 其他類型的讀取，例如過時讀取，也會挑選讀取的時間戳記 (但時間戳記可能在過去的時間)。
  3. API 層會傳送讀取請求至分割 0、分割 1 和分割 2 的部分複本，也會加入在上述步驟選取的讀取時間戳記。

  4. 對於強式讀取作業，服務備用資源通常會向領導者發出 RPC，要求需要套用的最後一筆交易的時間戳記，而讀取作業可在套用該交易後繼續進行。如果備用資源是領導者，或是它判斷自己的進度足以處理內部狀態和 TrueTime 的要求，就會直接提供讀取作業。

  5. 系統可整合備用資源的結果並 (透過 API 層) 傳回用戶端。

請注意在唯讀交易中，讀取不會獲得任何鎖定。而且讀取可由特定分割的任何最新的備用資源來執行，因此系統的讀取總處理量可能非常高。若用戶端可容忍讀取有至少 10 秒的延遲，讀取的總處理量可以更高。由於領導者通常會在每 10 秒使用最新的安全時間戳記更新備用資源，擁有過時時間戳記的讀取可避免向領導者額外傳送 RPC。

結論

傳統上，分散式資料庫系統的設計人員發現強大交易保證十分昂貴，因為所有交易都需要跨機器的通訊。有了 Spanner，我們一直著眼於降低交易的成本，讓交易可以不管分散的程度，大規模執行。實現這項目標的關鍵因素是 TrueTime，它可為多種協調方式減少跨機器的通訊作業。除此之外，謹慎的工程與效能微調也成就了這個在提供強大保證的情況下仍有高效能的系統。我們在 Google 發現，這個方法使得在 Spanner 開發程式，比在其他只有較低保證的資料庫系統中來得容易許多。應用程式開發人員若無需擔心資料有競爭狀況或不一致，便可專注在他們真正在意的事情上，也就是建構和發布出色的應用程式。