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

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

• 字符串：set數(shù)字就是int，普通字符串就是sds(simple dynamic string)，一個沒有\(zhòng)0作為結束符的，不用內(nèi)存對齊的字符串數(shù)據(jù)結構。
• 隊列：ziplist + linkedlist。·ziplist（壓縮列表）：當列表的元素個數(shù)小于list-max-ziplist-entries配置（默認512個），同時列表中每個元素的值都小于list-max-ziplist-value配置時（默認64字節(jié)），Redis會選用ziplist來作為列表的內(nèi)部實現(xiàn)來減少內(nèi)存的使用。Redis3.2版本提供了quicklist內(nèi)部編碼，簡單地說它是以一個ziplist為節(jié)點的linkedlist，它結合了ziplist和linkedlist兩者的優(yōu)勢，為列表類型提供了一種更為優(yōu)秀的內(nèi)部編碼實現(xiàn)。

·linkedlist（鏈表）：當列表類型無法滿足ziplist的條件時，Redis會使用linkedlist作為列表的內(nèi)部實現(xiàn)。

redis> RPUSH numbers 1 "three" 5

image.png

image.png

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

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

• hash：是一種field - value類型的數(shù)據(jù)結構，而不是key-value，ziplist和hashtable。ziplist（壓縮列表）：當哈希類型元素個數(shù)小于hash-max-ziplist-entries配置（默認512個）、同時所有值都小于hash-max-ziplist-value配置（默認64字節(jié)）時，Redis會使用ziplist作為哈希的內(nèi)部實現(xiàn)，ziplist使用更加緊湊的結構實現(xiàn)多個元素的連續(xù)存儲，所以在節(jié)省內(nèi)存方面比hashtable更加優(yōu)秀。hashtable：當哈希類型無法滿足ziplist的條件時，Redis會使用hashtable（依托于dict，底層為hashtable）作為哈希的內(nèi)部實現(xiàn)，因為此時ziplist的讀寫效率會下降，而hashtable的讀寫時間復雜度為O（1）。

  
  
  image.png
  
  

  此時，鍵和值都是字符串對象。

image.png

redisObject對象

redis的所有對象都用如下數(shù)據(jù)結構進行表示：

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; // 引用計數(shù)，達到內(nèi)存回收
    void *ptr;
} robj;

image.png

對于Redis數(shù)據(jù)庫保存的鍵值對來說，鍵總是一個字符串對象，而值則可以是字符串對象、列表對象、哈希對象、集合對象或者有序集合對象的其中一種

image.png

2. redis幾種數(shù)據(jù)結構

redis的數(shù)據(jù)結構突出一個省內(nèi)存，一般都要加attributes關鍵字表示不需要內(nèi)存對齊，壓縮表這種結構更是這一精神的人為體現(xiàn)。

ziplist

image.png

image.png

字典

所謂的字典，歸根到底還是一個鍵值對的形式，

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屬性保存著鍵值對中的鍵，而v屬性則保存著鍵值對中的值，其中鍵值對的值可以是一個指針，或者是一個uint64_t整數(shù)，又或者是一個int64_t整數(shù)。
next屬性是指向另一個哈希表節(jié)點的指針，這個指針可以將多個哈希值相同的鍵值對連接在一次，以此來解決鍵沖突（collision）的問題。

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

但是，這個rehash動作并不是一次性、集中式地完成的，而是分多次、漸進式地完成的。
這樣做的原因在于，如果ht[0]里只保存著四個鍵值對，那么服務器可以在瞬間就將這些鍵值對全部rehash到ht[1]；但是，如果哈希表里保存的鍵值對數(shù)量不是四個，而是四百萬、四千萬甚至四億個鍵值對，那么要一次性將這些鍵值對全部rehash到ht[1]的話，龐大的計算量可能會導致服務器在一段時間內(nèi)停止服務。
因此，為了避免rehash對服務器性能造成影響，服務器不是一次性將ht[0]里面的所有鍵值對全部rehash到ht[1]，而是分多次、漸進式地將ht[0]里面的鍵值對慢慢地rehash到ht[1]。
以下是哈希表漸進式rehash的詳細步驟：
1）為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表。
2）在字典中維持一個索引計數(shù)器變量rehashidx，并將它的值設置為0，表示rehash工作正式開始。
3）在rehash進行期間，每次對字典執(zhí)行添加、刪除、查找或者更新操作時，程序除了執(zhí)行指定的操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]，當rehash工作完成之后，程序將rehashidx屬性的值增一。
4）隨著字典操作的不斷執(zhí)行，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash至ht[1]，這時程序將rehashidx屬性的值設為-1，表示rehash操作已完成。
漸進式rehash的好處在于它采取分而治之的方式，將rehash鍵值對所需的計算工作均攤到對字典的每個添加、刪除、查找和更新操作上，從而避免了集中式rehash而帶來的龐大計算量。

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

有序列表

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

image.png

壓縮表模型：

image.png

跳轉表模型：

image.png

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

數(shù)據(jù)結構如下：

/* 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 */ -- 就是用戶空間可見的
    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;

可以看到，所有的鍵值對都是通過dict進行存儲的，假如我們輸入如下命令：

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