intset

當set集合存儲的是整數時，encoding為intset類型（小整數集合）

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

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

ziplist

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

hash-max-ziplist-entries 512 # 當hash元素個數小于512時
hash-max-ziplist-value 64 # 當hash鍵或值長度小于64時
zset-max-ziplist-entries 128 # 當zset元素個數小于128時
zset-max-ziplist-value 64 # 當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字節，zlbytes為25，說明該壓縮列表共占用25個字節
• 第5-8字節，zltail_offset為22，說明最后一個元素從22開始
• 第9-10字節，zllength為3，說明共有3個元素
• 第11-16字節，第一個entry: 其中prevlen=0，因為它前面沒有數據項；encoding=4，表示后面4byte按照字符串存儲，數據的值為name
• 第17-21字節，第二個entry: 其中prevlen=6，表示前一個entry共占用6byte；encoding=3，表示后面3byte按照字符串存儲，數據的值為why
• 第22-24字節，第三個entry: 其中prevlen=5，表示前一個entry共占用5byte；encoding=0xFE，表示后面1byte存儲整數，數據的值為14
• 第25字節，zlend為FF，標志壓縮列表的結束

當用ziplist存儲hash結構時，將key與value分別當作一個entry存儲。

可見壓縮列表存儲非常的緊湊，當某一個entry長度變為254時，下一個entry的prevlen將從1個字節擴展到5個字節，這就是級聯更新

quicklist

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

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

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

quicklist默認的壓縮深度為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，對于每一個新插入的節點，會調用一個隨機算法，來給它分配一個合理的層數

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

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

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

總結

Redis作為單線程內存服務，在響應、數據結構上作出了很多的優化，值得我們學習

HyperLogLog

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

pfadd

element經過hash算法之后是一個64位的固定值

低14位為桶

查找高50位第一個為1的位數，如果大于當前桶的位數，就將其設置為當前桶的位數

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

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

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

調和平均數：

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

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

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

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

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

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