不啰嗦，我們直接開始！

一、redis底層資料結構

1.sds結構

Redis中并沒有直接使用C語言中的字串，而是定義了一種簡單動態字串（simple dynamic string）作為Redis的默認字串實作，簡稱SDS，

在Redis中，C語言的字串只會用于一些無需對字串修改的地方，如日志列印等，

而Redis默認的字串實作是SDS，如set命令中的key底層即是一個SDS，而value如果是一個字串型別，則底層也是SDS，如果value是串列，則串列里的每個元素底層都是SDS，

除了set命令外，SDS還被用作緩沖區：AOF模塊中的AOF緩沖區，客戶端狀態中的輸入緩沖區等都是SDS實作的，

SDS定義

SDS的定義在Redis原始碼的src目錄下的sds.h和sds.c檔案中，定義如下：

typedef struct sdshdr{
     //記錄buf陣列中已使用位元組的數量
     //等于 SDS 保存字串的長度
     unsigned int len;
     //記錄 buf 陣列中未使用位元組的數量
     unsigned int free;
     //位元組陣列，用于保存字串
     char buf[];
}

redis使用類似c的方法存盤字串，用'\0'來結尾，'\0'并不用來表示具體的字符，只是一個結尾符，
使用free可以減少處理程序中可能遇到的記憶體申請和釋放的次數，

sds擴容

• 當字串進行初始化的時候，buf=len+1,就是加上'\0'作為長度

• 當字串預計小于1mb的時候，擴容后buf大小=預期長度*2+1，既不考慮在雨后的'\0'，buf加倍

• 當字串預計大于1mb的時候，buf會預留1mb的空間，buf用2倍擴容，但是預留1mb，

2、list結構

typedef struct list{
     //表頭節點
     listNode *head;
     //表尾節點
     listNode *tail;
     //鏈表所包含的節點數量
     unsigned long len;
     //節點值復制函式
     void (*free) (void *ptr);
     //節點值釋放函式
     void (*free) (void *ptr);
     //節點值對比函式
     int (*match) (void *ptr,void *key);
}list;

typedef  struct listNode{
       //前置節點
       struct listNode *prev;
       //后置節點
       struct listNode *next;
       //節點的值
       void *value;  
}listNode

由于在list的結構中定義了頭尾指標和長度，可以讓push/pop、或者是求長度的操作復雜度只有o(1)，
使用了void*的操作實作了多型,可以保存不同的型別的資料，

3、ziplist結構

<bytes><tail><len><entry><entry><end>
bytes是ziplist的總長度，tail是尾部元素，len是表示元素的長度，entry是一個個物體

<entry>會有以下的部分組成
<prelen><encode><content>
prelen是前一個物體的長度，encode是指當前資訊的編碼資訊，content是指編碼過的資訊

4、hashtable結構

typedef struct dictht{
     //哈希表陣列
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩碼，用于計算索引值
     unsigned long sizemask;
     //該哈希表已有節點的數量
     unsigned long used;

}dictht

typedef struct dictEntry{
     void *key;
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
     struct dictEntry *next;
}dictEntry

這里的hash很像java中的hashmap，桶的個數也是2的n次方，方便使用&進行快速運算取模，

hashtable擴容和縮容

負載因子=哈希表中已有元素和哈希桶數的比值

• 負載因子小于1一定不擴容

• 負載因子大于5一定擴容

• 負載因子如果在1-5之間，redis沒有進行save/rewrite的操作就會擴容

• 負載因子如果是0.1，那么會進行縮容

擴容會變成原來的2倍，縮容會變成原來的1/2，

5、intset結構

typedef struct intset{
     //編碼方式
     uint32_t encoding;
     //集合包含的元素數量
     uint32_t length;
     //保存元素的陣列
     int8_t contents[];

}intset

默認其中存放的資料是從小到大有序的，len表示長度,encode表示編碼方式，int8_t不保存對應的值，真正的型別由encoding決定

插入的時候先二分查找到插入的位置（O(log(N))），然后在對插入位置后面所有的元素往后移動一個位置，復雜度(O(N))

• 當插入的一個資料比原有的資料的位元組都大，那么整個資料中的所占用的位元組都會進行升級，

6、skiplist結構

跳表如下圖

image.png

typedef struct zskiplistNode {

     struct zskiplistLevel{

       struct zskiplistNode *forward;

       unsigned int span;

     }level[];


     struct zskiplistNode *backward;

     double score;

     robj *obj;

} zskiplistNode

typedef struct zskiplist{
     //表頭節點和表尾節點
     structz skiplistNode *header, *tail;
     //表中節點的數量
     unsigned long length;
     //表中層數最大的節點的層數
     int level;

}zskiplist;

• 跳表有很多層組成，

• 每一層都是有序的，除了最后一層都只包含部分資料

• 最底層的包含所有的資料

搜索：從最上層開始搜索，如果發現當前層的最大值小于搜索的值，那么就去下一層尋找，往復如此的操作，直到找到最下面的一層，復雜度（O（Log(N)））

redis上層資料結構和底層資料結構對應

• string的資料使用string，

• list內部使用linkedlist和ziplist，當數量比較小的時候會使用ziplist來減少記憶體使用，否則使用linkedlist

• map使用hashtable和ziplist，當資料量比較小的時候使用map,否則使用ziplist

• set在資料都是整數型別時，使用intset,否則使用hashtable

• sort-set使用ziplist和skiplist+hashtable，當資料量小的時候使用ziplist，否則使用skiplist+hashtable

二、redis持久化

1、全量寫入的方式

1、save模式

save模式可以被客戶端觸發，也可以在關閉redis的時候出發，當被觸發的時候，作業行程開始去串行化地執行一個一個的
命令，當前的無法在處理客戶端的請求，因此會花很多的時間，但是由于不在處理客戶端的請求，因此整個快照有一致性的，

2、bgsave模式

bgsave模式可以被客戶端觸發，也可以通過配置定時任務觸發，bgsave模式會fork一個子執行緒出來，在子執行緒啟動以后修改一些狀態后
redis的主行程進行處理后續的命令，寫快照的任務會和主執行緒并發執行，因此可以繼續提供對外服務，當子執行緒完成任務后會通知
主行程，在之后的資料修改則不會寫入快照，因為子執行緒是父執行緒fork出來的，會設計到父行程的記憶體復制，因為有增加大量的記憶體開銷，
fork也會阻塞主行程，

3、全量恢復流程

redis啟動進入事件處理主回圈，會全量把快照中的資料全部讀出來放到記憶體中，之后在來處理請求，因為在加載快照的程序中redis是不處理客戶端請求的，

4、增量性質的持久化

增量保存的是每一次變化，給定初始狀態，經常相同的變化操作后，最終的狀態也是一樣的，因此可以根據增量持久化資料，通過對一個
初始狀態進行變化回復出最終的狀態，

2、增量寫入的方式

每次主回圈處理完寫命令以后，通過propagate函式觸發，propagate方法將當前的命令append到redisServer物件中的aof_buf中，
在主回圈進入下次select之前，redis通過flushAppendOnlyFile將aof_buf的內容write到的aof檔案中，但是存在一個問題write只是寫入到作業系統的快取
中，具體什么時候落盤不一定，只有呼叫fsync()才能強制落地，

1、AOF的三種策略

• always：每次呼叫flushAppendOnlyFile直接在呼叫一次fsync方法，強制資料落地，但是會降低redis的吞吐能力，寫操作可能變成瓶頸，
  但是是安全性最高的，

• every secord：每秒異步的觸發一次fsync方法，fsync方法會呼叫bio的中的執行緒來處理，

• no：不直接呼叫，一切有作業系統決定，完全不可控

2、增量恢復流程

AOF也和全量一樣，當redis啟動進入事件處理主回圈之前進行處理，但是存在AOF，redis會選擇增量不是全量，因為增量的資料是持續的寫入，因此和
全量相比資料更加新一些，會寫程序就是把命令在重新執行一遍，只有執行完成以后，redis主回圈才會繼續接受客戶端命令，

不啰嗦，文章結束，期待三連！