vlambda博客
学习文章列表

redis相关底层数据结构及原理

Redis是一种速度非常快的非关系数据库,它可以存储键和5种不同类型的值直接的映射,可以将存储在内存中的键值对数据持久化到磁盘,可以使用复制特性来扩展读性能,还可以使用客户端分片来扩展写性能。
redis是个单线程程序,只使用单核,redis一般用于缓存数据库使用,存储生命周期比较短的数据,当然也可以作为内存数据库。

基础数据结构

redis相关底层数据结构及原理

redis存储的底层数据结构分为:
  • 简单动态字符串(simple dynamic string,SDS):redis默认字符串表示,SDS定义:

    struct sdshdr {
    //记录buf中已使用数组的数量,即sds所保存的字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组,用于保存字符串
    char buf[];
    }

    SDS实现了空间预分配惰性空间释放两种优化策略。

    (1)空间预分配:SDS字符串增长后长度<1M,则预分配和len属性同样大小的未使用空间,如果修改后SDS长度>=1M时,固定分片1M大小的未使用空间。

    (2)惰性空间释放:SDS字符串缩短后,程序不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。


  • 链表:提供高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过节点来灵活地调整链表的长度。定义如下:

    //每个链表节点定义如下:
    typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
    }listNode;
    typedef struct list {
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表包含的节点数量
    unsigned long len;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr, void *key);
    }list;

    链表结构如下:

    redis相关底层数据结构及原理

图一    链表


  • 字典:又称为符号表、关联数组或映射,是一种用于保存键值对(key-value pair)的抽象数据结构。Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有很多哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。

    //哈希表
    typedef struct dictht {
    //哈希表数组
    dicEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码,用于计算索引值,总数等于size-1
    unsigned long sizemask;
    //该哈希表已有节点数量
    unsigned long used;
    } dictht;
    //哈希表节点
    typedef struct dicEntry {
    //键
    void *key;
    //值
    union {
    void *val;
    uint64_tu64;
    int64_ts64;
    }v;
    //指向下个哈希表节点,形成链表
    struct dicEntry *next;
    } dicEntry;
    //字典
    typedef struct dict {
    //类型特定函数
    dicType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引,当rehash不在进行时,值为-1
    int rehashidx;
    }dict;

    字典结构如下:

    redis相关底层数据结构及原理

    图二    普通状态下的字典


  • 跳跃表skiplist:是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素比较多,或有序集合中元素成员(member)是比较长的字符串时,Redis就会使用跳跃表作为有序集合键的底层实现。

    跳跃表的结构定义如下:

    //跳跃表节点
    typedef struct zskiplistNode {
    //层
    struct zskiplistLevel {
    //前进指针
    struct zskiplistNode *forword;
    //跨度
    unsigned int span;
    }level[];
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //成员对象
    robj *obj;
    }zskiplistNode;
    //跳跃表
    typedef struct zskiplist{
    //表头节点和表尾节点
    struct zskiplistNode *header,*tail;
    //表中节点数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;
    }zskiplist;

    redis相关底层数据结构及原理

    图三    带有skiplist结构的跳跃表

    每个跳跃表节点的层高都是1~32之间的随机数,同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。


  • 整数集合intset:是集合键的底层实现之一,当一个集合只包含整数元素,且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。

    集合键的结构定义:

    typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
    }intset;

    整数集合的底层实现为数组,这个数组以有序、无重复的方式保存集合元素,在有需要时,程序会根据新添加的元素的类型,改变这个数据的类型。升级操作为整数集合带来了操作上的灵活性,并且尽可能的节约了内存。整数集合只支持升级操作(如int8_t->int16_t->int32_t->int64_t),不支持降价操作。


  • 压缩列表ziplist:是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么redis就会使用压缩列表来做列表键的底层实现。压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值。

    redis相关底层数据结构及原理


redis由上面6种底层数据结构实现了5种数据结构:
字符串string:intset、SDS
列表list:ziplist、双端链表
哈希表hash:ziplist、dict
集合set:intset、dict
有序结合zset:ziplist、skiplist+dict

redis相关底层数据结构及原理

持久化

redis相关底层数据结构及原理
redis是内存数据库,它将自己的数据库状态存储在内存里面,所以如果不想办法将内存中数据保存到磁盘中的话,一旦redis服务器进程退出,服务器中的数据库状态也会消失不见了。所以redis提供了2种持久化方式:RDB持久化、AOF(append only file)持久化。
RDB持久化功能所生成的RDB文件是一种经过压缩的二进制文件,通过该文件还原生产RDB文件时的数据库状态。redis没有专门的载入RDB文件的命令,只要Redis服务器在启动时检测到RDB文件存在,它就会自动载入RDB文件。可以用命令save(阻塞式)、bgsave(非阻塞式)手工持久化redis,也可以通过配置save选项,让服务器每隔一段时间自动执行bgsave命令。如save 300 10表示300秒内,对数据库进行了至少10次修改。serverCron每个100ms会检查一次是否需要执行bgsave。对于不同类型的键值对,RDB文件会使用不同的方式保存他们。

redis相关底层数据结构及原理

AOF持久化是通过保存redis服务器所执行的写命令来记录数据库状态的。redis启动时通过对aof文件的载入还原数据到内存,因通过写命令记录数据库状态,随着时间流逝,aof文件中的内容会越来越多,文件体积会越来越大,为解决aof文件膨胀问题,redis提供了aof文件重新(rewrite)功能,新aof文件不会包含冗余命令(不是读取和分析老的aof文件的内容,而是直接从数据库中读取键值对,用一条命令记录键值对,同时如数据量大时为避免客户端输入缓存区溢出,使用多条命令记录),为避免阻塞主进程,rewrite是通过fork子进程来执行的,完成后通知主进程,将aof重写缓冲区(rewrite期间双写,除了写aof缓存区, 还写aof重写缓存区)内容追加到新的aof文件末尾,将新aof文件替换旧aof文件。这个信号处理函数执行完毕后,父进程就可以继续像往常一样接收命令的请求了。


redis相关底层数据结构及原理

复制

redis相关底层数据结构及原理
用户可以通过执行slaveof命令或者设置slaveof选项,让一个服务器去复制(replicate)另一个服务器。
redis的复制功能分为同步和命令传播两个操作:
  • 同步操作用于将slave服务器的数据库状态更新至master当前所处的数据库状态。

  • 命令传播操作则用于在master的数据库状态被修改,导致master与slave数据库状态不一致时,让master与slave数据库重新回到一致状态。

同步状态分为完整重同步和部分重同步:

  • 完整重同步:用于处理初次复制和状态未持久化场景,通过让主服务器创建并发送RDB文件,以及向从服务器发送保存在缓存区里面的写命令进行同步。

  • 部分重同步:当从服务器在断线后重新连接主服务器时,如果条件允许,主服务器可以将主从服务器连接断开期间执行的命令发送给从服务器,从服务器只要接收并执行这些命令,就可以将数据库更新至主服务器当前所处的状态。

部分重同步涉及几个概念:主从服务器复制偏移量、主服务器的复制积压缓存区、服务器的运行ID(run ID)。通过对比主从服务器的复制偏移量,程序可以很容易主从服务器是否处于一致状态,复制积压缓存区是由主服务器维护的一个固定长度先进先出队列,默认大小为1M,当从服务器重连主服务器后,通过PSYNC将自己的复制偏移量offset发送给主服务器,如果offset之后的数据在复制积压缓存区则进行部分重同步,如果不在,则进行完整重同步。
当完成了同步之后,主从服务器就会进入命令传播阶段,这时主服务器只要一直将自己执行的写命令发送给从服务器,而从服务器只要一直接受并执行主服务器发送来的命令,就可以保证主从服务器一直保持一致了。主服务器通过向从服务器传播命令来更新从服务器的状态,保持主从服务器一致,而从服务器则通过向主服务器发送REPLCONF ACK命令(默认每秒一次)来进行心跳检测,以及命令丢失检测。


redis相关底层数据结构及原理

Sentinel

redis相关底层数据结构及原理

sentinel(哨兵)是Redis高可用解决方案:由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器,以及这些主服务器属下的所有从服务器,并在被监视的主服务器进入下线状态时,自动将下线的主服务器属下的某个从服务器升级为新的主服务器,然后由新的主服务器替代已下线的主服务器继续处理命令请求。

redis相关底层数据结构及原理

图四    服务器与Sentinel系统


Sentinel通过向主服务器发送Info命令来获取主服务器属下所有从服务器信息,并为这些从服务器创建响应的实例结构,以及连向这些从服务器的命令连接和订阅连接。在一般情况下,Sentinel以每十秒一次的频率向被监视的主从服务器发送Info命令,当主服务器处于下线状态,或者Sentinel正在对主服务器进行故障转移操作时,Sentinel向从服务器发送Info命令的频率改为每秒一次,Sentinel以每秒1次的频率向实例(包括主从服务器、其他Sentinel)发送Ping命令,并根据实例对ping命令的回复来判断实例是否在线,当一个实例在指定时长中连续向Sentinel发送无效回复时,Sentinel会将此实例判断为主观下线。当Sentinel将一个主服务器判断为主观下线时,它会向其他Sentinel进行询问,看它们是否同意这个主服务器已经进入主观下线状态。当Sentinel收集到足够多(Sentinel配置监视的master时设置)的主观下线投票后,将主服务器判断为客观下线,并发起一次针对主服务器的故障转移操作。当一个主服务器被判断为客观下线时,监视这个下线主服务器的各个Sentinel会进行协商,选举出一个领头Sentinel(采用先到先得投票过半策略选出),并由领头Sentinel对下线主服务器执行故障转移操作。领头Sentinel对已下线的主服务器执行故障转移操作包括以下三个步骤:
  • 在已下线的主服务器属下的所有从服务器里面,挑选出一个从服务器,并将其转换为主服务器(发送slaveof no one命令,并1s发送一次info检查角色是否变为master)。

  • 让已下线的主服务器属下所有从服务器改为复制新的主服务器(发送slaveof newIP newPort命令)。

  • 将已下线的主服务器设置为新的主服务器的从服务器,当这个旧的主服务器重新上线时,它就会成为新的主服务器的从服务器(发送slaveof newIP newPort命令)。

其中从服务器选主时,领头Sentinel对从服务器列表中先删除下线断线状态的从服务器、删除5s内info没回复的从服务器、删除与下线的主服务器连接断开超过一定毫秒的从服务器(保证从服务器数据是比较新的),之后,领头Sentinel根据从服务器优先级、从服务器的复制偏移量大小、运行ID小大排序顺序选主。


redis相关底层数据结构及原理

事件与ServerCron函数

redis相关底层数据结构及原理


Redis服务是一个事件驱动程序,服务器处理的事件分为时间事件和文件事件两类。
文件事件处理器是基于Reactor模式实现的网络通信程序,文件事件是对套接字操作的抽象:每次套接字变为可应答(acceptable)、可写(writable)或者可读(readable)时,相应的文件事件就会产生。
时间时间分为定时事件和周期性事件:定时事件只在指定的事件到达一次,而周期性事件则每隔一段时间到达一次。服务器在一般情况下只执行serverCron函数一个时间事件,并且这个事件是周期性事件。
redis服务器中的serverCron函数默认每隔100毫秒执行一次,这个函数负责管理服务器的资源,并保持服务器自身的良好运转。包括更新服务器统计信息、清理数据库过期键值对、关闭和清理连接失效的客户端、尝试进行RDB和AOF的持久化操作、如果为主服务器定期同步数据到从服务器、集群模式下对集群进行定期同步和连接测试等。


redis相关底层数据结构及原理

lua脚本、发布与订阅

redis相关底层数据结构及原理


redis从2.6版本开始引入对Lua脚本的支持,通过在服务器中嵌入Lua环境,Redis客户端可以使用lua脚本,直接在服务器端原子地执行多个Redis命令。因为执行Redis命令必须有相应的客户端状态,所以为了执行Lua脚本中包含的Redis命令,Redis服务器专门为Lua环境创建了一个伪客户端,并有这个伪客户端负责处理Lua脚本中包含的所有Redis命令。
redis相关底层数据结构及原理

图五    Lua脚本执行Redis命令时的通信步骤


与其他普通redis命令一样,当服务器运行在复制模式下时,具有写性质的脚本命令也会被复制到从服务器,执行命令包括eval命令、evalsha命令、script flush命令已经script load命令。主服务器在复制evalsha命令时,必须确保所有从服务器都已经载入了evalsha命令指定的sha1校验和所对应的Lua脚本,如果不能确保这一点的话,主服务器会将evalsha命令转换为等效的eval命令,并通过传播eval命令来获得相同的脚本执行结果。
服务器状态在pubsub_channels字典保存了所有频道/模式的订阅关系:subscribe/psubscribe命令负责将客户端和被订阅的频道/模式关联到这个字典里面,而unsubscribe/punsubscribe命令则负责解除客户端和被退订频道/模式直接的关联。publish命令通过访问pubsub_channels字典、pubsub_patterns链表来向频道/模式的所有订阅者发送消息。


redis相关底层数据结构及原理

过期字典删除

redis相关底层数据结构及原理


数据库键的过期时间都保存在过期字典中,redis过期键删除策略包括两种:惰性删除和定期删除。
惰性删除,放任键过期不管,但是每次从键空间中获取键时,都检查取得的键是否过期,如果过期的话,就删除该键,如果没过期,就返回该键。惰性删除对CPU时间来说是最友好的,但它对内存是最不友好的,存在内存泄露的危险。
定期删除,每隔一段时间,程序就对数据库进行一次检查,删除里面的过期键。每当redis的服务器周期性的操作serverCron函数执行时,在规定的时间内,分多次遍历服务器中的多个数据库(默认16个库),从数据库的expires字典中随机检查一部分键(默认20)的过期时间,并删除其中的过期键。


redis相关底层数据结构及原理

E N D