Redis设计与实现2020-12-25演讲人目录数据结构与对象1单机数据库的实现2多机数据库的实现3独立功能的实现401数据结构与对象数
据结构对象（RedisObject）数据结构与对象特性编码类型与对应的数据结构数据结构与对象数据结构030102字典(map)简单
动态字符串（SDS）双端链表(list)060405跳跃表(skiplist)整数集合(intset)压缩列表(ziplist)简
单动态字符串（SDS）结构：sdshdr{intlen：记录buf数组中已使用字节数量intfree：记录buf
数组中未使用字节数量charbuf[]：字节数组，用于保存字符串（用来保存一系列的二进制数据）}对比C字符串的优点：1、
杜绝缓冲区溢出：会先检查空间十分满足，如果不满足的话会扩展2、减少修改字符串带来的内存重分配次数：空间预分配：len小于1MB，
那么会分配和len属性同样大小的未使用空间，free和len相同；如果len大于等于1MB，那么会分配1MB的未使用空间惰性空间
释放：并不会立即内存重分配来回收缩短多出来的字节，而是使用free记录下来，再下次增长操作会用上，避免了频繁的内存重分配，在有需
要的时候可以调用api真正的释放未使用空间二进制安全：会处理二进制的方式来处理SDS放在buf数字里简单动态字符串（SDS）作用
保存字符串，作为缓存区结构：链表节点的结构：listNode{listNodeprev：前置节点listNod
enext：后置节点voidvalue：节点的值}链表的结构：list{listNodehead：头
节点listNodetail：尾节点longlen：链表包含的节点数量}双端链表(list)作用：发布与订阅、
慢查询、监视器；保存多个客户端的状态信息，客户端输出的缓冲区结构：dict{dictTypetype：类型特定函数
voidprivdata：私有数据dicththt[2]：哈希表，一个rehash用inttrehashid
x：rehash索引，没在rehash为-1}dictht{dictEntrytable：哈希表数组lon
gsize：哈希表大小longsizemask：哈希表大小掩码，用于计算索引值，总是等于size-1longus
ed：该哈希表已有的节点数量}dictEntry{voidkey：键union{voidva
luint64_tu64int64_ts64}值dictEntrynext：下一个哈希节
点，形成链表}字典结构哈希表结构哈希表节点结构字典(map)哈希算法成功hash=dict.type.hashFuncti
on(key)index=hash&dict.ht[x].sizemask：x为0或1MurmurHash2是
一种非加密型哈希函数，适用于一般的哈希检索操作。与其它的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特
征表现更良好字典(map)链地址法（separatechaining）,用next来形成一个链表，因为没有表尾指针，为了速
度，新节点放在链表的表头（头插法）解决hash冲突负载因子的计算：load_factor=ht[0].used/ht[0]
.size扩展扩展条件ht[1]的大小为第一个大于等于ht[0].used2的2的n次幂，比如ht[0].used=6,则
ht[1].size=16>=62收缩收缩条件：当负载因子小于0.1时，会自动对哈希表收缩ht[1]的大小为第一个大于
等于ht[0].used的2的n次幂比如ht[0].used=6,则ht[1].size=8>=6过程当ht[0]中的
所有键值对都迁移到了ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上
当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变空表），释放ht[0]，将ht[1]设置为ht[0]。并在ht[
1]新创建一个空白的哈希表，为下次rehash做准备重新散列（rehash）渐进式rehash扩展和收缩需要将ht[0]里面的所有
的键值对rehash到ht[1]里面，但是这个rehash动作并不是一次性、集中性的完成，而是分多次、渐进式的完成的如果要一
次性的将这些键值对全部rehash到ht[1]中，庞大的计算量可能会导致服务器在一段时间内停止服务，所以分多次、渐进式渐进式re
hash4个步骤1、为ht[1]分配空间，让字典同时持有ht[0]和ht[1]俩个哈希表2、在字典中维持一个索引计数量rehas
hidx,并把它从-1设置为0，表示rehash工作正式开始3、在rehash进行期间，每次对字典执行的任何（读写）操作，程序除了
执行指定的操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当完成后，再将reh
ashidx属性的值增一（每次操作的记录，类似循环i++）4、随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对
rehash到ht[1]，这时将rehashidx设置为-1，表示完整的rehash操作已完成了优点：采用分而治之的方式，将reh
ash键值对所需的计算工作均摊到对字典的每个读写操作上，从而避免了集中式的rehash而带来的庞大计算量渐进式rehash在渐进式
rehash执行期间，字典会同时使用ht[0]和ht[1]俩个哈希表，删、改、查会在俩个哈希表上进行，会先在ht[0]查找，没找
到会继续到ht[1]里面查找，而新添加到字典的键值对一律会被保跳跃表(skiplist)跳跃表结构skiplist{zs
kiplistNodeheader：表头节点zskiplistNodetail：表尾节点longlength
：节点的数量（表头节点不算在内）intlevel：表中层数最大的节点层数（表头节点不算在内）}跳跃表节点结构层：lev
el数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，层的数量越多，访问其他
节点的速度就越快。每次创建新的跳跃表节点，就会随机生成一个1-32之间的值，就是层的高度前进指针：level[i].foward，
用于从表头向表尾方向访问节点跨度：level[i].span，用于记录俩个节点之间的距离，计算排位rank后退指针：backwar
d，用于从表尾向表头方向访问节点分值：score，是一个double类型的浮点数，跳跃表的所有节点都按分值从小到大排序跳跃表节点成
员：obj，是一个指针，他指向一个字符串对象，而字符串对象保存着一个sds值画外音：在同一个跳跃表中，各个节点保存的成员对象必须是
唯一的，但是多个节点保存的分值可以是相同的，分值相同的节点将按照成员对象在字典序的大小来从小到大排序跳跃表节点结构zskipli
stNod{zskiplistNodebackwawrd：后退指针doublescore：分值robj
obj：成员对象zskiplistLevel{zskiplistNodeforward：前进指针
intspan：跨度}leve[]：层}整数集合(intset)结构intset{uint32_tenco
ding：编码方式，16，32，64uint32_tlength：集合包含的元素数量int8_tcontents[
]：保存元素的数组是整数集合的底层实现，各个项在数组中按值的大小从小到大有序的排列并且不包含任何的重复项}升级
当将一个新元素添加到整数集合中，并且新元素的类型比整数集合现所有的元素的类型都要长时，整数集合需要先进行升级，才能将新元素添加到整
数集合中3个步骤1、根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间2、将底层数组现有的所有元素都转换成新
元素的相同的类型，并将类型转换后的元素放在正确的位置上，而且在放置元素的过程中，需要继续维持底层数组的有序性3、将新元素添加到新底
层数组中好处：提升整数集合的灵活性，尽可能的节约内存整数集合(intset)降级整数集合不支持降级操作，一旦对数组进行了升级，编
码就会一直保持升级后的状态压缩列表(ziplist)是一系列特殊编码的连续内存块的顺序型数据结构，为了节约内存而开发组成部分zlb
yteuint32_t4字节：记录整个压缩列表占用的内存字节数；内存重分配和计算zlend的位置用到zltailui
nt32_t4字节：记录压缩列表表尾点的距离压缩列表的起始地址有多少字节通过这个偏移量，无线遍历整个压缩列表就可以确定表尾节
点的地址zllenuint_16_t2字节：记录了压缩列表包含的节点数量entryX列表节点不定压缩列表包
含的各个节点，节点长度又节点保存的内容决定节点构成zlenduint8_t1字节：特殊值0xFF，用于标记压缩列表的末端
压缩列表(ziplist)连锁更新添加新节点、删除新节点都可能会引发连锁更新，在连续多个处于临界长度（254字节）才会发生，所以
并不多见数据结构与对象对象（RedisObject）01结构02查看键对应的值对象类型命令：typekey03字符串对象（st
ring）04列表对象（list）05哈希对象（hash）06集合对象（set）数据结构与对象对象（RedisObject）有序集
合对象（zset）结构redisObject{unsignedtype：类型（typekey）unsigned
encoding：编码(objectencodingkey)voidptr：指向底层实现数据结构的指针in
treference：引用计数unsignedlru：最后一次被访问的时间}编码embstr：简单动态字符串raw：
简单动态字符串int：使用整数值字符串长度小于等于39通过调用一次内存分配来分配一块连续的空间，依次包含redisObejct和
sdshdr俩个结构，释放也只需要调用一次只读的，有修改会变成raw长度大于39会调用俩次内存分配来分别分配redisObject
和empstr结构，需要调用俩次内存释放列表对象（list）ziplist：压缩列表linkedlist：双端列表编码020104
03list-max-ziplist-value和list-max-ziplist-entries可修改上面的值同时满足所有字
符串元素的长度都小于64字节，元素数量小于512个则使用ziplist编码，否则使用linkedlist编码哈希对象（hash）编
码ziplist：压缩列表hash-max-ziplist-value和hash-max-ziplist-entries可修
改上面的值14ht：字典同时满足所有的键值对的字符串长度都小于64字节，键值对数量小于512个则使用ziplist，否则使用has
htable23集合对象（set）编码intset：整数集合set-max-inset-entries可修改14ht：字典同时满
足所有的元素都是整数值，并且元素数量不超过512个，则使用intset，否则使用ht23编码ziplist：压缩列表skipli
st：跳跃表和字典无论单独使用跳跃表还是字典对比同时使用俩种都有性能降低zset{dict：字典skiplist：
跳跃表}同时满足元素数量小于128个，并且所有元素成员的长度都小于64字节，则使用ziplist，否则使用skiplistzs
et-max-ziplist-entries和zset-max-ziplist-value可修改12查看键对应的值对象的编
码：objectencoingkeyRedis_Encoding_Int：long类型的整数数据结构与对象34Redis_En
coding_Embstr：embstr编码的简单动态字符串Redis_Encoding_raw：简单动态字符串编码类型与对应的数
据结构56Redis_Encoding_Ht：字典Redis_Encoding_Linkedlist：双端链表Redis_Enco
ding_Ziplist：压缩列表01数据结构与对象Redis_Encoding_Intset：整数集合02编码类型与对应的数据结
构Redis_Encoding_Skiplist：跳跃表和字典03数据结构与对象特性类型检查命令多态内存回收ABC对象共享对象的空
转时长DE类型检查根据redisObejct.type来实现有的命令只能对特定类型键执行，否则返回一个类型错误命令多态1基于类型
的多态：del、expire2基于编码的多态：llen内存回收引用计数（referencecounting）创建新对象会初始化为
11被新程序使用会被增一2查看值命令：objectrefcountkey5当对象不再被一个程序使用，计数值会减一3值变为0，对
象占用的内存会释放4对象共享01将键的值指针指向一个现有的值对象，将被共享的值对象的引用计数增一02对节约内存有帮助03Redis
在初始化服务器的时候，会创建一万个字符串对象，从0到999904只有在共享对象和目标对象完全相同的情况下，程序才会将共享对象作为键
的值对象对象的空转时长查看键的空转时长：objectidletimekey跟内存回收有联系02单机数据库的实现单机数据库的实现
数据库RDB持久化AOF持久化单机数据库的实现数据库结构键的生存时间和过期时间过期键的删除策略结构客户端结构服务器结构redis
Client{redisDbdb：记录客户端当前正在使用的数据库}selectnum切换目标数据库redisSe
rver{redisDbdbs：一个数组，保存着服务器所有的数据库intdbnum：服务器数据库数量，默认是1
6saveparamsaveparams：记录保存条件的数组longlongdirty：修改计数器tim
e_tlastsave：上次执行保存的时间}结构数据库结构redisDb{dictdict：字典，数据库键空间
，保存着数据库中所有的键值对键空间的键也就是数据库的键，每个键都是一个字符串对象；键空间的值也就是数据库的值，
每个值可以是任意一种RedisObject对象dictexpires：过期字典，保存着键的过期时间，毫秒精度的unix时
间戳}键的生存时间和过期时间设置过期时间expire<key><ttl>命令用于将键key的生
存时间设置为ttl秒pexire<key><ttl>命令用于将键key的生存时间设置为ttl毫秒ex
pireat<key><timestamp>命令用于将键key的生存时间设置为timestamp所指
定的秒数时间戳pexpireat<key><timestamp>命令用于将键key的生存时间设置为t
imestamp所指定的毫秒数时间戳画外音：无论执行的是以上4个命令的哪一个，经过转换后，最终的效果都和执行pexpireat命令
一样保存过期时间：在dictexpires结构中存储定时删除01RDB、AOF、和复制功能对过期键的处理惰性删除过期键的删除
策略05020403Redis的使用定期删除过期键的删除策略定时删除在设置键的过期时间同时创建一个定时器（time），让定时器在键
的过期时间来临，立即执行键的删除操作对内存的友好的，很快的删除释放内存；但是对cpu是不友好的，在定时器删除键会对服务器的响应时间
和吞吐量造成影响过期键的删除策略惰性删除放任键过期不管，但是每次从键空间中获取键时，都检查获取的键是否过期，如果过期则删除该键，否
则返回对Cpu时间是友好的，只会在读取的时候会有额外删除操作；但是对内存是不友好的，如果一直没有读取到，就会一直存储在内存中，除非
是用户手动去scan扫描读取、触发删除，可以看成一种内存泄露过期键的删除策略定期删除每个一段时间程序就对数据库进行一次检查，删除里
面的过期键，至于删除多少和检查多少，由算法决定对内存和cpu相对来说都是友好的，每隔一段时间来执行删除过期键的操作来减少内存浪费，
并通过限制删除操作的执行时长和频率来减少删除操作对Cpu的影响过期键的删除策略Redis的使用惰性删除和定期删除俩种策略，
通过俩种策略来合理使用cpu和避免浪费内存去的平衡惰性删除策略的实现：expireIfNeeded函数实现，过期则删除，否则正常处
理定期删除策略实现：activeExpireCycle函数实现，他在规定的时间内，遍历服务器的所有数据库，从数据库的expire
s字典中随机检查一部分键的过期时间，并删除其中的过期键，当到了时间会记录当前遍历的数据库current_db，下次就直接从这个db
开始，所有遍历一遍current_db会被置零过期键的删除策略RDB：已过期的键不会被包含到新创建的RDB文件中，从服务器载入不关
系是否过期都会载入数据库中AOF：已过期的键不会被保存到重写后的AOF文件中，当键别策略删除，程序会想AOF文件追加一个del命令
复制：在复制模式下，从服务器的过期键删除动作都由主服务器控制，在主服务器删除一个键后，会显式的向所有从服务器发送一个del命令通知
从服务器删除该键。从服务器在读到已过期未删除的键，不会主动删除该键，而是像处理未过期的键一样来处理（也就是说从服务器上可能读到已
过期未删除的键，是一个bug，在3.2版本中修复了），这种统一、中心化的过期键删除策略可以保证主持服务器的数据一致性RDB、AO
F、和复制功能对过期键的处理单机数据库的实现RDB持久化成功SAVE：会阻塞Reids服务器进程，直到RDB文件创建完毕，这个期间不能处理任何命令请求BGSAVE：会派生一个子进程，子进程负责创建RDB文件，父进程继续处理命令请求服务器启动载入会先判断是否开启AOF持久化，如果开启则载入AOF文件，否则载入RDB文件（因为AOF文件的更新频率通常比RDB文件要高）自动间隔性保存RDB持久化SAVE：会阻塞Reids服务器进程，直到RDB文件创建完毕，这个期间不能处理任何命令请求RDB持久化BGSAVE：会派生一个子进程，子进程负责创建RDB文件，父进程继续处理命令请求RDB持久化服务器启动载入会先判断是否开启AOF持久化，如果开启则载入AOF文件，否则载入RDB文件（因为AOF文件的更新频率通常比RDB文件要高）自动间隔性保存条件结构saveparam{intseconds：秒数intchanges：修改数}通过检查条件redisServer.saveparams、修改计数器dirty、上次执行save或bgsave命令的时间lastsave来判断是否需要自动执行bgsave命令来保存03多机数据库的实现多机数据库的实现04独立功能的实现独立功能的实现感谢聆听 |
|
