Redis设计与实现（一）、内部数据结构

| 分类 redis  | 标签 redis 

###前言

项目中用到了redis，但用到的都是最最基本的功能，比如简单的slave机制，数据结构只使用了字符串。但是一直听说redis是一个很牛的开源项目，很多公司都在用。于是我就比较奇怪，这玩意不就和 memcache 差不多吗？仅仅是因为memcache是内存级别的，没有持久化功能。而redis支持持久化？难道这就是它的必杀技？

带着这个疑问，我在网上搜了一圈。发现有个叫做huangz的程序员针对redis写了一本书叫做《redis设计与实现》，而且业界良心搞了一个reids2.6版本的注释版源码。这本书不到200页，估计2个星期能看完吧，之后打算再看下感兴趣部分的源码。当然，如果你不知道redis是干嘛的，请自行谷歌，简单说就是Key-Value数据库，而且 value 支持5种数据结构：

  1. 字符串
  2. 哈希表（map）
  3. 列表（list）
  4. 集合（set）
  5. 有序集

下面我们就从 redis 的内部结构开始说起吧：）

###一、redis内部数据结构

首先需要知道，redis是用C写的。众所周知，任何系统对于字符串的操作都是最频繁的，而恰巧C语言的字符串备受诟病。然后作者就封装了一下 C 语言的字符串 char *。

总之，根据redis的业务场景，整个redis系统的底层数据支撑被设计为如下几种：

  • 简单动态字符串sds(Simple Dynamic String)
  • 双端链表
  • 字典(Map)
  • 跳跃表

下面我们就分别来说说这4种数据结构。

####1. 简单动态字符串sds

  • redis的字符串表示为sds，而不是C字符串（以\0结尾的char*）
  • 对比C字符串，sds有以下特性
    • 可以高效执行长度计算O(1)
    • 可以高效执行append操作(通过free提前分配）
    • 二进制安全
  • sds会为追加操作进行优化，加快追加操作的速度，并降低内存分配的次数，代价是多占用内存，且不会主动释放

这个一看名字就能知道个大概了，因为字符串操作无非是增删查改，如果使用char[]数组，那是要死人的，任何操作都是O(N)复杂度。所以，要对某些频繁的操作实现O(1)级性能。但是我们还是得思考：

为什么要对字符串造轮子？

因为redis是一个key-value类型的数据库，而key全部都是字符串，value可以是集合、hash、list等等。同时，在redis的各种操作中，都会频繁使用字符串的长度和append操作，对于char[]来说，长度操作是O(N)的，append会引起N次realloc。而且因为redis分为client和server，传输的协议内容必须是二进制安全的，而C的字符串必须保证是\0结尾，所以在这两点的基础上开发sds

知道了上面几点就可以看下实现了，其实实现特别简单。它通过一个结构体来代表字符串对象，内部有个len属性记录长度，有个free用于以后的append操作，具体的值还是一个char[]。长度就不说了，只在插入的时候用一下，以后只需要维护len就可以O(1)拿到；对于free也很简单，vector不也是这么实现的嘛。就是按照某个阈值进行翻倍叠加。

###2. 双端链表

  • redis自己实现了双端链表
  • 双端链表主要两个作用：
    1. 作为redis列表类型的底层实现之一
    2. 作为通用数据结构被其他模块使用
  • 双端链表及其节点的性能特征如下：
    • 节点带有前驱和后继指针
    • 链表是双向的，所以对表头和表尾操作都是O(1)
    • 链表节点可以会被维护，LLEN复杂度为O(1)

这玩意当时刷数据结构与算法分析那本书看过，但是没怎么用到过。说白了双端链表就是有2个指针，一个指向链表头，一个指向链表尾。对每个节点而言，记录自己的父节点和子节点，这样双向移动速度会快很多。

还是老问题：

为什么要有双端链表？

在Java或者C++中，都有现成的容器供我们使用，但是C没有。于是作者自己造了一个双端链表数据结构。而这个也是redis列表数据结构的基础之一（另外一个还是压缩列表）。而且双端链表也是一个通用的数据结构被其他功能调用，比如事务。

至于实现也是比较简单，双端链表，肯定有2个指针指向链表头和链表尾，然后内部维护一个len保存节点的数目，这样当使用LLEN的时候就能达到O(1)复杂度了。其他的，额，对每个节点而言，都有双向的指针，另外还有针对双端链表的迭代器，也是两个方向。

###3. 字典（其实说Map更通俗）

  • 字典是由键值对构成的抽象数据结构
  • redis中的数据库和哈希键值对都基于字典实现
  • 字典的底层实现为哈希表，每个字典含有2个哈希表，一般只是用0号哈希表，1号哈希表是在rehash过程中才使用的
  • 哈希表使用链地址法来解决碰撞问题
  • rehash可以用于扩展或者收缩哈希表
  • 对哈希表的rehash是分多次、渐进式进行的

这个虽然说经常用，但是对于redis来说确实是重中之重。毕竟redis就是一个key-value的数据库，而key被称为键空间(key space)，这个键空间就是由字典实现的。第二个用途就是用作hash类型的其中一种底层实现。下面分别来说明。

  1. 键空间：redis是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对应的字典，这个字典被称为键空间。当用户添加一个键值对到数据库（不论键值对是什么类型），程序就讲该键值对添加到键空间，删除同理。
  2. 用作hash类型键的其中一种底层实现：hash底层实现是通过压缩列表和字典实现的，当建立一个hash结构的时候，会优先使用空间占用率小的压缩列表。当有需要的时候会将压缩列表转化为字典

对于字典的实现这里简单说明一下即可，因为很简单。

字典是通过hash表实现的。每个字典含有2个hash表，分别为ht[0]和ht[1]，一般情况下使用的是ht[0],ht[1]只有在rehash的时候才用到。为什么呢？因为性能，我们知道，当hash表出现太多碰撞的话，查找会由O(1)增加到O(MAXLEN),redis为了性能，会在碰撞过多的情况下发生rehash，rehash就是扩大hash表的大小，从而将碰撞率降低，当hash表大小和节点数量维持在1：1时候性能最优，就是O(1)。另外的rehashidx字段也比较有看头，redis支持渐进式hash，下面会讲到原理。

下面讲一下rehash的触发条件：

当新插入一个键值对的时候，根据used/size得到一个比例，如果这个比例超过阈值，就自动触发rehash过程。rehash分为两种：

  • 自然rehash:满足used/size >= 1 && dict_can_resize条件触发的
  • 强制rehash:满足used/size >= dict_force_resize_ratio(默认为5)条件触发的。

思考一下，为什么需要两种rehash呢？答案还是为了性能，不过这点考虑的是redis服务的整体性能。当redis使用后台子进程对字典进行rehash的时候，为了最大化利用系统的copy on write机制，子进程会暂时将自然rehash关闭，这就是dict_can_resize的作用。当持久化任务完成后，将dict_can_resize设为true，就可以继续进行自然rehash；但是考虑另外一种情况，当现有字典的碰撞率太高了，size是指针数组的大小，used是hash表节点数量，那么就必须马上进行rehash防止再插入的值继续碰撞，这将浪费很长时间。所以超过dict_force_resize_ratio后，无论在进行什么操作，都必须进行rehash。

rehash过程很简单，分为3步：

  1. 给ht[1]分配至少2倍于ht[0]的空间
  2. 将ht[0]数据迁移到ht[1]
  3. 清空ht[0], 将ht[0]指针指向ht[1],ht[1]指针指向ht[0]

同样是为了性能（当用户对一个很大的字典插入时候，你不能让系统阻塞来完成整个字典的rehash。所以redis采用了渐进式rehash。说白了就是分步进行rehash。具体由下面2个函数完成：

  1. _dictRehashStep:从名字可以看出，是按照step进行的。当字典处于rehash状态(dict的rehashidx不为-1)，用户进行增删查改的时候会触发_dictRehashStep，这个函数就是将第一个索引不为空的全部节点迁移到ht[1]，因为一般情况下节点数目不会超过5(超过基本会触发强制rehash），所以成本很低，不会影响到响应时间。
  2. dictRehashMilliseconds:这个相当于时间片轮转rehash，定时进行redis cron job来进行rehash。会在指定时间内对dict的rehashidx不为-1的字典进行rehash

上面讲完了rehash过程，但是以前在组内分享redis的时候遇到过一个问题：

当进行rehash时候，我进行了增删查改怎么办？是在ht[0]进行还是在ht[1]进行呢？

redis采用的策略是rehash过程中ht[0]只减不增，所以增加肯定是ht[1]，查找、修改、删除则会同时在ht[0]和ht[1]进行。

Tips: redis为了减少存储空间，rehash还有一个特性是缩减空间，当多次进行删除操作后，如果used/size的比例小于一个阈值（现在是10%),那么就会触发缩减空间rehash，过程和增加空间类似，不详述了。

###3. 跳跃表

  • 跳跃表是一种随机化数据结构（它的层是随机产生的），查找、添加、删除操作都是O(logN)级别的。
  • 跳跃表目前在redis的唯一用处就是有序集类型的底层数据结构之一（另外一个还是字典）
  • 当然，根据redis的特性，作者对跳跃表进行了修改
    • socre可以重复
    • 对比一个元素需要同时检查它的score和member
    • 每个节点带有高度为1的后退指针，用于从表尾方向向表头方向迭代

redis使用了跳跃表，但是我发现。。。。我竟然不知道跳跃表是什么东东。亏我还觉得数据结构基础还凑合呢= =。于是赶紧去看了《数据结构与算法分析》，算是知道是啥玩意的。说白了，就是链表+二分查找的结合体。这里主要是研究redis的，所以就不细谈这个数据结构了。

和双端链表、字典不同的是，跳跃表在reids中不是广泛使用的，它在redis中的唯一作用就是实现有序集数据类型。所以等到集合的时候再深入了解。


上一篇     下一篇