SDS
数据结构
struct sdshdr{
//记录buf数组中已使用的字节数量
//等于SDS所保存字符串的长度
int len;
//记录buf数组中未使用的字节数量
int free;
//字节数组，用于保存字符串
char buf[];
};
SDS 与 C
- C获取字符串长度：O(n),SDS获取字符串长度：O(1)。
- SDS对字符串操作时会先检查空间是否满足需求，去过不满足的话会对SDS进行扩容，C不会检查，所以C会造成缓冲区溢出。
- SDS分配为字符串分配空间时，如果要存储的字符串长度小于1MB，那么会分配空余时间和len属性同样大小的预留空间，如果len的属性大于1MB，那么会分配1MB的预留空间。
a) 会减少内存重分配的次数。
b) 如果字符串长度变短，也不会立即释放多余的空间。 - SDS用len属性记录字符串的长度，C用‘\0’记录字符串的长度，所以SDS可以存储的字符串的范围比C大。
链表
数据结构
链表节点
typedef struct listNode{
//前置节点
listNode *prev;
//后置节点
listNode *next;
//节点的值
void* value;
}listNode;
管理链表的节点
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表包含的节点
unsigned long len;
//节点复制函数
void *(*dup)(void *ptr);
//节点释放函数
void(*free)(void *ptr);
}list;
链表特点
- 双端：双向链表访问前一个节点和后一个节点的时间复杂度为O(1)。
- 无环：表头节点的prev指向NULL，表尾的next指向NULL，对链表的遍历以NULL结束。
- 带表头和表尾指针：访问表头和表尾节点的时间复杂度为O(1)。
- 记录链表的长度变量：获取链表长度的时间复杂度O(1)。
- 多态：采用函数指针实现多态。
链表用途
列表键、发布与订阅、慢查询、监视器。
字典
数据结构
//hash节点
typedef struct dictEntry{
//键
void *key;
//值
union{
void *val;
unsigned __int64 u64;
__int64 s64;
}v;
//指向下一个哈希表节点形成链表
struct dictEntry *next;
}dictEntry;
//哈希表
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表掩码，用于计算索引值
//大小总是等于size-1
unsigned long sizemask;
//hash表已有节点数量
unsigned long used;
}dicht;
//管理hash表的节点
typedef struct dict{
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash索引
//当rehash不进行时，值为-1
int trehashidx;
}dict;
字典
hash算法：
首先根据key计算出hash值，
Index=hash&sizemask
解决键冲突：拉链法，头插的方式。
扩容收缩
- 当服务器没有执行BGSAVE命令或者BGREWRITEAOF命令，并且hash表的负载因子大于等于1。
- 服务器正在执行BGSAVE命令或者BGREWRITEAOF命令，并且hash表的负载因子大于等于5。
- Hash表的负载因子小于0.1时，程序会自动开始对hash表进行收缩操作。
负载因子=hash表已保存的节点数量/hash表大小。
Eg: load_factory=ht[0].used/ht[0].size
提高负载因子的原因：
执行上面的命令时，Redis需要创建当前服务进程的子进程，大多数系统采用写时复制来优化子进程的使用效率，所以子进程存在期间，服务器会提高扩展操作所需的负载因子，从而避免在子进程存在期间进行扩容操作，进而避免不必要的内存写入操作，尽最大限度的节约内存。
扩容和收缩的尺寸：
扩容：扩容后的大小2n 第一个大于等于已有节点的数量2的2n
eg:已有节点数量 6
62=12 <= 24 = 16 扩容后为16
收缩：收缩后的大小2n 第一个大于等于已有节点的数量的2n
eg:已有节点数量 8
6<=23=8 收缩后为8
ht[1]用来扩容使用，扩容完毕后释放ht[0]的指向，并将ht[1]扩容好的hash表重新用ht[0]指向。
渐进rehash
Rehash的动作不是一次完成，而是分多次，渐进式完成的。（如果键值对很多的，一次完成可能会导致服务器停止服务）
- 在字典中维持一个索引计数器rehashidx，值设为0，表示rehash正式开始。
- 在rehash期间，每次对字典进行添加、删除、查找或者更新，程序除了执行指定的操作外，还会将ht[0]哈索希表在rehashidx索引上的所有键值对rehash到ht[1]上。
Rehash执行期间字典会同时使用ht[0]和ht[1]两个hash表，所以如果执行删、改、查时，会先检查ht[0]上是否有对应的键，如果没有会到ht[1]中查找，如果执行增操作，回直接对ht[1]进行添加。
跳跃表
数据结构
//跳跃表
typedef struct zskiplistNode{
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
void *obj;
//层级
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
}zskiplistNode;
- 层：跳跃表的level数组可以包含多个元素。每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快其他节点的访问速度，层的数量越多，访问节点的速度就越快。层的范围（1~32）
- 前进指针：用于指向表尾方向的前进指针。
- 跨度：用于记录连个节点之间的距离，跨度越大距离越远。指向NULL的所有前进指针的跨度为0，因为没有指向任何节点。也可以用跨度来计算该节点在跳表中的位置。
- 后退指针：每次只能访问前一个节点不能跳级访问，
-
分值和成员：
a) 分值是一个double型的浮点数，跳表中的节点都按照从小到大进行排序。
b) 成员对象指向一个字符串对象，字符串对象中保存着SDS的值。
跳跃表
跳表属性
跳表属性
- 跳跃表示有序集合的底层实现之一。
- 跳表表头保存表头节点表尾节点，长度；跳表节点保存分值和成员。
- 一个跳表中可以有多个相同的分值，但是相同的分值对象是不同的，分值相同时，节点按照对象的大小进行排序。
- 跳表时有序集合底层实现的原理之一。
整数集合
可以存储int_16,int_32,int_64的整数值，有序并且不会出现重复值。
数据结构
typedef struct intset{
//编码方式
unsigned __int32 encoding;
//集合包含的元素数量
unsigned __int32 length;
//保存元素的数组
__int8 contents[];
}intset;
升级降级
升级整数集合并添加新元素的类型，扩展为3步：
- 根据新元素的类型拓展整数数组的空间大小，并为新元素分配空间。
- 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位置上，并且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
- 将新元素添加到底层数组里面。
【注意】 - 因为每次向集合添加新元素都有可能引起升级，每次升级都会对底层数组进行内存重分配，所有元素也会进行类型转换，所以向整数集合中添加元新元素的时间复杂度是O(n)。
- 因为引发升级的元素长度总是比现有整数的长度大，也就是说新元素可能都小于现有元素，也可能都大于现有元素，新元素摆放的位置要么在集合的最前面要么在集合的末尾（length-1）
- 整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。
升级好处
- 尽可能的节约了内存。
- 提升了集合的灵活性：可以任意添加各种长度的整数集合，不用担心出现类型错误的情况。
压缩列表
为了节约内存而设计的一种特殊编码的连续内存组成的数据结构。
常用作列表键和hash键的底层实现之一。
数据结构
压缩列表数据结构
- zlbytes ：记录压缩列表占用内存字节数；在对压缩列表进行内存重分配或者记录zlen的位置时使用。
- ztail：记录压缩列表表尾节点距离压缩列表起始地址有所少个字节，通过这个偏移量可以直接计算出表尾节点的地址。
- zllen：记录压缩列表包含节点的数量。（节点的数量小于65536才能计算出来）
- entry：压缩列表包含的各个节点。节点可以保存一个字节数组或者一个整数值。
-
zlend：用于标记压缩列表的末端。
压缩列表节点的构成：
压缩列表节点的构成
-
previous_entry_length：记录前一个节点的长度。程序可以根据前一个节点的长度，当前节点的地址，计算出前一个节点的起始地址，实现元素的逆向遍历。
-
encoding：保存当前节点数据类型及其长度。
-
content：可以保存一个字节数组或者一个整数值。值的长度和类型由encoding决定。
对象
数据结构
typedef struct redisObject{
//类型
unsigned type : 4;
//编码
unsigned encoding : 4;
//指向底层数据结构的指针
void *ptr;
//...
}robj;
Redis数据库保存的键值对来说：
键总是一个字符串对象，而值则可以是字符串对象，列表对象，hash对象，集合对象或者有序集合对象其中的一种。
类型：记录了对象的类型。例如：字符串对象，列表对象，hash对象，集合对象，有序集合对象。
编码：对象的encoding属性记录了对象使用的编码，通过这种方式提升了Redis的灵活性和效率，
例如：列表对象包含元素少时使用压缩列表，压缩列表比双向链表更加节约内存，而且地址是连续的，可以更快的被载入内存。但是如果元素渐渐增多，压缩列表将失去优势，转换为双向链表。
字符串对象
字符串对象的编码可能是int ,raw,embstr。
如果一个字符串对象保存的是整数值可以用long类型表示那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面。
embstr是专门用来保存短字符串的一种优化编码方式。
Raw会调用两次内存分配分别创建对象和底层sds,embstr只会调用一次内存分配一块连续的空间来创建对象和底层sds。
Embstr好处
embstr将内存分配的次数降低为了1次，所以对于对象的创建，内存的回收以及缓存都会有优势。
如果是浮点数，redis会采用字符串的形式进行保存，对浮点数进行运算时，redis会先取出字符串，之后转换为浮点数进行运算，最后将运算后的浮点数转换成字符串保存起来。
编码转换
在整数后面追加一个字符串，会将int转换为raw
对一个embstr字符串进行修改时，embstr会转换为raw,(embstr没有任何的修改程序)
列表对象
列表对象的编码可以是ziplist或者linkedlist。
Hash对象
Hash对象编码可以是ziplist或者hashtable
Ziplist编码实现
每当有新的键值对要加入到hash对象中时，程序会将保存了键的压缩列表节点推入到列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。
特点：
- 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；
- 先添加hash对象中的键值对会被放在压缩列表的表头方向，而后来添加hash对象中的键值对会被放在压缩列表的表尾方向。
如图：
压缩列表实现hashtable
集合对象
集合对象的编码实现可以是intset或者hashtable
使用hashtable作为编码的时候：字典的每个键都是一个字符串对象，字典的值都为NULL。
有序集合
有序集合的编码可以是ziplist或者skiplist和字典。
使用skiplist和字典的原理：
跳跃表的score属性保存了元素的分值，obj属性保存了元素的成员，字典的key属性保存了元素的成员，value属性保存了元素的分值。
他们是通过两个指针指向同一块内存实现的，所以不会出现内存浪费。
为什么要同时使用跳表和字典实现zset？
这属于取两者的长度综合起来使得zset元素的访问效率变高，跳表查找元素的时间复杂度为O(NlogN),而字典的查找元素的效率为O（1），但是跳表是有序的数据结构，所以对于范围查询，时间复杂度为O（1），但是字典的范围查询首先要讲整个字典进行排序，所以最快时间复杂度为O（NlogN）,除此之外还需要O(N)的额外内存空间，所以可以将两种数据结构综合起来使用，达到效率最佳。
内存回收
C语言不具备内存回收功能，redis构建了引用计数实现内存回收。
创建一个对象时，该对象的引用计数值为1，被一个程序使用后引用+1，不在被一个程序使用，引用-1，引用为0，对象所占内存会被释放。
对象共享
Redis会在初始化服务器的时候创建一万个字符串对象对象包含了0-9999的所有整数值，服务器用到这些对象时，直接使用，不再创建。
网友评论