Redis數據結構總結

2020 年 1 月 16 日
筆記

Redis數據結構總結

字元串（string）

字元串 string 是 Redis 最簡單的數據結構。Redis 所有的數據結構都是以唯一的 key 字元串作為名稱，然後通過這個唯一 key 值來獲取相應的 value 數據。不同類型的數據結構的差異就在於 value 的結構不一樣。

字元串結構使用非常廣泛，一個常見的用途就是快取用戶資訊。我們將用戶資訊結構體使用 JSON 序列化成字元串，然後將序列化後的字元串塞進 Redis 來快取。同樣，取用戶資訊會經過一次反序列化的過程。

Redis 的字元串是動態字元串，是可以修改的字元串，內部結構實現上類似於 Java 的 ArrayList，採用預分配冗餘空間的方式來減少記憶體的頻繁分配，如圖中所示，內部為當前字元串實際分配的空間 capacity 一般要高於實際字元串長度 len。當字元串長度小於 1M 時，擴容都是加倍現有的空間，如果超過 1M，擴容時一次只會多擴 1M 的空間。需要注意的是字元串最大長度為 512M。

鍵值對

set name codehole OK get name 「codehole」 exists name (integer) 1 del name (integer) 1 get name (nil)

批量鍵值對

利用mget 可以批量對多個字元串進行讀寫，節省網路耗時開銷。

set name1 codehole OK set name2 holycoder OK mget name1 name2 name3 # 返回一個列表

「codehole」
「holycoder」
(nil) mset name1 boy name2 girl name3 unknown mget name1 name2 name3
「boy」
「girl」
「unknown」…

過期和 set 命令擴展

可以對 key 設置過期時間，到點自動刪除，這個功能常用來控制快取的失效時間。

set name codehole get name 「codehole」 expire name 5 # 5s 後過期 … # wait for 5s get name (nil)
setex name 5 codehole # 5s 後過期，等價於 set+expire get name 「codehole」 … # wait for 5s get name (nil)
setnx name codehole # 如果 name 不存在就執行 set 創建 (integer) 1 get name 「codehole」 setnx name holycoder (integer) 0 # 因為 name 已經存在，所以 set 創建不成功 get name 「codehole」 # 沒有改變…

計數

如果 value 值是一個整數，還可以對它進行自增操作。自增是有範圍的，它的範圍是 signed long 的最大最小值，超過了這個值，Redis 會報錯。

set age 30 OK incr age (integer) 31 incrby age 5 (integer) 36 incrby age -5 (integer) 31 set codehole 9223372036854775807 # Long.Max OK incr codehole (error) ERR increment or decrement would overflow…

incr在原來的基礎上增加1，incrby是在原來的基礎上增加n

字元串是由多個位元組組成，每個位元組又是由 8 個 bit 組成，如此便可以將一個字元串看成很多 bit 的組合，這便是 bitmap「點陣圖」數據結構，點陣圖的具體使用會放到後面的章節來講。

list (列表)

Redis 的列表相當於 Java 語言裡面的 LinkedList，注意它是鏈表而不是數組。這意味著 list 的插入和刪除操作非常快，時間複雜度為 O(1)，但是索引定位很慢，時間複雜度為 O(n)，這點讓人非常意外。當列表彈出了最後一個元素之後，該數據結構自動被刪除，記憶體被回收。

Redis 的列表結構常用來做非同步隊列使用。將需要延後處理的任務結構體序列化成字元串塞進 Redis 的列表，另一個執行緒從這個列表中輪詢數據進行處理。

右邊進左邊出：隊列

rpush books python java golang (integer) 3 llen books (integer) 3 lpop books 「python」 lpop books 「java」 lpop books 「golang」 lpop books (nil)…

右邊進右邊出：棧

rpush books python java golang (integer) 3 rpop books 「golang」 rpop books 「java」 rpop books 「python」 rpop books (nil)…

慢操作

lindex 相當於 Java 鏈表的get(int index)方法，它需要對鏈表進行遍歷，性能隨著參數index增大而變差。 ltrim 和字面上的含義不太一樣，個人覺得它叫 lretain(保留) 更合適一些，因為 ltrim 跟的兩個參數start_index和end_index定義了一個區間，在這個區間內的值，ltrim 要保留，區間之外統統砍掉。我們可以通過ltrim來實現一個定長的鏈表，這一點非常有用。 index 可以為負數，index=-1表示倒數第一個元素，同樣index=-2表示倒數第二個元素。

rpush books python java golang (integer) 3 lindex books 1 # O(n) 慎用「java」 lrange books 0 -1 # 獲取所有元素，O(n) 慎用

「python」
「java」
「golang」 ltrim books 1 -1 # O(n) 慎用 OK lrange books 0 -1
「java」
「golang」 ltrim books 1 0 # 這其實是清空了整個列表，因為區間範圍長度為負 OK llen books (integer) 0…

需要注意，當ltrim參數的區間範圍長度為負數，會清空整個列表

快速列表

如果再深入一點，你會發現 Redis 底層存儲的還不是一個簡單的 linkedlist，而是稱之為快速鏈表 quicklist 的一個結構。首先在列表元素較少的情況下會使用一塊連續的記憶體存儲，這個結構是 ziplist，也即是壓縮列表。它將所有的元素緊挨著一起存儲，分配的是一塊連續的記憶體。當數據量比較多的時候才會改成 quicklist。因為普通的鏈表需要的附加指針空間太大，會比較浪費空間，而且會加重記憶體的碎片化。比如這個列表裡存的只是 int 類型的數據，結構上還需要兩個額外的指針 prev 和 next 。所以 Redis 將鏈表和 ziplist 結合起來組成了 quicklist。也就是將多個 ziplist 使用雙向指針串起來使用。這樣既滿足了快速的插入刪除性能，又不會出現太大的空間冗餘。

hash (字典)

Redis 的字典相當於 Java 語言裡面的 HashMap，它是無序字典。內部實現結構上同 Java 的 HashMap 也是一致的，同樣的數組 + 鏈表二維結構。第一維 hash 的數組位置碰撞時，就會將碰撞的元素使用鏈表串接起來。

不同的是，Redis 的字典的值只能是字元串，另外它們 rehash 的方式不一樣，因為 Java 的 HashMap 在字典很大時，rehash 是個耗時的操作，需要一次性全部 rehash。Redis 為了高性能，不能堵塞服務，所以採用了漸進式 rehash 策略。

漸進式 rehash 會在 rehash 的同時，保留新舊兩個 hash 結構，查詢時會同時查詢兩個 hash 結構，然後在後續的定時任務中以及 hash 操作指令中，循序漸進地將舊 hash 的內容一點點遷移到新的 hash 結構中。當搬遷完成了，就會使用新的hash結構取而代之。當舊hash 移除了最後一個元素之後，該數據結構自動被刪除，記憶體被回收。

hash 結構也可以用來存儲用戶資訊，不同於字元串一次性需要全部序列化整個對象，hash 可以對用戶結構中的每個欄位單獨存儲。這樣當我們需要獲取用戶資訊時可以進行部分獲取。而以整個字元串的形式去保存用戶資訊的話就只能一次性全部讀取，這樣就會比較浪費網路流量。

hash 也有缺點，hash 結構的存儲消耗要高於單個字元串，到底該使用 hash 還是字元串，需要根據實際情況再三權衡。

hset books java 「think in java」 # 命令行的字元串如果包含空格，要用引號括起來 (integer) 1 hset books golang 「concurrency in go」 (integer) 1 hset books python 「python cookbook」 (integer) 1 hgetall books # entries()，key 和 value 間隔出現

「java」
「think in java」
「golang」
「concurrency in go」
「python」
「python cookbook」 hlen books (integer) 3 hget books java 「think in java」 hset books golang 「learning go programming」 # 因為是更新操作，所以返回 0 (integer) 0 hget books golang 「learning go programming」 hmset books java 「effective java」 python 「learning python」 golang 「modern golang programming」 # 批量 set OK…

同字元串對象一樣，hash 結構中的單個子 key 也可以進行計數，它對應的指令是 hincrby，和 incr 使用基本一樣。

hmset user age 1 「OK」 hincrby user age 2 // 增加2 (integer) 3 hmget user age 「3」

set (集合)

Redis 的集合相當於 Java 語言裡面的 HashSet，它內部的鍵值對是無序的唯一的。它的內部實現相當於一個特殊的字典，字典中所有的 value 都是一個值NULL。

當集合中最後一個元素移除之後，數據結構自動刪除，記憶體被回收。

set 結構可以用來存儲活動中獎的用戶 ID，因為有去重功能，可以保證同一個用戶不會中獎兩次。

sadd books python (integer) 1 sadd books python # 重複 (integer) 0 sadd books java golang (integer) 2 smembers books # 注意順序，和插入的並不一致，因為 set 是無序的

「java」
「python」
「golang」 sismember books java # 查詢某個 value 是否存在，相當於 contains(o) (integer) 1 sismember books rust (integer) 0 scard books # 獲取長度相當於 count() (integer) 3 spop books # 彈出一個「java」

zset (有序集合)

zset 可能是 Redis 提供的最為特色的數據結構，它也是在面試中面試官最愛問的數據結構。它類似於 Java 的 SortedSet 和 HashMap 的結合體，一方面它是一個 set，保證了內部 value 的唯一性，另一方面它可以給每個 value 賦予一個 score，代表這個 value 的排序權重。它的內部實現用的是一種叫做「跳躍列表」的數據結構。 zset 中最後一個 value 被移除後，數據結構自動刪除，記憶體被回收。

zset 可以用來存粉絲列表，value 值是粉絲的用戶 ID，score 是關注時間。我們可以對粉絲列表按關注時間進行排序。 zset 還可以用來存儲學生的成績，value 值是學生的 ID，score 是他的考試成績。我們可以對成績按分數進行排序就可以得到他的名次。

zadd books 9.0 「think in java」 (integer) 1 zadd books 8.9 「java concurrency」 (integer) 1 zadd books 8.6 「java cookbook」 (integer) 1 zrange books 0 -1 # 按 score 從小到大排序列出，參數區間為排名範圍

「java cookbook」
「java concurrency」
「think in java」 zrevrange books 0 -1 # 按 score 逆序列出，參數區間為排名範圍
「think in java」
「java concurrency」
「java cookbook」 zcard books # 相當於 count() (integer) 3 zscore books 「java concurrency」 # 獲取指定 value 的 score 「8.9000000000000004」 # 內部 score 使用 double 類型進行存儲，所以存在小數點精度問題 zrank books 「java concurrency」 # 排名 (integer) 1 zrangebyscore books 0 8.91 # 根據分值區間遍歷 zset
「java cookbook」
「java concurrency」 zrangebyscore books -inf 8.91 withscores # 根據分值區間 (-∞, 8.91] 遍歷 zset，同時返回分值。inf 代表 infinite，無窮大的意思。
「java cookbook」
「8.5999999999999996」
「java concurrency」
「8.9000000000000004」 zrem books 「java concurrency」 # 刪除 value (integer) 1 zrange books 0 -1
「java cookbook」
「think in java」

跳躍列表

zset 內部的排序功能是通過「跳躍列表」數據結構來實現的，它的結構非常特殊，也比較複雜。

因為 zset 要支援隨機的插入和刪除，所以它不好使用數組來表示。我們先看一個普通的鏈表結構。

我們需要這個鏈表按照 score 值進行排序。這意味著當有新元素需要插入時，要定位到特定位置的插入點，這樣才可以繼續保證鏈表是有序的。通常我們會通過二分查找來找到插入點，但是二分查找的對象必須是數組，只有數組才可以支援快速位置定位，鏈表做不到，那該怎麼辦？

想想一個創業公司，剛開始只有幾個人，團隊成員之間人人平等，都是聯合創始人。隨著公司的成長，人數漸漸變多，團隊溝通成本隨之增加。這時候就會引入組長制，對團隊進行劃分。每個團隊會有一個組長。開會的時候分團隊進行，多個組長之間還會有自己的會議安排。公司規模進一步擴展，需要再增加一個層級 —— 部門，每個部門會從組長列表中推選出一個代表來作為部長。部長們之間還會有自己的高層會議安排。跳躍列表就是類似於這種層級制，最下面一層所有的元素都會串起來。然後每隔幾個元素挑選出一個代表來，再將這幾個代表使用另外一級指針串起來。然後在這些代表里再挑出二級代表，再串起來。最終就形成了金字塔結構。想想你老家在世界地圖中的位置：亞洲–>中國->安徽省->安慶市->樅陽縣->湯溝鎮->田間村->xxxx號，也是這樣一個類似的結構。

「跳躍列表」之所以「跳躍」，是因為內部的元素可能「身兼數職」，比如上圖中間的這個元素，同時處於 L0、L1 和 L2 層，可以快速在不同層次之間進行「跳躍」。定位插入點時，先在頂層進行定位，然後下潛到下一級定位，一直下潛到最底層找到合適的位置，將新元素插進去。你也許會問，那新插入的元素如何才有機會「身兼數職」呢？跳躍列表採取一個隨機策略來決定新元素可以兼職到第幾層。首先 L0 層肯定是 100% 了，L1 層只有 50% 的概率，L2 層只有 25% 的概率，L3 層只有 12.5% 的概率，一直隨機到最頂層 L31 層。絕大多數元素都過不了幾層，只有極少數元素可以深入到頂層。列表中的元素越多，能夠深入的層次就越深，能進入到頂層的概率就會越大。這還挺公平的，能不能進入中央不是靠拼爹，而是看運氣。

容器型數據結構的通用規則

list/set/hash/zset 這四種數據結構是容器型數據結構，它們共享下面兩條通用規則： create if not exists 如果容器不存在，那就創建一個，再進行操作。比如 rpush 操作剛開始是沒有列表的，Redis 就會自動創建一個，然後再 rpush 進去新元素。 drop if no elements 如果容器里元素沒有了，那麼立即刪除元素，釋放記憶體。這意味著 lpop 操作到最後一個元素，列表就消失了。

過期時間

Redis 所有的數據結構都可以設置過期時間，時間到了，Redis 會自動刪除相應的對象。需要注意的是過期是以對象為單位，比如一個 hash 結構的過期是整個 hash 對象的過期，而不是其中的某個子 key。還有一個需要特別注意的地方是如果一個字元串已經設置了過期時間，然後你調用了 set 方法修改了它，它的過期時間會消失。

127.0.0.1:6379> set codehole yoyo  OK  127.0.0.1:6379> expire codehole 600  (integer) 1  127.0.0.1:6379> ttl codehole  (integer) 597  127.0.0.1:6379> set codehole yoyo  OK  127.0.0.1:6379> ttl codehole  (integer) -1

參考

《Redis深度歷險》

Tags: