01.数据类型、底层数据结构

Redis 对象类型和编码：

Redis键和值都是由redisObject定义

typedef struct redisObiect{
	//类型
	unsigned type:4;
	//编码
	unsigned encoding:4;
	//指向底层数据结构的指针
	void *ptr;
}

数据类型和底层数据结构的关系：

底层数据结构时间复杂度：

String 对象的编码和数据结构：

• 特征：
  • String 是最基本的 key-value 结构
• 最大长度：512M
• 编码规则：根据值的类型和长度
  • 元素全部为整数， 且可以使用long表示，则 encoding为 int
  • 字符串 且长度 > 32字节，则encoding为 raw
  • 字符串 且长度 <= 32字节，则encoding为 embstr
• embstr 和 raw的区别：
  • embstr编码时，只需要一次内存分配，redisObject和SDS结构会存储在一块连续内存。embstr编码一般用于仅查询的场景，如果对embstr编码的数据做修改，需要先将编码改成raw，再修改数据
  • raw需要两次内存分配，能存储的字符串长度更大

简单动态字符串 SDS：

结构：

优点：

1. 动态扩展，最大不能超过512MB
2. 性能高（减少内存重分配次数）
   1. 空间预分配
   2. 空间惰性释放
3. 二进制安全
   1. 通过len判断是否结束，而不是结束符，存储的是二进制数据，而不是字符
4. 遵循以空字符结尾的惯例，因此兼容C字符串函数

List对象的编码和数据结构：

• 特征：
  • List是列表结构，按照插入顺序排序，可以从头部或尾部向 List 列表添加元素
• 最大长度： 2^32 - 1（40亿）
• 编码规则：元素个数和元素值大小
  • 元素个数 < 512 且元素值大小 < 64字节，encoding 为 ziplist(压缩列表，压缩列表本身可以支持的元素大小很大)
  • 否则，encoding为linkedlist(双向链表)
  • Redis > 3.2版本后，encoding只有quicklist

quicklist：

特征：

• ziplist和linkedlist的混合体
• 外层是linkedlist，每个node里面是ziplist
• quicklist会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题

查找过程：

因为是有序插入，可以先找对应node，再到node里面的ziplist找元素

ziplist 压缩列表：

特征：

• 内存占用小且连续，分配速度快，随机访问相对高效，插入删除相对低效（因为需要挪动）
• 压缩列表只会用于保存的节点数量不多的场景
• 压缩列表每个节点因为需要保存前一个节点的长度字段 prevlen，就会有连锁更新的隐患

结构：

• prevlen的作用：
  • 快速反向遍历：通过记录前一个 entry 的长度，可以快速定位到前一个元素的起始位置
• encoding: | encoding 编码 | 编码长度 | data保存的值类型、范围、和个数 | | -- | -- | -- | | 00开头 | 1字节 | data存字符串，长度<=63字节，编码的后6位记录字符串长度 | | 01开头 | 2字节 | data存字符串，长度<=2^14-1，编码的后14位记录字符串长度 | | 10开头 | 5字节 | data存字符串，长度<=2^32-1，编码的后38位记录字符串长度 | | 11开头 | 1字节 | data存的1个整数 |

查找过程：

1. 查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)
2. 查找其他元素时，只能逐个查找，此时的复杂度就是 O(N)。如果 ziplist 里面保存的是字符串，ziplist在查找某个元素时，还需要通过encoding逐个解码元素，判断每个元素的data大小。

linkedlist 双向链表：

特征：

• 内存不连续，随机访问低效，插入删除相对高效
• 无大小限制

结构：

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

typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void *(*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr,void *key);
}list;

listpack:

特征：

• 每个节点不再包含前一个节点的长度，无连锁更新隐患
• 用来替代ziplist

结构：

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

Hash对象的编码和数据结构：

• 特征：
  • 键值对中的值本身又是一个键值对结构
• 编码规则：元素个数和元素值大小
  • 元素个数 < 512 且元素值大小 < 64字节，encoding 为 ziplist(压缩列表)
  • 否则，encoding为hashtable(哈希表)

hashtable 哈希表：

特征：

1. 基于数组按照下标随机访问，复杂度O(1)
2. hash函数
3. hash冲突：
   • 开放寻址（重新探测一一个空闲位）
   • 链表法
   • 负载因子 rehash（是个指标，基于此扩容、收缩）

结构：

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

typedef struct dictEntry {
    //键值对中的键
    void *key;
  
    //键值对中的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

渐进式rehash：

• 当负载因子系数满足条件时，开始rehash
• 为字典的ht[1]散列表分配空间，修改rehashidx为0表示正在rehash
• 每次有更新命令时，将对应数据更新到ht[1],并分批将ht[0]部分键重新计算hash值，放入ht[1]
• 期间的操作需要到两个hash表查询
• 完成迁移后，调整rehashidx值，ht[0]变为空表

Set 对象的编码和数据结构：

• 特征：
  • 无序、不可重复、支持并交差等操作
  • 元素个数上限：2^32-1
• 编码规则：元素个数和元素类型
  • 元素全部为整数，且个数 < 512，则encoding为intset整数集合
  • 其他，使用hashtable哈希表

intset 整数集合：

特征：

• 整数集合是Redis自己设计的一种存储结构
• 可以存储int16_t、int32_t、int64_t的整数

结构：

//每个intset结构表示一个整数集合
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合中包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

• 整数集合升级：
  • 新元素的类型比整数集合现有元素的类型长时
  • 根据新元素的类型,扩展整数集合底层数组的空间大小
  • 原有元素类型转换
  • 新元素插入
• 整数集合降级：
  • 升级后不再发生降级

Zset 对象的编码和数据结构(Sorted Set)：

• 特征：
  • 有序、不可重复、支持并交差等操作
  • 相比于 Set 类型多了一个排序属性 score（分值）
• 元素个数上限：2^32-1
• 编码规则：元素个数和元素大小
  • 元素个数 < 128 且元素 < 64字节，encoding为ziplist压缩列表
  • 其他，使用skiplist跳表

skiplist 跳表：

• 定义：在链表的基础上，增加了多级索引
• 优点：既能进行高效的范围查询，也能进行高效单点查询

结构：

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的 level 数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

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

查找：

    // 跳表查找元素
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                     sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }

• 查找 (abcd，4)
• 过程：
  • 先从头节点的最高层 L2 开始，L2 forward 指向(abc，3)。权重3 < 4，x 设置为(abc，3)；
  • (abc，3)的forward为空指针, 向其下一层leve[1]寻找;
  • (abc，3)的leve[1]的forward指向(abcde，4)。权重4和查找元素相等，但 "abced" > "abcd"，不满足条件，继续向其下一层 leve[0]寻找;
  • (abc，3)的leve[0]的forward指针指向(abcd，4)，权重和SDS都与查找的节点相等，元素找到，查询结束。

说明：

• 跳表在链表的基础上，增加了多级索引。通过索引位置的几个跳转，实现数据的快速定位。（空间换时间的方式，首先得保证链表是有序的）

Bitmap 对象和数据结构：

• 特征：
  • Bitmap，即位图，是一串连续的二进制数组
  • 查找：可以通过偏移量（offset）定位元素
  • BitMap 通过最小的单位 bit 来进行0|1的设置，表示某个元素的值或者状态
  • 时间复杂度为 O(1)
• 编码规则：
  • 用 String 类型作为底层数据结构
• 作用：统计二值状态

HyperLogLog 对象和数据结构：

• 特征：
  • 提供不精确的去重计数，基于概率统计
  • 节省内存：HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数
• 作用：基数统计（指统计一个集合中不重复的元素个数）
• 底层数据结构：忽略

GEO 对象和数据结构：

• 特征：
• 作用：用于存储地理位置信息，并对存储的信息进行操作
• 底层数据结构：Sorted Set 集合类型
• 机制：
  • 「对二维地图做区间划分」
  • 「对区间进行编码」
  • 把编码值作为 Sorted Set 元素的权重分数

Stream 对象和数据结构：

• 特征：
  • 专门为消息队列设计的数据类型
  • 支持消息的持久化（pub/sub不支持）
  • 支持自动生成全局唯一 ID（List不支持）
  • 支持ack消息确认的模式（List不支持）
  • 支持消费组模式等
• pub/sub机制问题：
  • 因为不是基于基本数据类型实现，所以无法持久化
  • 订阅者离线重连，无法消费历史数据
  • 消费端消费能力差时，会被强行断开