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

1、Abase簡(jiǎn)介

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

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

2、多地域部署需求

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

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

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

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

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

但這個(gè)方案存在以下幾個(gè)問(wèn)題：

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

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

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

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

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

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

二、CRDT技術(shù)

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

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

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

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

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

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

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

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

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

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

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

上圖列舉了一些Abase支持的常見Redis命令， Abase2做到了以上類型的CRDT支持，用戶在各個(gè)地域不同的訪問(wèn)都能做到嚴(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”，是一個(gè)跨地域部署的集群；一個(gè)“Cluster”內(nèi)部可以分為多個(gè)“Region”，一個(gè)“Region”可能有不同的“可用區(qū)域”（“AZ”），一個(gè)“AZ”內(nèi)部可能還劃分為不同的“POD”。

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

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

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

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

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

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

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

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

四、Redis常見命令的CRDT支持

接下來(lái)介紹在工程實(shí)踐中，如何做到Redis常見命令的CRDT支持。

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

1、String類命令

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

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

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

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

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

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

2、Hash類命令

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

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

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

3、有序類命令

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

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

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

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

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

特點(diǎn)總結(jié)如下：

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

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

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

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