随着服务规模的扩大, 为了提升系统的容灾能力以及性能的要求, 会将服务部署在多个地域, 如果服务是有状态的, 比如redis/mysql等, 就需要在多地域之间进行数据同步, 如何保证数据一致性, 就成为了实现"多活"的关键. 以redis为例, 业内已经有redislab和阿里云实现了多活, 并且都是使用的一种叫CRDT的解决方案, 所以, 本文以CRDT的论文为基础, 介绍一下CRDT的理解, 有问题欢迎指正.

1. CRDT: 无冲突复制数据类型

   1. 解决多主架构中, 数据复制时的最终一致性问题

   2. 使用这类数据结构, 需要满足以下三个条件(比如: INCR命令满足交换律, 结合律, 但是不满足幂等)

      1. 交换律: x⊔y=y⊔x

      2. 幂等律: x⊔x=x

      3. 结合律: (x⊔y)⊔z=x⊔(y⊔z)

2. 分类

   1. 基于操作的(CmRT), 比如incr decr等

   2. 基于状态的(CvRT), 就是传输的是最终值, 比如restore

3. 数据类型

   1. Op-based counter

      2. 解释: 基于操作实现, 每个下游需要同步相同的操作, 查询时直接查询本地即可
      3. 说明: 适合类似INCR/DECR等命令, 但是需要确保幂等性

   2. G-Counter

      2. 解释: 基于状态进行复制, 合并的时候: 取两个时间点中值更大的, 查询的时候: 取各地域求和的值

      3. 说明: 只能增加, 因为如果有删除操作, 在max的运算下, 会被认为数据是老数据而丢弃

   3. PN-Counter

      2. 解释: 基于状态进行复制, 聚合时取两个时间点中最大的, 查询的时候: 取各地域求INCR和的值 - 各地域求DECR和的值

      3. 说明: 支持增加和减少, 而且由于是基于状态的, 幂等性也有保证

   4. Non-negative Counter

      1. 解释: 非负数的counter, 很遗憾, 没有给出实现

   5. LWW-Register

      3. 解释: 基于状态进行复制, 每个元素在生成时同时添加一个时间戳, 之后按取时间戳大的为标准进行聚合, 查询时取当前本地域的值

      4. 说明: 有两点限制, 一个是需要保障时间戳全局唯一,有序,一致, 另外需要保证状态不太大, 否则网络传输成本较高

      6. 解释: 基于操作进行复制, 每个地域执行update的时候, 会记录时间戳, 之后同步给其他地域, 其他地域判断时间戳是否大于本地的, 如果是的话, 就进行更新

      7. 说明: 可以用于SET,HSET这类幂等类型的操作, 同时需要保证时间戳的全局一致

   6. MV-Register

      3. 解释: 基于状态的, 带版本的更新, 元素变更, 就增加版本号, 实际的合并交给业务完成

   7. G-SET

      2. 解释: 一种只增加元素的set集合
      3. 点评: 只支持增加

   8. 2P-SET

      2. 解释: 基于状态, 由一个增加元素的set和一个删除元素的set组成, 查询时, 通过判断e是否属于A同时也不属于R来确认
      3. 说明: 删除的数据, 后续无法再次添加

   9. U-SET

      2. 解释: 基于操作的, 元素唯一的set类型, 如果保证add一定会在remove之前触发, 这样remove-set就可以不用了
      3. 说明: 元素必须唯一, 和基于状态的2P-SET类似, 但是更加严格

   10. LWW-Element-Set

       2. 解释: 一个元素会认为存在, 如果它在add set, 但是不在remove set, 或者它在add set的时间戳大于remove set中所有的时间戳

       3. 说明: 相比2P-SET的好处是可以添加已经删除的元素, 但是问题在于如何保证时间戳的全局有序性

   11. PN-Set(PositiveNegative-Set)

       2. 解释: 在Set中使用一个计数器, 每次添加就计数加1, 删除就计数减1, 如果计数大于0, 说明数据存在
       3. 说明: 这个的问题是如果删除了多次, add可能失效

   12. OR-Set (Observed-Remove Set)

       3. 解释: 基于操作, 2P-Set的变种, 把唯一性做到Set里了, 每次add 元素产生一个唯一tag, 每个地域rmv的时候, 只rmv本地所有的与元素相关的tag集合, 传播时会带上元素及对应tag, 下游接收到之后, 需要确认每个remove(e, u) 都已经add过了. 

       4. 说明: 元素带上唯一tag, 这样数据是不冲突了, 但是会导致和实际的操作不符合, 如图中所示, 期望应该是a查询不到的. 

4. 其他说明:

   1. 由于文中有说到很多数据类型都依赖全局的时间戳, 感兴趣的可以了解一下谷歌的原子钟

5. 参考文档: 

   1. CRDT tech report: https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf
   2. CRDT: https://hal.inria.fr/inria-00609399/document
   3. redislabs, Developing Applications with Geo-replicated CRDBs on Redis Enterprise Software(RS): https://redislabs.com/redis-enterprise-documentation/developing/crdbs/
   4. CRDT——解决最终一致问题的利器: https://yq.aliyun.com/articles/635632?utm_content=m_1000015503
   5. 谷歌利用GPS和原子钟使数据库全球范围信息同步: https://m.ithome.com/html/25938.htm