一、多地域部署挑戰

1、Abase簡介

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

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

2、多地域部署需求

再來看一下為什么數據庫需要多地域部署。

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

3、Abase架構演進

Abase多地域部署的架構也經歷了一個演進過程。

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

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

• 同步延遲：由于跨越多個組件，所以同步延遲較長，無法提供RPC級別的時延。如多地域的網絡延時可能是50ms，但是數據同步延遲可能到達秒級別以上。
• 一致性問題：由于是外掛系統，在架構設計中沒有能夠保證100%的數據傳輸可靠，另一方面多地域寫入數據沖突問題更難解決。
• 額外成本：包括同步組件的成本，數據沖突時修復數據時的成本，以及部署兩套集群需要額外的副本等。

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

解決數據沖突問題有如下一些方案：

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

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

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

二、CRDT技術

下面將對CRDT技術進行簡單介紹。

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

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

CRDT分為兩種形式：一種為基于狀態，一種為基于操作。無論是基于狀態還是基于操作，CRDT的結構設計都需要滿足以下幾個數學特性：

• 交換律
• 結合律
• 冪等性

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

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

• Register：KV
• Counter：計數器
• Set：集合

由于篇幅有限，就不詳細介紹每一種CRDT類型，僅簡單介紹一下Counter類型的CRDT。在多線程編程中，如果想構建一個高性能計數器，常用的手段是設置每一個線程有一個線程私有變量來各自獨立統計各自線程的計數器的累加值，最后讀的時候將所有的線程進行合并，每一個線程的計數器自增加時都不需要加鎖，效率很高。計數器類型的CRDT結構也是基于相似的思路，如要在多個地域維護一個計數器，每次更新僅在本地域更新，最后讀取的時候再merge到一起。

實際使用過程中需要對這些數據結構進行各種組合，會更復雜一些。現在業界也有一些CRDT的解決方案或產品，但不能完全滿足我們的需求。

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

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

三、Abase2架構

多地域部署，需要架構上的支持。

上圖展示了Abase2的模塊結構，和大多數分布式系統的結構類似，這里不作贅述。

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

比較關鍵的是Abase2 DataNode結構。

Abase2 DataNode主要分為三層：框架層、一致性協議層、引擎層。由于Abase2是一個多租戶系統，所以框架層包含一些多租戶QOS調度的內容。在一致性協議層，Abase2使用了一套自研的類多主同步的一致性協議同步數據。引擎層則分為兩層，一層為log引擎，一層為KV引擎。KV引擎抽象了接口，可以對接不同的LSM、Hash以及遠程引擎。

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

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

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

第二點則是需要全局唯一不重復。

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

混合邏輯時鐘方案能保證在系統內發生的事件有全序關系，如果事件A先于事件B發生，那么事件A的混合邏輯時鐘一定小于事件B。混合邏輯時鐘主要由物理時鐘、邏輯時鐘和副本標識組成。在具體實踐過程中還有一些工程優化手段來保證混合邏輯時鐘不發生異常。

四、Redis常見命令的CRDT支持

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

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

1、String類命令

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

下圖展示了Cache更新流程的實現：

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

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

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

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

2、Hash類命令

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

不同之處是在Hash類型中的緩存結構有些差異。

當元素個數較少時，Hash的meta和Hash的field是在一起的，而在元素個數較多時是分散的。

3、有序類命令

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

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

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

4、后續優化

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

特點總結如下：

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

目前Abase2正在優化的點總結如下：

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

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