redis基础知识

redis数据结构

五种常用数据结构：string, hash, list, set, zset
十种底层数据结构: ziplist(压缩链表)

hash结构

Redis在存储hash结构的数据，为了达到内存和性能的平衡，也针对少量存储和大量存储分别设计了两种结构，分别为：

ziplist：压缩列表，当hash达到一定的阈值时，会自动转换为hashtable结构
listpack：紧凑列表，在Redis7.0之后，listpack正式取代ziplist。同样的，当hash达到一定的阈值时，会自动转换为hashtable结构
hashtable：哈希表，类似map

从ziplist/listpack编码转换为hashTable编码是通过判断元素数量或单个元素Key或Value的长度决定的：

hash-max-ziplist-entries：表示当hash中的元素数量小于或等于该值时，使用ziplist编码，否则使用hashtable编码。ziplist是一种压缩列表，它可以节省内存空间，但是访问速度较慢。hashtable是一种哈希表，它可以提高访问速度，但是占用内存空间较多。默认值为512。
hash-max-ziplist-value：表示当 hash中的每个元素的 key 和 value 的长度都小于或等于该值时，使用 ziplist编码，否则使用 hashtable编码。默认值为 64。

相比于hashtable，ziplist把全部key-value都保存在一起，构成一个双向链表存储。通过牺牲部分读写性能，来通过时间换空间。只适合key-value数量少，数据小的场景

List结构

list 是一个有序的字符串列表，它按照插入顺序排序，并且支持在两端插入或删除元素。一个 list 类型的键最多可以存储 2^32 - 1 个元素。
redis3.2以后，list 类型的底层实现只有一种结构，就是quicklist，quicklist是ziplist/listpack和linkedlist结合版

Set结构

set 是一个无序的字符串集合，它不允许重复的元素。一个 set 类型的键最多可以存储 2^32 - 1 个元素。

set 类型的底层实现有两种：

intset，整数集合
hashtable（哈希表）。哈希表和 hash 类型的哈希表相同，它将元素存储在一个数组中，并通过哈希函数计算元素在数组中的索引

set底层变更：

在Redis7.2之前，set使用的是intset和hashtable
在Redis7.2之后，set使用的是intset、listpack、hashtable

在Redis7.2之前，当一个集合满足以下两个条件时，Redis 会选择使用intset编码：

集合对象保存的所有元素都是整数值
集合对象保存的元素数量小于等于512个（默认）

如果要添加的数据是字符串，分为三种情况

当前set的编码为intset：如果没有超过阈值，转换为listpack；否则，直接转换为hashtable
当前set的编码为listpack：如果超过阈值，就转换为hashtable
当前set的编码为hashtable：直接插入，编码不会进行转换

阈值条件为：

1
2
3

set-max-intset-entries 512 # intset最大元素，默认512
set-max-listpack-entries 128 #：最大元素个数，默认128
set_max_listpack_value 64 #：最大元素大小，默认64

为什么Set结构加入了listpack
在redis7.2之前，sds类型的数据会直接放入到编码结构式为hashtable的set中。其中，sds其实就是redis中的string类型。
而在redis7.2之后，sds类型的数据，首先会使用listpack结构当 set 达到一定的阈值时，才会自动转换为hashtable。
添加listpack结构是为了提高内存利用率和操作效率，因为 hashtable 的空间开销和碰撞概率都比较高。

ZSet结构

Redis 中的 zset 是一种有序集合类型，它可以存储不重复的字符串元素，并且给每个元素赋予一个排序权重值（score）。Redis 通过权重值来为集合中的元素进行从小到大的排序。zset 的成员是唯一的，但权重值可以重复。一个 zset 类型的键最多可以存储 2^32 - 1 个元素。

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

zset 类型的应用场景主要是利用分数和排序的特性，比如：

排行榜，利用 zadd 和 zrange 命令实现分数的更新和排名的查询
延时队列，利用 zadd 和 zpopmin 命令实现任务的添加和执行，并且可以定期地获取已经到期的任务
访问统计，可以使用 zset 来存储网站或者文章的访问次数，并且可以按照访问量进行排序和筛选。

zset底层原理：
Redis在存储zset结构的数据，为了达到内存和性能的平衡，针对少量存储和大量存储分别设计了两种结构，分别为：

ziplist（redis7.0之前使用）和listpack（redis7.0之后使用）
skiplist + dict (skiplist提供有序存储kv，dict提供hash唯一插入查找skiplist中的node地址)
当 zset 中的元素个数和元素值的长度比较小的时候，Redis 使用ziplist/listpack来节省内存空间。当 zset 中的元素个数和元素值的长度达到一定阈值时，Redis 会自动将ziplist/listpack转换为skiplist，以提高操作效率
当 zset 同时满足以下两个条件时，会使用 listpack作为底层结构：

1 2	zset_max_listpack_entries 128 zset_max_listpack_value 64

当 zset 中不满足以上两个条件时，会使用 skiplist 作为底层结构。

zset插入实现如下

int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
    // ...
    /* Update the sorted set according to its encoding. */
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        // ...
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplistNode *znode;
        dictEntry *de;

        de = dictFind(zs->dict,ele);
        if (de != NULL) {
            // 已经存在
            // ...
        } else if (!xx) {
            // 不存在，插入 skiplist和dict中
            ele = sdsdup(ele);
            znode = zslInsert(zs->zsl,score,ele);
            serverAssert(dictAdd(zs->dict,ele,&znode->score) == DICT_OK);
            *out_flags |= ZADD_OUT_ADDED;
            if (newscore) *newscore = score;
            return 1;
        } else {
            *out_flags |= ZADD_OUT_NOP;
            return 1;
        }

    }

Stream结构

GEO结构

Bitmap结构

redis底层数据结构

SDS

SDS字符串结构包括

len 保存了SDS保存字符串的长度
buf[] 数组用来保存字符串的每个元素
alloc分别以uint8, uint16, uint32, uint64表示整个SDS, 除过头部与末尾的\0, 剩余的字节数.
flags 始终为一字节, 以低三位标示着头部的类型, 高5位未使用

为什么不使用C语言字符串实现，而是使用 SDS呢

常数复杂度获取字符串长度
杜绝缓冲区溢出
减少修改字符串的内存重新分配次数
二进制安全（C语言是以空字符标识结束）

对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。
2。惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）

ziplist

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。ziplist这种数据结构是连续存储的，也就是说，它在内存中是一个连续的内存块。链表中可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。它能在O(1)的时间复杂度下完成list两端的push和pop操作。但是因为每次操作都需要重新分配ziplist的内存，所以实际复杂度和ziplist的内存使用量相关。

ziplist中的每个元素（也称为entry）都被存储在一个连续的内存区域中，而不是通过指针链接到其他地方。每个entry包括几个部分：前一个entry的长度（反向遍历的适合需要定位到前一个元素）、当前entry的长度、编码、内容等。这些部分都存储在一起，形成一个连续的内存区域。这样做的好处是可以减少内存碎片和指针引用的开销，提高内存利用率和数据访问速度。然而，这种设计也有一些限制。例如，如果要在ziplist中间插入或删除一个元素，可能需要移动后面的所有元素，这会造成一定的性能开销。因此，ziplist更适合存储小而固定数量的元素。

ziplist的entry结构：
第一种情况：一般结构

prevlen：前一个entry的大小（方便反向遍历）
encoding：不同的情况下值不同，用于表示当前entry的类型和长度；（方便正向遍历）
entry-data：真是用于存储entry表示的数据；
第二种情况：entry结构：。在entry中存储的是int类型时，encoding和entry-data会合并在encoding中表示，此时没有entry-data字段；redis中，在存储数据时，会先尝试将string转换成int存储，节省空间；

ziplist缺点

ziplist也不预留内存空间, 并且在移除结点后, 也是立即缩容, 这代表每次写操作都会进行内存分配操作.
结点如果扩容, 导致结点占用的内存增长, 并且超过254字节的话, 可能会导致链式反应: 其后一个结点的entry.prevlen需要从一字节扩容至五字节. 最坏情况下, 第一个结点的扩容, 会导致整个ziplist表中的后续所有结点的entry.prevlen字段扩容. 虽然这个内存重分配的操作依然只会发生一次, 但代码中的时间复杂度是o(N)级别, 因为链式扩容只能一步一步的计算. 但这种情况的概率十分的小, 一般情况下链式扩容能连锁反映五六次就很不幸了. 之所以说这是一个蛋疼问题, 是因为, 这样的坏场景下, 其实时间复杂度并不高: 依次计算每个entry新的空间占用, 也就是o(N), 总体占用计算出来后, 只执行一次内存重分配, 与对应的memmove操作, 就可以了

listpack
entry的结构改为将当前entry长度保存在entry最后，不再保存上个entry的长度，也就无法逆向遍历了，但用来保存hash数据足够了
因为entry中不保存其他entry中的长度了,所以当对listpack进行增删改的时候并不会出现级联更新的情况

quicklist

quicklist是ziplist和linkedlist结合版，内存布局如下：

和Hash结构一样，因为ziplist有连锁更新问题，redis7.0将ziplist替换为listpack

listpack内部entry个数可在redis.conf配置：

List-Max-listpack-size -2
# -5: 每个listpack最多为 64 kb  <-- 影响正常负载，不推荐
# -4: 每个listpack最多为 32 Kb  <-- 不推荐
# -3: 每个listpack最多为 16 Kb  <-- 最好不要使用
# -2: 每个listpack最多为 8 Kb   <-- 好
# -1: 每个listpack最多为 4 Kb   <-- 好
# 正数为listpack内部entry个数

Dict/hashtable

hash表定义如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

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

typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

操作和go的map很多一致的，可参考引用2的文章

IntSet

intset是一种紧凑的数组结构，它只保存int类型的数据，它将所有的元素按照从小到大的顺序存储在一块连续的内存中。intset会根据传入的数据大小，encoding分为int16_t、int32_t、int64_t

skiplist

跳跃表是一种随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳跃表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳跃表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能

优点：

实现简单，易于理解和调试
插入和删除操作只需要修改局部节点的指针，不需要像平衡树那样进行全局调整
可以利用空间换时间，通过增加索引层来提高查找效率
支持快速的范围查询，可以方便地返回指定区间内的所有元素

缺点：

空间复杂度较高，需要额外存储多级索引
随机性太强，性能不稳定，最坏情况下可能退化成链表
不支持快速的倒序遍历，需要额外的指针来实现

skiplist有一个层数上的问题，当层数过多，会影响查询效率。而Redis 使用了一个随机函数来决定每个节点的层数，这个随机函数的期望值是 1/(1-p) ，其中 p 是一个概率常数，Redis 中默认为 0.25。这样可以保证跳跃表的平均高度为 log (1/p) n ，其中 n 是节点数。Redis 还限制了跳跃表的最大层数为 32 ，这样可以避免过高的索引层造成空间浪费

插入流程如下：