《Redis設計與實作》讀書筆記
簡單動態字串
SDS的定義
結構：
buf陣列：用于保存字串
len屬性：記錄SDS中保存字串的長度
free屬性：記錄buf中未使用位元組數量
遵循C字串以空字串結尾的慣例，保存空字串的位元組不計入長度
SDS與C字串的區別
常數復雜度獲取字串長度
因為SDS中的len屬性已經記錄了字串長度，所以不需要像C字串一樣獲取長度時需要遍歷一遍字串，確保獲取字串長度的作業不會限制Redis的性能瓶頸
杜絕緩沖區溢位
當SDS API需要對SDS進行修改時，API會先檢查SDS的空間是否滿足修改所需要的要求，如果不滿足的話，API會自動將SDS的空間擴展至執行修改所需要的大小
減少修改字串時帶來的記憶體重分配次數
C字串修改時，需要程式重新分配記憶體，防止記憶體溢位或泄露，對于一個資料庫來說嗎，對于速度的要求時苛刻的，且資料會被頻繁的修改，而重分配會占用大量時間，修改頻繁的話，可能會對性能照成影響
而SDS通過free屬性，實作了空間預分配與惰性空間釋放兩種優化策略
1.空間預分配
SDS進行修改后len小于1MB時：程式會分配和len相同大小的未使用空間
SDS進行修改后len大于1MB時：程式會分配1MB的未使用空間
2.惰性空間釋放
當需要縮短SDS的字串時，程式不會立刻重分配來回收多余位元組，而是先使用free將這些位元組記錄起來，等待將來再使用
二進制安全
SDS API會以二進制的方式來處理SDS存放在陣列里面的資料
兼容部分C字串函式
因為SDS遵循了C字串以空字串結尾的慣例
SDS API
鏈表
鏈表與鏈表節點的實作
每個鏈表節點使用一個 adlist.h/listNode 結構來表示：
typedef struct listNode {
?
// 前置節點
struct listNode *prev;
?
// 后置節點
struct listNode *next;
?
// 節點的值
void *value;
?
} listNode;
多個 listNode 可以通過 prev 和 next 指標組成雙端鏈表
雖然僅僅使用多個 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;
list 結構為鏈表提供了表頭指標 head 、表尾指標 tail ， 以及鏈表長度計數器 len ， 而 dup 、 free 和 match 成員則是用于實作多型鏈表所需的型別特定函式：
-
dup函式用于復制鏈表節點所保存的值； -
free函式用于釋放鏈表節點所保存的值； -
match函式則用于對比鏈表節點所保存的值和另一個輸入值是否相等，
Redis 的鏈表實作的特性可以總結如下：
-
雙端： 鏈表節點帶有
prev和next指標， 獲取某個節點的前置節點和后置節點的復雜度都是
， -
無環： 表頭節點的
prev指標和表尾節點的next指標都指向NULL， 對鏈表的訪問以NULL為終點， -
帶表頭指標和表尾指標： 通過
list結構的head指標和tail指標， 程式獲取鏈表的表頭節點和表尾節點的復雜度為 ， -
帶鏈表長度計數器： 程式使用
list結構的len屬性來對list持有的鏈表節點進行計數， 程式獲取鏈表中節點數量的復雜度為， -
多型： 鏈表節點使用
void*指標來保存節點值， 并且可以通過list結構的dup、free、match三個屬性為節點值設定型別特定函式， 所以鏈表可以用于保存各種不同型別的值，
鏈表和鏈表節點的API
字典
字典的實作
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 結構定義：
typedef struct dictht {
?
// 哈希表陣列
dictEntry **table;
?
// 哈希表大小
unsigned long size;
?
// 哈希表大小掩碼，用于計算索引值
// 總是等于 size - 1
unsigned long sizemask;
?
// 該哈希表已有節點的數量
unsigned long used;
?
} dictht;
table 屬性是一個陣列， 陣列中的每個元素都是一個指向 dict.h/dictEntry 結構的指標， 每個 dictEntry 結構保存著一個鍵值對，
size 屬性記錄了哈希表的大小， 也即是 table 陣列的大小， 而 used 屬性則記錄了哈希表目前已有節點（鍵值對）的數量，
sizemask 屬性的值總是等于 size - 1 ， 這個屬性和哈希值一起決定一個鍵應該被放到 table 陣列的哪個索引上面，
哈希表節點
哈希表節點使用 dictEntry 結構表示， 每個 dictEntry 結構都保存著一個鍵值對：
typedef struct dictEntry {
?
// 鍵
void *key;
?
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
?
// 指向下個哈希表節點，形成鏈表
struct dictEntry *next;
?
} dictEntry;
key 屬性保存著鍵值對中的鍵， 而 v 屬性則保存著鍵值對中的值， 其中鍵值對的值可以是一個指標， 或者是一個 uint64_t 整數， 又或者是一個 int64_t 整數，
next 屬性是指向另一個哈希表節點的指標， 這個指標可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵沖突（collision）的問題，
舉個例子， 圖 4-2 就展示了如何通過 next 指標， 將兩個索引值相同的鍵 k1 和 k0 連接在一起，
字典
Redis 中的字典由 dict.h/dict 結構表示：
typedef struct dict {
?
// 型別特定函式
dictType *type;
?
// 私有資料
void *privdata;
?
// 哈希表
dictht ht[2];
?
// rehash 索引
// 當 rehash 不在進行時，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
?
} dict;
type 屬性和 privdata 屬性是針對不同型別的鍵值對， 為創建多型字典而設定的：
-
type屬性是一個指向dictType結構的指標， 每個dictType結構保存了一簇用于操作特定型別鍵值對的函式， Redis 會為用途不同的字典設定不同的型別特定函式， -
而
privdata屬性則保存了需要傳給那些型別特定函式的可選引數，
typedef 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);
?
} dictType;
ht 屬性是一個包含兩個項的陣列， 陣列中的每個項都是一個 dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用，
除了 ht[1] 之外， 另一個和 rehash 有關的屬性就是 rehashidx ： 它記錄了 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那么它的值為 -1 ，
哈希演算法
將新的鍵值插入字典時，程式需要先根據鍵值對的鍵計算出哈希值和索引值，然后根據索引值將新鍵值對所在的哈希表節點放到哈希表陣列對應的索引上面
Redis 計算哈希值和索引值的方法如下：
# 使用字典設定的哈希函式，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
?
# 使用哈希表的 sizemask 屬性和哈希值，計算出索引值
# 根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;
解決鍵沖突
當兩個或兩個以上的鍵分配到哈希陣列的同一個索引上時，Redis使用鏈地址法解決鏈沖突
鏈地址法
哈希表節點都有一個next指標，可以使用next指標構成單向鏈表，
且dictEntry節點構成的鏈表沒有指向鏈表末尾的指標，為了節省時間，新的節點一般直接添加到表頭位置
rehash（重新散列）
目的
隨著哈希表鍵值對的逐漸增加或減少，為了讓哈希表的負載因子維持在一定范圍內
步驟
-
為字典的
ht[1]哈希表分配空間，這個哈希表的空間大小取決于要執行的操作， 以及ht[0]當前包含的鍵值對數量 （也即是ht[0].used屬性的值）：-
如果執行的是擴展操作， 那么
ht[1]的大小為第一個大于等于ht[0].used * 2的
（2的n次方冪）； -
如果執行的是收縮操作， 那么
ht[1]的大小為第一個大于等于ht[0].used的 ，
-
-
將保存在
ht[0]中的所有鍵值對 rehash 到ht[1]上面： rehash 指的是重新計算鍵的哈希值和索引值， 然后將鍵值對放置到ht[1]哈希表的指定位置上， -
當
ht[0]包含的所有鍵值對都遷移到了ht[1]之后 （ht[0]變為空表）， 釋放ht[0]， 將ht[1]設定為ht[0]， 并在ht[1]新創建一個空白哈希表， 為下一次 rehash 做準備，
哈希表的收縮與擴展
以下條件滿足任意一個時，程式會自動開始對哈希表執行擴展操作：
-
服務器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的負載因子大于等于
1 -
服務器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的負載因子大于等于
5
負載因子計算公式：
# 負載因子 = 哈希表已保存節點數量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
當哈希表的負載因子小于 0.1 時， 程式自動開始對哈希表執行收縮操作
漸進式rehash
目的：
假如哈希表中保存了大量的資料，一次性將這些資料進行rehash時會產生龐大的計算量，為了防止rehash對redis的性能產生影響
漸進式rehash實作的詳細步驟：
-
為
ht[1]分配空間， 讓字典同時持有ht[0]和ht[1]兩個哈希表， -
在字典中維持一個索引計數器變數
rehashidx， 并將它的值設定為0， 表示 rehash 作業正式開始， -
在 rehash 進行期間， 每次對字典執行添加、洗掉、查找或者更新操作時， 程式除了執行指定的操作以外， 還會順帶將
ht[0]哈希表在rehashidx索引上的所有鍵值對 rehash 到ht[1]， 當 rehash 作業完成之后， 程式將rehashidx屬性的值增一， -
隨著字典操作的不斷執行， 最終在某個時間點上，
ht[0]的所有鍵值對都會被 rehash 至ht[1]， 這時程式將rehashidx屬性的值設為-1， 表示 rehash 操作已完成，
漸進式rehash執行期間的哈希表操作
-
字典的刪改查等操作都會在兩個哈希表之間共同進行
-
新增加的鍵只添加
ht[1]上
字典API
跳躍表
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/551003.html
標籤：其他
上一篇：袋鼠云春季生長大會圓滿落幕，帶來數實融合下的新產品、新方案、新實踐！
下一篇：返回列表