Redis基本類型及其數據結構
以前在使用Redis的時候，只是簡單地使用它提供的基本數據類型和接口，并沒有深入研究它底層的數據結構。最近打算重新學習梳理一下Redis方面的知識，所以打算從介紹Redis的基本類型及其數據結構入手。
redisObject
Redis的key是頂層模型，它的value是扁平化的。Redis中，所有的value都是一個object，它的結構如下：
- typedef struct redisObject {
- unsigned [type] 4;
- unsigned [encoding] 4;
- unsigned [lru] REDIS_LRU_BITS;
- int refcount;
- void *ptr;
- } robj;
簡單介紹一下這幾個字段：
- type：數據類型，就是我們熟悉的string、hash、list等。
- encoding：內部編碼，其實就是本文要介紹的數據結構。指的是當前這個value底層是用的什么數據結構。因為同一個數據類型底層也有多種數據結構的實現，所以這里需要指定數據結構。
- REDIS_LRU_BITS：當前對象可以保留的時長。這個我們在后面講鍵的過期策略的時候講。
- refcount：對象引用計數，用于GC。
- ptr：指針，指向以encoding的方式實現這個對象的實際地址。
string
在Redis內部，string類型有兩種底層儲存結構。Redis會根據存儲的數據及用戶的操作指令自動選擇合適的結構：
- int：存放整數類型;
- SDS：存放浮點、字符串、字節類型;
- SDS: 簡單動態字符串 simple dynamic string
SDS
SDS的內部數據結構：
- typedef struct sdshdr {
- // buf中已經占用的字符長度
- unsigned int len;
- // buf中剩余可用的字符長度
- unsigned int free;
- // 數據空間
- char buf[];
- }
可見，其底層是一個char數組。buf最大容量為512M，里面可以放字符串、浮點數和字節。所以你甚至可以放一張序列化后的圖片。它為什么沒有直接使用數組，而是包裝成了這樣的數據結構呢?
因為buf會有動態擴容和縮容的需求。如果直接使用數組，那每次對字符串的修改都會導致重新分配內存，效率很低。
buf的擴容過程如下：
- 如果修改后len長度將小于1M,這時分配給free的大小和len一樣,例如修改過后為10字節, 那么給free也是10字節，buf實際長度變成了10 + 10 + 1 = 21byte
- 如果修改后len長度將大于等于1M,這時分配給free的長度為1M,例如修改過后為30M,那么給free是1M.buf實際長度變成了30M + 1M + 1byte
惰性空間釋放指的是當字符串縮短時，并沒有真正的縮容，而是移動free的指針。這樣將來字符串長度增加時，就不用重新分配內存了。但這樣會造成內存浪費，Redis提供了API來真正釋放內存。
list
list底層有兩種數據結構：鏈表linkedlist和壓縮列表ziplist。當list元素個數少且元素內容長度不大時，使用ziplist實現，否則使用linkedlist。
鏈表
Redis使用的鏈表是雙向鏈表。為了方便操作，使用了一個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;
data存的其實也是一個指針。鏈表里面的元素是上面介紹的string。因為是雙向鏈表，所以可以很方便地把它當成一個棧或者隊列來使用。
壓縮列表
與上面的鏈表相對應，壓縮列表有點兒類似數組，通過一片連續的內存空間，來存儲數據。不過，它跟數組不同的一點是，它允許存儲的數據大小不同。每個節點上增加一個length屬性來記錄這個節點的長度，這樣比較方便地得到下一個節點的位置。
上圖的各字段含義為：
- zlbytes：列表的總長度
- zltail：指向最末元素
- zllen：元素的個數
- entry：元素的內容，里面記錄了前一個Entry的長度，用于方便雙向遍歷
- zlend：恒為0xFF，作為ziplist的定界符
壓縮列表不只是list的底層實現，也是hash的底層實現之一。當hash的元素個數少且內容長度不大時，使用壓縮列表來實現。
hash
hash底層有兩種實現：壓縮列表和字典(dict)。壓縮列表剛剛上面已經介紹過了，下面主要介紹一下字典的數據結構。
字典
字典其實就類似于Java語言中的Map,Python語言中的dict。與Java中的HashMap類似，Redis底層也是使用的散列表作為字典的實現，解決hash沖突使用的是鏈表法。Redis同樣使用了一個數據結構來持有這個散列表：
在鍵增加或減少時，會擴容或縮容，并且進行rehash，根據hash值重新計算索引值。那如果這個字典太大了怎么辦呢?
為了解決一次性擴容耗時過多的情況，可以將擴容操作穿插在插入操作的過程中，分批完成。當負載因子觸達閾值之后，只申請新空間，但并不將老的數據搬移到新散列表中。當有新數據要插入時，將新數據插入新散列表中，并且從老的散列表中拿出一個數據放入到新散列表。每次插入一個數據到散列表，都重復上面的過程。經過多次插入操作之后，老的散列表中的數據就一點一點全部搬移到新散列表中了。這樣沒有了集中的一次一次性數據搬移，插入操作就都變得很快了。這個過程也被稱為漸進式rehash。
set
set里面沒有重復的集合。set的實現比較簡單。如果是整數類型，就直接使用整數集合intset。使用二分查找來輔助，速度還是挺快的。不過在插入的時候，由于要移動元素，時間復雜度是O(N)。
如果不是整數類型，就使用上面在hash那一節介紹的字典。key為set的值，value為空。
zset
zset是可排序的set。與hash的實現方式類似，如果元素個數不多且不大，就使用壓縮列表ziplist來存儲。不過由于zset包含了score的排序信息，所以在ziplist內部，是按照score排序遞增來存儲的。意味著每次插入數據都要移動之后的數據。
跳表
跳表(skiplist)是另一種實現dict的數據結構。跳表是對鏈表的一個增強。我們在使用鏈表的時候，即使元素的有序排列的，但如果要查找一個元素，也需要從頭一個個查找下去，時間復雜度是O(N)。而跳表顧名思義，就是跳躍了一些元素，可以抽象多層。
如下圖所示，比如我們要查找8，先在最上層L2查找，發現在1和9之間;然后去L1層查找，發現在5和9之間;然后去L0查找，發現在7和9之間，然后找到8。
當元素比較多時，使用跳表可以顯著減少查找的次數。
同list類似，Redis內部也不是直接使用的跳表，而是使用了一個自定義的數據結構來持有跳表。下圖左邊藍色部分是skiplist，右邊是4個zskiplistNode。zskiplistNode內部有很多層L1、L2等，指針指向這一層的下一個結點。BW是回退指針(backward)，用于查找的時候回退。然后下面是score和對象本身object。
總結
Redis對外暴露的是對象(數據類型)，而每個對象都是用一個redisObject持有，通過不同的編碼，映射到不同的數據結構。從最開始的那個圖可以知道，有時候不同對象可能會底層使用同一種數據結構，比如壓縮列表和字典等。
在了解數據結構后，我們就能夠更清楚應該選用什么樣的對象，出現問題時應該如何優化了。
