您现在的位置是：首页 > 文章详情

redis异地多活理论基础之CRDT

日期：2019-04-16点击：1267收藏

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

CRDT: 无冲突复制数据类型
1. 解决多主架构中, 数据复制时的最终一致性问题
2. 使用这类数据结构, 需要满足以下三个条件(比如: INCR命令满足交换律, 结合律, 但是不满足幂等)
  1. 交换律: x⊔y=y⊔x
  2. 幂等律: x⊔x=x
  3. 结合律: (x⊔y)⊔z=x⊔(y⊔z)
分类
1. 基于操作的(CmRT), 比如incr decr等
2. 基于状态的(CvRT), 就是传输的是最终值, 比如restore
数据类型
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查询不到的.
其他说明:
1. 由于文中有说到很多数据类型都依赖全局的时间戳, 感兴趣的可以了解一下谷歌的原子钟
参考文档:
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