intset

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

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

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

ziplist

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

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

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;
}

下圖是一個(gè)ziplist的demo

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

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

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

quicklist

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

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

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

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

list-compress-depth 0

skiplist

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

先看skiplist的一個(gè)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，對(duì)于每一個(gè)新插入的節(jié)點(diǎn)，會(huì)調(diào)用一個(gè)隨機(jī)算法，來(lái)給它分配一個(gè)合理的層數(shù)

level1的概率為1-0.25=0.75，實(shí)際為100%，因?yàn)樘S列表的最小層數(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的原理為伯努利試驗(yàn)，即丟硬幣，根據(jù)連續(xù)出現(xiàn)反面的次數(shù)X，推算出一共丟了2的X次方次硬幣，當(dāng)X很大時(shí)，推算出來(lái)的總數(shù)與實(shí)際總數(shù)誤差就很接近了。具體可查詢其他文章。

pfadd

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

低14位為桶

查找高50位第一個(gè)為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個(gè)桶
• 高50位第一個(gè)1的位置是3，即count值為3
• registers[5]取出歷史值oldcount
• 如果count > oldcount，則更新 registers[5] = count
• 如果count <= oldcount，則不做任何處理

HyperLogLog用了16384個(gè)桶，每個(gè)桶占用6bit，因此說(shuō)一個(gè)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ù))

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

總數(shù)量：const*桶總數(shù)n*桶的平均個(gè)數(shù)，其中constant為不定值，與桶個(gè)數(shù)有關(guān)，假設(shè)m為桶個(gè)數(shù)，取對(duì)數(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)類型的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論