CRDTs in Redis

Redis 全球多活调研笔记。

1. CRDT 简单介绍

在 Conflict-free Replicated Data Types 一文中，作者依据传递消息内容的区别，提出了两种 CRDT：

• CvRDT(State-based Convergent Replicated Data Type): 基于状态的聚合复制数据类型

  • 条件：
    • 状态满足单调性，消息最终可达
    • 状态更改操作为 Merge 需满足交换律，结合律，幂等
  • 优点：对通信协议要求不高
  • 缺点：消息传递的内容是状态，消息体大

• CmRDT(Op-based Commutative Replicated Data Type)：基于操作的交换复制数据类型

  • 条件：
    • Update 操作要么可确定明确的因果顺序，要么满足可交换
    • 消息传输提供 exactly once 的保证 (幂等)
  • 优点：消息传递的内容是操作，消息体小
  • 缺点：对通信协议要求高

2. RedisLabs CRDB 相关

参考资料

• Active-Active Geo-Distribution (CRDT-Based)
• RedisConf18 - CRDTs and Redis - From sequential to concurrent executions
• Developing Applications with Geo-Distributed CRDBs on Redis Enterprise Software (RS)

目前 CRDB 支持的数据类型

目前可查询到有关 CRDB 实现的情报如下所述。

2.1. String

在 CRDB 中，String 分为 Counter 和 Pure String 两种类型，这两种类型之间不可动态转换。下表给出了其各自支持的操作，可以看到 Counter 和 Pure String 都不支持位操作。

• Counter：参考 PN-Counter 实现
• Pure String：采用 wall-clock timestamp 和 Last Write Wins (LWW)

2.2. Set

参考 OR-Set 实现

2.3. Hash

• 在 Key 维度参考 OR-Set 实现
• 在 Field 维度实现同 String 类型，分为 Counter 和 Pure String

2.4. Sorted Set

• 在 Key 维度参考 OR-Set 实现
• 在 Member 维度参考 PN-Counter 实现

2.5. List

尚未发现确切的情报，可能有参考 Specification and Complexity of Collaborative Text Editing。