Redis底层支撑数据结构简介

Redis提供了5种常用的数据结构:字符串(string),哈希(hash),列表(list),集合(set),有序集合(sorted set).

那redis底层是用什么样的数据结构对其支撑的呢?

注:以下数据结构是基于redis V4.0版本.

Redis底层提供了8种数据结构做为支撑数据结构:

源码参考:object.c

char *strencoding(int encoding) {
switch(encoding) {
// 小于等于44字节时sds数据结构
case OBJ_ENCODING_RAW: return "raw";
//64 位有符号整数类型
case OBJ_ENCODING_INT: return "int";
// 哈希表
case OBJ_ENCODING_HT: return "hashtable";
// 快表
case OBJ_ENCODING_QUICKLIST: return "quicklist";
// 压缩列表
case OBJ_ENCODING_ZIPLIST: return "ziplist";
// 存储无重复整数类型的数据结构
case OBJ_ENCODING_INTSET: return "intset";
// 跳跃表
case OBJ_ENCODING_SKIPLIST: return "skiplist";
// 大于44字节时sds数据结构
case OBJ_ENCODING_EMBSTR: return "embstr";
default: return "unknown";
    }
}

数据结构说明

对这些数据结构中较陌生部分,做下简单说明.

1. raw和embstr

这两种数据结构都是基于sds数据结构的;

是对字符串,数字,位图等类型数据的存储,数据结构及优化可以参考Redis SDS.这里不在赘述.

之所以会有两种数据格式,是因为redis分配内存空间的单位是2^n,这里是需分配64字节空间,去掉头部等相关信息后,embstr格式中只剩下44字节存储字符串相关信息了.这也解释了为什么是以44字节的长度区分出两种数据结构.

2. skiplist

一种基于线性表实现简单的快速搜索结构,详细说明可以参考跳跃表,这里不再赘述.

3. ziplist

是以连续的内存空间来表示双链表结构,比双向链表节点节省了前驱和后驱指针的空间,在 64 位机器上会节省了8字节空间.

ziplist的基本结构

zlbytes: 4字节,表示ziplist占用的字节总数(也包括zlbytes本身占用的4个字节).

zltail: 4字节,表示ziplist表中最后一项(entry)在ziplist中的偏移字节数.方便快速从尾端快速地执行push或pop操作.

zllen: 2字节,表示ziplist中数据项(entry)的个数.

zlend: ziplist最后1个字节,是一个结束标记,值固定等于255.

entry是典型的TLV(type-length-value)数据结构,下图是省略了部分数据项

4. quicklist

quicklist 是双向链表和ziplist的组合数据结构

是一个空间和时间的折中:

• 双向链表便于在两端进行push和pop操作,但是内存开销比较大.首先,每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表容易产生内存碎片.
• ziplist由于是一整块连续内存,所以存储效率很高.但是,它不利于修改操作,每次数据变动都会重新分配,当ziplist长度很长的时候,会导致大批量的数据拷贝,降低性能.

5. intset

一个集合元素不多,并只有整数时,使用的数据结构.

源码参考intest.h

contents[]会根据encoding的不同,选择不同数量的数组区间表示一个存储元素,类似于分别存储一个数值的高位和地位.

typedef struct intset {
    uint32_t encoding; // 编码方式,int16_t/int32_t/int64_t
    uint32_t length; // contents长度
    int8_t contents[]; // 存储值
} intset;

Redis底层支撑的数据结构已经介绍完了,后续文章中会介绍数据结构的对应关系和转换.