String
數(shù)據(jù)結(jié)構(gòu)
struct sdshdr {
int len;//記錄buf數(shù)組中已使用字節(jié)的數(shù)量等于SDS所保存字符串的長(zhǎng)度
int alloc;//記錄對(duì)象分配的內(nèi)存空間
char flag;//記錄字符串類(lèi)型钞钙。
char buf[];//字節(jié)數(shù)組伍俘，用于保存字符串
}
示例
string示例.png
這里就可以存儲(chǔ)"Redis C",而C只能讀取Redis字符串
對(duì)C字符串和SDS之間的區(qū)別進(jìn)行總結(jié)
| C字符串 | SDS |
|---|---|
| 獲取字符串長(zhǎng)度的復(fù)雜度為O(N) | 獲取字符串長(zhǎng)度的復(fù)雜度為O(1) |
| API是不安全的，可能會(huì)造成緩存區(qū)溢出 | API是安全的楣铁，不會(huì)造成緩存區(qū)溢出 |
| 修改字符串長(zhǎng)度N次必然需要執(zhí)行N次內(nèi)存重分配 | 修改字符串長(zhǎng)度N次最多需要執(zhí)行N次內(nèi)存重分配 |
| 只能保存文本數(shù)據(jù) | 可以保存文件或則二進(jìn)制數(shù)據(jù) |
| 可以使用所有<string.h>庫(kù)中的函數(shù) | 可以使用一部分<string.h>庫(kù)中的函數(shù) |
鏈表
數(shù)據(jù)結(jié)構(gòu)
typedef struct listNode {
struct listNode *prev; //前置節(jié)點(diǎn)
struct listNode *next; //后置節(jié)點(diǎn)
void *value; //節(jié)點(diǎn)的值
} listNode;
typedef struct listIter {
listNode *next;
int direction;
} listIter;
typedef struct list {
listNode *head; //表頭節(jié)點(diǎn)
listNode *tail; //表尾節(jié)點(diǎn)
void *(*dup)(void *ptr); //節(jié)點(diǎn)值復(fù)制函數(shù)
void (*free)(void *ptr); //節(jié)點(diǎn)值釋放函數(shù)
int (*match)(void *ptr, void *key); //節(jié)點(diǎn)值對(duì)比函數(shù)
unsigned long len;
} list;
示例
image.png
鏈表的特點(diǎn)
- 鏈表唄廣泛用于實(shí)現(xiàn)Redis的個(gè)鐘功能，比如列表鍵更扁，發(fā)布與訂閱盖腕、慢查詢(xún)、監(jiān)視器等浓镜。
- Redis的鏈表是雙向無(wú)環(huán)鏈表溃列。
- listIter的結(jié)構(gòu)是為了遍歷list使用的。與java Iterator類(lèi)似
- list定義的三個(gè)函數(shù)是為了抽象node的value使用竖哩。value的類(lèi)型不同哭廉，三個(gè)函數(shù)的內(nèi)容也不同，類(lèi)似于JAVA的抽象方法相叁。
MAP
數(shù)據(jù)結(jié)構(gòu)
typedef struct dictEntry {
void *key; //鍵
union { //值
void *val; //字符串或別的值
uint64_t u64; //無(wú)符號(hào)數(shù)字
int64_t s64; //有符號(hào)數(shù)字
double d; //浮點(diǎn)
} v;
struct dictEntry *next; //指向下個(gè)哈希表節(jié)點(diǎn),形成鏈表
} dictEntry;
typedef struct dictht {
dictEntry **table; //哈希表數(shù)組
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表大小掩碼遵绰，用于計(jì)算索引
unsigned long used; //該哈希表已有節(jié)點(diǎn)的數(shù)量
} dictht;
typedef struct dict {
dictType *type; //類(lèi)型特定函數(shù)
void *privdata; //私有數(shù)據(jù)
dictht ht[2]; //哈希表
long rehashidx; //rehash索引,當(dāng)rehash不在進(jìn)行時(shí),值為-1
unsigned long iterators; //當(dāng)前iterators遍歷的數(shù)量
} dict;
結(jié)構(gòu)示例
image.png
map特色
- rehash
- 為字典的ht[1]哈希表分配空間,,這個(gè)哈希表的空間大小取決于要執(zhí)行的操作,以及ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量(也即使ht[0].used屬性的值):
* 如果執(zhí)行的是擴(kuò)展操作,那么ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2的n次方冪;
* 如果執(zhí)行的是收縮操作,那么ht[1]的大小為第一個(gè)大于等于ht[0].used的2的n次冪.
- 將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上面;
3.當(dāng)ht[0]包含的所有鍵值對(duì)都遷移到ht[1]之后(ht[0]變?yōu)榭毡?,釋放ht[0],將ht[1]設(shè)置為ht[0],并在ht[1]新創(chuàng)建一個(gè)空白哈希表,為下一次rehash做準(zhǔn)備.
- rehash的擴(kuò)展與收縮條件
- 服務(wù)器當(dāng)前沒(méi)有執(zhí)行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的負(fù)載因子大于等于1.
- 服務(wù)器目前正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表負(fù)載因子大于等于5.
- 哈希表的負(fù)載因子小于0.1時(shí),程序自動(dòng)開(kāi)始對(duì)哈希表執(zhí)行收縮操作.
負(fù)載因子公式: load_factor = ht[0].used / ht[0].size;
java-hashMap負(fù)載因子為0.75 轉(zhuǎn)換為redis的負(fù)載因子為 0.75;
- 漸進(jìn)式rehash
如果 ht[0] 里只保存著四個(gè)鍵值對(duì)， 那么服務(wù)器可以在瞬間就將這些鍵值對(duì)全部 rehash 到 ht[1] 增淹； 但是椿访， 如果哈希表里保存的鍵值對(duì)數(shù)量不是四個(gè)， 而是四百萬(wàn)虑润、四千萬(wàn)甚至四億個(gè)鍵值對(duì)成玫， 那么要一次性將這些鍵值對(duì)全部 rehash 到 ht[1] 的話(huà)， 龐大的計(jì)算量可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)拳喻。
因此哭当， 為了避免 rehash 對(duì)服務(wù)器性能造成影響， 服務(wù)器不是一次性將 ht[0] 里面的所有鍵值對(duì)全部 rehash 到 ht[1] 冗澈， 而是分多次钦勘、漸進(jìn)式地將 ht[0] 里面的鍵值對(duì)慢慢地 rehash 到 ht[1] 。
以下是哈希表漸進(jìn)式 rehash 的詳細(xì)步驟：
- 為 ht[1] 分配空間亚亲， 讓字典同時(shí)持有 ht[0] 和 ht[1] 兩個(gè)哈希表彻采。
在字典中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx ， 并將它的值設(shè)置為 0 捌归， 表示 rehash 工作正式開(kāi)始肛响。 - 在 rehash 進(jìn)行期間，ht[0]只會(huì)執(zhí)行刪除'查找,對(duì)字典執(zhí)行添加只會(huì)作用于ht[1] 惜索， 當(dāng) rehash 工作完成之后特笋， 程序?qū)?rehashidx 屬性的值增一。
- 隨著字典操作的不斷執(zhí)行门扇， 最終在某個(gè)時(shí)間點(diǎn)上雹有， ht[0] 的所有鍵值對(duì)都會(huì)被 rehash 至 ht[1] 偿渡， 這時(shí)程序?qū)?rehashidx 屬性的值設(shè)為 -1， 表示 rehash 操作已完成霸奕。
代碼示例
//新增替換的時(shí)候調(diào)用該方法
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
//如果當(dāng)前正在rehash,則調(diào)用一步rehash,轉(zhuǎn)移一個(gè)table數(shù)組
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. (查找key,如果存在返回-1)*/
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* system it is more likely that recently added entries are accessed
* more frequently. (分配內(nèi)存,rehash時(shí)插入到ht[1]上面)*/
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. (設(shè)置key值)*/
dictSetKey(d, entry, key);
return entry;
}
跳躍表
數(shù)據(jù)結(jié)構(gòu)
typedef struct zskiplistNode {
sds ele; //對(duì)象
double score; //分值
struct zskiplistNode *backward; //后退指針
struct zskiplistLevel { //層
struct zskiplistNode *forward; //前進(jìn)指針
unsigned long span; //跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;//頭尾節(jié)點(diǎn)
unsigned long length; //list長(zhǎng)度
int level; //表中層數(shù)最大的節(jié)點(diǎn)層數(shù)
} zskiplist;
示例
跳表結(jié)構(gòu)示例
如果不懂跳表的數(shù)據(jù)結(jié)構(gòu)可以閱讀一下:http://zhangtielei.com/posts/blog-redis-skiplist.html
跳表特色
- 跳躍表示有序集合的底層實(shí)現(xiàn)之一
- Redis的跳躍表實(shí)現(xiàn)由zskiplist和zskiplistNode兩個(gè)結(jié)構(gòu)組成,其中zskiplist用于保存跳躍表信息,而zskiplistNode則用于標(biāo)示跳躍表節(jié)點(diǎn).
3.每個(gè)跳躍表節(jié)點(diǎn)的層高都是1至64之間的隨機(jī)數(shù).
4.在同一個(gè)跳躍表中,多個(gè)節(jié)點(diǎn)可以包含相同的分值,但每個(gè)節(jié)點(diǎn)的成員對(duì)象可以相同(<<redis設(shè)計(jì)與實(shí)現(xiàn)>>說(shuō)對(duì)象唯一,是因?yàn)樘S表永遠(yuǎn)都是和dict一起使用,所以已經(jīng)過(guò)濾掉了重復(fù)對(duì)象)
代碼:
//插入代碼
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
//校驗(yàn)數(shù)據(jù)
serverAssert(!isnan(score));
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position(查詢(xún)插入位置) */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))//因?yàn)閘evel[0]是前指針,所以在遍歷i=0時(shí)是往前遍歷,找到插入的前一個(gè)指針
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
level = zslRandomLevel();//獲取隨機(jī)level
...省略算法代碼
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward) //level[0]就是backward一樣
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
- 跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序,當(dāng)分值相同時(shí),節(jié)點(diǎn)按照成員對(duì)象大小進(jìn)行排序.
整數(shù)集合
數(shù)據(jù)結(jié)構(gòu)
typedef struct intset {
uint32_t encoding; //編碼方式INT16,INT32,INT64
uint32_t length; //數(shù)量
int8_t contents[]; //保存元素的數(shù)組
} intset;
示例
image.png
image.png
整數(shù)列表特色
- 整數(shù)集合是集合鍵的底層實(shí)現(xiàn)之一
- 不同的編碼是為了節(jié)約內(nèi)存,數(shù)字小的時(shí)候會(huì)用INT16的方式
- 整數(shù)集合只支持升級(jí)操作,不支持降級(jí)操作
- 數(shù)組以有序,無(wú)重復(fù)的方式保存集合
代碼示例:
//插入代碼
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 1;
if (valenc > intrev32ifbe(is->encoding)) {
//升級(jí)編碼長(zhǎng)度
return intsetUpgradeAndAdd(is,value);
} else {
//查詢(xún)value是否存在返回1,不存在返回0 pos返回前一個(gè)位置
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
return is;
}
is = intsetResize(is,intrev32ifbe(is->length)+1);//擴(kuò)容,刪除也會(huì)清空內(nèi)存
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);//不是最后一個(gè)移動(dòng)位置
}
_intsetSet(is,pos,value);//設(shè)置值
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
壓縮列表
數(shù)據(jù)結(jié)構(gòu)
壓縮列表沒(méi)有數(shù)據(jù)結(jié)構(gòu),只有一個(gè)大的內(nèi)存快,通過(guò)內(nèi)存地址計(jì)算各個(gè)屬性
組成部分視圖:
代碼實(shí)現(xiàn):
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))//定義ziplist頭部分
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) //記錄zip的大小
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) //記錄zip尾節(jié)點(diǎn)距離壓縮列表起始地址有多少字節(jié),定位尾節(jié)點(diǎn)地址
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))//節(jié)點(diǎn)的長(zhǎng)度
entry的數(shù)據(jù)結(jié)構(gòu):
typedef struct zlentry {
unsigned int prevrawlensize; //記錄了前一個(gè)節(jié)點(diǎn)的長(zhǎng)度溜宽，通過(guò)這個(gè)值，可以進(jìn)行指針計(jì)算质帅，從而跳轉(zhuǎn)到上一個(gè)節(jié)點(diǎn)适揉。
unsigned int prevrawlen; // 前一個(gè)entry長(zhǎng)度
unsigned int lensize; // entry的字節(jié)大小
unsigned int len;
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; //節(jié)點(diǎn)類(lèi)型可能是整數(shù)或者字符串
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
