1. redis的幾種基本數(shù)據(jù)類型

一般來(lái)說(shuō)祥绞，最常用的集中數(shù)據(jù)類型有五種，字符串鸭限，隊(duì)列蜕径，集合，有序集合败京，哈希兜喻。在較新的redis版本中還會(huì)有bitmap，hyperloglog,地理位置信息等赡麦。這一系列的數(shù)據(jù)結(jié)構(gòu)支撐了互聯(lián)網(wǎng)的很多業(yè)務(wù)朴皆，redis對(duì)外展示是一個(gè)簡(jiǎn)單的命令行，輸入指令返回信息泛粹，但是每一種數(shù)據(jù)類型在內(nèi)部實(shí)現(xiàn)的時(shí)候往往都會(huì)有幾種自定義數(shù)據(jù)結(jié)構(gòu)相結(jié)合去實(shí)現(xiàn)遂铡，（實(shí)際上，這也是很多其他c++開源工具的做法戚扳，造個(gè)輪子必須得從字符串開始就用自己實(shí)現(xiàn)的）忧便，簡(jiǎn)單介紹一下實(shí)現(xiàn)。

• 字符串：set數(shù)字就是int帽借，普通字符串就是sds(simple dynamic string)珠增，一個(gè)沒(méi)有\(zhòng)0作為結(jié)束符的，不用內(nèi)存對(duì)齊的字符串?dāng)?shù)據(jù)結(jié)構(gòu)砍艾。
• 隊(duì)列：ziplist + linkedlist蒂教。·ziplist（壓縮列表）：當(dāng)列表的元素個(gè)數(shù)小于list-max-ziplist-entries配置（默認(rèn)512個(gè)）脆荷，同時(shí)列表中每個(gè)元素的值都小于list-max-ziplist-value配置時(shí)（默認(rèn)64字節(jié)）凝垛，Redis會(huì)選用ziplist來(lái)作為列表的內(nèi)部實(shí)現(xiàn)來(lái)減少內(nèi)存的使用。Redis3.2版本提供了quicklist內(nèi)部編碼蜓谋，簡(jiǎn)單地說(shuō)它是以一個(gè)ziplist為節(jié)點(diǎn)的linkedlist梦皮，它結(jié)合了ziplist和linkedlist兩者的優(yōu)勢(shì)，為列表類型提供了一種更為優(yōu)秀的內(nèi)部編碼實(shí)現(xiàn)桃焕。

·linkedlist（鏈表）：當(dāng)列表類型無(wú)法滿足ziplist的條件時(shí)剑肯，Redis會(huì)使用linkedlist作為列表的內(nèi)部實(shí)現(xiàn)。

redis> RPUSH numbers 1 "three" 5

image.png

image.png

linkedlist編碼的列表對(duì)象在底層的雙端鏈表結(jié)構(gòu)中包含了多個(gè)字符串對(duì)象观堂，這種嵌套字符串對(duì)象的行為在稍后介紹的哈希對(duì)象让网、集合對(duì)象和有序集合對(duì)象中都會(huì)出現(xiàn)呀忧，字符串對(duì)象是Redis五種類型的對(duì)象中唯一一種會(huì)被其他四種類型對(duì)象嵌套的對(duì)象。

• 集合：inset + hashtable(依托于dict溃睹，底層是hashtable)
• 有序集合：ziplist + skiplist

• hash：是一種field - value類型的數(shù)據(jù)結(jié)構(gòu)而账，而不是key-value，ziplist和hashtable因篇。ziplist（壓縮列表）：當(dāng)哈希類型元素個(gè)數(shù)小于hash-max-ziplist-entries配置（默認(rèn)512個(gè)）泞辐、同時(shí)所有值都小于hash-max-ziplist-value配置（默認(rèn)64字節(jié)）時(shí)，Redis會(huì)使用ziplist作為哈希的內(nèi)部實(shí)現(xiàn)竞滓，ziplist使用更加緊湊的結(jié)構(gòu)實(shí)現(xiàn)多個(gè)元素的連續(xù)存儲(chǔ)铛碑，所以在節(jié)省內(nèi)存方面比hashtable更加優(yōu)秀。hashtable：當(dāng)哈希類型無(wú)法滿足ziplist的條件時(shí)虽界，Redis會(huì)使用hashtable（依托于dict，底層為hashtable）作為哈希的內(nèi)部實(shí)現(xiàn)涛菠，因?yàn)榇藭r(shí)ziplist的讀寫效率會(huì)下降莉御，而hashtable的讀寫時(shí)間復(fù)雜度為O（1）。

  
  
  image.png
  
  

  此時(shí)俗冻，鍵和值都是字符串對(duì)象礁叔。

image.png

redisObject對(duì)象

redis的所有對(duì)象都用如下數(shù)據(jù)結(jié)構(gòu)進(jìn)行表示：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount; // 引用計(jì)數(shù)，達(dá)到內(nèi)存回收
    void *ptr;
} robj;

image.png

對(duì)于Redis數(shù)據(jù)庫(kù)保存的鍵值對(duì)來(lái)說(shuō)琅关，鍵總是一個(gè)字符串對(duì)象，而值則可以是字符串對(duì)象讥蔽、列表對(duì)象涣易、哈希對(duì)象、集合對(duì)象或者有序集合對(duì)象的其中一種

image.png

2. redis幾種數(shù)據(jù)結(jié)構(gòu)

redis的數(shù)據(jù)結(jié)構(gòu)突出一個(gè)省內(nèi)存，一般都要加attributes關(guān)鍵字表示不需要內(nèi)存對(duì)齊响禽，壓縮表這種結(jié)構(gòu)更是這一精神的人為體現(xiàn)徒爹。

ziplist

image.png

image.png

字典

所謂的字典，歸根到底還是一個(gè)鍵值對(duì)的形式芋类，

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;


/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

key屬性保存著鍵值對(duì)中的鍵隆嗅，而v屬性則保存著鍵值對(duì)中的值，其中鍵值對(duì)的值可以是一個(gè)指針侯繁，或者是一個(gè)uint64_t整數(shù)胖喳，又或者是一個(gè)int64_t整數(shù)。
next屬性是指向另一個(gè)哈希表節(jié)點(diǎn)的指針巫击，這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一次禀晓，以此來(lái)解決鍵沖突（collision）的問(wèn)題精续。

隨著操作的不斷執(zhí)行，哈希表保存的鍵值對(duì)會(huì)逐漸地增多或者減少粹懒，為了讓哈希表的負(fù)載因子（load factor）維持在一個(gè)合理的范圍之內(nèi)重付，當(dāng)哈希表保存的鍵值對(duì)數(shù)量太多或者太少時(shí)，程序需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮凫乖。
Redis對(duì)字典的哈希表執(zhí)行rehash的步驟如下：
1）為字典的ht[1]哈希表分配空間确垫，這個(gè)哈希表的空間大小取決于要執(zhí)行的操作，以及ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量（也即是ht[0].used屬性的值）：
·如果執(zhí)行的是擴(kuò)展操作帽芽，那么ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2 n（2的n次方冪）删掀；
·如果執(zhí)行的是收縮操作，那么ht[1]的大小為第一個(gè)大于等于ht[0].used的2 n导街。
2）將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上面：rehash指的是重新計(jì)算鍵的哈希值和索引值披泪，然后將鍵值對(duì)放置到ht[1]哈希表的指定位置上。
3）當(dāng)ht[0]包含的所有鍵值對(duì)都遷移到了ht[1]之后（ht[0]變?yōu)榭毡恚┌峁澹尫舎t[0]款票，將ht[1]設(shè)置為ht[0]，并在ht[1]新創(chuàng)建一個(gè)空白哈希表泽论，為下一次rehash做準(zhǔn)備艾少。

但是，這個(gè)rehash動(dòng)作并不是一次性翼悴、集中式地完成的缚够，而是分多次、漸進(jìn)式地完成的鹦赎。
這樣做的原因在于谍椅，如果ht[0]里只保存著四個(gè)鍵值對(duì)，那么服務(wù)器可以在瞬間就將這些鍵值對(duì)全部rehash到ht[1]钙姊；但是毯辅，如果哈希表里保存的鍵值對(duì)數(shù)量不是四個(gè)，而是四百萬(wàn)煞额、四千萬(wàn)甚至四億個(gè)鍵值對(duì)思恐，那么要一次性將這些鍵值對(duì)全部rehash到ht[1]的話，龐大的計(jì)算量可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)膊毁。
因此胀莹，為了避免rehash對(duì)服務(wù)器性能造成影響，服務(wù)器不是一次性將ht[0]里面的所有鍵值對(duì)全部rehash到ht[1]婚温，而是分多次描焰、漸進(jìn)式地將ht[0]里面的鍵值對(duì)慢慢地rehash到ht[1]。
以下是哈希表漸進(jìn)式rehash的詳細(xì)步驟：
1）為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表荆秦。
2）在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx篱竭，并將它的值設(shè)置為0，表示rehash工作正式開始步绸。
3）在rehash進(jìn)行期間掺逼，每次對(duì)字典執(zhí)行添加、刪除瓤介、查找或者更新操作時(shí)吕喘，程序除了執(zhí)行指定的操作以外，還會(huì)順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]刑桑，當(dāng)rehash工作完成之后氯质，程序?qū)ehashidx屬性的值增一。
4）隨著字典操作的不斷執(zhí)行祠斧，最終在某個(gè)時(shí)間點(diǎn)上闻察，ht[0]的所有鍵值對(duì)都會(huì)被rehash至ht[1]，這時(shí)程序?qū)ehashidx屬性的值設(shè)為-1琢锋，表示rehash操作已完成蜓陌。
漸進(jìn)式rehash的好處在于它采取分而治之的方式，將rehash鍵值對(duì)所需的計(jì)算工作均攤到對(duì)字典的每個(gè)添加吩蔑、刪除、查找和更新操作上填抬，從而避免了集中式rehash而帶來(lái)的龐大計(jì)算量烛芬。

rehash總結(jié)：分配新空間，慢慢復(fù)制飒责，記錄復(fù)制位置赘娄，在漸進(jìn)式rehash執(zhí)行期間，新添加到字典的鍵值對(duì)一律會(huì)被保存到ht[1]里面宏蛉，而ht[0]則不再進(jìn)行任何添加操作遣臼，這一措施保證了ht[0]包含的鍵值對(duì)數(shù)量會(huì)只減不增，并隨著rehash操作的執(zhí)行而最終變成空表拾并。

有序列表

兩種實(shí)現(xiàn)方式：ziplist揍堰，dict + skiplist。
redisObject模型：

image.png

壓縮表模型：

image.png

跳轉(zhuǎn)表模型：

image.png

3 單機(jī)數(shù)據(jù)庫(kù)

數(shù)據(jù)結(jié)構(gòu)如下：

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */ -- 就是用戶空間可見(jiàn)的
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

可以看到嗅义，所有的鍵值對(duì)都是通過(guò)dict進(jìn)行存儲(chǔ)的屏歹，假如我們輸入如下命令：

redis> SET message "hello world"
OK
redis> RPUSH alphabet "a" "b" "c"
(integer)3
redis> HSET book name "Redis in Action"
(integer) 1
redis> HSET book author "Josiah L. Carlson"
(integer) 1
redis> HSET book publisher "Manning"
(integer) 1

則redisDb如下所示：

image.png