redis底层数据结构

2020-06-24  本文已影响0人  newbtao
一、redis中数据对象

redis有五大数据类型, 通过统一对象redisObject存储, redisObject的结构主要包含以下部分:

1 typedef struct redisObject {
2     // 类型
3     unsigned type:4;
4     // 编码
5     unsigned encoding:4;
6     // 指向底层实现数据结构的指针
7     void *ptr;
8     // ...
9 } robj;

redis为每种数据类型，提供了两种以上的底层数据结构实现，可以通过type和object encoding这两个命令查看数据对象的类型和数据结构。

127.0.0.1:6379> set key1 100
OK
127.0.0.1:6379> type key1
string
127.0.0.1:6379> object encoding key1
"int"
127.0.0.1:6379> set key2 'abc'
OK
127.0.0.1:6379> type key2
string
127.0.0.1:6379> object encoding key2
"embstr"

二、不同数据类型对应的底层数据结构

  1. 字符串
  1. 哈希
  1. 列表
  1. 集合
  1. 有序集合
三、数据结构实现

1. int

int保存的是long类型的整数，8个字节长整型，直接保存在redisObject对象的ptr属性中。
2. embstr
embstr保存小于等于39个字节的字符串，使用动态字符串（SDS）实现。直接保存在redisObject对象的ptr属性中，只需要分配一次内存， 即创建redisObject对象。

3. raw
raw保存大于39个字节的字符串，使用动态字符串（SDS）实现，需要单独分配内存给sdshdr（SDS）结构。

注意: 在redis 3.2之后，embstr和raw改为以44字节为分界线

SDS
redis没有采用c的字符串结构，而是构建了动态字符串的数据结构，先来看看结构源码：

struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组，用于保存字符串，最后一个位置存储的是空字符'\0', 不计入len
     char buf[];
}

SDS的优化：

分界线39或44的来源

4. ziplist
压缩列表是 Redis 为了节约内存而实现的，是一系列特殊编码的连续内存块组成的顺序型数据结构。 结构如下图：

压缩列表的遍历：
通过指向表尾节点的位置指针p1, 减去节点的previous_entry_length，得到前一个节点起始地址的指针。如此循环，从表尾遍历到表头节点。

5. linkedlist
双向链表结构，表头节点的前置节点和表尾节点的后置节点都是NULL，是无环链表。链表结构源码如下：

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;

6. quicklist
一个由ziplist组成的双向链表（ziplist和linklist结合），即链表的每个节点都是ziplist；redis3.2新增的数据结构，用于列表的实现。quicklist结构源码：

typedef struct quicklist {
    // 指向头部quicklist节点的指针
    quicklistNode *head;
    //  指向尾部quicklist节点的指针
    quicklistNode *tail;
    // quicklist中所有ziplist中的entry节点数量。
    unsigned long count;
    // quicklist的链表节点数量
    unsigned int len; 
    // 保存ziplist的大小，配置文件设定，占16bits
    int fill : 16;        
    // 保存压缩程度值，配置文件设定，占16bits，0表示不压缩
    unsigned int compress : 16; 
} quicklist;

7. intset
当一个集合中只有整数元素，就会使用intset结构。结构源码：

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

8. hashtable
redis的hash表，采用链地址法解决冲突。
哈希表结构：

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

其中dictht ht[0]为正常情况下使用，ht[1]为rehash过程使用。

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_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;  // 单链表结构
} dictEntry;
  1. 为ht[1]分配空间，大小为比当前ht[0]已使用值的两倍大的第一个2的整数幂。如，已使用空间7，则分配比7*2大的最近的2的整数幂，即16。
  2. 将ht[0]中所有键值对，rehash到ht[1]上。
  3. 完成迁移后，释放ht[0], 将ht[1]设置为ht[0], 在ht[1]处新建空白哈希表，为下一次rehash做准备。
  1. 为ht[1]分配空间，同时持有两个哈希表(一个空表、一个有数据)。
  2. 维持计数器rehashidx，初始值为0，表示rehash开始。
  3. 每次增删改查，都顺带将ht[0]中的数据迁移到ht[1], rehashidx++.
  4. 直到rehash完成，rehashidx设置为-1。
    渐进式hash中，更新、删除、查找都会在两个hash表上进行。新增操作只在ht[1]上进行，保证ht[0]只减不增，直到成为空表。
    （假如ht[0]有冷门数据一直不被操作，ht[0]一直没有清空，ht[1]触发新的rehash阈值怎么办？）

9. skiplist跳跃表


跳跃表的结构如下： 
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 跳表节点的数量
    unsigned long length;
    // 跳表层数
    int level;
} zskiplist;

节点结构如下：

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分数值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度，记录两个节点间的距离
        unsigned int span;
    } level[];
} zskiplistNode;

为什么用跳跃表不用平衡树

  1. skiplist算法实现简单得多。
  2. 跳跃表和平衡树的插入删除时间复杂度都是O(logn)，不过平衡树的插入和删除操作引发树结构的调整，操作复杂。skiplist只需要修改相邻节点的指针，操作简单。
  3. 查询单个key，跳跃表和平衡树的时间复杂度都是O(logn)，大体相当。
  4. 范围查找，平衡树要复杂，skiplist适合zset各种操作。
上一篇 下一篇

猜你喜欢

热点阅读