本文主要描述reids数据结构和底层数据结构的实现，用于熟悉redis的底层数据结构实现原理，下图是reids的整个数据结构组成。这篇文章主要介绍value对象这部分数据结构

 

SDS初识

string结构对应底层SDS数据结构，SDS是redis最简单的数据结构，一般用于分布式锁和Json序列化对象存储。

SDS命令:

• 设置SDS的值 set <key> <value>：SET NAME XIAOMING

• 获取SDS值 get <key>：GET NAME
• 计数 incr <key>:INCR NUM
• 设置SDS过期时间 expire <key>：EXPIRE NAME 100
• 查看SDS过期剩余时间 ttl <key>：TTL NAME

 

C语言字符串的问题

• C语言中以”/0“识别字符串的结尾，redis可以存储任何文件，那特殊文件中数据就会有"\0"的存在，这样就会导致数据截断。
• C语言中获取字符串长度的时候，也是遍历字符集，判断到"\0"时就计算完毕，每次计算都是一个O(n)的操作。

• 字符串合并时需要手动分配空间，容易导致内存溢出。

char * __cdecl strcat (char * dst, const char * src)
{
    char * cp = dst;
  
    while( *cp )
        cp++;
  
    while( *cp++ = *src++ ) ;
  
    return( dst );
}  

 

SDS数据结构：

 

 

面对上述的几个问题，SDS如何解决：

• 所有字符都存储在buf数组中，最后一位存储的是”\0“
• len记录了当前字符串的长度，每次获取只需要O(1)操作

• 字符串合并分配空间时，需要len相加，然后看当前字符串alloc中的空间是否足够承载合并后的字符，不够直接申请空间

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}
 
sds sdscatlen(sds s, const void *t, size_t len) {
  
    size_t curlen = sdslen(s);
     
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    
    memcpy(s+curlen, t, len);
 
    sdssetlen(s, curlen+len);
 
    s[curlen+len] = '\0';
    return s;
}

 

极致的优化:

SDS实际还分为了物种类型的SDS，主要是用来分别SDS存储的数据大小使用哪种数据结构，他们分别是：
#define SDS_TYPE_5 0

#define SDS_TYPE_8 1

#define SDS_TYPE_16 2

#define SDS_TYPE_32 3

#define SDS_TYPE_64 4

 

typedef struct __attribute__ ((__packed__)) 设置内存不对齐，固定数据在内存分配的大小，不需要编译器优化补全

struct my

{

char ch;

int a;

} sizeof(int)=4;sizeof(my)=8;（非紧凑模式）

 

struct my{

char ch;

int a;

}__attrubte__ ((packed)) sizeof(int)=4;sizeof(my)=5

为什么Reids不补全？因为redis中的SDS中指针指的是buf数组，获取其他字段是只需要移动申明时的空间就可以得到其他字段，如果补全的话不清楚最大数组会补全到多少

 

自动扩容机制总结：

扩容阶段：

若 SDS 中剩余空闲空间 avail 大于新增内容的长度 addlen，则无需扩容；
若 SDS 中剩余空闲空间 avail 小于或等于新增内容的长度 addlen：
若新增后总长度 len+addlen < 1MB，则按新长度的两倍扩容；
若新增后总长度 len+addlen > 1MB，则按新长度加上 1MB 扩容。

 

内存分配阶段：

根据扩容后的长度选择对应的 SDS 类型：
若类型不变，则只需通过 s_realloc_usable扩大 buf 数组即可；
若类型变化，则需要为整个 SDS 重新分配内存，并将原来的 SDS 内容拷贝至新位置。

 

压缩列表初识

压缩列表在Redis中的List和Hash中都有使用，一般存储一个序列的对象。

List命令：

• lpush <key> <value> :LPUSH NAME XIAOMING
• lpop <key>:LPOP NAME
• llen <key>:LLEN NAME
• rpush <key> :RPUSH NAME
• rpop <key>:RPOP NAME

Hash命令:

• hset <key> <field><value>:HSET XIAOMING AGE 12
• hexists <key> <field>:HEXISTS XIAOMING AGE
• hgetall <key>:HGETALL XIAOMING

zipList数据结构：

 

 

zlBytes:压缩列表存储的字节数

zltail:压缩列表尾部节点

zllen:压缩列表长度

entry:压缩列表元素

zlend:压缩列表结尾标识，永远都是255

entry:{

          prevlen:前继节点长度

          encoding:编码格式

          data:数据内容

}

ziplist优点：

• 内存连续，使用完成的内存存储数据
• 支持从后向前的遍历数据

zipList数据结构解读：

Q:为什么结尾标识一直是255？

A:这个标识是redis中固定的结尾是255，在prevLen中存储的格式，当前前一个数据长度小于254，使用1个字节存储前一个节点的长度，如果大于254就用5个字节存储前一个节点的长度。定义成255是一个主要的标识，识别是否是结尾

prevlen:

字节长度	存储格式
1~253	8bit 1~253
254	8bit      32bit 254      prevLen

Q:连锁更新的问题？

A:每个entry存储着前一个节点的长度，用于遍历查找时使用，这也就是说当一个节点更新内容时，需要更新后继节点中的prevlen，更新节点prevlen从1个字节到5个字节，后续的所有节点都需要更新，这就是典型的连锁更新问题。

 

快速列表初识

在 redis 3.2 之后，list 的底层实现变为快速列表 quicklist,快速列表是 linkedlist 与 ziplist 的结合: quicklist 包含多个内存不连续的节点，但每个节点本身就是一个 ziplist。

• 当列表对象中元素的长度比较小或者数量比较少的时候，采用压缩列表 ziplist 来存储
• 当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表 linkedlist 来存储

typedef struct quicklistNode {
       struct quicklistNode *prev; 
       struct quicklistNode *next;
       unsigned char *zl;         
       unsigned int sz;           
       unsigned int count : 16;   
       unsigned int encoding : 2;  
       unsigned int container : 2;
       unsigned int recompress : 1;        
       unsigned int attempted_compress : 1;
       unsigned int extra : 10;            
   } quicklistNode;
 
   typedef struct quicklistLZF {
       unsigned int sz;   
       char compressed[];
   } quicklistLZF;
 
   typedef struct quicklist {
       quicklistNode *head;       
       quicklistNode *tail;      
       unsigned long count;       
       unsigned long len;         
       int fill : 16;            
       unsigned int compress : 16;
   } quicklist;

quick 中使用之前的LinkedList和ZipList存储数据，quicklist.compress 指定在双向列表中前后有几个节点不进行压缩，这是方便在遍历时不用从zipList寻址。

quickList数据结构优点：

• 有效解决了连锁更新的问题，但是没有彻底解决，只是修改为部分连锁更新，当LinkListNode中的ZipList更新时只在当前的LinkListNode中做连锁更新。
• 支持存储更多的数据
• 支持双向查找

哈希表初识

hash表中使用key:value这样的方式存储数据，next指针存储了下个entry数据地址，在redis中Hash、zset、set使用哈希表存储数据

set命令：

• sadd <key> <value> :SADD NAME XIAOMING
• sismember <key> <value>:SISMEMBER NAME XIAOMING
• smembers <key>:SMEMBERS NAME
• sscan <key> <number> :SSCAN NAME 0
• srem <key> <value>:SREM NAME XIAOMING

zset命令：

• zadd <key> number <value>:ZADD XIAOMING 6 AGE 
• zcount <key> min max:ZCOUNT XIAOMING 0 1

• zrangebyscore <key> min max:ZRANGEBYSCORE XIAOMING 0 100

• zremrangebyscore <key> min max:ZREMRANGEBYSCORE XIAOMING 0 1

• zrem <key> <value>:ZREM XIAOMING AGE

Dic数据解读

      Dicht中的hash冲突

     从数据结构中可以看到redis中的hash冲突使用链表寻址法，当前节点存储了在同一个bucket中的下个节点，这样处理hash冲突的优点是同一个Key只需要经过一次hash算法找到存储数据的Bucket就可以找到数据，缺点是在一个Dic中数据存储过多，冲突发生的较多时，获取数据需要耗费更多的O(n)的操作下完成

      Dic中的rehash

      第一个图中可以看到Dic中有两个table，在redis中所有的数据都是存储在dic中的，当dic进行扩容时，就需要进行rehash，也就是把key重新进行hash存储到扩容后的dic中。

      Q:什么时候触发rehash

• 扩容操作   

                  如果没有进行bgsave 元素数量达到hash长度时就会扩容（负载因子大于等于 1）
                  如果进行bgsave，元素数量达到hash长度的5倍会进行扩容（负载因子大于等于 5）

• 收缩操作

                  当哈希表的负载因子小于 0.1时， 程序自动开始对哈希表执行收缩操作。

      Q:rehash执行了什么操作

      A: 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始；
           为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表

• 若是扩展操作，那么ht[1]的大小为>=ht[0].used*2的2^n
• 若是收缩操作，那么ht[1]的大小为>=ht[0].used的2^n

        将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上
        当 ht[0] 包含的所有键值对全部迁移到了 ht[1] 之后，释放 ht[0] ，将 ht[1] 设置为 ht[0]，并重置 ht[1] ，最好将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
        rehashidx还有一个作用：记录的是ht[0]的下标位置的位置，下次rehash就从该位置继续进行。

Q:rehash大数据时阻塞请求？

      A:redis在进行rehash进行了渐进式rehash操作，每次操作哈希表1中的数据时才会将数据添加到哈希表2中，每次之操作一个key。

      Q:rehash算法是什么样的，如何保证rehash之后的顺序和不冲突？

      A:redis采用高位加位法，在扩容之后之前相邻的key还是相邻的，缩容之后依旧相邻。
          核心算法：

                 a mod 8 = a & (8-1) = a & 7
                 a mod 16 = a & (16-1) = a & 15
                 a mod 32 = a & (32-1) = a & 31

           7，15，31也就是Mask，所谓的掩码，每个key在进行hash计算的时候都经过了相同的掩码。

跳表初识

redis中zset使用跳表存储数据，主要使用跳表计算score，支持按照score区间查找数据。

跳表数据结构解读

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
  
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

跳表由多个数组组成，每个数组代表一层，最底层的数组存储所有的数据，上面的每一层存储的是数据的索引（就好比B+ tree），redis中的跳表节点，存储了前继节点的指针、socre、和数据(在不同的跳表实现中会存储不同的节点信息，包括上层节点，前继节点，下层节点。)

 

跳表的来历

跳表的研究来源于，有一个1至9的数组，我需要查9。
第一次，从1到9一个一个查询，需要查询9次，才能返回我想要的9。

来如果我每次差两个数字，第5次就可以查到9。依次类推，每次多差一次，查询次数就是9/n次。n越大，循环的次数就越少。但是n很大时，直接跳过了我要寻找的数据，也是不行的，所以这个n是无法估量的一个数字，所以产生了跳表，由数据的数量决定每一层的n是多少。

如何升层

如何才能知道我当前的数据是否可以到更高层？这个有几种算法：

1.固定的间隔，固定的间隔会随着数据增多层数越来越高，每次查找数据都需要经过固定的间隔

2.随机升层，不稳定升层，有可能同一层的数据很多了，但是还是没有升层数据，查询发生O(n)的操作

reids使用抛硬币的原理计算是否在更高层建立索引，只要计算是小于0.25那么就在高层建立索引，但是也有一个最大层（64）的限制

int randomlevel() {
      //初始化为一级索引
     int level = 1; 
     //翻硬币，如果求余2等于1 则 level增加一层
     while( rand() % 2 ) level++; 
     //如果level 没有超过最大层数就返回，否则就返回最大层数
     level  = ( maxlevel > level ) ? level : maxlevel;
     return level;
 }

为何限制64层

1. 跳表层数越高，查询的复杂度就越高，想想一下一个满层（64层）的跳表，需要查询到中间内容，需要查几次呢？描述一下跳表查询步骤，从最高层的索引处第一个元素查询数据，如果比第一层的第二元素小并且比第一个元素大，那么向下一层的前一个元素的区间查找，没向下一层就会有N个节点区间，层数越高，节点区间越多，复杂度就越高。
2. 维护一个满层的数据结构，添加一个数据，需要重新建立索引，如果是从底层建立到最高层，那就需要调整所有层中的索引，这其中包括升层，降层。

跳表和树的比较

数据结构	简介	存储特性	查找复杂度	插入复杂度
跳表	使用层级创建索引，支持跳跃查询	最底层存储数据，上层建立索引	logN	logN
红黑树(AVL)	平衡二叉树	每个数节点只能由两个叶节点组成，树节点存储数据	log2N	log2N
B+树	索引平衡二叉树，叶子节点存储数据，树节点存储索引	每个树节点由两个叶子节点组成，最底层叶子节点存储数据，树节点存储索引	logmN	logmN
B树	索引平衡二叉树，树节点存储数据	树节点有多个叶节点组成，树节点存储数据和索引	logN	近似logN

 

学习的工具

在线测试redis命令：https://try.redis.io/

redis官网：https://redis.io/
书：《redis深度历险记》