Redis设计与实现阅读总结(一)数据结构和对象

Redis设计与实现阅读总结(一)数据结构和对象最近团队几个人和我聊了下,加上我自己平时的反思,我发现自己问题确实很多其中一个问题就是,自己学习东西没有系统性,没有总结这次的博客算是一个总结的开始。最近由于出实习题,趁着这个机会,自己阅读了《redis设计与实现》这本书为了解决自己的毛病,准备围绕这个话题写博文,做总结,从细节到总体,围绕这个话题写更多东西大家可能发现这个部分写的很粗略,因为red...

Redis设计与实现阅读总结(一)数据结构和对象
Redis设计与实现阅读总结(一)数据结构和对象

最近团队几个人和我聊了下,加上我自己平时的反思,我发现自己问题确实很多

其中一个问题就是,自己学习东西没有系统性,没有总结

这次的博客算是一个总结的开始。

最近由于出实习题,趁着这个机会,自己阅读了《redis设计与实现》这本书

为了解决自己的毛病,准备围绕这个话题写博文,做总结,从细节到总体,围绕这个话题写更多东西

大家可能发现这个部分写的很粗略,因为redis本身设计的就是很简单的,这些数据结构基本没有太多好写的,主要是写了后做一个总结,后面的更为重要的部分会做更多叙述

1. SDS(简单动态字符串)

每个 sds.h/sdshdr 结构表示一个 SDS 值:

struct sdshdr { // 记录 buf 数组中已使用字节的数量 // 等于 SDS 所保存字符串的长度 int len; // 记录 buf 数组中未使用字节的数量 int free; // 字节数组,用于保存字符串 char buf[];};

img

为什么不使用c语言简单字符串

原因有如下

  • 获取长度复杂度为O(1)
  • 避免缓冲区溢出

优化策略

redis非常注重性能,于是优化是非常必要的。

减少内存重分配
  • 空间预分配
  • 内存的分配设计到复杂算法或可能的系统调用,比较耗时

    于是,每次再字符串增长操作时,不仅仅会扩容到刚好所需的空间,而是会通过一定策略额外分配空间

  • 惰性空间释放
  • 字符串的缩短操作,不会进行内存重分配,而是会通过free记录起来,为未来可能存在的增长提供优化

    二进制安全

    不使用\0辨认结尾,而是通过len

    并且在SDS中\0被保留,可以兼容部分c字符串函数

    2. 链表

    redis是一个设计追求简单的数据库,链表这种简单实用的数据结构在很多地方都得到了应用,(事实上应该说是双向链表。)

    譬如 列表(List),慢查询,监视器,订阅与发布等。包括客户端状态也是用链表在服务器中进行保存的。

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

    img

    img

    3. 字典

    字典是使用哈希表作为底层实现。

    img

    一图胜千言

    看的出来,解决键冲突(collision)的办法是通过每个哈希表节点都是一个链表。(链地址法)

    • 哈希算法
    • 链地址法

    以上两者细节就不解释了

    rehash扩容

    img

    要扩多少内容,开多大空间的新dictEntry,然后把之前的dictEntry转到新的。

    当然,一次性转会有性能问题,所以

    渐进式rehash

    相当于是搭便车

    每次对字典进行更新添加查找删除操作时,会顺带的转移旧的dictEntry的一个index链表到新的dictEntry

    详细执行过程不予介绍

    4. 跳跃表(跳表)

    跳跃表(skiplist)是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的。

    跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找, 还可以通过顺序性操作来批量处理节点。

    在大部分情况下, 跳跃表的效率可以和平衡树相媲美, 并且因为跳跃表的实现比平衡树要来得更为简单, 所以有不少程序都使用跳跃表来代替平衡树。

    Redis 使用跳跃表作为有序集合键的底层实现之一: 如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员(member)是比较长的字符串时, Redis 就会使用跳跃表来作为有序集合键的底层实现

    img

    从上图可以看书,跳表其实就是一种分治思想的,利用空间换取时间的一种算法

    在看了上图之后,这个时候再看下图redis的跳表。就应该容易理解多了

    img

    整数集合

    整数集合就比较简单了,重要的一个点主要是升级

    redis的整数集合类型其实是会随着存入数字而变化的,当数都比较小的时候,类型可能就是int8_t,int16_t,但是一旦加入一个大数,集合会升级类型为相应类型,此时该集合中所有数都会被更新为该类型

    另外注意

    整数集合的数组不会出现降级

    img

    压缩列表对象
    源文地址:https://www.guoxiongfei.cn/csdn/4896.html