跨地域場景下，如何解決分布式系統的一致性？
跨地域，即常說的“異地雙活”、“異地多活”中的異地概念。在業務發展較快的情況下，我們的服務便需要跨地域部署，以滿足各區域就近訪問和跨地域容災等需求，在此過程中，不可避免會涉及到跨地域下的分布式一致性問題。由跨地域所帶來的網絡延遲問題，以及由于網絡延遲而衍生的一系列問題，對于設計和構建一個跨地域分布式一致性系統是極大的挑戰，業界有很多針對此問題的解決方案，都希望能解決跨地域場景下的一致性問題。
本文分享阿里巴巴女媧團隊在跨地域場景下對分布式一致性系統的探索，從"What How Future"三個方面，介紹跨地域場景下要承接的需求和挑戰、業界常見系統和女媧團隊對于跨地域場景權衡點的思考，以及對跨地域一致性系統未來發展的設計與思考，以發現和解決跨地域場景下更多的需求和挑戰。
一 跨地域需求和挑戰
1 需求
跨地域問題是在集團全球化戰略下，業務快速發展帶來的挑戰。像是淘寶單元化業務，或是AliExpress區域化業務，都有一個無法回避的問題——數據跨區域讀寫一致性。
其核心需求可以總結為以下幾點：
跨地域業務場景
跨地域配置同步與服務發現是兩個常見的跨地域一致性協調服務的業務需求，跨地域部署可以提供就近訪問能力以減小服務延遲，根據具體業務場景可分為多地域寫或簡化的單地域寫、強一致性讀或最終一致性讀等場景?？绲赜虻臅捁芾砑盎诖说目绲赜蚍植际芥i也亟待提供成熟的解決方案。
服務、資源的拓展問題
當一個地域內某個機房的服務能力達到上限而又無法擴容，需要一致性系統在一個地域多個機房水平拓展和能夠跨地域拓展。
跨地域容災能力
當遭遇機房或者一個地域的災難性故障時，需要一致性系統通過跨地域服務部署，將一個地域的業務迅速遷移到另一個地域完成災備逃逸，實現高可用。
2 挑戰
綜合網絡延遲和業務需求，可以歸納出跨地域一致性系統所需要化解的挑戰：
延遲：網絡延遲達幾十毫秒
多地域部署帶來的核心問題便是網絡延遲高，以我們線上跨地域部署的跨地域集群為例，集群中機器分屬于杭州、深圳、上海、北京四個地域的機房，實際測試杭州機房到上海延遲大約6ms，到深圳和北京的延遲可以達到接近30ms。同機房或同地域機房間的網絡延遲一般在毫秒內，相比之下跨地域訪問延遲上升了一個量級。
水平拓展：Quorum Servers規模受限
基于Paxos理論及其變種的分布式一致性系統，在拓展節點時不可避免會遇到Replication Overhead問題，一般一個Quorum的節點數目不大于9個，故無法簡單地將一致性系統節點直接部署在多個地域，系統需要能持續地水平拓展，來滿足服務、資源的拓展需求。
存儲上限：單個節點存儲數據受限且failover恢復慢
無論是MySQL還是基于Paxos的一致性系統，其單個節點都會維護和加載全量的鏡像數據，會受到單臺集群容量的限制。同時在failover恢復時，若數據版本落后較多，通過拉取其他地域鏡像恢復會有較長的不可用時間。
二 我們的探索
1 業界解決方案
業界有針對跨地域的一致性系統有很多的設計，主要參考了論文[1]和一些開源的實現，下面介紹常見的幾種：
跨地域部署
圖1 直接跨地域部署
直接跨地域部署，讀請求直接讀本地域節點，速度較快，一致性、可用性由Paxos保證，沒有單點問題。缺點也很明顯，會遇到第一部分中講到的水平拓展問題，即Quorum拓展時會遇到Replication Overhead問題。且隨著Quorum節點數目變多，在跨地域極高的網絡延遲下，每次多數派達成一致的時間會很長，寫效率很低。
單地域部署+Learner角色
圖2 引入Learner角色
通過引入Learner(例如zk中Observer、etcd的raft learner[2]) 角色，即只進行數據同步而不參與多數派投票的角色，將寫請求轉發到某一個區域(如圖2中的Region A)，來避免直接多節點部署的投票延時問題。此種方式可以解決水平拓展問題和延時問題，但由于參與投票的角色都部署在一個地域內，當此地域機房遇到災難性時間時，寫服務便不可用了。此種方式是Otter[3]所采用的部署方式。
多服務+Partition&單地域部署+Learner
圖3 多個服務處理分Partition
將數據按規則切分為不同Partition，每個地域一個Quorum提供服務，不同地域Quorum負責不同Partition，地域之間Quorum使用Learner進行不同Partition數據同步及寫請求轉發，保證某區域出現問題只影響該區域Partition可用性。同時此種方案下會有正確性問題，即操作不符合順序一致性[4]的問題(見論文[1])。
實際實現時根據業務場景有各種解決方案，會針對性地進行優化和權衡，彌補缺陷。業界較常見方案的是單地域部署+Learner角色這種方案，通過同城多活和Learner做跨地域數據同步來保證較高的可用性和較高的效率。其他方案也各有優化方案，跨地域部署可以通過減少達成決議時地域間通信，來減小延時和帶寬問題，如TiDB的Follower Replication[5];多服務+Partition&單地域部署+Learner這種方案的正確性也可以通過論文[1]中所述，在讀之前添加sync操作，犧牲一部分讀的可用性來保證一致性。
最后的結論如下表，后面會詳細闡釋其中的關鍵項：
2 跨地域的權衡
通過第一部分總結的需求挑戰和前面對業界跨地域一致性系統解決方案的調研，可以總結出基于Paxos的分布式一致性系統在跨地域場景下的核心權衡點：
- 寫操作跨地域走一致性協議達成決議太慢
- 地域內多活無法提供極端情況下的可用性
- 需要具備分布式系統最核心的水平拓展能力
針對這三點問題，我們設計了一種日志鏡像解耦的跨地域一致性系統。
3 跨地域日志鏡像解耦
圖4 日志鏡像解耦示意圖
如圖3所示，我們的系統分為后端日志同步通道和前端全量狀態機——日志與鏡像解耦的架構。后端跨地域全局日志同步通道，負責保證請求日志在各個區域的強一致性;前端全量狀態機部署在各地域內，處理客戶端請求，也負責與后端日志服務交互，對外提供全局強一致性元數據訪問服務，接口可以根據業務需求快速修改狀態機來實現。
在全局日志與本地鏡像分離的架構下，除了解耦本身帶來的系統運維和可拓展性的提升，我們還可以解決很多未解耦架構下的問題，后面幾條分析是在此種架構下如何對之前思考部分幾大問題的一個解決：
寫操作效率
單從部署的模式上看，看起來與直接多地域多節點部署，然后各地域添加Learner角色的做法類似，是直接多節點部署和引入Learner的一個結合，綜合了兩種方式的優缺點。最大區別在于，我們的日志和鏡像解耦了，也就是說跨地域的部分是足夠輕量高效的單純日志同步，且由于每個地域只有一個節點，能夠節省跨地域帶寬(類似TiDB的Follower Replication)。同時后端日志同步通道，也可以實現多Group的功能，將數據分成Partition，每個一致性Group負責不同的Partiton。
由于大部分業務場景的讀操作為讀本地數據，各種方式相差不大，主要進行寫操作的延遲分析，下面是對于寫操作(或強一致性讀)的延遲分析：
RTT(Round-Trip Time)，可以簡單理解為發送消息方從發送請求到得到響應所經過的時間。由于跨地域網絡延遲較大，后面RTT主要指跨地域RTT。
(1)直接跨地域部署
對于一個常見的有主一致性協議，我們的請求分兩種情況：
訪問Leader所在地域 1個RTT(暫時忽略地域內較小的延遲)
- Client -> Leader ----> Follower ----> Leader -> Client
訪問Follower所在地域 2個RTT
- Client -> Follower ----> Leader ----> Follower ----> Leader ----> Follower ->
(2)單地域部署+Learner同步
在地域內多活，地域間Learnner同步的方案中，我們的延時為：
本地域 0個RTT
- Client -> Quorum -> Client
地域間 1個RTT
- Client -> Learner ----> Quorum ----> Learner -> Client
(3)多服務Partition，單地域部署+Learner同步(與B結果類似)
寫本地域Partition 0個RTT
跨Partition寫 1個RTT
(4)日志鏡像解耦的架構(與A結果類似)
寫本地域Partiton 1個RTT
- Client ->Frontend -> LogChannel(local) ----> LogChannel (peer) ----> LogChannel (local) -> Frontend -> Client
跨Partition寫 2個RTT (Paxos兩階段提交/轉發leader)
- Client ->Frontend -> LogChannel (local) ----> LogChannel (peer) ----> LogChannel (local) ----> LogChannel (peer) ----> LogChannel (local) -> Frontend -> Client
經過以上的對比，可以看出只要跨地域走一致性協議進行寫操作，最少也會有1個RTT的延遲，而如果將Paxos Quorum只部署在單地域，又不能保證任何極端情況下的可用性。所以我們根據業務需要，可以進行可用性和寫效率的權衡，日志鏡像解耦的架構可以在多地域部署場景下保證極端的可用性和正確性，當然效率上會比單地域部署+learner稍差一些，但如果采用多整體比直接多地域部署的方式要輕量高效，因為Quorum規模不會因水平拓展增加，不會影響投票效率。與多服務分Partition部署的方案則沒有效率優勢，但在可運維護性、正確性、可用性這些方面都有優勢。
一致性
跨地域部署和單地域部署+Learner的強一致性是滿足的，zookeeper和etcd都有對應的介紹，在此不做贅述。多服務Partition分Partion這種方案不滿足順序一致性，主要是因為多服務不能保證每條寫操作commit的順序性，見下圖：
圖5 順序一致性
可以看到，當兩個Client同時對x,y進行修改時，在寫操作并發程度較高的情況下，不能保證順序一致性。
順序一致性即可以將各個Client的操作排列出一個正確順序，在圖4的例子中：
- set1(x,5) => get1(y)->0 => set2(y,3) => get2(x)->5
或者
- set2(y,3) => get2(x)->0 => set2(y,3) => get1(y)->3
都是符合順序一致性的。
日志鏡像解耦的架構的一致性可以簡單理解為跨地域部署+Learner，寫操作有sync選項，會在后端log提交成功并拉取到對應log時才會返回成功，因此一定是可以拉取到其他Client在此操作之前的寫操作對應的log，故符合順序一致性。
可用性
可用性這點與直接跨地域多節點部署的可用性類似，前端狀態機可以在某個地域后端節點掛掉情況下進行請求轉發，在后端全局日志服務不可用時也可以提供讀的可用性，可以提供極端情況下的讀寫高可用保證。
同時由于鏡像存儲在各個地域的狀態機中，當某個前端狀態機掛掉時可以把客戶端切換到其他前端，failover恢復時也可以直接從后端拉取數據恢復，在落后太多情況下才需要從本地域其他前端拉取鏡像，不用跨地域同步鏡像，由此可以使得前端的不可用時間極短。
水平拓展能力
水平拓展能力是分布式服務的核心能力，在前述的多種方案中，直接跨地域部署水平拓展能力極差，其他依賴Learner的方式，也解決了水平拓展的問題，只是解耦沒有日志鏡像解耦的設計干凈。
將以上幾個關鍵問題總結對比：
三 跨地域更多可能性
后端日志和前端鏡像解耦的狀態下，我們對跨地域場景的探索分為兩部分——后端日志同步輕量高效和前端狀態機靈活豐富。
- 輕量，體現在架構，后端只同步日志帶來的后端存儲壓力極小，只用同步輕量的增量日志。
- 高效，體現在后端的一致性協議，由于輕量，所以只需要考慮投票和選舉的邏輯，只用注重日志同步效率的提升，后端資源不用消耗在其他業務邏輯上。
- 靈活，體現在架構，前端可以自定義上傳日志，CAS、事務等都可以包裝成日志由前端解析和處理。
- 豐富，主要是體現在前端的狀態機，由于日志的靈活留給我們探索和構建的空間極大，可以根據需求包裝出處理各種復雜事務的狀態機。
新的架構下有新的問題，這一部分主要探究如何吸取已有系統的優點，利用日志鏡像解耦下的輕量、靈活，來實現跨地域場景下一致性協議和狀態機的高效、豐富，也會對跨地域一致性系統后繼如何發展有一個思考和規劃?？傮w目標是后端一致性協議做精做深，前端狀態機做大做強。
1 高效的后端一致性協議
基于我們前面對寫操作效率的討論，在多地域寫同一數據場景下，延遲只能控制在2RTT。因為跨地域場景下，延遲占比主要在跨地域網絡通信，無論是有主的轉發還是無主的Paxos兩階段提交，延遲都有2RTT。但如果使用無主的協議，如Paxos的變種EPaxos[6]，則可以盡可能提高跨地域場景下寫的效率，其延遲分Fast Path和Slow Path兩種情況，在Fast Path下延遲為1RTT, Slow Path下延遲為2RTT。
引用介紹EPaxos文章中的一句話：
若并發提議的日志之間沒有沖突，EPaxos只需要運行PreAccept階段即可提交(Fast Path)，否則需要運行Accept階段才能提交(Slow Path)。
相比于分Partition操作，如果將后端一致性協議選為EPaxos，則可以保證極端情況下的可用性和大多數情況下延遲為1RTT，這是無主一致性協議在跨地域場景下的優勢，主要是因為省去了一次轉發Leader操作的RTT。目前我們系統中使用的是最基礎的Paxos的實現，在多地寫場景下延遲理論上與有主的協議相差不大，后繼發展期望利用EPaxos來加快跨地域場景下寫操作的效率。
由于不需要實現各種業務邏輯，高效便是后端一致性協議的最大訴求，當然其正確性、穩定性也是必不可少的，而對于前端的狀態機，則有著豐富的場景來設計和發揮。
CAS操作
CAS操作在此種架構下的實現是很自然的，由于后端只有一致性log，所以我們每一次CAS請求，自然而然會有Commit的先后順序，舉一個例子。
兩個客戶端同時寫同一個Key的值：
圖 6 CAS操作示意圖
開始時key的值為0，此時Client 1和Client 2并發對key進行CAS操作，分別為CAS(key, 0, 1)和CAS(key, 0, 2)，當這兩個操作同時提交并Commit后，由于后端Quorum達成決議的先后，Replication Log一定會有先后順序，因此自然而然這兩個并發的CAS操作轉換為順序執行。當Frontend同步到這兩個操作的log時，會依次apply這兩個操作到本地狀態機，自然CAS(key, 0, 1)成功，更新key值為1，而CAS(key, 0, 2)更新失敗，這時前端會返回給對應請求的Client其CAS請求是否成功或失敗的結果。
其原理是將一個并發操作變成了一個順序執行的串行過程，由此避免了在跨地域場景下對加鎖的操作，可以想象如果是后端維護了一個kv結構數據，則還需要增加一個跨地域分布式鎖來完成此操作，相對更加繁瑣，效率也沒有保證。通過只同步日志把復雜計算轉移到Frontend，可以靈活地構建前端狀態機，更好地實現CAS或更復雜的事務功能(此種架構可參考pravega的StateSynchronizer[7])。
Global ID
Global ID是一個常見的需求，分布式系統生成一個唯一ID，常見的有使用UUID、snow flake算法，或者基于數據庫、redis、zookeeper的方案。
類似使用zookeeper的znode數據版本進行Global ID的生成，在此種日志鏡像分離架構中，可以使用CAS接口調用，生成一個key作為Global ID，每次對Global ID進行原子操作?；谏鲜龅腃AS設計，跨地域并發場景下不需要加鎖，在使用方式上類似redis對key進行原子操作。
2 Watch操作
訂閱功能是分布式協調服務的不可或缺的，是業務最常見的一種需求，下面是對zk和etcd的調研結果：
目前業界比較成熟的實現了訂閱通知的分布式協調系統包括ETCD和ZooKeeper，我們分別以這兩個系統為例講解各自的解決方案。
ETCD會保存數據的多個歷史版本(MVCC)，通過單調遞增的版本號來表明版本的新舊，客戶端只要傳入自己關心的歷史版本，服務端就可以將后續的所有事件推送給客戶端。
Zookeeper并不會保存數據的多個歷史版本，只有當前的數據狀態，客戶端并不能訂閱數據的歷史版本，客戶端只能訂閱當前狀態之后的改變事件，所以訂閱伴隨著讀，服務端把當前的數據發送給客戶端，然后推送后續的事件，同時為了防止在failover等異常場景訂閱到老的數據和事件，客戶端會拒絕連接數據比較老的服務端(這依賴于服務端會在每個請求會返回當前的服務端全局的XID)。
上述的調研結果中ETCD較為符合我們的接口設計，目前ETCDv3 使用了HTTP/2的TCP鏈接多路復用，watch性能有提升。由于同為日志加狀態機結構，設計功能時主要參考了ETCD v3，借鑒其如何訂閱多個key以及返回全部歷史事件這兩個特性。若要達到etcd訂閱的功能，我們在前端狀態機同步并解析日志時，如果出現寫日志，則將kv結構的狀態機Store和 專門提供給watch接口的狀態機watchableStore同時更新，具體實現可以完全參考etcd，然后按日志版本號將訂閱時版本后的歷史事件全部返回給客戶端。而訂閱多個key則同樣使用線段樹作為watcher的range keys存儲結構，可以實現watch范圍keys的watcher通知。
3 Lease機制
在無主的系統中實現高效的Lease機制是一大挑戰，無主的系統中沒有Leader，任意節點均可維護Lease，Lease分布在各個節點上，當有節點不可用時，需要平滑切換到其它節點。無主的系統中實現高效的Lease機制的難點在于隨著Lease數量的增加，如何避免后端的一致性協議中出現大量的Lease維持消息，影響系統性能，最好讓Lease維持消息能夠直接在前端本地處理，而不經過后端。所以我們的思路是將客戶端與前端的Lease聚合到前端與后端的Lease，使得Lease維持消息能夠直接在前端本地處理。
四 結語
隨著全球化戰略的推進，跨地域方面的需求一定會越來越迫切，跨地域場景的真正痛點也會越來越清晰，希望我們在跨地域方面的調研和探索可以給大家一個思路和參考，我們也會繼續探索跨地域日志鏡像分離的架構下更多的可能性。
相關鏈接
[1]https://www.usenix.org/conference/atc16/technical-sessions/presentation/lev-ari
[2]https://github.com/etcd-io/etcd/blob/master/Documentation/learning/design-learner.md
[3]https://github.com/alibaba/otter
[4]https://zhuanlan.zhihu.com/p/43949695
[5]https://zhuanlan.zhihu.com/p/94663335
[6]https://zhuanlan.zhihu.com/p/163271175
[7]https://github.com/pravega/pravega/blob/master/documentation/src/docs/state-synchronizer-design.md
