赞
踩
typedef struct redisObject{
// 类型
unsigned type:4;
// 编码方式
unsigned encoding:4;
// LRU - 24位, 记录最末一次访问时间(相对于lru_clock); 或者 LFU(最少使用的数据:8位频率,16位访问时间)
unsigned lru:LRU_BITS; // LRU_BITS: 24
// 引用计数
int refcount;
// 指向底层数据结构实例
void *ptr;
} robj;
为什么Redis会设计redisObject对象?
在redis的命令中,用于对键进行处理的命令占了很大一部分,而对于键所保存的值的类型(键的类型),键能执行的命令又各不相同。如: LPUSH
和 LLEN
只能用于列表键, 而 SADD
和 SRANDMEMBER
只能用于集合键, 等等; 另外一些命令, 比如 DEL
、 TTL
和 TYPE
, 可以用于任何类型的键;但是要正确实现这些命令, 必须为不同类型的键设置不同的处理方式: 比如说, 删除一个列表键和删除一个字符串键的操作过程就不太一样。
以上的描述说明, Redis 必须让每个键都带有类型信息, 使得程序可以检查键的类型, 并为它选择合适的处理方式
为了解决以上问题, Redis 构建了自己的类型系统, 这个系统的主要功能包括:
redisObject 对象.
基于 redisObject 对象的类型检查.
基于 redisObject 对象的显式多态函数.
对 redisObject 进行分配、共享和销毁的机制
type记录了对象所保存的值的类型,它的值可能是以下常量中的一个:
/*
* 对象类型
*/
#define OBJ_STRING 0 // 字符串
#define OBJ_LIST 1 // 列表
#define OBJ_SET 2 // 集合
#define OBJ_ZSET 3 // 有序集
#define OBJ_HASH 4 // 哈希表
/*
* 对象编码
*/
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* 注意:版本2.6后不再使用. */
#define OBJ_ENCODING_LINKEDLIST 4 /* 注意:不再使用了,旧版本2.x中String的底层之一. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
redis执行命令的过程
redis一般会把一些常见的值放到一个共享对象中,这样可使程序避免了重复分配的麻烦,也节约了一些CPU时间。
redis预分配的值对象如下:
redisObject中有refcount属性,是对象的引用计数,显然计数0那么就是可以回收。
redis中保存的key是字符串,value往往是字符串或者字符串的集合,可见字符串是redis中最常用的一种数据结构
C语言字符串问题:c语言字符串本质是一个字符数组
为此redis构建了一种新的字符串结构,称为简单动态字符串简称:SDS
alloc - len
计算出剩余的空间大小,可以用来判断空间是否满足修改需求,如果不满足的话,就会自动将 SDS 的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用 SDS 既不需要手动修改 SDS 的空间大小,也不会出现前面所说的缓冲区溢出的问题。Redis 一共设计了 5 种类型,分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
这 5 种类型的主要区别就在于,它们数据结构中的 len 和 alloc 成员变量的数据类型不同。
比如 sdshdr8它的定义分别如下:
//__attribute__ ((packed)) ,它的作用是:告诉编译器取消结构体在编译过程中的优化对齐,按照实际占用字节数进行对齐。
struct __attribute__ ((__packed__)) sdshdr8{
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
SDS扩容原理:
这样的好处是,下次在操作 SDS 时,如果 SDS 空间够的话,API 就会直接使用「未使用空间」,而无须执行内存分配,有效的减少内存分配次数。
常见的双向链表的实现方式
typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
} l
redis在listNode结构体基础上又封装了list
typedef struct list {
//链表头节点
listNode *head;
//链表尾节点
listNode *tail;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void (*free)(void *ptr);
//节点值比较函数
int (*match)(void *ptr, void *key);
//链表节点数量
unsigned long len;
} list
优点:
缺点:
因此,Redis 3.0 的 List 对象在数据量比较少的情况下,会采用「压缩列表」作为底层数据结构的实现,它的优势是节省内存空间,并且是内存紧凑型的数据结构。
不过,压缩列表存在性能问题(具体什么问题,下面会说),所以 Redis 在 3.2 版本设计了新的数据结构 quicklist,并将 List 对象的底层数据结构改由 quicklist 实现。
然后在 Redis 5.0 设计了新的数据结构 listpack,沿用了压缩列表紧凑型的内存布局,最终在最新的 Redis 版本,将 Hash 对象和 Zset 对象的底层数据结构实现之一的压缩列表,替换成由 listpack 实现。
压缩列表是 Redis 为了节约内存而开发的,它是由连续内存块组成的顺序型数据结构,有点类似于数组。
zlbytes
字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数
zltail
字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作
zllen
字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占2bytes(16位): 如果ziplist中entry的数目小于65535(2的16次方), 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到.
zlend
是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255
前三这个都采用小端的存储方式
常见的entry的结构为** **
prevlen
:前一个entry的大小 为了实现从后往前遍历; 当前一个元素长度小于254(255用于zlend)的时候,prevlen长度为1个字节,值即为前一个entry的长度,如果长 度大于等于254的时候,prevlen用5个字节表示,第一字节设置为254,后面4个字节存储一个小端的无符号整 型,表示前一个entry的长度;
encoding
:不同的情况下值不同,用于表示当前entry的类型和长度;
如果当前节点的数据是整数,则 encoding 会使用 1 字节的空间进行编码,也就是 encoding 长度为 1 字节。通过 encoding 确认了整数类型,就可以确认整数数据的实际大小了,比如如果 encoding 编码确认了数据是 int16 整数,那么 data 的长度就是 int16 的大小。
如果当前节点的数据是字符串,根据字符串的长度大小,encoding 会使用 1 字节/2字节/5字节的空间进行编码,encoding 编码的前两个 bit 表示数据的类型,后续的其他 bit 标识字符串数据的实际长度,即 data 的长度
entry-data
:真是用于存储entry表示的数据;
在entry中存储的是int类型时,encoding和entry-data会合并在encoding中表示,此时没有entry-data字段;
typedef struct zlentry{
unsigned int prevrawlensize; //表示 previous_entry_length字段的长度
unsigned int prevrawlen; //表示 previous_entry_length字段存储的内容
unsigned int lensize; //表示 encoding字段的长度
unsigned int len; //表示数据内容长度
unsigned int headersize;//表示当前元素的首部长度,即previous_entry_length字段长度与encoding字段长度之和
unsigned char encoding; //表示数据类型
unsigned char *p; //p表示当前元素首地址
}zlentry;
ziplist也不预留内存空间, 并且在移除结点后, 也是立即缩容, 这代表每次写操作都会进行内存分配操作.
结点如果扩容, 导致结点占用的内存增长, 并且超过254字节的话, 可能会导致链式反应: 其后一个结点的entry.prevlen需要从一字节扩容至五字节. 最坏情况下, 第一个结点的扩容, 会导致整个ziplist表中的后续所有结点的entry.prevlen字段扩容. 虽然这个内存重分配的操作依然只会发生一次, 但代码中的时间复杂度是o(N)级别, 因为链式扩容只能一步一步的计算.
因此,压缩列表只会用于保存的节点数量不多的场景,只要节点数量足够小,即使发生连锁更新,也是能接受的。
哈希表结构
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值
unsigned long sizemask;
//该哈希表已有的节点数量
unsigned long used;
} dictht
哈希节点结构
typedef struct dictEntry {
//键值对中的键
void *key;
//键值对中的值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//指向下一个哈希表节点,形成链表
struct dictEntry *next;
} dict
dictEntry 结构里键值对中的值是一个「联合体 v」定义的,因此,键值对中的值可以是一个指向实际值的指针,或者是一个无符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间,因为当「值」是整数或浮点数时,就可以将值的数据内嵌在 dictEntry 结构里,无需再用一个指针指向实际的值,从而节省了内存空间。
Redis采用链式哈希存储哈希冲突
b452135f44fab77e3c578d91666e.png#pic_center)
链式哈希局限性也很明显,随着链表长度的增加,在查询这一位置上的数据的耗时就会增加,毕竟链表的查询的时间复杂度是 O(n)。
要想解决这一问题,就需要进行 rehash,也就是对哈希表的大小进行扩展。
1、如果执行扩展操作,会基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表(也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表)。相反如果执行的是收缩操作,每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。
redis定义一个dict结构体,其中两个哈希表
typedef struct dict {
…
//两个Hash表,交替使用,用于rehash操作
dictht ht[2];
…
} dict;
2、重新利用上面的哈希算法,计算索引值,然后将键值对放到新的哈希表位置上。
3、所有键值对都迁徙完毕后,释放原哈希表的内存空间。
触发扩容的条件:
1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且负载因子大于等于1。
2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且负载因子大于等于5。
负载因子 = 哈希表已保存节点数量 / 哈希表大小
如果「哈希表 1 」的数据量非常大,那么在迁移至「哈希表 2 」的时候,因为会涉及大量的数据拷贝,此时可能会对 Redis 造成阻塞,无法服务其他请求。因此redis采用的是渐进式rehash
渐进式 rehash 步骤如下:
在渐进式hash过程中哈希表1不再进行增加操作,哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。
整数集合本质上是一块连续内存空间,它的结构定义如下:
typedef struct intset {
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
encoding
表示编码方式,的取值有三个:INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
length
代表其中存储的整数的个数
contents
指向实际存储数值的连续内存区域, 就是一个数组;整数集合的每个元素都是 contents 数组的一个数组项(item),各个项在数组中按值得大小从小到大有序排序,且数组中不包含任何重复项。(虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组,但实际上 contents 数组并不保存任何 int8_t 类型的值,contents 数组的真正类型取决于 encoding 属性的值)
当在一个int16类型的整数集合中插入一个int32类型的值,整个集合的所有元素都会转换成32类型。 整个过程有三步:
升级过程
那么如果我们删除掉刚加入的int32类型时,会不会做一个降级操作呢?
不会。主要还是减少开销的权衡。
typedef struct zskiplistNode { //Zset 对象的元素值 sds ele; //元素权重值 double score; //后向指针 struct zskiplistNode *backward; //节点的level数组,保存每层上的前向指针和跨度 struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;
跳表的结构:
跳表的查找过程
如果要查找「元素:abcd,权重:4」的节点,查找的过程是这样的:
跳表的节点层数设置:
跳表的相邻两层的节点数量的比例会影响跳表的查询性能。
那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢?
如果采用新增节点或者删除节点时,来调整跳表节点以维持比例的方法的话,会带来额外的开销。
Redis 则采用一种巧妙的方法是,跳表在创建节点的时候,随机生成每个节点的层数,并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。
具体的做法是,跳表在创建节点时候,会生成范围为[0-1]的一个随机数,如果这个随机数小于 0.25(相当于概率 25%),那么层数就增加 1 层,然后继续生成下一个随机数,直到随机数的结果大于 0.25 结束,最终确定该节点的层数。
这样的做法,相当于每增加一层的概率不超过 25%,层数越高,概率越低,层高最大限制是 64。
虽然我前面讲解跳表的时候,图中的跳表的「头节点」都是 3 层高,但是其实如果层高最大限制是 64,那么在创建跳表「头节点」的时候,就会直接创建 64 层高的头节点。
如下代码,创建跳表时,头节点的 level 数组有 ZSKIPLIST_MAXLEVEL个元素(层),节点不存储任何 member 和 score 值,level 数组元素的 forward 都指向NULL, span值都为0。
/* Create a new skiplist. */ zskiplist *zslCreate(void) { int j; zskiplist *zsl; zsl = zmalloc(sizeof(*zsl)); zsl->level = 1; zsl->length = 0; zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->level[j].forward = NULL; zsl->header->level[j].span = 0; } zsl->header->backward = NULL; zsl->tail = NULL; return zsl; }
其中,ZSKIPLIST_MAXLEVEL 定义的是最高的层数,Redis 7.0 定义为 32,Redis 5.0 定义为 64,Redis 3.0 定义为 32。
typedef struct quicklist { //quicklist的链表头 quicklistNode *head; //quicklist的链表头 //quicklist的链表尾 quicklistNode *tail; //所有压缩列表中的总元素个数 unsigned long count; //quicklistNodes的个数 unsigned long len; ... } quicklist; typedef struct quicklistNode { //前一个quicklistNode struct quicklistNode *prev; //前一个quicklistNode //下一个quicklistNode struct quicklistNode *next; //后一个quicklistNode //quicklistNode指向的压缩列表 unsigned char *zl; //压缩列表的的字节大小 unsigned int sz; //压缩列表的元素个数 unsigned int count : 16; //ziplist中的元素个数 .... } quicklistNode;
quicklist内存布局图:
在向 quicklist 添加一个元素的时候,不会像普通的链表那样,直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素,如果能容纳就直接保存到 quicklistNode 结构里的压缩列表,如果不能容纳,才会新建一个新的 quicklistNode 结构。
quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数,来规避潜在的连锁更新的风险,但是这并没有完全解决连锁更新的问题
listpack如何解决反向遍历的?
首先访问 listpack 的前4字节得到总长度,然后就可以定位到末尾结尾符位置。然后指针左移就可以访问到最后一个元素的长度 len,指针再左移 len 就可以访问最后一个元素的 encoding,根据编码方式访问元素。指针再左移又可以访问到倒数第2个元素的长度,以此类推。
访问元素长度len字段时,有一个关键点,就是如何判断 len 部分结束了。因为 len 可能占用1字节,也可能占用多个字节。listpack 的做法是,每个字节只使用 7 Bit,最高位来表示是否还要继续读。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。