一、多地域部署挑戰(zhàn)

1、Abase簡介

首先簡單了解一下Abase在字節(jié)跳動公司（以下簡稱字節(jié)）的使用情況。

Abase是字節(jié)跳動規(guī)模最大的NoSQL數(shù)據(jù)庫之一，峰值QPS達(dá)到了百億級別，管理的數(shù)據(jù)存儲容量達(dá)到了EB級別，服務(wù)了字節(jié)跳動大多數(shù)產(chǎn)品線。Abase支持Redis協(xié)議/Thrift協(xié)議/批量導(dǎo)入等接入方式。用戶最常使用的接入方式為Redis協(xié)議，本次的分享主要圍繞Redis協(xié)議的CRDT支持來介紹。

2、多地域部署需求

再來看一下為什么數(shù)據(jù)庫需要多地域部署。

• 就近訪問：用戶和服務(wù)本身就是多地域部署的場景，服務(wù)有就近訪問需求；需要做到本地訪問的地延遲。
• 容災(zāi)需求：相比于同地域內(nèi)部多可用區(qū)域容災(zāi)，多地域部署能夠提供更高的容災(zāi)能力；
• 資源問題：當(dāng)某個地域沒有足夠資源，只能在其他地域部署；

3、Abase架構(gòu)演進(jìn)

Abase多地域部署的架構(gòu)也經(jīng)歷了一個演進(jìn)過程。

如上圖所示，是Abase 1.0版本中的異地多活方案，簡單來講就是部署兩個Abase集群，然后通過一個中間組件把一個地域的Abase集群的op log傳輸?shù)搅硪粋€地域，再寫入到Abase集群中。

但這個方案存在以下幾個問題：

• 同步延遲：由于跨越多個組件，所以同步延遲較長，無法提供RPC級別的時延。如多地域的網(wǎng)絡(luò)延時可能是50ms，但是數(shù)據(jù)同步延遲可能到達(dá)秒級別以上。
• 一致性問題：由于是外掛系統(tǒng)，在架構(gòu)設(shè)計中沒有能夠保證100%的數(shù)據(jù)傳輸可靠，另一方面多地域?qū)懭霐?shù)據(jù)沖突問題更難解決。
• 額外成本：包括同步組件的成本，數(shù)據(jù)沖突時修復(fù)數(shù)據(jù)時的成本，以及部署兩套集群需要額外的副本等。

下面我們具體介紹一下Abase1.0方案中，多地域部署下的數(shù)據(jù)不一致的問題：如上圖。在地域A和地域B各部署了一套Abase服務(wù)，初始時X都等于1，在地域A將X值設(shè)置為2，在地域B執(zhí)行刪除X的操作。當(dāng)數(shù)據(jù)互相同步之后，地域A可能看到X是一個空值，地域B可能看到X的值是2，如果沒有其他手段介入，這兩個地域的X值就會一直不一致，這種情況對用戶是很不友好的。

解決數(shù)據(jù)沖突問題有如下一些方案：

• 用戶側(cè)避免沖突：一種方式是用戶只在一個地域?qū)?，但這種方式會使得另一個地域跨地域訪問的延遲無法滿足；另一種方式是用戶將key進(jìn)行一些處理，部分key在某個地域?qū)?，部分key在另一個地域?qū)懀M(jìn)行單元化處理，但實際上并不是所有的key都能做到單元化。
• 搭建數(shù)據(jù)不一致檢測和修復(fù)系統(tǒng)：搭建一個第三方系統(tǒng)進(jìn)行數(shù)據(jù)沖突檢測，然后修復(fù)。這個方案是可行的，但是代價非常高，時間也非常長。字節(jié)內(nèi)部也有這樣的系統(tǒng)，但是該系統(tǒng)也不能100%保證數(shù)據(jù)最終一致。
• 服務(wù)側(cè)解決沖突：一種方式是通過向量時間戳等技術(shù)將沖突檢測出來交給用戶處理，這種方式對于一些高級用戶可能是ok的，但對于大多數(shù)普通用戶來說使用成本過高，我們希望能夠提供的是一個多地域部署的數(shù)據(jù)庫，用戶看到的是同一個Abase集群，在不同地域可以就近訪問。用戶不需要關(guān)心數(shù)據(jù)同步鏈路，不需要擔(dān)心數(shù)據(jù)最終一致性。所以我們采用了CRDT（無沖突復(fù)制數(shù)據(jù)類型）技術(shù)方案，從根本上避免沖突，達(dá)到數(shù)據(jù)的最終一致。

Abase通過支持原生多活以及CRDT技術(shù)，帶來了以下好處：

• 同步時延低：同步延遲基本為RPC時間；
• 強(qiáng)最終一致保證：保證數(shù)據(jù)無沖突，并且數(shù)據(jù)同步無丟失；
• 更低成本：不需要額外數(shù)據(jù)同步組件的成本，并且可以做到更低的副本數(shù)。

二、CRDT技術(shù)

下面將對CRDT技術(shù)進(jìn)行簡單介紹。

CRDT概念在2011年的一篇論文中正式提出，該論文主要討論了如果存在多副本同時更新的情況下，滿足怎樣的條件能讓數(shù)據(jù)達(dá)成最終一致。很快，CRDT技術(shù)在協(xié)同編輯領(lǐng)域得到了廣泛應(yīng)用。現(xiàn)在，在分布式數(shù)據(jù)庫中，特別是NoSQL類型數(shù)據(jù)庫中，如RedisLab，Cosmosdb以及Riak等數(shù)據(jù)庫中目前都提供了CRDT數(shù)據(jù)類型的支持。

如上圖所示，在CAP原理中強(qiáng)一致性、可用性、分區(qū)容錯性三者不能兼得，尤其是跨地域部署的情況下，分區(qū)容錯或兩個地域的網(wǎng)絡(luò)隔離和各種異常是不可避免的。Abase所服務(wù)的場景，更多是為了追求可用性，所以必須要犧牲強(qiáng)一致性，但犧牲強(qiáng)一致性不代表不追求最終一致性。CRDT中的“強(qiáng)最終一致性”做到了在最終一致的基礎(chǔ)上提供更強(qiáng)的保證。 “強(qiáng)最終一致”與可用性、分區(qū)容錯性并不沖突，是一個適合多地域部署解決方案。

CRDT分為兩種形式：一種為基于狀態(tài)，一種為基于操作。無論是基于狀態(tài)還是基于操作，CRDT的結(jié)構(gòu)設(shè)計都需要滿足以下幾個數(shù)學(xué)特性：

• 交換律
• 結(jié)合律
• 冪等性

其中交換律和結(jié)合律指，有副本A和副本B，多個副本的狀態(tài)以不同的順序合并都能達(dá)到一致。滿足這個條件后，不管是什么順序來同步副本數(shù)據(jù)，所有副本之間的最終數(shù)據(jù)必然是一致的。一般來講基于狀態(tài)的CRDT，需要傳輸每個副本之間的所有數(shù)據(jù)，對于一些比較大的數(shù)據(jù)集合對傳輸要求是比較高的，所以實際工程實踐中使用比較多的是基于操作的CRDT類型，只需要同步用戶的操作，這種方式對傳輸層的壓力較小。此外，大多數(shù)分布式存儲系統(tǒng)中已經(jīng)記錄了OP log，只需要將這些OP log做一些處理就可以滿足CRDT要求中的冪等性規(guī)則。只需要保證，這些OP log無論以什么次序，進(jìn)行數(shù)據(jù)同步，最終值都是一樣的就可以。

如上圖所示，常見的CRDT類型為以下幾種：

• Register：KV
• Counter：計數(shù)器
• Set：集合

由于篇幅有限，就不詳細(xì)介紹每一種CRDT類型，僅簡單介紹一下Counter類型的CRDT。在多線程編程中，如果想構(gòu)建一個高性能計數(shù)器，常用的手段是設(shè)置每一個線程有一個線程私有變量來各自獨立統(tǒng)計各自線程的計數(shù)器的累加值，最后讀的時候?qū)⑺械木€程進(jìn)行合并，每一個線程的計數(shù)器自增加時都不需要加鎖，效率很高。計數(shù)器類型的CRDT結(jié)構(gòu)也是基于相似的思路，如要在多個地域維護(hù)一個計數(shù)器，每次更新僅在本地域更新，最后讀取的時候再merge到一起。

實際使用過程中需要對這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行各種組合，會更復(fù)雜一些?，F(xiàn)在業(yè)界也有一些CRDT的解決方案或產(chǎn)品，但不能完全滿足我們的需求。

比如RedisLab提供的CRDT版本Redis命令支持較為完整，但這個版本并不開源。其他支持CRDT的產(chǎn)品，很多會將計數(shù)器和register類型分為兩種命令類型來處理，這與Redis原生語義不兼容。Abase2的CRDT方案必須要做到完全兼容Redis語義，同時支持Abase1已經(jīng)支持的Redis命令，讓用戶的使用方式保持一致，不需要改造代碼，就可以使用CRDT版本的服務(wù)，同時要求在SSD下有比較良好的性能。

上圖列舉了一些Abase支持的常見Redis命令， Abase2做到了以上類型的CRDT支持，用戶在各個地域不同的訪問都能做到嚴(yán)格的最終一致，包括String、Hash、Zset、List等結(jié)構(gòu)。

三、Abase2架構(gòu)

多地域部署，需要架構(gòu)上的支持。

上圖展示了Abase2的模塊結(jié)構(gòu)，和大多數(shù)分布式系統(tǒng)的結(jié)構(gòu)類似，這里不作贅述。

上圖展示了Abase2的部署方式，Abase2要支持多地部署，所以邏輯上分了以下幾層：首先是“Global Abase Cluster”，是一個跨地域部署的集群；一個“Cluster”內(nèi)部可以分為多個“Region”，一個“Region”可能有不同的“可用區(qū)域”（“AZ”），一個“AZ”內(nèi)部可能還劃分為不同的“POD”。

比較關(guān)鍵的是Abase2 DataNode結(jié)構(gòu)。

Abase2 DataNode主要分為三層：框架層、一致性協(xié)議層、引擎層。由于Abase2是一個多租戶系統(tǒng)，所以框架層包含一些多租戶QOS調(diào)度的內(nèi)容。在一致性協(xié)議層，Abase2使用了一套自研的類多主同步的一致性協(xié)議同步數(shù)據(jù)。引擎層則分為兩層，一層為log引擎，一層為KV引擎。KV引擎抽象了接口，可以對接不同的LSM、Hash以及遠(yuǎn)程引擎。

如上圖所示，Abase2引擎層結(jié)構(gòu)主要分為三層。除了RecordCache來保證熱點數(shù)據(jù)高性能，還有KV引擎外。相比于一般引擎結(jié)構(gòu)，Abase2還有一個log引擎層，有一些OP操作需要記錄在log中，由于數(shù)據(jù)是多點寫入的、在最終數(shù)據(jù)達(dá)成一致之前是不會記錄到引擎中的。但對于本地域的用戶來說，用戶既然已經(jīng)寫成功了，對本地域來說就需要能夠讀到這部分?jǐn)?shù)據(jù)，故Abase基于OP log提供了查詢功能來滿足用戶的需求。

在CRDT支持中還有一個重要的部分就是用戶的時間戳方案。用戶時間戳需要達(dá)到幾個要求：

第一點要滿足因果關(guān)系，符合用戶意圖。如用戶先寫入A再寫入B，那么寫入B的時間戳要大于A。

第二點則是需要全局唯一不重復(fù)。

Abase實際使用的是混合邏輯時鐘技術(shù)。有些CRDT實踐中使用向量時鐘，向量時鐘既能保證因果關(guān)系，也能在有沖突的時候檢測出來。但是對于Abase2而言，并不需要檢測出沖突并報告給用戶處理，同時向量時鐘隨著副本數(shù)增加還會造成結(jié)構(gòu)膨脹，所以Abase2采用了更“簡單粗暴”的混合邏輯時鐘方案。

混合邏輯時鐘方案能保證在系統(tǒng)內(nèi)發(fā)生的事件有全序關(guān)系，如果事件A先于事件B發(fā)生，那么事件A的混合邏輯時鐘一定小于事件B?；旌线壿嫊r鐘主要由物理時鐘、邏輯時鐘和副本標(biāo)識組成。在具體實踐過程中還有一些工程優(yōu)化手段來保證混合邏輯時鐘不發(fā)生異常。

四、Redis常見命令的CRDT支持

接下來介紹在工程實踐中，如何做到Redis常見命令的CRDT支持。

Redis命令可以大概分為兩類，上圖展示了第一類命令，這類命令是序列無關(guān)的，如String、Set和Hash類型等，雖然命令的類型不同，查詢可能更為復(fù)雜，但這些數(shù)據(jù)的操作和順序無關(guān)。第二類是有序類命令。

1、String類命令

前文中提到，數(shù)據(jù)結(jié)構(gòu)分為三層，包括Cache層、Log引擎層和KV引擎層。所有用戶的更新會先寫入到log引擎層的log中，并為log構(gòu)建索引，以保證大多數(shù)熱的、最新的OP操作都在log中。Cache層也非常重要，為滿足高性能需求，不論遠(yuǎn)方來的OP操作以什么順序提交，需要保證與Cache中結(jié)果的當(dāng)前值進(jìn)行merge，都在Cache中得到及時的更新，而不需要再去查詢引擎。

下圖展示了Cache更新流程的實現(xiàn)：

Cache層是保證在CRDT條件下高性能的關(guān)鍵。如圖所示，除了Cache當(dāng)前的merge value外，用戶基于不同的OP操作，比如set key1=5，然后“+1”、“+1”，最終值是7，在Cache中要緩存7，此外還要存儲額外的信息（操作對應(yīng)的時間等），因為如果只緩存7，假如用戶同步過來一個set命令，這時就會不知道是否應(yīng)該更新緩存。

以case1為例，假設(shè)外界寫入一個時間戳為5的“+1”操作，首先將查詢緩存信息，緩存信息中最近一次的set命令時間戳是2，最近一次修改的時間戳是6，如果有一個時間戳為5的“+1”的操作，則說明這是在最近一次設(shè)置時間戳之后發(fā)生的，就可以直接將內(nèi)存結(jié)果更新為8，就不需要再查詢引擎了。

在正常的讀取流程中，如果沒有命中Cache，將會重新遍歷OpList中的操作記錄，如果遇到set則返回，并將之后的結(jié)果merge起來；如果OP log沒有這一條key的操作記錄，則直接讀取KV引擎中的KV存儲結(jié)果返回給用戶。

如果OP log一直保留，則會不斷增多，不僅浪費存儲空間，也會影響查詢速度。故對OP log也會有定期的GC回收機(jī)制，在這個過程中就使用了混合邏輯時鐘的因果關(guān)系保證，它能保證一旦混合邏輯時鐘時間戳之前的日志完成了同步，那就保證之前日志數(shù)據(jù)不需要了，未來不會再產(chǎn)生時間戳更小的日志。

2、Hash類命令

如下圖，Hash類型的命令與String類型是類似的。

不同之處是在Hash類型中的緩存結(jié)構(gòu)有些差異。

當(dāng)元素個數(shù)較少時，Hash的meta和Hash的field是在一起的，而在元素個數(shù)較多時是分散的。

3、有序類命令

除了上面介紹的無序類型的命令，還有一類Redis命令的CRDT實現(xiàn)是有序類型的。

比如Sorted Set類型命令中元素有一個score，基于score的順序/排名進(jìn)行一些操作。List類型雖然沒有score，但也有頭部和尾部之分，也可以看作是有序結(jié)構(gòu)。

在有序結(jié)構(gòu)下，CRDT會面臨如下問題：舉個例子，比如有一個有序集合（Sorted Set）內(nèi)，副本A上ABC的score分別為1000，2000，3000，副本B上BC的score分別為2000，3000，如果需要刪除score最小的元素，則在副本A上執(zhí)行的操作是刪除A，而在副本B上則會執(zhí)行刪除B的操作，最后導(dǎo)致當(dāng)副本A上的操作同步到副本B時，就會出現(xiàn)數(shù)據(jù)不一致的情況。一種方案是可以保留OP log，并在每次同步到操作時按照時間順序強(qiáng)制回放OP log，但這樣實施起來的代價是非常高的。前文有提到，我們要求所有操作可以直接合并到Cache中，而不需要重新加載log。在具體實踐中，Abase對部分操作進(jìn)行了轉(zhuǎn)化，將“ZremRangeByRank”這種基于序列的操作轉(zhuǎn)換成基于Member的操作，即在副本A執(zhí)行的時候會將操作轉(zhuǎn)換成“Zrem A”并且標(biāo)記操作時間戳，這時當(dāng)操作同步到副本B時，由于副本B沒有“A”，則不會產(chǎn)生刪除元素的操作。

4、后續(xù)優(yōu)化

最后總結(jié)一下Abase2對Redis命令CRDT之處的一些特點和我們的后續(xù)計劃。

特點總結(jié)如下：

• 采用OP-based的CRDT算法，支持了Redis幾乎所有常用結(jié)構(gòu)的異地多活下的數(shù)據(jù)最終一致；
• 充分利用內(nèi)存資源，通過cache有效的提高了熱點數(shù)據(jù)的查詢性能；

目前Abase2正在優(yōu)化的點總結(jié)如下：

對于復(fù)雜數(shù)據(jù)結(jié)構(gòu)的更科學(xué)的 RU（request unit）評估，Abase2是多租戶serverless的云存儲服務(wù)，對用戶的計費和限速都是基于RCU的，對于KV類型的RCU評估業(yè)界有比較通用的做法，但對于復(fù)雜數(shù)據(jù)結(jié)構(gòu)如Zset或List等請求，RCU的評估是不太精準(zhǔn)的，繼而會帶來資源使用、負(fù)載均衡及用戶計費上的不精準(zhǔn)，所以要不斷優(yōu)化更科學(xué)的評估RCU；

• 進(jìn)一步優(yōu)化cache命中率，提升性能；
• 對于cache不命中的場景進(jìn)行進(jìn)一步的優(yōu)化和剪枝，改善長尾延遲。