万字长文带你深化Redis底层数据结构

Redis数据库的数据结构

Redis 的键值对中的 key 便是字符串目标，而 value 便是指Redis的数据类型，可所以String，也可所以List、Hash、Set、 Zset 的数据类型。

其实是Redis 底层运用了一个大局哈希表保存一切键值对，哈希表的最大长处便是 O(1) 的时刻复杂度快速查找到键值对。哈希表其实便是一个数组，数组中的元素叫做哈希桶。

• redisDb 结构，表明 Redis 数据库的结构，结构体里寄存了指向了 dict 结构的指针；//默许有16个数据库
• dict 结构，结构体里寄存了 2 个哈希表，正常状况下都是用哈希表1，哈希表2只要在 rehash 的时分才用；
• ditctht 结构，表明哈希表的结构，结构里寄存了哈希表数组，数组中的每个元素都是指向一个哈希表节点结构（dictEntry）的指针；
• dictEntry 结构，表明哈希表节点的结构，结构里寄存了 void* key 和 void* value 指针， key 指向的是 String 目标，而 value 便是指Redis的几种数据类型。

struct redisServer {
   //...
    redisDb *db;
	//...
	int dbnum; //默许16个
}

typedef struct redisDb {
    dict *dict;     //大局hash表
    //...
} redisDb;

struct dict {
   //...
     dictht ht[2]; //两个dictEntry，一个开端为空，rehash搬迁时运用
    //...
	long rehashidx; /* rehashing not in progress if rehashidx == -1 */
};

typedef struct dictht {
    dictEntry **table;        // 哈希表节点数组
    unsigned long size;       // 哈希表巨细
    unsigned long sizemask;   // 哈希表巨细掩码，用于核算索引值，总是等于size-1
    unsigned long used;       // 该哈希表已有节点的数量
} dictht;

struct dictEntry {//详细的目标
    void *key; //key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;//value
    struct dictEntry *next;    //下一个节点的指针
    void *metadata[];
};

void *key 和 void *value 指针指向的便是 Redis 目标。Redis中有大局hash表，key是String,value是不同类型的目标，假如是Java，那能够直接用Map<String,Object>来通用表明。而Redis直接由C言语完结，因而详细的每个目标都由 redisObject 结构表明，用type来表明详细类型，如下：

typedef struct redisObject {
    unsigned type: 4;        // 目标类型
    unsigned storage: 2;     // REDIS_VM_MEMORY or REDIS_VM_SWAPPING
    unsigned encoding: 4;    // 目标所运用的编码
    unsigned lru: 22;        // lru time (relative to server.lruclock)
    int refcount;            // 目标的引证计数
    void *ptr;               // 指向目标的底层完结数据结构
} robj;

• type，标识该目标是什么类型的目标（String 目标、 List 目标、Hash 目标、Set 目标和 Zset 目标）；
• encoding，标识该目标运用了哪种底层的数据结构；
• ptr，指向底层数据结构的指针。

如图，Redis 数据类型（也叫 Redis 目标）和底层数据结构的对应关图：

• 默许状况下hash运用listpack存储，当保存的字段-值的数量大于512个或许单个字段的值大于64个字节时，改为hashtable。
• 默许状况下zSet运用listpack做为存储结构，当调集中的元素大于等于128个或是单个值的字节数大于等于64，存储结构会批改为skiplist。

这几个值都是能够批改的，没必要记；在redis.conf里

hash-max-listpack-entries 512
hash-max-listpack-value 64

zset-max-listpack-entries 128
zset-max-listpack-value 64

SDS

Simple Dynamic String，简略动态字符串

C言语中的缺陷

获取字符串长度复杂度为O(n)

在 C 言语里，字符数组的完毕方位用“\0”表明，意思是指字符串的完毕。
因而c言语获取字符串长度的函数 strlen，便是遍历字符数组中的每一个字符，遇到字符为 “\0” 后，就会中止遍历，然后回来现已核算到的字符个数，即为字符串长度，因而复杂度为O(n)

字符串只能保存文本数据

字符数组的完毕方位用“\0”表明
因而，除了字符串的完毕之外，字符串里边不能含有 “\0” 字符，不然最早被程序读入的 “\0” 字符将被误认为是字符串完毕，这个约束使得 C 言语的字符串只能保存文本数据，不能保存像图片、音频、视频文明这样的二进制数据

有或许产生缓冲区溢出

C 言语的字符串是不会记载自身的缓冲区巨细的，所以 strcat 函数假定程序员在履行这个函数时，现已为 dest 分配了满足多的内存，能够包容 src 字符串中的一切内容，而一旦这个假定不成立，就会产生缓冲区溢出将或许会形成程序运转停止。

SDS结构

• len，记载了字符串长度。这样获取字符串长度的时分，只需求回来这个成员变量值就行，时刻复杂度只需求 O（1）。
• alloc，分配给字符数组的空间长度。这样在批改字符串的时分，能够经过 alloc - len 核算出剩下的空间巨细，能够用来判别空间是否满意批改需求，假如不满意的话，就会主动将 SDS 的空间扩容至履行批改所需的巨细，然后才履行实践的批改操作。这样就不会产生缓冲区溢出
• flags，用来表明不同类型的 SDS。总共规划了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
• buf[]，字符数组，用来保存实践数据。不只能够保存字符串，也能够保存二进制数据。

SDS 的 API 运用二进制的办法来处理 SDS 寄存在 buf[] 里的数据，使得 Redis 不只能够保存文本数据，也能够保存恣意格局的二进制数据。

SDS的动态其实指的便是动态扩容

hisds hi_sdsMakeRoomFor(hisds s, size_t addlen)
{
    ... ...
    // s现在的剩下空间已满足，无需扩展，直接回来
    if (avail >= addlen)
        return s;
    //获取现在s的长度
    len = hi_sdslen(s);
    sh = (char *)s - hi_sdsHdrSize(oldtype);
    //扩展之后 s 至少需求的长度
    newlen = (len + addlen);
    //依据新长度，为s分配新空间所需求的巨细
    if (newlen < HI_SDS_MAX_PREALLOC)
        //新长度<HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间
		//默许界说HI_SDS_MAX_PREALLOC为(1024*1024)即1M
        newlen *= 2;
    else
        //不然，分配长度为现在长度+1MB
        newlen += HI_SDS_MAX_PREALLOC;
       ...
}

// #define HI_SDS_MAX_PREALLOC (1024*1024)

• 假如所需的 sds 长度小于 1 MB，那么终究的扩容是依照翻倍扩容来履行的，即 2 倍的newlen
• 假如所需的 sds 长度超越 1 MB，那么终究的扩容长度应该是 newlen + 1MB。

双向链表

Redis中的链表是双向链表结构

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

不过，Redis 在 listNode 结构体基础上又封装了 list 这个数据结构；类似于Java界说了Node节点，一起再此基础上封装了LinkedList

typedef struct list {
	//链表头节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //节点值仿制函数
    void *(*dup)(void *ptr);
    //节点值开释函数
    void (*free)(void *ptr);
    //节点值比较函数
    int (*match)(void *ptr, void *key);
    //链表节点数量
    unsigned long len;
} list;

Redis的链表的优缺陷与链表的优缺陷共同

紧缩列表

紧缩列表是 Redis 为了节省内存而开发的，它是由接连内存块组成的次序型数据结构，类似于数组。

紧缩列表有四个重要字段：

• zlbytes，记载整个紧缩列表占用对内存字节数；
• zltail，记载紧缩列表「尾部」节点间隔开端地址由多少字节，也便是列表尾的偏移量；
• zllen，记载紧缩列表包括的节点数量；
• zlend，符号紧缩列表的完毕点，固定值 0xFF（十进制255）。

在紧缩列表中，假如要查找定位第一个元素和终究一个元素，能够经过表头三个字段（zllen）的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐一查找，此刻的复杂度便是 O(N) 了，因而紧缩列表不适合保存过多的元素。

紧缩列表节点（entry）的构成如下：

entry中的字段：

• prevlen，记载了前一个节点的长度，意图是为了完结从后向前遍历；
• encoding，记载了当时节点实践数据的类型和长度，类型首要有两种：字符串和整数。
• data，记载了当时节点的实践数据，类型和长度都由 encoding 决议；

往紧缩列表中刺进数据时，紧缩列表会依据数据类型是字符串仍是整数，以及数据的巨细，会运用不同空间巨细的 prevlen 和 encoding 这两个元素里保存的信息，这种依据数据巨细和类型进行不同的空间巨细分配的规划思维，正是 Redis 为了节省内存而选用的。

紧缩列表里的每个节点中的 prevlen 特点都记载了前一个节点的长度，而且 prevlen 特点的空间巨细跟前一个节点长度值有关，比方：

• 假如前一个节点的长度小于 254 字节，那么 prevlen 特点需求用 1 字节的空间来保存这个长度值；
• 假如前一个节点的长度大于等于 254 字节，那么 prevlen 特点需求用 5 字节的空间来保存这个长度值；

连锁更新

紧缩列表新增某个元素或批改某个元素时，假如空间不不行，紧缩列表占用的内存空间就需求重新分配。由于prevlen是前一个节点的长度，当新刺进的元素较大时，那么就或许会导致后续元素的 prevlen 占用空间都产生改变（比方说1字节编程5字节），假如当时节点的prevlen特点从1字节变成5字节后导致下一个节点的prevlen特点也变大，那或许就会而引起「连锁更新」问题，导致每个元素的空间都要重新分配，形成拜访紧缩列表功能的下降。

紧缩列表的优缺陷

长处：

• 依据数据巨细和类型进行不同的空间巨细分配来紧缩内存空间
• 紧缩列表是一种内存紧凑型的数据结构，占用一块接连的内存空间，不只能够运用 CPU 缓存（链表自身内存地址是不接连的，所以不能运用CPU缓存），而且会针对不同长度的数据，进行相应编码，这种办法能够有效地节省内存开支。

缺陷：

• 不能保存过多的元素，不然查询功率就会下降；
• 新增或批改某个元素时，紧缩列表占用的内存空间需求重新分配，乃至或许引发连锁更新的问题。

现在已被listpack代替

哈希表

大局哈希表 和 底层哈希表的目标都是运用的这个结构

哈希表中的节点结构

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
    void *metadata[];          
};

dictEntry 结构里不只包括指向键和值的指针，还包括了指向下一个哈希表节点的指针，这个指针能够将多个哈希值相同的键值对链接起来，以此来处理哈希抵触的问题，这便是链式哈希。

关于处理hash抵触问题能够看这篇文章：处理哈希抵触的三种办法

而redis是先经过拉链法处理，再经过rehash来处理hash抵触问题的，即再hash法

rehash

Redis 界说一个 dict 结构体，这个结构体里界说了两个哈希表（ht_table[2]）。

struct dict {
   //...
    dictEntry **ht_table[2]; //两个dictEntry，一个开端为空，rehash搬迁时运用
    //...
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
};

在正常服务恳求阶段，刺进的数据，都会写入到哈希表 1，此刻的哈希表 2 并没有被分配空间。跟着数据逐渐增多（依据负载因子判别），触发了 rehash 操作，这个进程分为如下三步：

假如哈希表 1的数据量十分大，那么在搬迁至哈希表 2的时分，由于会触及许多的数据复制，此刻或许会对 Redis 形成堵塞，无法服务其他恳求。因而redis选用了渐进式rehash

渐进式 rehash 进程如下：

1. 先给哈希表 2分配空间；
2. 在 rehash 进行期间，每次哈希表元素进行新增、删去、查找或许更新操作时，Redis 除了会履行对应的操作之外，还会次序将哈希表 1中索引方位上的一切 key-value 搬迁到哈希表 2上；
3. 跟着处理客户端建议的哈希表操作恳求数量越多，终究在某个时刻点会把哈希表 1的一切 key-value 搬迁到哈希表 2，然后完结 rehash 操作。

这样就把一次性许多数据搬迁作业的开支，分摊到了屡次处理恳求的进程中，避免了一次性 rehash 的耗时操作。

在进行渐进式 rehash 的进程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删去、查找、更新等操作都会在这两个哈希表进行。比方，在渐进式 rehash 进行期间，查找一个 key 的值的话，先会在哈希表 1里边进行查找，假如没找到，就会持续到哈希表 2 里边进行找到。新增一个 key-value 时，会被保存到哈希表 2里边，而哈希表 1则不再进行任何添加操作，这样确保了哈希表 1的 key-value 数量只会削减，跟着 rehash 操作的完结，终究哈希表 1就会变成空表。

哈希表的查找进程：

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (dictSize(d) == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);//查看是否正在渐进式 rehash，假如是，那就rehash一步
    h = dictHashKey(d, key);//核算key的hash值
	//哈希表元素的删去、查找、更新等操作都会在两个哈希表进行
    for (table = 0; table <= 1; table++) {
        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        while(he) {
            void *he_key = dictGetKey(he);
            if (key == he_key || dictCompareKeys(d, key, he_key))
                return he;
            he = dictGetNext(he);
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

关键在于哈希表刺进时会去查看是都正在Rehash，假如不是，那就往0号hash表中刺进；假如是，那就直接往1号hash表中刺进，由于假如正在Rehash还往0号hash表中刺进，那么终究仍是要rehash到1号hash表的

int htidx = dictIsRehashing(d) ? 1 : 0;

rehash的触发条件

负载因子 = 哈希表已保存节点数量/哈希表巨细

触发 rehash 操作的条件，首要有两个：

• 当负载因子大于等于 1 ，而且 Redis 没有在履行 bgsave 指令或许 bgrewiteaof 指令，也便是没有履行 RDB 快照或没有进行 AOF 重写的时分，就会进行 rehash 操作。
• 当负载因子大于等于 5 时，此刻阐明哈希抵触十分严峻了，不论有没有有在履行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作

整数调集

当一个 Set 目标只包括整数值元素，而且元素数量不大时，就会运用整数集这个数据结构作为底层完结。

typedef struct intset {
    uint32_t encoding;
   //调集包括的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

保存元素的容器是一个 contents 数组，尽管 contents 被声明为 int8_t 类型的数组，可是实践上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的实在类型取决于 intset 结构体里的 encoding 特点的值。比方：

• 假如 encoding 特点值为 INTSET_ENC_INT16，那么 contents 便是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
• 假如 encoding 特点值为 INTSET_ENC_INT32，那么 contents 便是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
• 假如 encoding 特点值为 INTSET_ENC_INT64，那么 contents 便是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

整数调集晋级

将一个新元素参加到整数调集里边，假如新元素的类型（int32_t）比整数调集现有一切元素的类型（int16_t）都要长时，整数调集需求先进行晋级，也便是按新元素的类型（int32_t）扩展 contents 数组的空间巨细，然后才能将新元素参加到整数调集里，当然晋级的进程中，也要保持整数调集的有序性。

整数调集晋级的长处：
假如要让一个数组一起保存 int16_t、int32_t、int64_t 类型的元素，最简略做法便是直接运用 int64_t 类型的数组。不过这样的话，当假如元素都是 int16_t 类型的，就会形成内存糟蹋。

运用整数调集首要思维便是为了节省内存开支。

跳表

跳表的优势是能支撑均匀 O(logN) 复杂度的节点查找。

跳表是在链表基础上改善过来的，完结了一种「多层」的有序链表，这样的长处是能快读定位数据。

typedef struct zskiplist {
	//便于在O(1)时刻复杂度内拜访跳表的头节点和尾节点；
    struct zskiplistNode *header, *tail;
	//跳表的长度
    unsigned long length;
	//跳表的最大层数
    int level;
} zskiplist;

typedef struct zskiplistNode {
    //Zset 目标的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针，指向前一个节点，意图是为了便利从跳表的尾节点开端拜访节点，便利倒序查找。
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

跳表结构如下：

跳表的相邻两层的节点数量最理想的份额是 2:1，查找复杂度能够下降到 O(logN)。

Redis中的跳表是两步两步跳的吗？

假如选用新增节点或许删去节点时，来调整跳表节点以保持份额2：1的办法的话，显然是会带来额定开支的。

跳表在创立节点时分，会生成规模为[0-1]的一个随机数，假如这个随机数小于 0.25（相当于概率 25%），那么层数就添加 1 层，然后持续生成下一个随机数，直到随机数的成果大于 0.25 完毕，终究确认该节点的层数。由于随机数取值在[0,0.25）规模内概率不会超越25%，所以这也阐明晰添加一层的概率不会超越25%。这样的话，当刺进一个新结点时，只需批改前后结点的指针，而其它结点的层数就不需求随之改变了，这样就下降刺进操作的复杂度。

// #define ZSKIPLIST_P 0.25
int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1; //初始化为一级索引
    while (random() < threshold)
        level += 1;//随机数小于 0.25就添加一层
	//假如level 没有超越最大层数就回来，不然就回来最大层数
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

为什么不必AVL树

• 在做规模查找的时分，跳表比AVL操作要简略。AVL在找到最小值后要中序遍历，跳表直接往后遍历就可
• 跳表完结上更简略。AVL的在刺进和删去时或许会需求进行左旋右旋操作，带来额定的开支，而跳表的刺进和删去只需求批改相邻节点的指针，操作更简略

listpack

listpack，意图是代替紧缩列表，它最大特点是 listpack 中每个节点不再包括前一个节点的长度了,处理紧缩列表的连锁更新问题

listpack 选用了紧缩列表的许多优异的规划，比方仍是用一块接连的内存空间来紧凑地保存数据，而且为了节省内存的开支，listpack 节点与紧缩列表相同选用不同的编码办法保存不同巨细的数据

typedef struct {
    /* When string is used, it is provided with the length (slen). */
    unsigned char *sval;
    uint32_t slen;
    /* When integer is used, 'sval' is NULL, and lval holds the value. */
    long long lval;
} listpackEntry;

• encoding，界说该元素的编码类型，会对不同长度的整数和字符串进行编码；
• data，实践寄存的数据；
• len，encoding+data的总长度；

listpack 没有紧缩列表中记载前一个节点长度的字段了，listpack 只记载当时节点的长度，向 listpack 参加一个新元素的时分，不会影响其他节点的长度字段的改变，然后避免了紧缩列表的连锁更新问题。

quicklist

现在版别的 quicklist 其实是 双向链表 + listpack 的组合，由于一个 quicklist 便是一个链表，而链表中的每个元素又是一个listpack。

typedef struct quicklist {
	//quicklist的链表头
    quicklistNode *head;
	//quicklist的链表尾
    quicklistNode *tail;
	//一切listpacks中的总元素个数
    unsigned long count;        /* total count of all entries in all listpacks */
    //quicklistNodes的个数
	unsigned long len;          /* number of quicklistNodes */
    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
	//指向listpack的指针
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    size_t sz;
    int offset;
} quicklistEntry;

typedef struct quicklistNode {
	//前一个quicklistNode
    struct quicklistNode *prev;
	//下一个quicklistNode
    struct quicklistNode *next;
    unsigned char *entry;
	//listpack的的字节巨细
    size_t sz;             /* entry size in bytes */
	//listpack列表的元素个数
    unsigned int count : 16;     /* count of items in listpack */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
    unsigned int extra : 9; /* more bits to steal for future usage */
} quicklistNode;

BitMap

概况请看 位图，源码部分就不多做介绍了

HyperLogLog

HyperLogLog算法是一种十分奇妙的近似核算海量去重元素数量的算法。它内部保护了 16384 个桶（bucket）来记载各自桶的元素数量。当一个元素到来时，它会散列到其间一个桶，以必定的概率影响这个桶的计数值。由于是概率算法，所以单个桶的计数值并不准确，可是将一切的桶计数值进行调合均值累加起来，成果就会十分挨近实在的计数值。

为了便于了解HyperLogLog算法，咱们先简化它的计数逻辑。由于是去重计数，假如是准确的去重，必定需求用到 set 调集，运用调集来记载一切的元素，然后运用 scard 指令来获取调集巨细就能够得到总的计数。由于元素特别多，单个调集会特别大，所以将调集打散成 16384 个小调集。当元素到来时，经过 hash 算法将这个元素分派到其间的一个小调集存储，相同的元素总是会散列到相同的小调集。这样总的计数便是一切小调集巨细的总和。运用这种办法准确计数除了能够添加元素外，还能够削减元素。

调集打散并没有什么显着长处，由于总的内存占用并没有削减。HyperLogLog必定不是这个算法，它需求对这个小调集进行优化，紧缩它的存储空间，让它的内存变得十分细小。HyperLogLog算法中每个桶所占用的空间实践上只要 6 个 bit，这 6 个 bit 自然是无法包容桶中一切元素的，它记载的是桶中元素数量的对数值。

为了阐明这个对数值详细是个什么东西，咱们先来考虑一个小问题。一个随机的整数值，这个整数的尾部有一个 0 的概率是 50%，要么是 0 要么是 1。相同，尾部有两个 0 的概率是 25%，有三个零的概率是 12.5%，以此类推，有 k 个 0 的概率是 2^(-k)。假如咱们随机出了许多整数，整数的数量咱们并不知道，可是咱们记载了整数尾部接连 0 的最大数量 K。咱们就能够经过这个 K 来近似推断出整数的数量，这个数量便是 2^K。

当然成果是十分不准确的，由于或许接下来你随机了十分多的整数，可是完毕接连零的最大数量 K 没有改变，可是估量值仍是 2^K。你或许会想到要是这个 K 是个浮点数就好了，每次随机一个新元素，它都能够略微往上涨一点点，那么估量值应该会准确许多。

HyperLogLog经过分配 16384 个桶，然后对一切的桶的最大数量 K 进行调合均匀来得到一个均匀的完毕零最大数量 K# ，K# 是一个浮点数，运用均匀后的 2^K# 来估量元素的总量相对而言就会准确许多。不过这仅仅简化算法，实在的算法还有许多批改因子，由于触及到的数学理论知识过于繁复，这儿就不再准确描绘。

下面咱们看看Redis HyperLogLog 算法的详细完结。咱们知道一个HyperLogLog实践占用的空间大约是 13684 * 6bit / 8 = 12k 字节。可是在计数比较小的时分，大多数桶的计数值都是零。假如 12k 字节里边太多的字节都是零，那么这个空间是能够恰当节省一下的。Redis 在计数值比较小的状况下选用了稀少存储，稀少存储的空间占用远远小于 12k 字节。相对于稀少存储的便是密布存储，密布存储会稳定占用 12k 字节。

密布存储结构

不论是稀少存储仍是密布存储，Redis 内部都是运用字符串位图来存储 HyperLogLog 一切桶的计数值。密布存储的结构十分简略，便是接连 16384 个 6bit 串成的字符串位图。

那么给定一个桶编号，怎么获取它的 6bit 计数值呢？这 6bit 或许在一个字节内部，也或许会跨过字节鸿沟。咱们需求对这一个或许两个字节进行恰当的移位拼接才能够得到计数值。

假定桶的编号为idx，这个 6bit 计数值的开端字节方位偏移用 offset_bytes表明，它在这个字节的开端比特方位偏移用 offset_bits 表明。咱们有

offset_bytes = (idx * 6) / 8
offset_bits = (idx * 6) % 8

前者是商，后者是余数。比方 bucket 2 的字节偏移是 1，也便是第 2 个字节。它的位偏移是4，也便是第 2 个字节的第 5 个位开端是 bucket 2 的计数值。需求留意的是字节位序是左面低位右边高位，而一般咱们运用的字节都是左面高位右边低位，咱们需求在脑海中进行倒置。

假如 offset_bits 小于等于 2，那么这 6bit 在一个字节内部，能够直接运用下面的表达式得到计数值 val

val = buffer[offset_bytes] >> offset_bits  # 向右移位

假如 offset_bits 大于 2，那么就会跨过字节鸿沟，这时需求拼接两个字节的位片段。

# 低位值
low_val = buffer[offset_bytes] >> offset_bits
# 低位个数
low_bits = 8 - offset_bits
# 拼接，保存低6位
val = (high_val << low_bits | low_val) & 0b111111

不过下面 Redis 的源码要不流畅一点，看方式它好像只考虑了跨过字节鸿沟的状况。这是由于假如 6bit 在单个字节内，上面代码中的 high_val 的值是零，所以这一份代码能够一起照料单字节和双字节。

// 获取指定桶的计数值
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
    uint8_t *_p = (uint8_t*) p; \
    unsigned long _byte = regnum*HLL_BITS/8; \ 
    unsigned long _fb = regnum*HLL_BITS&7; \  # %8 = &7
    unsigned long _fb8 = 8 - _fb; \
    unsigned long b0 = _p[_byte]; \
    unsigned long b1 = _p[_byte+1]; \
    target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
} while(0)

// 设置指定桶的计