Redis之数据结构底层实现
目錄
redis底層數據結構實現
Redis數據結構
String字符串
常用命令
SDS的定義
SDS的好處
應用場景
List列表
常用命令
壓縮列表ziplist
quicklist
應用場景
Hash哈希
常用命令
hashtable
應用場景
Set集合
常用命令
inset整型集合
應用場景
ZSet有序集合
存儲原理
skiplist
應用場景
參考鏈接
redis底層數據結構實現
redis是（REmote DIctionary Service）作為NoSQL數據庫，以key-value的字典方式來存儲數據，其中的value主要支持五種數據類型。
本文主要講解redis的五種常用數據類型（string、list、hash、set、zset）的底層數據結構實現。
Redis數據結構
Redis采用key-value的方式來存儲數據，每個鍵值對都會有一個dictEntry，里面有指向key,value的指針，還有指向下一個鍵值對的next指針
typedef struct dictEntry {void *key; /* key 關鍵字定義*/union {void *val; uint64_t u64; /* value 定義*/int64_t s64;double d;} v;struct dictEntry *next; /* 指向下一個鍵值對節點*/ } dictEntry;這里的key 是字符串，使用了Redis自己定義的SDS數據結構來存儲,而value 是存儲在redisObject 中的。
typedef struct redisObject {unsigned type:4; /* 對象的類型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET*/unsigned encoding:4; /* 底層存儲的具體數據結構*/unsigned lru:LRU_BITS; /* 24 位，對象最后一次被訪問的時間，與內存淘汰機制有關*/int refcount; /* 引用計數。當其為0的時候，表示該對象已經不被任何對象引用，可以進行垃圾回收*/void *ptr; /* 指向對象實際的數據結構*/ } robj;String字符串
redis中并沒有使用C語言的?字符串表示(以空字符結尾的字符數組)，而是自己定義了一個SDS(Simple Dynamic String,簡單動態字符串)作為字符串的默認實現
常用命令
| 1 | SET key value 設值 |
| 2 | GET key 取值。 |
| 3 | MGET key1 [key2..] 獲取所有(一個或多個)給定 key 的值。 |
| 4 | SETEX key seconds value 設值，并將 key 的過期時間設為 seconds (以秒為單位) (原子性)。 |
| 5 | SETNX key value 只有在 key 不存在的時候才可以成功設置(可以根據這個特性來創建分布式鎖) |
| 6 | MGET key1 [key2..] 獲取所有(一個或多個)給定 key 的值。 |
| 7 | MSET key value [key value ...] 同時設置一個或多個 key-value 對(批量操作，原子性)。 |
| 8 | INCR/DECR key 將 key 中儲存的數字值增一/減一。 |
| 9 | APPEND key value 向key對應的value值后追加新的value到其末尾 |
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
對于字符串,其內部的encoding有三種:? 根本原因還是為了減少內存消耗
Embstr和raw的區別? 區別在于分配內存的次數
Embstr在使用的時候只需要分配一次內存空間(RedisObject和SDS是連續的),而raw需要分配兩次。如果字符串的長度增加導致需要重新分配內存空間，embstr類型的RedisObject和SDS都需要重新分配,因此 Redis中的embstr表現為只讀(對embstr進行修改就會轉化為raw編碼)
?
SDS的定義
redis中的SDS有各種結構，sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，用于存儲不同的長度的字符串(節省內存空間)，分別代表2^5=32byte， 2^8=256byte，2^16=65536byte=64KB，2^32byte=4GB
/* sds.h */ struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* 當前字符數組的長度*/uint8_t alloc; /*當前字符數組總共分配的內存大小*/unsigned char flags; /* 當前字符數組的屬性,用來標識是sdshdr8 還是sdshdr16 等*/char buf[]; /* 字符串真正的值,最后一個字符保存了空字符 '\0' */ };比方說一個字符串"Redis",給它分配了32個字節的空間，目前只保存了5個字符
SDS的好處
1.在聲明的時候提前預留了空間，并且會在內存不夠的時候進行擴容
2.在SDS定義了字符串的長度len,獲取其長度的時間復雜度為O(1)
3.通過事先分配空間（空間預分配）和惰性空間釋放，較少內存重新分配的次數，大大提高存儲效率
4.以從開始的第len個字符表示字符串的結束，不用擔心存儲二進制數據的時候由于’\0’而導致無法完整獲取數據，是二進制安全的
5.同樣以'\0'結尾是因為這樣就可以使用C語言中函數庫操作字符串的函數了
應用場景
緩存熱點數據,可以提升熱點數據的訪問速度
在分布式下共享數據 eg.分布式session
分布式鎖 (setnx)
計數器:頁面訪問流量統計(incr)
List列表
用于存儲有序的字符串,可以從頭和尾添加或者獲取元素(Left/Right)，列表里的元素可以重復,能夠充當隊列和棧的角色
常用命令
| 1 | BLPOP key1 [key2 ] timeout 從左側移出并獲取列表的第一個元素， 如果列表沒有元素會阻塞直到超時或發現可彈出元素為止。 |
| 2 | BRPOP key1 [key2 ] timeout 從右側并獲取列表的最后一個元素， 如果列表沒有元素會阻塞直到超時或發現可彈出元素為止。 |
| 3 | LPUSH key value1 [value2] 將一個或多個值插入到列表頭部(左側) |
| 4 | RPUSH key value1 [value2] 向列表尾部添加一個或多個值(右側) |
?
?
?
?
?
?
?
?
先來說一下redis里的壓縮列表的數據結構
壓縮列表ziplist
壓縮列表(ziplist),顧名思義，在條件允許的情形下對保存的列表數據盡可能的進行壓縮，是Redis 為了節約內存而開發的， 一個經過特殊編碼的連續內存塊組成的雙向鏈表。它不像普通的鏈表存儲指向上一個鏈表節點和指向下一個鏈表節點的指針，而是存儲上一個節點長度和當前節點長度，通過犧牲部分讀寫性能，來換取高效的內存空間利用率。只適合用在字段個數少，字段值小的場景里面。
typedef struct zlentry {unsigned int prevrawlensize; /* 上一個鏈表節點占用的長度*/unsigned int prevrawlen; /* 存儲上一個鏈表節點的長度數值所需要的字節數*/unsigned int lensize; /* 存儲當前鏈表節點長度數值所需要的字節數*/unsigned int len; /* 當前鏈表節點占用的長度*/unsigned int headersize; /* 當前鏈表節點的頭部大小（prevrawlensize + lensize），即非數據域 的大小*/ unsigned char encoding; /* 編碼方式*/unsigned char *p; /* 壓縮鏈表以字符串的形式保存，該指針指向當前節點起始位置*/ } zlentry;其存儲結構如下圖:
早期版本里，redis的列表是通過ziplist或者linkedlist的結構實現,數據量較小的時候會使用ziplist來保存數據，較大的時候會使用linkedlist(雙向鏈表的結構)來存儲，類似于下圖，就不再贅述了
quicklist
3.2版本之后，統一用quicklist來存儲。quicklist存儲了一個雙向鏈表，每個節點都是一個ziplist。?
typedef struct quicklist { quicklistNode *head; /* 指向雙向列表的表頭 */ quicklistNode *tail; /* 指向雙向列表的表尾 */ unsigned long count; /* 所有的 ziplist 中一共存了多少個元素 */ unsigned long len; /* 雙向鏈表的長度，node 的數量 */ int fill : 16; /* fill factor for individual nodes */ unsigned int compress : 16; /* 壓縮深度，0：不壓縮； */} quicklist; typedef struct quicklistNode { struct quicklistNode *prev; /* 前一個節點 */ struct quicklistNode *next; /* 后一個節點 */ unsigned char *zl; /* 指向實際的 ziplist */ unsigned int sz; /* 當前 ziplist 占用多少字節 */ unsigned int count : 16; /* 當前 ziplist 中存儲了多少個元素，占 16bit（下同），最大 65536 個 */ unsigned int encoding : 2; /* 是否采用了 LZF 壓縮算法壓縮節點，1：RAW 2：LZF */ unsigned int container : 2; /* 2：ziplist，未來可能支持其他結構存儲 */ unsigned int recompress : 1; /* 當前 ziplist 是不是已經被解壓出來作臨時使用 */ unsigned int attempted_compress : 1; /* 測試用 */ unsigned int extra : 10; /* 預留給未來使用 */ } quicklistNode; quicklist結構圖?
應用場景
消息隊列: List提供了兩個帶阻塞功能的pop操作：BLPOP/BRPOP，可以實現簡單的類似消息隊列的功能
隊列：先進先出：rpush blpop
棧：先進后出：rpush brpop
?
Hash哈希
存儲包含鍵值對的無序散列表,其value只能是字符串，不能嵌套其他類型
常用命令
| 1 | HDEL key field1 [field2] 刪除一個或多個哈希表字段 |
| 2 | HEXISTS key field 查看哈希表中，是否存在指定的field |
| 3 | HGET key field 獲取存儲在哈希表中指定field對應的value。 |
| 4 | HGETALL key 獲取在哈希表中指定 key 的所有字段和值 |
| 5 | HKEYS key 獲取key對應的哈希表中所有的字段 |
| 6 | HMSET key field1 value1 [field2 value2 ] 同時將多個 field-value (鍵值對)設置到哈希表 key 中。 |
| 7 | HSET key field value 將哈希表 key 中的字段 field 的值設為 value 。 |
?
?
?
?
?
?
?
?
?
?
:zipl
前面說到redis本身就是一個K-V鍵值對的字典數據庫，對于Hash結構，相當于將Redis的Value也使用field-value的方式來進行存儲。其存儲方式有兩種:ziplist和hashtable
當hash對象同時滿足以下兩個條件的時候，會使用ziplist編碼：
1）所有的鍵值對的健和值的字符串長度都小于等于64byte；
2）哈希對象保存的鍵值對數量小于512個。?
壓縮列表在前面就介紹過了，這里就介紹下hashtable\
hashtable
哈希表的節點使用dictEntry來表示,每個?dictEntry?結構都保存著一個鍵值對：
typedef struct dictEntry {void *key; /* key 關鍵字定義*/union {void *val; uint64_t u64; /* value 定義*/int64_t s64; double d;} v;struct dictEntry *next; /* 指向下一個鍵值對節點*/ } dictEntry;而dictEntry存儲在一個dictht里(一個hashtable),
/*Thisisourhashtablestructure.Everydictionaryhastwoofthisaswe *implementincrementalrehashing,fortheoldtothenewtable.*/ typedef struct dictht{dictEntry **table;/* 哈希表數組 每一個元素是一個dictEntry*/ unsigned long size;/* 哈希表大小 */ unsigned long sizemask;/* 掩碼大小，用于計算索引值。總是等于 size-1*/ unsigned long used;/* 已有節點數 */} dictht;而上述哈希表又保存到了dict里
typedef struct dict{ dictType *type;/* 字典類型 */ void *privdata;/* 私有數據 */ dictht ht[2];/* 一個字典有兩個哈希表 */ long rehashidx;/*rehash 索引 */ unsigned long iterators;/* 當前正在使用的迭代器數量 */ } dict;從外層到底層是這樣的一個包含關系
dict-->dictht-->dictEntry
在普通情形下，一個哈希的字典的存儲結構如下圖:
其存儲的方式類似于hashMap,如果發生hash沖突，那么就會將對應下標的最后一個元素的next指針指向新的dictEntry
這里定義了兩個hashtable，主要是為了在發生大量哈希碰撞的時候進行擴容使用
一般情形下,dict里使用hashtable的時候，默認使用的是ht[0],ht[1]不會進行初始化和分配空間。哈希表使用鏈地址法來解決hash碰撞，如果碰撞劇烈，導致ht[0]的鏈很長，就會影響到redis的查詢速度。故hashtable的查詢性能取決于其table大小和保存的節點數量之間的比值。當上述比值較大的時候,也就是說hash碰撞發生比較劇烈的時候會對其進行擴容
此時需滿足兩個條件:
1)允許擴容 dict_can_resize=1
2)table里保存的節點數/table的大小大于dict_force_resize_ratio
擴容時，會對ht[1]進行初始化，并且分配空間，新的hashtable的大小為當前hashtable保存的節點數*2，然后將ht[0]里的dictEntry遷移到ht[1],重新計算哈希值和索引，存放到新的索引下。遷移完成后，將ht[1]設置為ht[0]表,然后把原來的ht[0]清空回收內存，將其設置為ht[1]以供下次rehash使用
應用場景
字符串數據結構可以做的事情，Hash也都能實現
存儲對象類型的數據，以field為屬性，value為對應的屬性值，便于管理
Set集合
string類型的無序集合
常用命令
| 1 | SADD key member1 [member2] 向集合添加一個或多個成員 |
| 2 | SCARD key 獲取集合的成員數 |
| 3 | SDIFF key1 [key2] 返回給定所有集合的差集 |
| 4 | SDIFFSTORE destination key1 [key2] 返回給定所有集合的差集并存儲在 destination 中 |
| 5 | SINTER key1 [key2] 返回給定所有集合的交集 |
| 6 | SINTERSTORE destination key1 [key2] 返回給定所有集合的交集并存儲在 destination 中 |
| 7 | SISMEMBER key member 判斷 member 元素是否是集合 key 的成員 |
| 8 | SPOP key 移除并返回集合中的一個隨機元素 |
| 9 | SRANDMEMBER key [count] 返回集合中一個或多個隨機數 |
| 10 | SREM key member1 [member2] 移除集合中一個或多個成員 |
| 11 | SUNION key1 [key2] 返回所有給定集合的并集 |
| 12 | SUNIONSTORE destination key1 [key2] 所有給定集合的并集存儲在 destination 集合中 |
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
Redis采用用intset或hashtable來存儲set。如果元素都是整數類型，使用inset存儲。
如果不全是整數類型，就用hashtable（數組+鏈表的結構來存儲）,目的還是為了節省存儲空間
inset整型集合
typedef struct intset {// 編碼方式 : INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64uint32_t encoding;// 集合包含的元素數量uint32_t length;// 保存元素的數組 不同的encoding,其數組的元素大小也不一樣int8_t contents[]; } intset;使用hashtable來存儲set的時候，dictEntry里的key對應于set里的成員，value為null
應用場景
抽獎 : 隨機獲取一個成員
簽到 , 點贊，打卡
商品標簽
商品篩選 ： 通過交集，差集，并集等做商品篩選
?
ZSet有序集合
有序的集合，每個元素都會有對應的score,根據score來排序；score相同時，按照key的ASCII碼排序。
| 1 | ZADD key score1 member1 [score2 member2] 向有序集合添加一個或多個成員，或者更新已存在成員的分數 |
| 3 | ZCOUNT key min max 計算score在指定區間的有序集合的成員數 |
| 4 | ZINCRBY key increment member 有序集合中對指定成員的分數加上增量 increment |
| 5 | ZRANGE key start stop [WITHSCORES] 通過索引區間返回有序集合指定區間內的成員 |
| 6 | ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT] 通過分數返回有序集合指定區間內的成員 |
| 7 | ZRANK key member 返回有序集合中指定成員的索引 |
| 8 | ZREM key member [member ...] 移除有序集合中的一個或多個成員 |
| 9 | ZREVRANGE key start stop [WITHSCORES] 返回有序集中指定區間內的成員，通過索引，分數從高到低 |
| 10 | ZREVRANGEBYSCORE key max min [WITHSCORES] 返回有序集中指定分數區間內的成員，分數從高到低排序 |
| 11 | ZREVRANK key member 返回有序集合中指定成員的排名，有序集成員按分數值遞減(從大到小)排序 |
| 12 | ZSCORE key member 返回有序集中，成員的分數值 |
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
存儲原理
有序集合底層采用ziplist或者skiplist的方式進行存儲
當?元素數量小于128個且所有member的長度都小于64字節的時候會使用ziplist存儲有序集合,在壓縮列表內部，按照score遞增的順序來進行存儲，故而每次插入或者刪除的時候要移動之后的數據
當大于這個閾值時，會使用跳躍表(skiplist)來存儲
skiplist
大家都知道，對于鏈表，插入和刪除的效率比較高，但是查詢的效率會很低，因為需要從head節點開始遍歷，直到找到對應的元素或者遍歷完整個鏈表，其時間復雜度時O(n).同理，在有序鏈表里插入數據的時候也需要先查詢一遍才可以確定插入的位置
對于有序數組我們可以使用二分查找法來優化查詢的速度，對于有序鏈表，可以使用跳躍表
假如我們每相鄰的兩個節點間增加一個指針，形成一個新的Level(實際情形不一定是相鄰2個節點形成一個level,但是Level越大，該層上的節點數就越少)，讓其上的指針指向下一個節點。這樣新的Level也是一個鏈表，但它包含的節點個數只有原來的一半(實際一定比原來少，具體多少不一定)（圖中的8, 19, 41）。
如下圖:
當想新增一個節點數據的時候，會根據冪次定律 （power law，越大的數出現的概率越小） 隨機生成一個介于?1?和?32?之間的值作為level數組的大小， 這個大小就是層的“高度” (redis t_zset.c 中的zslRandomLevel方法)。
當我們想查詢數據V的時候，可以先沿著這個新鏈表(最頂層Level)進行查找。當碰到比V大的節點或者下一個節為null時，下落到下一層進行查找(因為之后的節點只可能更大或者到頭)，下落到較小的level節點之后，比較節點值和V的大小，如果V較大，則繼續向前查找，如果V較小，則 通過后退指針"后退"查找，不斷繼續這個過程，直到找到對應的節點，或者V位于level1相鄰兩節點之間。
在查找過程中，由于新增加的層級包含更少的節點，故不再需要與鏈表中每個節點逐個進行比較才能找到對應的位置了，這就是跳躍表。
Redis中skiplist的定義
隨機獲取層數的函數
int zslRandomLevel(void){ int level=1; while((random()&0xFFFF)<(ZSKIPLIST_P*0xFFFF))level+=1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; }應用場景
排行榜 點擊數前幾的新聞等
參考鏈接
http://redisbook.com/
?
?
總結
以上是生活随笔為你收集整理的Redis之数据结构底层实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 滑动窗口算法学习(一)
- 下一篇： virtualbox+vagrant安装