Skip to content

Latest commit

 

History

History
189 lines (114 loc) · 6.83 KB

数据结构.md

File metadata and controls

189 lines (114 loc) · 6.83 KB

redis 的根对象是一个 redisDb 结构体。里面有个 dict 字段，存储了所有的 kv，还有个 expire 字段，存储了所有设置了过期时间的 key。

typedef struct redisDb {
    dict *dict;          // 保存所有 kv
    dict *expires;       // 设置了过期时间的 key 及其过期时间
}

// src/dict.h
// 哈希表
typedef struct dict {
    dictht ht[2];   // ht=hash table，每个dict有俩，增量扩容时使用
} dict;

// 哈希表子结构
typedef struct dictht {
    // 哈希表数组
    // 可以看作是：一个哈希表数组，数组的每个项是entry链表的头结点（链地址法解决哈希冲突）
    dictEntry **table;
} dictht;

// 24字节
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;     // 指向下个哈希表节点，形成链表
} dictEntry;

当我们使用 EXPIRE key duration 命令对一个 key 设置过期时间时，会将该 key 保存到 expires 这个字典中，就是说一个 key 存了两次，额外占用内存。不过这个 key 的 value 不是实际数据的 value，而是过期时间。

dict 的结构详见 哈希表结构

dictEntry 里的 key 和 value，由一种叫做 redisObject 的结构来存储。

RedisObject

在 redis 命令中，对 key 进行处理的命令占了很大一部分。对于不同的 value 类型，key 能执行的命令又大不相同。比如说，LPUSH 和 LLEN 只能用于 list 类型的 key。另外一些命令，比如 DEL、TTL 和 TYPE，可以用于任何类型的 key，但底层的执行逻辑又是不一样的。说明 redis 必须让每个 key 都带有类型信息，使得程序可以检查 key 的类型，并为它选择合适的处理方式。

为了解决以上问题，redis 构建了自己的类型系统，用来储存 value。RedisObject 是其中的核心。其结构如下：

// src/server.h，基于 redis 6.2
// 空间占用16B
typedef struct redisObject {
	unsigned type:4;     // 类型, 4bit
	unsigned encoding:4; // 编码方式, 4bit
	unsigned lru:22;     // LRU时间（相对于server.lrulock）, 3B
	int refcount;        // 引用计数, 4B
	void *ptr            // 指向值的指针, 8B
} robj;

type, encoding, 和 ptr 是最重要的3个属性。

type 可能的值如下：

#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */
#define OBJ_MODULE 5    /* Module object. */
#define OBJ_STREAM 6    /* Stream object. */

encoding 可能的值如下：

#define OBJ_ENCODING_RAW 0        /* Raw representation */
#define OBJ_ENCODING_INT 1        /* Encoded as integer */
#define OBJ_ENCODING_HT 2         /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3     /* 已弃用，Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* 已弃用，No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5    /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6     /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7   /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8     /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9  /* 3.2出的，替代 LINKEDLIST，用作 List 结构的编码。底层其实是把 ziplist 串了起来*/
#define OBJ_ENCODING_STREAM 10    /* Encoded as a radix tree of listpacks */

String

结构为 SDS，编码有如下三种：

  • int：这种编码支持 incr、decr 命令
  • embstr：长度小于 44 的字符串
  • raw：长度超过 44 的字符串

List

  • quicklist: linkedlist 与 ziplist 的结合。

Hash

  • ziplist: 数据量小时，会直接用 ziplist 编码
  • hashtable: 数据量大时，改为 hashtable 编码

Set

  • intset: 元素全为 int，且数量小于配置时，使用该特殊编码
  • hashtable: 其它情况使用 hashtable 编码。其实就是个 value 为 NULL 的 Hash 的结构

Sorted Set

  • ziplist: 数据量小时，使用该编码
  • skiplist + hashtable: 其余情况使用该编码，跳表用于排序，hashtable 用于 O(1) 查找元素

image-20211027194146066

高级数据结构

Bitmap

底层为 String，只不过操作的粒度变成了位。因为 String 类型最大长度为 512MB，所以 bitmap 最多可以存储 2^32 个 bit

GEO
  • 本质上还是借助于 ZSET，并且使用 GeoHash 技术进行填充。Redis 中将经纬度使用 52 位整数进行编码，放进 zset 中，score 就是这 52 位整数值
  • 通过对 score 进行排序就可以得到坐标附近的其它元素，将 score 还原成坐标值就可以得到元素的原始坐标
HyperLogLog
  • 可以用来统计网站PV
  • 基本原理是伯努利实验，比如进行 n 轮抛硬币实验，每轮直到出现 1 为止，如果最多出现连续 2 个 0 然后才是 1 的情况 (001)，那么 n 大概率为 8
    • 001 的概率为 1/2^3，也就是说如果 出现了 001 这个序列，说明起码抛了 8 次硬币。
  • 但是这样误差太大，因此 HyperLogLog 做了分桶。使用 PFAdd key offset 添加元素时，先计算元素的 64 位 hash， 前 14 位用于分桶，后 50 位即伯努利过程，计算最长的连续 0 的个数。
  • 基于每个桶里 0 的最大长度计算平均值，并乘以修正因子，得到最后的计数。
  • 感觉桶里 0 的最大长度，其实类似布谷鸟过滤器里的指纹。
Stream
  • 用作消息队列。底层的数据结构是 radix tree（基数树）

命令的类型检查和多态

有了 redisObject 结构的存在，在执行处理数据类型的命令时，进行类型检查和对编码进行多态操作就简单得多了。

当执行一个处理数据类型的命令时，Redis 执行以下步骤：

  1. 根据给定 key, 在数据库字典中查找和它相对应的 redisObject，如果没找到, 就返回 NULL
  2. 检查 redisObject 的 type 属性和执行命令所需的类型是否相符，如果不相符，返回类型错误
  3. 根据 redisObject 的 encoding 属性所指定的编码，选择合适的操作函数来处理底层的数据结构。返回数据结构的操作结果作为命令的返回值

参考

redis容量估算

头条面试真题：请谈谈Redis 9种数据结构以及它们的内部编码实现

Jackey - 走近源码：神奇的HyperLogLog