《redis设计与实现》-总结

链表

实现

总结

链表在redis应用非常广泛，比如当列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串，redis就会使用链表作为列表键的底层实现

链表的实现总结如下

字典

结构

dict结构

该结构中的type定义了特定类型键值对的函数，trehash定义了是否正在rehash，因为redis的rehash是渐进式的，渐进式的hash要操作2个dictht结构

dictEntry

分键值对和(next)指向下一个节点的指针(用于解决键的冲突)

dictht

又dictEntry的数组，还有哈希表的大小，用于hash的sizemask,和节点数量

hash算法

哈希表的扩展和收缩

或者负载因子小于0.1系统会自动收缩

总结

跳跃表

跳跃表按照分值来进行排序，所以基本redis只有有序列表和内部数据采用这个结构

跳跃表节点

跳跃表

typedef struct zskiplist {
    //指向跳跃表的表头和表尾
    structs zkiplistNode *header, *tail;
    //节点数量
    unsigned long length;
    //最大节点的基数
    int level;
}

总结

整数集合

其中encoding表示其contents数组中保存的数据大小，而不是根据int8_t来代表数据大小，因为c中的数组本质就是一个指针，然后整数集合会自动触发升级，也就是将int8_t升级成int16_t，升级的好处就是可以很灵活，当想要大的数据就进行扩容然后再存入，然后就是节约内存，因为当要大的数据时候才会扩容，小数据的时候就使用小的数据结构

总结

压缩列表

www.cnblogs.com/hunternet/p…

总结

压缩列表就是类似数组，但是本身结构存储了自身的长度和其他信息，结尾有个0xff来表示结尾，然后中间的数据都有自己的长度标识，其中previous_entry_length用来标识前一个数据的长度，encoding用来标识本身数据的长度，其中以11开始标识是整数型，而01 00 10用来标识字节数组，后续的位用来表示长度，content用来表示内容

• 压缩列表是Redis为节约内存自己设计的一种顺序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
• 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高

对象

redis不是直接拿上面提到的数据结构来实现键值对数据库，而是创建了一个对象系统，用上面的数据结构来组成

类型

可以使用type命令查看其键的值的类型，比如type price

编码

可以使用object encoding命令查看键的值的编码，比如object encoding price

字符串对象

1. 字符串对象可以用int, raw和embstr来编码，
2. 当设置的key是number的时候就会使用int编码，但是当变为字符串的时候就会选择使用embstr或者raw来进行编码，字符串的长度大于32字节的时候会选择raw
3. 而embstr和raw的区别是，raw是sds结构，内存分配的时候会分配2次，一次给redisObject另一次给sdshdr结构，而embstr分配一次将2个结构放在同一块内存中，embstr分配次数会少，释放对应也少，然后两个结构的内存有连续性可以更好的利用缓存
4. 可以用long double类型标识浮点数作为redis的字符串的值来保存，一般再进行浮点数运算的时候，将字符串类型的浮点数和浮点数进行计算会自动转化位long duuble计算完了后又会存入字符串
5. embstr一般都是只读的，在修改后会直接变成raw然后进行修改

列表对象

列表对象由ziplist或者linkedlist编码

ziplist

linkedlist

linkedlist会嵌套redis的StringObject对象

编码转化

同时满足一下两个条件的时候列表使用ziplist编码

1. 列表对象的所有字符串元素的长度都小于64字节
2. 列表对象保存的元素数量小于512个 我们知道ziplist会有连锁更新问题，但是因为redis这里限制了数量和大小所以触发的连锁更新并不会消耗很多性能

hash对象

哈希对象使用ziplist或者hashtable来编码

ziplist

hashtable

编码转换

当满足两个条件时，哈希对象使用ziplist编码

1. 哈希对象保存的所有键值对字符串长度都小于64字节
2. 键值对数量小于512个

集合对象

集合对象的编码可以是intset或者hashtable

当集合对象都是整数值，而且数量小于512个就会使用intset编码

有序集合对象

有序集合编码可以是ziplist或者skiplist

ziplist

skiplist

当使用skiplist编码的时候是会使用zset结构，该结构包含了skiplist和字典来实现，因为字典可以很快定位成员的分值，但是做区间计算的时候无法进行只能进行排序后获取，而skiplist作为支持有序集合查找和范围操作尽可以快的执行，所以redis使用字典和跳跃表来实现有序集合

转换

当元素数量小于128个，且成员的长度都小于64字节的时候使用ziplist

垃圾回收

因为c语言不具备内存回收功能，所以redis自己实现了一套引用计数的回收机制

对象共享

在回收机制之外，因为引入了对象引用计数的机制，然后对象可以在2个键中进行共享，当他们的值相同的时候他们的值可以指向同一块内存

对象的空转市场

redisObject中除了上面提到的对象还有lru这个属性，该属性记录了最后一次命令访问的时间，该空转时长还有另外一项作用，就是服务器设定了某种内存回收机制，就是当内存超过了maxmemory，空转时长比较高的那部分会优先丢弃从而回收内存

数据库

struct redisServer{
    // ...
    redis *db;
    int dbnum;
    // ...
}
typedef struct redisDb{
    // ...
    dict *dict
    dict *expries
    // ...
}

过期时间

redis有4个命令可以设置过期时间, expire pexpire expireat pexpireat, 本质上最终都是使用pexpireat命令来设置过期时间，不管是相对时间还是绝对时间，最终都是用绝对时间来进行设置，然后过期时间保存和key-value是不一样的，用的是redisDb中的expreies

过期时间删除策略

AOF和RDB复制功能对过期键的处理

1. 对于生成rdb文件，当有过期键的时候调用rdb生成命令不会将过期键保存到
2. 当载入rdb文件的时候，当是主服务载入rbd的时候会进行检查，没过期才会载入，当是从服务器载入的时候，主服务器进行同步的时候会发送指令将过期的删除
3. aof持久化模式的时候当某个键过期的时候虽然他没有删除，但是当删除后会给aof文件最佳一条del命令
4. 在主从复制的情况下，主服务删除了过期键会给从发送del命令，而从虽然知道过期了但是要等待主服务器发送del命令否则还是会给客户端返回对应过期的值

RDB持久化

rdb有3种

1. save命令会阻塞所有操作，知道生成完rdb文件后(备份完)
2. bgsave会启动一个子进程来进行生成备份，但是会阻塞其他所有备份操作，正常客户端操作可以进行
3. 根据配置文件定时和定量的进行自动备份，根据没多少秒对数据库多少次修改

dirty计数器和lastsave属性saveparams

dirty,saveparams和lastsave都是redisServer的属性，一个用来记录在备份期间有多少数据更新了，而lastsave是最后更新时间,saveparams用来记录定时定量备份用到的时间和更新次数从而知道什么时候能进行更新

rdb文件结构

1. redis就是redis字符串的二进制数据但是除了'\0'结尾符，长度5字节
2. db_version用来记录rdb的版本长度4字节
3. database包含了0个或多个数据库的键值对数据
4. EOF长度1字节来代表rdb文件正文内容的结束
5. check_sum是一个8字节长的无符号整数，一般存入的值是将其他4部分的数据进行校验和

database部分

1. selectdb长度位1个字节代表下面要读入的是数据库的号码
2. db_number保存的是数据库的号码，根据号码的长度保存的字节长度也不同
3. key_value_pairs保存了数据库种的所有键值对

key_value_pairs

1. EXPIRETIME_MS长度1字节代表下面的是过期时间
2. type其实就是上面提到的对象的编码(encoding)

AOF持久化

AOF的本质就是将每一条命令进行持久化，包括选择数据库的命令，然后有3种模式将AOF进行同步到磁盘的选项

1. always 每次都将缓冲区的内容写入aof文件种
2. everysec 距离上次同步超过一秒就进行同步，有专门的线程负责执行
3. no 就是磁盘什么时候决定将缓冲区存入磁盘

aof重写

aof重写就是假如有很多命令都是操作同一个key，那么重写的过程就会直接从数据库中拿到那个key的value, 然后生成一条这个value的命令来代替原来的多条命令，然后在重写期间，redis会创建一个子进程，因为子进程用的是进程的数据副本，不会有锁的冲突，这就有个问题就是主进程还在进行接收客户端命令，这边就需要一个临时的重写缓冲区来存储最新的命令，当子进程重写完成后，将缓冲区的命令追加到aof文件结尾就ok了，这样重写后的数据才不会不一致

客户端

服务端有一个指针用链表的形式保存了所有客户端的属性(也就是客户端的对象)

typeof struct redisClient {
    // ...
    int fd;
    robj *name;
    int flag;
    sds querybuf;
    robj **argv;
    int argc;
    struct redisCommand *cmd;
    char buf[REDIS_REPLY_CHUNK_BYTES];
    int bufpos;
    list *reply;
    int authenticated;
    time_t ctime;
    time_t lastinteraction;
    time_t dbuf_soft_limit_reached_time;
    // ...
}

1. fd用来表示客户端套接字，因为客户端是网络程序有文件套接字所以必大于-1，然后特殊的伪客户端(lua脚本，aof载入)等fd都是-1
2. name用来表示客户端的名称，默认客户端没有名称
3. flag用来表示客户端的状态，多个状态通过二进制或的操作
4. querybuf是输入缓冲区，里面存储了用户输入的命令以sds的形式保存
5. argv和argc就是对querybuf的解析，argv是数组每个项都保存一个字符串，argc保存的是长度
6. redisCommand就是对应argv的每项对应的实现函数
7. buf是客户端用来回复的缓冲区是固定大小一般默认是16kb，然后bufpos是多少个元素
8. reply是个链表，当回复的大小超过了固定值就会用reply来回复
9. authenticated是对用户的权限校验0是校验过的，1是没有校验
10. ctime是客户端创建事件
11. lastinteraction最后一次互动事件
12. dbuf_soft_limit_reached_time第一次到达软限制的事件

复制

早期版本sync命令

如图，直接进行同步rdb文件，然后有新的数据就存放在缓冲区，最后同步下缓冲区的内容就Ok了，初次同步是这样，后续都在线的情况下，每当不同步，主服务都会发送不同步的命令给从服务进行执行，然后有个问题就是断线重连，每当重连后都会进行一次重新的rdb同步，虽然新增命令较少但是rdb太耗时耗力了，

新版psync

psync就增加2种模式

1. 完全重同步类似sync
2. 部分重同步

对于部分重同步，psync是这样设计的，每个服务都有一个偏移量，而主服务上有个复制挤压缓冲区，也就是下标是偏移量对应内容，然后各个服务之间会进行偏移量对比，发现少的时候从缓冲区里拿，发现缓冲区都找不到就直接完全重同步，然后还假如服务id这个字段，当从重连到主的时候发现id不一样直接完全重同步

事务

www.cnblogs.com/DeepInThoug…

每个客户端都有一个multistate msstats的属性用来表示事务状态

typedef struct multistate{
    // ...
    multiCmd *commands;
    int counts;
    // ...
}

typedef struct multiCmd {
    // ...
    robj **argv;
    int argc;
    struct redisCommond *cmd;
    // ...
}

1. commands其实就是一个multiCmd数组，counts用来表示数组的长度
2. multiCmd保存了事务中每行命令的argv和argc和rediCommond
3. 事务的本质就是队列，然后当redis在运行队列中的命令的时候不会执行其他的命令，只会等到执行完队列中的命令

watch

watch本质其实就是在redisDb中有一个字典表，里面对应的就是监听的key, 在进行命令操作对应的key的时候会去监听字典表中看是否有客户端监听，当有监听就会去打开对应的客户端的REDIS_DIRTY_CAS的flag, 当事务看到flag是打开的时候就会报错这行命令

事务的ACID

redis的事务本质就是保证一致性和隔离性，而原子性因为没有回滚一行命令出错不会影响下面的命令执行，redis将这种错误称之为程序错误，不应该出现在生产环境，而持久性是根据rdb和aof的策略来判定的，当每次事务完成都会进行落盘的操作就可以拥有持久性，而隔离性因为是单线程所以天生具有隔离性，一致性是说数据没有错误和非法数据，因为redis的单挑命令是原子的，当是命令错误的时候这条命令不会执行保证了一致性，当服务宕机的时候，不管有没有被落盘数据都不会错误，要不就是丢失，然后就是入队错误也就是非法命令，redis会在事务之前检验所有命令，所以不会有问题