侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

Redis 常见数据结构的底层实现系列(六):字典篇

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 92 阅读 / 2,164 字

压缩列表

当我们初始化一个新的 Redis 字典时,默认使用压缩列表来创建:

robj *createHashObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

关于压缩列表,这里复用的是同样的数据结构,和有序集合类似,Redis 会将字典中的所有键值依次紧凑地存放到压缩列表的 entry 中:

127.0.0.1:6379> hmset users name tom age 25 career programmer
OK
127.0.0.1:6379> debug object users
Value at:0x7f86796c4dd0 refcount:1 encoding:ziplist serializedlength:51 lru:602338 lru_seconds_idle:6

1.jpeg

哈希表

当压缩列表中 entry 数量超过 512,或者单个 entry 长度超过 64 时,就会转化为哈希表来存储字典,和有序集合一样,这两个阈值可以在 Redis 配置文件中配置:

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

对应的哈希表结构和集合、有序集合复用的是同一个 dict,然后更底层存放字典数据的是 dictht,存放具体元素的是 dictEntry:

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

只不过对于集合而言,键值 v 为 NULL,对于有序集合而言,键值 v 为 score 值,对于字典而言,键值 v 为传递的字符串格式属性值:

1.jpeg

其他逻辑都是一样的,比如单个字典较大时,也会进行渐进式 rehash,如果你想要深入了解 Redis 底层 rehash 和哈希函数的实现细节,可以阅读 Redis 源码库中的 dict.c 文件,限于篇幅这里就不详细展开了。

如果前面初始化的 users 字典为例,使用哈希表存储的话,对应的底层数据结构图示如下:

1.jpeg

小结

1.jpeg

为了优化内存管理效率,将数据存取性能做到极致,Redis 会根据存储数据的类型和规模使用不同的数据结构和编码类型:

  • 对于字符串而言,整型数据会通过 int 编码,长度不超过 44 时,使用 embstr 编码,其他情况才使用 raw 编码;
  • 对于列表而言,从 Redis 4.0 后统一使用快速列表(quicklist)存储,它其实是双向链表和压缩列表的混合体,内部以压缩列表为存储单元;
  • 对于集合而言,小规模整型集合通过 IntSet 实现,其他情况使用哈希表(值为 NULL);
  • 对于有序集合而言,元素数量不多时使用压缩列表,否则使用哈希表+跳跃列表实现;
  • 对于字典而言,元素数量不多时使用压缩列表实现,否则使用哈希表实现。

不同底层数据结构的时间复杂度如下:

1.jpeg

这些高效的底层数据结构,是撑起了 Redis 高性能数据存取操作的重要基石。

对于一些时间复杂度为 O(N) 的数据结构,要尽量避免大规模的范围查询,比如列表,我们应该合理利用不同数据结构的特点实现合适的业务功能,还是以列表为例,虽然范围查询效率低,但是可以用作消息队列,因为从列表头尾存取数据的时间复杂度是 O(1)。

0

评论区