string、hash 最多个 2^32 个 key。每个 key 最大 512MB，value 最大 512MB。
list、set、zset 最多 2^32 个元素。

1 string

1.1 使用场景

1.1.1 选举

  1. 节点抢占 leaderKey SET leaderKey hostId NX EX 30
  2. 节点每20秒查询一次 GET leaderKey

  3. 如果自己是 master，做一次续约 EXPIRE leaderKey 30

    1.1.2 分布式锁

    分布式锁

    1.1.3 分布式ID

    可以使用 INCR 每次自增1，但这样发号，客户端要请求一次 Redis，影响性能。
    推荐号段生成：

  4. INCRBY 步长，如果 key 不存在，从 0 开始自增；如果 key 存在，返回自增后的数值。

  5. 客户端分配号段 [结果 - 步长, 结果)

    1.2 数据结构

    简单动态字符串，Simple Dynamic String 有 free、len 两个字段:
    len 的作用：

  6. 二进制安全。不同于 c字符串通过 ‘\0’ 判断字符串长度，SDS 通过 len 记录长度
    free 的作用：

  7. 空间预分配。当进行 concat 等扩展操作时，SDS 会预留 free 空间，避免连续扩展带来的内存分配消耗
  8. 惰性释放空间。当进行字符串缩减操作时候，SDS 并不会马上收回空间，避免后续有扩展操作带来内存分配消耗

2 hash

2.1 使用场景

2.2.1 统计 PV、UV

  1. 用户110 访问 index.html HINCRBY index.html0527 110 1
  2. 用户110 再次访问 index.html HINCRBY index.html0527 110 1
  3. 查询 index.html 5月27日 PV HGETALL index.html0527，然后算总和（不建议，HGETALL 时间复杂度 O(n)，会阻塞主线程）

  4. 查询 index.html 5月27日 UV HLEN index.html0527

    2.2.2 统计 UV（BitMap）

  5. 用户110 访问 index.html SETBIT index.html0527 110 1

  6. 用户233 访问 index.html SETBIT index.html0527 233 1

  7. 查询 index.html 5月27日 UV BITCOUNT index.html0527

    2.2.3 统计 UV（HyperLogLog）

  8. 用户 110、233 访问 index.html PFADD index.html0527 110 233

  9. 查询 index.html 5月27日 UV PFCOUNT index.html0527

2.2 数据结构

dict 哈希表，元素数量多于64 使用。链地址法

3 set

3.1 使用场景

3.1.2 共同关注

  1. 用户110 关注用户996 SADD follow110 996
  2. 用户110、233 的共同关注 SUNION follow110 follow233

    3.2 数据结构

    dict 哈希表，元素数量多于64 使用。value 存储 null

4 list

4.1 使用场景

4.1.2 限流（令牌桶）

  1. 固定速率生成令牌 LEFTPUSH limit UUID
  2. 达到上限，停止生成令牌 LLEN limit
  3. 消耗令牌 RIGHTPOP limit

    4.2 数据结构

    quicklist 双向链表，每一个节点都是 ziplist

5 zset

5.1 使用场景

5.1.1 限流（滑动窗口）

  1. 用户110 请求进来 ZADD limit110 UUID cur_time
  2. 时间范围内的请求 ZRANGEBYSCORE limit110 cur_time - interval cur_time

  3. 删除历史请求记录 ZREMRANGEBYSCORE limit110 0 cur_time - interval

    5.1.2 排行榜

  4. 用户110 获得 99分 ZADD board 99 110

  5. 查询前100名高分用户 ZREVRANGE board 0 99

  6. 查询用户110的排名 ZRANK board 110

    5.1.3 延时队列

  7. 按任务时间戳升序 ZADD delay timpestamp A

  8. while 检查第一个元素 ZRANGE delay 0 0
  9. 比较时间戳，如果能执行，就删除第一个元素 ZREM delay A

    5.2 数据结构

    dict 哈希表，key 是 member，value 是 score。
    zskiplist 跳表。0层存储完整数据，随机建新层，最高32层就可以容纳 2^64 个元素。
    对比红黑树：
命令 红黑树 跳表 说明
ZADD O(logN) O(logN) 并发环境，跳表需要锁定的粒度更少
ZSCORE O(1) O(1) 引入 dict
ZRANK O(logN) O(logN) 复杂度一样，跳表实现更简单
ZRANGE O(N) O(logN+k) 跳表更高效

6 压缩数据结构

intset 当 set 元素数量少于64 使用
zipmap 当 hash 元素数量少于64 使用
ziplist 当 zset 元素数量少于64 使用。list 的节点就是 ziplist

参考文献