前言

參考資料：《Redis設(shè)計(jì)與實(shí)現(xiàn) 第二版》；

本篇筆記按照書(shū)里的脈絡(luò)，將知識(shí)點(diǎn)分為四個(gè)部分。其中第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)與對(duì)象分為上中下篇，上篇包括：SDS、鏈表和字典；中篇包括跳躍表、整數(shù)集合和壓縮列表；下篇為對(duì)象；

上篇的鏈接：http://m.itdecent.cn/p/33f4cb95c008

下篇的鏈接：http://m.itdecent.cn/p/56efcba460a7

與本章相關(guān)的 Redis 命令總結(jié)在下篇文章，歡迎點(diǎn)擊收藏，本篇將不再重復(fù)：

《Redis常用命令及示例總結(jié)（API）》：http://m.itdecent.cn/p/f8eb9afaa908

1. 跳躍表

• 跳躍表支持平均 O(logN)、最壞 O(N) 復(fù)雜度的節(jié)點(diǎn)查找，還可以通過(guò)順序性操作來(lái)批量處理節(jié)點(diǎn)；
• 跳躍表的效率可以媲美平衡樹(shù)，實(shí)現(xiàn)比平衡樹(shù)簡(jiǎn)單；
• 跳躍表在Redis里只有兩個(gè)應(yīng)用：有序集合鍵的底層實(shí)現(xiàn)、集群節(jié)點(diǎn)中用作內(nèi)部數(shù)據(jù)結(jié)構(gòu)；

1.1 跳躍表與其節(jié)點(diǎn)的定義

• 跳躍表的定義，在redis.h/zskiplist結(jié)構(gòu)里：

  typedef struct zskiplist {
      //表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
      structz skiplistNode *header, *tail;
      //表中節(jié)點(diǎn)的數(shù)量（不包括表頭指針）
      unsigned long length;
      //表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)（不包括表頭指針）
      int level;
  } zskiplist;
  

• 跳躍表節(jié)點(diǎn)的定義，在redis.h/zskiplistNode結(jié)構(gòu)里：

  typedef struct zskiplistNode{
      //后退指針
      struct zskiplistNode *backwars;
      //分值
      double score;
      //成員對(duì)象
      robj *obj;
      //層
      struct zskiplistLevel{
          //前進(jìn)指針
          struct zskiplistNode *forward;
          //跨度
          unsigned int apan;
      } level[];
  } askiplistNode;
  

  • 節(jié)點(diǎn)中使用L1、L2、L3等來(lái)標(biāo)記節(jié)點(diǎn)的各個(gè)層，每個(gè)層有前進(jìn)指針和跨度；
    • 帶數(shù)字的箭頭為前進(jìn)指針，數(shù)字為跨度；
    • 一般來(lái)說(shuō)，層數(shù)越多訪問(wèn)其他節(jié)點(diǎn)速度越快；
    • 創(chuàng)建新跳躍表節(jié)點(diǎn)時(shí)，隨機(jī)生成介于1和32之間的數(shù)作為level數(shù)組的大?。?/li>
    • 跨度與遍歷無(wú)關(guān)，與排位rank有關(guān)。查找某個(gè)節(jié)點(diǎn)時(shí)，將沿途層相加，得到排位；
  • 帶BW字樣的為后退指針；
  • 1.0、2.0、3.0為分值，分值從小到大排列；
    • 當(dāng)分值相同時(shí)，成員對(duì)象在字典中排序小的靠近表頭節(jié)點(diǎn)；
  • o1、o2、o3等是成員對(duì)象，成員對(duì)象必須唯一；
  • 表頭節(jié)點(diǎn)也有后退指針、分值和成員對(duì)象，不會(huì)用到所以圖中沒(méi)有顯示；
  • 下圖中level為5是因?yàn)閛3對(duì)象有5層，為該跳躍表中最大層；
    [圖片上傳中...(跳躍表邏輯圖.png-3e98f2-1637400003565-0)]

1.2 跳躍表的API

2. 整數(shù)集合

• 整數(shù)集合 intset，其特點(diǎn)是從小到大保存整數(shù)且不會(huì)重復(fù)；
• 整數(shù)集合在Redis里的應(yīng)用：集合鍵的底層實(shí)現(xiàn)；

2.1 整數(shù)集合的實(shí)現(xiàn)

• 整數(shù)集合的定義，在intset.h/intset結(jié)構(gòu)中：

  typedef struct intset{
      //編碼方式
      uint32_t encoding;
      //集合包含的元素?cái)?shù)量
      uint32_t length;
      //保存元素的數(shù)組
      int8_t contents[];
  } intset;
  

  • contents聲明為 int8_t 類型的數(shù)組，但數(shù)組的真正類型取決于encoding屬性的值；

  encoding值	contents值	范圍
  INTSET_ENC_INT16	int16_t	-32768~32768
  INTSET_ENC_INT32	int32_t	-2147483648~2147483647
  INTSET_ENC_INT64	int64_t	-9223372036854775808~9223372036854775807

整數(shù)集合邏輯圖.png

2.2 整數(shù)集合的類型升級(jí)

• 當(dāng)新增的元素類型比整數(shù)集合現(xiàn)有元素的類型長(zhǎng)時(shí)，需要升級(jí)；
• 步驟：
  • 根據(jù)新元素類型，擴(kuò)展整數(shù)集合底層數(shù)組空間大小，并為新元素分配空間；
  • 將底層數(shù)組現(xiàn)有元素轉(zhuǎn)換成新元素相同的類型，在維持集合有序性質(zhì)不變情況下將轉(zhuǎn)換后的元素放置到正確位置上；
  • 將新元素添加到底層數(shù)組里；
• 因?yàn)樘砑有略乜赡軙?huì)引起升級(jí)，每次升級(jí)需要對(duì)所有元素進(jìn)行類型轉(zhuǎn)換，因此時(shí)間復(fù)雜度為O(N)；
• 因?yàn)橐鹕?jí)操作的新元素比現(xiàn)有元素長(zhǎng)，所以新元素要么添加到數(shù)組開(kāi)頭，要么數(shù)組末尾；
• 好處：
  • 靈活性：C語(yǔ)言通常不會(huì)將不同類型值放在同一個(gè)數(shù)據(jù)結(jié)構(gòu)里，Redis的升級(jí)使其可以；
  • 節(jié)約內(nèi)存；
• 整數(shù)集合不允許降級(jí)操作；

2.3 整數(shù)集合的API

3. 壓縮列表

• 壓縮列表 ziplist，其特點(diǎn)是管理小整數(shù)值和短字符串；
• 壓縮列表在Redis里的應(yīng)用：列表鍵與哈希鍵的底層實(shí)現(xiàn)之一；
• 壓縮列表的Redis為節(jié)省內(nèi)存而開(kāi)發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)；

3.1 壓縮列表的結(jié)構(gòu)

• 壓縮列表是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)；
  
  ziplist 示例圖.png

壓縮列表各組成部分說(shuō)明.png

3.2 壓縮列表節(jié)點(diǎn)的定義

• 節(jié)點(diǎn)的定義在ziplist.c/zlentry結(jié)構(gòu)里：

  typedef struct zlentry {
      // prevrawlen ：前置節(jié)點(diǎn)的長(zhǎng)度
      // prevrawlensize ：編碼 prevrawlen 所需的字節(jié)大小
      unsigned int prevrawlensize, prevrawlen;
      // len ：當(dāng)前節(jié)點(diǎn)值的長(zhǎng)度
      // lensize ：編碼 len 所需的字節(jié)大小
      unsigned int lensize, len;
      // 當(dāng)前節(jié)點(diǎn) header 的大小
      // 等于 prevrawlensize + lensize
      unsigned int headersize;
      // 當(dāng)前節(jié)點(diǎn)值所使用的編碼類型
      unsigned char encoding;
      // 指向當(dāng)前節(jié)點(diǎn)的指針
      unsigned char *p;
  } zlentry;
  

  • 可以用當(dāng)前節(jié)點(diǎn)地址減去prevrawlen的值獲得前置節(jié)點(diǎn)的首地址，可以由此實(shí)現(xiàn)從尾到頭的遍歷；
  • *p指向一個(gè)content，保存節(jié)點(diǎn)的值，值的類型和長(zhǎng)度由encoding決定；
  • encoding的屬性（下劃線表示留空，abcdx代表實(shí)際二進(jìn)制數(shù)據(jù)）：

encoding的編碼方式.png

3.3 連鎖更新

• 首先，壓縮列表節(jié)點(diǎn)有個(gè)prevrawlen屬性，用于記錄前一個(gè)節(jié)點(diǎn)的長(zhǎng)度，前一個(gè)節(jié)點(diǎn)的長(zhǎng)度變化會(huì)影響prevrawlen屬性的長(zhǎng)度取值（使用1個(gè)字節(jié)存儲(chǔ)前一個(gè)節(jié)點(diǎn)的長(zhǎng)度還是5個(gè)）；
• 假設(shè)所有結(jié)點(diǎn)（e1, e2......eN）長(zhǎng)度介于250~253字節(jié)之間，在表頭新增長(zhǎng)度大于等于254字節(jié)的new節(jié)點(diǎn)，因?yàn)閑1的prevrawlen屬性僅1字節(jié)，無(wú)法保存大于254的數(shù)字（new的長(zhǎng)度），因此需要擴(kuò)展為5字節(jié)長(zhǎng)，此時(shí)e1的長(zhǎng)度介于254~257字節(jié)之間。這樣，new引發(fā)e1的擴(kuò)展，e1引發(fā)e2的擴(kuò)展，形成連鎖更新；
• 刪除節(jié)點(diǎn)也可能引發(fā)連鎖更新；
• 連鎖更新的最壞時(shí)間復(fù)雜度為 O(N²)；
• 在實(shí)際中，連鎖更新造成的性能問(wèn)題幾率很低；

3.4 壓縮列表的API

• 最壞時(shí)間復(fù)雜度為O(N²)是因?yàn)榭赡芤l(fā)連鎖更新；

最后