Abase2's CRDT Support in Multi-Region Deployments

本文将分享Abase2在跨地域部署下的CRDT支持实践。首先将介绍NoSQL数据库在多地域部署下的一些挑战，然后介绍解决多地域部署下冲突问题的CRDT方案，接下来将介绍Abase2为了支撑多地域部署下冲突解决以及CRDT技术而打造的架构，最后将分享具体工程实践的经验。

今天的介绍会围绕下面四点展开：

1. 多地域部署挑战

2. CRDT技术

3. Abase2架构

4. Redis常见命令的CRDT支持

分享嘉宾｜刘健 字节跳动 Abase产品研发负责人

编辑整理｜熊丹妮

出品社区｜DataFun

01. 多地域部署挑战

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级别的时延；一致性问题：由于是外挂系统，在架构设计中没有能够保证100%的数据传输可靠，另一方面多地域写入数据冲突问题更难解决；额外成本：包括同步组件的成本，数据冲突时修复数据时的成本，以及部署两套集群需要额外的副本等。

4. Redis常见命令的CRDT支持

如上图所示，在地域A和地域B各部署了一套Abase服务，初始时X都等于1，在地域A将X值设置为2，在地域B执行删除X的操作。当数据互相同步之后，地域A可能看到X是一个空值，地域B可能看到X的值是2，如果没有其他手段介入，这两个地域的X值就会一直不一致，这种情况对用户是很不友好的。

解决数据冲突问题有如下一些方案：用户侧避免冲突：一种方式是用户只在一个地域写，但这种方式会使得另一个地域跨地域访问的延迟无法满足；另一种方式是用户将key进行一些处理，部分key在某个地域写，部分key在另一个地域写，进行单元化处理，但实际上并不是所有的key都能做到单元化；搭建数据不一致检测和修复系统：搭建一个第三方系统进行数据冲突检测，然后修复，这个方案是可行的，但是代价非常高，时间也非常长；服务侧解决冲突：一种方式是通过向量时间戳等技术将冲突检测出来交给用户处理，这种方式对于一些高级用户可能是ok的，但对于大多数普通用户来说使用成本过高，我们希望能够提供的是一个多地域部署的数据库，用户看到的是同一个Abase集群，在不同地域可以就近访问。用户不需要关心数据同步链路，不需要担心数据最终一致性。所以我们采用了CRDT（无冲突复制数据类型）技术方案，从根本上避免冲突，达到数据的最终一致。

CRDT概念在2011年的一篇论文中正式提出，该论文主要讨论了如果存在多副本同时更新的情况下，满足怎样的条件能让数据达成最终一致。很快，CRDT技术在协同编辑领域得到了广泛应用。现在，在分布式数据库中，特别是NoSQL类型数据库中，如RedisLab，Cosmosdb以及Riak等数据库中目前都提供了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的解决方案或产品，但不能完全满足我们的需求。

Abase2的CRDT方案必须要做到完全兼容Redis语义，同时支持Abase1已经支持的Redis命令，让用户的使用方式保持一致，不需要改造代码，就可以使用CRDT版本的服务，同时要求在SSD下有比较良好的性能。

Abase2的模块结构主要分为三层：框架层、一致性协议层、引擎层。由于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支持。前文提到，数据结构分为三层，包括Cache层、Log引擎层和KV引擎层。所有用户的更新会先写入到log引擎层的log中，并为log构建索引，以保证大多数热的、最新的OP操作都在log中。Cache层也非常重要，为满足高性能需求，不论远方来的OP操作以什么顺序提交，需要保证与Cache中结果的当前值进行merge，都在Cache中得到及时的更新，而不需要再去查询引擎。

下图展示了Cache更新流程的实现：以case1为例，假设外界写入一个时间戳为5的“+1”操作，首先将查询缓存信息，缓存信息中最近一次的set命令时间戳是2，最近一次修改的时间戳是6，如果有一个时间戳为5的“+1”的操作，则说明这是在最近一次设置时间戳之后发生的，就可以直接将内存结果更新为8，就不需要再查询引擎了。

在正常的读取流程中，如果没有命中Cache，将会重新遍历OpList中的操作记录，如果遇到set则返回，并将之后的结果merge起来；如果OP log没有这一条key的操作记录，则直接读取KV引擎中的KV存储结果返回给用户。

如果OP log一直保留，则会不断增多，不仅浪费存储空间，也会影响查询速度。故对OP log也会有定期的GC回收机制，在这个过程中就使用了混合逻辑时钟的因果关系保证，它能保证一旦混合逻辑时钟时间戳之前的日志完成了同步，那就保证之前日志数据不需要了，未来不会再产生时间戳更小的日志。

对于有序结构，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”，则不会产生删除元素的操作。

最后总结一下Abase2对Redis命令CRDT之处的一些特点和我们的后续计划：特点总结如下：采用OP-based的CRDT算法，支持了Redis几乎所有常用结构的异地多活下的数据最终一致；充分利用内存资源，通过cache有效的提高了热点数据的查询性能；对于复杂数据结构的更科学的RU评估，继而会带来资源使用、负载均衡及用户计费上的不精准，所以要不断优化更科学的评估RCU；进一步优化cache命中率，提升性能；对于cache不命中的场景进行进一步的优化和剪枝，改善长尾延迟。