Redis内核实现技术

xiangtingsl

数据结构与对象

简单动态字符串（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