Redis内核实现技术

数据结构与对象

简单动态字符串（SDS）

用于保存会变化的字符串和用于缓冲区

例如键值对里面的key/value，AOF缓冲之类

struct sdshdr {
    int len;//字符串长度
    int free;//未使用的字节
    char buf[];
};

SDS与C字符串的区别

• 常数时间获取字符串长度

• 避免内存溢出

• 内存预分配，减少内存重申请

  如果申请的len小于1MB，那么申请内存会是len*2+1的空间；如果申请len大于1MB，那么申请内存回事len+1+1MB

• 惰性释放内存

• 二进制安全

• 兼容C字符串函数

链表

用于发布订阅、慢查询、监视、链表键等功能

哈希表

struct dictht{
    dictEntry ** table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
};
struct dictEntry {
    void * key;
    union{
      void* val;
        uint64_tu64;
        int64_ts64;
    }v;
    struct dictEntry* next;
};

redis-hash-table

struct listNode {
    struct listNode* prev;
    struct listNode* next;
    void* value;
};

字典

key/value数据结构

用于哈希键底层实现

struct dict {
    dictType* type;
    void* privdata;
    dictht ht[2]; //hash table
    int trehashidx;//rehash in progress flag
};

redis-dict

使用MurmurHash算法来计算hash值

rehash

根据需要进行缩容和扩容，以2的n次方为单元

过程如下：

redis-rehash-1
redis-rehash-2
redis-rehash-3
redis-rehash-4

rehash的触发场景：

• 目前没有执行BGSAVE或者BGREWRITEAOF，且哈希表的负载因子大于1
• 目前执行BGSAVE或者BGREWRITEAOF，且哈希表的负载因子大于5
• 负载因子小于0.1时，缩容

渐进式rehash

通过分批次，从哈希表0慢慢迁移到哈希表1，避免服务器暂停服务

delete、find、update会同时在两个哈希表操作

跳跃表

是一种有序的链表结构

查找算法复杂度平均logN，最坏N

作为有序集合键的底层实现

redis-skip-list

整数集合

struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[]; //int16/int32/int64
};

通过排序数组，来保持set内整数唯一

压缩列表

是列表键和哈希键的底层实现之一

如果键是小整数和短字符串为主，就会使用压缩列表来存储

用于节省内存

对象

redis-obj

内存回收

使用引用计数来回收内存

数据库

读写操作

数据库读写除了对键空间进行读写操作，还会包含以下操作：

• 更新是否读命中或者不命中
• 更新键的LRU
• 如果读的一个键过期，则删除过期键
• 如果客户端使用了watch来监视某个键，服务器对此键修改后，会把此键标记为脏
• 每次修改一个键后，会把脏计数加一，这个计数会触发持久化和复制操作
• 如果服务器开启了数据库通知功能，会在对键修改后，服务器会按配置发送相应的数据库通知

过期处理

键过期的时间保存在redisDb的expires字典中

struct reidstDb {
    dict* expires;
};

redis-expired

过期键删除策略

• 惰性删除

  如果读到某个过期键，则删除此键

• 定期随机删除

  定期随机挑选一些键进行检查，并删除其中的过期键

时间事件

通过一个链表来维持时间超时事件

每次都必须遍历整个链表才知道哪些事件需要触发

持久化与复制

生成RDB文件

• 执行SAVE或者BGSAVE会创建一个新的RDB文件，程序会对数据库的键进行检查，已过期的键不会保存到新创建的RDB文件中。
• 通过配置定期执行，通过时间间隔内，写入的次数来决定
• SAVE会阻塞Redis；BGSAVE会产生一个子进程，来生成RDB文件

载入RDB文件

• 服务器启动时，检测是否存在RDB文件，如果存在自动载入
• 如果是主服务器，载入RDB文件时，会过滤过期键
• 如果是从数据库，载入RDB文件时，不会过滤过期键，因为从数据库将会被主数据库覆盖
• 载入RDB时，服务器会一直阻塞

AOF文件写入

• 写操作会写入AOF缓冲区
• 每一秒/每一次/每个大循环，写操作的命令的缓冲区会sync到磁盘
• 过期键被清除时，会写入一个del命令

AOF载入

• 如果开启了AOF持久化，服务器会使用AOF来还原数据库

AOF重写

• 单纯的通过命令来维持AOF文件，会造成文件太大。通过重写，把冗余状态的写命令合并，可以减少AOF文件的大小
• 重写期间，新的写命令会同时写入AOF缓冲区和AOF重写缓冲区，来保证重写后的AOF文件的一致性
• AOF重写，会过滤过期键

复制

• 通过sync初始同步RDB，接着同步写命令来保持主从服务器的一致性
• 断线重连psync部分重传来把断线期间的写命令同步给从服务器，来恢复一致性
  • 复制积压缓冲区是固定大小的队列，默认1MB
  • 如果主从的offset偏差超过了复制挤压缓冲区，那么psync将不能适用，同步会退化成全同步sync
• 主服务器删除一个过期键，会发送一条DEL到从服务器
• 从服务器不主动删除过期键
• 主从通过ping pong来维持心跳检测

Sentinel

redis-sentinel

• Server1是主数据库
• 其他为从数据库
• 如果server1对sentinel的应答超时，那么sentinel会对server1进行下线
• 并从其他从数据库中挑选一个出来作为主数据库
• 其他从数据库则复制新的主数据库
• 如果server1又重新上线，则会作为从数据库存在

Sentinel与服务器的连接

redis-sentinel-connect

• 由于redis的发布订阅功能，被发送的消息不会保存在redis中，如果发送时，接收信息的客户端不在线，那么客户端就会丢失这条信息
• 为了不丢失任何信息，sentinel专门用一个订阅连接来接收该频道的信息

获取服务器信息

redis-get-master
redis-get-slave

• Sentinel每10秒向master服务器发送INFO命令
• 从INFO信息获取master的信息并更新内存结构
• 从INFO信息获取slave的信息，并向slave发起订阅连接

感知其他sentinel节点

redis-feel-others-sentinel
redis-connect-sentinel

• sentinel每两秒会发送hello到master服务器
• 同时sentinel会订阅hello信息
• sentinel发送的hello信息会进入订阅队列，并被所有的sentinel消费
• 通过订阅hello信息，sentinel可以发现其他连接着同一个主服务器的sentinel
• 并发起连接操作

主观下线

redis-sentinel-ping

• sentinel会向其他所有节点每秒发送ping
• 其他节点如果返回pong失败，在一定时间后，sentinel会判定此服务器主观下线

客观下线

sentinel monitor master 127. 0. 0. 1 6379 2

通过配置指定达到多少个sentinel判定服务器为主观下线，来触发客观下线

上面的命令表达达到2个sentinel判定服务器为主观失效，则此服务器为客观下线

Sentinel master选举

得到半数以上票数的sentinel，将成为master

sentinel master的工作

• 选举redis数据库主服务器
• 修改从服务器的复制目标
• 将旧的主服务器变为从服务器

集群

通过对key进行hash分片，通过分布式集群统一对外提供数据访问。集群提供复制和分片功能，实现高可用与大数据存储量功能

集群加节点

redis-cluster-meet

• 通过发送meet命令加入集群
• 加入后的新节点通过gossip协议同步给集群中的其他节点
• 加入后，如果整个集群还没完全分配槽，则集群不可用

槽slot

• 整个数据库有16384个槽
• 集群中的每个节点可以处理0到16384个槽
• 当16384个槽都有节点处理，并处理的节点都在线，则集群处于上线状态；否则为下线状态
• 节点通过广播来告诉其他节点本节点处理的槽信息
• 节点通过cluster addslots来加槽

执行命令

客户端向在线的集群的其中一个节点发送命令

• 如果key的槽正好是这个节点，则这个节点接受命令并处理
• 如果key的cao不在这个节点，则此节点会返回MOVE错误，客户端会redirect到正确的节点

节点数据库

• 单机数据库可以使用0到16个不同的数据库
• 节点数据库只能使用第0个数据库

slots_to_keys

• 使用跳跃表来组织结构
• 使用key的槽号来排序
• 用来管理同一槽的数据，例如要批量迁移

重新分片

• 可以将任意数量已经指派给某个节点的槽改为指派给另一个节点
• 重新分片过程中，不影响集群的在线状态
• 源节点和目标节点都可以继续处理命令

redis-slot-reballance

重分片过程中执行命令

• 正在迁移的源节点接受到客户端请求

• 如果key是本节点处理，则查找key是否在本数据库中

• 如果在本数据库，则执行命令并返回

• 否则返回客户端一个ASK错误，指引客户端转向目标节点执行命令

redis-ask

复制与故障转移

• 集群中的节点分为主节点和从节点
• 从节点关联一个节点为主节点，通过复制来同步主节点的数据
• 但主节点下线，从节点会上升为主节点
• 旧的主节点重新上线，则会作为从节点继续服务

状态检测

• 集群中的每个节点都会向其他节点发送ping来检测其他节点的状态
• 如果发现某个节点pong返回异常，则会标志为主观下线
• 当集群中的半数以上主节点标志某个节点为主观下线，则此节点会被判定为下线，并会通知集群中的所有节点，此节点下线
• 此时如果此节点有从节点
• 则从节点会选举一个新的主节点，并把主节点的所有槽指向新的主节点
• 选举新的主节点的规则是，从节点向所有的主节点请求投票给自己，如果节点收到超过半数以上的票，则会成为master。依据先到先得的规则

Redis的不足与改进

• 利用多核优势，使用多线程处理
• 有序列表使用数组，更好的利用计算机缓存
• 更丰富的数据结构类型
• 时间事件不要使用链表，应该使用更高级的数据结构
• 利用SIMD计数，提高并行度
• 对整数的处理可以引入protobuf的技术来压缩
• 如果内存不足时，可以引入磁盘辅组存储，而不是直接拒绝服务
• 更丰富的热点统计数据，例如top 10的key访问
• 热点倾斜数据自动re-balance