[Redis]Redis的设计与实现-链表/字典/跳跃表

redis的设计与实现: 1.假如有一个用户关系模块,要实现一个共同关注功能,计算出两个用户关注了哪些相同的用户,本质上是计算两个用户关注集合的交集,如果使用关系数据库,需要 对两个数据表执行join操作,对合并的结果执行去重distinct操作,非常复杂 2.Redis直接内置了集合数据类型,支持对集合执行交集/并集/差集等集合计算操作,交集操作可以直接用于共同关注功能,使用之后速度更快代码量更少,可读性大大提高 3.越来越多的疑问:五种数据类型是由什么数据结构实现的?字符串数据类型既可以存储字符串,又可以存储整数浮点数,二进制位,在内部是怎么存储这些值的? 有些命令只能对特定数据类型执行,是如何进行类型检查的?怎样存储各种不同类型的键值对?过期键是怎样实现自动删除的?发布与订阅/脚本/事务等特性是如何实现的?使用什么模型处理客户端的命令请求?一条命令从发送到返回需要经历的步骤? 4.第一版发布的时候还不是很完善,作者一边注释源码一边写,只介绍了内部机制和单机特性,新版添加了关于二进制位操作/排序/复制/Sentinel和集群等主题的新章节 5.数据结构与对象,单机数据库的实现,多机数据库的实现,独立功能的实现 6.数据库里面的每个键值对都是由对象组成的:数据库键总是字符串对象;键的值可以是字符串对象/列表对象(list object)/哈希对象(hash object)/集合对象(set object)/有序集合对象(sorted set object),这五种中的其中一种 7.第一部分和第二部分单机功能比较重要:第一部分,简单动态字符串,链表,字典,跳跃表,整数集合,压缩列表,对象 8.Redis自己构建了一个SDS的类型用来保存所有的字符串对象,包括键值对的键,值中存储字符串对象的底层也是SDS

redis的设计与实现-链表 1.链表提供了高效的节点重排能力,顺序性的节点访问方式,通过增删节点调整链表的长度,C语言不内置,Redis构建了自己的链表实现 2.列表键的底层实现之一就是链表,当元素比较多,元素都是比较长的字符串,就会使用链表作为底层实现 3.发布与订阅,慢查询,监视器等功能也用到了链表,redis本身使用链表保存多个客户端的状态信息 4.每个链表节点使用adlist.h/listNode结构表示,通过prev和next指针组成双端链表;使用adlist.h/list结构操作更方便,提供了表头指针head,表尾指针tail,长度计数len,特定类型的函数等 5.链表表头前置和表尾后置都是指向null,所以是无环链表,设置不同类型特定函数,可以用于保存不同类型的值 字典 1.字典,又称为符号表/关联数组/映射,保存键值对的抽象数据结构;一个键和一个值进行关联,或者叫键映射为值 2.redis的数据库就是使用字典作为底层,对数据库的增删查改操作也是构建在对字典的操作之上;字典还是哈希键的底层实现 3.redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,每个哈希表节点保存了字典中的一个键值对 4.redis字典所使用的哈希表由dict.h/dictht结构,table属性是一个数组,每个元素都是指向dict.h/dictEntry结构的指针.每个dictEntry结构保存一个键值对 5.哈希表节点使用dictEntry结构表示,key属性保存着键值对中的键,v属性保存着键值对中的值,键值对的值可以是指针或整数,next属性是指向另一个哈希表节点的指针,以此解决键冲突,通过next指针将两个索引值相同的键k1和k0连接在一起 6.Redis字典由dict.h/dict结构表示,type属性和privdata属性是针对不同类型的键值对,为创建多态字典设置;ht属性是一个包含两个项的数组,每一项都是dictht哈希表,一般只使用ht[0],ht[1]只会在哈希表进行rehash的时候使用,rehashidx记录rehash的进度 7.哈希算法-将一个新的键值对添加到字典里面时,先根据键计算出哈希值和索引值,根据索引值将一个新键值对的哈希表节点放到哈希表数组的指定索引上 hash=dict->type->hashFunction(key);index=hash&dict->ht[x].sizemask Redis使用了MurmurHash2算法来计算键的哈希值 8.解决键冲突,使用了链地址法,被分配到同一个索引的多个节点可以用单向链表连接起来 9.哈希表保存的键值对逐渐增多或者减少,为了让哈希表的负载因子维持在一个合理的范围内,程序对大小进行扩展或者收缩

redis的设计与实现-跳跃表 1.跳跃表(skiplist)是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,达到快速访问其他节点的目的,跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作批量处理节点

1.跳跃表(skiplist)大部分情况下效率可以和平衡树媲美,并且比平衡树要简单 2.Redis使用跳跃表作为有序集合键的底层实现之一,在内部的集群节点中也有使用 3.比如zrange fruit 0 2 withscores 水果名是成员,水果价钱是分数值,每个水果存储在跳跃表节点中,价钱由低到高排序 4.redis跳跃表由redis.h/zskiplist和redis.h/zskiplistNode两个结构定义,zskiplist包含,header指向表头节点,tail指向表尾节点,length跳跃表的长度,level节点中最高层数 zskiplistNode结构包含,level表示层每层都有前进指针和跨度指向下一个节点,backward表示后退指针,score表示分值,obj表示成员对象;遍历时这些前进指针和后退指针就能启动快速访问的目的 5.迭代程序遍历跳跃表的时候只与前进指针有关,每个层的跨度与节点在跳跃表中的排位有关,每个节点的层高在1-32之间的随机数