一、redis中数据对象
redis有五大数据类型, 通过统一对象redisObject存储, redisObject的结构主要包含以下部分:
- type属性存储对象的类型, 也就是string, list, hash, set, zset中的一种。可以通过type命令查看。
- encoding属性记录对象的所使用的编码，即底层数据结构。
- ptr 指向底层数据结构的指针。
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"
二、不同数据类型对应的底层数据结构
- 字符串
- int:8个字节的长整型。
- embstr:小于等于39个字节的字符串。
- raw:大于39个字节的字符串。
Redis会根据当前值的类型和长度决定使用哪种内部编码实现。
- 哈希
- ziplist(压缩列表):当哈希类型元素个数小于hash-max-ziplist-entries 配置(默认512个)、同时所有值都小于hash-max-ziplist-value配置(默认64 字节)时，Redis会
使用ziplist作为哈希的内部实现，ziplist使用更加紧凑的 结构实现多个元素的连续存储，所以在节省内存方面比hashtable更加优秀。 - hashtable(哈希表):当哈希类型无法满足ziplist的条件时，Redis会使 用hashtable作为哈希的内部实现，因为此时ziplist的读写效率会下降，
而 hashtable的读写时间复杂度为O(1)。
- 列表
- ziplist(压缩列表):当列表的元素个数小于list-max-ziplist-entries配置 (默认512个)，同时列表中每个元素的值都小于list-max-ziplist-value配置时 (默认64字节)，
Redis会选用ziplist来作为列表的内部实现来减少内存的使 用。 - linkedlist(链表):当列表类型无法满足ziplist的条件时，Redis会使用 linkedlist作为列表的内部实现。
- quicklist ziplist和linkedlist的结合， 以ziplist为节点的链表(linkedlist)
- 集合
- intset(整数集合):当集合中的元素都是整数且元素个数小于set-max- intset-entries配置(默认512个)时，Redis会选用intset来作为集合的内部实 现，从而减少内存的使用。
- hashtable(哈希表):当集合类型无法满足intset的条件时，Redis会使 用hashtable作为集合的内部实现。
- 有序集合
- ziplist(压缩列表):当有序集合的元素个数小于zset-max-ziplist- entries配置(默认128个)，同时每个元素的值都小于zset-max-ziplist-value配 置(默认64字节)时，
Redis会用ziplist来作为有序集合的内部实现，ziplist 可以有效减少内存的使用。 - skiplist(跳跃表):当ziplist条件不满足时，有序集合会使用skiplist作 为内部实现，因为此时ziplist的读写效率会下降。
三、数据结构实现
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的优化：
- 空间预分配，不用担心字符串变更造成的内存溢出。
- 如果空间够用，则不会额外分配空间， 通过free属性。
- 如果修改后的 SDS 长度 len 小于 1MB，那么程序分配和 len 属性相等的未使用空间，此时 free 和 len 的值相同。所以此时数组的实际长度为 free + len + 1byte（额外的空字符 1 个字节）。
- 如果修改后的 SDS 长度大于 1MB，那么程序分配 1MB 的未使用空间。实际长度为 len + 1MB + 1byte。
- 惰性空间释放，字符串缩短，并不是立即重新分配内存，释放空间。
- 常数时间复杂度读取字符串长度， 通过len属性
- 二进制安全， c语言中空字符意味着字符串结束，SDS则不需要考虑，通过len判断是否结束。
分界线39或44的来源
- Redis中内存分配使用的是 jemalloc，jemalloc 分配内存的时候是按照 8、16、32、64 作为 chunk 的单位进行分配的。
- 为了保证采用embstr编码方式的字符串能被 jemalloc 分配在同一个 chunk 中，整个redisObject不超过64
- 因此OBJ_ENCODING_EMBSTR_SIZE_LIMIT = 64 - 16(redisObject) - 4(sdshdr的len属性) - 4(sdshdr的free属性) - 1(sdshdr的buf最后一位'\0') = 39。
- len和size之前使用unsign int，占4个字节，调整为调整为unit8_t， 占1个字节。并追加了一个char flag 1个字节。
4. ziplist
压缩列表是 Redis 为了节约内存而实现的，是一系列特殊编码的连续内存块组成的顺序型数据结构。 结构如下图：
- zlbytes 4字节，记录整个压缩列表占用的内存字节数。
- zltail 4字节，记录压缩列表表尾节点的位置。
- zllen 2字节，记录压缩列表节点个数。超过需要65535遍历。
- entry 列表节点，长度不定，由内容决定。
-
zlend 1字节，0xFF 标记压缩的结束。
压缩列表的节点结构如下图：
- privious_entry_length占四个字节，取决于前一个节点的长度，小于254字节，就是占1个字节，否则就是5个字节。
- enncoding 记录节点的content保存数据的类型和长度。
压缩列表的遍历：
通过指向表尾节点的位置指针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;
- encoding有三种属性值：INTSET_ENC_INT16，INTSET_ENC_INT32， INTSET_ENC_INT64， 分别表示用int16_t， int32_t, int64_tL类型的数组，进行数据存储。
当元素大小超过时，会进行升级。（不支持降级）
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;
-
redis的hash节点采用单链表结构，哈希表没有使用红黑树，对哈希节点进行优化。
ps： 在hash冲突严重时，大量hashcode落到同一个hash节点上，此时hash表退化成单链表。
在JDK1.8中采用HashTable对进行优化，当链表数量超过8时，使用红黑树替代链表。 -
rehash 由负载因子决定什么时候进行rehash。过程如下：
- 为ht[1]分配空间，大小为比当前ht[0]已使用值的两倍大的第一个2的整数幂。如，已使用空间7，则分配比7*2大的最近的2的整数幂，即16。
- 将ht[0]中所有键值对，rehash到ht[1]上。
- 完成迁移后，释放ht[0], 将ht[1]设置为ht[0], 在ht[1]处新建空白哈希表，为下一次rehash做准备。
- 渐进式rehash 当键值对数量巨大，一次性全部rehash将造成阻塞，服务暂停。所以拆分成多次，慢慢的将ht[0]中的数据rehash到ht[1]中。过程如下：
- 为ht[1]分配空间，同时持有两个哈希表(一个空表、一个有数据)。
- 维持计数器rehashidx，初始值为0，表示rehash开始。
- 每次增删改查，都顺带将ht[0]中的数据迁移到ht[1], rehashidx++.
- 直到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;
- skiplist是一种以空间换取时间的结构。由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点（索引），先在关键节点上查找，再进入下层链表查找。提取多层关键节点，就形成了跳跃表。
- 跳跃表在es的lucene索引也有有应用。
为什么用跳跃表不用平衡树
- skiplist算法实现简单得多。
- 跳跃表和平衡树的插入删除时间复杂度都是O(logn)，不过平衡树的插入和删除操作引发树结构的调整，操作复杂。skiplist只需要修改相邻节点的指针，操作简单。
- 查询单个key，跳跃表和平衡树的时间复杂度都是O(logn)，大体相当。
- 范围查找，平衡树要复杂，skiplist适合zset各种操作。
网友评论