天天看點
傳回

REDIS五種資料結構基礎資料結構對象redisObject其他機制

基礎資料結構

string實作：SDS(Simple Dynamic String) 簡單動态字元串

結構：

  • int len; 字元串長度
  • int free; 空閑長度
  • char[] buf 存儲字元串的字元數組，采取c語言風格。

buf特點：

  • 采用c語言存儲字元串的風格，在字元數組後多開辟一個位元組空間，用來存儲空字元串

    \0

     , 表示結束符【原本擁有free和len的他是不需要的，但是為了統一還是設了]
  • 好處是可以直接使用c語言關于字元串的函數。

采用SDS的優點：

  • o(1)時間擷取長度，而無需周遊數組。
  • 避免記憶體溢出。c語言動态數組添加内容都會預設空間是足夠的，若是空間不足就會溢出，是以需要手動添加記憶體。sds會在添加之前先檢查記憶體是否足夠，如不足會首先通過api自動添加記憶體。
  • 避免大量的空間配置設定行為。c數組在添加新元素會首先進行記憶體擴充，這是一個非常耗時的工作，需要調用os來進行。而數組庫資料是進行需要進行修改的，是以添加操作很常見，sds可以對其進行優化。

sds會在空間判斷不足做這樣的行為：

（1）若所需空間不足1m, 會首先擴充到需要的大小【如需要13byte，就給13byte】，在多配置設定一倍+1byte空間【1byte還是作為結束位置】

（2）若所需空間超過1m，會多配置設定1m + 1byte

若空間充足，sds不會進行擴充

是以，對于sds，他将原本擴容n次就需要配置設定n次空間降低到了最多隻需要配置設定n次空間。

  • 避免了記憶體洩漏。c數組若某些單元不再使用需要手動釋放，否則會記憶體溢出。sds會自動對這些無用空間進行處理
sds會将這些垃圾空間變成free的一部分，下次擴容可以直接使用這些空間【這樣也減少了空間配置設定的次數】
  • 二進制安全。c字元串不能存儲

    \0

     ，是以則會導緻之後的字元失效【這是

    字元數組

     的缺陷】，sds由于要存儲不僅僅是字元，還有大量的位元組資料【如圖檔等等】，是以必須要保證空字元不被過濾，sds對位元組流可以進行原樣的儲存，是以不是字元數組，而是

    位元組數組
  • 複用c字元串函數。由于\0的存在可以透明的使用c語言的某些字元串庫函數而不用另寫。

list實作：LinkedList 

typed struct listNode {
    void *vlaue; //void指針存儲值
    listNode *prev;
    listNode *next;
}
typed struct list {
	listNode *head; //頭結點
    listNode *tail; //尾結點
    unsinged long len; //連結清單長度
    void dup(); //複制節點
    int match(); //比對兩個節點
    void free(); //釋放節點
}

特點：

  • 雙端：擁有prev與next兩個指針擷取前後節點;
  • 無環：tail的下個節點和head的上一個節點都為空；
  • 頭尾指針：通過head和tail可以在o(1)時間擷取頭尾節點；
  • 多态：

    void*

     的值類型可以保證存儲任意類型的值；
  • o(1)時間擷取長度。

set實作：dict(哈希表/字典)

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-GsTrn8lG-1615539216854)(https://i.loli.net/2021/03/08/8lv1b9aEBQYPZnA.png)]

set由三個結構共同組合成：

  1. dictEntry; //哈希表節點

每個桶位上的連結清單節點，擁有key, value, next三個值，指向同hash的下個節點。

需要注意的是：沒有tail指針，是以為了保證插入效率隻能采取頭插法

  1. dictht; //哈希表結構 
typed struct dictht {
  	int size; //哈希表最大容量；
    int sizemask; //計算哈希時候的掩碼
    int use; //目前使用長度
    dictEntry[] table; //哈希節點數組，存儲每個初始桶位
}
  1. dict; //字典結構 
    typedef struct dictType {
    dictType type; //指定類型的函數；
    void *privdata; // 私有資料
    int trehashidx; //rehash索引，進行rehash到達的位置，不rehash就為-1，為0表示rehash開始。
    dictht ht[2]; //哈希表；之是以兩個位置，0是普通存儲位，1是rehash時候的複制位置；
}

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-UPitiGgt-1615539216856)(https://i.loli.net/2021/03/08/FxRKgeTD4c6vrYj.png)]

  • 雜湊演算法：
    1. hash:
      • hash算法是為了計算dictEntry的插入數組的位置，并采取頭插法插入。
      • 過程：
        • 計算hash：通過key計算hashcode hashFuntion(key)。計算hashCode采用

          Murmur2算法
        • 通過hashCode與sizemask得到插入下标：

          index = hashCode & sizemask;

          這是和java的hashMap同樣的方式：

          隻要将table長度設為2的整數倍，就可以通過hashcode & (len - 1)映射到表的下标上，與的運算速度遠高于取餘。

    2. rehash：
      • rehash是對運作過程中hashEntry數量增減而适時調整哈希表容量以穩定負載因子的行為，分為擴容和縮減。
        • 擴容：
          • 當不在執行

            BGSAVE與BREWRITEDAOF

             指令時，負載因子達到1.0就進行擴容；
          • 當在執行這兩個指令時，負載因子達到5.0開始擴容
          擴容過程：
          1. 初始化ht[1], 表長初始化為

            大于ht[0].use * 2 的最小的那個二進制整數幂

             【如，現在有3個HashEntry，那ht[1]就會初始化長度為8】
          2. 對每個ht[0]上的dictEntry進行rehash【根據新的表長生成的sizemask進行重新計算下标】,并将所有entry的引用移動到ht[1]的下标桶位處；
          3. 将ht[1]修改為新的ht[0],将原本ht[0]釋放。
    [外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-aPI3ZBnQ-1615539216859)(https://i.loli.net/2021/03/08/eCyzbTj4KJX6ZsE.png)]
    • 縮減：
      • 當負載因子低到0.1以下，會進行縮減，容量依然為

        大于ht[0].use * 2 的最小的那個二進制整數幂

    • load_factor = ht[0].used / ht[0].size;
      關于

      BGSAVE

       與

      BGREWRITEAOF

      指令時提高loadfactor的上限：

      這是為了避免在寫時複制時不必要的記憶體寫入。

  • 漸進式rehash:
    • 當哈希表資料量很大時，采用一次移動所有entry的方式會導緻伺服器暫停，非常影響體驗。redis采取漸進式rehash的方式，一次轉移一部分entry，在一段時間之後才會完成轉移；
      • 當達到rehash條件時，開始進行rehash，将rehashidx指派為0，表示開始；
      • 當出現對ht[0]的delete, find, update操作時，會執行一次rehashidx上的rehash，将這個桶位上的entry全部複制到ht[1]上重寫經過hash計算的桶位上，并将rehashidx + 1；
      • 當新插入entry時，隻會插入到ht[1]上，是以ht[0]隻減不增，最終會為空。
    [外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-5FfOfCjh-1615539216862)(https://i.loli.net/2021/03/08/NlvwazbXSEf124g.png)]

sortedSet底層實作：skiplist(跳躍表)

跳躍表是一種有序的鍊狀結構，用來代替平衡樹實作平均查找長度o(logn)最差查找長度o(n)的資料查找。

跳躍表底層通過兩個結構：跳躍表節點zskiplistNode和跳躍表zskiplist實作。

  • zskiplistNode有如下屬性：
    • 分數score:用來進行排序的資料；【可重複，重複後按照obj字典序排列】
    • 對象obj：存儲實際資料的指針【不可重複】
    • level[]：層級數組，每個數組單元都指向存儲的其他層【如下标2就指向層數為2的節點】， level具有兩個指針：
      • forward：前進指針，指向下個位置；
      • backward：後退指針

    • 跨度

       ：配合level的forward指針使用，表示level指向的指針離目前節點在排序序列之間的距離，用于統計排列位置。
  • zskiplist有如下屬性：
    • head, tail :頭尾節點
    • level：層數最高的節點的層數【此“層數”是說他是level幾】；
    • length: 節點數目，不包括頭結點
  • 注：
    • 頭結點沒有level[]以外其他屬性指派，但是也存在，隻是沒有值。
    • 頭結點不參與排序與計數。
    • 跨度不是用來周遊的，而是用來計算排序位置的：
      • 如，從level1開始，查找level4的指針，若level1的節點有level4的指針，則該指針上跨度為3，則level4的排序位置為 1 + 3 = 4； 若每次跨度隻為1，那麼隻能一次增長一個，從level1到l2，l3, l4, 也是4.

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-Vst9CmSv-1615539216864)(https://i.loli.net/2021/03/08/xfiHGtXCU9enO4D.png)]

L5節點位于頭結點跨度為3的位置，而頭結點計數視為0，是以L5位于第三層。
  • 分值可以相等，之後按照對象字典序排序。
  • level[]的size稱為節點的層數，或者層的高度，與節點數量無關，是随機生成的一個

    1~32

     的數【建立節點随機生成】
  • 幂次定律：
    • level[]存儲的層數越高，同樣的，周遊速度越快。

總結：

簡單說，跳躍表就是一種存儲多個序列其他節點位址的資料結構，其快讀通路由其level的指針及跨度實作。

集合 實作方式的一種：整數集合

當集合存儲元素全為整數時，采用。

特點：

  • 存儲元素有序；
  • 具有16, 32, 64三種類型，每次隻會使用一種。

結構：

  • encoding:編碼方式【uin16_t, …]
  • length：集合元素個數
  • contents[] :存儲元素的數組，有序排列。初始為uint8_t[], 随着插入元素的類型進行

    更新

     。

更新：

當新插入的元素的範圍大于目前數組的單元範圍時，會将整個數組的存儲範圍提升。

如在16位整形中插入65536，會引發其向着32位更新。

更新過程：

  • 重新劃分空間：按照encoding * length 來劃分空間。
  • 按照從右向左的順序移動元素【如下圖移動3的過程】

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-dPZ9lL8T-1615539216866)(https://i.loli.net/2021/03/08/4LlTtyzZ2J1SCAM.png)]

好處：

  • 節省空間，若沒有大的資料，可以用小範圍控制，隻在合适時候更新。
  • 避免出錯，c語言是靜态語言，本身不允許高類型資料進入低類型空間，更新避免了這種問題。

注意：

  • 隻有全部是整數才能使用整形數組；
  • 隻能更新不能降級；
  • 引起更新的元素要麼在最開頭，要麼在最結尾；
  • 集合不允許重複，存儲資料有序。

其他結構

壓縮清單

為了減少空間的浪費，

節省記憶體

，對某些簡單的鍵使用壓縮清單存儲。

主要用于list和hash結構，用來存儲較短的整形以及位元組數組。

壓縮清單是一個

雜表

，作為清單結構，其中存儲的元素類型可以是各式各樣的，他通過開頭的标志位已經标志位後面的數值來辨別這塊節點的類型以及長度。

屬性；

  • zlbytes:整個壓縮清單所占記憶體空間；
  • zltail：清單尾節點首位址。
  • zllen: 節點數量；
  • entry。。。 主體資料部分，由各種類型的資料節點組成；
  • zlend:标志位，辨別壓縮清單的結束位置。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-mKgFcIgK-1615539216868)(https://i.loli.net/2021/03/08/kcbXIf9MxtEVzyr.png)]

節點entry屬性：

  • previous_entry_length

     标記上個節點的長度【用于從後往前周遊：

    目前節點首位址 - 這個

     就是上個節點首位址】；
    previous_entry_length的長度在前節點小于254位元組時為1位元組，大于則為5位元組。
  • encoding:标記目前節點的類型、大小資訊。
[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-p6MN68L8-1615539216869)(https://i.loli.net/2021/03/08/xUuZLHynIsGq53O.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-autE2p5i-1615539216870)(https://i.loli.net/2021/03/08/JbsvUEhAHjp6eWO.png)]

連鎖更新：

  • 由于一個previous_entry_length在前節點小于254位元組存儲一個位元組内容，一旦前面插入了大于254的單元，就需要将自己的previous_entry_length + 1，是以現在需要5位元組，同樣，後面也會因為前面長度突然增加到254以上導緻更新previous_entry_length，如果大家都是254，就會一直連鎖下去，但這種可能性很低。
  • 這種情況下，導緻插入複雜度為o(N^2).

對象

上面提到了大部分redis存儲采用的資料結構。但是實際上redis并不直接采用這些結構，而是通過

組合成對象

的方式間接的使用。

組成的對象有五種：

  • string
  • set
  • sortedset
  • list
  • hash

可以通過

type 鍵

來擷取鍵的類型。

使用對象的好處：

  • 可以使用

    引用計數法

     , 對使用不到的對象進行回收；
  • 實作了

    對象共享機制

     ，多個資料庫可以共用同一個對象資料。

redis的對象采用結構redisObject描述：

typedef struct redisObject {
    type; // 表示對象類的類型【即五種之一】
    encoding; // 實作這種結構采用的編碼方式【每種結構都至少有兩種編碼，各有優勢】
    *ptr; // 指向存儲這種編碼的資料結構的位置。【如采用sds的raw方式實作的字元串，會指向raw的資料結構】
}
  • 通常說的“xx鍵”指的是一個值為xx類型鍵值對，因為redis的鍵都是字元串

對象編碼類型如下：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-nwrkjBvw-1615539216871)(https://i.loli.net/2021/03/08/4Gun78vqNgidbEf.png)]

任何對象的實作方式都無外乎這8種的組合。

五種類型采用的編碼方式列舉：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-6g5EVN1N-1615539216873)(https://i.loli.net/2021/03/08/vhVBKs76HPm5oES.png)]

如圖，除了string有三種，其他都是兩種。

redis可以根據不同的應用場景以及操作需求進行不同實作方式的切換。

string

string采用三種方式：

int， 存儲一個long以下的整形時使用；

embstr， sds的一種，申請和釋放記憶體都隻進行一次，效率高。但是

隻讀

。long double以下的浮點數以及32位以下的字元串采用

raw，sds一種，申請和釋放記憶體都需要進行兩次，可以存儲任何類型字元串，支援讀寫。預設用來存儲long double存儲不了的浮點數以及32位以上的字元串。

  • int隻能存儲數字字元，并且對這個數字字元的append（修改）會首先轉換為raw，之後也不會轉回來。
  • float類型使用embstr和raw，在進行浮點運算時會轉回浮點型，操作完成後轉回字元串【如 incrybyfloat pi 2.0, 将pi + 2.0】【他不會直接轉為raw，而是之前用embstr就用embstr】
  • 由于embstr隻讀，是以對embstr做任何修改都會導緻轉換為raw【浮點操作不屬于字元串操作】

字元串指令的流程：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-ai7eqrHR-1615539216874)(https://i.loli.net/2021/03/08/UXlp4A1v6PMBi5R.png)]

list

list有兩種編碼方式：ziplist與linklist

ziplist适合存儲整形和短數組，可以節省空間。

linklist隻有o(n)的存取速度，但是存儲數量可以無限延伸。

兩者的頭尾節點存取速度都是O(1).

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-vBnLqT7s-1615539216875)(https://i.loli.net/2021/03/09/P9mcSJr3Qnsup1g.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-s0KgA63h-1615539216876)(https://i.loli.net/2021/03/09/1cO4zPpVwWURICo.png)]

StringObject是對String存儲結構的縮寫，其實是：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-jWkyCfKo-1615539216876)(https://i.loli.net/2021/03/09/wG5dIJYNztciMUE.png)]

上面隻有存儲鍵值對的鍵的時候使用了這種結構。

存儲時會優先使用zipList，但是不滿足下面兩個條件之一就會引發轉化為linklist，即

編碼轉化

(1)每個字元串的值不超過64位元組。

(2)數組的

位元組量

大于512byte；

hash

hash有兩種編碼：ziplist以及dict

ziplist采用線性存儲，每次插入鍵值對都會插入到表尾節點，同樣，查找一個元素也隻能采用o(N)周遊，但是由于存儲量小，也很快。

dict是字典的資料結構，采取hashCode映射數組下标的方式，存取速度很快。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-uwEnHT2U-1615539216878)(https://i.loli.net/2021/03/09/Eirxl2mZOC6FRPs.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-pO0pzoKR-1615539216879)(https://i.loli.net/2021/03/09/1S5wsZTqu98Yhki.png)]

在以下條件都滿足時，使用ziplist存儲：

(1)存儲的每個鍵值對的鍵和值的字元串都小于64bytes；

(2)存儲數組長度小于等于512byte。

set

set采用兩種存儲方式：intset與hashtable

intset隻能存儲全為整形、元素數量較小的集合。

hashtable可以存儲任意類型的集合。

使用hashtable存儲時，key用來存儲值，而value全部設為null，保證存取速度又不浪費空間。

當滿足以下兩個條件，可以使用intset：

(1)全為整形；

(2)數量小于等于512個

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-jVYvgPlx-1615539216880)(https://i.loli.net/2021/03/09/QTRMUEgSyrtH6A3.png)]

sortedSet

有序集合采用兩種方式編碼：ziplist與zset【内置skiplist與hashtable】

當存儲的

值-分

對很少時，采用ziplist。ziplist會使用順序存儲，排序按照score。【可以想象插入和删除、查找都很慢，都需要o(N)，但是由于節點很少，也很快】

以下是ziplist的存儲：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-0Z3QnOvh-1615539216881)(https://i.loli.net/2021/03/09/gQ4HG6ailFtLsDS.png)]

采用zset存儲時，zset會同時使用兩種結構：skiplist和字典

兩種資料結構所

引用的是同一個資料

，是以不會耗費額外的空間存儲資料。

兩種存儲結構的

值-分

對存儲方式：

（1）skiplist采用object屬性存儲對象，score存儲分數；

（2）dict采用key存儲字元串對象，value存儲分數

為什麼同時使用skiplist和dict？

dict用來實作o(1)的

單個節點分數

的取值；（zscore）

skiplist用來實作範圍操作和排序(zrange, zrank)

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-B4XXu7MG-1615539216882)(https://i.loli.net/2021/03/09/OpCwAW2baNhP8xz.png)]

上圖有些問題，其實兩種結構的資料區域共用同一個資料單元；

編碼轉化：

當不滿足任一個條件，ziplist轉化為zset:

(1)集合元素數量小于128個；

(2)每個元素長度小于64byte

注：

以上關于編碼轉化的門檻值都可以調節。

redisObject其他機制

指令多态

redis有一些共享的指令，可以被好幾種資料結構甚至所有的5種結構使用，如

del expire type

當執行這些指令時，需要首先判斷redis對象的類型，再通路其結構中的資料。

也有一些私有的指令，其他類型不能使用，如llen隻有list才能使用。

類型的檢查與多态調用指令基于redisObject的type屬性。

在執行指令前，會首先檢查type屬性是否滿足，再根據encoding調用對應資料結構的編碼。

del對不同type調用不同的方法，list的llen根據不同的encoding也會調用不同的方法，按照oo的角度，都稱為多态。

引用計數與記憶體回收

redis通過引用計數法決定對象生命周期。

引用的計數展現在redisObject的

refcount

屬性。

機制：

  • 建立一個redis對象，refcount初始化為1；
  • 每多一個程式引用這個redis對象，refcount + 1；
  • 每少… refcount - 1;
  • refcount降為0時，對象回收。
這裡的程式一般指的是

伺服器程式

 ，即使用redis作為緩存的伺服器項目。

通過

object refcount obj

可以檢視對象的引用計數。

不僅程式引用會導緻引用計數的修改，

被其他redis對象引用

 也會修改。

共享對象

refcount也會因為其他redisObject的引用而修改。

當不同的redisObject的引用值相等時，不會建立新的資料單元，而是共同引用同一個對象。

引用不會做其他的事情，隻會吧refcount + 1；

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-3GP8GkDE-1615539216883)(https://i.loli.net/2021/03/09/fCwc7JomjWVBu6q.png)]

注意：redis隻會共享

整形

 資料，任何

包含字元串的資料類型都不會共享

空轉時長

redisObject還擁有最後一個參數：lru，表示這個對象上一次被通路的時間，通過

目前時間 - lru

可以得到對象的空轉時間，這個資料可以通過

object idletime obj

指令得到【這個指令不會修改lru值，雖然他也通路了對象】

除了查詢空轉時長，lru還有一個作用：

建立一個redis對象，refcount初始化為1；

  • 每多一個程式引用這個redis對象，refcount + 1；
  • 每少… refcount - 1;
  • refcount降為0時，對象回收。
這裡的程式一般指的是

伺服器程式

 ，即使用redis作為緩存的伺服器項目。

通過

object refcount obj

可以檢視對象的引用計數。

不僅程式引用會導緻引用計數的修改，

被其他redis對象引用

 也會修改。

共享對象

refcount也會因為其他redisObject的引用而修改。

當不同的redisObject的引用值相等時，不會建立新的資料單元，而是共同引用同一個對象。

引用不會做其他的事情，隻會吧refcount + 1；

[外鍊圖檔轉存中…(img-3GP8GkDE-1615539216883)]

注意：redis隻會共享

整形

 資料，任何

包含字元串的資料類型都不會共享

空轉時長

redisObject還擁有最後一個參數：lru，表示這個對象上一次被通路的時間，通過

目前時間 - lru

可以得到對象的空轉時間，這個資料可以通過

object idletime obj

指令得到【這個指令不會修改lru值，雖然他也通路了對象】

除了查詢空轉時長，lru還有一個作用：

伺服器在設定了

maxMemory

後，且回收政策為

volatile-lru

或者

allkeys-lru

，一旦記憶體超過maxMemory，會引發idletime最大的對象被标記釋放，等待回收。

Redis java 字元串
上一篇: python幾種資料結構_python的五種資料結構
下一篇: redis五種資料結構一、string（字元串）二、list（清單）三、hash（字典）四、set（集合）五、zset（有序集合）六、總結一下五種類型的作用

繼續閱讀