Redis為何這么快——數據存儲角度
本文內容思維導圖如下：
一、簡介和應用
Redis是一個由ANSI C語言編寫，性能優秀、支持網絡、可持久化的K-K內存數據庫，并提供多種語言的API。它常用的類型主要是 String、List、Hash、Set、ZSet 這5種
Redis在互聯網公司一般有以下應用:
- String：緩存、限流、計數器、分布式鎖、分布式Session
- Hash：存儲用戶信息、用戶主頁訪問量、組合查詢
- List：微博關注人時間軸列表、簡單隊列
- Set：贊、踩、標簽、好友關系
- Zset：排行榜
再比如電商在大促銷時，會用一些特殊的設計來保證系統穩定，扣減庫存可以考慮如下設計：
上圖中，直接在Redis中扣減庫存，記錄日志后通過Worker同步到數據庫，在設計同步Worker時需要考慮并發處理和重復處理的問題。
通過上面的應用場景可以看出Redis是非常高效和穩定的，那Redis底層是如何實現的呢？
二、Redis的對象redisObject
當我們執行set hello world命令時，會有以下數據模型：
- dictEntry：Redis給每個key-value鍵值對分配一個dictEntry，里面有著key和val的指針，next指向下一個dictEntry形成鏈表，這個指針可以將多個哈希值相同的鍵值對鏈接在一起，由此來解決哈希沖突問題(鏈地址法)。
- sds：鍵key“hello”是以SDS（簡單動態字符串）存儲，后面詳細介紹。
- redisObject：值val“world”存儲在redisObject中。實際上，redis常用5中類型都是以redisObject來存儲的；而redisObject中的type字段指明了Value對象的類型，ptr字段則指向對象所在的地址。
redisObject對象非常重要，Redis對象的類型、內部編碼、內存回收、共享對象等功能，都需要redisObject支持。這樣設計的好處是，可以針對不同的使用場景，對5中常用類型設置多種不同的數據結構實現，從而優化對象在不同場景下的使用效率。
無論是dictEntry對象，還是redisObject、SDS對象，都需要內存分配器（如jemalloc）分配內存進行存儲。jemalloc作為Redis的默認內存分配器，在減小內存碎片方面做的相對比較好。比如jemalloc在64位系統中，將內存空間劃分為小、大、巨大三個范圍；每個范圍內又劃分了許多小的內存塊單位；當Redis存儲數據時，會選擇大小最合適的內存塊進行存儲。
前面說過，Redis每個對象由一個redisObject結構表示，它的ptr指針指向底層實現的數據結構，而數據結構由encoding屬性決定。比如我們執行以下命令得到存儲“hello”對應的編碼：
redis所有的數據結構類型如下（重要，后面會用）：
三、String
字符串對象的底層實現可以是int、raw、embstr（上面的表對應有名稱介紹）。embstr編碼是通過調用一次內存分配函數來分配一塊連續的空間，而raw需要調用兩次。
int編碼字符串對象和embstr編碼字符串對象在一定條件下會轉化為raw編碼字符串對象。embstr：<=39字節的字符串。int：8個字節的長整型。raw：大于39個字節的字符串。
簡單動態字符串（SDS），這種結構更像C++的String或者Java的ArrayList<Character>，長度動態可變：
- struct sdshdr {
- // buf 中已占用空間的長度
- int len;
- // buf 中剩余可用空間的長度
- int free;
- // 數據空間
- char buf[]; // ’’空字符結尾
- };
- get：sdsrange---O(n)
- set：sdscpy—O(n)
- create：sdsnew---O(1)
- len：sdslen---O(1)
常數復雜度獲取字符串長度：因為SDS在len屬性中記錄了長度，所以獲取一個SDS長度時間復雜度僅為O(1)。
預空間分配：如果對一個SDS進行修改，分為一下兩種情況：
- SDS長度（len的值）小于1MB，那么程序將分配和len屬性同樣大小的未使用空間，這時free和len屬性值相同。舉個例子，SDS的len將變成15字節，則程序也會分配15字節的未使用空間，SDS的buf數組的實際長度變成15+15+1=31字節（額外一個字節用戶保存空字符）。
- SDS長度（len的值）大于等于1MB，程序會分配1MB的未使用空間。比如進行修改之后，SDS的len變成30MB，那么它的實際長度是30MB+1MB+1byte。
惰性釋放空間：當執行sdstrim（截取字符串）之后，SDS不會立馬釋放多出來的空間，如果下次再進行拼接字符串操作，且拼接的沒有剛才釋放的空間大，則那些未使用的空間就會排上用場。通過惰性釋放空間避免了特定情況下操作字符串的內存重新分配操作。
杜絕緩沖區溢出：使用C字符串的操作時，如果字符串長度增加（如strcat操作）而忘記重新分配內存，很容易造成緩沖區的溢出；而SDS由于記錄了長度，相應的操作在可能造成緩沖區溢出時會自動重新分配內存，杜絕了緩沖區溢出。
四、List
List對象的底層實現是quicklist（快速列表，是ziplist 壓縮列表 和linkedlist 雙端鏈表 的組合）。Redis中的列表支持兩端插入和彈出，并可以獲得指定位置（或范圍）的元素，可以充當數組、隊列、棧等。
- typedef struct listNode {
- // 前置節點
- struct listNode *prev;
- // 后置節點
- struct listNode *next;
- // 節點的值
- void *value;
- } listNode;
- typedef struct list {
- // 表頭節點
- listNode *head;
- // 表尾節點
- listNode *tail;
- // 節點值復制函數
- void *(*dup)(void *ptr);
- // 節點值釋放函數
- void (*free)(void *ptr);
- // 節點值對比函數
- int (*match)(void *ptr, void *key);
- // 鏈表所包含的節點數量
- unsigned long len;
- } list;
- rpush: listAddNodeHead ---O(1)
- lpush: listAddNodeTail ---O(1)
- push:listInsertNode ---O(1)
- index : listIndex ---O(N)
- pop:ListFirst/listLast ---O(1)
- llen:listLength ---O(N)
4.1 linkedlist（雙端鏈表）
此結構比較像Java的LinkedList，有興趣可以閱讀一下源碼。
從圖中可以看出Redis的linkedlist雙端鏈表有以下特性：節點帶有prev、next指針、head指針和tail指針，獲取前置節點、后置節點、表頭節點和表尾節點的復雜度都是O（1）。len屬性獲取節點數量也為O（1）。
與雙端鏈表相比，壓縮列表可以節省內存空間，但是進行修改或增刪操作時，復雜度較高；因此當節點數量較少時，可以使用壓縮列表；但是節點數量多時，還是使用雙端鏈表劃算。
4.2 ziplist（壓縮列表）
當一個列表鍵只包含少量列表項，且是小整數值或長度比較短的字符串時，那么redis就使用ziplist（壓縮列表）來做列表鍵的底層實現。
ziplist是Redis為了節約內存而開發的，是由一系列特殊編碼的連續內存塊(而不是像雙端鏈表一樣每個節點是指針)組成的順序型數據結構；具體結構相對比較復雜，有興趣讀者可以看 Redis 哈希結構內存模型剖析。在新版本中list鏈表使用 quicklist 代替了 ziplist和 linkedlist：
quickList 是 zipList 和 linkedList 的混合體。它將 linkedList 按段切分，每一段使用 zipList 來緊湊存儲，多個 zipList 之間使用雙向指針串接起來。因為鏈表的附加空間相對太高，prev 和 next 指針就要占去 16 個字節 (64bit 系統的指針是 8 個字節)，另外每個節點的內存都是單獨分配，會加劇內存的碎片化，影響內存管理效率。
quicklist 默認的壓縮深度是 0，也就是不壓縮。為了支持快速的 push/pop 操作，quicklist 的首尾兩個 ziplist 不壓縮，此時深度就是 1。為了進一步節約空間，Redis 還會對 ziplist 進行壓縮存儲，使用 LZF 算法壓縮。
五、Hash
Hash對象的底層實現可以是ziplist（壓縮列表）或者hashtable（字典或者也叫哈希表）。
Hash對象只有同時滿足下面兩個條件時，才會使用ziplist（壓縮列表）：1.哈希中元素數量小于512個；2.哈希中所有鍵值對的鍵和值字符串長度都小于64字節。
hashtable哈希表可以實現O(1)復雜度的讀寫操作，因此效率很高。源碼如下：
- typedef struct dict {
- // 類型特定函數
- dictType *type;
- // 私有數據
- void *privdata;
- // 哈希表
- dictht ht[2];
- // rehash 索引
- // 當 rehash 不在進行時，值為 -1
- int rehashidx; /* rehashing not in progress if rehashidx == -1 */
- // 目前正在運行的安全迭代器的數量
- int iterators; /* number of iterators currently running */
- } dict;
- typedef struct dictht {
- // 哈希表數組
- dictEntry **table;
- // 哈希表大小
- unsigned long size;
- // 哈希表大小掩碼，用于計算索引值
- // 總是等于 size - 1
- unsigned long sizemask;
- // 該哈希表已有節點的數量
- unsigned long used;
- } dictht;
- typedef struct dictEntry {
- void *key;
- union {void *val;uint64_t u64;int64_t s64;} v;
- // 指向下個哈希表節點，形成鏈表
- struct dictEntry *next;
- } dictEntry;
- typedef struct dictType {
- // 計算哈希值的函數
- unsigned int (*hashFunction)(const void *key);
- // 復制鍵的函數
- void *(*keyDup)(void *privdata, const void *key);
- // 復制值的函數
- void *(*valDup)(void *privdata, const void *obj);
- // 對比鍵的函數
- int (*keyCompare)(void *privdata, const void *key1, const void *key2);
- // 銷毀鍵的函數
- void (*keyDestructor)(void *privdata, void *key);
- // 銷毀值的函數
- void (*valDestructor)(void *privdata, void *obj);
- } dictType;
上面源碼可以簡化成如下結構：
這個結構類似于JDK7以前的HashMap<String,Object>，當有兩個或以上的鍵被分配到哈希數組的同一個索引上時，會產生哈希沖突。Redis也使用鏈地址法來解決鍵沖突。即每個哈希表節點都有一個next指針，多個哈希表節點用next指針構成一個單項鏈表，鏈地址法就是將相同hash值的對象組織成一個鏈表放在hash值對應的槽位。
Redis中的字典使用hashtable作為底層實現的話，每個字典會帶有兩個哈希表，一個平時使用，另一個僅在rehash（重新散列）時使用。隨著對哈希表的操作，鍵會逐漸增多或減少。為了讓哈希表的負載因子維持在一個合理范圍內，Redis會對哈希表的大小進行擴展或收縮（rehash），也就是將ht【0】里面所有的鍵值對分多次、漸進式的rehash到ht【1】里。
六、Set
Set集合對象的底層實現可以是intset（整數集合）或者hashtable（字典或者也叫哈希表）。
intset（整數集合）當一個集合只含有整數，并且元素不多時會使用intset（整數集合）作為Set集合對象的底層實現。
- typedef struct intset {
- // 編碼方式
- uint32_t encoding;
- // 集合包含的元素數量
- uint32_t length;
- // 保存元素的數組
- int8_t contents[];
- } intset;
- sadd:intsetAdd---O(1)
- smembers:intsetGetO(1)---O(N)
- srem:intsetRemove---O(N)
- slen:intsetlen ---O(1)
intset底層實現為有序，無重復數組保存集合元素。 intset這個結構里的整數數組的類型可以是16位的，32位的，64位的。如果數組里所有的整數都是16位長度的，如果新加入一個32位的整數，那么整個16的數組將升級成一個32位的數組。升級可以提升intset的靈活性，又可以節約內存，但不可逆。
7.ZSet
ZSet有序集合對象底層實現可以是ziplist（壓縮列表）或者skiplist（跳躍表）。
當一個有序集合的元素數量比較多或者成員是比較長的字符串時，Redis就使用skiplist（跳躍表）作為ZSet對象的底層實現。
- typedef struct zskiplist {
- // 表頭節點和表尾節點
- struct zskiplistNode *header, *tail;
- // 表中節點的數量
- unsigned long length;
- // 表中層數***的節點的層數
- int level;
- } zskiplist;
- typedef struct zskiplistNode {
- // 成員對象
- robj *obj;
- // 分值
- double score;
- // 后退指針
- struct zskiplistNode *backward;
- // 層
- struct zskiplistLevel {
- // 前進指針
- struct zskiplistNode *forward;
- // 跨度---前進指針所指向節點與當前節點的距離
- unsigned int span;
- } level[];
- } zskiplistNode;
zadd---zslinsert---平均O(logN), 最壞O(N)
zrem---zsldelete---平均O(logN), 最壞O(N)
zrank--zslGetRank---平均O(logN), 最壞O(N)
skiplist的查找時間復雜度是LogN，可以和平衡二叉樹相當，但實現起來又比它簡單。跳躍表(skiplist)是一種有序數據結構，它通過在某個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。
