Redis设计与实现

最近为了学习redis,把redis设计与实现这本书看完了。这本书图文并茂,深入浅出,有种作者是把菜饭嚼碎了喂给你吃的感觉。看完后对redis的实现有了比较深的理解,决定把感触比较深的几点记录下来。

数据类型和结构

首先要明白数据类型和数据结构的区别:

  • redis支持五种数据类型:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted set:有序集合)。
  • redis底层的六种数据结构:SDS(简单动态字符串),list(链表),dict(字典),skiplist(跳跃表),intset(整数集合),ziplist(压缩列表)。

redis中的数据都是以键值对存储的,我们根据key来set和get。而用来存储的value可以是以上五种数据类型。
redis_dataType

而六种数据结构,则是整个redis底层的基石,是用来实现五种数据类型的结构。redis会为每个value选取最合适的结构,用来提高读取速度。

数据结构

SDS
struct sdshdr {      
    // buf 中已占用空间的长度  
    int len;  
    // buf 中剩余可用空间的长度  
    int free;  
    // 数据空间  
    char buf[];  
};  
  1. 当对SDS进行修改时,先检查SDS的空间是否满足修改所需要的空间要求,如果不满足,则先扩展空间,然后执行修改操作。
  2. 当缩短字符串时,并不会立即使用内存重分配来回收多出来的字符,而是记录在free属性中。
    这样每次对value进行修改时,可以减少内存重分配次数。
list
/* 
 * 双端链表节点 
 */  
typedef struct listNode {  
    // 前置节点  
    struct listNode *prev;  
    // 后置节点  
    struct listNode *next;  
    // 节点的值  
    void *value;  
} listNode;  

/* 
 * 双端链表结构 
 */  
typedef struct list {  
    // 表头节点  
    listNode *head;  
    // 表尾节点  
    listNode *tail;  
    // 节点值复制函数  
    void *(*dup)(void *ptr);  
    // 节点值释放函数  
    void (*free)(void *ptr);  
    // 节点值对比函数  
    int (*match)(void *ptr, void *key);  
    // 链表所包含的节点数量  
    unsigned long len;  
} list;  

  1. head,tail指向链表头尾。
  2. 每个节点都有前置和后置指针。
hash

/* 
 * 字典 
 */  
typedef struct dict {  
    // 类型特定函数,Redis为不同用途的字典设置不同的类型特定函数  
    dictType *type;  
    // 私有数据,传递给特定类型函数的可选参数  
    void *privdata;  
    // 哈希表,一般情况下字典使用ht[0],ht[1]只会在对ht[0]进行rehash时使用  
    dictht ht[2];  
    // rehash 索引  
    // 当 rehash 不在进行时,值为 -1  
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */  
    // 目前正在运行的安全迭代器的数量  
    int iterators; /* number of iterators currently running */  
} dict;  

/* 
 * 哈希表 
 * 每个字典都使用两个哈希表,从而实现渐进式 rehash 。 
 */  
typedef struct dictht {      
    // 哈希表数组,存放具体的键值对  
    dictEntry **table;  
    // 哈希表大小  
    unsigned long size;      
    // 哈希表大小掩码,用于计算索引值  
    // 总是等于 size - 1  
    unsigned long sizemask;  
    // 该哈希表已有节点的数量  
    unsigned long used;  
} dictht;  

/* 
 * 哈希表节点 
 */  
typedef struct dictEntry {      
    // 键  
    void *key;  
    // 值  
    union {  
        void *val;  
        uint64_t u64;  
        int64_t s64;  
    } v;  
    // 指向下个哈希表节点,形成链表  
    struct dictEntry *next;  
} dictEntry;  

每个哈希表底层结构都是一个数组,要考虑的事情无非3件:好的哈希函数,解决地址冲突的方法,扩容策略。redis是这样实现的:

  1. 根据key计算出hash值,然后用hash值对哈希数组长度取余获得索引值。
  2. 链接地址法(拉链法)解决哈希冲突
  3. 增量扩容:rehash动作并不是一次性、集中式的完成,而是分多次、渐进式地完成。
skiplist

/* 
 * 跳跃表 
 */  
typedef struct zskiplist {  
    // 表头节点和表尾节点  
    struct zskiplistNode *header, *tail;  
    // 表中节点的数量  
    unsigned long length;  
    // 表中层数最大的节点的层数,表头结点的层数不计算在内  
    int level;  
} zskiplist;  

/* 
 * 跳跃表节点 
 */  
typedef struct zskiplistNode {  
    // 成员对象  
    robj *obj;  
    // 分值,跳跃表中节点按各自所保存的分值从小到大排列  
    double score;  
    // 后退指针,指向当前节点的前一个节点  
    struct zskiplistNode *backward;  
    // 层,每次创建一个新节点,程序按幂次定律随机生成一个1~32的值作为level数组的大小(层高度)  
    struct zskiplistLevel {  
        // 前进指针  
        struct zskiplistNode *forward;  
        // 跨度,前进指针所指向的节点和当前节点的距离  
        unsigned int span;  
    } level[];  
} zskiplistNode;  

每个跳跃表节点都有一个score,所以跳跃表是有序的。其实跳跃表就是有序链表的扩展,主要目的就是为了快速地找到某一节点,所以跳跃表的实现和平衡树很像。
它会取出一些关键节点用来加速寻找,这幅图一目了然:
redis_skiplist

intset

typedef struct intset {      
    // 编码方式  
    uint32_t encoding;  
    // 集合包含的元素数量  
    uint32_t length;  
    // 保存元素的数组,各项在数组中按值大小有序地排序并且不包含重得项  
    int8_t contents[];  
} intset;  

由于整数集合有三种类型(int16_t,int32_t,int64_t),所以redis会了提高效率:

  1. 提高灵活性和读取速度,整数集合中每个值的类型固定。
  2. 为了节约内存,只有当添加比当前数组元素的类型长的元素时,才会对当前集合升级。
  3. 应该是为了更加简单,整数集合一旦对数组升级了,就一直保持升级后的状态不支持降级操作。
ziplist

压缩列表(ziplist)是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点,每个结点可以保存一个字节数组或一个整数值。
因为是连续内存块,所以存储的列表项要么是小整数,要么是较短的字符串,而且存储的列表项个数要少。

数据类型

对象

redis使用前面说的五大数据类型来表示键和值,每次在redis数据库中创建一个键值对时,至少会创建两个对象,一个是键对象,一个是值对象,而redis中的每个对象都是由 redisObject 结构来表示:

 
typedef struct redisObject{
     //类型
     unsigned type;
     //编码
     unsigned encoding;
     //指向底层数据结构的指针
     void *ptr;
     //引用计数
     int refcount;
     //记录最后一次被程序访问的时间
     unsigned lru;
 
}robj

  • type:对应五种数据类型,string ,list ,hash ,set ,zset 。
  • encoding:对象的 ptr 指针指向对象底层的数据结构。

每种数据类型都有可能由2种数据结构来实现,而redis的高效性和灵活性正是得益于对于同一个对象类型采取不同的底层结构,并在必要的时候对二者进行转换。具体的转换临界值都可以自己设置。

zset

有序集合对象比较特殊,当使用 zet 结构作为底层实现,一个 zset 结构同时包含一个字典和一个跳跃表:


typedef struct zset {  
    // 字典  
    dict *dict;  
    // 跳跃表  
    zskiplist *zsl;  
} zset;

  • 有序集合中每个值都会绑定一个分值,所以dict做了个值和分值的映射,这样根据值获得分值则为O(1)。
  • 而zsl本身是有序的,可以来做插入删除和范围操作。

单机数据的实现

AOF与RDB

  • RDB:对Redis中的数据执行周期性的持久化。
  • AOF:对每条写入命令作为日志,以append-only的模式写入一个日志文件中,在redis重启的时候,可以通过回放AOF日志中的写入指令来重新构建整个数据集。

两种模式的具体优缺点就不介绍了,这边特别说下AOF模式:

为了解决 AOF 文件越来越大的问题,用户可以向 Redis 发送 BGREWRITEAOF 命令,这个命令会移除 AOF 文件中冗余的命令来重写 AOF 文件,使 AOF 文件的体积变得尽可能地小。
值得注意的是,进行 AOF 文件重写时,如果原来的 AOF 文件体积已经非常大,那么重写 AOF 并删除旧 AOF 文件的过程将会对 Redis 的性能造成较大的影响。

事件循环

一个线程一次只能执行一个任务,执行完成后线程就会退出。如果我们需要一个机制,让线程能随时处理事件但并不退出,这种模型通常被称作 Event Loop。
Event Loop 在很多系统和框架里都有实现,比如 Node.js 的事件处理,比如 Windows 程序的消息循环,再比如 OSX/iOS 里的 RunLoop。


void aeMain(aeEventLoop *eventLoop) {
    eventLoop->stop = 0;
    while (!eventLoop->stop) {
        if (eventLoop->beforesleep != NULL)
            eventLoop->beforesleep(eventLoop);
        aeProcessEvents(eventLoop, AE_ALL_EVENTS);
    }
}  

int aeProcessEvents(aeEventLoop *eventLoop, int flags) {
    int processed = 0, numevents;
    
    processed += processFileEvents(eventLoop);
    processed += processTimeEvents(eventLoop);
    
    return processed;
}

redis事件循环简写下来就是上面这样,主要处理文件事件时间事件

IO多路复用

redis执行aeMain的线程只有一个,所以说redis是单线程的。

对于一次IO访问(以read举例),一般都会有两步:

  1. 等待数据准备 (Waiting for the data to be ready)
  2. 将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

因为这两个阶段,linux下会有各种网络模式方案,这个就不具体讲了,下面这篇文章讲的很详细:
Linux IO模式

对于redis,如果同时有多个连接过来,一般的思路下,最容易有两种思路:

  1. 单线程,每次只处理一个连接,每次IO等待的时候就轮询(我觉得和空转没什么区别了)或者阻塞(也就是休眠)。之后把数据写入连接,结束后在处理下一个连接。
  2. 多线程,每个线程对应一个连接,开始重复第一步做的事情。这样免不了各种上下文切换,竞争条件。

这个时候就会有第三种思路,就是IO多路复用,redis正是采用这种方式。他和上面单线程的不同就是:

I/O 多路复用的特点是通过一种机制使一个线程能同时等待多个文件描述符,而这些文件描述符(套接字描述符)其中的任意一个进入读就绪状态,select()函数就可以返回。

下面这篇文章详细地介绍了Redis里 I/O 多路复用的实现:
Redis 和 I/O 多路复用

redis这样选择的好处:

  • 绝大部分请求是纯粹的内存操作(非常快速),采用单线程,避免了不必要的上下文切换和竞争条件。
  • select/epoll的 I/O 多路复用可以使单线程同时处理多个连接,不会因为一个连接没有准备好数据就一直阻塞下去。

多机数据库的实现

主从复制

  • 全量同步:Redis全量复制一般发生在Slave初始化阶段,这时Slave需要将Master上的所有数据都复制一份。
  • 增量同步:Redis增量复制是指Slave初始化后开始正常工作时主服务器发生的写操作同步到从服务器的过程。
  • 主从同步策略:主从刚刚连接的时候,进行全量同步;全同步结束后,进行增量同步。一般情况下首先会尝试进行增量同步,如不成功,要求从机进行全量同步。
  • 如果多个Slave断线了,需要重启的时候,因为只要Slave启动,就会发送sync请求和主机全量同步,所以当多个同时出现的时候,可能会导致Master剧增宕机。

选举(Raft)

在redis集群中,如果主节点出现故障,子节点采用选举算法选出新的主节点。
Raft协议算法国际论文

Paxos协议晦涩难懂,在工程实践中难以得到应用。Raft是一种分布式一致算法,是RaplicationAnd Fault Tolerant的缩写。Raft相对来说容易理解,容易应用到工程实践中去。所以Raft会大行其道。

独立功能

  • 发布与订阅:Redis 通过 PUBLISH 、 SUBSCRIBE 等命令实现了订阅与发布模式, 这个功能提供两种信息机制, 分别是订阅/发布到频道和订阅/发布到模式。正是因为这个功能,Redis 可以用来实现类似 nsq 那种 mq 功能,不过并不推荐这样做。
  • 事务:以一个MULTI命令为开始,接着将多个命令放在事务中,最后由EXEC命令将这个事务提交(commit)给服务器执行。
  • Lua脚本:Lua 脚本功能是 Reids 2.6 之后添加的新功能,通过内嵌对 Lua 环境的支持,可以执行EVALEVALSHA两个命令。
  • 排序:SortByLimitGetStore
  • 二进制位数组:二进制求和:SWAR 算法。
  • 慢查询日志:日志数量超过 slowlog-max-len 后,最新的日志会保留。和 Mysql 一样,主要用来优化一些执行很慢的命令。
  • 监视器:通过执行 MONITOR 命令,client 可以将自己变成监视器,实时地接收并打印出服务器当前处理的命令请求相关信息。
作者:levi
comments powered by Disqus