01-redis数据结构与对象
3. redis数据结构与对象
redis对外支持数据结构
- 字符串 （string）
- 字符串列表（list）
- 字符串集合（sets）
- 有序字符串集合（sorted sets）
- 哈希（hash）
redis内部数据结构
1. 字符串
简单动态字符串 - 外部字符串数据格式的底层实现
// sds.h/sdshdr结构
struct sdshdr {
int len; // 字符串长度 即已使用的字符串长度
int free; // 未使用的字节长度
char buf[]; // 字节数组 保存字符串
};
2. 链表
链表 - 外部字符串列表数据格式的底层实现
// adlist.h/listNode结构
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value; // 节点的值
}listNode;
// adlist/list结构
typedef struct list {
listNode *head;
listNode *tail;
unsigned lone len; // 链表包含节点数量
void *(dup)(void *ptr); // 节点值复制函数
void *(*free)(void *ptr); // 节点值释放函数
void *(match)(void *ptr, void *key); // 节点值对比函数
}list;
3. 字典
字典，又称符号表，关联数组，映射。用于保存键值对的抽象数据结构。 - 数据库的增删改查和哈希键的底层实现
哈希表
// dict.h/dictEntry结构
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
}v;
struct dictEntry *next;
} dictEntry;
// dict.h/dictht结构
typedef struct dictht {
dictEntry **table; // 哈希数组
unsigned long size; // 哈希表数组大小
unsigned long sizemask; // 哈希表数组大小掩码，总是size - 1
unsigned long used; // 哈希表已有节点数量
}dictht;
字典
// dict.h
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 哈希表, 一个正常哈希，一个用于rehash
int trehashidx; // rehash索引 当rehash不再进行时 值为-1
} dict;
typedef struct dictType {
// 计算哈希值函数
unsigned int (*hashFunction)(const void *key);
// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);
// 复制值的函数
void *(*objDup)(void *privdata, const void *key);
// 对比键的函数
void *(keyCompare)(void *provdata, const void *key1, const void *key2);
// 销毁键的函数
void *(keyDestructor)(void *privdata, void *key);
// 销毁值的函数
void *(valDestructor)(void *privdata, void *key);
} dictType;
3. 跳跃表
跳跃表 - 字符串有序集合数据格式的底层实现
还用在集群节点中用作内部结构
// redis.h
typedef struct zskiplistNode {
struct zskiplistNode *backward; // 后退指针
double score; // 分值
robj obj; // 成员对象
struct zskiplistLevel { // 层
struct zskiplistNode *forward; // 前进指针
unsigned int span; // 跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length; // 表节点的数量
int level; // 表中层数最大的节点层数
} zskiplist;
每个跳跃表节点的层高都是1~32之间的随机数
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序
5. 整数集合
整数集合 - 集合键的底层实现
// intset.h
typedef struct intset {
uint32_t encoding; // 编码方式
uint32_t length; // 集合包含的元素数量
int8_t contents[]; // 保存元素的数组
} intset;
/*
其中 encoding属性取值为：指明conetens数组元素单元的大小
INTSET_ENC_INT16
INTSET_ENC_INT32
INTSET_ENC_INT64
可自动升级操作
*/
6. 压缩列表
压缩列表 - 是列表键哈哈希键的底层实现之一
压缩列表可以保存多个节点，每个节点可以保存一个字节数组或整数值
结构如下：
| 4字节 | 4字节 | 2字节 | 不定 | 不定 | ... | 不定 | 1字节 |
|---|---|---|---|---|---|---|---|
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
- zlbtyes：记录整个压缩列表暂用的内存字节数
- zltail：压缩列表起始地址加上这个偏移量可以确定entryN表尾节点的地址
- zllen：记录压缩列表节点个数
- zlend：特殊值0xFF, 用于标记压缩列表的末端
- entryN：
| previous_entry_length | encoding | content |
|---|
- previous_entry_length：记录压缩列表前一个节点的长度；1字节或者5字节
若前一个字节长度小于254，该字段占1字节；
否则占5字节，这时候第一个字节设置为0xFE, 剩下4个字节表示前一个节点的长度
- encoding：记录了节点content属性所保存数据的类型及长度
有点复杂 - 先不了解 见《redis设计与实现》
- content：保存节点的值
连锁更新 ----> 见《redis设计与实现》
添加新节点到压缩列表或删除节点可能会引发连锁更新操作，但是这种机率并不高
7. 对象
对象就是上面所说的redis对外支持的数据结构，这里是用对象更为合适吧
- 字符串对象
- 列表对象
- 哈希对象
- 集合对象
- 有序集合对象
还实现了基于引用计数的内存回收机制，当程序不再使用某个对象时，这个对象所占用的内存会被释放
还通过这个引用计数实现对象共享机制
typedef struct redisObject {
unsigned type:4; // 类型
unsigned encoding:4; // 编码
void *ptr; // 指向底层数据结构指针
...
} robj;
/*
type: 五种对象类型
REDIS_STRING -> string
REDIS_LIST -> list
REDIS_HASH -> hash
REDIS_SET -> set
REDIS_ZSET -> zset
*/
/*
encoding: 底层实现的数据结构
REDIS_ENCODING_INT -> long类型的整数
REDIS_ENCODING_EMBSTR -> embstr编码的简单动态字符串
REDIS_ENCODING_RAW -> 简单动态字符串
REDIS_ENCODING_HT -> 字典
REDIS_ENCODING_LINKEDLIST -> 双端链表
REDIS_ENCODING_ZIPLIST -> 压缩列表
REDIS_ENCODING_INTSET -> 整数集合
REDIS_ENCODING_SKIPLIST -> 跳跃表和字典
*/
- 字符对象 可以是 整数数值 或 emstr 或 简单动态字符串实现
- 列表对象 可以是 压缩列表 或 双端队列
- 哈希对象 可以是 压缩列表 或 字典实现
- 集合对象 可以是 整数集合 或 字典实现
- 有序集合对象 可以是 跳跃表 或 字典实现、
7.1 字符串对象
如果字符串对象是整数值，且可以用long类型表示 采用编码方式是int
如果字符串对象是字符串值，且字符串长度超过39个字节，采用编码方式是raw
如果字符串对象是字符串值，且字符串长度小于等于39个字节，采用编码方式是embstr
区别raw与embstr两种类型的简单动态字符串
编码转换
int编码的字符串对象 和 embstr编码的字符串对象 在条件满足的情况下， 会被转换成 raw编码的字符串对象
7.2 列表对象
当列表同时满足以下两个条件时，采用编码方式为ziplist，否则为linklist
- 列表对象保存的所有字符串元素长度都小于64字节（可配）
- 列表对象保存的元素数量小于512个（可配）
编码转换
当以上两个条件被破坏时，ziplist编码会转换成linklist编码
7.3 哈希对象
当哈希同时满足以下两个条件时，采用编码方式为ziplist，否则为hashtable
- 哈希对象保存的所有字符串元素长度都小于64字节（可配）
- 哈希对象保存的元素数量小于512个（可配）
编码转换
当以上两个条件被破坏时，ziplist编码会转换成hashtable编码
7.4 集合对象
当集合同时满足以下两个条件时，采用编码方式为intset，否则为hashtable
- 集合对象保存的所有元素都是整数值
- 集合对象保存的元素数量小于512个（可配）
编码转换
当以上两个条件被破坏时，ziplist编码会转换成hashtable编码
7.5 有序集合对象
typedef struct zset {
zskiplist *zsl;
dict *dict;
} zset;
当有序集合同时满足以下两个条件时，采用编码方式为intset，否则为skiplist
- 有序集合对象保存的所有元素成员的长度都小于64个字节（可配）
- 有序集合对象保存的元素数量小于128个（可配）
编码转换
当以上两个条件被破坏时，ziplist编码会转换成skiplist编码
7.6 内存回收
在对象结构中增加一个引用计数技术实现内存回收机机制
typedef struct redisObject {
...
int refcount; // 引用计数
...
} robj;
/*
当创建新对象时，引用计数加1
当对象被一个新程序使用时，引用计数加1
当对象不再被一个程序使用时，引用计数减1
当引用计数数值为0时，对象所占用的内存会被释放
*/
7.7 对象共享
引用计数除了可以实现内存回收机制，还可以带有对象共享的作用
--- 节约内存
7.8 对象的空转时长
reidsObject结构还有一个字段lru属性，该属性记录例如对象最后一次被命令程序访问的时间
#define LRU_BITS 24
typedef struct redisObject {
...
unsigned lru:LRU_BITS; // 引用计数
...
} robj;
参考：
黄键宏老师的《redis设计与实现》，机械工业出版社
