Skip to content

Latest commit

 

History

History
159 lines (126 loc) · 8.23 KB

RedisData.md

File metadata and controls

159 lines (126 loc) · 8.23 KB

Redis数据结构

  • Redis 使用了一个哈希表来保存所有键值对。它的存储是以 key-value 的形式的。 key 一定是字符串，value 可以是 string、list、hash、set、sortset 中的随便一种。
  • 一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。每个哈希桶中保存了键值对数据，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。

1. SDS 简单动态字符串

简单动态字符串 (Simple dynamic string,SDS)源码如下：

struct sdshdr{

    // 字节数组，用于保存字符串
    char buf[];

    // 记录buf数组中已使用的字节数量，也是字符串的长度
    int len;

    // 记录buf数组未使用的字节数量
    int free;
}
优点
  1. 常数复杂度获取字符串长度：C 字符串不记录长度，统计长度只能逐个遍历字符，复杂度是 O(N)；而 SDS 在 len 属性中记录了自身长度，复杂度仅为 O(1)。
  2. 不会发生缓冲区溢出：SDS 不会发生溢出的问题，如果修改 SDS 时，空间不足。先会扩展空间，再修改！(内部实现了动态扩展机制)。
  3. SDS 可以减少内存分配的次数 (空间预分配 & 惰性空间释放)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间 (free 属性)。
  4. SDS 是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据。

2. 链表

链表的特性

  1. 双端：有 prev 和 next 两个指针；可以前后移动。
  2. 无环：链表不闭环，prev 和 next 都指向 null，链表访问以 null 为终点。
  3. 获取带表头指针、表尾指针、节点数量的时间复杂度均为 O (1)。
  4. 链表使用 void * 指针来保存节点值，可以保存各种不同类型的值。

3. 哈希表

3.1 rehash（扩容）

Redis 开始执行 rehash，这个过程分为三步：

  • 1、给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
  • 2、把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
  • 3、释放哈希表 1 的空间。
缺点:
  • 当哈希表 1 数据量很大，如果一次性复制就会造成线程阻塞，无法服务其他请求。
  • Redis 不允许这种事发生，因此使用了渐进式 rehash。
3.2 渐进式 rehash
  • 在第二步拷贝数据时，Redis 仍然正常处理客户端请求
  • 每处理一个请求，顺带从哈希表 1 中的第一个索引位置开始，把这个位置上所有的 entry 复制到哈希表 2 中，下个请求就复制位置 2；
  • 直至全部复制完成。

具体到代码，它的过程是这样的：

  • 1、在字典中维持一个索引计数器变量 rehashidx，并将设置为 0，表示 rehash 开始。
  • 2、在 rehash 期间，客户端每次对字典进行 CRUD 操作时，会将 ht [0] 中 rehashidx 索引上的值 rehash 到 ht [1]，操作完成后 rehashidx+1。
  • 3、字典操作不断执行，最终在某个时间点，所有的键值对完成 rehash，这时将 rehashidx 设置为 - 1，表示 rehash 完成
Q: 只有在操作字典的时候才进行复制数据吗？如果客户端只操作一次字段是不是就完不成 rehash 了？
  • 渐进式 rehash 执行时，除了根据针对字典的 CRUD 操作来进行数据迁移，Redis 本身还会有一个定时任务在执行 rehash，如果没有针对字典的请求时，这个定时任务会周期性地（例如每 100ms 一次）搬移一些数据到新的哈希表。
Q: 渐进式 rehash，CRUD 究竟在哪个哈希表操作呢？
  1. 在渐进式 rehash 过程中，字典会同时使用两个哈希表 ht [0] 和 ht [1]，所有的 CRUD 操作也会在两个哈希表进行。
  2. 比如要查找一个键时，服务器会优先查找 ht [0]，如果不存在，再查找 ht [1]。当执行新增操作时，新的键值对一律保存到 ht [1]，不再对 ht [0] 进行任何操作，以保证 ht [0] 的键值对数量只减不增，最后变为空表。

4. 跳跃表

跳跃表 (shiplist) 是实现 sortset (有序集合) 的底层数据结构之一；

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

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

最左边的是 zskiplist 结构，包含：

  • header：指向跳跃表的表头节点。
  • tail：指向跳跃表的表尾节点。
  • level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
  • length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

zskiplist结构右方的是四个zskiplistNode结构， 包含：

  • 层：比如节点中的 L1、L2、L3 等，包括前进指针和跨度
  • 前进指针：用于访问位于表尾方向的其他节点
  • 跨度：记录了前进指针所指向节点和当前节点的距离
  • 后退指针：指向当前节点的前一个节点，从表尾向表头遍历
  • 分值：节点按各自分值从小到大排列
  • 成员对象：节点所保存的成员对象

5. 整数集合

整数集合是 Set（集合）的底层数据结构之一。 当 Set 只包含整数值元素，并且这个 Set 的元素数量不多时，Redis 就会使用整数集合作为 Set 的底层实现。

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

contents 的真正类型取决于encoding 的值：

  1. INTSET_ENC_INT16
  2. INTSET_ENC_INT32
  3. INTSET_ENC_INT64
  • 如果 contents 本来保存 1、3、5 三个整数值，后面加一个 2147483647456。
  • 那么只有 2147483647456 是真正需要 int64_t 类型来保存的，而其他的 1、3、5 都可以用 int16_t 类型来保存；这时是整体升级，所有元素都会被升级为 int64_t 类型。 也就是说本来是 int16_t 类型的集合，要放入大于本身的整数。就需要升级，步骤如下：
升级操作
  • 1、根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
  • 2、将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。
  • 3、将新元素添加到底层数组。

注意点：整数集合只支持升级、不支持降级。

6. 压缩列表

  • 压缩列表是 list 和 hash 的底层实现之一，当 list 只包含少量元素，并且每个元素都是小整数值，或者是比较短的字符串，压缩列表会作为 list 的底层实现。
  • 压缩列表（ziplist）是 Redis 为节约内存而开发，它的理念是多大元素用多大内存。
  • 压缩列表是根据每个节点的实际存储的内容决定内存的大小，第一个节点占用 5 字节，第二个节点占用 5 字节，第三个节点占用 1 字节，第四个节点占用 4 字节，第五个节点占用 3 字节。
ziplist 的结构：

它类似于一个数组，不同的是它在表头有三个字段 zlbytes、zltail 和 zllen；分别表示列表长度、列表尾的偏移量和元素的个数；表尾有 zlend，列表结束的标识。

ziplist 节点构成
  1. previous_entry_length：记录前一个节点的长度
  2. encoding：编码，控制 content 的类型和长度；分为字节数组编码和整数编码
  3. content：保存节点值，可以是一个字节数组或整数
ziplist的查找
  • 如果查找的是第一个元素或最后一个元素，可通过表头三个字段的长度直接定位，复杂度是 O (1)。而查找其他元素时，只能逐个查找，复杂度是 O (N) 。
  • 倒序遍历：首先指针通过 zltail 偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。