sds结构
sds主要是用来存储字符串
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
空间预分配
/*
* 对 sds 中 buf 的长度进行扩展，确保在函数执行之后，
* buf 至少会有 addlen + 1 长度的空余空间
* （额外的 1 字节是为 \0 准备的）
*
* 返回值
* sds ：扩展成功返回扩展后的 sds
* 扩展失败返回 NULL
*
* 复杂度
* T = O(N)
*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 获取 s 目前的空余空间长度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空间已经足够，无须再进行扩展，直接返回
if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
sh = (void*)(s - (sizeof(struct sdshdr)));
// s 最少需要的长度
newlen = (len + addlen);
// 根据新长度，为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC (1M)
// 那么为它分配两倍于所需长度的空间
newlen *= 2;
else
// 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr) + newlen + 1);
// 内存不足，分配失败，返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余长度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}
删除空间
/*
* 回收 sds 中的空闲空间，
* 回收不会对 sds 中保存的字符串内容做任何修改。
*
* 返回值
* sds ：内存调整后的 sds
*
* 复杂度
* T = O(N)
*/
sds sdsRemoveFreeSpace(sds s) {
struct sdshdr *sh;
sh = (void*)(s - (sizeof(struct sdshdr)));
// 进行内存重分配，让 buf 的长度仅仅足够保存字符串内容
// T = O(N)
sh = zrealloc(sh, sizeof(struct sdshdr) + sh->len + 1);
// 空余空间为 0
sh->free = 0;
return sh->buf;
}
链表
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
链表里面封装了一个迭代器
//
// listIter 双端链表迭代器
//
typedef struct listIter {
// 当前迭代到的节点
listNode *next;
// 迭代的方向
int direction;
} listIter;
字典
//哈希表结点
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表, 哈希冲突解决的一种方法
struct dictEntry *next;
} dictEntry;
//
// dictht 哈希表
//每个字典都使用两个哈希表，从而实现渐进式 rehash
//
typedef struct dictht { // 这是字典的头部
// 哈希表数组, 每个元素都是一条链表
dictEntry **table;
// 哈希表大小
unsigned long size; //初始值为4， 跟STL不太一样
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
//
// dict 字典
//
typedef struct dict {
// 类型特定函数
dictType *type; // type里面主要记录了一系列的函数,可以说是规定了一系列的接口
// 私有数据
void *privdata; // privdata保存了需要传递给那些类型特定函数的可选参数
// 哈希表
dictht ht[2]; // 有两张hash表
// rehash 索引
// 并没有rehash时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; // 目前正在运行的安全迭代器的数量
} dict;
哈希算法
/* Thomas Wang's 32 bit Mix Function */
unsigned int dictIntHashFunction(unsigned int key) {
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
/* MurmurHash2, by Austin Appleby
* Note - This code makes a few assumptions about how your machine behaves -
* 1. We can read a 4-byte value from any address without crashing
* 2. sizeof(int) == 4
*
* And it has a few limitations -
*
* 1. It will not work incrementally.
* 2. It will not produce the same results on little-endian and big-endian
* machines.
*/
unsigned int dictGenHashFunction(const void *key, int len) {
/* 'm' and 'r' are mixing constants generated offline.
They're not really 'magic', they just happen to work well. */
uint32_t seed = dict_hash_function_seed;
const uint32_t m = 0x5bd1e995;
const int r = 24;
/* Initialize the hash to a 'random' value */
uint32_t h = seed ^ len;
/* Mix 4 bytes at a time into the hash */
const unsigned char *data = (const unsigned char *)key;
while (len >= 4) {
uint32_t k = *(uint32_t*)data;
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
data += 4;
len -= 4;
}
/* Handle the last few bytes of the input array */
switch (len) {
case 3: h ^= data[2] << 16;
case 2: h ^= data[1] << 8;
case 1: h ^= data[0]; h *= m;
};
/* Do a few final mixes of the hash to ensure the last few
* bytes are well-incorporated. */
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return (unsigned int)h;
}
/* And a case insensitive hash function (based on djb hash) */
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
unsigned int hash = (unsigned int)dict_hash_function_seed;
while (len--)
hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
return hash;
}
/* A fingerprintis a 64 bit number that represents the state of the dictionary
* at a given time, it's just a few dictproperties xored together.
* When an unsafe iterator is initialized, weget the dict fingerprint, and check
* the fingerprint again when the iterator isreleased.
* If the two fingerprints are different itmeans that the user of the iterator
* performed forbidden operations against thedictionary while iterating. */
long longdictFingerprint(dict *d) {
long long integers[6], hash = 0;
int j;
//将dict结构体中的几个状态放入到数组中，以便后面应用到64 bit MixFunctions中。
//dict结构体其实就是一个hash表的实现，而这些状态其实就是第一、第二哈希表的表地址、表大小与
//已用条目的数量
integers[0] = (long) d->ht[0].table;
integers[1] = d->ht[0].size;
integers[2] = d->ht[0].used;
integers[3] = (long) d->ht[1].table;
integers[4] = d->ht[1].size;
integers[5] = d->ht[1].used;
/* We hash N integers by summing everysuccessive integer with the integer
* hashing of the previous sum. Basically:
*
* Result =hash(hash(hash(int1)+int2)+int3) ...
*
* This way the same set of integers in adifferent order will (likely) hash
* to a different number. */
//利用64 bit Mix Functions，将这些状态信息混合到hash中，组成最后的指纹，如果这些状态中有一个
//出现变化，可以通过一个算法逆推出该状态变化之前的值。例如，d->ht[0].size发生变化，则我们可
//以通过hash和其他的几个状态，逆推出d->ht[0].size的最初值。
for (j = 0; j < 6; j++) {
hash += integers[j];
/* For the hashing step we use TomasWang's 64 bit integer hash. */
hash = (~hash) + (hash << 21); //hash = (hash << 21) - hash - 1;
hash = hash ^ (hash >> 24);
hash = (hash + (hash << 3)) +(hash << 8); // hash * 265
hash = hash ^ (hash >> 14);
hash = (hash + (hash << 2)) +(hash << 4); // hash * 21
hash = hash ^ (hash >> 28);
hash = hash + (hash << 31);
}
return hash;
}
哈希冲突解决
redis使用的是链地址法， 每个哈希表结点有一个next指针；
哈希表调整
哈希表调整扩展触发条件：
- 当服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令， 并且哈希表的负载因子大于等于1。
- 服务器目前正在执行BGSAVE命令或者BFREWRITEAOF命令， 并且哈希表的负载因子大于等于5。
哈希表调整规则由_dictNextPower函数确定, 规则如下： - 如果执行的是扩展操作， 那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n；
- 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n;
下面是迁移函数的实现
int dictRehash(dict *d, int n) {
// 这里的n代表一共要迁移多少个dictEntry
// 只可以在 rehash 进行中时执行
if (!dictIsRehashing(d)) return 0;
// 进行 N 步迁移
// T = O(N)
while (n--) {
dictEntry *de, *nextde;
// 如果 0 号哈希表为空，那么表示 rehash 执行完毕
// T = O(1)
if (d->ht[0].used == 0) {
// 释放 0 号哈希表
zfree(d->ht[0].table);
// 将原来的 1 号哈希表设置为新的 0 号哈希表
d->ht[0] = d->ht[1];
// 重置旧的 1 号哈希表
_dictReset(&d->ht[1]);
// 关闭 rehash 标识
d->rehashidx = -1;
// 返回 0 ，向调用者表示 rehash 已经完成
return 0;
}
// Note that rehashidx can't overflow as we are sure there are more
// elements because ht[0].used != 0
// 确保 rehashidx 没有越界
assert(d->ht[0].size > (unsigned)d->rehashidx);
// 略过数组中为空的索引，找到下一个非空索引
while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; //dictEntry偏移一位
// 指向该索引的链表表头节点
de = d->ht[0].table[d->rehashidx];
// 将链表中的所有节点迁移到新哈希表
// T = O(1)
while (de) {
unsigned int h;
// 保存下个节点的指针
nextde = de->next;
// 计算新哈希表的哈希值，以及节点插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 插入节点到新哈希表,而且是插入到表头
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 更新计数器
d->ht[0].used--;
d->ht[1].used++;
// 继续处理下个节点
de = nextde;
}
// 将刚迁移完的哈希表索引的指针设为空
d->ht[0].table[d->rehashidx] = NULL;
// 更新 rehash 索引
d->rehashidx++;
}
return 1;
}
redis还有一个渐进式rehash方法， 主要解决键值对数量太多迁移时间太长的问题。
压缩列表
整数集合
