sds結(jié)構
sds主要是用來存儲字符串
struct sdshdr {
// buf 中已占用空間的長度
int len;
// buf 中剩余可用空間的長度
int free;
// 數(shù)據(jù)空間
char buf[];
};
空間預分配
/*
* 對 sds 中 buf 的長度進行擴展督函，確保在函數(shù)執(zhí)行之后借卧，
* buf 至少會有 addlen + 1 長度的空余空間
* （額外的 1 字節(jié)是為 \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 目前的空余空間已經(jīng)足夠悼瓮，無須再進行擴展距淫，直接返回
if (free >= addlen) return s;
// 獲取 s 目前已占用空間的長度
len = sdslen(s);
sh = (void*)(s - (sizeof(struct sdshdr)));
// s 最少需要的長度
newlen = (len + addlen);
// 根據(jù)新長度，為 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);
// 內(nèi)存不足雏吭，分配失敗，返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余長度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}
刪除空間
/*
* 回收 sds 中的空閑空間淮悼，
* 回收不會對 sds 中保存的字符串內(nèi)容做任何修改咐低。
*
* 返回值
* sds ：內(nèi)存調(diào)整后的 sds
*
* 復雜度
* T = O(N)
*/
sds sdsRemoveFreeSpace(sds s) {
struct sdshdr *sh;
sh = (void*)(s - (sizeof(struct sdshdr)));
// 進行內(nèi)存重分配，讓 buf 的長度僅僅足夠保存字符串內(nèi)容
// T = O(N)
sh = zrealloc(sh, sizeof(struct sdshdr) + sh->len + 1);
// 空余空間為 0
sh->free = 0;
return sh->buf;
}
鏈表
typedef struct listNode {
// 前置節(jié)點
struct listNode *prev;
// 后置節(jié)點
struct listNode *next;
// 節(jié)點的值
void *value;
} listNode;
鏈表里面封裝了一個迭代器
//
// listIter 雙端鏈表迭代器
//
typedef struct listIter {
// 當前迭代到的節(jié)點
listNode *next;
// 迭代的方向
int direction;
} listIter;
字典
//哈希表結(jié)點
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個哈希表節(jié)點袜腥，形成鏈表, 哈希沖突解決的一種方法
struct dictEntry *next;
} dictEntry;
//
// dictht 哈希表
//每個字典都使用兩個哈希表见擦，從而實現(xiàn)漸進式 rehash
//
typedef struct dictht { // 這是字典的頭部
// 哈希表數(shù)組, 每個元素都是一條鏈表
dictEntry **table;
// 哈希表大小
unsigned long size; //初始值為4钉汗， 跟STL不太一樣
// 哈希表大小掩碼，用于計算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點的數(shù)量
unsigned long used;
} dictht;
//
// dict 字典
//
typedef struct dict {
// 類型特定函數(shù)
dictType *type; // type里面主要記錄了一系列的函數(shù),可以說是規(guī)定了一系列的接口
// 私有數(shù)據(jù)
void *privdata; // privdata保存了需要傳遞給那些類型特定函數(shù)的可選參數(shù)
// 哈希表
dictht ht[2]; // 有兩張hash表
// rehash 索引
// 并沒有rehash時鲤屡，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; // 目前正在運行的安全迭代器的數(shù)量
} 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結(jié)構體中的幾個狀態(tài)放入到數(shù)組中损痰，以便后面應用到64 bit MixFunctions中。
//dict結(jié)構體其實就是一個hash表的實現(xiàn)酒来，而這些狀態(tài)其實就是第一卢未、第二哈希表的表地址、表大小與
//已用條目的數(shù)量
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堰汉，將這些狀態(tài)信息混合到hash中辽社，組成最后的指紋，如果這些狀態(tài)中有一個
//出現(xiàn)變化翘鸭，可以通過一個算法逆推出該狀態(tài)變化之前的值滴铅。例如，d->ht[0].size發(fā)生變化就乓，則我們可
//以通過hash和其他的幾個狀態(tài)汉匙，逆推出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使用的是鏈地址法生蚁， 每個哈希表結(jié)點有一個next指針盹兢；
哈希表調(diào)整
哈希表調(diào)整擴展觸發(fā)條件：
- 當服務器目前沒有在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令， 并且哈希表的負載因子大于等于1守伸。
- 服務器目前正在執(zhí)行BGSAVE命令或者BFREWRITEAOF命令绎秒， 并且哈希表的負載因子大于等于5。
哈希表調(diào)整規(guī)則由_dictNextPower函數(shù)確定, 規(guī)則如下： - 如果執(zhí)行的是擴展操作尼摹， 那么ht[1]的大小為第一個大于等于ht[0].used*2的2^n见芹；
- 如果執(zhí)行的是收縮操作，那么ht[1]的大小為第一個大于等于ht[0].used的2^n;
下面是遷移函數(shù)的實現(xiàn)
int dictRehash(dict *d, int n) {
// 這里的n代表一共要遷移多少個dictEntry
// 只可以在 rehash 進行中時執(zhí)行
if (!dictIsRehashing(d)) return 0;
// 進行 N 步遷移
// T = O(N)
while (n--) {
dictEntry *de, *nextde;
// 如果 0 號哈希表為空蠢涝，那么表示 rehash 執(zhí)行完畢
// 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 玄呛，向調(diào)用者表示 rehash 已經(jīng)完成
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);
// 略過數(shù)組中為空的索引，找到下一個非空索引
while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; //dictEntry偏移一位
// 指向該索引的鏈表表頭節(jié)點
de = d->ht[0].table[d->rehashidx];
// 將鏈表中的所有節(jié)點遷移到新哈希表
// T = O(1)
while (de) {
unsigned int h;
// 保存下個節(jié)點的指針
nextde = de->next;
// 計算新哈希表的哈希值和二，以及節(jié)點插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 插入節(jié)點到新哈希表,而且是插入到表頭
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 更新計數(shù)器
d->ht[0].used--;
d->ht[1].used++;
// 繼續(xù)處理下個節(jié)點
de = nextde;
}
// 將剛遷移完的哈希表索引的指針設為空
d->ht[0].table[d->rehashidx] = NULL;
// 更新 rehash 索引
d->rehashidx++;
}
return 1;
}
redis還有一個漸進式rehash方法徘铝， 主要解決鍵值對數(shù)量太多遷移時間太長的問題。
壓縮列表
整數(shù)集合
