阿裡雲redis CRDT産品支援說明

CRDT支援概述

CRDT天然支援redis的幾種資料結構，下表給出一個簡單映射：

redis資料結構	CRDT資料結構
string(int或double類型編碼)	counter
string	register
set
基本kv	set + register
hash
zset
GEO
hyperloglog

然而對于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，計數器(counter)，位操作(bit)三類指令進行讨論

• 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。

• 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

• 暫不保證

• 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

• CRDT典型使用場景: 使用者，網站或應用的全局session資訊
• 保證指令集4：

  HSET

  HMSET

  HSETNX

  HDEL

  • 實作方式: OR-Set
• 保證指令集5：

  HINCRBY

  • 實作方式：op-based

    > 同理, HSET或HDEL和HINCRBY在不同執行個體上同時操作不能保證最終一緻
               

• HINCRBYFLOAT

  同樣會存在浮點數精度差異

list

• 暫不支援

• CRDT典型使用場景：統計全局的近似uv
• 保證指令集6：

  PFADD

• PFMERGE

• hll在redis中儲存為string類型的對象, 是以原則上string類型的所有操作均可作用于hll之上, 但不建議對hll使用string類型的操作, 不僅保證不了最終一緻, 還會破壞hll本身的正确性

• CRDT典型使用場景：使用者帶有時間序列資訊, 如timeline
• 保證指令集7：

  ZADD NX|XX|CH

  ZREM
• 保證指令集8：

  ZADD INCR

  ZINCRBY

• ZINTERSTORE

  ZUNIONSTORE

  ZREMRANGEBYRANK

  ZREMRANGEBYSCORE

  ZREMRANGEBYLEX

geo

• CRDT典型使用場景：全局地理位置資訊
• 保證指令集9：

  GEOADD
• 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元資訊，但保證相容性