748
淺析分布式係統中的 Linearizability
在分布式係統裏，出於可靠性（reliability）或者性能的考慮，數據通常會被複製為多個副本。因此，係統需要定義一組協議，來規定用戶讀寫多副本時的行為。這組協議稱之為 consistency model。
最終一致性（eventually consistency），linearizability（atomic consistency）是不同類型的一致性模型。下圖是最終一致性模型的示例，用戶 B/C 在讀取不同的副本時看到了不同的 x 的值。請注意，用戶A，B，C的操作是完全串行執行的，即操作在時間軸上沒有重疊。C 讀取操作發生在 B 之後，卻讀到了過期的值。可見，最終一致性是一個較弱的一致性模型，用戶需要自己解決讀取到過期數據的問題。
接下來，讓我們看看一個中間狀態的一致性模型，它比最終一致性強，但是比 linearizability 弱。從時間軸上可以看到，B0 發生在 A0 之前，讀取到的 x 值為0。B2 發生在 A0 之後，讀取到的 x 值為1。而讀操作 B1，C0，C1 與寫操作 A0 在時間軸上有重疊，因此他們可能讀取到舊的值0，也可能讀取到新的值1。注意，C1 發生在 B1 之後（二者在時間軸上沒有重疊），但是 B1 看到 x 的新值，C1 反而看到的是舊值。即對用戶來說，x 的值發生了回跳。
Linearizability，則提供了更強的一致性保證。注意下圖中的 C1 和 B1 操作，C1 發生在 B1 之後，但是與 A0 並行。在 Linearizable 係統中，如果 B1 看到的 x 值為1，則 C1 看到的值也一定為1。而在前兩種一致性模型中，同樣的場景，C1 看到的 x 值既可能是0，也可能是1。在 Linearizable 的係統中，任何操作在該係統生效的時刻都對應時間軸上的一個點。如果我們把這些時刻連接起來，如下圖中紫線所示，則這條線會一直沿時間軸向前，不會反向回跳。所以，在 Linearizable 係統中，**任何操作**都可以互相比較決定誰發生在前，誰發生在後。例如 B1 發生在 A0 前，C1 發生在 A0 後。而在前麵較弱的一致性模型中，我們無法比較諸如 B1 和 A0 的先後關係。對這個性質更正式的表述是：在 Linearizable 係統中，我們可以獲得操作的全序（total order）。而在提供較弱一致性的係統中，我們隻能獲得操作的偏序（partial order）。
注意：
由於網絡延時以及係統本身執行請求的不確定性，請求發起得早不意味著在服務端被執行得早。例如 A0 比 B1 在客戶端發起得早，但 A0 在存儲係統生效晚於 B1。反之，在服務端被執行得早的請求也有可能很晚客戶端才收到結果，例如 C0。
需要 Linearizability 語義的一個典型場景是實現分布式鎖。例如當一個鎖被 client A獲取後，則希望後續看到該鎖的狀態都是被A locked，而不是其他狀態。
附錄
A. Linearizability 與 Serializability 的差別
關於二者的差別，可以參考這一篇文章。
最後更新：2017-06-11 14:33:03