redis之数据结构探究-白红宇

redis之数据结构探究

阅读量：4221 次

发布时间：2019-05-26

本文共 4610 字，大约阅读时间需要 15 分钟。

　　在了解redis之前，先要知道一个概念：分布式内存对象缓存系统。起什么作用呢？用于将需要即时处理的一些数据放入到内存中，通过在快速的内存中进行访问，减少了链接数据库需要的时间和空间开销，也大大提高了访问效率。现在常用的有memchahed，还有就是这里要说的redis。redis相对memcached支持更多的数据结构，支持数据的备份（内部有一个主从机制），支持数据的持久化（持久化有AOF和RDB两种模式，以后会提到）

　　那咱们这里来讲讲redis所谓的多种数据结构和底层数据结构支持。

　　Redis是一个key-value数据库，键值对，它的键是string类型（它底层是用C写的，大家也都知道C哪来的sttring，说到底这里应该是C风格的字符数组，但是如果直接使用C风格的字符串，那会带来很多问题，这里redis的作者封装了一下C风格字符串(char *)，使得它有了许多其他操作），而它的值支持５种数据结构：1.字符串 2.哈希表(map映射) 3.列表(list) 4.集合(set) 5.有序集

　　这一节我们只需要知道redis的值支持这５中上层数据的存储，过后会再研究，这里我们来看它的底层数据结构支持，也就是内部实现：

　　一：首先来将上面特别提到的封装char *（C语言中是以'\0'为结尾标识的char *）。

　　　　怎么封装的呢？redis中管它叫做SDS---简单动态字符串。　　　

　　　　内部结构：（内部实现不仅仅下面这简单的几行，这只是sdshdr的结构，后面的方法中根据传入的sds，redis重写了一个内存申请的模块叫做zmalloc，对这个char*重新操作，分配内存和维护len以及sdsfree操作(针对free的操作)）

typedef  char*  sds;struct   sdshdr{            unsigned   int   len;            unsigned   int   free;            char   buf[];};

　　　　如上所示，一个len表示sds的长度（在插入的时候直接定位到要插入的位置），一个free用于以后的append（当数据超过某个阀值，进行翻倍叠加，和vector容器类似申请两倍的内存）

　　　　　至于为什么要这么做呢？之前也提到过直接使用char *会带来很多的问题：

　　　　　　1.char *的求长度操作是O(N)，append操作会引起N次remalloc（动态内存调整，增加分配内存）。而我们实际应用中需要大量的对key值进行操作，这样一来，那基本分分钟死机。使用len来操作则会使上面两种操作均为O(1)。这样效率就可观了。

　　　　　2.redis进程之间存在通信，client和server端，需要遵守一些传输协议（RESP），所有数据必须是二进制的，保证安全（与字符串操作函数有关系，因为对于二进制数据，程序不会对其进行特殊字符解释操作，得到的数据都是最原始最安全的）。

　　　　　　放到redis中是因为重新定义的sds，封装了char *之后，我们有了len，意味着我们所有的操作都以这个len为核心。字符串不会以"\0"作为结束标识。这里的安全就是输入任何字节都能正确处理，就算包含\0。

　　　二：双端链表。

　　　　　这个就很好理解了，学过数据结构就差不多了。

　　　　　它拥有两个指针，一个指向链表头，一个指向链表尾。每个节点带有前驱和后继指针，所以它是双向的。对头或者尾的操作均是O(1)，一步完成。其余就是链表的性质了。

　　　　　当然，内部也有一个len保存节点的数目，通过len又会使很多操作优化，我们只需要维护这个len。

　　　三：字典（重头戏）

　　　　　定义：由键值对构成的抽象数据结构

　　　　　redis中的数据库（看看这可是数据库）和哈希键值对都基于字典的实现--->>而字典的底层实现是啥呢？哈希表，所以这个字典数据结构也被叫做Map。

　　　　　下面看两张图片，能很快的了解这层层递进的关系：

　　　　从上面可以很清楚地看出来，redis数据库的主体是基于其结构中的dict，从第一张图可以看出它包含了所有的键值对数据

（也就是整个redis的真实数据全在这）。第一张图其他的一些过期时间，watched_keys，阻塞命令都是和客户端操作键值对的动作

有关，这里不讨论，主要看其数据结构dict。

　　　　从第二张图，我们能看出来一个包含２张hashtable表：ht[0] // ht[1]，２张哈希表的目的是实现动态的伸缩数据库大小

（rehash），优化它的效率.。

哈希表的实现如下：

typedef   struct   dictht{              dictEntry   **table;                    //hash表节点指针数组              unsigned   long   size;                  //指针数组长度              unsigned   long   sizemask;                 //长度掩码，用于计算索引值，快速定位查找              unsigned   long   used;                   //现有的节点数量}dictht;

　　　　字典是基于hashtable实现的，那么ht的实现了？这时候就到了最底层的东西，哈希表中包含了一大堆的指针，指向物理上

的数据地址，也就是哈希表节点：

typedef   struct   dictEntry{               void*   key;               union{                     void*  val;                     uint64_t   u64;                     int64_t     s64;                 }v;struct   dictEntry  *next;}dictEntry;

　　　现在看上面的代码是不是很简明易懂呢？注意其中的next指针是为了解决多个不同键拥有相同哈希值的时候的处理方法，将

后来的键放在next位置。数据结构有两种解决哈希冲突的方法，这就是其中一种，拉链法

　　　　但是如果节点数量比哈希表大大小大很多的话，那么哈希表就会退化成多个链表，这样一来哈希表本身的７优势便不再那么

突出，就成了类似链表的效率，这怎么可以叫哈希呢？所以才有了对应的rehash。

　　　　针对上面的rehash，我们都知道，一个hash表的比率（used/size==1）的时候，效率是最好的，一般都是O(1)，当链表变

长之后那就不知道是啥样了.....

　　　　我们假设比率为radio:

　　　　　1.radio>=1 ,并且dict_can_resize为true，自然rehash

　　　　　2.radio > dict_force_resize_radio(一般为５)，强制rehash

　　　　　　　rehash的过程在网站上也能找到很多，这里简要说一下　：

　　　　　　　　1.创建一个比ht[0]->table更大的ht[1]->table（根据情况，但是起码两倍，和vector类似）

　　　　　　　　2.将ht[0]->table中的所有键值对都迁移到ht[1]->table