江苏龙网

  1. 主页 > 生活百科 > >

你知道 Redis数据结构底层实现吗？一文详解，彻底弄懂

Redis

作者：JAVA知音
链接：https://www.cnblogs.com/javazhiyin/p/11063944.html
我们在面试时，常常可以遇到的面试题是关于redis，这是很多面试官都喜欢的一个部分 。而今天要讲的，是redis的底层数据结构，并非是我们所理解中的五大数据结构 。那么，redis底层数据结构到底是怎样的呢？你知道 Rdidis数据结构底层实现吗？
1. 字符串处理(string)我们都知道redis是用C语言写，但是C语言处理字符串和数组的成本是很高的，下面我分别说几个例子 。
没有数据结构支撑的几个问题
  1. 及其容易造成缓冲区溢出问题，比如用strcat()，在用这个函数之前必须要先给目标变量分配足够的空间，否则就会溢出 。
  2. 如果要获取字符串的长度，没有数据结构的支撑，可能就需要遍历，它的复杂度是O(N)
  3. 内存重分配 。C字符串的每次变更(曾长或缩短)都会对数组作内存重分配 。同样，如果是缩短，没有处理好多余的空间，也会造成内存泄漏 。
【你知道 Redis数据结构底层实现吗？一文详解，彻底弄懂】好了，Redis自己构建了一种名叫Simple dynamic string(SDS)的数据结构，他分别对这几个问题作了处理 。我们先来看看它的结构源码：
struct sdshdr{ //记录buf数组中已使用字节的数量 //等于 SDS 保存字符串的长度 int len; //记录 buf 数组中未使用字节的数量 int free; //字节数组，用于保存字符串 char buf[];}再来说说它的优点：
  1. 开发者不用担心字符串变更造成的内存溢出问题 。
  2. 常数时间复杂度获取字符串长度len字段 。
  3. 空间预分配free字段，会默认留够一定的空间防止多次重分配内存 。
更多了解：https://redis.io/topics/internals-sds
这就是string的底层实现，更是redis对所有字符串数据的处理方式(SDS会被嵌套到别的数据结构里使用) 。
2. 链表
Redis的链表在双向链表上扩展了头、尾节点、元素数等属性 。

你知道 Redis数据结构底层实现吗？一文详解，彻底弄懂

文章插图
 
2.1 源码
ListNode节点数据结构：
typedef struct listNode{ //前置节点 struct listNode *prev; //后置节点 struct listNode *next; //节点的值 void *value; }listNode链表数据结构：
typedef struct list{ //表头节点 listNode *head; //表尾节点 listNode *tail; //链表所包含的节点数量 unsigned long len; //节点值复制函数 void (*free) (void *ptr); //节点值释放函数 void (*free) (void *ptr); //节点值对比函数 int (*match) (void *ptr,void *key);}list;从上面可以看到，Redis的链表有这几个特点：
  1. 可以直接获得头、尾节点 。
  2. 常数时间复杂度得到链表长度 。
  3. 是双向链表 。
3. 字典(Hash)
Redis的Hash，就是在数组+链表的基础上，进行了一些rehash优化等 。

你知道 Redis数据结构底层实现吗？一文详解，彻底弄懂

文章插图
 
3.1 数据结构源码
哈希表：
typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used;} dictht;Hash表节点：
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; // 单链表结构} dictEntry;字典：
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;可以看出：
  1. Reids的Hash采用链地址法来处理冲突，然后它没有使用红黑树优化 。
  2. 哈希表节点采用单链表结构 。
  3. rehash优化 。
下面我们讲一下它的rehash优化 。
3.2 rehash
当哈希表的键对泰国或者太少，就需要对哈希表的大小进行调整，redis是如何调整的呢？
  1. 我们仔细可以看到dict结构里有个字段dictht ht[2]代表有两个dictht数组 。第一步就是为ht[1]哈希表分配空间，大小取决于ht[0]当前使用的情况 。
  2. 将保存在ht[0]中的数据rehash(重新计算哈希值)到ht[1]上 。
  3. 当ht[0]中所有键值对都迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并ht[1]初始化，为下一次rehash做准备 。
3.3 渐进式rehash
我们在3.2中看到，redis处理rehash的流程，但是更细一点的讲，它如何进行数据迁的呢？


推荐阅读


上一篇：几种常见的负载均衡算法的工作原理

下一篇：PHP防止跨站和xss攻击代码