第六章----Redis数据类型底层实现

Redis的数据库就是使用字典(哈希表)来作为底层实现的，对数据库的增删改查都是构建在字典(哈希表)的操作之上的。

typedef struct redisDb { 
    int id;         // 数据库ID标识
    dict *dict;     // 键空间，存放着所有的键值对              
    dict *expires;  // 过期哈希表，保存着键的过期时间                          
    dict *watched_keys; // 被watch命令监控的key和相应client    
    long long avg_ttl;  // 数据库内所有键的平均TTL（生存时间）     
} redisDb;

DB数据结构

每次在Redis中创建数据时都会生成两个对象：键对象、值对象。Redis对象用redisObject结构表示，其中类型、编码和指针记录了Redis五个数据类型和六个底层数据结构的关系。

typedef struct redisObject{
     //类型
     unsigned type:4;
     //编码
     unsigned encoding:4;
     //指向底层数据结构的指针
     void *ptr;
     //引用计数
     int refcount;
     //记录最后一次被程序访问的时间
     unsigned lru:22;
}robj

数据类型与数据结构

1. string对象

• Redis 是用 C 语言写的，但Redis的字符串是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型。

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串
     char buf[];
}

• 字符串对象的编码可以是int，raw或者embstr。int 编码是用来保存整数值，raw编码是用来保存长字符串，而embstr是用来保存短字符串。其实 embstr 编码是专门用来保存短字符串的一种优化编码。

• raw 和 embstr 的区别？

  1. embstr的使用只分配一次内存空间（因此redisObject和sds是连续的），而raw需要分配两次内存空间（分别为redisObject和sds分配空间）。
  2. 因为redis中的embstr实现为只读，所以只要是修改embstr对象，修改后的对象一定是raw的。

raw字符串 embstr字符串

2. list对象

• Redis中链表也是自己定义实现的，双向链表结构为：

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;

链表具有前置节点和后置节点的引用，表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，通过 len 属性获取链表长度，链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

• 压缩列表（ziplist）是Redis为了节省内存而开发的，它并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域的顺序型数据结构。

压缩列表组成 列表节点组成

• list对象可以是 ziplist(压缩列表) 和 linkedlist(双端链表)，当列表保存元素个数小于512个且每个元素长度小于64字节时为ziplist，可以更改list-max-ziplist-value选项和 list-max-ziplist-entries 选项进行配置。

ziplist linkedlist

3. hash对象

• 字典哈希表，Redis 的字典使用哈希表作为底层实现，通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点，也就是链地址法解决哈希冲突问题。

# hash表
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_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

# 字典
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

• hash对象的编码可以是 ziplist 或者 hashtable。当列表保存元素个数小于512个且每个元素长度小于64字节时为ziplist，可以更改list-max-ziplist-value选项和 list-max-ziplist-entries 选项进行配置。

ziplist hashtable

• rehash扩容过程

  1. 在字典中维持一个索引计数器变量rehashidx，并将设置为0，表示rehash开始。
  2. 在rehash期间每次对字典进行增加、查询、删除和更新操作时，除了执行指定命令外；还会将ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。
  3. 字典操作不断执行，最终在某个时间点，所有的键值对完成rehash，这时将rehashidx设置为-1，表示rehash完成。
  4. 在渐进式rehash过程中，字典会同时使用两个哈希表ht[0]和ht[1]，所有的更新、删除、查找操作也会在两个哈希表进行。例如要查找一个键的话，服务器会优先查找ht[0]，如果不存在，再查找ht[1]，诸如此类。此外当执行新增操作时，新的键值对一律保存到ht[1]，不再对ht[0]进行任何操作，以保证ht[0]的键值对数量只减不增，直至变为空表。

4. set对象

• 整数集合（intset）是Redis用于保存整数值的集合抽象数据类型，不会出现重复元素。

typedef struct intset{
     //编码方式
     uint32_t encoding;
     //集合包含的元素数量
     uint32_t length;
     //保存元素的数组
     int8_t contents[];
 
}intset;

• set对象的编码可以是 intset 或者 hashtable。当集合对象中所有元素都是整数且所有元素数量不超过512时为intset类型，可通过set-max-intset-entries 进行配置。

• intset 编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合中。

• hashtable 编码的集合对象使用 字典作为底层实现，字典的每个键都是一个字符串对象，这里的每个字符串对象就是一个集合中的元素，而字典的值则全部设置为 null。

intset hashtable

5. zset对象

• 跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。

  跳跃表类似公司的组织架构：董事会->C？O->部门->组长->员工

  1. 由很多层结构组成
  2. 每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点
  3. 最底层的链表包含了所有的元素
  4. 如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）
  5. 链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点

typedef struct zskiplistNode {
     //层
     struct zskiplistLevel{
           //前进指针
           struct zskiplistNode *forward;
           //跨度
           unsigned int span;
     }level[];
 
     //后退指针
     struct zskiplistNode *backward;
     //分值
     double score;
     //成员对象
     robj *obj;
 
} zskiplistNode

typedef struct zskiplist{
     //表头节点和表尾节点
     structz skiplistNode *header, *tail;
     //表中节点的数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;
 
}zskiplist;

跳跃表

• zset集合的编码可以是 ziplist 或者 skiplist，当保存的元素数量小于128且长度都小于64字节为ziplist类型，通过zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改。

• ziplist 编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个节点保存元素的分值。并且压缩列表内的集合元素按分值从小到大的顺序进行排列，小的放置在靠近表头的位置，大的放置在靠近表尾的位置。

ziplist

• skiplist 编码的有序集合对象使用 zet 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表，字典的键保存元素的值，字典的值则保存元素的分值；跳跃表节点的 object 属性保存元素的成员，跳跃表节点的 score 属性保存元素的分值。

typedef struct zset{
     //跳跃表
     zskiplist *zsl;
     //字典
     dict *dice;
} zset;

6. 内存回收和共享

• Redis自己构建了一个内存回收机制，通过在 redisObject 结构中的 refcount 属性实现。

  1. 创建一个新对象，属性 refcount 初始化为1
  2. 对象被一个新程序使用，属性 refcount 加 1
  3. 对象不再被一个程序使用，属性 refcount 减 1
  4. 当对象的引用计数值变为 0 时，对象所占用的内存就会被释放

API

定期删除+惰性删除

定期删除： redis默认是每隔 100ms 就随机抽取一些设置了过期时间的key，检查其是否过期，如果过期就删除。

惰性删除 ： 当去查询已经过期的key时，Redis才会对其删除。

• 当存在循环引用就会造成内存泄露，所以redis可以配置6种清除策略，maxmemory-policy ：当内存使用达到最大值时，有以下几种策略：

  1. volatile-lru 利用LRU算法移除设置过过期时间的key (LRU:最近使用 Least Recently Used )
  2. allkeys-lru 利用LRU算法移除任何key
  3. volatile-random 移除设置过过期时间的随机key
  4. allkeys-random 移除随机key
  5. volatile-ttl 移除即将过期的key(minor TTL)
  6. noeviction 不移除任何key，只是返回一个写错误 ，默认选项
  7. volatile-lfu：从所有配置了过期时间的键中移除使用频率最少的键
  8. allkeys-lfu：从所有键中移除使用频率最少的键

  Redis 4.0 引入了 volatile-lfu 和 allkeys-lfu 淘汰策略。

  LFU 策略：通过统计访问频率，将访问频率最少的数据淘汰。
  LRU策略：通过最近访问，将长时间没有访问的数据淘汰。

• refcount 属性除了能实现内存回收以外，还能用于内存共享：将数据库键的值指针指向一个现有值的对象 、将被共享的值对象引用refcount 加 1。

内存共享

7. 降低内存占用的几种方式

降低内存占用有助于减少创建快照和加载快照的时间、提升载入AOF文件和重新文件的效率、缩短主从同步所需的时间等！

• 短结构：如ziplist、intset、string符合条件解析的int和embstr等。但操作一个长压缩列表或者大整数集合会对性能带来影响，严重时可能导致不可用。可是设置元素不超过1024个字节不超过64位。

• 分片结构：分片本质上是基于某些简单的规则将数据划分为更小的部分，如根据算法计算key的组成。

• 打包存储二进制位和字节。

---

春暖花开 应该走出去看看这片春色