第一章 資料結構

　　1. 簡單動態字串

　　下圖是簡單動態字串（simple dynamic string， SDS）的結構表示

• free屬性的值為0，表示這個SDS沒有分配任何未使用空間
• len屬性的值為5，表示這個SDS保存了一個5位元組長的字串
• buf屬性是一個char型別的陣列，陣列的前五個位元組分別保存了R, e, d, i, s五個字符，最后一個位元組則保存了空字符'\o'

　　SDS遵循C語言字串以空字符結尾的慣例，保存空字符的1位元組空間不計算在SDS的len屬性里面，這個空字符對SDS的使用者來說是完全透明的，遵循空字符結尾的好處是，可以重用一些C字串函式庫中的函式，例如，有一個指向圖2-1所示SDS的指標s，那么可以直接使用<stdio.h>/printf函式，通過執行以下陳述句：printf("%s", s->buf);

　　1.1 SDS與C字串的區別

　　1.1.1 常數復雜度獲得字串長度

　　因為C字串并不記錄自身長度資訊，所以為了獲取一個C字串長度，程式必須遍歷整個字串，對遇到的每個字符進行計數，直到遇到代表字串結尾的空字符為止，這個操作的復雜度為O(N)，如下圖所示，

　　通過訪問SDS的len屬性，Redis將獲取字串長度所需的復雜度從O（N）降低到了O（1）， 

　　1.1.2 杜絕緩沖區溢位

　　<string.h>/strcat函式可以將src字串中的內容拼接到dest字串的末尾： char *strcat (char *dest, const char *src)

　　strcat函式假定用戶在執行這個函式時，已經為dest分配了足夠多的記憶體，如果假設不成立，則會造成緩沖區溢位，導致s2保存的內容被意外修改了，

　　當SDS API需要對SDS進行修改時，API先檢查SDS的空間是否滿足修改所需的要求，如果不滿足，API會自動將SDS的空間擴展至執行修改所需的大小，然后再進行修改，用戶不需要手動修改SDS空間的大小， 

　　1.1.3 減少修改字串時帶來的記憶體重分配次數

　　對于一個包含N個字符的C字串，底層實作是一個N+1個字符長的陣列，每次縮短或者增加C字串，都需要對陣列做一次記憶體重分配：

• 如果程式執行的是增長字串的操作，比如拼接（append），那么執行這個操作之前，程式需要先通過記憶體重分配來擴展底層陣列的空間大小——不然會造成緩沖區溢位
• 對于縮短字串操作，比如截斷（trim）操作，需要釋放不再需要的記憶體空間，不然會造成記憶體泄漏

　　由于記憶體重分配涉及復雜的演算法，比較耗時，SDS通過空間預分配和惰性空間釋放兩種優化策略減少記憶體重分配次數

　　1. 空間預分配

　　空間預分配用于優化SDS的字串增長操作：當SDS的API對一個SDS進行修改，并需要對SDS進行空間擴展，程式不僅會分配必須的空間，還會為SDS分配額外的未使用空間，如果SDS長度小于1MB，程式分配和len屬性同樣大小的未使用空間；如果長度大于1MB，程式分配1MB的未使用空間，

　　2. 惰性空間釋放

　　當SDS的API需要縮短SDS保存的字串時，程式并不立即使用記憶體重分配來回收縮短后多出來的位元組，而是使用free屬性將這些位元組的數量記錄起來，以備將來使用，

　　1.1.4 二進制安全

　　C字串中的字符必須符合某種編碼（比如ASCII），并且除了字串的末尾之外，字串里面不能包含空字符，否則最先被程式讀入的空字符將被誤認為是字串結尾，這些限制使得C字串只能保存文本資料，而不能保存圖片、音頻、視頻、壓縮檔案這樣的二進制資料，

　　SDS API都會以處理二進制的方式來處理SDS存放在buf陣列里的資料，程式不會對其中的資料做任何限制、過濾或者假設，資料寫入是什么樣子，讀取時就是什么樣子，

　　1.1.5 兼容部分C字串函式

　　通過在buf陣列分配空間時多分配一個位元組來容納空字符，使得SDS可以重用一部分<string.h>庫定義的函式，表2-2列出了SDS主要操作API，

　　2. 鏈表

　　每個鏈表節點使用一個adlist.h/listNode結構來表示：

 　　多個listNode可以通過prev和next指標組成雙端鏈表：

　　list結構表示：

　　Redis鏈表特性：

• 雙端：鏈表節點帶有prev和next指標，獲取某個節點的前置節點和后置節點的復雜度都是O(1)
• 無環：表頭節點的prev指標和表尾節點的next指標都指向NULL，對鏈表的訪問以NULL為終點
• 帶表頭指標和表尾指標：通過list結構的head指標和tail指標，程式獲取鏈表的表頭節點和表尾節點的復雜度為O(1)
• 帶鏈表長度計數器：程式獲取鏈表中節點數量的復雜度為O（1）
• 多型：節點使用void*指標保存節點值，所以鏈表可以保存各種不同型別的值

　　3. 字典

　　3.1 字典結構

　　Redis字典使用哈希表作為底層實作，一個哈希表里面可以有多個哈希表節點，而每個哈希表節點就保存了字典中的一個鍵值對，

　　哈希表結構及哈希表節點定義： 

　　資料存放如下所示：

　　Redis中字典由dict.h/dict結構表示：

　　type屬性和privdata屬性是針對不同型別的鍵值對，為創建多型字典而設定的：

• type屬性是一個指向dictType結構的指標，每個dictType結構保存了一簇用于操作特定型別鍵值對的函式，Redis會為用途不同的字典設定不同的型別特定函式
• privdata屬性則保存了需要傳給那些型別特定函式的可選引數

　　ht[1]哈希表會在對ht[0]哈希表進行rehash時使用，

　　3.2 哈希演算法

　　Redis計算哈希值和索引值的方法如下：

　　hash = dict->type->hashFunction(key);

　　index = hash & dict->ht[x].sizemask;

 　　index表示放在dictEntry中的哪個槽內

　　3.3 解決鍵沖突

　　當兩個或以上的鍵被分配到了哈希表陣列的同一個索引上面時，稱為發生了哈希碰撞，Redis的哈希表通過使用鏈地址法來解決鍵沖突，被分配到同一個索引上的多個節點可以用這個單向鏈表連接起來，

　　因為dictEntry節點組成的鏈表沒有指向鏈表表尾的指標，所以為了速度考慮，程式總是將節點添加到鏈表的表頭位置（復雜度為O(1)），排在其他所有節點前面，

　　3.4 rehash

　　哈希表的擴展和收縮

　　滿足下面任一條件，哈希表會進行擴展操作：

• 服務器沒有執行BGSAVE或BGREWRITEAOF命令，并且哈希表的負載因子大于等于1
• 服務器正在執行BGSAVE或BGREWRITEAOF命令，并且哈希表的負載因子大于等于5

　　負載因子的計算：哈希表已保存節點數量/哈希表大小

　　當負載因子小于0.1時，程式自動對哈希表進行收縮操作，

　　Redis對字典的哈希表執行rehash的步驟如下：

　　1） 為字典ht[1]哈希表分配空間：

• 如果執行的是擴展操作，那么ht[1]的大小為第一個大于等于ht[0].used*2ⁿ
• 如果執行的是收縮操作，那么ht[1]的大小也為第一個大于等于ht[0].used*2ⁿ

　　2） 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面

　　3） 當ht[0]包含的所有鍵值對都遷移到ht[1]后，釋放ht[0]，將ht[1]設定為ht[0]，并在ht[1]新創建一個空白哈希表，為下一次rehash做準備

　　示例步驟如下所示：

　　3.5 漸進式rehash

　　擴展或收縮哈希表需要將ht[0]里面的所有鍵值對rehash到ht[1]里面，但是，這個rehash動作并不是一次性、集中式地完成的，而是多次、漸進式地完成的，具體步驟如下：

　　1）為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表

　　2）在字典中維持一個索引計數器變數rehashidx，并將它的值設為0，表示rehash作業正式開始

　　3） 在rehash期間，每次對字典執行添加、洗掉、查找或者更新操作時，程式除了執行指定的操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當rehash完成后，將rehashidx屬性值加一

　　4） 隨著字典操作不斷執行，最后在某個時間點上，ht[0]的所有鍵值對都會被rehash到ht[1]，這時將rehashidx設定為-1，表示rehash操作結束，

　　字典主要API操作

　　4. 跳躍表

 　　如果一個有序集合包含的元素數量比較多，或者有序集合中元素的成員是比較長的字串時，Redis就會使用跳躍表來作為有序集合鍵的底層實作，例如，fruit-price是一個有序集合鍵，以水果名為成員，水果價錢為分值，fruit-price有序集合的所有資料都保存在一個跳躍表里面，其中每個跳躍表節點會保存一款水果的資訊，所有水果按價錢由低到高排序，

　　4.1 跳躍表的實作

　　Redis跳躍表由redis.h/zskiplistNode（用于表示跳躍表節點）和redis.h/zskiplist（保存跳躍表節點相關資訊）兩個結構定義，示例如下：

　　4.2 跳躍表節點

　　跳躍表節點的實作由redis.h/zskiplistNode結構定義：

 　　1. 層

　　每次創建一個新的跳躍表節點時，程式都根據冪次定律（power low，越大的數出現的概率越小）隨機生成一個介于1和32之間的值作為level陣列的大小，即層的高度，如圖5-2所示，

　　跳躍表節點中每個元素包含一個指向其他節點的指標，程式可以通過這些層加快訪問其他節點的速度，一般來說，層的數量越多，訪問其他節點的速度就越快，

　　2. 前進指標

　　每個層都有一個指向表尾方向的前進指標（level[i].forward屬性），用于從表頭向表尾方向訪問節點，圖5-3用虛線表示了程式從表頭向表尾方向，遍歷跳躍表中所有節點的路徑，

　　3. 跨度

　　層的跨度（level[i].span）用于記錄兩個節點之間的距離：

• 兩個節點之間的跨度越大，相距的越遠
• 指向NULL的所有前進指標的跨度都為0

　　遍歷操作使用前進指標即可完成，跨度是用來計算排位的（節點在跳躍表中的位置），

　　4. 后退指標

　　節點的后退指標（backward屬性）用于從表尾向表頭訪問節點，

　　5. 分值和成員

　　節點的分值（score屬性）是一個double型別的浮點數，跳躍表中的所有節點都按分值從小到大來排序，

　　節點的成員物件（obj屬性，唯一的）是一個指標，它指向一個字串物件，而字串物件則保存一個SDS值，

 　　4.3 跳躍表

　　zskiplist結構的定義如下：

　　header和tail指標分別指向跳躍表的表頭和表尾節點，通過這兩個指標，程式定位表頭節點和表尾節點的復雜度為O（1）.

　　length屬性記錄節點的數量，程式可以在O(1)復雜度內回傳跳躍表的長度，

　　level屬性用于獲得跳躍表中層高最大的節點的層數量，表頭節點的層高不計算在內， 　　

　　4.4 跳躍表常用API

　　5. 整數集合

　　5.1 整數集合的實作

　　其中encoding有三種取值：

• INTSET_ENC_INT16   每個項是int16_t型別的整數值（取值范圍：-2¹⁵~2¹⁵-1）
• INTSET_ENC_INT32   每個項是int32_t型別的整數值（取值范圍：-2³¹~2³¹-1）　
• INTSET_ENC_INT64   每個項是int64_t型別的整數值（取值范圍：-2⁶³~2⁶³-1）

　　5.2 升級

　　如果新添加的元素型別比整數集合現有所有元素的型別都要長時，整數集合需要先進行升級（upgrade），然后再將新元素添加到整數集合里面，升級分三步進行：

　　1） 根據新元素的型別，擴展整數集合底層陣列的空間大小，并為新元素分配空間

　　2） 將底層陣列現有的所有元素都轉換成與新元素相同的型別，并將型別轉換后的元素放置到正確的位置上，而且在放置元素程序中，需要維持底層陣列的有序性質不變

　　3） 將元素添加到底層陣列里面

　　contents陣列中原先包含3個，每個占用16位空間的元素，之后需要插入一個占用32位空間的元素65535，其程序如下所示：

 　　5.3 升級的好處

　　5.3.1 提升靈活性

　　整數集合可以通過自動升級底層陣列來適應新元素，可以隨意地將int16_t，int32_t或int64_t型別的整數添加到集合中，不必擔心出現型別錯誤，

　　5.3.2 節約記憶體

　　盡量先用int16_t型別來保存元素，在必要時進行升級，以節約記憶體，

　　5.4 降級

　　整數集合不支持降級，

　　5.5 整數集合API

　　6. 壓縮串列

　　6.1 壓縮串列的構成

　　壓縮串列是Redis為了節約記憶體而開發的，由一系列特殊編碼地連續記憶體塊組成的順序型資料結構，一個壓縮串列可以包含任意多個節點（entry），每個節點可以保存一個位元組陣列或者一個整數值，

　　下圖為壓縮串列各組成部分：

　　圖7-2展示了一個壓縮串列實體：

• zlbytes屬性地值位0x50（十進制80），表示壓縮串列總長80位元組
• zltail屬性值為0x3c（十進制60），這表示如果我們有一個指向壓縮串列起始地址地指標p，那么p+60，就可以計算出表尾節點entry3的地址
• zllen屬性值為0x3，表示壓縮串列包含三個節點

　　6.2 壓縮串列節點的構成

　　下圖為壓縮串列各個組成部分：

　　1. previous_entry_length

　　節點的previous_entry_length屬性以位元組為單位，記錄了壓縮串列中前一個節點的長度：

• 如果前一個節點長度小于254位元組，previous_entry_length屬性的長度為1位元組
• 如果前一個位元組長度大于等于254位元組，previous_entry_length的長度為5位元組，第一個位元組會被設定為0xFE（十進制254），之后的四個位元組用于保存前一節點的長度 

　　如果有一個指向當前節點起始地址的指標c，可以根據下圖計算出前一個節點的指標p，壓縮串列從表尾向表頭遍歷操作就是基于這一原理實作的，

　　2. encoding

　　節點encoding屬性記錄了節點的content屬性所保存資料的型別及長度，

　　值的最高位為00、01、10是位元組陣列編碼，陣列的長度由編碼除去最高兩位之后的其他位記錄

　　值的最高位以11開頭的是整數編碼

　　3. content　　

　　6.3 連鎖更新

　　下面討論一種對串列插入或洗掉節點時，會發生的極端情況——連鎖更新，

　　前面小節提到過，如果前一個節點長度小于254位元組，那么previous_entry_length屬性需要用1位元組來保存長度值；如果前一個節點長度大于254位元組，那么previous_entry_length屬性需要用5位元組來保存長度值，

　　現在，考慮這樣一種情況，在一個壓縮串列中，存在多個連續的、長度介于250位元組到253位元組之間的節點e1至eN，如下圖所示：

　　如果將一個長度大于等于254位元組的新節點new設定為壓縮串列的表頭節點，如下圖所示：

　　此時e1節點的previous_entry_length屬性從原來的1位元組擴展為5位元組，e1原本的長度介于250位元組到253位元組之間，由于previous_entry_length長度改變，e1的長度變為介于254位元組到257位元組，從而引發e2的更新，e2又會引發e3的擴展，直到eN為止，并將此程序稱為連鎖更新，下圖是另一種引起連鎖更新的情況：

　　因為連鎖更新在最壞的情況下需要對壓縮串列執行N次空間重分配操作，而每次空間重分配的最壞復雜度是O（N），所以連鎖更新的最壞復雜度為O(N²) ，

　　但是，盡管連鎖更新的復雜度較高，但是真正造成性能問題的幾率很低：

• 壓縮串列里面需要恰好有多個連續的、長度介于250位元組到253位元組之間的節點
• 即使出現連鎖更新，只要被更新的節點不多，就不會對性能造成太大影響

　　壓縮串列API　　

標籤：其他

上一篇：第五章 索引與演算法（學習筆記）

下一篇：第二章 物件