Redis數據結構

• 2020 年 12 月 6 日
• 筆記
• NoSQL, Redis

Redis開發

API及底層實現

全局命令

keys *：查看所有的鍵 O(n)

dbsize：鍵總數 O(1)

exists key ：檢查鍵是否存在

del key：刪除鍵

expire key seconds：鍵過期

ttl : 返回鍵的剩餘時間 (

• >=0: 剩餘時間
• -1：沒設置過期時間
• -2：鍵不存在

)

type key：鍵的類型

object encoding：查詢內部編碼

數據結構和內部編碼：

每種數據結構都有兩種以上的內部編碼實現，好處：

1. 可以改進內部編碼，而對外的數據結構和命令沒有影響
2. 多種內部編碼實現可以在不同場景下發揮各自的優勢

單線程架構

為什麼單線程還能這麼快？

1. 純內存訪問
2. 非阻塞I/O，redis使用epoll作為I/O多路復用技術的實現
3. 單線程避免了線程切換和競態產生的消耗

缺點：如果某個命令執行時間過長，會造成其他命令的阻塞。

字符串

字符串類型的值可以是普通字符串，也可以是複雜字符串（Json, Xml）, 數字（整數、浮點數），二進制的圖片、音頻、視頻，但值最大不能超過512MB

字符串api

1. set key value [ex seconds] [px milliseconds] [nx | xx]

   • ex seconds : 為鍵設置秒級過期時間
   • px milliseconds : 為鍵設置毫秒級過期時間
   • nx : 鍵不存在才設置成功，用於添加
   • xx : 鍵存在才設置成功，用於更新

2. get key

3. mset key value [key value ……]

4. mget key [key……]

5. incr key 自增

   • 值不是整數，返回錯誤
   • 值是整數，返回自增後的結果
   • 鍵不存在，按照值為0自增，返回結果為1

6. decr、incrby(自增指定數字)、decrby、incrbyfloat

7. append key value 向字符串尾部追加值

8. strlen key 字符串長度

   每個中文佔用3個位元組

9. getset key value 設置並返回原值

10. setrange key offset value 設置指定位置的字符

11. getrange key start end 獲取部分字符串，下標從0開始，包括右下標

字符串內部編碼

有3種編碼：

• int：8個位元組的長整型
• embstr：小於等於39個位元組的字符串
• raw：大於39個位元組的字符串

通過object encoding key 查看內部編碼

使用場景

• 緩存功能
• 計數：視頻播放數
• 共享session：出於分佈式服務考慮，已不適用
• 限速：防盜刷

哈希

api

• hset key field value 設置值
• hget key field 獲取值
• hdel key field 刪除filed
• hlen key 計算field的個數
• hmget key field [filed ……]
• hmset key filed value ……
• hexists key field 判斷field是否存在
• hkeys key 獲取所有field
• hvals key 獲取所有value
• hgetall key 獲取所有的f-v，如果個數過多，會造成阻塞
• hincrby key field
• hincrbyfloat key field
• hstrlen key field 計算value的長度

內部編碼

有2種：

ziplist (壓縮列表)：當元素個數小於hash-max-ziplist-entries配置（默認512個）、同時所有值都小於hash-max-ziplist-value配置（默認64位元組），redis使用ziplist作為內部編碼。ziplist 使用緊湊的結構實現多個元素的連續存儲，在節省內存方面比hashtable更加好。

hashtable (哈希表)：當上述條件無法滿足時，redis使用hashtable，因為此時ziplist 的讀寫效率會下降，而hashtable 的讀寫時間複雜度為O(1)

使用場景

緩存：用戶的id作為鍵後綴，多對f-v對應每個用戶的屬性

列表

一個列表最多可以存儲2³²-1 個元素，列表中的元素是有序的且可以重複的

api

lpush key value 從左插入元素

rpush key value 從右插入元素

lrange 0 -1 從左到右獲取列表中的所有元素

linsert key before | after pivot value 從列表中找到等於pivot的元素，插入

lrange key start end 獲取指定索引範圍的所有元素，索引下標：從左到右是0 – N-1，從右到左是-1 – -N；lrange中的end元素包括自身。

lindex key index 獲取指定索引下標

llen key 獲取列表長度

lpop key 從左彈出元素

lrem key count value

• count > 0, 從左到右，最多刪除count個value值的元素
• count < 0, 從右到左，最多刪除count絕對值的元素
• count = 0，刪除所有。

ltrim key start end 按照索引範圍剪列表

lset key index newValue 修改指定索引下標的元素

blpop/brpop key timeout 阻塞彈出

• key 可以多個

• timeout 如果列表為空，則等待timeout時間返回。timeout = 0時，則一直等待。

• 如果列表不為空，立即返回

  注意：

  • 如果有多個鍵，則從左到右遍歷鍵，有一個鍵可以返回就立即返回。
  • 如果多個客戶端對同一個鍵執行blpop，則最先執行命令的客戶端返回，其他客戶端阻塞。

內部編碼

ziplist：當列表元素個數小於list – max – ziplist – entries（默認512個），同時列表中每個元素的值小於list – max – ziplist – values（默認64位元組)

linkedlist：無法滿足ziplist條件，則用linkedlist

使用場景

• 消息隊列：用rpush + blpop 實現阻塞隊列。多個消費者客戶端使用blpop阻塞「搶」列表尾部元素，多個客戶端保證了消費的負載均衡和高可用性。
• 文章列表：每個用戶有自己的文章列表，需要分頁展示文章列表
  • rpush user:1:articles 文章
  • lrange user:1:articles 0 9 （ps：取出前10條）

集合

集合不允許有重複元素，且元素是無序的，不能通過索引獲取。

api

sadd key element[…] 添加元素

srem key element[…] 刪除元素

scard key 計算元素個數

sismember key element 判斷元素是否在集合中，返回1存在，0不存在

srandmember key 【count】 隨機返回集合中指定個數的元素

spop key 隨機彈出

smembers key 獲取所有元素，可能會造成阻塞

sinter key [key…] 求交集

sunion key [key…] 求並集

sdiff key [key…] 求差集

sinterstore / sunionstore / sdiffstore destination key [key…] 求結果並保存

內部編碼

intset（整數集合）：元素都是整數並且元素個數小於 set – max – intset – entries (默認512個)，減少內存的使用

hashtable（哈希表）：無法滿足上述，則用hashtable

使用場景

• 標籤：比如用戶對娛樂、體育、歷史等比較感興趣，可以得到喜歡同一個標籤的人，以及用戶的共同喜好標籤。
  • 給用戶添加標籤和給標籤添加用戶，需要在一個事務中進行
  • 刪除用戶下的標籤和刪除標籤下的用戶，也需要在一個事務中進行
  • 計算用戶共同感興趣的標籤：sinter user:1:tage user2:tag
• 抽獎

有序集合

沒有重複元素，給每個元素設置一個分數，作為排序的依據；提供了獲取指定元素分數和元素範圍查詢、計算成員排名等功能

api

zadd key score member [….] 添加成員

zcard key 計算成員個數

zscore key memeber 計算某個成員分數

zrank key memeber 從低到高排名

zrevrank key member 從高到底排名

zrem key member [….] 刪除成員

zincrby key increment member 增加成員分數

zrange key start end [withscores] 返回指定排名範圍成員

zrevrange key start end [withscores] 返回指定排名範圍成員

zrangebyscore key min max 返回指定分數範圍成員

zcount key min max 返回指定分數範圍成員個數

zremrangebyrank key start end 刪除指定排名範圍內的元素

zremrangebyscore key min max 刪除指定分數範圍內的元素

zinterstore destination numkeys key [key…] [weights [weight …]] [aggregate sum|min|max] 求交集

• destination ： 保存到目標集合
• numkeys ：鍵的個數
• weights：每個鍵的權重，默認是1
• aggregate ：聚合運算，默認是sum

zunionstore……

內部編碼

ziplist：元素個數小於zset – max – ziplist – entries（默認128個），值小於zset – max – ziplist – value（默認64位元組）

skiplist：不滿足上述條件

使用場景

• 排行榜：比如對用戶上傳的視頻做排行榜，可以按照時間、播放量、贊數排行。

  比如贊數：

  • 添加用戶贊數

    zadd …

    之後再獲得一個贊：zincrby ….

  • 取消用戶贊數

    zrem …

  • 展示獲取贊數最多的10個用戶

    zrevrangebyrank …

壓縮列表底層實現

壓縮列表是列表鍵和哈希鍵的底層實現之一，鍵值要麼是小整數值，要麼是短字符串

壓縮列表是為了節約內存，是由一系列特殊編碼的連續內存塊組成的順序型數據結構，一個壓縮列表可以包含任意多個節點（entry)，每個節點可以保存一個位元組數組或者一個整數值

壓縮列表組成：

節點組成：

每個節點可以保存一個位元組數組或一個整數值：

位元組數組：

• 長度小於等於2⁶ – 1的位元組數組
• 小於等於2¹⁴ – 1
• 小於等於2³² – 1

整數值：

• 4位長，0-12的無符號整數
• 1位元組長的有符號整數
• 3位元組長的有符號整數
• int16_t 類型整數
• int32_t 類型整數
• int64_t 類型整數

previous_entry_length：以位元組為單位，可以是1位元組或5位元組，記錄前一個節點的長度

• 如果前一個節點的長度小於254位元組，該值為1位元組

• 如果前一個節點的長度大於等於254位元組，該值為5位元組，第一位元組會被設置為0xFE(254)，後4個位元組表示前一節點的長度

  作用：可以根據當前節點的起始地址計算前一節點的起始地址，壓縮列表從表尾到表頭的遍歷操作就是這樣實現的。

encoding：記錄content屬性保存的數據類型及長度

• 位元組數組：1位元組、2位元組或5位元組長，值最高位為00，01或者10

  編碼	編碼長度	content屬性保存的值
  00bbbbbbb	1位元組	長度小於等於26 – 1位元組的位元組數組
  01bbbbbbb xxxxxxxx	2位元組	長度小於等於214 – 1位元組的位元組數組
  10___ aaa……	5位元組	長度小於等於232 – 1位元組的位元組數組

• 整數：1位元組長，值的最高位以11開頭

  編碼	編碼長度	content屬性保存的值
  11000000	1位元組	int16_t類型的整數
  11010000	1位元組	int32_t類型的整數
  11100000	1位元組	int64_t類型的整數
  11110000	1位元組	1位元組
  11111110	1位元組	8位有符號整數
  1111xxxx	1位元組	沒有content屬性，本身包含了0-12的值

content：負責保存節點的值，節點值可以是一個整數或位元組數組

連鎖更新：壓縮列表恰有好多個連續的、長度介於250位元組至253位元組的節點，當添加一個長度大於等於254位元組的節點時，可能會導致後續的節點的previous_entry_length屬性從1位元組擴展為5位元組。刪除節點也可能產生更新。時間複雜度O(n²)

整數集合底層實現

整數集合是集合鍵的底層實現之一，集合只包含整數值元素並且元素數量不多。

encoding：contents數組中存儲值的類型

• int16_t
• int32_t
• int64_t

length：集合包含的元素個數

contents：按照從小到大的順序保存元素

升級：當添加一個新元素到整數集合時，並且新元素的類型比整數集合中所有元素類型都要長時，要先進行升級，然後才將新元素添加到整數集合中。

​ 升級整數集合的三步驟：

• 根據新元素的類型，擴展整數集合底層數組的空間大小，並為新元素分配空間

• 將底層數組現有的所有元素都轉換成與新元素相同的類型，然後將元素放到正確的位置上，需要維持底層數組的有序性

• 將新元素添加到底層數組

  每次升級都需要對底層數組的元素進行類型轉換，因此向整數集合添加新元素的時間複雜度為O(N)

升級後新元素的位置：

​ 引發升級的新元素的長度總是比整數集合所有的元素長度大，

• 新元素小於所有現有元素時，新元素會被放置在底層數組的最開頭
• 新元素大於所有現有元素時，新元素會被放置在底層數組的最末尾

升級的好處：提升整數集合的靈活性，儘可能節約內存

​ 提升靈活性：整數集合通過自動升級底層數組來適應新元素，因此可以隨意將不同類型的整數添加到集合中，靈活性較好。

​ 節約內存：整數集合既能保存三種不同類型的值，又能確保升級操作只會在有需要的時候進行，可以盡量節省內存。

整數集合不支持降級，一旦升級，就會一直保持升級後的狀態

跳躍表底層實現

跳錶是一種有序的數據結構，通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的

跳錶是有序集合鍵的底層實現之一，當有序集合中包含的元素個數較多或者元素的成員是比較長的字符串時

redis用到跳錶的地方：有序集合鍵、集群節點的內部數據結構

​ 表頭節點的結構：表頭節點也有後退指針、分值和成員對象

• header：指向跳躍表的表頭節點
• tail：指向跳躍表的表尾節點
• level：記錄目前跳躍表內，層數最大的那個節點的層數（表頭節點的層數不計）
• length：跳躍表的長度

​ 跳錶節點的結構：

• level數組：level數組可以包含多個元素，每個元素都包含前進指針和跨度。

  ​ 前進指針用於從表頭向表尾訪問其他節點，跨度則記錄了前進指針所指向節點和當前節點的距離。

  ​ 層的數量越多，訪問其他節點的速度就更快。

  ​ 每次創建一個新節點時，會隨機生成一個1-32之間的值作為level數組的大小。

  ​ 跨度實際上是用來排位的，而不是遍歷：在查找某個節點的過程中，將沿途訪問過的所有層的跨度累計得到的結 果就是目標節點在跳錶中的排位。

• 後退指針：指向位於當前節點的前一個節點，可以用於從表尾向表頭遍歷時使用，每次只能後退至前一個節點

• 分值：在跳錶中，節點按各自所保存的分值從小到大排列

• 成員對象：節點所保存的成員對象

  各個節點保存的成員對象必須是唯一的，但是多個節點保存的分值可以是相同的，如果分值相同，則按照成員對象的字典序來排序，較小的排前面。

字典底層實現

Redis數據庫使用字典作為底層實現，字典也是哈希鍵的底層實現之一，當包含的鍵值對比較多或者鍵值對中的元素都是比較長的字符串時

字典組成：

• type：一個指向dictType結構的指針，每個dictType保存了一組用於操作特定類型鍵值對的函數

  dictType包含的函數：計算hash值；複製鍵；複製值；銷毀鍵；銷毀值；對比鍵

• privdata：傳給函數的可選參數

• ht：包含兩個項的數組，每個項都是一個哈希表，一般只是用ht[0]，ht[1]只會在對ht[0]哈希表進行rehash使用

• rehashidx：rehash索引，記錄當前rehash的進度，如果當前沒有進行rehash，值為-1

哈希表組成：

• table：哈希數組，數組中的每一個元素指向一個entry結構，每個entry保存一個鍵值對
• size：數組的大小
• sizemask：等於size – 1，用hash值&sizemask算出鍵應該放在哪個索引上
• used：目前哈希表的鍵值對數量

哈希表節點組成：

• key：鍵
• v：值，可以是一個指針或者uint64_t或者是int64_t
• next：指向另一個節點的指針，將多個哈希值相同的鍵值對連接起來

哈希算法：

使用MurmurHash2算法，調用type中的計算哈希值的函數算出hash，然後和sizemask進行按位&運算

鍵衝突：

採用鏈地址法，為了速度考慮，採用頭插法，總是將新節點添加到鏈表的表頭

rehash：

當保存的鍵值對太多或太少，需要通過rehash對哈希表的大小進行相應的擴展或者收縮，讓負載因子維持在一個合理範圍內。

rehash步驟：

• 為哈希表ht[1] 分配空間，空間的大小取決於要執行的操作以及ht[0]當前包含的鍵值對數量：
  • 如果是擴展操作，ht[1] 大小為第一個大於等於ht[0].used * 2 的 2ⁿ
  • 如果是收縮操作，ht[1] 大小為第一個大於等於ht[0].used 的 2ⁿ
• 將ht[0] 的所有鍵值對rehash到ht[1]
• 當ht[0] 的所有鍵值對遷移到ht[1]後，釋放ht[0]，將ht[1] 設置為ht[0]，並為ht[1] 新建一個空白的哈希表，為下一次rehash做準備

哈希表的擴展與收縮：

擴展：

• 當前沒有在執行 BGSAVE 或 BGREWRITEAOF ，並且負載因子大於等於1

• 當前有在執行 BGSAVE 或 BGREWRITEAOF，並且負載因子大於等於5

  負載因子 = （哈希表已保存的節點數量）/ 哈希表大小

  在執行BGSAVE 或 BGREWRITEAOF 時，需要創建子進程，大多數操作系統都是採用寫時複製來優化子進程使用效率，所以在子進程存在期間，提高執行擴展所需負載因子，避免子進程存在期間進行擴展操作，避免不必要的內存寫入，最大限度節約內存。

收縮：負載因子小於0.1時，執行收縮操作。

漸進式rehash:

rehash並不是一次性完成，而是分多次、漸進式完成，如果鍵值對數量比較多，要一次性將全部鍵值對rehash到ht[1]，可能會導致服務器在一段時間內停止服務

rehash步驟：

• 為ht[1] 分配空間
• 維持索引計數器rehashidx，並將值設為0，表示rehash開始
• rehash期間，每次對字典執行增刪改查時，順帶將ht[0] 在rehashidx 索引上的所有鍵值對rehash到ht[1]，rehash完成後，rehashidx加1
• 當ht[0] 全部的鍵值對rehash完成後，將rehashidx設置為-1，表示完成

rehash期間操作：

• 增：新添加操作只被保存到ht[1]，ht[0]不再進行任何添加操作，保證ht[0]鍵值對的數量只增不減，最終變成空表
• 刪、改、查：先在ht[0]里進行，如果沒有操作成功，再到ht[1]進行。

鏈表底層實現

鏈表是列表鍵的底層實現之一，除此之外，發佈與訂閱、慢查詢、監視器等功能也用到了鏈表，Redis本身也使用了鏈表保存多個客戶端的狀態信息

鏈表組成：

• head：表頭節點
• tail：表尾節點
• len：節點的數量
• dup：複製鏈表節點所保存的值
• free：釋放鏈表節點所保存的值
• mathch：對比鏈表節點所保存的值和另一個輸入值是否相等

節點組成：

• prev：前驅節點
• next：後置節點
• value：節點的值

特性：

• 雙向無環鏈表
• 帶表頭和表尾指針
• 帶鏈表長度計數器
• 多態

簡單動態字符串

Redis中，C字符串只會作為字符串字面量，用在一些無須對字符串值進行修改的地方，比如打印日誌

字符串值的鍵值對都是SDS實現的，SDS還可以被用作緩衝區：AOF緩衝區、客戶端輸入緩衝區

• len：字符串的長度

• free：未使用的位元組數量

• buf：位元組數組，用於保存字符串

  SDS遵循C字符串以空字符結尾的慣例，空字符的1位元組空間不計算在len中，好處：可以直接重用一部分C字符串函數。

SDS與C字符串的區別：

• 常數複雜度獲取字符串長度

  C字符串不記錄自身的長度，要獲取長度，必須遍歷，O(N)；SDS只要反問len屬性就可以知道長度，即使對一個非常長的字符串鍵反覆執行獲取長度的命令，也不會對系統造成任何影響。

• 杜絕緩衝區溢出

  C字符串如果沒有分配足夠的內存空間，在執行修改字符串時可能會溢出。SDS杜絕了緩衝區溢出的可能性：當SDS修改時，會先檢查SDS空間是否滿足修改所需的要求，不滿足自動將SDS擴展至執行修改所需的大小，然後執行實際修改操作。

• 減少修改字符串時的內存重分配次數

  每次增長或縮短一個C字符串，都要進行一次內存重分配操作：

  • 如果是增長操作，需要先通過內存重分配來擴展底層數組，忘了這一步會產生緩衝區溢出

  • 如果是縮短操作，需要先通過內存重分配來釋放不再使用的空間，忘 了這一步會產生內存泄漏

    內存重分配是一個耗時的操作，如果每次修改字符串都要進行內存重分配，在修改頻繁的情況下，會對性能造成影響。

  SDS的空間預分配和惰性空間兩種優化策略：

  1. 空間預分配：每次修改並需要對SDS進行擴展時，除了分配修改所需要的空間，還需要分配額外未使用的空間

     • 如果修改之後，SDS的長度小於1MB，將分配和len屬性同樣大小的未使用空間，這時buf實際長度等於len位元組+free位元組+1位元組

     • 如果修改之後，SDS的長度大於等於1MB，將分配1MB未使用空間，buf實際長度等於lenMB+1MB+1位元組

       通過空間預分配，可以減少連續執行字符串增長操作所需的內存重分配次數，和C字符串對比，將連續增長N次所需的內存重分配次數從必定的N次降低為最多N次

  2. 惰性空間釋放：優化縮短SDS操作，需要縮短SDS時，不是立即用內存重分配來回收縮短後多出來的位元組，而是使用free記錄這些位元組的數量，並等待將來使用。

     通過惰性空間釋放，SDS避免了縮短字符串所需的內存重分配操作，並為將來可能有的增長操作提供了優化

• 二進制安全

  C字符串除了字符串末尾的空字符外，裏面不能包含空字符，使得只能保存文本數據，不能保存圖片、音頻、視頻等二進制文件。

  SDS的buf屬性是保存二進制數據，SDS會以處理二進制的方式處理buf數組，數據寫入時什麼樣，讀出時就什麼樣。

• 重用部分C字符串函數

  SDS遵循C字符串以空字符結尾，可以讓保存文本數據的SDS重用一部分C字符串函數。