Spanner:TrueTime 與外部一致性

TrueTime 是可用性高的分散式時鐘,提供所有 Google 伺服器1 上的應用程式使用。TrueTime 讓應用程式可以產生單調遞增的時間戳記:應用程式可計算時間戳記 T,這個時間戳記保證大於任何時間戳記 T',只要完成的 T' 產生的時間早於開始的 T'。此保證適用於所有伺服器和所有時間戳記。

Spanner 會使用 TrueTime 的這項特點,為交易指派時間戳記。特別是每筆交易都會指派一個時間戳記,可反映出 Spanner 認為此交易發生的時間。由於 Spanner 使用多版本並行控制,時間戳記的順序保證讓 Spanner 用戶端得以在整個資料庫 (甚至是跨多個 Cloud 地區) 執行一致的讀取作業,而不會封鎖寫入。

外部一致性

Spanner 提供用戶端最嚴格的交易並行控制保證,稱為外部一致性2。具備外部一致性的系統行為有如所有交易都是依序執行,即使 Spanner 實際上是在多個伺服器 (或可能是多個資料中心) 執行交易以獲得高效能與可用性。此外,若一筆交易在另一筆交易開始修訂前完成,系統保證用戶端不會看到包含第二筆交易效果而未包含第一筆交易效果。直覺上,Spanner 在語意上是無法從單一機器資料庫上區分出來。即使 Spanner 提供如此強力的保證,比起提供較低保證 (以換得較高效能) 的資料庫,仍可讓應用程式獲致效能優勢。舉例來說,與支援快照隔離的資料庫一樣,Spanner 可讓寫入作業繼續執行,不會遭到唯讀交易阻擋,但不會呈現快照隔離允許的異常情況。

外部一致性大幅簡化應用程式的開發。舉例來說,假設您在 Spanner 建立銀行應用程式,您的某個客戶一開始即在其支票和儲蓄帳戶各放入 $50 美元,接著應用程式便展開工作流程。首先確認交易 T1,存入 $200 到儲蓄帳戶。然後發出第二筆交易 T2,從支票帳戶扣款 $150。假設最終某個帳戶若有負項餘額,將從另一個帳戶自動撥款抵銷,若當日任何時間所有帳戶的總餘額是負數,客戶將會因此受罰。外部一致性可保證因為 T2 在 T1 完成後才確認,所以所有資料庫的讀取者都可以看到存款 T1 是在扣款 T2 之前發生。換句話說,外部一致性保證沒有人會看到 T2 在 T1 之前發生;也就是說,這個扣款不會因為資金不足而產生罰金。

使用單一版本儲存空間和嚴格二階段鎖定的傳統資料庫也提供外部一致性。可惜的是,在這樣的系統中,每次應用程式想要讀取最新資料時 (我們稱為「強式讀取」),系統就會取得資料的讀取鎖定,封鎖讀取資料的寫入作業。

時間戳記與多版本並行控制 (MVCC)

為了讀取而不封鎖寫入作業,Spanner 與其他許多資料庫系統會保留資料的多個不可變版本 (通常稱為多版本並行控制)。寫入會建立新的不可變版本,其時間戳記是該寫入交易的時間戳記。某個時間戳記的「快照讀取」會傳回離該時間戳記最近的值,無需封鎖寫入作業。因此重要的是,指派給版本的時間戳記必須與觀察到的交易確認順序一致。我們稱這個屬性為「適當時間戳記」;請注意適當時間戳記的存在便等於外部一致性。

如要瞭解適當時間戳記的重要性,請參考前一節的銀行範例。沒有適當時間戳記,T2 被指派的時間戳記可能會早於指派給 T1 的時間戳記 (例如,若一假設系統採用當地時鐘而非 TrueTime,處理 T2 的伺服器時鐘會稍微延遲)。接著,即使客戶看到存款在扣款開始前完成,快照讀取仍會反映 T2 的扣款而非存款 T1

取得適當時間戳記對於只有單一機器的資料庫而言是小事一樁 (例如,您只需從通用的單調遞增計數器指派時間戳記即可)。但要在廣泛分散的系統如 Spanner 中有效率地取得適當時間戳記就困難的多,因為這些系統遍布全球的伺服器需要指派時間戳記。

Spanner 仰賴 TrueTime 產生單調遞增的時間戳記,並採用兩種方式來運用時間戳記。首先,Cloud Spanner 會使用時間戳記做為適當時間戳記,在無需全域通訊的情況下寫入交易。再者,Cloud Spanner 會使用適當時間戳記做為強式讀取的時間戳記,讓強式讀取在第一輪通訊時執行,即使強式讀取作業橫跨多個伺服器也是如此。

常見問題

Spanner 提供哪些一致性保證?

Spanner 提供外部一致性,這是交易處理系統中最嚴格的一致性屬性。不僅是分區中的交易,Spanner 中的所有交易都滿足此一致性屬性。外部一致性代表 Spanner 執行交易的方式是無法從執行序列交易的系統中區分出來。再者,其序列順序會與觀察到的交易修訂順序一致。由於為交易產生的時間戳記會對應到序列順序,若任何用戶端看到交易 T2 在另一個交易 T1 結束之後開始確認,系統指派給 T2 的時間戳記會比指派給 T1 的時間戳記數字更大 (時間更晚)。

Spanner 是否提供線性一致性?

可以。實際上,Spanner 提供外部一致性,這是比線性一致性更強大的屬性,因為線性一致性並未描述交易行為。線性一致性是並行物件的屬性,支援自動讀取和寫入作業。在資料庫中,「物件」通常是單一資料列或單一儲存格。外部一致性是交易處理系統的屬性,用戶端會動態合成交易,在任意物件上包含多個讀取和寫入作業。線性一致性可以當做是外部一致性的特殊案例,其交易只能包含在單一物件上的單一讀取和寫入作業。

Spanner 是否提供可序列化能力?

可以。實際上,Spanner 提供外部一致性,這是比可序列化更嚴格的屬性。若交易處理系統執行交易的方式,無法從執行序列交易的系統中區分,則此系統即為序列化系統。Spanner 也保證序列順序與觀察到的交易確認順序一致。

請再次回想我們稍早使用的銀行範例。在提供序列化卻無外部一致性的系統中,雖然客戶依序執行 T1 和 T2,系統可能允許重新排序這兩項作業,導致扣款因資金不足而產生罰金。

Spanner 是否提供同步一致性?

可以。事實上,Spanner 提供外部一致性,這項屬性比同步一致性更強。Spanner 中讀取作業的預設模式是「強式」讀取,可保證用戶端看到在作業開始之前確認的所有交易效果,不論是哪個複本接收到這項讀取作業。

同步一致性與外部一致性有什麼不同?

若複製的物件具有線性一致性,複製通訊協定會展現「同步一致性」。與線性一致性相同,「同步一致性」因為沒有任何有關交易行為的敘述,因此不比「外部一致性」強。

Spanner 是否提供最終 (或延遲) 一致性?

Spanner 提供外部一致性,這是比最終一致性更強大的屬性。最終一致性以較低的保證換來較高的效能。最終一致性有其問題存在,因為它代表的是讀取者可以觀察到資料庫未曾真正存在的狀態 (也就是說,即使 A 在 B 之前發生,讀取作業可以觀察到確認 B 交易但未確認 A 交易的狀態)。Spanner 提供過時讀取,提供類似最終一致性的效能優勢,但是具有更強的一致性保證。過時讀取會傳回「舊」的時間戳記資料,但因為舊版資料不可變而無法阻擋寫入作業。

延伸閱讀

附註

  • 1J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang 和 D. Woodford。Spanner:Google 遍及全球的資料庫。美國加州好萊塢第 10 屆 USENIX 作業系統設計和實作研討會 (OSDI 12),頁數 261–264,2012 年 10 月。
  • 2Gifford, D. K. Information Storage in a Decentralized Computer System (分散式電腦系統的資訊儲存)。史丹佛大學博士論文,1981 年。