Redis 具有如下特点：

• KV 键值对。
• 支持丰富的数据类型。
• 内存数据库，读写效率非常高。（写 8万/s, 读 11万/s）。
• 支持持久化。
• 使用io多路复用（epoll）保证高并发。
• 业务逻辑是单线程的；但是 IO 序列化反序列化从 6.0 版本开始是多线程的。
• 可以使用主从模式，哨兵模式或者集群模式 保证高可用。

数据结构&&算法

Redis 以 hash 表存储键值对。使用拉链法解决 hash 冲突。拉链法的示例代码如下图

N = 100010

class HashTable:
    """拉链法实现哈希表"""
    def __init__(self):
        self.h = [-1] * N
        self.idx = 0
        self.e = [0] * N
        self.ne = [0] * N
        self.MOD = N
    
    def query(self, x):
        curr = self.h[x % self.MOD]    
        while curr != -1:
            if self.e[curr] == x:
                return True
            curr = self.ne[curr]
        return False
    
    def add(self, x):
        self.e[self.idx] = x
        self.ne[self.idx] = self.h[x % self.MOD]
        self.h[x % self.MOD] = self.idx
        self.idx += 1

hash_table = HashTable()
n = int(input())
for _ in range(n):
    arr = input().split()
    if arr[0] == 'I':
        hash_table.add(int(arr[1]))
    if arr[0] == 'Q':
        if hash_table.query(int(arr[1])):
            print("Yes")
        else:
            print("No")

渐进式 Hash:

• Redis 是单线程的，为了不阻塞业务线程， Redis 使用 渐进式 Hash 的方法，扩缩容。

编码:

• Redis 为了最大限度的节省内存，对同一个类型的值也会使用多种编码。总得来说，当值较小时，会节省内存优先（比如会使用压缩格式），当值较大后，就会查询效率优先（比如不再使用压缩格式）。
• 查询当前值编码格式的命令为： object encoding mykey

string

• 二进制安全：允许字符串中包含 \0。

hash

• 使用 hash表 实现，使用拉链法解决 hash 冲突。

list

• 压缩列表/ZipList
• 双端列表。两头都可以插入，两头都可以取走元素。

set

• 整数集合/intset：从小到大保存整数的数组。查找(二分查找)的时间复杂度时 O(logN)。

zset

• 跳表/SkipList： 跳表增删查操作的期望时间复杂度是 O(logN)，空间复杂度为 N。参考 设计跳表 理解跳表的实现，在 Redis 中每一层是双向链表，这道LC题，每一层使用单链表也可以搞定。跳表是一种随机算法，新添加节点的层数是根据随机函数确定的。
• 压缩列表/ZipList: 压缩列表增，删，查的时间复杂度是 O(N)，空间占用因为使用了定制的格式做压缩，所以占用较小。
• 当有序集合中元素个数很少，元素体积不大的时候，redis 使用 压缩列表/ZipList 实现 zset；当元素个数较大，元素体积较大时，使用 跳表/SkipList 实现。redis 使用 zset-max-ziplist-entries, zset-max-ziplist-value 来判断还能不能使用 ziplist。可以这样理解，数量太少时，随机函数不够随机，性能波动太大。

hyperloglog

• 用于解决基数（不重复元素个数）统计问题

• 算法是基于概率统计的估计算法，有误差。Redis 误差为 0.81%

• 空间复杂度为 (O(m * loglogN))，空间复杂度极低。在 Redis 中使用稀疏存储结构和密集存储结构保存，最多占用12KB 内存（16384个桶）。

• 算法原理基于 伯努利试验 和 分桶取平均，缩小误差

• 伯努利试验，讲的是我们 N 次抛硬币（假设出现正面反面的概率相同），如果直到 k 次才出现正面，那么 N 大约为 2 的 k 次方。

• 分桶取平均，指的是将 N 个数据均为为 m 个桶，每个桶单独 k 的值（1 出现的最大位数），取平均（有多种取法，常见的是调和平均）

• Redis 中使用 HyperLogLog 的命令为：

  • pfadd uv a # 时间复杂度为 O(1)
  • pfcount uv # 时间复杂度为 O(1), HyperLogLog 算法时间复杂度为 O(N), 因为对于每个值都要计算其hash 值最低1 的位。但是我们在 pfadd 时，可以预先计算好这些值，所以到了 pfcount 的时候，时间复杂度是 O(1)
  • pfmerge a b # 时间复杂度为 O(N)

• bitmap

事件机制

• 事件

  • 文件事件：Redis 基于 Reactor 模式（TODO: 搞清楚 Reactor 模式），使用 I/O多路复用（multiplexing）监听文件事件。

    • 事件类型：
      • AE_READABLE socket可读事件
      • AE_WRITABLE socket可写事件
    • Redis 调用底层的 multiplexing/多路复用 库函数，且自动会选择性能最高的 multiplexing/多路复用 函数使用。

  • 时间事件：定时任务，周期任务。Redis 使用链表（time_events）保存时间事件。

    • 时间事件：
      • id: 时间事件 id
      • when: 处理时间
      • timeProc: 本时间事件对应的事件处理器
    • 处理逻辑：

      def processTimeEvents():
          # 遍历事件是否已经到达
          for time_event in all_time_events():
              # 检查事件是否到达
              if time_event.when <= unix_ts_now():
                  # 事件已到达
                  # 执行事件处理器，并获取返回值
                  retval = time_event.timeProc()
              
                  # 如果这是一个定时事件
                  if retval == AE_NOMORE:
                      # 那么将该事件从服务器中删除
                      delete_from_event_from_server(time_event)
                  else:
                      # 更新事件的 when 属性
                      update_when(time_event, retval)
    • 应用实例. 参考 reis.c/serverCron 。
      • 更新服务器各类统计信息，比如事件，内存占用，数据库占用等等。
      • 清理数据库中的过期键值对。
      • 关闭和清理连接失败的客户端。
      • 尝试进行 AOF 或者 RDB
      • 操作。
      • 如果服务器是主服务器，那么对从服务器进行定期同步。
      • 如果处于集群模式，对集群进行定期同步和连接测试。

• 事件处理逻辑
  代码在 ae.c/aeProcessEvents 函数。伪代码如下：

  def aeProcessEvents():
      # 获取到达时间离当前时间最接近的时间事件
      time_event = aeSearchNearestTimer()
  
      # 计算最接近时间，还有多少毫秒到达
      remaind_ms = time_event.when - unix_ts_now()
  
      # 如果事件已经到达，那么 remaind_ms 取值位负数，将它设为 0
      if remaind_ms < 0:
          remaind_ms = 0
  
      # 根据 remaind_ms 的值，创建 timeval 结构
      timeval = create_timeval_with_ms(remaind_ms)
  
      # 阻塞并等待文件事件发生，最大阻塞由传入的 timeval 结构决定
      # 如果 remaind_ms 的值为 0， 那么 aeApiPoll 调用之后马上返回，不阻塞
      aeApiPoll(timeval)
  
      # 处理所有已经产生的文件事件
      processFileEvents()
      
      # 处理所有已到达的时间事件
      processTimeEvents()

  def main():
      # 初始化服务器
      init_server()
  
      # 一直处理事件，直到服务器关闭为止
      while server_is_not_shutdown():
          aeProcessEvents()
  
      # 服务器关闭，执行清理操作
      clean_server()
  • 从上面的伪代码可以看出:
    • 对事件的处理是：同步，有序，原子性地操作的。
    • 时间事件的处理时间，通常会比时间事件设计的到达时间晚一些。
    • 事件处理函数需要快速完成，否则会阻塞其他操作，也会使得时间处理时间延迟很多。

事务

• Redis 单条命令保证操作的原子性；但是 Redis 事务（MULTI 操作）仅仅保证将一组命令（入队的命令）有序执行，并不保证这些操作的原子性。

• MULTI EXEC/DISCARD 命令

  > MULTI
  OK
  > zadd salary 100 wangmeng
  QUEUED
  > zadd salary xxx zhangsan  # 执行错误，不影响接下来命令的执行。
  QUEUED
  > zadd salary 200 wangxiaoyu
  QUEUED
  > EXEC
  1) 0
  2) ERR value is not a valid float
  3) 0

  > MULTI
  OK
  > zadd salary 100 wangmeng
  QUEUED
  > zadd salary xxx  # 入队错误，会导致所有命令都执行不了。
  QUEUED
  > zadd salary 200 wangxiaoyu
  QUEUED
  > EXEC
  (error) ERR wrong number of arguments for 'zadd' command
  • 实现逻辑
    • muli:

      def MULTI():
          # 打开事务标识
          client.flags |= REDIS_MULTI
          # 返回 ok 回复
          replyOk()
    • 事务队列：

      typedef struct redisClient {
          ...
          // 事务状态
          multiState mstate;
          ...
      }

      typedef struct multiState {
          // 事务队列， FIFO 顺序
          multiCmd *commands;
          // 已入队命令计数
          int count;
      } multiState;

      typedef struct multiCmd {
          // 参数
          robj **argv;
          // 参数数量
          int argc;
          // 命令指针
          struct redisCommand *cmd;
      } multiCmd;
    • EXEC

      def EXEC():
          # 创建空白的回复队列
          reply_queue = []
          # 遍历事务队列中的每个项
          # 读取命令的参数，参数的个数，以及要执行的命令
          for argv, argc, cmd in client.mstate.commands:
              # 执行命令，并取得命令的返回值
              reply = execute_command(cmd, argv, argc)
              # 将返回值追加到回复队列队尾
              reply_queue.append(reply)
      
          # 移除 REDIS_MULTI 标识，让客户端回到非事务状态
          client.flags &= ~REDIS_MULTI
      
          # 清空客户端的事务状态，包括：
          # 1） 清零入队命令计数器
          # 2） 释放事务队列
          client.mstate.count = 0
          release_transaction_queue(client.mstate.commands)
      
          # 将事务的执行结果返回给客户端
          send_reply_to_client(client, rely_queue)

• WATCH 命令

  可以使用 WATCH 来监视变量，如果变量在期间被操作过，就拒绝执行 MUTLI/EXEC 事务。这是个乐观锁的逻辑。

  两个客户端执行命令的过程：

  时间	客户端A	客户端B
  T1	WATCH "name"
  T2	MULTI
  T3	SET "name" "peter"
  T4		SET "name" "john"
  T5	EXEC

  • watched_keys

    typedef struct redisDb {
        ...
        // 正在被 WATCH 监视的键
        dict *watched_keys;
        ...
    }

  • 所有对数据库进行修改的命令，比如 SET, LPUSH, SADD, ZREM, DEL, FLUSHDB 等等，在执行之后，都会调用 multi.c/touchWatchedKey 函数对 watched_keys 字典进行检查，查看是否有客户端正在监视刚刚被命令修改过的数据库键，如果有的话，那么 touchWatchKey 函数会将监视被修改键的客户端的 REDIS_DIRTY_CAS 标识打开，标识该客户端的事务安全性已经被破坏。

    def touchWatchKey(db, key):
        # 如果 key 存在于数据库的 watched_keys 字典中
        # 那么说明至少有一个客户端在监视这个 key
        if key in db.watched_keys:
            # 遍历所有监视键 key 的客户端
            for client in db.watched_keys[key]:
                # 打开标识
                client.flags |= REDIS_DIRTY_CAS

  • 判断事务是否安全，客户端执行 EXEC 命令时，会首先检查 REDIS_DIRTY_CAS 标识，如果该标识被打开，说明事务不安全，客户端拒绝执行事务；否则客户端执行事务。

Lua 脚本

发布与订阅

持久化

• rdb

  • 使用快照，将 Redis 内存中的数据保存到 dump.rdb 文件中。
  • 持久化的数据，不够实时。执行效率高。
  • save 命令， bgsave 命令
    • save 会阻塞 Redis 业务线程。导致 Redis 暂时不可用。
    • bgsave 会 fork 一个新的进程，来做持久化。不会阻塞 Redis 业务线程。
    • 可以手动执行，也可以配置成定时任务执行。

• aof(Append Only File)

  • 类似 MYSQL 的binlog 日志，通过不断执行 aof 的命令来持久化。
  • 执行效率不高。

• rdb + aof: TODO: 给个配置案例。

  • 使用两种方式，尽可能保证持久化所有数据。
  • Redis 没办法保证持久化所有数据。重启可能会丢失数据。

高可用

• 主从

  • 类似于 MYSQL 主从模式。主节点负责读写，从节点负责读；主节点的数据异步复制到从节点。
  • 手动故障转移/failover: 主节点挂掉后，需要运维手动重新启动主节点。
  • 配置：

• 哨兵

  • 相比于主从，哨兵模式仍然有主从节点，主节点负责读写，从节点负责读；主节点的数据异步复制到从节点。
  • 哨兵是用于监视主从节点工作状态的多个进程。出现故障时，哨兵负责做自动的故障转移/failover。
  • 配置：

• 集群

  • 类似于 MSYQL 中的分表。集群一共可写入 16384 个槽位，集群中的每个主节点（负责写的节点）负责其中一段槽位的读写。
  • 支持自动故障转移。
  • 自动故障转移原理，肯定是通过模式共识或者广播算法，选举一个从节点作为新的主节点。细节一直记不清，只记住几个名词： Gossip 协议，主观下线，客观下线 等几个概念，TODO: 后续再研究下吧。

应用示例

String

• 计数器
  • 利用了 redis incr/incrby 原子性的特点，可以用来实现计数器
• 分布式锁
  • 利用了 setnx 操作的原子性，可以用来实现分布式锁。
• 分布式全局唯一id
  • 利用了 redis incr/incrby 原子性的特点，可以用来位分布式系统提供唯一 id。
• 缓存
  • 很多系统的 session 是缓存在 redis（或者 memcached）中的。缓存用的很多。

Hash

• 缓存关系数据库慢查询
  • Hash 类似于 MySQL 中的一条记录，所以适合用来缓存 MySQL 查询结果。

List:

• 消息队列
  • 生产者消费者模型，生产者将消息推到 List 中，消费者从 List 中取走元素。这就构成了个消息队列。
  • 项目中用过 scrapy-redis 做分布式爬虫。scrapy-redis 就是使用 redis 做消息队列。代码见 https://github.com/rmax/scrapy-redis/blob/master/src/scrapy_redis/queue.py 中的 FifoQueue

Set:

• 签到
• like，打标签等

ZSet:

• 排行榜，新闻列表。
• 优先队列/消息队列。代码见 https://github.com/rmax/scrapy-redis/blob/master/src/scrapy_redis/queue.py 中的 PriorityQueue。

HyperLogLog:

• 统计 uv 。

参考文献

• Redis设计与实现
• 渐进式ReHash
• 从redis，memcached到nginx，网络底层io的那些事
• 设计跳表题解
• HyperLogLog 算法原理及其在 Redis 中的实现