redis对象结构
注：本文基于redis3.0
redis是一种键值（key-value）数据库，键的数据类型是字符串，而值的数据类型有多种。在redis源码redis.h中定义了存储对象的结构体：
typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 引用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;
// 对象类型
#define REDIS_STRING 0 // 字符串对象
#define REDIS_LIST 1 // 列表对象
#define REDIS_SET 2 // 集合对象
#define REDIS_ZSET 3 // 有序集合对象
#define REDIS_HASH 4 // 哈希对象
// 对象编码
#define REDIS_ENCODING_RAW 0 // 简单动态字符串
#define REDIS_ENCODING_INT 1 // long型整形数值
#define REDIS_ENCODING_HT 2 // 字典
#define REDIS_ENCODING_ZIPMAP 3 // 压缩字典
#define REDIS_ENCODING_LINKEDLIST 4 // 双端列表
#define REDIS_ENCODING_ZIPLIST 5 //压缩列表
#define REDIS_ENCODING_INTSET 6 // 整数集合
#define REDIS_ENCODING_SKIPLIST 7 // 跳表
#define REDIS_ENCODING_EMBSTR 8 // EMBSTR编码的简单动态字符串
其中，type表示该对象的对象类型，redis定义了 String,List,Set,Zset,Hash 五种对象类型。encoding表示对象底层所使用的编码，redis3.0定义了9种对象编码。对于同一种对象类型，redis在不同情况下使用不同的对象编码来实现对象的存储，目的是为了提高存储效率和执行效率。
Redis对象编码
REDIS_ENCODING_RAW（简单动态字符串）
redis中，各种编码对象的创建定义在object.h中，对于简单字符串对象的创建定义如下。sdshdr结构定义了字符数组buf[]作为数据存储空间，len与free分别表示已使用空间和可用空间的长度，redisObj中ptr指向字符数组所在的数据空间，字符串数组是能够改变的。
/**object.c */
robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o));
o->type = type;
o->encoding = REDIS_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;
/* Set the LRU to the current lruclock (minutes resolution). */
o->lru = LRU_CLOCK();
return o;
}
// 创建一个 REDIS_ENCODING_RAW 编码的字符对象
// 对象的指针指向一个 sds 结构,sdsnewlen的实现在sds.h中
robj *createRawStringObject(char *ptr, size_t len) {
return createObject(REDIS_STRING,sdsnewlen(ptr,len));
}
/**sds.h */
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
// 根据是否制定大小进行空间分配
if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
}
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0;
if (initlen && init)
memcpy(sh->buf, init, initlen);
sh->buf[initlen] = '\0';
return (char*)sh->buf;
}
image.png
REDIS_ENCODING_EMBSTR（embstr编码字符串）
embstr编码对象也是字符串对象，如果字符串对象的长度小于等于39字节，则选择embstr编码方式，否则使用raw编码。
/** object.h */
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39
robj *createStringObject(char *ptr, size_t len) {
if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
return createEmbeddedStringObject(ptr,len);
else
return createRawStringObject(ptr,len);
}
/**
* 创建一个REDIS_ENCODING_EMBSTR编码的字符串对象
*/
robj *createEmbeddedStringObject(char *ptr, size_t len) {
// sdshdr的内存空间与robj一起分配，是不可改变的
robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr)+len+1);
struct sdshdr *sh = (void*)(o+1);
o->type = REDIS_STRING;
o->encoding = REDIS_ENCODING_EMBSTR;
o->ptr = sh+1;
o->refcount = 1;
o->lru = LRU_CLOCK();
sh->len = len;
sh->free = 0;
if (ptr) {
memcpy(sh->buf,ptr,len);
sh->buf[len] = '\0';
} else {
memset(sh->buf,0,len+1);
}
return o;
}
embstr与raw的不同在于：
- embstr编码的对象的创建只进行一次内存分配，而raw为两次（sdshdr结构分配一次，robj结构分配一次，embstr两个结构内存空间一次性分配）；embstr对象的ptr指针直接指向sdshdr的buf数组，而raw指向sdshdr对象。
- embstr对象释放内存空间的次数也是一次
- embstr对象robj与sdshdr在连续的内存空间，能更高的利用缓存优势。
- embstr对象是只读形式，redis并没有提供任何修改embstr对象的方法，对该类型对象的修改都是转换成raw后进行的。
image.png
REDIS_ENCODING_INT（长整形数值）
如果一个字符串能够转换为long型，那么该字符串会被转换为long类型，redisObject的ptr指针指向该long对象。创建一个long对象时，当long对象符合redis共享整数的范围（[0,10000)），会返回一个共享对象；当数值可以用long类型表示（LONG_MIN <= value <=LONG_MAX）时，会创建一个encoding=REDIS_ENCODING_INT的对象，ptr指针指向long型对象；不符合上述两个情况时，创建一个encoding=REDIS_ENCODING_RAW的字符串对象。
注：redis还提供long double类型对象的创建，并不会使用INT进行编码，而是将尾部多余的0清除后（比如3.14000转换为3.14）,生成一个RAW编码的字符串对象。
// redis.h
// 共享整数边界
#define REDIS_SHARED_INTEGERS 10000
/*
* object.c
* 根据传入的整数值，判断是否能使用INT 编码保存，否则创建一个RAW编码的字符串对象
*/
robj *createStringObjectFromLongLong(long long value) {
robj *o;
// value 的大小符合 REDIS 共享整数的范围：[0, 10000)
// 那么返回一个共享对象
if (value >= 0 && value < REDIS_SHARED_INTEGERS) {
incrRefCount(shared.integers[value]);
o = shared.integers[value];
// 不符合共享范围，创建一个新的整数对象
} else {
// 值可以用 long 类型保存，创建一个 REDIS_ENCODING_INT 编码的字符串对象
if (value >= LONG_MIN && value <= LONG_MAX) {
o = createObject(REDIS_STRING, NULL);
o->encoding = REDIS_ENCODING_INT;
o->ptr = (void*)((long)value);
// 值不能用 long 类型保存（long long 类型），将值转换为字符串，
// 并创建一个 REDIS_ENCODING_RAW 的字符串对象来保存值
} else {
o = createObject(REDIS_STRING,sdsfromlonglong(value));
}
}
return o;
}
REIDS_ENCODING_LINKEDLIST（双向链表）
redis中双向链表定义与Java中LinkedList类似，包含头尾两个节点，每个节点有自己的前驱和后继节点，每新增一个节点都需要重新申请一块内存。根据执行的命令决定节点插入的位置，lpush将节点插入列表头部（head=node），rpush将节点查询列表尾部（tail=node）。
redis还维护着一个列表迭代器listIter，记录next指针及迭代方向direction，在对列表中的元素进行操作时，使用迭代器进行元素遍历。
/*
* object.c
* 创建一个 LINKEDLIST 编码的列表对象
*/
robj *createListObject(void) {
// 构建一个空的双端链表
list *l = listCreate();
// 常见type=REDIS_LIST的对象，分配内存空间
robj *o = createObject(REDIS_LIST,l);
// 设置list的释放函数
listSetFreeMethod(l,decrRefCountVoid);
// 将编码更改为linkedlist
o->encoding = REDIS_ENCODING_LINKEDLIST;
return o;
}
/** adlist.h */
/*
* 双端链表结构
*/
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
//...
// 链表所包含的节点数量
unsigned long len;
} list;
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
/** adlist.c */
/**
* 创建一个新的链表
*/
list *listCreate(void)
{
struct list *list;
// 分配内存
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
// 初始化属性
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
/**
* 新增节点至链表尾部（rpush命令）
*/
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
// 为新节点分配内存
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
// 保存值指针
node->value = value;
// 添加节点到空链表
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
// 添加节点到非空链表
} else {
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
// 更新链表节点数
list->len++;
return list;
}
image.png
REDIS_ENCODING_ZIPLIST（压缩列表）
当列表中的数据量比较小且每个元素不大时，列表就可以采用压缩列表的方式实现。zipList是由一系列特殊编码的连续内存块组成的顺序存储结构，类似于数组，与数组不同的是，ziplist中每个节点所占的内存大小可以不同。每个节点可以用于存储一个整数或者一个字符串。
ziplist的一般布局为<zlbytes><zltail><zllen><entry><entry><zlend>
zlbytes：32位无符号整数，保存ziplist的内存大小
zltail：保存着到达列表最后一个节点的偏移量，这个偏移量使得对表位的pop操作可以在无须遍历整个列表的情况下进行。
zllen：保存列表中节点数量。
entry：节点
zlend：长度为1个字节，值为255，标记列表的结尾。
image.png
ziplist的节点信息存储在zlentry结构中，每个节点主要由三部分组成：prevrawlen，data，enconding
typedef struct zlentry {
// prevrawlen ：前置节点的长度
// prevrawlensize ：编码 prevrawlen 所需的字节大小
unsigned int prevrawlensize, prevrawlen;
// len ：当前节点值的长度
// lensize ：编码 len 所需的字节大小
unsigned int lensize, len;
// 当前节点 header 的大小
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 当前节点值所使用的编码类型
unsigned char encoding;
// 指向当前节点的指针
unsigned char *p;
} zlentry;
（1）prevrawlen：前置节点的长度，在程序从后面向前遍历时使用。
编码前置节点的长度的定义如下：
- 如果前置节点的长度小于254字节，使用1字节保存这个长度；
- 如果前置节点的长度大于等于254字节，使用5个字节保存这个长度：第1个字节的值为254，用于标识这是一个5字节长的长度值；之后的4个字节用于保存前置节点的实际长度。（边界为254而不是255的原因为zlend的值为255，用于标志列表的结尾）
image.png
（2）encoding：当前节点所保存的值的类型和长度
- 如果节点保存的是字符串，节点header的头2个位将保存编码字符串长度所使用的类型，之后是字符串的实际长度。
/** 字符串编码类型*/
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
image.png
- 如果节点保存的是整数值，那么节点header的头2位将被设置为11，之后2位则用于标识节点所保存的整数的类型。
// int16_t类型的整数，长度为2字节:00 /11000000/data/
#define ZIP_INT_16B (0xc0 | 0<<4)
// int32_t类型的整数，长度为4字节:01 /11010000/data/
#define ZIP_INT_32B (0xc0 | 1<<4)
// int63_t类型的整数，长度为8字节:10 /11100000/data/
#define ZIP_INT_64B (0xc0 | 2<<4)
// 24位（3字节）长的整数:11 /11110000/data/
#define ZIP_INT_24B (0xc0 | 3<<4)
// 8位（1字节）长的整数 /11111110/data/
#define ZIP_INT_8B 0xfe
// 数值范围1-13，encoding低四位表示data，没有另外的data部分 /1111xxxx/
#define ZIP_INT_IMM_MASK 0x0f
ziplist存储的内容是在连续的内存空间中的，相比起双端链表，ziplist节点存储的数据大小是不固定的，使得数据存储更加紧凑，紧凑的数据能够更好地利用CPU缓存；其次，ziplist省略了前驱和后续节点的指针空间，在64位机器上需要占用8B，只要清晰地描述每个数据项的边界，就能得到前驱后继数据项的位置，这在数据量小的列表上压缩效果是很明显的。因此ziplist能够很好的节省内存空间。
由于ziplist允许列表在两端进行O（1）复杂度的push和pop操作，但是这些操作需要对整个ziplist进行内存重分配，所以对于节点数量比较多的情况，ziplist的效率并不高。ziplist能存储的节点数量是有限的，zllen标识ziplist中节点的数量，占2bytes。
REDIS_ENCODING_HT（字典）
redis中HashTable由dict这个结构实现，dict表示为一个字典，每个字典中都包含两个哈希表，用于实现渐进式rehash，ht[0]存放实际数据，ht[1]用于rehash过程数据中转。当哈希表中已使用节点的数量和字典大小之间的比率大于dict_force_resize_ratio=5（强制rehash的比率）时，会进行扩容。
/** dict.h */
/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
/*
* 字典
*/
typedef struct dict {
// 字典类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引,不处于rehash时，值为-1
int rehashidx;
// 目前正在运行的安全迭代器的数量
int iterators;
} dict;
对于键值对的增加，首先计算键在哈希表中的索引值，判断键是否已在字典存在，如果存在，则返回null，否则创建新的哈希节点，插入链表头部，并插入到字典中，返回节点本身。
image.png
REDIS_ENCODING_INTSET（整数列表）
intset是一个有序的整形数组，数组存放相同类型的整数，支持三种长度类型（int16_t、int32_t，int64_t）。三种长度类型逐渐升级，初始为int16_t，当集合中都是int16_t类型的整数，此时插入一个int32_t的数据，为了维持集合中数据类型的一致性，所有的数据都会被转换为int32_t类型，会进行内存重新分配。
/** intset.h */
/*
* intset 的编码方式
*/
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
intset中元素的查找过程为使用二分查找算法，时间复杂度度为O(logN)。因为底层数组是有序的，所有先判断查找的值与首位两个元素的大小，小于首元素或大于尾元素，都说明查询的数据不在数组中，反之则进行二分查找。而由于数据插入的过程总可能会涉及数据类型升级，数据插入的时间复杂度不一定为O(logN)，而是O(N)。
/** intset.c*/
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
// 处理列表为空时的情况
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
// 因为底层数组是有序的，如果 value 比数组中最后一个值都要大
if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
// 因为底层数组是有序的，如果 value 比数组中最前一个值都要小
} else if (value < _intsetGet(is,0)) {
if (pos) *pos = 0;
return 0;
}
}
// 在有序数组中进行二分查找
// T = O(log N)
while(max >= min) {
mid = (min+max)/2;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
// 检查是否已经找到了 value
if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
REDIS_ENCODING_SKIPLIST(跳表)
skiplist是redis对有序集合的另一种编码方式，能够实现有序集合的快速查找，在大多数情况下其查找效率与平衡树差不多，但它的实现比较简单，可以代替平衡树。
redis对REDIS_ENCODING_SKIPLIST的实现不仅用到了skiplist，还有dict。dict的作用是查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可以是范围查找）。比如以下几个典型的zset命令：
ZADD key score1 member1 // 向有序集合添加元素
ZSCORE key member1 // 根据member查找对应的score
ZREVRANGE key 0 3 // 查询从大到小排名前4的分数对应的member
ZSCORE命令根据member查询对应的score，使用dict进行查询，时间复杂度为O（1）;
ZREVRANGE命令是一个有序的范围查询，显示dict无法支持，而使用skiplist则容易实现，时间复杂度为O(logN)。
dict和skiplist的结合使用，使得有序集合的查询能够更加快速高效。dict在之前的小节已总结，而skiplist的具体实现算法可查找其他资料，redis的对skiplist的实现基本一致，本节讨论skiplist在redis的结构。
/** redis.h */
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
/*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作以及范围操作
zskiplist *zsl;
} zset;
image.png
上图为redis中一个skiplist的可能结构，包含三个节点，score分别为10、 20、 30，横线上的括号表示对应的span值。即当前指针跨越了多少个节点，这个计数不包括指针的起始节点，但包括指针的终止节点。
当在这个skiplist中查找score=30的节点时，查询路径会经过上图标红的指针，这些指针上面的span值累加就得到score=30的节点从小到大的排名，即（2+1）-1=2（rank值从0开始，需要减1）。如果需要计算从大到小的排名，只需要用skiplist的长度减去查找路径span的累加值，即3-（2+1）=0。通过上述方法可以实现zrange或者zrevrange这两个根据排名获取范围值的操作，时间复杂度与查找节点一样，为O(logN)。
redis使用skiplist而不是平衡树的原因？
- skiplist并不会占用太多的内存空间。
- 有序集合更多的操作时zrange和zrevrange等范围查找，使用平衡树需要通过遍历实现，树节点之间跨度大，数据远没有skiplist紧凑，没法很好的利用缓存，相比下skiplist更有优势。
- skiplist比平衡树更简单更容易实现。平衡树每新增一个节点，都可能需要进行旋转平衡，而skiplist新增节点的复杂度为O(logN)，通过类似二分查找定位插入数据位置，不需要移动其他节点数据。
redis对象类型
REDIS_STRING
字符串对象的编码可以是int、raw或者embstr。
如果一个字符的内容能够转化为long，那么该字符串会被转换为long类型，使用REDIS_ENCODING_INT编码。
如果字符串对象的长度小于39，那么该字符串对象会使用REDIS_ENCODING_EMBSTR编码，一次性分配内存，对象数据更紧凑，并减少一个指针的开销。
其余情况则使用REDIS_ENCODNG_RAW编码。
REDIS_LIST
列表对象的编码可以是ziplist或者linkedlist。
当数据量比较小且节点数据不大时，列表使用REDIS_ENCODING_ZIPLIST编码，否则使用REDIS_ENCODING_LINKEDLIST编码。
redis.conf中定义了两者之间的转换边界。当以下两个条件之一满足时，ziplist会转换为linkedlist：
- 列表中的节点数量超过512
- 列表新增节点的数据长度超过64
# Similarly to hashes, small lists are also encoded in a special way in order
# to save a lot of space. The special representation is only used when
# you are under the following limits:
list-max-ziplist-entries 512
list-max-ziplist-value 64
REDIS_SET
集合对象的底层实现可以是intset或者hashtable。
当集合中的元素都能用int（int16_t、int32_t、int64_t）表示时，所有数据会被转换为整数数值，使用REDIS_ENCODING_INTSET编码。
当集合中元素数据类型不为整数时，则使用hashtable进行存储，使用REDIS_ENCODING_HT编码。
redis.conf中定义了intset的最大节点数：
# Sets have a special encoding in just one case: when a set is composed
# of just strings that happens to be integers in radix 10 in the range
# of 64 bit signed integers.
# The following configuration setting sets the limit in the size of the
# set in order to use this special memory saving encoding.
set-max-intset-entries 512
REDIS_ZSET
有序集合的底层实现有两种，一种是ziplist，另一种是skiplist+dict。
ziplist中集合对象是按照<member1><score1><member2><socre2>进行存储的，而且是数据是按score有序（从小到大）的。同样只适用于较少的数据量。
skiplist与dict的结合使用，使得redis能快速通过member定位数据（dict），快速通过score进行范围查找（skiplist）。
redis.conf中定义ziplist与skiplist+dict的转换边界。当满足下面两个条件时，ziplist将转换为skiplist+dict：
- 有序集合中节点数量（键值对）超过128
- 有序集合新增节点数据大小超过64
# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
REDIS_HT
哈希对象的底层实现可以是ziplist或者hashtable。
ziplist中的哈希对象是按照<key1><value1><key2><value2>进行存储的，当数据数量不多且数据不大时，这种存储方式效率比较高。而hashtable则有dict结构实现。
redis.config中定义了ziplist与hashtable之间转换的边界。当满足以下两个条件时，ziplist会转换为dict：
- 数据节点（键值对）数量超过512
- 新增节点数据大小超过64
# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
总结
redis的高效性和灵活性得益于对同一对象类型采用不同的底层结构，并在必要时进行转换。
ziplist是比较特殊的结构，在数据量较少且数据不大的情况下，列表、集合、有序集合、哈希表都可以使用压缩列表实现，它的特点是节省内存空间，这对redis这种内存数据库来说非常有效。embstr及zipmap的定义同样是为了优化内存的使用。
网友评论