我们都知道在 Reids 当中我们所保存的 key 都是字符串的形式,value 往往也是字符串或者字符串的集合。可见字符串也是 Redis 中最常用的一种数据结构。
我们也都知道 Redis 底层是用 C 语言所写的,但是 Redis 在字符串这并没有完全直接的使用 C 语言的字符串,因为对于 Redis 来说,C 语言的字符串会出现许多问题,在这并不能完全满足需求。
因为 C 语言当中,字符串的底层是字符数组,所以想要获取字符串的长度,就必须通过循环运算才能得到结果,不发直接获取字符串的长度;
并且在 C 语言当中,它的字符串结束会用 ‘\0’ 用来标注结束语言,这对 Redis 来说,是非二进制安全的;
在 C 语言当中一旦字符串创建好后,是保存在常量池当中,而保存在常量池当中,我们就都知道是无法修改的。
而正是因为这些原因,所以 Redis 创建了一种符合自己的字符串结构,称为简单动态字符串(Simple Dynamic String),简称为 SDS。
我们先看看创建 SDS 时的底层源码:(用 C 语言写的)
struct __attribute__ ((__packed__)) sdshdr8 {
/* uint8_t 中的8表示占 8 个字节 */
uint8_t len; /* 表示已保存的字符串的字节数,不包含表示结尾的标识符 */
uint8_t alloc; /* 表示申请的字节数,不包含表示结尾的标识符 */
unsigned char flags; /* 表示不同 SDS 的头部类型,用来控制 SDS 的头大小 */
char buf[]; /* 保存存进来的字符串 */
};
在这之中,我们显然看出存储的字符串字节数最大只为 2的8次方(-257 ~ +255) ,这显然是很不合理的,但是别慌, Redis 肯定不会犯这种很低级的操作,在 Redis 具体的实现当中,它实现了类似于 Java 当中多态这样的概念。(共有5 个)在这的 flags 就是对这个版本进行的一种控制。
这样显然就能满足我们的需求。
我们不停的说 SDS 是一个动态的字符串。
举个例子:我们现在要创建一个字符串 “hi” 的 SDS 的。
那么它初始创建的结构为:
现在我们要给 SDS 追加一段字符串“,Tom”,在这时 Redis 首先会申请新的内存空间:
如果新字符串小于1M,则新空间为扩展后字符串长度的两倍 + 1;
如果新字符串大于1M,则新空间为扩展后字符串长度+1M+1。
把这种需要分配略大于的实地需要的内存空间的方式就叫做称为内存预分配。
那么当前这个 SDS 括容后的结构就为:
至于尚敏的扩容机制中,最后都要加 1 ,就是为了保存字符串结尾的标识符,但是在 SDS 当中,标识字符串结束的符号是前面的 len 长度,所以从本质上来说,它是可以保存特使标识符,但是不建议使用。
SDS 优点
IntSet 是 Redis 当中 Set 集合的一种实现方式,是基于整数数组来实现的,并且具备可读可变,有序,且唯一的特征。
先看下它的源码:
typedef struct intset {
uint32_t encoding; /* 表示编码方式,支持存放16位、32位、64位 */
uint32_t length; /* 表示元素的个数 */
int8_t contents[]; /* 整数的数组,保存集合数据 */
} intset;
在这个当中 encoding 是由包含三种模式的,分别表示存储的整数的大小。
在 IntSet 当中,为了方便查找, Redsi 会将 IntSet 中的所有数据按照升序 的方式依次进行保存在 contents 数组当中。
现在我们要保存一个数组为 5,10,20 的数组,那么它的底层具体实现是:
现在,数组中每个数字都在 int16_t 的范围内,因此采用的编码方式是 INTSET_ENC_INT16,每部分占用的字节大小为:
encoding:4字节
length:4字节
contents:2字节 * 3 = 6字节
在这个时候,我们想向其中添加一个数字:5000,但是这个数字现在超过了当前了 int16_t 的范围,所以在这,IntSet 会发生自动升级编码的方式找到合适的大小。
所以它在扩容的大致流程为下:
最后修改一下结构体的头信息。
下面我们来看一下增加时候的源码:(代码里面我都做好了备注)
新增数据流程:
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);//获取当前值的编码
uint32_t pos;//要插入的位置
if (success) *success = 1;
//编码是否超过当前的 intset 的编码
if (valenc > intrev32ifbe(is->encoding)) {
//超出了编码规定,需要升级,调用intsetUpgradeAndAdd具体实现
return intsetUpgradeAndAdd(is,value);
}
// 当时添加的数据还没有超过
else {
// 在当前 intset 中查找值与 value 一样的元素角标
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
//若找到了,则无需在执行插入了,直接返回失败
return is;
}
// 数组扩容
is = intsetResize(is,intrev32ifbe(is->length)+1);
// 移动数组中的 pos 之后的所有元素到 pos+1,给新空间腾出空间
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
// 插入新元素
_intsetSet(is,pos,value);
// 重置元素的长度
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
IntSet 升级流程:
/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
//获取当前 intset 的编码
uint8_t curenc = intrev32ifbe(is->encoding);
//获取新编码
uint8_t newenc = _intsetValueEncoding(value);
// 获取元素个数
int length = intrev32ifbe(is->length);
//判断新加入的元素时大于0还是小于0,大于加队尾,小于加队首
int prepend = value < 0 ? 1 : 0;
// 重置编码为新编码
is->encoding = intrev32ifbe(newenc);
// 重置数组大小
is = intsetResize(is,intrev32ifbe(is->length)+1);
// 倒序遍历,逐个搬运旧元素到新的位置,_intsetGetEncoded按照旧编码方式查找旧元素
while(length--)// _intsetSet按照新编码方式插入新元素
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/* 插入新元素,prepend决定是队首还是队尾*/
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
// 修改数组长度
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
而在新增数据里面的,查找当前元素是否已存在,采用的是二分查找。(二分查找这的代码就不具体分析了,大致看一下)
众所周知,在 Redis 中,它是以键值对的形式(key-value pair)的数据库,所以我们就可以根据键来实现快速的增删改查,而键与值之间的映射关系就是通过 Dict 来实现的。
Dict主要是由三部分来实现的: 哈希表(DictHashTable)、哈写节点(DictEntry)、字典(Dict)
哈希表数据:
typedef struct dictht {
// entry数组
// 数组中保存的是指向entry的指针
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小的掩码,等于的是 size - 1
unsigned long sizemask;
// entry个数
unsigned long used;
} dictht;
哈希节点源代码:
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值
// 下一个Entry的指针
struct dictEntry *next;
} dictEntry;
在当我们向 Dict 里面添加键值对的时候,Redis 会首先根据 key 计算出 hash 值(h),然后利用 h & sizemask 与运算来计算元素应该存储到数组中的那个索引位置。
字典的源代码:
typedef struct dict {
dictType *type; // dict类型,内置不同的hash函数
void *privdata; // 私有数据,在做特殊hash运算时用
dictht ht[2]; // 在一个Dict包含两个哈希表,其中一个是当前数据,另一个一般是空,rehash时使用
long rehashidx; // rehash的进度,-1表示未进行
int16_t pauserehash; // rehash是否暂停,1则暂停,0则继续
} dict;
而在 Dict 里面它的存储方式图解为:
在这就可以观察到一个字典里面是有两个哈希表的,但是一般在使用的时候是只使用一个hash 表,另一个hash表只是在rehash的时候才会被使用。
Dict中的扩容:
在 Dict 当中的 HashTable 就是数组结合单向链表的实现,当集合当中的元素较多的时候,必然会加大hash 冲突的机会,在链表过长的时候,那么它的查询效率也会必然下降。
所以在 Dict 当中的每次新增键值对时都会检查负载因子(LoadFactor = used / size),并且在满足以下两种情况下。就会触发hash 扩容的机制。
源码分析一下:
static int _dictExpandIfNeeded(dict *d){
// 如果正在rehash,则返回ok
if (dictIsRehashing(d)) return DICT_OK; // 如果哈希表为空,则初始化哈希表为默认大小:4
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 当负载因子(used/size)达到1以上,并且当前没有进行bgrewrite等子进程操作
// 或者负载因子超过5,则进行 dictExpand ,也就是扩容
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio){
// 扩容大小为used + 1,底层会对扩容大小做判断,实际上找的是第一个大于等于 used+1 的 2^n
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}
当然在除过扩容以外,在缩容的时候也会对负责因子做一个判断,当 LoadFactor < 0.1 的时候,就会发生哈希缩容。
源码分析一下:
// t_hash.c # hashTypeDeleted()
...
if (dictDelete((dict*)o->ptr, field) == C_OK) {
deleted = 1;
// 删除成功后,检查是否需要重置Dict大小,如果需要则调用dictResize重置 /* Always check if the dictionary needs a resize after a delete. */
if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
...
// server.c 文件
int htNeedsResize(dict *dict) {
long long size, used;
// 哈希表大小
size = dictSlots(dict);
// entry数量
used = dictSize(dict);
// size > 4(哈希表初识大小)并且 负载因子低于0.1
return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL));
}
int dictResize(dict *d){
unsigned long minimal;
// 如果正在做bgsave或bgrewriteof或rehash,则返回错误
if (!dict_can_resize || dictIsRehashing(d))
return DICT_ERR;
// 获取used,也就是entry个数
minimal = d->ht[0].used;
// 如果used小于4,则重置为4
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
// 重置大小为minimal,其实是第一个大于等于minimal的2^n
return dictExpand(d, minimal);
在上面也提到了在Redis 当中发生了 BGSAVE 或者 BGREWRITEAOF 的时候,就会暂时阻止发生 rehash
rehash 到底是什么?
在不管扩容还是缩容,都必定会创建新的哈希表,从而导致哈希表的 size 和 sizemask 变化,而 key 的查询是与 sizemask 有关。所以就必须对哈希表中的每一个 key 重新计算索引,插入新的哈希表,这个过程称为 rehash。
而 rehash的大致过程如下:
如果是扩容,则新 size 为第一个大于等于dict.ht[0].used + 1的2^n。
如果是收缩,则新 size 为第一个大于等于dict.ht[0].used的2^n (最小不得小于4)
在这个过程中,开始rehash时 dict中的 rehashidx 的默认值(-1)会变为0,再最后rehash 完毕之后,会将 rehashidx 的值再次改为-1。
但是在这我们还要考虑一个问题, Redis 是单线程的,在 rehash 的时候如果因为数据量过于庞大,那么就会导致线程进入阻塞状态,对我们的体验是极不佳的。
所以 Dict 中的 rehash 绝不是一次就完成的。因此发展到现在rehash是分多次的,以渐进式来完成的。因此也将它称为渐进式 rehash。
而它的具体流程如下:
如果是扩容,则新 size 为第一个大于等于dict.ht[0].used + 1的2^n。
如果是收缩,则新 size 为第一个大于等于dict.ht[0].used的2^n (最小不得小于4)
在这也为我们解答了为什么Dict 当中的rehashidx 默认表示的是-1 ,而不是我们经常认为的 0 ,在 rehash 的过程当中,我们是会将rehashidx座位数组角标来使用的
Dict的结构:
它是类似 java 的 HashTable,底层是数组加链表来解决哈希冲突
Dict 中是包含两个哈希表,ht[0] 平常用,ht[1] 用来 rehash时使用的
Dict的伸缩:
当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时,Dict扩容
扩容大小为第一个大于等于used + 1的2^n
当LoadFactor小于0.1时,Dict收缩
收缩大小为第一个大于等于used 的2^n
Dict采用渐进式 rehash,每次访问 Dict 时就执行一次 rehash;保证了 rehash时ht[0]只减不增,新增操作只在ht[1]执行,其它操作在两个哈希
ZipList 是一种特殊的 “双端链表” ,它是由一系列特殊编码的连续内存块组成。可以在任意一端进行压入 / 弹出操作, 并且该操作的时间复杂度为 O(1)。
而 ZipList 的基本机构为:
属性 | 类型 | 长度 | 用途 |
---|---|---|---|
zlbytes | uint32_t | 4字节 | 记录整个压缩列表占用的内存字数 |
zltail | uint32_t | 4字节 | 记录的是压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,可以确定表尾节点的地址。 |
zllen | uint16_t | 2字节 | 记录了压缩列表包含的节点数量。 最大值为UINT16_MAX (65534),如果超过这个值,此处会记录为65535,但节点的真实数量需要遍历整个压缩列表才能计算得出。 |
entry | 列表节点 | 不定 | 压缩列表包含的各个节点,节点的长度由节点保存的内容决定。 |
zlend | uint8_t | 1字节 | 特殊值 0xFF (十进制 255 ),用于标记压缩列表的末端。 |
ZipList 中的 Entry 并不是普通链表那样记录前后节点的指针,因为记录两个指针要占用 16 个字节,浪费内存。
所以在 ZipList 当中采用了另外一套结构。
如果前一节点的长度小于254字节,则采用1个字节来保存这个长度值
如果前一节点的长度大于254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据
注意:
ZipList中所有存储长度的数值均采用小端字节序,即低位字节在前,高位字节在后。例如:数值0x1234,采用小端字节序后实际存储值为:0x3412
在 ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小,长度是1个或5个字节:
如果前一节点的长度小于254字节,则采用1个字节来保存这个长度值
如果前一节点的长度大于等于254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据
现在,假设我们有N个连续的、长度为 250~253 字节之间的entry,因此entry 的 previous_entry_length 属性用1个字节即可表示。
现在我们在头位置添加新的entry 数据大小为254bytes。那么根据后面的entry 里的 pre_entry_len 判断,大小改为5bytes,那么后面的entry 总和就大于等于254了,再往后的entry就也需要更改pre_entry_len 的大小,这样依次向下。
ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新(Cascade Update)。在新增、删除都可能导致连锁更新的发生。
ZipList特性:
QuickList用于存储大量数据的。
在上面的ZipList还存在着一些问题:
问题1:ZipList虽然节省内存,但申请内存必须是连续空间,如果内存占用较多,申请内存效率很低。怎么办?
为了缓解这个问题,我们必须限制 ZipList 的长度和 entry 大小。
问题2:但是我们要存储大量数据,超出了ZipList最佳的上限该怎么办?
我们可以创建多个 ZipList 来分片存储数据。
问题3:数据拆分后比较分散,不方便管理和查找,这多个ZipList如何建立联系?
Redis在3.2版本引入了新的数据结构 QuickList,它是一个双端链表,只不过链表中的每个节点都是一个 ZipList。
在为了避免 QuickList 中的每个 ZipList 中 entry 过多,Redis 提供了一个配置项:list-max-ziplist-size 来限制。
在 Redis 中除了控制 ZipLis t的大小,QuickList 还可以对节点的ZipList做压缩。通过配置项 list-compress-depth 来控制。因为链表一般都是从首尾访问较多,所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数:
源代码:
typedef struct quicklist {
// 头节点指针
quicklistNode *head;
// 尾节点指针
quicklistNode *tail;
// 所有ziplist的entry的数量
unsigned long count;
// ziplists总数量
unsigned long len;
// ziplist的entry上限,默认值 -2
int fill : QL_FILL_BITS; // 首尾不压缩的节点数量
unsigned int compress : QL_COMP_BITS;
// 内存重分配时的书签数量及数组,一般用不到
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
typedef struct quicklistNode {
// 前一个节点指针
struct quicklistNode *prev;
// 下一个节点指针
struct quicklistNode *next;
// 当前节点的ZipList指针
unsigned char *zl;
// 当前节点的ZipList的字节大小
unsigned int sz;
// 当前节点的ZipList的entry个数
unsigned int count : 16;
// 编码方式:1,ZipList; 2,lzf压缩模式
unsigned int encoding : 2;
// 数据容器类型(预留):1,其它;2,ZipList
unsigned int container : 2;
// 是否被解压缩。1:则说明被解压了,将来要重新压缩
unsigned int recompress : 1;
unsigned int attempted_compress : 1; //测试用
unsigned int extra : 10; /*预留字段*/
} quicklistNode;
图解:
QuickList的特点:
SkipList(跳表)本质还是为链表。且为双向链表
它也有一些自身的特点:
简单概念图:
看一下它的源码:
// t_zset.c
typedef struct zskiplist {
// 头尾节点指针
struct zskiplistNode *header, *tail;
// 节点数量
unsigned long length;
// 最大的索引层级,默认是1
int level;
} zskiplist;
// t_zset.c
typedef struct zskiplistNode {
sds ele; // 节点存储的值
double score;// 节点分数,排序、查找用
struct zskiplistNode *backward; // 前一个节点指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 下一个节点指针
unsigned long span; // 索引跨度
} level[]; // 多级索引数组
} zskiplistNode;
SkipList的特点:
RedisObject是Redis中的任意数据类型的键和值都会被封装为一个RedisObject,也叫做Redis对象,
源码如下:
这里只是RedisObject 的头部信息。
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;
unsigned type:4; 表示对象类型,分别是 String、hash、list、set和zset,占4个bit位。
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
unsigned encoding:4; 表示底层编码方式,共有 11 种,占 4 个bit 位
unsigned lru:LRU_BITS; 表示该对象最后一次被访问的时间,其占有24个 bit位,便于判断空闲时间太久的 key。
int refcount; 表示对象引用计数器,计数器为 0,则说明对象无人引用,是可以被回收的。
void *ptr;: 表示指针,指向存放实际数据的空间。
在 Redis 中会根据存储的数据类型不同,选择不同的编码方式,共包含11种不同类型:
编号 | 编码方式 | 说明 |
---|---|---|
0 | OBJ_ENCODING_RAW | raw编码动态字符串 |
1 | OBJ_ENCODING_INT | long类型的整数的字符串 |
2 | OBJ_ENCODING_HT | hash表(字典dict) |
3 | OBJ_ENCODING_ZIPMAP | 已废弃 |
4 | OBJ_ENCODING_LINKEDLIST | 双端链表 |
5 | OBJ_ENCODING_ZIPLIST | 压缩列表 |
6 | OBJ_ENCODING_INTSET | 整数集合 |
7 | OBJ_ENCODING_SKIPLIST | 跳表 |
8 | OBJ_ENCODING_EMBSTR | embstr的动态字符串 |
9 | OBJ_ENCODING_QUICKLIST | 快速列表 |
10 | OBJ_ENCODING_STREAM | stream流 |
在 Redis 中也会根据存储的数据类型不同,选择不同的编码方式。每种数据类型的使用的编码方式如下:
数据类型 | 编码方式 |
---|---|
OBJ_STRING | int、embstr、raw |
OBJ_LIST | LinkedList和ZipList(3.2以前)、QuickList(3.2以后) |
OBJ_SET | intset、HT |
OBJ_ZSET | ZipList、HT、SkipList |
OBJ_HASH | ZipList、HT |