阿里云redis CRDT产品支持说明

CRDT支持概述

CRDT天然支持redis的几种数据结构，下表给出一个简单映射：

然而对于redis来说，同一数据类型可能既存在CRDT中register的SET操作，又存在CRDT中counter的INCR操作。所以设计上我们考虑根据同一数据类型的不同命令划分命令集，不同命令集CRDT的实现方式不同。

CRDT支持原则

• 目前仅支持redis 4.0版本
• 所有CRDT操作均针对写(update)而言，所有的读(query)逻辑均保持不变

• 对同一key或同一field同时进行同一命令集内的操作才能保证key或field最终一致

  • 对同一个key同时进行不同数据类型的操作不保证最终一致

    > 例如实例A上做SET key value，实例B上做SADD key a b，无法保证最终一致
    

  • 对同一个key同时进行同一数据类型不同命令集内的操作不保证最终一致

    > 例如实例A上做SET key 1，实例B上做INCR key 2，同步之后A的key为2，B的key为1，无法保证最终一致
    

  • 除了string类型, 对其它类型的key做DEL不做最终一致保证

    > 例如实例A上做DEL setkey，实例B上SADD setkey a b，无法保证最终一致
    

CRDT算法选择

• 若命令集内所有命令间均具备交换律、结合律的，直接回放操作(op-based CRDT)
• 若命令集对应的数据类型是set，使用基于时间戳做tag的OR-Set策略
• 其它情况使用LWW(Last write wins)策略

CRDT命令集

string

分为string，计数器(counter)，位操作(bit)三类命令进行讨论

string

• CRDT典型使用场景：基础数据类型, 应用广泛

• 保证命令集1： SET族 MSET MSETNX PSETEX GETSET DEL

  • 实现方式：LWW

    > 实例A上SET key a，然后在实例B上SET key b，同步之后以最新的操作为准，A和B上key均为b。
    > 实例A上SET key a，然后在实例B上SET key b；DEL key，同步之后以最新的操作为准，A和B上key均不存在。
    

• 暂不保证： MOVE RENAME

  实例A上SET key a，同时实例B上MOVE key keyext，同步之后A上有keyext，B上有keyext和key。

• 暂不保证： SETRANGE APPEND

  实例A进行APPEND key hello，同时实例B进行APPEND key world，最终在实例A和B上key的值可能分别为helloworld和worldhello。

counter

• CRDT典型使用场景：计算全局pv, 转发数, 点赞数等

• 保证命令集2: INCR DECR INCRBY DECRBY [INCRBYFLOAT]

  • 实现方式: op-based

    > 实例A上INCR k, 同时实例B上INCR k, 同步之后A和B上的k值均为2
    

• 不保证：DEL SET

  在实例A上执行INCR k, 同时在实例B上执行SET k 2, 最终结果可能是A上k的值为2, B上k的值为3
  在实例A上执行INCR k, 同时在实例B上执行DEL k, 最终结果可能是A上k不存在, B上k的值为1

• INCRBYFLOAT 会存在浮点数计算本身的精度差异

bit

• 暂不保证

set

• CRDT典型使用场景: 购物车，收藏夹

• 保证命令集3： SADD SREM SPOP

  • 实现方式：OR-Set

    > 实例A上SADD key a, 同时实例B上SADD key b, 同步之后A和B上key均有a, b两个fields
    

• 暂不保证：SMOVE SINTERSTORE SUNIONSTORE SDIFFSTORE

hash

• CRDT典型使用场景: 用户，网站或应用的全局session信息

• 保证命令集4：HSET HMSET HSETNX HDEL

  • 实现方式: OR-Set

• 保证命令集5：HINCRBY

  • 实现方式：op-based

    > 同理, HSET或HDEL和HINCRBY在不同实例上同时操作不能保证最终一致
    

• HINCRBYFLOAT 同样会存在浮点数精度差异

list

• 暂不支持

hyperloglog

• CRDT典型使用场景：统计全局的近似uv

• 保证命令集6：PFADD

  • 实现方式：op-based
• 暂不保证：PFMERGE
• hll在redis中保存为string类型的对象, 所以原则上string类型的所有操作均可作用于hll之上, 但不建议对hll使用string类型的操作, 不仅保证不了最终一致, 还会破坏hll本身的正确性

zset

• CRDT典型使用场景：用户带有时间序列信息, 如timeline

• 保证命令集7：ZADD NX|XX|CH ZREM

  • 实现方式：OR-Set

• 保证命令集8：ZADD INCR ZINCRBY

  • 实现方式：op-based
• 暂不保证：ZINTERSTORE ZUNIONSTORE ZREMRANGEBYRANK ZREMRANGEBYSCORE ZREMRANGEBYLEX

geo

• CRDT典型使用场景：全局地理位置信息

• 保证命令集9：GEOADD

  • 实现方式：OR-Set
• geo类型数据底层在redis中使用zset实现，所以原则上zset类型的所有操作均可作用于geo之上，但不建议对geo使用zset类型操作

其它redis特性支持

rdb

• 在rdb中保存crdt相关元信息，保证下次加载之后满足一致性，同时对开源redis 4.0及阿里云redis 4.0其它产品形态保持兼容

expire

• 对于expire的时间设置不保证最终一致，原则上以设置的最短过期时间为准，会分发DEL操作。

evict

• 内存处于高水位的特殊情况，直接根据具体设置策略逐出，目前不做最终一致保证

lua

• 支持lua脚本中执行的命令

实现代价

• 性能上无影响
• 每个key或field将多占用8个字节存储crdt相关元信息，未来可以压缩到4个字节
• set和hash类型只支持 OBJ_ENCODING_HT 编码，zset类型只支持 OBJ_ENCODING_SKIPLIST 编码，以下几个配置项将不再起作用：
  set_max_intset_entries

hash_max_ziplist_entries hash_max_ziplist_value
zset_max_ziplist_entries zset_max_ziplist_value

• rdb将额外占用空间存储crdt元信息，但保证兼容性