Redis 数据结构

2018-01-10 • jyjsjd

 数据库  数据库

1、简单动态字符串（Simple Dynamic String，SDS）

（1）结构

  • SDS 遵循 c 字符串以 '\0' 结尾的惯例，但是不计算在长度里；
  • SDS 记录了自身长度，获取字符串长度复杂度 O(1)；
struct {
  int len;    // 已用长度
  int free;   // 未用长度
  char buf[]; //字节数组
}

redis_str

（2）减少修改字符串带来的内存重分配次数

  • 空间预分配：
    • 如果对 SDS 修改之后的长度小于 1MB，那么程序分配和 len 属性同样大小的未使用空间；
    • 如果大于 1MB，程序分配 1MB 的未使用空间。
  • 惰性空间释放：当 SDS 缩短字符串时，程序并不立即回收多余空间，而是用 free 属性记录长度，以待未来使用。

（3）二进制安全

SDS 的 API 都是二进制安全的，所有 API 都以处理二进制的方式处理存放的数据，程序不会对其中的数据进行任何限制、过滤或者假设，数据在写入时什么样，读取时就是什么样。

2、链表

  • 双端；
  • 无环，头节点的 prev 和尾节点的 next 都指向 null；
  • 保存链表长度；
  • 多态：可保存不同类型的值。
typedef struct list {
  listNode *head;                    // 头节点
  listNode *tail;                    // 尾节点
  unsigned long len;                 // 链表包含的节点数量
  void *(*dup)(void * ptr);          // 节点复制函数
  void (*free)(void *ptr);           // 节点值释放函数
  int(*match)(void *ptr, void *key); // 节点值对比函数
}

typedef struct listNode {
  struct listNode *prev; // 前置节点
  struct listNode *next; // 后置节点
  void *value;           // 节点的值
}

redis_list

3、字典

（1）结构

  • 哈希表：table 属性是一个数组，数组中每个元素都是一个指向 dictEntry 结构的指针，每个 dictEntry 结构保存一个键值对。
typedef struct dictht {
  dictEntry **table;      // 哈希表数组
  unsigned long size;     // 哈希表大小
  unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于size-1
  unsigned long used;     // 哈希表已有节点数量
} dictht;
  • 哈希表节点：
    • key 保存键；
    • v 保存值，值可以是一个指针、一个 uint64_t 整数或者是一个 int64_t 整数；
    • next 指向下一个节点———解决冲突。
typedef struct dictEntry {
  void *key; // 键
  union {    // 值
    void *val;
    uint64_tu64;
    int64_ts64; 
  } v;
  struct dictEntry *next; // 指向下个哈希节点，形成链表
} dictEntry;

redis_hash

  • 字典：
    • ht 属性是包含两个项的数组，字典只使用 ht[0]，ht[1] 只会在对 ht[0] rehash 时使用;
    • rehashidx 记录 rehash 的进度，如果没有进行 rehash，它等于 -1。
typedef struct dict {
  dictType *type; // 类型待定函数
  void *privdata; // 私有数据
  dictht ht[2];   // 哈希表
  int rehashidx;  // 标志 rehash 是否进行，当 rehash 不在进行时为-1
} dict;

typedef struct dictType {
  unsigned int (*hashFunction)(const void *key);
  void *(*keyDup)(void *privdata, const void *key);
  void *(*valDup)(void *privdata, const void *obj);
  int (*keyCompare)(void *privdata, const void *key1, const void *key2);
  void (*keyDestructor)(void *privdata, void *key);
  void (*valDestructor)(void *privdata, void *val);
}

redis_dict

（2）哈希算法

  • 将一个新的键值对添加到字典时，首先根据键计算出哈希值和索引值，然后再根据索引值将包含键值对的节点放到哈希表数组的指定索引上；
  • 解决冲突：链地址法——多个哈希节点构成一个单向链表；为了速度考虑，程序总是将新节点添加到链表的表头。

（3）rehash

执行时机

负载因子 = 哈希表已保存节点数量 / 哈希表大小

哈希表扩展和收缩：

  • 扩展
    • 服务器没有执行 BGSAVE 或 BGREWRITEAOF，并且负载因子大于等于 1；
    • 服务器正在执行 BGSAVE 或 BGREWRITEAOF，并且负载因子大于等于 5。
  • 收缩：负载因子小于 0.1。
执行步骤
  • 为 ht[1] 分配空间：
    • 扩展：ht[1] 的大小等于_第一个大于等于_ ht[0].used*2 的 2的n次幂；
    • 收缩：ht[1] 的大小等于_第一个大于等于_ ht[0].used 的 2的n次幂。
  • 将保存在 ht[0] 的所有键值对 rehash 到 ht[1] 上：重新计算哈希值和索引值；
  • 当 ht[0] 的所有键值对都 rehash 到 ht[1] 上之后：
    • 释放 ht[0]；
    • 将 ht[1] 设置为 ht[0]；
    • 为 ht[1] 新建一个空白哈希表。
渐进式 rehash

如果哈希表数量庞大，一次性 rehash 会导致服务器在一段时间内停止服务。为了避免这种情况，redis 分多次、渐进式地把 ht[0] 里的键值对 rehash 到 ht[1]。

  • 为 ht[1] 分配空间，字典_同时_持有 ht[0] 和 ht[1]；
  • 把 rehashidx 设置为 0，表示正在 rehash；
  • 在 rehash 过程中对 ht[0] 的操作，都会顺带 rehash 到 ht[1]；
  • rehash 完成之后把rehashidx 设置为 -1，表示完成。

4、跳跃表

  • 跳跃表节点：
    • 层：level 数组包含多个元素，每个元素都包含一个指向其他节点的指针；
    • 前进指针：每层都有一个指向表尾方向的前进指针，用于表头向表尾方向访问节点；
    • 跨度：记录两个节点间的距离；
    • 后退指针：用于从表尾向表头方向访问节点。
    • 分值和成员：分值是一个 double 类型的浮点数，跳跃表中的所有节点按照分值大小排序；成员对象是一个指针，指向一个字符串对象。
typedef struct zskiplistNode {
  struct zskiplistLevel { // 层
    struct zskiplistNode *forward; // 前进指针
    unsigned int span;             // 跨度
  } level[];
  struct zskiplistNode *backward;  // 后退指针
  double score;                    // 分值
  robj *obj;                       // 成员对象
} zskiplistNode;
  • 跳跃表
typedef struct zskiplist {
  struct skiplistNode *header, *tail; // 表头和表尾节点
  unsigned long length;               // 节点数量
  int level;                          // 层数最大的节点层数
} zskiplist;

redis_skiplist

5、整数集合

（1）结构

  • contents 数组是整数集合的底层实现————每个元素都是一个数组项，按照值的大小从小到大排序，且不包含重复项；
  • contents 声明为 int8_t 类型，但实际上的类型由 encoding 决定。
typedef struct intset {
  uint32_t encoding; // 编码方式
  uint32_t length;   // 集合包含的元素数量
  int8_t contents[]; // 保存元素的数组
}

（2）升级

当要把一个新元素加入整数集合，且这个元素比现有所有元素的类型都要长时，整数集合必须要升级。

  • 根据新元素类型，扩展整数集合数组的空间大小，并为新元素分配空间；
  • 将底层数组的所有元素都转换为与新元素相同的类型；
  • 添加新元素。

（3）降级

不支持降级操作。

6、压缩列表

压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

节点构成

  • 字节数组，可以是以下3种长度：
    • 长度小于等于26 - 1字节的字节数组；
    • 长度小于等于214 - 1字节的字节数组；
    • 长度小于等于232 - 1字节的字节数组。
  • 整数值：
    • 4位长，介于0 - 12间的无符号整数；
    • 1字节长的有符号整数；
    • 3字节长的有符号整数
    • int16_t类型整数；
    • int32_t类型整数；
    • int64_t类型整数。

每个压缩节点都由 previous_entry_length、encoding、content 组成：

  • previous_entry_length：记录前一个节点长度，可以为1字节或5字节，通过这个属性，程序可以从表尾向表头遍历：
    • 1字节：前一个节点长度小于254字节；
    • 5字节：前一个节点长度大于等于254字节。
  • content：记录节点保存数据的类型和长度。
  • encoding：保存节点的值。

连锁更新

更新节点时，会导致所有节点的previous_entry_length重新扩展。

 Toc
 Tags
 Related