StateSynchronizer 是開源分佈式流存儲平臺 Pravega 的核心組件。StateSynchronizer 組件以 stream 為基礎，對外提供一致性狀態共享服務。StateSynchronizer 允許一組進程同時讀寫同一共享狀態而不必擔心一致性問題。本文將從共享狀態和一致性的角度出發，詳細描述 StateSynchronizer 的整體架構、工作機制和實現細節。利用 stream 的天然特性，StateSynchronizer 可以高效地確定出更新操作的全局順序，並且從邏輯上實現了對共享狀態的一致性更新與存儲。由於 stream 訪問的高效與輕量，StateSynchronizer 特別適用於高併發 (>= 10000 clients) 的場景，並在此場景下可以作為替代 ZooKeeper 和 etcd 的解決方案。
StateSynchronizer 設計者之一 Flavio 是著名開源組件 ZooKeeper 的最早作者，他同時也是《ZooKeeper：分佈式過程協同技術詳解》這本書的作者。
StateSynchronizer 不僅是 Pravega 公共 API 的一部分，許多 Pravega 內部組件也大量依賴 StateSynchronizer 共享狀態，如 ReaderGroup 的元信息管理。並且我們可以基於 StateSynchronizer 實現更高級的一致性原語，例如跨 stream 的事務。
開源項目地址：https://github.com/pravega/pravega/tree/v0.4.0
1 背景簡介
1.1 什麼是 StateSynchronizer（狀態同步器）
Pravega [1] 既可以被想象成是一組流存儲相關的原語，因為它是實現數據持久化的一種方式，Pravega 也可以被想象成是一個消息訂閱 - 發佈系統，因為通過使用 reader，writer 和 ReaderGroup 它可以自適應地進行消息傳遞。本文假設讀者已經熟悉 Pravega 的有關概念，否則可以參考相應的官方文檔 [2] 和已發佈的 4 篇專欄文章（見文末鏈接）。
Pravega 實現了各種不同的構建模塊用以實現 stream 相關原語，StateSynchronizer [2] 就是其中之一，目的在於協調分佈式的環境中的各個進程^2。從功能上看，StateSynchronizer 為一組進程提供可靠的共享的狀態存儲服務：允許多個客戶端同時讀取和更新同一共享狀態並保證一致性語義，同時提供數據的冗餘和容錯。從實現上看，StateSynchronizer 使用一個 stream 為集群中運行的多個進程提供了共享狀態的同步機制，這使得構建分佈式應用變得更加簡單。使用 StateSynchronizer，多個進程可以同時對同一個共享狀態進行讀取和修改，而不必擔心一致性問題 [3]。
StateSynchronizer 的最大貢獻在於它提供了一種 stream 原生的一致性存儲方案。由於 stream 具有隻允許追加（Append-Only）的特性，這使得大部分現有的存儲服務都無法很好地應用於 stream 存儲的場景。相比於傳統的狀態存儲方案，stream 原生的存儲使得 StateSynchronizer 具有以下優點：
- 與常見的鍵值存儲（Key/Value Store）不同，StateSynchronizer 支持任意抽象的共享狀態，而不僅僅侷限於維護鍵值集合。
- 與常見的數據存儲不同，StateSynchronizer 以增量的方式維護了共享狀態的整個變更歷史，而不僅僅是維護共享狀態的最新快照。這一特性不僅大大減少了網絡傳輸開銷，還使得客戶端可以隨時將共享狀態回滾到任意歷史時刻。
- 與常見的狀態存儲不同，StateSynchronizer 的服務端既不存儲共享狀態本身也不負責對共享狀態進行修改，所有共享狀態的存儲和計算都只發生在客戶端本地。這一特性不僅節約了服務端的計算資源，還增加了狀態計算的靈活性，例如：除了基本的 CAS（Compare-And-Swap）語義，還支持高隔離級別的複雜事務^3。
- 與現有的基於樂觀併發控制（Optimistic Concurrent Control, OCC） [4] [5] 的存儲系統不同，StateSynchronizer 可以不依賴多版本控制機制（Multi Version Concurrent Control, MVCC） [6] [7]。這意味著即使在極端高併發的場景下，狀態更新的提交也永遠不會因版本衝突而需要反覆重試。
StateSynchronizer 無意於也不可能在所有場景中替代傳統的分佈式鍵值存儲組件，因為它的運行機制大量依賴 stream 的特性。但是，在具有 stream 原生存儲和較強一致性需求的場景下，StateSynchronizer 可能是一種比其它傳統鍵值存儲服務更為高效的選擇。
1.2 “一致性”的不同語義
在不同的上下文環境中，“一致性”一詞往往有著不同的語義 [8] [9]。在分佈式存儲和數據高可用（High Availability）相關的語境下，一致性通常指數據副本（Replica）的一致性 [8]：如何保證分佈在不同機器上的數據副本內容不存在衝突，以及如何讓客戶端看起來就像在以原子的方式操作唯一的數據副本，即線性化（Linearizability） [10]。常見的分佈式存儲組件往往依賴單一的 Leader（主節點）確定出特定操作的全局順序，例如：ZooKeeper [11] 和 etcd [12] 都要求所有的寫操作必須由 Leader 轉發給其它數據副本。數據副本的一致性是分佈式系統的難點，但卻並不是一致性問題的全部。
脫離數據副本，在應用層的語境下，一致性通常指數據滿足某種約束條件的不變性（Invariant）[13]，即：指的是從應用程序特定的視角出發，保證多個進程無論以怎樣的順序對共享狀態進行修改，共享狀態始終處於一種“正確的狀態”，而這種正確性是由應用程序或業務自身定義的。例如，對於一個交易系統而言，無論同時有多少個交易在進行，所有賬戶的收入與支出總和始終都應該是平衡的；又如，多進程操作（讀 / 寫）一個共享的計數器時，無論各進程以怎樣的順序讀寫計數器，計數器的終值應該始終與所有進程順序依次讀寫計數器所得到的值相同。參考文獻 [8] 將這種一致性歸類為“事務性的一致性（Transactional Consistency）”，而參考文獻 [9] 則將此類一致性簡單稱為“涉及多對象和多操作的一致性”。應用層的數據一致性語義與數據副本的一致性語義完全不同，即使是一個滿足線性化的分佈式系統，也需要考慮應用層的數據一致性問題^4。
1.3StateSynchronizer 與現有的一致性存儲產品
目前常用的分佈式鍵值存儲服務，例如 ZooKeeper 和 etcd，都可以看作是一種對共享狀態進行存儲和維護的組件，即所有鍵值所組成的集合構成了當前的共享狀態。在數據副本層面，ZooKeeper 和 etcd 都依賴共識（Consensus）算法提供一致性保證。ZooKeeper 使用 ZAB（ZooKeeper’s Atomic Broadcast）協議 [14] 在各節點間對寫操作的提交順序達成共識。在廣播階段，ZAB 協議的行為非常類似傳統的兩階段提交協議。etcd 則使用 Raft 協議 [15] 在所有節點上確定出唯一的寫操作序列。與 ZAB 協議不同，Raft 協議每次可以確認出一段一致的提交序列，並且所有的提交動作都是隱式的。在應用層數據層面，ZooKeeper 和 etcd 都使用基於多版本控制機制的樂觀併發控制提供最基礎的一致性保證。一方面，雖然多版本控制機制提供了基本的 CAS 語義，但是在極端的高併發場景下仍因競爭而存在性能問題。另一方面，僅僅依靠多版本控制機制無法提供更加複雜的一致性語義，例如事務。儘管在數據副本層面，ZooKeeper 和 etcd 都提供很強的一致性語義，但對於應用層面的數據一致性卻還有很大的提升空間：ZooKeeper 無法以原子的方式執行一組相關操作，而 etcd 的事務僅支持有限的簡單操作（簡單邏輯判斷，簡單狀態獲取，但不允許對同一個鍵進行多次寫操作）。
在應用層數據層面，ZooKeeper 和 etcd 都使用多版本控制機制提供最基礎的一致性保證。例如，ZooKeeper 的所有寫操作都支持樂觀併發控制：只有當目標節點的當前版本與期望版本相同時，寫操作才允許成功；而 etcd 則更進一步，還支持非常有限的簡單事務操作。一方面，雖然多版本控制機制提供了基本的 CAS 語義，但是在極端的高併發場景下仍因競爭而存在性能問題。另一方面，僅僅依靠多版本控制機制無法提供更加複雜的一致性語義，例如事務。儘管在數據副本層面，ZooKeeper 和 etcd 都提供很強的一致性語義，但對於應用層面的數據一致性卻還有很大的提升空間：ZooKeeper 無法以原子的方式執行一組相關操作，尤其是同時操縱多個鍵；而 etcd 的事務僅支持非常有限的簡單操作（簡單邏輯判斷，簡單狀態獲取，但不允許對同一個鍵進行多次寫操作）。為應用層數據提供比現有的分佈式存儲組件更強的一致性語義（複雜事務）和更高的併發度是 StateSynchronizer 的主要目標，尤其是在 stream 原生場景下，因為傳統的以隨機訪問為主的存儲組件很難適配 stream 存儲的順序特性。得益於 stream 的自身特性，StateSynchronizer 可以不依賴樂觀併發控制和 CAS 語義，這意味著不會出現版本衝突也無需重試，從而更加適用於高併發的場景（2.2.4 小節）。在“無條件寫”模式下，StateSynchronizer 的理論更新提交速度等價於 stream 的寫入速度。
與現有的絕大多數存儲服務不同，StateSynchronizer 反轉了傳統的數據存儲模型（2.2.3 小節）：它並不存儲共享狀態本身，轉而存儲所有作用在共享狀態上的更新操作。一方面，這一反轉的數據模型直接抽象出了共享狀態，使得共享狀態不再侷限於簡單的鍵值存儲，而可以推廣到任意需要一致性語義的狀態。另一方面，反轉數據存儲的同時還不可避免地反轉了數據相關的操作，使得原本大量的服務端狀態計算可以直接在客戶端本地完成（2.2.1 小節）。這一特性不僅大大降低了服務端的資源消耗，同時也使得 StateSynchronizer 可以提供更靈活的更新操作和更強一致性語義：複雜事務。在 StateSynchronizer 的框架中，客戶端提交的所有更新操作都是以原子的方式順序執行的，並且所有更新操作的執行都發生在本地。從邏輯上看，每一個更新操作都等價於一個本地事務操作。這也意味著客戶端可以在更新操作中使用複雜的業務邏輯（幾乎是不受限的操作，只要操作本身的作用是確定性的）而無需擔心一致性問題。
2 實現細節
2.1StateSynchronizer 的本質
從整體架構上看，StateSynchronizer 是一個很典型的客戶端 / 服務器結構（如圖 1 所示）：它包括一個以庫的形式（當前版本僅支持 Java）嵌入在應用中的客戶端，以及服務器端的一個對應 stream。從概念上看，StateSynchronizer 服務端負責以 stream 的形式“存儲”共享狀態。嚴格說來，stream 存儲的是更新操作而不是共享狀態本身。2.2.3 小節將對此進行更加深入的討論。
StateSynchronizer 客戶端是一個輕量級的組件，它與所有其它的 stream 客戶端（例如 reader 和 writer）並沒有本質上的不同：StateSynchronizer 客戶端使用標準的 stream API 與服務器端的 stream 交互，並且服務器端也並不存在任何特定於 StateSynchronizer 的特性或實現。也就是說，StateSynchronizer 客戶端具有其它 stream 客戶端共同的優點，高效。所有 StateSynchronizer 特定的行為都是在客戶端實現的，服務器端僅僅用於提供 stream 形式的存儲媒介。StateSynchronizer 的客戶端還非常精巧，核心部分的實現不過數百行代碼 [16]。
2.2StateSynchronizer 的工作機制
2.2.1維護本地共享狀態
從概念上說，每一個 StateSynchronizer 都對應一個共享狀態：所有的客戶端都可以併發地對這個共享狀態進行讀寫操作，並且保持一致性。這個共享狀態既可以很簡單（例如，它可以是一個基本的數值變量），也可以很複雜（例如，它也可以是一個任意複雜的數據結構）。但是，如果從物理實現角度上看，根本不存在這樣一個可以被共享訪問的狀態：每一個 StateSynchronizer 的客戶端都只在各自的本地維護著一個“共享”狀態的副本（Copy），除此以外沒有任何地方存儲這個狀態。所有的讀和寫（更新）操作都是直接作用在這個本地共享狀態副本上：讀操作直接返回本地共享狀態副本，而更新操作作用於本地共享狀態並生成新的共享狀態。
為了達到順序一致性 [8]，所有共享狀態必須滿足全序（Total Order）關係 [17]。如果用符號“≺”表示二元 happens-before 語義 [18]，則任意 N 個狀態必須能夠確定出唯一全局順序，如下：
(1)
注意，happens-before 關係必須滿足傳遞性，反自反性和反對稱性 [19]。
如果讀者閱讀過StateSynchronizer接口 [20] 的實現類StateSynchronizerImpl，就會發現它有一個名為currentState的StateT類型的成員，並且StateT類型實現了Revisioned接口。這就是 StateSynchronizer 所維護的本地共享狀態副本。Revisioned接口僅有兩個成員方法：getScopedStreamName()用於獲取該狀態對應的 stream 的名字，getRevison()方法用於獲取該狀態對應的 Revision（一個抽象的版本概念，也可以近似等價為 Kafka 的 offset）。而Revision接口最終繼承了Comparable接口，允許任意兩個 Revision 進行比較，用於保證共享狀態的全序關係。感興趣的讀者可以繼續閱讀Revision接口的標準實現類RevisionImpl的compareTo()方法，就會發現 Revision 的比較實際上是基於 Segment 偏移量進行的。由於 StateSynchronizer 的底層 stream 僅包含一個 segment，基於該 segment 的偏移量天然就是一個全序關係的良定義（well-defined）。
2.2.2更新操作的抽象模型
StateSynchronizer 上的更新操作的實現是遞歸式的，也可以說是生成式的。StateSynchronizer 的客戶端接受一個更新操作 un ，將其成功持久化後（細節將在下文討論）應用於當前的本地共享狀態副本 sn，從而生成新狀態 sn+1 ，如下：
sn+1 = un(sn) (2)
從純數學的角度看，這是一個很典型的一階馬爾科夫模型 / 鏈（Markov Model） [21]：如果把n看作是離散的時間，那麼 sn就構成了系統狀態隨時間遷移（Transition）的一個有序序列，並且該系統在任意時間點的狀態 sn+1只依賴前一時刻的狀態 sn ，並由當前更新 un 確定，而與任何其它狀態無關。也可以這麼理解，我們假設了狀態 sn已經包含了所有之前時刻的狀態信息。這就是所謂的馬爾科夫假設。為了啟動狀態遷移，我們規定系統必須具有一個起始狀態 s0 ，而更新操作引起了隨後的狀態遷移。
如果從集群的視角看，有多個 StateSynchronizer 客戶端獨立同時運行並接受更新操作，而每個客戶端本地的共享狀態則分別經歷著基於馬爾科夫模型的狀態遷移。為保證每個 StateSynchronizer 客戶端的本地共享狀態都能夠收斂於相同的最終狀態，首先要求狀態遷移是確定性的（deterministic），也就是說，更新操作 un 本身必須是確定性的（我們將在 2.3.1 小節深入討論更新操作與確定性問題）。從這個角度看，上述馬爾可夫鏈其實已經退化成一個普通狀態機。其次，所有的 StateSynchronizer 客戶端必須具有相同的起始狀態 s0，並且以相同的順序應用更新 un。整個集群的這種行為模式非常類似經典的複製狀態機（Replicated State Machine）模型 [22]。複製狀態機模型是一個應用廣泛的分佈式模型，許多常見的全序廣播 / 原子廣播協議都是基於該模型進行的，如 ZAB 協議和 Raft 協議等。我們有意忽略了著名的 Paxos 協議 [23] [24]，因為原生的 Paxos 協議並非用於解決全序廣播問題，儘管共識算法與全序廣播之間確實被證明存在等價關係 [25]。複製狀態機模型可以簡單描述如下：
- 在各自獨立的服務器節點上放置同一狀態機的實例；
- 接受客戶端請求，並轉譯成狀態機的輸入；
- 確定輸入的順序；
- 按已確定的順序在各個狀態機實例上執行輸入；
- 用狀態機的輸出回覆客戶端；
- 監測各個狀態副本或者狀態機輸出可能出現的差異。
複製狀態機最核心也是最困難的部分是如何確定出一個輸入順序，以便讓每個狀態機實例都嚴格按照該順序執行狀態遷移，從而保證一致性。從整體架構上來說，ZAB 協議和 Raft 協議都依賴單一的主節點確定輸入順序：所有的更新操作只能通過主節點進行，因此順序由主節點唯一確定。所不同的是，ZAB 協議通過顯式的類兩階段提交方法保持廣播更新操作的原子性，而 Raft 協議甚至沒有顯式的提交過程，直接依賴計數的方法實現隱式提交。
在 StateSynchronizer 的場景下，狀態機實例即 StateSynchronizer 客戶端，輸入順序即更新操作的應用順序，執行狀態遷移即應用更新操作至本地共享狀態。StateSynchronizer 使用完全不同的方式解決輸入順序的確定問題，使得 StateSynchronizer 不需要依賴任何主節點。從嚴格意義上說，StateSynchronizer 並不負責維護數據副本，但是其本地共享狀態的維護和更新模型都與數據副本有著相似之處。我們將在下文詳細討論 StateSynchronizer 如何確定輸入順序以及和傳統模型的差別。
如果讀者仔細閱讀過 StateSynchronizer 的源代碼，就會發現 StateSynchronizer 接口內定義有一個名為UpdateGenerator的函數式接口。UpdateGenerator接口本質上是一個二元消費者：它接受兩個參數，其中一個是StateT類型的當前共享狀態，另一個是以List形式存在在更新操作（Update類型）列表，而列表內 的更新操作最終都將被持久化到相應的 stream 上。從概念上看，UpdateGenerator接口其實就是公式 2 的等價實現。
2.2.3只存儲更新操作
在傳統的數據庫模型中，數據庫的服務器端負責維護一個全局的持久化的共享狀態，即數據庫中所有數據所組成的一個集合。多個獨立的客戶端同時向服務器端提交更新操作（事務），更新操作作用於共享狀態上引起狀態改變，而客戶端本地不存儲任何狀態。在這個模型中，服務器端的共享狀態無論從邏輯上看還是從物理上看，它都是共享的（這與 StateSynchronizer 的共享狀態有很大的不同）：因為幾乎所有的數據庫系統都允許多個事務併發執行。從形式化的角度看，所謂“事務 ui和 uj是併發的”指的是它們既不滿足 ui ≺ uj 關係，也不滿足 uj ≺ ui 關係，即 ui 的作用對 uj不完全可見，並且 uj的作用對 ui也不完全可見 [13]。可以不是很精確地將併發理解為：ui和 uj之間無法確定順序。也可以從直覺上這樣理解：ui和 uj的執行，在時間上存在重疊部分。併發直接導致了數據一致性問題。傳統數據庫模型解決併發問題的手段是設置事務的隔離級別 [26]：併發事務在不同的隔離級別下有著不同的可見性。
StateSynchronizer 擯棄了傳統的數據庫模型，從一個完全不同的角度解決併發問題和狀態機輸入順序問題。其核心思想是，StateSynchronizer 的服務器端只存儲（持久化）了更新操作本身而不是共享狀態，共享狀態由每個客戶端獨立維護，如 2.2.1 小節所述。由於 StateSynchronizer 架構中並不存在物理上的共享狀態，因此不會因為狀態共享而導致競爭，也不會因此產生併發問題。對於每一個 StateSynchronizer 的客戶端而言，所有的更新操作都是順序地作用於本地的共享狀態副本（物理上順序執行），這也不存在併發問題。但是，單憑這一點還不足以保證共享狀態的一致性，除非能夠保證唯一的更新操作應用順序。StateSynchronizer 的服務器端用單 segment 的 stream 存儲了所有的更新操作：每一個更新操作作為一個 event 被持久化 ^5。Stream 的最大特性就是隻允許追加：所有的 event 寫入操作只允許在尾部進行（原子操作），並且一個 event 一旦寫入就不允許修改。這一特性不僅使得多個 writer 可以同時進行寫入並且保持一致性，還使得所有 event 的順序得以唯一確定，即每個 event 最終在 Segment 內的相對順序。所以，對於每一個 StateSynchronizer 客戶端來說，都能夠看見一個一致的有序的更新操作視圖。
細心的讀者可能還希望進一步瞭解服務器端的 stream 是如保持只允許追加的特性和一致性的。與 Kafka 的消息代理節點（Broker）直接用本地文件系統存儲 stream 數據的方法不同，Pravega 的消息代理節點將數據的存儲完全交由一個抽象的存儲層代理，包括數據副本的維護。目前已經支持的具體存儲層實現包括：BookKeeper [27]，HDFS [28]，Extended S3 [29]，NFS [30] 等等。也就是說，數據副本的實現對消息代理節點來說是完全透明的。具體的 segment 分層存儲設計細節已經超出本文的討論範圍，感興趣的讀者可以自行閱讀 Pravega 的相關文檔 [31]。
StateSynchronizer 的這種數據模型其實非常類似 Change Data Capture（CDC） [32] 和 Event Sourcing [33] 的設計模式：不存儲系統狀態，而是通過推導計算得出 [13]。以 stream 形式存在的更新操作其實可以看作是系統狀態的另一種視圖。從這一視圖出發，不僅能夠推導出系統的最終狀態，還可以得出系統在歷史任意時刻的狀態。
為了讓所有的更新操作本身都能被持久化到 stream 中，StateSynchronizer 要求所有的更新操作都以類的形式實現，封裝好所有所需的狀態並且支持序列化 / 反序列化。這一點從StateSynchronizer的接口定義上也可以反映出來：創建一個StateSynchronizer實例必須提供兩個Serializer接口實例，分別用於對更新操作和起始狀態作序列化 / 反序列化，並且UpdateGenerator接口的定義要求所有更新操作必須實現Update接口。
2.2.4更新操作的寫入模式：條件寫與無條件寫
將更新操作本身持久化到相應的 stream 中是 StateSynchronizer 實現更新操作接口的重要步驟之一，因為只有這樣才能使所有的 StateSynchronizer 客戶端都看見一個全局唯一的更新操作序列。目前，StateSynchronizer 支持以兩種不同的模式將更新操作持久化到 stream 端：條件寫模式（Conditionally Write）與無條件寫模式（Unconditionally Write）。這兩種更新模式分別有各自的適用場景。
在條件寫模式下（參考StateSynchronizer接口上updateState()方法的實現），當 StateSynchronizer 客戶端嘗試把一個更新操作寫入 stream 內時需要首先檢查當前本地的共享狀態是否是對應 stream 上的最新狀態。如果是，則寫入成功，可以繼續將該更新操作作用於本地的共享狀態並更新為新狀態；如果不是，說明已經有其它的客戶端搶先往 stream 中寫入了其它更新操作，此時本地的共享狀態已經“過期”，本次寫入失敗，如圖 2 所示。對於寫入失敗的情況，StateSynchronizer 會自動嘗試從 stream 拉取所有缺失的更新，並將所有拉取到的更新順序作用於當前本地共享狀態以便將其更新到最新狀態，然後重試條件寫。這一“失敗 - 重試”的過程可能重複多次，直至寫入成功。從概念上看，條件寫表現出的行為與多線程編程中的 CAS 操作有著諸多相似之處。
如果讀者仔細思考條件寫的實現細節，不難得出如下的結論：檢查狀態是否過期與實際的 stream 寫入動作必須是一個整體的原子操作，否則將出現競爭條件。事實上，檢查狀態是否過期這一動作並不是在客戶端進行的，而是由 stream 的相關接口直接代理的，否則很難與發生在服務器端的寫入動作合併為一個原子操作。在閱讀過 StateSynchronizer 實現類StateSynchronizerImpl的源代碼之後，讀者會發現一個名為client的RevisionedStreamClient類型成員。RevisionedStreamClient是 StateSynchronizer 客戶端用來與後端 stream 交互的唯一入口，所有 stream 的讀寫操作都通過該接口進行，包括條件寫。RevisionedStreamClient接口上有一個名為writeConditionally()的方法（即條件寫的真正實現），允許在寫入一個 event 的同時指定一個 Revision。正如其名字所暗示的那樣，Revision接口可以近似理解為 stream 的“版本”：每次成功的寫入操作都會導致對應 stream 的 Revision 發生變化，writeConditionally()方法甚至還直接返回該 Revision 以方便客戶端用作多版本併發控制。現在繼續討論writeConditionally()方法的行為，只有當 stream 的當前的實際 Revision 與指定的 Revision 相同時（即：從上次成功條件寫入到目前為止都沒有其它的成功寫入發生），真正的寫入動作才發生，否則寫入失敗。很明顯，這是一個典型的樂觀併發控制模式。
聰明的讀者甚至還可以從物理實現角度理解 Revision。從 2.2.1 小節的討論中我們知道，Revision 是基於 segment 內的偏移量實現的，而 segment 本質上就是一個無邊界的字節流。所謂 stream 的“版本”其實就是 stream 當前尾端的偏移量。由於 stream 只允許追加的特性，往指定偏移位置執行寫入操作時，只有當該偏移確實處於尾端時才能成功。圖 2 中所標記的 Revision 既可以看作是當前本地共享狀態所對應的 stream 版本，也可以看作是當前 StateSynchronizer 客戶端所看見的 stream 尾部位置。從這個角度看，stream 的特性和操作得到了統一。
由於條件寫的失敗 - 重試機制，在某些極端場景下（例如更新操作極度頻繁引起的激烈競爭），可能導致較多次數的重試。並且由於條件寫操作目前並未實現公平機制，理論上可能出現某個客戶端“飢餓”的情況。為應對這種場景，StateSynchronizer 還提供了另一種持久化模式：無條件寫模式。在無條件寫模式下（參考StateSynchronizer接口上updateStateUnconditionally()方法的實現），StateSynchronizer 客戶端往 stream 寫入更新操作時並不會要求比較 Revision，而是無條件地將該更新操作寫入當前 stream 的實際尾端，並且在寫入成功後也不會更新本地的共享狀態。從實現上看，無條件寫模式下的更新動作其實就是一個簡單的 stream 追加動作。在服務和資源正常的情況下，stream 的追加寫入總是能夠成功的。如果調用者希望得到更新操作作用後的共享狀態，則還需要手動拉取一次更新（參考StateSynchronizer接口上的fetchUpdates()方法）。由於更新操作的件寫入動作與拉取動作之間存在時間窗口，在這段時間內可能已經有其它的客戶端繼續寫入新的更新操作。因此，在拉取得到的更新操作序列上，並不能保證之前提交的更新操作是該序列上的最後一個元素。也就是說，在應用該更新操作之前和之後，可能有其它的更新操作已經作用或繼續作用在當前本地共享狀態上。相反，條件寫模式卻總是能保證所提交的更新一定是最後一個作用在當前本地共享狀態上的操作。根據具體應用場景的不同，這可能是個問題，也可能不是。例如，在無條件寫模式下，所有的更新操作現在都變得不可觀測了：假設你執行了一個無條件的更新操作，往一個共享的集合裡面添加了一個元素。現在，哪怕你立刻進行集合遍歷，也不能保證你一定能夠找到剛剛添加的元素，因為可能存在其它客戶端提交的後續更新操作已經將剛剛添加的元素刪除了。這恐怕是一種與直覺相違背的行為表現。總之，與條件寫相比，無條件寫有著優異的併發性能，但是這一切都是有代價的，例如：犧牲了開發者的可理解性。
2.3其它問題
2.3.1更新操作與確定性
StateSynchronizer 的更新操作模型（2.2.2 小節）要求所有更新操作的實現必需是確定性的，因為所有的更新操作都會在每一個 StateSynchronizer 客戶端被重放。對於相同的輸入，如果更新操作本身不能夠產生確定性的結果，即使以完全相同的順序在每一個客戶端被執行，也會破壞共享狀態的最終一致性。根據實際業務場景的不同，這一要求可能是一個問題，也可能不是，例如：
- 不可以使用隨機函數。這一看似簡單的要求實際上限制了不少可能性，很多科學計算依賴隨機函數。
- 不可以使用絕大多數的本地狀態，例如：本地時間，本機硬件信息等。
- 引用任何外部系統的狀態都需要格外小心可能引入的不一致。例如，如果一個外部系統的狀態會隨時間變化，各個客戶端可能看到各不相同的外部狀態，因為同一個更新操作在每個客戶端被執行的時間點是不確定的。
除了保證更新操作的確定性之外，還需要特別注意更新操作的執行是否具有“副作用”，例如：引發全局狀態或外部系統狀態的改變。如果回答是肯定的，那麼還需要特別注意這些引發狀態改變的動作接口是否具有冪等性 [34]，因為同一個更新操作不僅會在每個客戶端被執行，即使在同一客戶端也可能被執行多次（2.2.4 小節）。
2.3.2更新操作與更新丟失問題
有人擔心 StateSynchronizer 是否存在丟失更新問題 [6]。丟失更新問題一般在如下場景發生：兩個進程併發地對同一共享變量進行“讀取 - 修改 - 寫入”組合操作。如果這一組合操作不能夠被作為一個原子操作完成，那麼後寫入的狀態有可能覆蓋另一個寫入操作的結果，導致其中一個修改結果（更新）“丟失”。如 2.2.3 小節所述，所有的更新操作都是在 StateSynchronizer 的客戶端本地順序執行的，因此不存在併發修改共享狀態的場景，也不會產生更新丟失問題。
雖然 StateSynchronizer 客戶端保證了以併發安全的方式執行所有更新操作，但是，一個不正確實現的更新操作仍有可能導致更新丟失問題。如果一個應用需要實現“讀取 - 修改 - 寫入”組合操作，唯一正確的做法是將所有的讀取，修改和寫入動作都封裝在同一個更新操作中，即按如下偽代碼所示實現更新操作 un ：
un：
> 讀取狀態 sn；
> 執行修改；
> 生成並返回新狀態 sn+1；
源代碼 1 用偽代碼表示的更新操作一般實現
一種常見的錯誤是在更新操作 un外部進行“讀取狀態 sn”和“執行修改”動作，並將新狀態 sn+1直接封裝進更新操作 un。另一種不那麼直觀的錯誤是，儘管將“讀取”，“修改”和“寫入”動作都封裝進了同一個更新操作，但是在進行“讀取狀態 sn”動作時有意或無意地使用了某種緩存機制，即並非每次都從 StateSynchronizer 獲取當前共享狀態 sn。這兩種錯誤的實現都將導致很嚴重的丟失更新問題。2.2.4 小節的相關討論解釋了其中的原因：由於條件寫操作可能失敗並重試多次，並且每次重試都意味著 StateSynchronizer 客戶端本地的共享狀態已經改變，任何緩存或者等價的行為都將導致實際的“執行修改”動作作用在一個已經過期的舊狀態上，從而導致丟失更新問題。
2.3.3更新操作的順序執行與性能
在每一個 StateSynchronizer 客戶端上，所有的更新操作都是順序執行並作用在本地共享狀態上的，正所謂“解決併發問題最簡單的辦法就是完全消除併發” [13]。有人擔心更新操作的順序執行是否會顯著降低系統性能。從目前已有的研究看，用單線程的方式執行所有事務是完全可行的 [35]，並且在很多現有的數據庫實現中已經被採用，例如：VoltDB/H-Store [36]，Redis [37]，Datomic [38] [39] 等。當然，這對事務本身以及數據集都有所要求 [13]，例如：
- 每個事務必須足夠小，並且足夠快。
- 數據集的活躍部分必須足夠小，以便能夠全部載入物理內存。否則，頁面的頻繁換入和換出會引起大量的磁盤 IO 操作，導致事務頻繁阻塞。
- 寫操作的吞吐量必須足夠小，以便單 CPU 核心可以有足夠的能力處理。否則，CPU 運算能力將成為瓶頸。
對於一個 StateSynchronizer 應用來說，無論是共享狀態還是更新操作的設計實現，都必須遵循上述要求。
2.3.4歷史重放與狀態壓縮
每一個 StateSynchronizer 客戶端在進行啟動後的首次更新操作時，都需要從對應的 stream 拉取所有的歷史更新操作，並重放這些操作以便得到當前最新的共享狀態。如果這是一個長時運行的共享狀態，那麼 stream 內此時可能已經累積了相當數量的更新操作。拉取並重放所有這些更新操作可能需要消耗大量的時間與資源，造成首次更新性能低下。為了應對這種場景，StateSynchronizer 還提供了所謂的狀態壓縮機制。狀態壓縮（compact）是一個特殊的StateSynchronizer接口方法，它允許將 StateSynchronizer 客戶端的本地共享狀作為一個新的起始狀態，用條件寫模式重新寫入 stream^6，並且使用 stream 的 mark 機制標記該起始狀態的最新位置^7。StateSynchronizer 客戶端每次拉取更新操作時，都會首先嚐試使用 mark 機制定位到最新的起始狀態並忽略所有之前的更新操作，從而避免了長時間的歷史重放。
如果首次更新操作的性能對於應用程序來說非常重要，那麼開發者可以選擇週期性地進行狀態壓縮。那麼首次更新操作所要拉取和應用的更新操作數量則不會多於一個週期內所累積的更新操作數量，這將大大提升首次更新操作的性能。
3總結
本文主要從狀態共享和一致性的角度出發，詳細描述了 Pravega 的狀態同步組件 StateSynchronizer 的工作機制和實現細節。StateSynchronizer 支持分佈式環境下的多進程同時讀寫共享狀態，並提供一致性保證。StateSynchronizer 具有典型的客戶端 / 服務器架構，但是卻非常輕量和高效，因為服務器端僅僅用於提供存儲媒介。StateSynchronizer 的核心工作機制可以歸納為兩個關鍵點：維護本地共享狀態和只存儲更新操作本身。StateSynchronizer 利用 stream 的天然特性實現了更新操作的全局有序。StateSynchronizer 還提供了條件寫和無條件寫兩種更新寫入模式，可以適用於併發度極高的場景。StateSynchronizer 未來的工作可能集中在如何向開發者提供更加便捷易用的編程接口，以減輕開發者的負擔。
Pravega 系列文章計劃
Pravega 根據 Apache 2.0 許可證開源，0.4 版本已於近日發佈。我們歡迎對流式存儲感興趣的大咖們加入 Pravega 社區，與 Pravega 共同成長。本篇文章為 Pravega 系列第五篇，系列文章如下：
- 實時流處理 (Streaming) 統一批處理 (Batch) 的最後一塊拼圖:Pravega
- 開源 Pravega 架構解析：如何通過分層解決流存儲的三大挑戰？
- Pravega 應用實戰：為什麼雲原生特性對流存儲至關重要
- “ToB” 產品必備特性: Pravega 的動態彈性伸縮
- 高併發下新的分佈式一致性解決方案 (StateSynchronizer)
- Pravega 的僅一次語義及事務支持
- 與 Apache Flink 集成使用
閱讀更多 碼農架構 的文章
