intset

當(dāng)set集合存儲的是整數(shù)時，encoding為intset類型（小整數(shù)集合）

typedef struct intset {
    int32 encoding;
    int32 length;
    int contents[];
}

intset按照從小到大的順序保存元素。存儲元素時，根據(jù)整數(shù)大小決定是否要將encoding升級，找到要插入元素的位置，如果不是最后一位，會將所在位置之后的元素后移一位，最后插入元素。如果插入的元素不為整數(shù)，存儲形式將變成hash結(jié)構(gòu)。

ziplist

當(dāng)hash與zset滿足如下條件條件時，編碼類型為ziplist（壓縮列表），具體可在配置文件中查看。

hash-max-ziplist-entries 512 # 當(dāng)hash元素個數(shù)小于512時
hash-max-ziplist-value 64 # 當(dāng)hash鍵或值長度小于64時
zset-max-ziplist-entries 128 # 當(dāng)zset元素個數(shù)小于128時
zset-max-ziplist-value 64 # 當(dāng)zset值小于64時

typedef struct ziplist {
    int32 zlbytes;
    int32 zltail_offset;
    int16 zllength;
    T[] entries;
    int8 zlend;
}
typedef struct entry {
    int<var> prevlen;
    int<var> encoding;
    byte[] content;
}

下圖是一個ziplist的demo

• 第1-4字節(jié)，zlbytes為25，說明該壓縮列表共占用25個字節(jié)
• 第5-8字節(jié)，zltail_offset為22，說明最后一個元素從22開始
• 第9-10字節(jié)，zllength為3，說明共有3個元素
• 第11-16字節(jié)，第一個entry: 其中prevlen=0，因為它前面沒有數(shù)據(jù)項；encoding=4，表示后面4byte按照字符串存儲，數(shù)據(jù)的值為name
• 第17-21字節(jié)，第二個entry: 其中prevlen=6，表示前一個entry共占用6byte；encoding=3，表示后面3byte按照字符串存儲，數(shù)據(jù)的值為why
• 第22-24字節(jié)，第三個entry: 其中prevlen=5，表示前一個entry共占用5byte；encoding=0xFE，表示后面1byte存儲整數(shù)，數(shù)據(jù)的值為14
• 第25字節(jié)，zlend為FF，標(biāo)志壓縮列表的結(jié)束

當(dāng)用ziplist存儲hash結(jié)構(gòu)時，將key與value分別當(dāng)作一個entry存儲。

可見壓縮列表存儲非常的緊湊，當(dāng)某一個entry長度變?yōu)?54時，下一個entry的prevlen將從1個字節(jié)擴(kuò)展到5個字節(jié)，這就是級聯(lián)更新

quicklist

quicklist（快速列表）用于存儲list集合，它是ziplist與linkedlist的混合體，linkedlist與雙向列表結(jié)構(gòu)類似。

quicklist內(nèi)部默認(rèn)單個ziplist長度為8K，超過這個長度，就會另起一個node，可在配置文件中配置。

# -2表示8k，枚舉類型可在配置文件中查看
list-max-ziplist-size -2

quicklist默認(rèn)的壓縮深度為0，也就是不壓縮。如果壓縮深度為1，那么就是首尾不壓縮，如果壓縮深度為2，那么就是首2個、尾2個不壓縮，可在配置文件中配置。

list-compress-depth 0

skiplist

zset使用dict存儲value與score的映射，另一方面還需要按照score提供排序功能，于是就有了skiplist（跳躍列表）

先看skiplist的一個demo

typedef struct zsl {
    zslnode* header;
    zslnode* tail;
    int maxLevel;
}

typedef struct zslnode {
    sds value;
    double score;
    zslforward*[] forwards;
    zslnode* backward;
}

typedef struct zslforward {
    zslnode* item;
    int span;
}

最小分值的backward固定null，對于每一個新插入的節(jié)點，會調(diào)用一個隨機(jī)算法，來給它分配一個合理的層數(shù)

level1的概率為1-0.25=0.75，實際為100%，因為跳躍列表的最小層數(shù)為1

level2的概率為0.75*0.25=0.1875level3的概率為0.1875*0.25=0.0468 ......

leveln的概率為(1-0.25)*Math.pow(0.25,n-1)

總結(jié)

Redis作為單線程內(nèi)存服務(wù)，在響應(yīng)、數(shù)據(jù)結(jié)構(gòu)上作出了很多的優(yōu)化，值得我們學(xué)習(xí)

HyperLogLog

HyperLogLog的原理為伯努利試驗，即丟硬幣，根據(jù)連續(xù)出現(xiàn)反面的次數(shù)X，推算出一共丟了2的X次方次硬幣，當(dāng)X很大時，推算出來的總數(shù)與實際總數(shù)誤差就很接近了。具體可查詢其他文章。

pfadd

element經(jīng)過hash算法之后是一個64位的固定值

低14位為桶

查找高50位第一個為1的位數(shù)，如果大于當(dāng)前桶的位數(shù)，就將其設(shè)置為當(dāng)前桶的位數(shù)

假設(shè)hash值是 ：{此處省略45位}01100 00000000000101

• 低14位的二進(jìn)制轉(zhuǎn)為10進(jìn)制，值為5（regnum），即我們把數(shù)據(jù)放在第5個桶
• 高50位第一個1的位置是3，即count值為3
• registers[5]取出歷史值oldcount
• 如果count > oldcount，則更新 registers[5] = count
• 如果count <= oldcount，則不做任何處理

HyperLogLog用了16384個桶，每個桶占用6bit，因此說一個HyperLogLog所占用內(nèi)存是12K。

調(diào)和平均數(shù)：

假設(shè)我的工資為10_000，馬云的工資為1_000_000，那我和馬云的平均工資為505_000，我肯定是不認(rèn)同的。。。

如果使用調(diào)和平均數(shù)，則為2/(1/10_000+1/1_000_000)=19_801

同理，桶位數(shù)的平均數(shù)為：n/(1/桶1位數(shù)+1/桶2位數(shù)+...+1/桶n位數(shù))

桶的平均個數(shù)為：Math.pow(2，桶位數(shù)的平均數(shù))

總數(shù)量：const*桶總數(shù)n*桶的平均個數(shù)，其中constant為不定值，與桶個數(shù)有關(guān)，假設(shè)m為桶個數(shù)，取對數(shù)

pfcount

p=log2m
switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

以上就是Redis數(shù)據(jù)結(jié)構(gòu)類型示例解析的詳細(xì)內(nèi)容，更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)類型的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論