本篇文章是基于作者黄建宏写的书 Redis 设计与实现而做的笔记
Redis 中数据结构的底层实现包括以下对象:
对象 | 解释 |
---|---|
简单动态字符串 | 字符串的底层实现 |
链表 | 列表的底层实现 |
字典 | 运用在多个方面,包括 Hash 的实现等 |
跳跃表 | 有序集合的底层实现 |
整数集合 | 集合的底层实现之一 |
压缩字典 | 列表键和哈希键的底层实现之一 |
Redis 中并没有直接使用 C 语言中的字符串,而是在其基础之上实现了字符串的数据结构,叫做简单动态字符串(SDS)。
其内部的定义为:
- /* Redis简单动态字符串的数据结构 */
- struct sdshdr {
- //字符长度,记录buf数组中已使用的字节数量
- unsigned int len;
- //当前可用空间,记录buf数组中未使用的字节数量
- unsigned int free;
- //具体存放字符的buf
- char buf[];
- };
链表提供了高效的结点重排能力,以及顺序性的结点访问方式,并且可以通过增删结点来灵活的调整链表的长度。
每个链表结点使用的是一个 listNode 结构表示:
- typedef struct listNode {
- // 前置结点
- struct listNode * prev;
- // 后置结点
- struct listNode * next;
- // 结点值
- void * value;
- }
在此基础之上,Redis 通过封装了 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 结构为链表提供了表头指针 head、表尾指针 tail,以及链表长度计数器 len,而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数:
Redis 的链表实现的特性总结如下:
字典由哈希表组成,而哈希表又由哈希结点组成。
和链表一样,Redis 也自己实现了哈希表结点结构和哈希表结构,如下:
哈希表结点:
- typeof struct dictEntry {
- //键
- void * key;
- //值
- union {
- void * val;
- uint64_tu64;
- int64_ts64;
- }
- struct dictEntry * next;
- }
每个 dictEntry 结构都保存着一个键值对,分别对应属性 key 和 value,同时,next 属性是指向另外一个哈希表结点的指针,作用就是将多个哈希值相同的哈希结点连接起来,以此来解决键冲突的问题。
Redis 在 dictEntry 的基础之上封装实现了哈希表,如下:
- typedef struct dictht {
- //哈希表数组
- dictEntry * *table;
- //哈希表大小
- unsigned long size;
- //哈希表大小掩码,用于计算索引值
- unsigned long sizemask;
- //该哈希表已有节点的数量
- unsigned long used;
- }
其中需要提到的是 sizemark,这个属性和哈希值一起决定一个键应该被放到 table 数组中的哪个索引上面。
Redis 在哈希表的基础上封装了 dictht 实现字典,如下:
- typedef struct dict {
- // 类型特定函数
- dictType * type;
- // 私有数据
- void * privedata;
- // 哈希表
- dictht ht[2];
- // rehash 索引
- int rehashidx;
- }
type 属性和 privdata 属性是针对不同类型的键值对,为创建多态字典而设置的。ht 属性是一个包含两个项的数组,数组中的每个项都是一个 dictht 哈希表,一般情况下,字典只使用 ht[0] 哈希表,ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用,而 rehashidx 则决定了 rehash 的进度,如果没有进行 rehash,其值则为 - 1。
当要把一个新的键值对添加到字典里面时,程序先要根据键值对中的键值计算出哈希值,再计算出索引值,然后将包含新键值对的哈希表结点放到哈希表数组的指定索引上面。
Redis 使用 murmurhash 算法来计算哈希值
键冲突:存在两个或者两个以上的键被分配到了哈希表数组的同一个索引上面。
解决办法:Redis 的哈希表使用开链法来解决冲突,每个哈希表结点都存在一个 next 指针,多个哈希表值可以用 next 指针来构成一个单向链表,被分配到同一个索引上的多个结点可以用这个单向链表连接起来,从而解决键冲突问题。
需要注意的是,因为考虑到下次方便再次读取,因此总是将冲突的新结点插入到链表的表头位置,也就是已有其他结点的前面。
当哈希表的负载因子(已有数量/表数量)达到一个阀值以后,再次保存新的键值对时,冲突的几率将逐渐增加,因此需要进行响应的扩展(收缩)。
以扩展为例,程序需要经过以下步骤(腾笼换鸟):
为了避免一次性交换所造成的性能影响,Redis 采用的是渐进式 rehash,也就是说,将会分多次、渐进式的完成数据的迁移。所以会同时存在两个哈希表数组,并不会急着一次性的将数 ht[0] 的数据迁移到 ht[1] 中,而是在每次操作的同时,将部分的 ht[0] 中的数据保存到 ht[1] 中,采用愚公移山的方式最终将 ht[0] 中的数据搬完,为了避免 ht[0] 中的数据不断增加,相关的增加的操作都会作用在 ht[1] 之上,最后,搬完后的操作和之前的操作是一致的。
它的优点在于:采用了分而治之的方式,将 rehash 键值对所需的操作均摊到字典的每个添加、删除、查找和更新操作之上,从而避免集中式 rehash 而带来的庞大计算量。
我认为它的缺点也是存在的,譬如在查询的时候,可能在 ht[0] 中查找不到,还得跑到 ht[1] 中查找,无形中增加了开销。
跳跃表是一种有序数据结构,它通过在每个结点中维持多个指向其它结点的指针,从而达到快速访问结点的目的。其查找的时间复杂度平均可以达到 O(logn),最坏 O(N),还可以通过顺序性操作来批量处理结点。
目前,Redis 中只有两个地方用到了跳跃表,一个是有序集合键,另外一个是集群结点中用作内部数据结构。
跳跃表由多个跳跃结点组成:
- typedef struct zskiplistNode {
- //层
- struct zskiplistLevel {
- //前进指针
- struct zskiplistNode * forward;
- //跨度
- unsigned int span;
- }
- level[];
- //后退指针
- struct zskiplistNode * backward;
- //分值
- double score;
- //成员对象
- robj * obj;
- }
- typedef struct zskiplist {
- //表头节点和表尾节点
- structz skiplistNode *header,*tail;
- //表中节点数量
- unsigned long length;
- //表中层数最大的节点的层数
- int level;
- }zskiplist;
其搜索的步骤为,先通过头结点定位到跳跃表结点,然后通过层去定位到下一个跳跃表结点的位置,直到找到给定分值的结点。
前提:当一个集合只包含整数值元素,并且这个集合的元素数量不多时。
- typedef struct intset {
- //编码方式
- uint32_t enconding;
- // 集合包含的元素数量
- uint32_t length;
- //保存元素的数组
- int8_t contents[];
- }
因为可能存在存入的整数不符合已存在集合中的编码格式,因此需要使用升级策略来解决。
一旦对数组进行了升级,编码就会一直保存升级后的状态。
压缩列表是 Redis 为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个结点,每个结点可以保存一个字节数或者一个整数值。
来源: http://www.cnblogs.com/George1994/p/7421001.html