Abase2: NoSQL数据库中的CRDT支持实践
今天的介绍会围绕下面四点展开：
1. 多地域部署挑战
2. CRDT技术
3. Abase2架构
4. Redis常见命令的CRDT支持出品社区｜DataFun
多地域部署挑战
首先简单了解一下Abase在字节跳动公司（以下简称字节）的使用情况。
Abase是字节跳动规模最大的NoSQL数据库之一，峰值QPS达到了百亿级别，管理的数据存储容量达到了EB级别，服务了字节跳动大多数产品线。Abase支持Redis协议/Thrift协议/批量导入等接入方式。用户最常使用的接入方式为Redis协议，本次的分享主要围绕Redis协议的CRDT支持来介绍。
再来看一下为什么数据库需要多地域部署。
就近访问：用户和服务本身就是多地域部署的场景，服务有就近访问需求；需要做到本地访问的地延迟。
容灾需求：相比于同地域内部多可用区域容灾，多地域部署能够提供更高的容灾能力；
资源问题：当某个地域没有足够资源，只能在其他地域部署；
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类型等，虽然命令的类型不同，查询可能更为复杂，但这些数据的操作和顺序无关。第二类是有序类命令。
前文中提到，数据结构分为三层，包括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回收机制，在这个过程中就使用了混合逻辑时钟的因果关系保证，它能保证一旦混合逻辑时钟时间戳之前的日志完成了同步，那就保证之前日志数据不需要了，未来不会再产生时间戳更小的日志。
如下图，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”，则不会产生删除元素的操作。
最后总结一下Abase2对Redis命令CRDT之处的一些特点和我们的后续计划。
特点总结如下：
采用OP-based的CRDT算法，支持了Redis几乎所有常用结构的异地多活下的数据最终一致；
充分利用内存资源，通过cache有效的提高了热点数据的查询性能；
目前Abase2正在优化的点总结如下：
对于复杂数据结构的更科学的 RU（request unit）评估，Abase2是多租户serverless的云存储服务，对用户的计费和限速都是基于RCU的，对于KV类型的RCU评估业界有比较通用的做法，但对于复杂数据结构如Zset或List等请求，RCU的评估是不太精准的，继而会带来资源使用、负载均衡及用户计费上的不精准，所以要不断优化更科学的评估RCU；
进一步优化cache命中率，提升性能；
对于cache不命中的场景进行进一步的优化和剪枝，改善长尾延迟。
以上就是本次分享的内容，谢谢大家。
分享嘉宾
INTRODUCTION
刘健
字节跳动
Abase产品研发负责人
字节跳动Abase产品研发负责人，在分布式存储领域拥有10年技术经验。曾在百度参与Mola，Aries等存储系统的研发工作。当前主要关注超大规模的NoSQL数据库在稳定性、成本、数据生态、多地域支持等方向的工作。
峰会推荐
往期推荐