這是一個系列的文章抡笼，打算把Redis的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)锚贱、高級數(shù)據(jù)結(jié)構(gòu)、持久化的方式以及高可用的方式都講一遍吆寨，公眾號會比其他的平臺提前更新赏淌，感興趣的可以提前關(guān)注，「SH的全棧筆記」啄清，下面開始正文六水。

如果你是一個有經(jīng)驗的后端或者服務(wù)器開發(fā)，那么一定聽說過Redis辣卒，其全稱叫Remote Dictionary Server掷贾。是由C語言編寫的基于Key-Value的存儲系統(tǒng)。說直白點就是一個內(nèi)存數(shù)據(jù)庫荣茫，既然是內(nèi)存數(shù)據(jù)庫就會遇到如果服務(wù)器意外宕機造成的數(shù)據(jù)不一致的問題想帅。

這跟很多游戲服務(wù)器也是一樣的，感興趣的可以參考我之前的文章游戲服務(wù)器和Web服務(wù)器的區(qū)別计露。其數(shù)據(jù)首先會流向內(nèi)存博脑，基于快速的內(nèi)存讀寫來實現(xiàn)高性能，然后定期將內(nèi)存的數(shù)據(jù)中的數(shù)據(jù)落地票罐。Redis其實也是這么個流程叉趣，基于快速的內(nèi)存讀寫操作，單機的Redis甚至能夠扛住10萬的QPS该押。

Redis除了高性能之外疗杉，還擁有豐富的數(shù)據(jù)結(jié)構(gòu)，支持大多數(shù)的業(yè)務(wù)場景蚕礼。這也是其為什么如此受歡迎的原因之一烟具，下面我們就來看一看Redis有哪些基礎(chǔ)數(shù)據(jù)類型，以及他們底層都是怎么實現(xiàn)的奠蹬。

1. 數(shù)據(jù)類型

其基礎(chǔ)數(shù)據(jù)類型有String朝聋、List、Hash囤躁、Set冀痕、Sorted Set，這些都是常用的基礎(chǔ)數(shù)據(jù)類型狸演，可以看到非常豐富言蛇，幾乎能夠滿足大部分的需求了。其實還有一些高級數(shù)據(jù)結(jié)構(gòu)宵距，我們在這章里暫時先不提腊尚，只聊基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。

2. String

String可以說是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了满哪， 用法上可以直接和Java中的String掛鉤婿斥，你可以把String類型用于存儲某個標(biāo)志位劝篷，某個計數(shù)器，甚至狠一點受扳，序列化之后的JSON字符串都行携龟，其單個key限制為512M兔跌。其常見的命令為get勘高、set、incr坟桅、decr 华望、mget。

2.1 使用

• get 獲取某個key仅乓，如果key不存在會返回空指針
• set 給key賦值赖舟，將key設(shè)置為指定的值，如果該key之前已經(jīng)有值了夸楣，那么將被新的值給覆蓋
• incr 給當(dāng)前的key的值+1宾抓，如果key不存在則會先給key調(diào)用set賦值為0，再調(diào)用incr豫喧。當(dāng)然如果該key的類型不能做加法運算石洗，例如字符串，就會拋出錯誤
• decr 給當(dāng)前key的值-1紧显，其余的同上
• mget 同get讲衫，只是一次性返回多條數(shù)據(jù)，不存在的key將會返回空指針

string相關(guān)命令

可能大多數(shù)的人只是到用一用的地步孵班，這也無可厚非涉兽，但是如果是作為一個對技術(shù)有追求的開發(fā)，或者說你有想近大廠的想法篙程，一定要有刨根問底的精神枷畏。只有當(dāng)你真正知道一個東西的底層原理時，你遇到問題時才能提供給你更多的思路去解決問題虱饿。接下來我們就來聊一下Redis中String底層是如何實現(xiàn)的拥诡。

2.2 原理

2.2.1 結(jié)構(gòu)

我們知道Redis是用C語言寫的，但是Redis卻沒有直接使用郭厌，而是自己實現(xiàn)了一個叫SDS（Simple Dynamic String）的結(jié)構(gòu)來實現(xiàn)字符串袋倔，結(jié)構(gòu)如下。

struct sdshdr {
  // 記錄buf中已使用的字節(jié)數(shù)量
  int len;
  // 記錄buf中未使用的字節(jié)數(shù)量
  int free;
  // 字節(jié)數(shù)組折柠，用于保存字符串
  char buf[];
}

2.2.2 優(yōu)點

為什么Redis要自己實現(xiàn)SDS而不是直接用C的字符串呢宾娜？主要是因為以下幾點。

• 減少獲取字符串長度開銷 C語言中獲取字符串的長度需要遍歷整個字符串扇售，直到遇到結(jié)束標(biāo)志位\0前塔，時間復(fù)雜度為O(n)嚣艇，而SDS直接維護了長度的變量，取長度的時間復(fù)雜度為O(1)
• 避免緩沖區(qū)溢出 C語言中如果往一個字節(jié)數(shù)組中塞入超過其容量的字節(jié)华弓，那么就會造成緩沖區(qū)溢出食零，而SDS通過維護free變量解決了這個問題。向buf數(shù)組中寫入數(shù)據(jù)時寂屏，會先判斷剩余的空間是否足夠塞入新數(shù)據(jù)贰谣，如果不夠，SDS就會重新分配緩沖區(qū)迁霎，加大之前的緩沖區(qū)吱抚。且加大的長度等于新增的數(shù)據(jù)的長度
• 空間預(yù)分配&空間惰性釋放 C語言中，每次修改字符串都會重新分配內(nèi)存空間考廉，如果對字符串修改了n次秘豹，那么必然會出現(xiàn)n次內(nèi)存重新分配。而SDS由于冗余了一部分空間昌粤，優(yōu)化了這個問題既绕，將必然重新分配n次變?yōu)?strong>最多分配n次，而數(shù)據(jù)從buf中移除的時候涮坐，空閑出來的內(nèi)存也不會馬上被回收凄贩，防止新寫入數(shù)據(jù)而造成內(nèi)存重新分配
• 保證二進制安全 C語言中，字符串遇到\0會被截斷膊升，而SDS不會因為數(shù)據(jù)中出現(xiàn)了\0而截斷字符串怎炊，換句話說，不會因為一些特殊的字符影響實際的運算結(jié)果

可以結(jié)合下面的圖來理解SDS廓译。

圖片來源于網(wǎng)絡(luò)评肆，侵刪

總結(jié)一下就是上面列表的四個小標(biāo)題，為了減少獲取字符串長度開銷非区、避免緩沖區(qū)溢出瓜挽、空間預(yù)分配&空間惰性釋放和保證二進制安全。

3. List

List也是一個使用頻率很高的數(shù)據(jù)結(jié)構(gòu)征绸，其設(shè)計到的命令太多了久橙，就不像String那樣一個一個演示了，感興趣的大家可以去搜一搜管怠。命令有l(wèi)push淆衷、lpushx、rpush渤弛、rpushx祝拯、lpop、rpop、lindex佳头、linsert鹰贵、lrange、llen康嘉、lrem碉输、lset、ltrim亭珍、rpoplpush敷钾、brpoplpush、blpop块蚌、brpop闰非，其都是對數(shù)組中的元素的操作膘格。

3.1 使用

List的用途我認(rèn)為主要集中在以下兩個方面峭范。

1. 當(dāng)作普通列表存儲數(shù)據(jù)（類似于Java的ArrayList）
2. 用做異步隊列

普通列表這個自然不必多說，其中存放的必然業(yè)務(wù)中需要的數(shù)據(jù)瘪贱，下面來著重聊一下異步隊列纱控。

啥玩意，List還能當(dāng)成隊列來玩菜秦？

List除了能被用做隊列甜害，還能當(dāng)作棧來使用。在上面介紹了很多操作List命令球昨，當(dāng)我們用rpush/lpop組合命令的時候尔店，實際上就是在使用一個隊列，而當(dāng)我們用rpush/rpop命令組合的時候主慰，就是在使用一個棧嚣州。lpush/rpop和lpush/lpop是同理的。

假設(shè)我們用的是rpush來生產(chǎn)消息共螺，當(dāng)我們的程序需要消費消息的時候该肴，就使用lpop從異步隊列中消費消息。但是如果采用這種方式藐不，當(dāng)隊列為空時匀哄，你可能需要不停的去詢問隊列中是否有數(shù)據(jù)吻氧，這樣會造成機器的CPU資源的浪費墨辛。

所以你可以采取讓當(dāng)前線程Sleep一段時間作烟，這樣的確可以節(jié)省一部分CPU資源拦惋。但是你可能就需要去考慮Sleep的時間痛垛，間隔太短丑搔，CPU上下文切換可能也是一筆不小的開銷奏瞬，間隔太長侄刽，那么可能造成這條消息被延遲消費（不過都用異步隊列了衷模，應(yīng)該可以忽略這個問題）鹊汛。

除了Sleep蒲赂，還有沒有其他的方式？

有刁憋，答案是blpop滥嘴。當(dāng)我們使用blpop去消費時，如果當(dāng)前隊列是空的至耻，那么此時線程會阻塞住若皱，直到下面兩種condition。

1. 達到設(shè)置的timeout時間
2. 隊列中有消息可以被消費

比起Sleep一段時間尘颓，實時性會好一點走触；比起輪詢，對CPU資源更加友好疤苹。

3.2 原理

在Redis3.2之前互广，Redis采用的是ZipList（壓縮列表）或者LinkedList（鏈表）。當(dāng)List中的元素同時滿足每個元素的小于64字節(jié)和List元素個數(shù)小于512個時卧土，存儲的方式為ZipList惫皱。但凡有一個條件沒滿足就會轉(zhuǎn)換為LinkedList。

而在3.2之后尤莺，其實現(xiàn)變成了QuickList（快速列表）旅敷。LinkedList由于是較為基礎(chǔ)的東西，此處就不贅述了颤霎。

3.2.1 ZipList

ZipList采用連續(xù)的內(nèi)存緊湊存儲媳谁，不像鏈表那樣需要有額外的空間來存儲前驅(qū)節(jié)點和后續(xù)節(jié)點的指針。按照其存儲的區(qū)域劃分友酱，大致可以分為三個部分晴音，每個部分也有自己的劃分，其詳細(xì)的結(jié)構(gòu)如下粹污。

• header ziplist的頭部信息
  • zlbytes 標(biāo)識ziplist所占用的內(nèi)存字節(jié)數(shù)
  • zltail 到ziplist尾節(jié)點的偏移量
  • zllen ziplist中的存儲的節(jié)點數(shù)量
• entries 存儲實際節(jié)點的信息
  • pre_entry_length 記錄了前一個節(jié)點的長度段多，通過這個值可以快速的跳轉(zhuǎn)到上一個節(jié)點
  • encoding 顧名思義，存儲量元素的編碼格式
  • length 所存儲數(shù)據(jù)的長度
  • content 保存節(jié)點的內(nèi)容
• end 標(biāo)識ziplist的末尾

如果采用鏈表的存儲方式壮吩，鏈表中的元素由指針相連进苍，這樣的方式可能會造成一定的內(nèi)存碎片。而指針也會占用額外的存儲空間鸭叙。而ZipList不會存在這些情況觉啊，ZipList占用的是一段連續(xù)的內(nèi)存空間。

但是相應(yīng)地沈贝，ZipList的修改操作效率較為低下杠人，插入和刪除的操作會設(shè)計到頻繁的內(nèi)存空間申請和釋放（有點類似于ArrayList重新擴容），且查詢效率同樣會受影響，本質(zhì)上ZipList查詢元素就是遍歷鏈表嗡善。

3.2.2 QuickList

在3.2版本之后辑莫，list的實現(xiàn)就換成了QuickList。QuickList將list分成了多個節(jié)點罩引，每一個節(jié)點采用ZipList存儲數(shù)據(jù)各吨。

4. Hash

其用法就跟Java中的HashMap中一樣，都是往map中去丟鍵值對袁铐。

4.1 使用

基礎(chǔ)的命令如下：

• hset 在hash中設(shè)置鍵值對
• hget 獲hash中的某個key值
• hdel 刪除hash中某個鍵
• hlen 統(tǒng)計hash中元素的個數(shù)
• hmget 批量的獲取hash中的鍵的值
• hmset 批量的設(shè)置hash中的鍵和值
• hexists 判斷hash中某個key是否存在
• hkeys 返回hash中的所有鍵（不包含值）
• hvals 返回hash中的所有值（不包含鍵）
• hgetall 獲取所有的鍵值對揭蜒，包含了鍵和值

其實大多數(shù)情況下的使用跟HashMap是差不多的，沒有什么較為特殊的地方剔桨。

4.2 原理

hash的底層實現(xiàn)也是有兩種屉更，ZipList和HashTable。但具體采用哪一種與Redis的版本無關(guān)洒缀，而與當(dāng)前hash中所存的元素有關(guān)瑰谜。首先當(dāng)我們創(chuàng)建一個hash的時候，采用的ZipList進行存儲帝洪。隨著hash中的元素增多似舵，達到了Redis設(shè)定的閾值，就會轉(zhuǎn)換為HashTable葱峡。

其設(shè)定的閾值如下：

• 存儲的某個鍵或者值長度大于默認(rèn)值（64）
• ZipList中存儲的元素數(shù)量大于默認(rèn)值（512）

ZipList上面我們專門簡單分析了一下，理解這個設(shè)定應(yīng)該也比較容易龙助。當(dāng)ZipList中的元素過多的時候砰奕，其查詢的效率就會變得低下。而HashTable的底層設(shè)計其實和Java中的HashMap差不多提鸟，都是通過拉鏈法解決哈希沖突军援。具體的可以參考從基礎(chǔ)的使用來深挖HashMap這篇文章。

5. Set

Set的概念可以與Java中的Set劃等號称勋，用于存儲一個不包含重復(fù)元素的集合胸哥。

5.1 使用

其主要的命令如下，key代表redis中的Set赡鲜，member代表集合中的元素空厌。

• sadd sadd key member [...] 將一個或者多個元素加入到集合中，如果有已經(jīng)存在的元素會忽略掉银酬。
• srem srem key member [...]將一個或者多個元素從集合中移除嘲更，不存在的元素會被忽略掉
• smembers smembers key返回集合中的所有成員
• sismember dismember key member判斷member在key中是否存在，如果存在則返回1揩瞪，如果不存在則返回0
• scard scard key返回集合key中的元素的數(shù)量
• smove move source destination member將元素從source集合移動到destination集合赋朦。如果source中不包含member，則不會執(zhí)行任何操作，當(dāng)且僅當(dāng)存在才會從集合中移出宠哄。如果destination已經(jīng)存在元素則不會對destination做任何操作壹将。該命令是原子操作。
• spop spop key隨機刪除并返回集合中的一個元素
• srandmember srandmember key與spop一樣毛嫉，只不過不會將元素刪除瞭恰，可以理解為從集合中隨機出一個元素來。
• sinter 求一個或者多個集合的交集
• sinterstore sinterstore destination key [...]與sinter類似狱庇，但是會將得出的結(jié)果存到destination中惊畏。
• sunion 求一個或者多個集合的并集
• sunionstore sunionstore destination key [...]
• sdiff 求一個或者多個集合的差集
• sdiffstore sdiffstore destination key [...]與sdiff類似，但是會將得出的結(jié)果存到destination中密任。

5.2 原理

我們知道Java中的Set有多種實現(xiàn)颜启。在Redis中也是，有IntSet和HashTable兩種實現(xiàn)浪讳，首先初始化的時候使用的是IntSet缰盏，而滿足如下的條件時，就會轉(zhuǎn)換成HashTable淹遵。

• 當(dāng)集合中保存的所有元素都是整數(shù)時
• 集合對象保存的元素數(shù)量不超過512

上面已經(jīng)簡單的介紹了HashTable了口猜，所以這里只聊聊IntSet。

5.2.1 IntSet

intset底層是一個數(shù)組透揣，既然數(shù)據(jù)結(jié)構(gòu)是數(shù)組济炎，那么存儲數(shù)據(jù)就可以是有序的，這也使得intset的底層查詢是通過二分查找來實現(xiàn)辐真。其結(jié)構(gòu)如下须尚。

struct intset {
  // 編碼方式
  uint32_t encoding;
  // 集合包含元素的數(shù)量
  uint32_t length;
  // 存儲元素的數(shù)組
  int8_t contents[];
}

與ZipList類似，IntSet也是使用的一連串的內(nèi)存空間侍咱，但是不同的是ZipList可以存儲二進制的內(nèi)容耐床，而IntSet只能存儲整數(shù)；且ZipList存儲是無序的楔脯，IntSet則是有序的撩轰，這樣一來，元素個數(shù)相同的前提下昧廷，IntSet的查詢效率會更高。

6. Sorted Set

其與Set的功能大致類似麸粮，只不過在此基礎(chǔ)上，可以給每一個元素賦予一個權(quán)重弄诲。你可以理解為Java的TreeSet娇唯。與List寂玲、Hash、Set一樣拓哟，其底層的實現(xiàn)也有兩種，分別是ZipList和SkipList（跳表）断序。

初始化Sorted Set的時候流纹，會采用ZipList作為其實現(xiàn)，其實很好理解违诗，這個時候元素的數(shù)量很少漱凝，采用ZipList進行緊湊的存儲會更加的節(jié)省空間。當(dāng)期達到如下的條件時诸迟，就會轉(zhuǎn)換為SkipList：

• 其保存的元素數(shù)量的個數(shù)小于128個
• 其保存的所有元素長度小于64字節(jié)

6.1 使用

下面的命令中茸炒，key代表zset的名字；4代表score阵苇，也就是權(quán)重壁公；而member就是zset中的key的名稱。

• zadd zadd key 4 member用于增加元素
• zcard zcard key用于獲取zset中的元素的數(shù)量
• zrem zrem key member [...]刪除zset中一個或者多個key
• zincrby zincrby key 1 member給key的權(quán)重值加上score的值（也就是1）
• zscore zscore key member用于獲取指定key的權(quán)重值
• zrange zrange key 0 -1獲取zset中所有的元素绅项，zrange key 0 -1 withscores獲取所有元素和權(quán)重紊册，withscores參數(shù)的作用是決定是否將權(quán)重值也一起返回。其返回的元素按照從小到大排序趁怔，如果元素具有相同的權(quán)重湿硝，則會按照字典序排序。
• zrevrange zrevrange key 0 -1 withscores润努，其與zrange類似，只不過zrevrange按照從大到小排序示括。
• zrangebyscore zrangebyscore key 1 5铺浇，返回key中權(quán)重在區(qū)間(1, 5]范圍內(nèi)元素。當(dāng)然也可以使用withscores來將權(quán)重值一并返回垛膝。其元素按照從小到大排序鳍侣。1代表min，5代表max吼拥，他們也可以分別是-inf和inf倚聚，當(dāng)你不知道key中的score區(qū)間時，就可以使用這個凿可。還有一個類似于SQL中的limit的可選參數(shù)惑折，在此就不贅述授账。

除了能夠?qū)ζ渲械脑靥砑訖?quán)重之外，使用ZSet還可以實現(xiàn)延遲隊列惨驶。

延遲隊列用于存放延遲任務(wù)白热，那什么是延遲隊列呢粗卜？

舉個很簡單的例子续扔， 你在某個電商APP中下訂單纱昧，但是沒有付款砌些，此時它會提醒你存璃，「訂單如果超過1個小時沒有支付纵东，將會自動關(guān)閉」偎球；再比如在某個活動結(jié)束前1個小時給用戶推送消息；再比如訂單完成后多少天自動確認(rèn)收貨等等袍冷。

用人話解釋一遍胡诗，那就是過會才要干的事情煌恢。

那ZSet怎么實現(xiàn)這個功能瑰抵？

其實很簡單二汛，就是將任務(wù)的執(zhí)行時間設(shè)置為ZSet中的元素權(quán)重，然后通過一個后臺線程定時的從ZSet中查詢出權(quán)重最小的元素逛球，然后通過與當(dāng)前時間戳判斷颤绕，如果大于當(dāng)前時間戳（也就是該執(zhí)行了）就將其從ZSet中取出奥务。

那氯葬，怎么戎愠啤闯睹？

其實我看很多講Redis實現(xiàn)延遲隊列的博客都沒有把這個怎么取講清楚楼吃，到底該用什么命令孩锡，傳什么參數(shù)躬窜。我們使用zrangebyscore命令來實現(xiàn)斩披，還記得-inf和inf嗎，其全稱是infinity仍劈，分別表示無限小和無限大贩疙。

由于我們并不知道延遲隊列當(dāng)中的score（也就是任務(wù)執(zhí)行時間）的范圍这溅，所以我們可以直接使用-inf和inf臭胜，完整命令如下癞尚。

zrangescore key -inf inf limt 0 1 withscores

還是有點用仪壮，那ZSet底層是咋實現(xiàn)的呢胳徽？

上面已經(jīng)講過了ZipList缚陷，就不贅述爪瓜，下面聊聊SkipList铆铆。

6.2 原理

6.2.1 SkipList

SkipList存在于zset（Sorted Set）的結(jié)構(gòu)中薄货，如下：

struct zset {
  // 字典
  dict *dict;
  // 跳表
  zskiplist *zsl;
}

而SkipList的結(jié)構(gòu)如下：

struct zskiplist {
  // 表頭節(jié)點和表尾節(jié)點
  struct zskiplistNode *header, *tail;
  // 表中節(jié)點的數(shù)量
  unsigned long length;
  // 表中層數(shù)最大的節(jié)點的層數(shù)
  int level;
}

不知道大家是否有想過柄慰，為什么Redis要使用SkipList來實現(xiàn)ZSet坐搔，而不用數(shù)組呢概行？

首先ZSet如果數(shù)組存儲的話凳忙，由于ZSet中存儲的元素是有序的勤家，存入的時候需要將元素放入數(shù)組中對應(yīng)的位置伐脖。這樣就會對數(shù)組進行頻繁的增刪晓殊，而頻繁的增刪在數(shù)組中效率并不高，因為涉及到數(shù)組元素的移動介汹，如果元素插入的位置是首位嘹承，那么后面的所有元素都要被移動叹卷。

所以為了應(yīng)付頻繁增刪的場景骤竹，我們需要使用到鏈表蒙揣。但是隨著鏈表的元素增多，同樣的會出現(xiàn)問題开瞭，雖然增刪的效率提升了懒震，但是查詢的效率變低了，因為查詢元素會從頭到尾的遍歷鏈表嗤详。所有如果有什么方法能夠提升鏈表的查詢效率就好了个扰。

于是跳表就誕生了〈猩基于單鏈表锨匆，從第一個節(jié)點開始，每隔一個節(jié)點，建立索引恐锣。其實也是單鏈表。只不是中間省略了節(jié)點。

例如存在個單鏈表 1 3 4 5 7 8 9 10 13 16 17 18

抽象之后的索引為 1 4 7 9 13 17

如果要查詢16只需要在索引層遍歷到13，然后根據(jù)13存儲的下層節(jié)點（真實鏈表節(jié)點的地址），此時只需要再遍歷兩個節(jié)點就可以找到值為16的節(jié)點。

所以可以重新給跳表下一個定義昼榛，鏈表加多級索引的結(jié)構(gòu)莺掠，就是跳表

在跳表中酒朵，查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度是O(logn)匙铡。時間復(fù)雜度跟二分查找是一樣的矿瘦∫捉幔可以換句話說滋尉，用單鏈表實現(xiàn)了二分查找碌识。但這也是一種用空間換時間的思路，并不是免費的旅薄。

End

關(guān)于Redis的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和其底層的原理就簡單的聊到這里绍弟，之后的幾篇應(yīng)該會聊聊Redis的高可用和其對應(yīng)的解決方案，感興趣的可以持續(xù)關(guān)注，公眾號會比其他的平臺都先更新适刀。

好了以上就是本篇博客的全部內(nèi)容了稽物，如果你覺得這篇文章對你有幫助那先，還麻煩點個贊售淡，關(guān)個注衩茸，分個享楞慈，留個言。

歡迎微信搜索關(guān)注【SH的全棧筆記】姥芥，查看更多相關(guān)文章