Redis核心结构以及渐进式扩容

总体结构图

设计理论

Redis K-V底层设计原理

在Redis底层总的来看就是一个Map

• 数据访问问题

  采用hash算法+数组从而做到O(1)的时间复杂度

• 由于客户端传输的K类型不可控

  采用SDS存储数据，动态的控制数据存储的大小（不同的头），并尽量减少内存空间的浪费
  在3.2后版本后，不同的sdshdr*是根据不同的K的大小，进行选择不同的头部，来防止free,len数据类型过大，浪费过多的空间

  • 二进制安全的数据结构 （保证数据类型的兼容）
  • 提供了内存预分配机制，避免了重复的内存分配
  • 兼容C语言的函数库
• 采用redisObjecct进行封装value，做到不同类型value结构
  • 内部采用encoding规范存储数据编码，做到根据数据的类型、长度、数量动态的选择最佳的结构

主要数据结构解释

RedisDB

Redis的数据库，默认16个，数据相互隔离

typedef struct redisDb {
 dict *dict;                 /* The keyspace for this DB 机翻：此数据库的键空间*/
 dict *expires;              /* Timeout of keys with a timeout set  机翻：设置了超时的字典 过期时间字典 */
 dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) 机翻：客户端等待数据的密钥（BLPOP）*/
 dict *ready_keys;           /* Blocked keys that received a PUSH 机翻： 收到推送的锁定键*/
 dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS 多/执行CAS的监视键*/
 int id;                     /* Database ID 数据库ID*/
 long long avg_ttl;          /* Average TTL, just for stats 平均TTL，仅用于统计*/
 unsigned long expires_cursor; /* Cursor of the active expire cycle. 活动过期周期的光标*/
 list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. 尝试逐步逐个碎片整理的密钥名称列表。*/
} redisDb;
1
2
3
4
5
6
7
8
9
10
11

dict

字典，用于保存键值数组，以及数据库扩容

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];// ht[0] , ht[1] =null
    long rehashidx; /* rehashing not in progress if rehashidx == -1 如果rehashidx==-1，则未进行数据迁移*/
    unsigned long iterators; /* number of iterators currently running 当前运行的迭代器数*/
} dict;
1
2
3
4
5
6
7

dictht

保存数据的hashTable，默认大小4
存在2个是因为在扩容时需要保持旧和新的数组

typedef struct dictht {
 dictEntry **table;
 unsigned long size; //  hashtable 容量
 unsigned long sizemask;  // size -1
 unsigned long used;  // hashtable 元素个数   used / size =1
} dictht;
1
2
3
4
5
6

dictEntry

存储键值对的数据类型，保存单个键值的数据

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
1
2
3
4
5
6
7
8
9
10

• key 存储redis中的K,该类型即为SDS
• val 存储redis中的V,该类型为redisObject
• next 存储下一个dictEntry,建立链表

redisObject

键存储的基本类型，记录了当前存储的数据类型，编码类型等

typedef struct redisObject {
    unsigned type:4;        //  4 bit, sting , hash 数据类型
    unsigned encoding:4;    //  4 bit 编码类型
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time).  
                            *    24 bit 用于记录各种淘汰算法
                            * */
    int refcount;           // 4 byte  采用引用计数法标记是否废弃
    void *ptr;              // 8 byte  具体数据存储指针 总空间:  4 bit + 4 bit + 24 bit + 4 byte + 8 byte = 16 byte  
} robj;
1
2
3
4
5
6
7
8
9
10
11

• type:数据类型，用于约束数据类型
  type K查看K的数据类型 例如: string,hash,list,set,sort set

• encoding:底层 编码
  obejct encodin 获取底层编码 例如:int,raw,embstr,quicklist 等

• lru:内存淘汰策略 例如:LRU,LFU 等

• refcount :引用数量,采用引用计数法来进行垃圾清除，进行内存释放

• prt:数据的实际位置（指针）

SDS

Redis3.2以前

• SDS结构

  struct sdshdr {
  
    int len;
  
    int free;
  
    char buf[];
  };
  1
  2
  3
  4
  5
  6
  7
  8

• 总结
  len:记录buf数组中已使用字节数量
  free:记录buf数组中剩余字节数量
  buf[]:字节数组，保存字符串
  估计报废原因:无法充分利用内存空间，造成了内存浪费，在存储value的值较小情况下，len与free使用的大小居然比buf还要大。

Reddis3.2后

• SDS结构

  typedef **char** *sds;
  
  
  
  struct __attribute__ ((__packed__)) sdshdr5 {
  
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
  
    char buf[];
  
  };
  
  struct __attribute__ ((__packed__)) sdshdr8 {
  
    uint8_t len; /* used */
  
    uint8_t alloc; /* excluding the header and null terminator */
  
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
  
    char buf[];
  
  };
  
  struct __attribute__ ((__packed__)) sdshdr16 {
  
    uint16_t len; /* used */
  
    uint16_t alloc; /* excluding the header and null terminator */
  
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
  
    char buf[];
  
  };
  
  struct __attribute__ ((__packed__)) sdshdr32 {
  
    uint32_t len; /* used */
  
    uint32_t alloc; /* excluding the header and null terminator */
  
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
  
    char buf[];
  
  };
  
  struct __attribute__ ((__packed__)) sdshdr64 {
  
  ........
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51

• sdsReqType函数

  static inline char sdsReqType(size_t string_size) {
      if (string_size < 32)  
          return SDS_TYPE_5;
      if (string_size < 0xff) //2^8 -1  
          return SDS_TYPE_8;
      if (string_size < 0xffff) // 2^16 -1  
          return SDS_TYPE_16;
      if (string_size < 0xffffffff)  // 2^32 -1 
          return SDS_TYPE_32;
      return SDS_TYPE_64;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

• 图解
  
  在不同大value大小下使用buf尽可能多的存储数据，sdshdr后面的数据代表的是长度所占用的bit位
  len:记录buf数组中已使用字节数量
  flags:当前类型(不同的sdshdr)
  alloc:不包括头和空结束符的字节数量

• 总结
  该机制保证不同长度的value,充分利用内存资源避免内存浪费

渐进式rehash及动态扩容机制（为何需要2个dictht）

Redis每次扩容HashTable的2倍，并且不会一次性进行数据迁移，每次命令执行都会将一部分数据进行迁移，在长时间没有命令时，会进行指令轮询进行迁移

• 迁移时数据获取

  采用先查找老Table，然后查找新Table

• 访问算法 hash算法

  跟Java中的HashMap查找类似 位置=hash结果&(Tb大小-1）

• 数据迁移

  每次数据访问时，会进行当前槽位的迁移，只有在长时间没有命令时，会进行指令轮询进行迁移

• 扩容规则

  • 当容量大于1M(1024*1024)时不再进行成倍扩容
  • 动态扩容:每次扩容都根据算法多扩容一部分

    newLen=（len +addlen）* 2 //扩容
    实际上的实现是比较复杂的，学习的主要是设计思想
    本质是根据hash表的负载因子决定的，即:存储数据的大小/hash表的数量，根据大小决定是否进行扩容和收缩，为的是保证查询效率会大规模退化
    有没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令对负载因子有影响,在执行时大于5才进行扩展，不执行时大于1才扩展,主要是为了从而尽可能地避免在子进程存在期间进行哈希表扩展操作， 这可以避免不必要的内存写入操作， 最大限度地节约内存