成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

面試官：你看過Redis數據結構底層實現嗎？

作者：奔頭哥
數據庫 其他數據庫 Redis
面試中，redis也是很受面試官親睞的一部分。我向在這里講的是redis的底層數據結構，而不是你理解的五大數據結構。

面試中，redis也是很受面試官親睞的一部分。我向在這里講的是redis的底層數據結構，而不是你理解的五大數據結構。你有沒有想過redis底層是怎樣的數據結構呢，他們和我們java中的HashMap、List、等使用的數據結構有什么區別呢。

1. 字符串處理(string)

我們都知道redis是用C語言寫，但是C語言處理字符串和數組的成本是很高的，下面我分別說幾個例子。

沒有數據結構支撐的幾個問題

  1.  極其容易造成緩沖區溢出問題，比如用strcat()，在用這個函數之前必須要先給目標變量分配足夠的空間，否則就會溢出。
  2.  如果要獲取字符串的長度，沒有數據結構的支撐，可能就需要遍歷，它的復雜度是O(N)
  3.  內存重分配。C字符串的每次變更(曾長或縮短)都會對數組作內存重分配。同樣，如果是縮短，沒有處理好多余的空間，也會造成內存泄漏。

好了，Redis自己構建了一種名叫Simple dynamic string(SDS)的數據結構，他分別對這幾個問題作了處理。我們先來看看它的結構源碼： 

  1. struct sdshdr{  
  2.      //記錄buf數組中已使用字節的數量  
  3.      //等于 SDS 保存字符串的長度  
  4.      int len;  
  5.      //記錄 buf 數組中未使用字節的數量  
  6.      int free;  
  7.      //字節數組，用于保存字符串  
  8.      char buf[];  
  9. } 

再來說說它的優點：

  1.  開發者不用擔心字符串變更造成的內存溢出問題。
  2.  常數時間復雜度獲取字符串長度len字段。
  3.  空間預分配free字段，會默認留夠一定的空間防止多次重分配內存。

更多了解：https://redis.io/topics/internals-sds

這就是string的底層實現，更是redis對所有字符串數據的處理方式(SDS會被嵌套到別的數據結構里使用)。

2. 鏈表

Redis的鏈表在雙向鏈表上擴展了頭、尾節點、元素數等屬性。

2.1 源碼

ListNode節點數據結構： 

  1. typedef  struct listNode{  
  2.        //前置節點  
  3.        struct listNode *prev;  
  4.        //后置節點  
  5.        struct listNode *next;  
  6.        //節點的值  
  7.        void *value;    
  8. }listNode 

鏈表數據結構： 

  1. typedef struct list{  
  2.      //表頭節點  
  3.      listNode *head;  
  4.      //表尾節點  
  5.      listNode *tail;  
  6.      //鏈表所包含的節點數量  
  7.      unsigned long len;  
  8.      //節點值復制函數  
  9.      void (*free) (void *ptr);  
  10.      //節點值釋放函數  
  11.      void (*free) (void *ptr);  
  12.      //節點值對比函數  
  13.      int (*match) (void *ptr,void *key);  
  14. }list; 

從上面可以看到，Redis的鏈表有這幾個特點：

  1.  可以直接獲得頭、尾節點。
  2.  常數時間復雜度得到鏈表長度。
  3.  是雙向鏈表。

3. 字典(Hash)

Redis的Hash，就是在數組+鏈表的基礎上，進行了一些rehash優化等。

3.1 數據結構源碼

哈希表： 

  1. typedef struct dictht {  
  2.     // 哈希表數組  
  3.     dictEntry **table;  
  4.     // 哈希表大小  
  5.     unsigned long size;  
  6.     // 哈希表大小掩碼，用于計算索引值  
  7.     // 總是等于 size - 1  
  8.     unsigned long sizemask;  
  9.     // 該哈希表已有節點的數量  
  10.     unsigned long used;  
  11. } dictht; 

Hash表節點： 

  1. typedef struct dictEntry {  
  2.     // 鍵  
  3.     void *key;  
  4.     // 值  
  5.     union {  
  6.         void *val;  
  7.         uint64_t u64;  
  8.         int64_t s64;  
  9.     } v;  
  10.     // 指向下個哈希表節點，形成鏈表  
  11.     struct dictEntry *next;  // 單鏈表結構  
  12. } dictEntry; 

字典： 

  1. typedef struct dict {  
  2.     // 類型特定函數  
  3.     dictType *type;  
  4.     // 私有數據  
  5.     void *privdata;  
  6.     // 哈希表  
  7.     dictht ht[2];  
  8.     // rehash 索引  
  9.     // 當 rehash 不在進行時，值為 -1  
  10.     int rehashidx; /* rehashing not in progress if rehashidx == -1 */  
  11. } dict; 

可以看出：

  1.  Reids的Hash采用鏈地址法來處理沖突，然后它沒有使用紅黑樹優化。
  2.  哈希表節點采用單鏈表結構。
  3.  rehash優化。

下面我們講一下它的rehash優化。

3.2 rehash

當哈希表的鍵對泰國或者太少，就需要對哈希表的大小進行調整，redis是如何調整的呢？

  1.  我們仔細可以看到dict結構里有個字段dictht ht[2]代表有兩個dictht數組。第一步就是為ht[1]哈希表分配空間，大小取決于ht[0]當前使用的情況。
  2.  將保存在ht[0]中的數據rehash(重新計算哈希值)到ht[1]上。
  3.  當ht[0]中所有鍵值對都遷移到ht[1]后，釋放ht[0]，將ht[1]設置為ht[0]，并ht[1]初始化，為下一次rehash做準備。

3.3 漸進式rehash

我們在3.2中看到，redis處理rehash的流程，但是更細一點的講，它如何進行數據遷的呢？

這就涉及到了漸進式rehash，redis考慮到大量數據遷移帶來的cpu繁忙(可能導致一段時間內停止服務)，所以采用了漸進式rehash的方案。步驟如下：

  1.  為ht[1]分配空間，同時持有兩個哈希表(一個空表、一個有數據)。
  2.  維持一個技術器rehashidx，初始值0。
  3.  每次對字典增刪改查，會順帶將ht[0]中的數據遷移到ht[1],rehashidx++(注意：ht[0]中的數據是只減不增的)。
  4.  直到rehash操作完成，rehashidx值設為-1。

它的好處：采用分而治之的思想，將龐大的遷移工作量劃分到每一次CURD中，避免了服務繁忙。

4. 跳躍表

這個數據結構是我面試中見過最多的，它其實特別簡單。學過的人可能都知道，它和平衡樹性能很相似，但為什么不用平衡樹而用skipList呢?

4.1 skipList & AVL 之間的選擇

  1.  從算法實現難度上來比較，skiplist比平衡樹要簡單得多。
  2.  平衡樹的插入和刪除操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。
  3.  查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當。
  4.  在做范圍查找的時候，平衡樹比skiplist操作要復雜。
  5.  skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的。

可以看到，skipList中的元素是有序的，所以跳躍表在redis中用在有序集合鍵、集群節點內部數據結構。

4.2 源碼

跳躍表節點： 

  1. typedef struct zskiplistNode {  
  2.     // 后退指針  
  3.     struct zskiplistNode *backward;  
  4.     // 分值  
  5.     double score;  
  6.     // 成員對象  
  7.     robj *obj;  
  8.     // 層  
  9.     struct zskiplistLevel {  
  10.         // 前進指針  
  11.         struct zskiplistNode *forward;  
  12.         // 跨度  
  13.         unsigned int span;  
  14.     } level[];  
  15. } zskiplistNode; 

跳躍表： 

  1. typedef struct zskiplist {  
  2.     // 表頭節點和表尾節點  
  3.     struct zskiplistNode *header, *tail;  
  4.     // 表中節點的數量  
  5.     unsigned long length;  
  6.     // 表中層數最大的節點的層數  
  7.     int level;  
  8. } zskiplist; 

它有幾個概念：

4.2.1 層(level[])

層，也就是level[]字段，層的數量越多，訪問節點速度越快。(因為它相當于是索引，層數越多，它索引就越細，就能很快找到索引值)。

4.2.2 前進指針(forward)

層中有一個forward字段，用于從表頭向表尾方向訪問。

4.2.3 跨度(span)

用于記錄兩個節點之間的距離。

4.2.4 后退指針(backward)

用于從表尾向表頭方向訪問。

案例 

  1. level0    1---------->5  
  2. level1    1---->3---->5  
  3. level2    1->2->3->4->5->6->7->8 

比如我要找鍵為6的元素，在level0中直接定位到5，然后再往后走一個元素就找到了。

5. 整數集合(intset)

Reids對整數存儲專門作了優化，intset就是redis用于保存整數值的集合數據結構。當一個結合中只包含整數元素，redis就會用這個來存儲。 

  1. 127.0.0.1:6379[2]> sadd number 1 2 3 4 5 6  
  2. (integer) 6  
  3. 127.0.0.1:6379[2]> object encoding number  
  4. "intset" 

源碼

intset數據結構： 

  1. typedef struct intset {  
  2.     // 編碼方式  
  3.     uint32_t encoding;  
  4.     // 集合包含的元素數量  
  5.     uint32_t length;  
  6.     // 保存元素的數組  
  7.     int8_t contents[];  
  8. } intset; 

你肯定很好奇編碼方式(encoding)字段是干嘛用的呢？

  •  如果 encoding 屬性的值為 INTSET_ENC_INT16 ， 那么 contents 就是一個 int16_t 類型的數組， 數組里的每個項都是一個 int16_t 類型的整數值 （最小值為 -32,768 ，最大值為 32,767 ）。
  •  如果 encoding 屬性的值為 INTSET_ENC_INT32 ， 那么 contents 就是一個 int32_t 類型的數組， 數組里的每個項都是一個 int32_t 類型的整數值 （最小值為 -2,147,483,648 ，最大值為 2,147,483,647 ）。
  •  如果 encoding 屬性的值為 INTSET_ENC_INT64 ， 那么 contents 就是一個 int64_t 類型的數組， 數組里的每個項都是一個 int64_t 類型的整數值 （最小值為 -9,223,372,036,854,775,808 ，最大值為 9,223,372,036,854,775,807 ）。

說白了就是根據contents字段來判斷用哪個int類型更好，也就是對int存儲作了優化。

說到優化，那redis如何作的呢？就涉及到了升級。

5.1 encoding升級

如果我們有個Int16類型的整數集合，現在要將65535(int32)加進這個集合，int16是存儲不下的，所以就要對整數集合進行升級。

它是怎么升級的呢(過程)？

假如現在有2個int16的元素:1和2，新加入1個int32位的元素65535。

  1.  內存重分配，新加入后應該是3個元素，所以分配3*32-1=95位。
  2.  選擇最大的數65535, 放到(95-32+1, 95)位這個內存段中，然后2放到(95-32-32+1+1, 95-32)位...依次類推。

升級的好處是什么呢？

  1.  提高了整數集合的靈活性。
  2.  盡可能節約內存(能用小的就不用大的)。

5.2 不支持降級

按照上面的例子，如果我把65535又刪掉，encoding會不會又回到Int16呢，答案是不會的。官方沒有給出理由，我覺得應該是降低性能消耗吧，畢竟調整一次是O(N)的時間復雜度。

6. 壓縮列表(ziplist)

ziplist是redis為了節約內存而開發的順序型數據結構。它被用在列表鍵和哈希鍵中。一般用于小數據存儲。

引用https://segmentfault.com/a/1190000016901154中的兩個圖：

6.1 源碼

ziplist沒有明確定義結構體，這里只作大概的演示。 

  1. typedef struct entry {  
  2.      /*前一個元素長度需要空間和前一個元素長度*/  
  3.     unsigned int prevlengh;  
  4.      /*元素內容編碼*/  
  5.     unsigned char encoding;  
  6.      /*元素實際內容*/  
  7.     unsigned char *data;  
  8. }zlentry;  
  1. typedef struct ziplist{  
  2.      /*ziplist分配的內存大小*/  
  3.      uint32_t zlbytes;  
  4.      /*達到尾部的偏移量*/  
  5.      uint32_t zltail;  
  6.      /*存儲元素實體個數*/  
  7.      uint16_t zllen;  
  8.      /*存儲內容實體元素*/  
  9.      unsigned char* entry[];  
  10.      /*尾部標識*/  
  11.      unsigned char zlend;  
  12. }ziplist; 

第一次看可能會特別蒙蔽，你細細的把我這段話看完就一定能懂。

Entry的分析

entry結構體里面有三個重要的字段：

  1.  previous_entry_length: 這個字段記錄了ziplist中前一個節點的長度，什么意思？就是說通過該屬性可以進行指針運算達到表尾向表頭遍歷，這個字段還有一個大問題下面會講。
  2.  encoding:記錄了數據類型(int16? string?)和長度。
  3.  data/content: 記錄數據。

連鎖更新

previous_entry_length字段的分析

上面有說到，previous_entry_length這個字段存放上個節點的長度，那默認長度給分配多少呢?redis是這樣分的，如果前節點長度小于254,就分配1字節，大于的話分配5字節，那問題就來了。

如果前一個節點的長度剛開始小于254字節，后來大于254,那不就存放不下了嗎？ 這就涉及到previous_entry_length的更新，但是改一個肯定不行阿，后面的節點內存信息都需要改。所以就需要重新分配內存，然后連鎖更新包括該受影響節點后面的所有節點。

除了增加新節點會引發連鎖更新、刪除節點也會觸發。

7. 快速列表(quicklist)

一個由ziplist組成的雙向鏈表。但是一個quicklist可以有多個quicklist節點，它很像B樹的存儲方式。是在redis3.2版本中新加的數據結構，用在列表的底層實現。

結構體源碼

表頭結構：  

  1. typedef struct quicklist { 
  2.     //指向頭部(最左邊)quicklist節點的指針 
  3.     quicklistNode *head;  
  4.     //指向尾部(最右邊)quicklist節點的指針 
  5.     quicklistNode *tail;  
  6.     //ziplist中的entry節點計數器 
  7.     unsigned long count;        /* total count of all entries in all ziplists */  
  8.     //quicklist的quicklistNode節點計數器 
  9.     unsigned int len;           /* number of quicklistNodes */  
  10.     //保存ziplist的大小，配置文件設定，占16bits 
  11.     int fill : 16;              /* fill factor for individual nodes */  
  12.     //保存壓縮程度值，配置文件設定，占16bits，0表示不壓縮 
  13.     unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ 
  14. } quicklist; 

quicklist節點結構：

  1. typedef struct quicklistNode {  
  2.     struct quicklistNode *prev;     //前驅節點指針  
  3.     struct quicklistNode *next;     //后繼節點指針  
  4.     //不設置壓縮數據參數recompress時指向一個ziplist結構  
  5.     //設置壓縮數據參數recompress指向quicklistLZF結構  
  6.     unsigned char *zl;  
  7.     //壓縮列表ziplist的總長度 
  8.     unsigned int sz;                  /* ziplist size in bytes */  
  9.     //ziplist中包的節點數，占16 bits長度  
  10.     unsigned int count : 16;          /* count of items in ziplist */  
  11.     //表示是否采用了LZF壓縮算法壓縮quicklist節點，1表示壓縮過，2表示沒壓縮，占2 bits長度  
  12.     unsigned int encoding : 2;        /* RAW==1 or LZF==2 */  
  13.     //表示一個quicklistNode節點是否采用ziplist結構保存數據，2表示壓縮了，1表示沒壓縮，默認是2，占2bits長度  
  14.     unsigned int container : 2;       /* NONE==1 or ZIPLIST==2 */  
  15.     //標記quicklist節點的ziplist之前是否被解壓縮過，占1bit長度  
  16.     //如果recompress為1，則等待被再次壓縮  
  17.     unsigned int recompress : 1; /* was this node previous compressed? */  
  18.     //測試時使用  
  19.     unsigned int attempted_compress : 1; /* node can't compress; too small */  
  20.     //額外擴展位，占10bits長度  
  21.     unsigned int extra : 10; /* more bits to steal for future usage */  
  22. } quicklistNode; 

相關配置

在redis.conf中的ADVANCED CONFIG部分： 

  1. list-max-ziplist-size -2  
  2. list-compress-depth 0 

list-max-ziplist-size參數

我們來詳細解釋一下list-max-ziplist-size這個參數的含義。它可以取正值，也可以取負值。

當取正值的時候，表示按照數據項個數來限定每個quicklist節點上的ziplist長度。比如，當這個參數配置成5的時候，表示每個quicklist節點的ziplist最多包含5個數據項。

當取負值的時候，表示按照占用字節數來限定每個quicklist節點上的ziplist長度。這時，它只能取-1到-5這五個值，每個值含義如下：

-5: 每個quicklist節點上的ziplist大小不能超過64 Kb。（注：1kb => 1024 bytes）

-4: 每個quicklist節點上的ziplist大小不能超過32 Kb。

-3: 每個quicklist節點上的ziplist大小不能超過16 Kb。

-2: 每個quicklist節點上的ziplist大小不能超過8 Kb。（-2是Redis給出的默認值）

list-compress-depth參數

這個參數表示一個quicklist兩端不被壓縮的節點個數。注：這里的節點個數是指quicklist雙向鏈表的節點個數，而不是指ziplist里面的數據項個數。實際上，一個quicklist節點上的ziplist，如果被壓縮，就是整體被壓縮的。

參數list-compress-depth的取值含義如下：

0: 是個特殊值，表示都不壓縮。這是Redis的默認值。 1: 表示quicklist兩端各有1個節點不壓縮，中間的節點壓縮。 2: 表示quicklist兩端各有2個節點不壓縮，中間的節點壓縮。 3: 表示quicklist兩端各有3個節點不壓縮，中間的節點壓縮。 依此類推…

Redis對于quicklist內部節點的壓縮算法，采用的LZF——一種無損壓縮算法。 

 

責任編輯：龐桂玉 來源： Java知音
Redis數據結構數據庫
相關推薦

2021-09-01 09:44:16

Redis持久化配置

2025-04-08 00:00:00

@AsyncSpring異步

2024-08-29 16:30:27

2024-02-29 16:49:20

volatileJava并發編程

2019-09-27 08:53:47

Redis數據C語言

2020-07-02 07:52:11

RedisHash映射

2022-06-30 14:31:57

Java阻塞隊列

2024-03-14 14:56:22

反射Java數據庫連接

2021-11-02 09:05:25

Redis

2020-03-06 15:36:01

Redis內存宕機

2020-09-26 22:04:32

數據安全傳輸HTTPSHTTP 協議

2015-08-13 10:29:12

面試面試官

2024-04-09 10:40:04

2024-10-22 16:39:07

2020-11-10 13:47:29

String源碼長度限制

2022-06-15 15:14:17

Java公平鎖非公平鎖

2019-06-12 22:51:57

Redis軟件開發

2022-07-18 13:59:43

Redis單線程進程

2024-03-06 15:38:06

Spring微服務架構擴展組件

2019-04-17 15:35:37

Redis數據庫數據結構
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板： 成人国产精品久久 | 天天弄天天操 | 亚洲国产欧美一区二区三区久久 | 日本a v在线播放 | 日韩二三区| 亚洲欧洲成人av每日更新 | 6996成人影院网在线播放 | 成人影院午夜 | 日本一区精品 | 亚洲一区在线播放 | 激情欧美日韩一区二区 | 日本高清aⅴ毛片免费 | 欧美日韩高清在线观看 | 久久久久成人精品亚洲国产 | 国产成人短视频在线观看 | 日韩精品一区二区三区中文在线 | 国产精品成人国产乱 | 国产亚洲精品久久久久动 | 三级成人在线 | www.99re5.com| 亚洲欧美日韩国产综合 | 日韩免费网站 | 亚洲第一视频网 | 在线亚洲人成电影网站色www | 亚洲一级av毛片 | 瑞克和莫蒂第五季在线观看 | 成人免费共享视频 | 九九视频网| 97国产在线视频 | 成人av色 | 国产精品久久国产精品 | 欧美极品少妇xxxxⅹ免费视频 | 国产一区二区 | 综合精品在线 | 国产精品视频网址 | 97超碰免费 | 午夜激情视频在线 | 亚洲精品视频免费 | 成人日韩av | 国产成人综合网 | 日本欧美视频 |