Redis中所有的key都是使用了字符串对象,还有部分字符串类型的value
struct sdshdr{
//记录buf数组中已使用字节的数量
//等于SDS所保存字符串的长度
int len;
//记录buf数据中未使用字节的数量
int free;
//字节数据,用于保存字符串
char buf[];
}
SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在SDS的len属性里面,并且为空字符分配额外的1字节空间,以及添加空字符到字符串末尾等操作,都是由SDS函数自动完成的,所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是,SDS可以直接重用一部分C字符串函数库里面的函数,比方说可以直接使用<stdio.h>/printf函数
1)获取字符串长度的时间复杂度是O(1)
2 ) 杜绝缓冲区溢出
例如:SDS提供了sdscat函数,在执行拼接操作之前,会检查sds的空间是否足够,如果不够会先扩展
3)减少修改字符串时带来的内存重分配次数
内存重分配涉及复杂的算法,并且可能需要执行系统调用,所以比较耗时。Redis的Sds解决方案是空间预分配和惰性空间释放
a)空间预分配:sds在分配时不仅会分配所必须要的空间,还会为sds分配额外的未使用的空间,其中未使用的空间的数量由以下公式决定:
if len(扩展后) < 1MB
free = len ;//比如说len将变成13字节,那么len实际长度 是 13 + 13 + 1 byte
if len (扩展后 ) ≥ 1MB
free = 1MB //比方说len将变成30Mb,那么len实际长度是 30MB+1M+1 byte
b)惰性空间释放:在对sds进行一些操作后使得sds实际使用长度减小后,它并不会立即释放出多的空间,二是讲这些空间作为未使用空间保留在sds里面。当然,sds提供了主动回收这些空间的api
4)二进制安全
C字符串中的字符必须符合某周编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符串,否则最先被读入的空字符串会被误认为是字符串结尾,这些使得C字符串只能保存文本,而不能保存图片、音频、视频等二进制数据。但是SDS是使用len属性的值而不是空字符串来判读字符串是否结束。
5)兼容部分C字符串函数
虽然SDS的API都是二进制安全的,但它们一样遵循C字符串以空字符结尾的惯例:这些API总会将SDS保存的数据的末尾设置为空字符,并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符,这是为了让那些保存文本数据的SDS可以重用一部分<string.h>库定义的函数
比如:SDS可以重用<string.h>/strcasecmp函数,使用它来对比SDS保存的字符串和另一个C字符串
strcasecmp(sds->buf,"hello world");//比对两个字符串
strcat(c_string,sds->buf);//拼接字符串
6)小结
/**
*每个链表节点使用一个adlist.h/listNode结构来表示
**/
typedef struct listNode{
//前置节点
struct listNode * prev;
//后置节点
struct listNode * next;
//节点的值
void * value;
} listNode;
/**
*虽然仅仅使用多个listNode结构就可以组成链表,但使用adlist.h/list来持有链表的话,操作起来会更方便
**/
typedef struct list{
//表头节点
listNode * head;
//表尾节点
listNode * tail;
//链表所包含的节点数量
unsigned long len;
//节点值复制函数
void * (*dup) (void *ptr)
//节点值释放函数
void * (*free) (void *ptr)
//节点值对比函数
void * (*match) (void *ptr,void *key)
} list;
/**
*Redis字典所使用的哈希表由dict.h/dictht结构定义
**/
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值
//总是等于size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}
//其中的哈希表节点
typedef struct dictEntry{
//键
void *key;
//值
union{//可以是一个指针,或者是一个uint64_t整数,又或者是一个int64_t整数。
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
/**
*Redis中的字典由dict.h/dict结构表示:
*/
typedef struct dict{
//类型特定函数
dictType * type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash索引
//当rehash不在进行时,值为-1
int trehashidx;
} dict;
/**
*
*/
typedef struct dictType {
uint64_t (*hashFunction)(const void *key); //字典key哈希函数
void *(*keyDup)(void *privdata, const void *key); //字典key复制函数
void *(*valDup)(void *privdata, const void *obj); //字典值复制函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2); //字典key比较函数
void (*keyDestructor)(void *privdata, void *key); //字典key析构函数
void (*valDestructor)(void *privdata, void *obj); //字典值析构函数
} dictType;
Redis使用MurmurHash2算法来计算键的哈希值。MurmurHash算法最初由Austin Appleby于2008年发明,这种算法的优点在于,即使输入的键是有规律的,算法仍能给出一个很好的随机分布性,并且算法的计算速度也非常快。MurmurHash算法目前的最新版本为MurmurHash3,而Redis使用的是MurmurHash2,关于MurmurHash算法的更多信息可以参考该算法的主页:http://code.google.com/p/smhasher/
Redis计算哈希值和索引值的方法如下:
//使用字段设置的哈希函数,计算键key的哈希值
hash = dict ->type->hashFcuntion(key);
//使用哈希表的sizemask属性和哈希值,计算出索引值
//根据情况不同,ht[x]可以是ht[0]也可以是ht[1]
index = hash & dict->ht[x].sizemask;
解决键冲突 - 链地址法(separate chaining)
(1)概念介绍
rehash是以bucket(桶)为基本单位进行渐进式的数据迁移的,每步完成一个bucket的迁移,直至所有数据迁移完毕。一个bucket对应哈希表数组中的一条entry链表。新版本的dictRehash()还加入了一个最大访问空桶数(empty_visits)的限制来进一步减小可能引起阻塞的时间。
activerehashing yes
,默认为开启,此配置项针对数据库的dict与expires,如果开启了rehash配置,redis服务器会有一个定时器,每毫秒执行一次渐进式rehash,代码实现如下:/* This function handles 'background' operations we are required to do
* incrementally in Redis databases, such as active key expiring, resizing,
* rehashing. */
void databasesCron(void) {
/* Expire keys by random sampling. Not required for slaves
* as master will synthesize DELs for us. */
if (server.active_expire_enabled && server.masterhost == NULL) {
activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
} else if (server.masterhost != NULL) {
expireSlaveKeys();
}
/* Defrag keys gradually. */
if (server.active_defrag_enabled)
activeDefragCycle();
/* Perform hash tables rehashing if needed, but only if there are no
* other processes saving the DB on disk. Otherwise rehashing is bad
* as will cause a lot of copy-on-write of memory pages. */
if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {
/* We use global counters so if we stop the computation at a given
* DB we'll be able to start from the successive in the next
* cron loop iteration. */
static unsigned int resize_db = 0;
static unsigned int rehash_db = 0;
int dbs_per_call = CRON_DBS_PER_CALL;
int j;
/* Don't test more DBs than we have. */
if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
/* Resize */
for (j = 0; j < dbs_per_call; j++) {
tryResizeHashTables(resize_db % server.dbnum);
resize_db++;
}
/* Rehash */
if (server.activerehashing) {
for (j = 0; j < dbs_per_call; j++) {
int work_done = incrementallyRehash(rehash_db);
if (work_done) {
/* If the function did some work, stop here, we'll do
* more at the next cron loop. */
break;
} else {
/* If this db didn't need rehash, we'll try the next one. */
rehash_db++;
rehash_db %= server.dbnum;
}
}
}
}
}
int incrementallyRehash(int dbid) {
/* Keys dictionary */
if (dictIsRehashing(server.db[dbid].dict)) {
dictRehashMilliseconds(server.db[dbid].dict,1);
return 1; /* already used our millisecond for this loop... */
}
/* Expires */
if (dictIsRehashing(server.db[dbid].expires)) {
dictRehashMilliseconds(server.db[dbid].expires,1);
return 1; /* already used our millisecond for this loop... */
}
return 0;
}
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;
}
return rehashes;
}
函数调用为 serverCron -> databasesCron -> incrementallyRehash -> dictRehashMilliseconds,具体执行操作时间为1ms,在1ms的时间时间内每次rehash 100个数据桶。直到每个字典rehash完成。
(2) rehash函数的具体实现:
(3)渐进式哈希的精髓在于:
typedef struct zskiplistNode{
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
rsobj *obj;
}zskiplistNode;
typedef struct zskiplist{
//表头节点和表尾节点
struct zskiplistNode *header *tail;
//表中节点的数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;
zskiplist :
❑header:指向跳跃表的表头节点。❑tail:指向跳跃表的表尾节点。❑level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)。❑length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)。
zskiplistNode:
❑层(level):节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,以此类推。每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。
❑后退(backward)指针:节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。❑分值(score):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。❑成员对象(obj):各个节点中的o1、o2和o3是节点所保存的成员对象
❑分值(score):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。
❑成员对象(obj):各个节点中的o1、o2和o3是节点所保存的成员对象。
https://www.notion.so/Redis-6fdfb56611be4cc0b1083fd40a675417
typedef struct intset{
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
contents数组是整数集合的底层实现:整数集合的每个元素都是contents数组的一个数组项(item),各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项。length属性记录了整数集合包含的元素数量,也即是contents数组的长度。虽然intset结构将contents属性声明为int8_t类型的数组,但实际上contents数组并不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值: