最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

简单动态字符串SDS

  • 今天我们正式进入redis5源码的学习。redis是一个由C语言编写、基于内存、单进程、可持久化的Key-Value型数据库,解决了磁盘存取速度慢的问题,大幅提升了数据访问速度,所以它常常被用作缓存。
  • 那么为什么redis会如此之快呢?让我们首先从内部存储的数据结构的角度,一步一步揭开它神秘的面纱。
  • 在redis的set、get等常用命令中,最常使用的就是字符串类型。在redis中,存储字符串的数据类型,叫做简单动态字符串(Simple Dynamic String),即SDS,它在redis中是如何实现的呢?

引入

  • 回顾我们之前在PHP7源码分析中讲到的zend_string结构:
  1. struct _zend_string {
  2. zend_refcounted_h gc; /*引用计数,与垃圾回收相关,暂不展开*/
  3. zend_ulong h; /* 冗余的hash值,计算数组key的哈希值时避免重复计算*/
  4. size_t len; /* 存长度 */
  5. char val[1]; /* 柔性数组,真正存放字符串值 */
  6. };
  • 之前提到,设计一个存储字符串的结构,最重要的就是存储其长度和字符串本身的内容。至于为什么存储长度,是为了解决二进制安全的问题,且能够以常量复杂度访问到字符串的长度,详情可以到上述文章中查看。

SDS新老结构的对比

  • 在redis3.2.x之前,SDS的存储结构如下:
  1. struct sdshdr {
  2. int len; //存长度
  3. int free; //存字符串内容的柔性数组的剩余空间
  4. char buf[]; //柔性数组,真正存放字符串值
  5. };
  • 以“Redis”字符串为例,我们看一下它在旧版SDS结构中是如何存储的:

  • free字段为0,代表buf字段没有剩余存储空间
  • len字段为5,代表字符串长度为5
  • buf字段存储真正的字符串内容“Redis”
  • 存储字符串内容的柔性数组占用内存大小为6字节,其余字段所占用8个字节(4+4+6 = 14字节)
  • 在新版本redis5中,为了进一步减少字符串存储过程中的内存占用,划分了5种适应不同字符串长度专用的存储结构:
  1. struct __attribute__ ((__packed__)) sdshdr5 {
  2. unsigned char flags; //低三位存储类型,高5位存储字符串长度,这种字符串存储类型很少使用
  3. char buf[]; //存储字符串内容的柔性数组
  4. };
  5. struct __attribute__ ((__packed__)) sdshdr8 {
  6. uint8_t len; //字符串长度
  7. uint8_t alloc; //已分配的总空间
  8. unsigned char flags; //标识是哪种存储类型
  9. char buf[]; //存储字符串内容的柔性数组
  10. };
  11. struct __attribute__ ((__packed__)) sdshdr16 {
  12. uint16_t len; //字符串长度
  13. uint16_t alloc; //已分配的总空间
  14. unsigned char flags; //标识是哪种存储类型
  15. char buf[]; //存储字符串内容的柔性数组
  16. };
  17. struct __attribute__ ((__packed__)) sdshdr32 {
  18. uint32_t len; //字符串长度
  19. uint32_t alloc; //已分配的总空间
  20. unsigned char flags; //标识是哪种存储类型
  21. char buf[]; //存储字符串内容的柔性数组
  22. };
  23. struct __attribute__ ((__packed__)) sdshdr64 {
  24. uint64_t len; //字符串长度
  25. uint64_t alloc; //已分配的总空间
  26. unsigned char flags; //标识是哪种存储类型
  27. char buf[]; //存储字符串内容的柔性数组
  28. };
  • 我们可以看到,SDS的存储结构由一种变成了五种,他们之间的不同就在于存储字符串长度的len字段和存储已分配字节数的alloc字段的类型,分别占用了1、2、4、8字节(不考虑sdshdr5类型),这决定了这种结构能够最大存储多长的字符串(2^8/2^16/2^32/2^64)。
  • 我们注意,这些结构体中都带有attribute ((_packed_))关键字,它告诉编译器不进行结构体的内存对齐。这个关键字我们下文会详细讲解。关于结构体内存对齐是什么,请参考【PHP7源码学习】2019-03-08 PHP内存管理2笔记。

利用gdb查看SDS的存储结构

  • 接着说我们之前存储“Redis”的例子,我们需要先对其进行gdb,观察”Redis”字符串使用了哪种结构,gdb的步骤如下:
  • 首先到官网下载源码包,编译
  • 启动一个终端,进入redis源码的src目录下,后台启动一个redis-server:
  1. ./redis-server &
  • 然后查看当前redis的后台进程的pid:
  1. ps -aux |grep redis
  • 记录下这个pid,然后利用gdb -p命令调试该端口(如端口号是11430):
  1. gdb -p 11430
  • 接着在setCommand函数处打一个断点,这个函数用来执行set命令,然后使用c命令执行到断点处:
  1. (gdb) b setCommand
  2. (gdb) c
  • 有了redis服务端,我们还要启动一个redis客户端,接下来启动另一个终端(同样在src目录下),启动客户端:
  1. ./redis-cli
  • 接着我们在redis客户端中执行set命令,我们设置了一个key为Redis,值为1的key-value对:
  1. 127.0.0.1:6379> set Redis 1
  • 返回我们之前终端中的服务端,我们发现它停在了setCommand处:
  • 接着一直n下去,直到setGenericCommand函数,s进去,就可以看到我们的key “Redis”了,它是一个rObj结构(我们暂时不看),里面的ptr就指向字符串结构的buf字段,我们强转一下,能够看到字符串内容“Redis”。
  • 我们知道,无论是这五种结构中的哪一种,其前一位一定是flag字段,我们打印它的值,它的值为1。那么1是什么含义呢,它被用来标识是这五种字符串结构中的哪一种:
  1. #define SDS_TYPE_5 0
  2. #define SDS_TYPE_8 1
  3. #define SDS_TYPE_16 2
  4. #define SDS_TYPE_32 3
  5. #define SDS_TYPE_64 4
    • 我们可以看到,它总共占用3+6 = 9字节,比之前的14字节节省了5字节。通过对之前长度和alloc字段的细化(由之前的int转为int8、int16、int32、int64),这样一来,就会大大节省redis存储字符串所占用的内存空间。内存空间是非常宝贵的,而且redis中最常用的数据类型就是字符串类型。虽然看起来节省的空间很少,但由于它非常常用,所以这样做的好处是无穷大的。

    关键字attribute ((packed))的作用

    • 该关键字用来告知编译器不需要进行结构体的内存对齐。
    • 为了测试attribute ((packed))关键字在redis字符串结构中的作用,我们写如下一段测试代码:
    1. #include "stdio.h"
    2. int main(){
    3. struct __attribute__ ((__packed__)) sdshdr64{
    4. long long len;
    5. long long alloc;
    6. unsigned char flags;
    7. char buf[];
    8. };
    9. struct sdshdr64 s;
    10. s.len = 1;
    11. s.alloc = 2;
    12. printf("sizeof sds64 is %d", sizeof(s));
    13. return 1;
    14. }
    • 我们定义一个结构体,其字段和redis中的字符串结构基本一致。如果加上attribute ((packed)) ,应该不是内存对齐的。如果去掉它,就应该是内存对齐的,会比前一种情况更加浪费内存,所以会对齐会节省内存。我们现在猜想的内存结构图应该如下所示:
    • 我们首先验证加上attribute ((packed)) 的情况,我们预期应该是不对齐的,在gdb中内存地址如下:
    • 我们看到,buf确实是从0×171地址处开始的,并没有对齐。那么我们看另一种情况,去掉attribute ((packed)),再进行gdb调试:
    • 大家看这张图,是不是和上一张图一摸一样(我真的去掉了并且重新编译了!!!)。这说明在当前情况下,redis字符串结构中的柔性数组的起始位置并不受是否加attribute ((packed))关键字而影响,是紧跟在结构体后面的,所以节省内存这个说法并不成立。(不一定是所有情况下柔性数组都紧跟在结构体后面,如果把buf的类型改为int就不是紧跟在后面,大家感兴趣可以自己调试一下)。
    • 那么,为什么这里要加上attribute ((packed)呢?我们换个思路,既然不能节省空间,那么能不能节省时间呢?会不会操作非对齐的结构体性能更好、效率更高,或者是写代码更方便、可阅读性强呢?
    • 笔者在这里的猜想是比较方便工程中的代码编写,可阅读性更强,我的参考如下:
    • 在sizeof运算符中,它返回的是结构体占用空间的大小,和是否对齐有很大关系。比如上例中的结构体,如果不加上attribute((packed)),说明需要内存对齐,sizeof(struct s)的回结果应该为24(8+8+8);如果加上attribute ((packed)),说明不需要对齐,返回的结果应该为17(8+8+1),我们打印一下:
    • 结果和我们预期的一致。我们知道,在之前我们gdb的时候,rObj的指针直接指向柔性数组buf的地址,即字符串内容的起始地址。那么如何知道它的len和alloc的值呢?只需要用buf的地址ptr – sizeof(struct s)即可。在这里,如果加上attribute ((packed)),它返回的结果是17,那么直接做减法,就可以到结构体开头的位置,即可直接读取len的值。如果不加attribute ((packed)),它返回的结果是24,做减法就会的到错误的位置,这就是原因所在,在源码中我们也可以看到,它确实是这么找到当前字符串结构体的头部的:
    1. #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
    2. #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
    • 那么我们可能会问了,你刚才不是还用buf[-1]也能访问到吗?或者buf[-17],应该也能访问到len吧。这里笔者简单猜想可能是上一种写法,在工程的代码实现中,更加易读也更加方便。更加深层的原因仍待讨论。

转载请注明:XAMPP中文组官网 » 简单动态字符串SDS