本地煮鸡:8080

# 数据结构

Redis 包含五个数据结构。分别是 String, List, Hash, Set 和 Sorted Set. 除了 String 以外，其他四种是集合类型，因为它们一个键对应一个集合的数据。

# 全局哈希表

在 Redis 中，为了组织所有的键值对，它维护了两张全局哈希表。
哈希表是一个数组，每个元素称为一个哈希桶，哈希桶中不保存元素本身，而保存指向具体 entry 的指针。每一个 entry 由键值对构成，可以通过指针被访问到。
利用了这样的全局哈希表，就可以在 O(1) 的时间复杂度中找到键值对。

全局哈希表

# 哈希冲突

但是随着数据变多，因为哈希冲突和 rehash, 可能会带来操作阻塞。
当发生哈希冲突时，Redis 采用链式哈希的操作来解决冲突。同一个哈希桶用链表的形式保存多个元素。

当数据逐渐增加，链表会导致性能下降时，它会通过 rehash 启用第二张全局哈希表。rehash 过程为：

  • 给第二张全局哈希表分配空间，大小是第一张的两倍
  • 将第一张全局哈希表中的数据重新映射到第二张中
  • 释放第一张全局哈希表的空间

为了避免第二步中数据映射可能带来的巨大开销，Redis 的 rehash 过程是渐进式的。即在映射过程中，Redis 仍然正常处理客户端请求。每处理一个请求，就通过键找到对应的第一张全局哈希表中的哈希桶位置，并将其所有 entry 都拷贝到第二张全局哈希表中。
通过这样的操作分摊了一次高开销的操作，并且保证了数据的快速访问。

# 内置数据结构与底层实现

# 内置数据结构

  • String
    • 底层实现：简单动态字符串
  • List
    • 底层实现：压缩列表；双向链表
  • Hash
    • 底层实现：压缩列表；哈希表
  • Set
    • 底层实现：整数数组；哈希表
  • Sorted Set (ZSet)
    • 底层实现：压缩列表；跳表

# 底层实现

  • 压缩列表
    • 类似数组，每一个位置保存一个数据。
    • 表头有三个字段：zlbytes, 列表长度； zltail, 列表尾偏移量；zllen, 列表 entry 个数.
    • 表尾有一个字段：zlend, 列表结束。
    • 当查找第一个和最后一个元素时，利用表头三个字段直接定位，时间复杂度 O(1)
    • 当查找其他元素时，时间复杂度 O(n)
  • 跳表
    • 在链表的基础上，增加了多级索引。通过索引位置进行跳转来快速定位。
    • 时间复杂度为 O(logN)

# 操作的时间复杂度

  • 单元素操作
    对单个元素的操作
    • O(1)
      • Hash: HGET, HSET, HDEL
      • Set: SADD, SREM, SRANDMEMBER
  • 范围操作
    对集合遍历操作，时间复杂度为 O(n). 但在 Redis 2.8 提供的 SCAN 操作下采用渐进式遍历，可以避免阻塞。
    • O(n)
      • Hash: HGETALL
      • Set: SMEMBERS
      • List: LRANGE
      • Sorted Set: ZRANGE
  • 统计操作
    • 统计集合中元素个数，时间复杂度为 O(1). 例如：LLEN, SCARD
  • 例外情况
    • 利用压缩列表和双向列表的头尾偏移量的操作时间复杂度都为 O(1). 例如：LPOP, RPOP, LPUSH, RPUSH

← 持久化 →