Redis 基本数据结构

作者

一、简单动态字符串

Redis 数据库的 key 总是一个字符串对象，value可以是 字符串、列表、哈希、集合、有序集合。

Redis 自己构建了一种简单动态字符串 simple dynamic string SDS，作为默认字符串表示。

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

程序通过直接访问 len属性，就可以知道 SDS 的长度，复杂度为 O(1)

1、空间预分配

SDS 进行操作之前会检查空间大小是否足够，不够的话会自动扩容。所以不会出现缓冲区溢出。

  • 当 SDS 小于 1MB 时，程序将分配和 len 同样大小的未使用空间。
  • 当 SDS 大于 1MB 时，程序将分配 1MB 的未使用空间。

2、惰性空间释放

当字符串缩短时，多余的字节不会被回收，而是成为 free，以便下次再分配。

3、二进制安全

4、兼容部分 C 字符串函数

二、链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活的调整链表的长度。

1、节点ListNode 结构：

typedef struct listNode{
    struct listNode * prev;
    struct listNode * next;
    void * value;
}listNode;

2、链表结构：

typedef struct list{
    //表头节点
    listNode * head;
    //表尾节点
    listNode * tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值复制函数
    void * (*dup) (void * ptr);
    //节点值释放函数
    void (*free) (void *ptr);
    //节点值对比函数
    int (*match) (void *ptr, void *key);
}list;
  • 链表被用于实现Redis 的各种功能，比如列表键，发布与订阅，慢查询，监视器等。
  • Redis 的链表是双端无环链表，每个链表使用一个 list 结构来表示，带有头尾指针和长度等信息。
  • 通过为链表设置不同的类型特定函数，Redis 的链表可以用于保存各种不同类型的值。

三、 字典

字典： 符号表，关联数组，映射（map），是一种用于保存键值对的抽象数据结构。

字典是 Redis 数据库的底层实现。

字典是 Hash 键的底层实现之一。

1、字典的实现

1、哈希表是字典的底层实现。一个 hash 表里可以有多个 hash 节点，每个 hash 节点就保存了字典中的一个键值对。

typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值==size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}dictht;
  • table 是一个数组，数组中的每个元素都是一个指向dictEntry 的指针。
  • 每个dictEntry 结构都保存着一个键值对。

2、哈希表节点

哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对。

typedef struct dictEntry{
    void *key;
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    }v;
    //指向下一个哈希表节点，形成链表
   struct dictEntry *next;
}dictEntry
  • v 属性保留着键值对中的值，可以是一个指针，也可以是一个uint64 整数，也可以是 int64 整数。

4、字典的结构

typedef struct dict{
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx;
}dict;
  • type 是一个指向 dictType 的指针，每个 dictType 结构保存了一簇用于操作键值对的函数
  • privatedata 保存了需要传给函数的可选参数
  • ht 属性保存了两个dictht 哈希表，一般使用 ht[0]，ht[1]在rehash 时使用
  • rehashidx记了了 rehash 的进度，没有进行时，值为 -1.

5、哈希算法

Redis 计算哈希值和索引值的方法：

  • 使用哈希函数，计算 key 的哈希值
  • 使用哈希表的 sizemask 属性和哈希值，计算出索引值
  • 将该键值对，放到哈希表数组的索引位置上
5.1、解决键冲突

Redis的哈希表使用链地址法来解决键冲突。

多个哈希表节点可以用next 指针构成一个单向链表。

5.2、rehash

当哈希表的键值对数量太多或太少时，程序需要对哈希表的大小进行相应的扩展或收缩。

  1. 为字典的ht[1]重新分配空间。
  2. 将保存在 ht[0]中的所有键值对 rehash 到 ht[1]上面。rehash 重新计算键的哈希值和索引值，重新将键值对放置到 ht[1]哈希表的指定位置上。
  3. 当 ht[0]的所有键值对都迁移到了 ht[1]之后，释放 ht[0]，将 ht[1]设置为 ht[0]，并在 ht[1]创建一个新的哈希表，为下次 rehash做准备。

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

Load_factor = ht[0].used / ht[0].size

5.3、渐进式rehash

将 ht[0]里所有的键值对 rehash 到ht[1]里面的动作，是分多次、渐进式的完成的。

在 rehash 进行期间，每次对字典执行增删改查时，会顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx 属性的值增加 1。

当 rehashidx 为 -1 时，表示 rehash完成。

  • 渐进式 rehash 过程中，删改查会在两个哈希表进行。
  • 新增只会在ht[1]上进行。

渐进式 rehash 避免了集中式 rehash 带来的庞大计算量。

四、 跳跃表

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

跳跃表是 Redis 有序集合键的底层实之一。

跳跃表在集群节点中用作内部数据结构。

1、跳跃表的实现

跳跃表由两个结构定义：

  • zskiplistNode 跳跃表节点
  • zskiplist 跳跃表节点的相关信息：节点数量，头尾指针

1、跳跃表节点

typedef struct zskiplistnode{
    //层，层高是 1~32 之间的随机数
    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度,记录两个节点之间的距离
        //累计起来为节点的排位
        unsigned int span;
    }level[];
    //后退指针
    struct zskiplistNode *backward;
    //分值，节点按照分值大小来排序
    double score;
    //成员对象，每个表中的对象时唯一的，指向一个字符串对象
    robj *obj;
}zskiplistNode;

2、跳跃表

zskiplist结构可以快速访问跳跃表的头尾节点，或者快速的获取节点数量。

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

五、 整数集合

整数集合是集合键的底层实现之一。

用于保存整数值的集合。

可以保存三种类型的整数值，并且不重复。

1、整数集合的实现

typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量，是 contents 数组的长度
    uint32_t length;
    //保存元素的数量
    int8_t contents[];
}intset;
  • 整数集合的每个元素都是 contents 数组的一个数组项（item），按从小到大有序排列，并且不包含任何重复项。

2、升级

  1. 根据 新元素的类型，扩展 contents 大小
  2. 将原有元素都转换成与新元素相同的类型，维持有序不变。
  3. 将新元素添加到底层数组里面。

升级可以提升整数集合的灵活性，也可以尽可能的节约内存。

不支持降级操作。

六、 压缩列表

压缩列表 ziplist 是列表键和哈希键的底层实现之一

1、压缩列表的构成

压缩列表由一系列特殊编码的连续内存块组成的顺序性数据结构。

一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

  • zlbytes：表示压缩列表的总长度
  • zltail：记录末尾节点距离头的偏移量
  • zllen：记录了包含的节点数
  • entryx：压缩列表的各个节点
  • zlend：记录压缩列表的末端

2、压缩列表节点

每个节点可以保存一个字节数组或者一个整数值

  • previous_entry_length：前一个节点的长度
    • 以 254区分成两种不同的情况。
    • 可以用他来计算出前一个节点的起始地址，用于从尾向头遍历
  • encoding：记录了content保存的数据类型以及长度
  • content：保存节点的值

3、连锁更新

添加和删除节点都可能导致连锁更新，连锁更新 previous_entry_length。最坏的复杂度为 O(N^2)，这种操作出现几率不高。

压缩表的平均复杂度为 O(N)。