一致性問題

一致性問題是分佈式領域最基礎也是最重要的問題,也是數十年來的研究熱點。

今天的業務場景越來越複雜,規模越來越大。在面向大規模複雜任務場景時,單點的服務往往難以解決可擴展(Scalability)和容錯(Fault-tolerance)兩方面的需求,就需要多臺服務器來組成集群系統,虛擬為更加強大和穩定的“超級服務器”。

集群的規模越大,處理能力越強,管理的複雜度也就越高。目前在運行的大規模集群包括谷歌公司的搜索系統,通過數十萬臺服務器支持了對整個互聯網內容的搜索服務。

通常情況下,集群系統中的不同節點可能處於不同的狀態,隨時收到不同的請求,要時刻保持對外響應的“一致性”,好比訓練一群鴨子齊步走,難度可想而知。

定義與重要性

定義 一致性(Consistency),早期也叫(Agreement),在分佈式系統領域中是指對於多個服務節點,給定一系列操作,在約定協議的保障下,使得它們對處理結果達成“某種程度”的協同。

理想情況(不考慮節點故障)下,如果各個服務節點嚴格遵循相同的處理協議(即構成相同的狀態機邏輯),則在給定相同的初始狀態和輸入序列時,可以確保處理過程中的每個步驟的執行結果都相同。因此,傳統分佈式系統中討論一致性,往往是指在外部任意發起請求(如向多個節點發送不同請求)的情況下,確保系統內大部分節點實際處理請求序列的一致,即對請求進行全局排序。

那麼,為什麼說一致性問題十分重要呢?

舉個現實生活中的例子,多個售票處同時出售某線路上的火車票,該線路上存在多個經停站,怎麼才能保證在任意區間都不會出現超售(同一個座位賣給兩個人)的情況?

這個問題看起來似乎沒那麼難,現實生活中經常通過分段分站售票的機制。然而,要支持海量的用戶進行並行購票,並非易事(參考 12306 的案例)。特別是計算機系統往往需要達到遠超物理世界的高性能和高可擴展性需求,挑戰會變得更大。這也是為何每年到了促銷季,各大電商平臺都要提前完善系統。

注:一致性關注的是系統呈現的狀態,並不關注結果是否正確;例如,所有節點都對某請求達成否定狀態也是一種一致性。

問題挑戰

計算機固然很快,但在很多地方都比人類世界脆弱的多。典型的,在分佈式系統中,存在不少挑戰:

  • 節點之間只能通過消息來交互和同步,而網絡通訊是不可靠的,可能出現任意消息延遲、亂序和錯誤;

  • 節點處理請求的時間無法保障,處理的結果可能是錯誤的,甚至節點自身隨時可能發生故障;

  • 為了避免衝突,採用同步調用可以簡化設計,但會嚴重降低系統的可擴展性,甚至使其退化為單點系統。

仍以火車票售賣問題為例,願意動腦筋的讀者可能已經想到了一些不錯的解決思路,例如:

  • 要出售任意一張票前,先打電話給其他售票處,確認下當前這張票不衝突。即退化為同步調用來避免衝突;

  • 多個售票處提前約好隔離的售票時間。比如第一家可以在上午 8 點到 9 點期間賣票,接下來一個小時是另外一家……即通過令牌機制來避免衝突;

  • 成立一個第三方的存票機構,票集中存放,每次賣票前找存票機構查詢。此時問題退化為中心化中介機制。

當然,還會有更多方案。

實際上,這些方案背後的思想,都是將可能引發不一致的並行操作進行串行化。這實際上也是現代分佈式系統處理一致性問題的基礎思路。另外,由於通常計算機硬件和軟件的可靠性不足,在工程實現上還要對核心環節加強容錯性。

注:這些思路假設每個售票處的售票機制都能保證正常工作;也沒有考慮請求和答覆消息出現失敗的情況。

一致性的要求

規範來看,分佈式系統達成一致的過程,應該滿足:

  • 可終止性(Termination):一致的結果在有限時間內能完成;

  • 約同性(Agreement):不同節點最終完成決策的結果是相同的;

  • 合法性(Validity):決策的結果必須是某個節點提出的提案。

可終止性很容易理解。有限時間內完成,意味著可以保障提供服務(Liveness)。這是計算機系統可以被正常使用的前提。需要注意,在現實生活中這點並不是總能得到保障的。例如取款機有時候會出現“服務中斷”;撥打電話有時候是“無法連接”的。

約同性看似容易,實際上暗含了一些潛在信息。決策的結果相同,意味著算法要麼不給出結果,任何給出的結果必定是達成了共識的,即安全性(Safety)。挑戰在於算法必須要考慮的是可能會處理任意的情形。凡事一旦推廣到任意情形,往往就不像看起來那麼簡單。例如現在就剩一張某區間(如北京 --> 南京)的車票了,兩個售票處也分別剛通過某種方式確認過這張票的存在。這時,兩家售票處幾乎同時分別來了一個乘客要買這張票,從各自“觀察”看來,自己一方的乘客都是先到的……這種情況下,怎麼能達成對結果的共識呢?看起來很容易,賣給物理時間上率先提交請求的乘客即可。然而,對於兩個來自不同位置的請求來說,要判斷在時間上的“先後”關係並不是那麼容易。兩個車站的時鐘時刻可能是不一致的;時鐘計時可能不精確的……根據相對論的觀點,不同空間位置的時間是不一致的。因此追求絕對時間戳的方案是不可行的,能做的是要對事件的發生進行排序。

事件發生的先後順序十分重要,確定了順序,就沒有了分歧。這也是解決分佈式系統領域很多問題的核心祕訣:把不同時空發生的多個事件進行全局唯一排序,而且這個順序還得是大家都認可的

注:Leslie Lamport 在 1978 年發表的論文《Time, Clocks and the Ordering of Events in a Distributed System》中首次將分佈式系統中順序與相對論進行對比,提出了偏序關係的觀點。

最後的合法性看似繞口,但其實比較容易理解,即達成的結果必須是節點執行操作的結果。仍以賣票為例,如果兩個售票處分別決策某張票出售給張三和李四,那麼最終達成一致的結果要麼是張三,要麼是李四,而不能是其他人。

帶約束的一致性

從前面的分析可以看到,要實現絕對理想的嚴格一致性(Strict Consistency)代價很大。除非系統不發生任何故障,而且所有節點之間的通信無需任何時間,此時整個系統其實就等價於一臺機器了。實際上,越強的一致性要求往往意味著帶來越弱的處理性能,以及越差的可擴展性。根據實際需求的不用,人們可能選擇不同強度的一致性,包括強一致性(Strong Consistency)和弱一致性(Weak Consistency)。

一般地,強一致性主要包括下面兩類:

  • 順序一致性(Sequential Consistency):Leslie Lamport 1979 年經典論文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出,是一種比較強的約束,保證所有進程看到的全局執行順序(total order)一致,並且每個進程看自身的執行順序(local order)跟實際發生順序一致。例如,某進程先執行 A,後執行 B,則實際得到的全局結果中就應該為 A 在 B 前面,而不能反過來。同時所有其它進程在全局上也應該看到這個順序。順序一致性實際上限制了各進程內指令的偏序關係,但不在進程間按照物理時間進行全局排序。

  • 線性一致性(Linearizability Consistency):Maurice P. Herlihy 與 Jeannette M. Wing 在 1990 年經典論文《Linearizability: A Correctness Condition for Concurrent Objects》中共同提出,在順序一致性前提下加強了進程間的操作排序,形成唯一的全局順序(系統等價於是順序執行,所有進程看到的所有操作的序列順序都一致,並且跟實際發生順序一致),是很強的原子性保證。但是比較難實現,目前基本上要麼依賴於全局的時鐘或鎖,要麼通過一些複雜算法實現,性能往往不高。

實現強一致性往往需要準確的計時設備。高精度的石英鐘的漂移率為 10710^{-7},最準確的原子震盪時鐘的漂移率為 101310^{-13}。Google 曾在其分佈式數據庫 Spanner 中採用基於原子時鐘和 GPS 的“TrueTime”方案,能夠將不同數據中心的時間偏差控制在 10ms 以內。在不考慮成本的前提下,這種方案簡單、粗暴,但是有效。

強一致的系統往往比較難實現,而且很多場景下對一致性的需求並沒有那麼強。因此,可以適當放寬對一致性的要求,降低系統實現的難度。例如在一定約束下實現所謂最終一致性(Eventual Consistency),即總會存在一個時刻(而不是立刻),讓系統達到一致的狀態。例如電商購物時將某物品放入購物車,但是可能在最終付款時才提示物品已經售罄了。實際上,大部分的 Web 系統為了保持服務的穩定,實現的都是最終一致性。

相對強一致性,類似最終一致性這樣在某些方面弱化的一致性,被籠統稱為弱一致性。