Redis 的底层数据结构(SDS和链表)

更新日期: 2019-09-13阅读: 2k标签: 数据

Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。可能几乎所有的线上项目都会使用到 Redis,无论你是做缓存、或是用作消息中间件,用起来很简单方便,但可能大多数人并没有去深入底层的看看 Redis 的一些策略实现等等细节。

正好最近也在项目开发中遇到一些 Redis 相关的 Bug,由于不熟悉底层的一些实现,较为费劲的解决了,所以打算开这么一个系列,记录一下对于 Redis 底层的一些结构、策略的学习笔记。

第一部分我们打算从 Redis 的五种数据结构以及对象类型的实现开始,主要涉及内容如下,你也可以通过文末给出 GitHub 仓库下载对应的思维导图。


本篇文章打算介绍 SDS 简单动态字符串和双端链表这两种数据结构。


一、SDS 简单动态字符串

大家都知道 Redis 是由 C 语言作为底层编程语言实现的,而 C 语言中也是有字符串这种数据结构的,它是一个字符数组并且是一个以空字符结尾的字符数组,这种结构对于 Redis 而言过于简单了,于是 Redis 自行实现了 SDS 这种简单动态字符串结构,它其实和 Java 中 ArrayList 的实现是很类似的。

Redis 源代码中 sds.h 文件下,有五种 sdshdr,它们分别是:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

其中,sdshdr5 的注释表明,sdshdr5 is never used。sdshdr5 这种数据结构一般用于存储长度小于 32 个字符的字符串,但现在也已经不再使用这种结构了,再小长度的字符串也建议使用 sdshdr8 进行存储,因为 sdshdr5 少了两个关键字段,因此不具备动态扩容操作,一旦预分配的内存空间使用完,就需要重新分配内存并完成数据的复制迁移,在实际的生产环境中对于性能的影响还是很大的,所以进行了一个抛弃,但其实有些比较小的键依然会采用这种结构存储。

关于 sdshdr5 我们不再多说,我们看其他四种结构的各个字段,len 字段表示当前字符串总长度,也即当前字符串已使用内存大小,alloc 表示为当前字符串分配的总内存大小(不包括len以及flags字段本身分配的内存),因为每一个结构在预分配的时候都会多分配一段内存空间,主要是为了方便以后的扩容。flags 的低三位表示当前 sds 的类型,高五位无用。低三位取值如下:

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

实际上,redis 对 sdshdr 内存分配是禁用内存对齐的,也就是说每个字段分配的内存地址是紧紧排列在一起的, 所以 redis 中字符串参数的传递直接使用 char* 指针。

可能有人会疑问,仅仅通过一个 char 指针如何确定当前字符串的类型,其实由于 sdshdr 内存分配禁止内存对齐,所以 sds[-1] 其实指向的就是 flags 字段的内存地址,通过 flags 字段又可以得到当前 sds 属于哪种类型,进而可以读取头部字段确定 sds 的相关属性。

接下来我们讲讲 sdshdr 相对于传统的 C 语言字符串,性能的提升在哪,以及具有哪些便捷的点。

首先,对于传统的 C 字符串,我想要获取字符串的长度,至少需要 O(n) 遍历一遍数组才行,而我们 sds 只需要 O(1) 的取 len 字段的值即可。

其次,也是非常重要的一个设计,如果我们初始分配了一个字符串对象,那么如果我要在这个字符串后面追加内容的话,限制于数组的长度一经初始化是不能修改的,我们至少需要分配一个足够大的数组,然后将原先的字符串进行一个拷贝。

sdshdr 每次为一个 sds 分配内存的时候都会额外分配一部分暂不使用的内存空间,一般额外的内存会等同于当前字符串占用的内存大小,如果超过 1MB,那么额外空间的内存大小就是 1MB。每当执行 sdscat 这种方法的时候,程序会用 alloc-len 比较下剩下的空余内存是否足够分配追加的内容,如果不够自然触发内存重分配,而如果剩余未使用内存空间足够放下,那么将直接进行分配,无需内存重分配。

通过这种预分配策略, SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

最后,对于常规的 C 语言字符串,它通过判断当前字符是否是空字符来决定字符串的结尾,所以就要求你的字符串中不能包含甚至一个空字符,否则空字符后面的字符都不能作为有效字符被读取。而对于某些具有特殊格式要求的,需要使用空字符进行分隔作用的,那么传统的 C 字符串就无法存储了,而我们的 sds 不是通过空字符判断字符串结尾,而是通过 len 字段的值判断字符串的结尾,所以说,sds 还具备二进制安全这个特性,即它可以安全的存储具备特殊格式要求的二进制数据。

关于 sds 我们就简单说到这,它是一种改良版的 C 字符串,兼容 C 语言中既有的函数 api,也通过一些手段提升了某些操作的性能,值得大家借鉴。


二、链表

链表这种数据结构相信大家也不陌生,有很多类型,比如单向链表,双向链表,循环链表等,链表相对于数组来说,一是不需要连续的内存块地址,二是删除和插入的时间复杂度是 O(1) 级别的,非常的高效,但比不上数组的随机访问查询方式。

一样的那句话,没有最好的数据结构,只有恰到好处的数据结构,比如我们后面要介绍的更高层次的数据结构,字典,它的底层其实就依赖的链表规避哈希冲突,具体的我们后面再说。

redis 中借助 C 语言实现了一个双向链表结构:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

pre 指针指向前一个节点,next 指针指向后一个节点,value 指向当前节点对应的数据对象。我盗一张图描述整个串联起来的链表结构:


虽然我通过链表的第一个头节点就可以遍历整个链表,但在 redis 向上封装了一层结构,专门用于表示一个链表结构:

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

head 指向链表的头节点,tail 指向链表的尾节点,dup 函数用于链表转移复制时对节点 value 拷贝的一个实现,一般来说用等于号足以,但某些特殊情况下可能会用到节点转移函数,默认可以给这个函数赋值 NULL 即表示使用等于号进行节点转移。free 函数用于释放一个节点所占用的内存空间,默认赋值 NULL 的话,即使用 redis 自带的 zfree 函数进行内存空间释放,我们也可以来看一下这个 zfree 函数。

void zfree(void *ptr) {
#ifndef HAVE_MALLOC_SIZE
    void *realptr;
    size_t oldsize;
#endif

    if (ptr == NULL) return;
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_free(zmalloc_size(ptr));
    free(ptr);
#else
    realptr = (char*)ptr-PREFIX_SIZE;
    oldsize = *((size_t*)realptr);
    update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
    free(realptr);
#endif
}

这里会涉及到一个内存对齐的概念,就比如一个 64 位的操作系统,一次内存 IO 会固定取出 8 个字节的内存数据出来,如果某个变量横跨了两个八字节段,那么 CPU 需要进行两次的 IO 才能完整取出该变量的数据,引入内存对齐,是为了保证任意变量的内存分配不会出现上述的横跨情况,具体的操作手法就是填充无用的内存位,当然这必然会造成内存碎片,不过这也是一种以空间换时间的策略,你也可以禁用它。

函数的上半部分是做一些判断,如果确定了该指针指向的数据结构占用的总内存,则直接调用 free 函数进行内存的释放,否则需要进行一个计算。redis 中的 zmalloc 在每一次内存数据分配的时候都会追加一个 PREFIX_SIZE 的头部数据块,它的值等于当前系统的最大寻址空间,比如 64 CPU的话,PREFIX_SIZE 就会占用到 8 个字节,并且这 8 个字节内部存储的是当前数据实际占用内存大小。

所以这里的话,ptr 指针向低位移动就是指向头部 PREFIX_SIZE 字段首地址,然后取出里面保存的值,也就是当前数据结构实际占用的内存大小,最后加上它自身传入 update_zmalloc_stat_free 函数中修改 used_memory 内存记录指针的值,并在最后调用 free 函数释放内存,包括头部的部分。

其实我们扯远了,继续看数据结构,这里如果还不是很明白的话,没关系,后面我们还会继续讲的。

match 函数依然是一个多态的实现,只给出了定义,具体实现由你来决定,你也可以选择不实现,它用于比较两个链表节点的 value 值是否相等。返回 0 表示不相等,返回 1 表示相等。

最后一个 len 字段描述的是,整个链表中所包含的节点数量。以上就是 redis 中链表的一个基本的定义,加上 list,最终链表结构在 redis 中呈现的抽象图大概是这样的,依然盗的图:


综上,我们介绍了 redis 中链表的一个基本实现情况,总结一下,它是一个双端链表,也就是查找某个节点的前后节点的时间复杂度都在 O(1),也是一个无环并具有首尾节点指针的链表,初次之外,还具有三个多态函数,用于节点间的复制、比较以及内存释放,需要使用者自行实现。

原文https://www.cnblogs.com/yangming1996/p/11521492.html

链接: https://www.fly63.com/article/detial/5317

双向数据绑定与单向数据绑定的各自优势和关系

在react中是单向数据绑定,而在vue和augular中的特色是双向数据绑定。为什么会选择两种不同的机制呢?我猜测是两种不同的机制有不同的适应场景,查了一些资料后,总结一下。

原生JS数据绑定的实现

双向数据绑定是非常重要的特性 —— 将JS模型与HTML视图对应,能减少模板编译时间同时提高用户体验。我们将学习在不使用框架的情况下,使用原生JS实现双向绑定 —— 一种为Object.observe

JavaScript判断数据类型的多种方法【 js判断一个变量的类型】

js判断数据类型的多种方法,主要包括:typeof、instanceof、 constructor、 prototype.toString.call()等,下面就逐一介绍它们的异同。

javascript中的typeof返回的数据类型_以及强制/隐式类型转换

由于js为弱类型语言拥有动态类型,这意味着相同的变量可用作不同的类型。 typeof 运算符返回一个用来表示表达式的数据类型的字符串,目前typeof返回的字符串有以下这些: undefined、boolean、string、number、object、function、“symbol

使用typeof obj===‘object’潜在的问题,并不能确定obj是否是一个对象?

在js中我们直接这样写typeof obj===‘object’有什么问题呢?发现Array, Object,null都被认为是一个对象了。如何解决这种情况,能保证判断obj是否为一个对象

js进制数之间以及和字符之间的转换

js要处理十六进制,十进制,字符之间的转换,发现有很多差不多且书写不正确的方法.一个一个实践才真正清楚如何转换,现在来记录一下它们之间转换的方法。

js判断数字是奇数还是偶数的2种方法实现

奇数和偶数的判断是数学运算中经常碰到的问题,这篇文章主要讲解通过JavaScript来实现奇偶数的判断。2种判断方法:求余% 、&1

js算法_判断数字是否为素数/质数

质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。比如100以内共25个,js实现代码如下。

Js数据类型转换_JavaScript 那些不经意间发生的数据类型自动转换

JavaScript自动类型转换真的非常常见,常用的一些便捷的转类型的方式,都是依靠自动转换产生的。比如 转数字 : + x 、 x - 0 , 转字符串 : \\\"\\\" + x 等等。现在总算知道为什么可以这样便捷转换。

Js中实现XML和String相互转化

XML是标准通用标记语言 (SGML) 的子集,非常适合 Web 传输。XML 提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。 这篇文章主要介绍Js中实现XML和String相互转化

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!