1.redis是使用ansi C(标准)写的和c区别不是很大2.动态字符串 redis没有使用c的字符串设计,而自己构建了一种名为简单动态字符串的抽象类型(SDS),在redis中,c字符串只会作为字符串字面量用于一些无须对字符串进行写改的地方如日志提示等. set msg "the value" 其中键是一个字符串对象,而对象的底层实现是一个保存着"msg"的SDS.键值对的值也是一个对象,底层也是保存"hello world"的SDS.
2.1 SDS的定义
每个sds.h/sdshdr结构表示一个SDS的值
struct sdshdr{
//记录buf数组中已经使用字节的数量
int len; //等于SDS所保存字符串的长度
int free;//记录buf数组中未使用的字节数量
char buf[];//字节数组,保存字符串
}
SDS遵循C字符串的'\0'结尾方式,且不算作一个长度.
含有len和free这一项使其比c的字符串多了以下特性:
A使查看长度变成O(1),设置和更新速度提升,
B杜绝缓存区溢出(当进行相加操作时,c会设置一个缓冲空间,然后将两个放入,当不知道两个字符串大小时,较大可能会溢出)
C减少修改字符串带来的内存重分配次数,替换操作(有时重新分配大小)但这里可以设置free和len的值,替换值
为了减少内存重分配free就可以起到作用:
a.空间预分配:用于优化SDS的字符串增长操作,当SDS的api对一个SDS进行修改,并且需要对SDS进行空间扩展,会分配必要空间和预留一定的未使用空间(free值).
每次拓展SDS之前,SDS会检查未使用空间是否够用,不够就重新加进行下面计算.
通过这种预分配,SDS将连续增长N次字符串所需的内存分配次数从必定N次降低到最多N次.
额外分配的空间大小计算: 当对SDS进行修改后,如果len的值小于1MB,那程序将分配和len大小相同的未使用空间(len=free,不包含'\0')—- , 当对SDS进行修改后,如果SDS的长度将大于1MB,那程序会分配1MB的未使用空间,
b.惰性空间释放:用于优化SDS的字符串缩短操作: 当SDS的api需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出的字节,而是使用free进行记录,等待(以后可能增长操作的)使用.
2.2 二进制安全
C的字符串中的字符必须符合某种编码,除了字符串的末尾之外,字符串中不能包含空字符,否则会认为是字符串结尾,这使c字符串只能保存文本,不能保存图像,等二进制数据.
但SDS 会以处理二进制的方式来处理SDS存放在buf数组的数据,程序不会对其中的数据做任何限制和过滤等.SDS的api都是二进制安全的.
但是兼容了c的字符串所以.部分的c的操作在<string.h>的是可以使用的
3. 链表
C中并没有链表,redis自己搞了一个♪(´ε｀)(^.^).
列表键的实现就是使用链表使用adlist.h/listNode
结构表示typedef struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}listNode; // 双向链表的形式使用adlist.h/list持有链表
typedef struct list{
listNode *head;//头节点
listNode *tail;//尾节点
unsigned long len;//表中所包含的节点数
void *(*dup) (void *ptr);//节点值复制函数
void (*free)(void *ptr);//节点值释放函数
int (*match)(void *ptr,void *key);//节点值对比函数
}list;
redis链表的特性总结: 1.双链表删除增加方便,2.无环路节点,3.带头尾指针,和长度多态:
void *指针来保存节点值,通过三个函数来设置,可以保存不同的类型值.
4.字典
在字典中一个键和一个值进行关联(映射)称为键值对,每个键都是独一无二的,redis构建了自己的字典实现.
当键值中的元素比较长的字符串时,redis会使用字典作为哈希键的底层实现.
哈希表的定义 dict.h/dictht
typedef struct dictht{
dictEntry **table;//哈希表数组;
unsigned long size;//哈希表大小
unsigned long sizemask ;//哈希表大小掩码,用于计算哈希索引值 等于size-1;
unsigned long used; //哈希表已有节点的数量.
}dictht;
其中table属性是一个数组,数组中的每个元素都是指向dict.h/dictEntry结构的指针,
每个dictEntry结构保存着一个键值对,dictEntry结构如下
typedef struct dictEntry{
void *key;//键
union{ //值
void *val;
uint64_tu64;
int64_ts64;
}v;
struct dictEntry *next;//指向下一个哈希表节点,形成链表
}dictEntry;
字典的结合struct dict{
dictType *type;//类型特定函数
void *privdata; //私有数据
dictht ht[2] ;//哈希表
//rehash索引 当rehash不在进行时,值为-1;
in trehashidx;
}dict;
ht属性包含两个dictht哈希表,字典只使用ht[0],ht[1]只会在对ht[0]进行rehash时使用.
type属性和privdata属性是针对不同类型的键值对,为创建多态字典而设置的;
type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数,
struct dictType{
unsigned int(*hashFunction)(const void *key);//计算哈希值
void *(*keyDup)(void *privdata, const void *key);//复制键
void *(*valDup)(void *privdata,const void *obj);//复制值
int (*keyCompare)(void *privdata,const void *key1,const void *key2);//对比键
void (*keyDestructor)(void *privdata,void *key);//销毁键
void (*valDestructor)(void *privdata,void *obj);//销毁值
}
4.2哈希算法
hash=dict->type->hashFunction(key);//计算键key的哈希值
index=hash & dict->ht[x].sizemask;//基本上x=0,使用第一个表,
使用表的sizemask 和哈希值计算出索引值,把哈希值缩小到哈希表的大小范围内,redis使用MurmurHash2算法来计算哈希键的哈希值;
4.3 解决键冲突
当有两个或两个以上数量的键被分配到了哈希表数组的同一个索引上面时,我们称这些键发生了冲突,redis采用链地址法进行解决,记得上面的dictEntry结构体中有一个next属性指向下一个dictEntry;
4.4 rehash
当操作不断进行,哈希表不断操作,哈希表的大小也会进行相应的扩展和收缩,
rehash步骤如下;
1)为字典ht[1]哈希表分配空间,这个表的空间大小取决于要执行的操作,以及ht[0]当前包含的键值对数量(ht[0].used的值) .如果执行拓展操作,ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方的值.如果执行的是收缩操作,那边ht[1]大小为第一个大于等于ht[0].used的2的n次方.
2)将保存在ht[0]中的所有键值对都迁移到ht[1]哈希表的指定位置上.
3)当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变成空表,释放ht[0],ht[1]设置为ht[0],并在ht[1]设置创建一个空表,为下一次rehash做准备.扩展和收缩开始的条件: 负载因子=哈希表已经保存的节点数量/哈希表的大小
1)服务器目前没有在执行BGSAVE命令或者BGREWAITEAOF命令,并且哈希表的负载因子大于等于1,
2)服务器目前正在执行BGSAVE命令或者BGREWAITEAOF命令,并且哈希表的负载因子大于等于5;
3)当负载因子小于0.1时,程序自动开始对哈希表执行收缩操作;
4.5 渐进式rehash
上一节说过,扩展或者收缩哈希表要将ht[0]里面的所有键值对rehash到ht[1]中,
但这个rehash动作并不是一次性,集中式的完成的,而是分为多次,渐进式的完成,如果太多1亿次肯定不能一次性完成,
因此为了避免rehash对服务器性能造成影响,服务器不是一次性将ht[0]里面所有的键值对全部rehash到ht[1]中,而是分多次,渐进式的.
渐进式步骤:
1)为ht[1]分配空间,
2)在字典中维持一个索引计数器变量rehashidx,并将其值设为0,表示rehash开始工作
3)在rehash进行期间,每次对字典执行添加,查找,或者更新操作时,程序除了执行操作还会顺带将rehashidx索引上的所有键值对rehash到ht[1]中,rehash完成后rehashidx的值增加ᕙ[･･]ᕗ.
4)随着字典不断的执行,最终在某个时间节点上ht[0]所有会被rehash完这时候rehashidx设为-1
发表回复