ふわふわ時間

0%

CRDTs in Redis

Redis 全球多活调研笔记。


CRDT 简单介绍

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

  • CvRDT(State-based Convergent Replicated Data Type): 基于状态聚合复制数据类型
    • 状态更改操作为 Merge,要求 Merge 满足交换律,结合律,幂等
    • 状态满足单调性
    • 优点:对通信协议要求不高,最终可达即可
    • 缺点:消息传递的内容是状态,消息体大
  • CmRDT(Op-based Commutative Replicated Data Type):基于操作交换复制数据类型
    • Update 操作要么可确定明确的因果顺序,要么满足可交换
    • 优点:消息传递的内容是操作,消息体小
    • 缺点:对通信协议要求高,需要保证因果顺序

RedisLabs CRDB 相关

参考资料

目前 CRDB 支持的数据类型

Data Type Support Level
Float Counters Supported
Geospatial Supported
Hashes Supported; Hash fields are treated as strings or counters
Integer Counters Supported
Lists Supported
Sets Supported
Strings Supported
Sorted Sets Supported
HyperLogLog Supported
Streams Supported
Bitsets Not currently supported

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

String

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

Type Support Methods
Counter INCR, DECR, INCRBY, DECRBY, GET
Pure String APPEND, GET, GETRANGE, GETSET, MGET, MSET, MSETNX, PSETEX, SET, SETEX, SETNX, SETRANGE, STRLEN
  • Counter:参考 PN-Counter 实现
  • Pure String:采用 wall-clock timestamp 和 Last Write Wins (LWW)

Set

参考 OR-Set 实现

Hash

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

Sorted Set

List

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