泰安营销型网站建设公司,计算机网络技术电商网站建设与运营,企业网站备案去哪里,asp网站建设公司目录
前言
为什么 Redis 不用 char*#xff1f;
char* 的结构设计
操作函数复杂度
SDS 的设计思想
SDS 结构设计
SDS 操作效率
紧凑型字符串结构的编程技巧
小结 前言 对于 Redis 来说#xff0c;键值对中的键是字符串#xff0c;值有时也是字符串在 Redis 中写入一…目录
前言
为什么 Redis 不用 char*
char* 的结构设计
操作函数复杂度
SDS 的设计思想
SDS 结构设计
SDS 操作效率
紧凑型字符串结构的编程技巧
小结 前言 对于 Redis 来说键值对中的键是字符串值有时也是字符串在 Redis 中写入一条用户信息记录了用户姓名、性别、所在城市等这些都是字符串如下所示此外Redis 实例和客户端交互的命令和数据也都是用字符串表示的那么既然字符串的使用如此广泛和关键就使得在实现字符串时需要尽量满足以下三个要求 能支持丰富且高效的字符串操作比如字符串追加、拷贝、比较、获取长度等能保存任意的二进制数据比如图片等能尽可能地节省内存开销其实如果你开发过 C 语言程序应该就知道在 C 语言中可以使用 char* 字符数组来实现字符串同时C 语言标准库 string.h 中也定义了多种字符串的操作函数比如字符串比较函数 strcmp、字符串长度计算函数 strlen、字符串追加函数 strcat 等这样就便于开发者直接调用这些函数来完成字符串操作所以这样看起来Redis 好像完全可以复用 C 语言中对字符串的实现呀但实际上在使用 C 语言字符串时经常需要手动检查和分配字符串空间而这就会增加代码开发的工作量而且图片等数据还无法用字符串保存也就限制了应用范围那么从系统设计的角度来看该如何设计实现字符串呢其实Redis 设计了简单动态字符串(Simple Dynamic StringSDS)的结构用来表示字符串相比于 C 语言中的字符串实现SDS 这种字符串的实现方式会提升字符串的操作效率并且可以用来保存二进制数据下面介绍下 SDS 结构的设计思想和实现技巧这样就既可以掌握char* 实现方法的不足和 SDS 的优势还能学习到紧凑型内存结构的实现技巧如果要在自己的系统软件中实现字符串类型就可以参考 Redis 的设计思想来更好地提升操作效率节省内存开销好接下来先来了解下为什么 Redis 没有复用 C 语言的字符串实现方法 为什么 Redis 不用 char* 实际上要想解答这个问题需要先知道 char* 字符串数组的结构特点还有 Redis 对字符串的需求是什么所以下面就来具体分析一下 char* 的结构设计 首先来看看 char* 字符数组的结构char*字符数组的结构很简单就是一块连续的内存空间依次存放了字符串中的每一个字符比如下图显示的就是字符串“redis”的char*数组结构从图中可以看到字符数组的最后一个字符是“\0”这个字符的作用是什么呢其实C 语言在对字符串进行操作时char* 指针只是指向字符数组的起始位置而字符数组的结尾位置就用“\0”表示意思是指字符串的结束这样一来C 语言标准库中字符串的操作函数就会通过检查字符数组中是否有“\0”来判断字符串是否结束比如strlen 函数就是一种字符串操作函数它可以返回一个字符串的长度这个函数会遍历字符数组中的每一个字符并进行计数直到检查的字符为“\0”此时strlen 函数会停止计数返回已经统计到的字符个数下图显示了 strlen 函数的执行流程 再通过一段代码来看下“\0”结束字符对字符串长度的影响这里创建了两个字符串变量 a 和 b分别给它们赋值为“red\0is”和“redis\0”然后用 strlen 函数计算这两个字符串长度如下所示 当程序执行完这段代码后输出的结果分别是 3 和 5表示 a 和 b 的长度分别是3个字符和5个字符这是因为 a 中在“red”这 3 个字符后就有了结束字符“\0”而 b 中的结束字符是在“redis”5 个字符后也就是说char* 字符串以“\0”表示字符串的结束其实会给我们保存数据带来一定的负面影响如果要保存的数据中本身就有“\0”那么数据在“\0”处就会被截断而这就不符合 Redis 希望能保存任意二进制数据的需求了 操作函数复杂度 而除了 char* 字符数组结构的设计问题以外使用“\0”作为字符串的结束字符虽然可以让字符串操作函数判断字符串的结束位置但它也会带来另一方面的负面影响也就是会导致操作函数的复杂度增加还是以 strlen 函数为例该函数需要遍历字符数组中的每一个字符才能得到字符串长度所以这个操作函数的复杂度是 O(N)再来看另一个常用的操作函数字符串追加函数 strcatstrcat 函数是将一个源字符串src 追加到一个目标字符串的末尾该函数的代码如下所示 从代码中可以看到strcat 函数和 strlen 函数类似复杂度都很高也都需要先通过遍历字符串才能得到目标字符串的末尾然后对于 strcat 函数来说还要再遍历源字符串才能完成追加另外它在把源字符串追加到目标字符串末尾时还需要确认目标字符串具有足够的可用空间否则就无法追加所以这就要求开发人员在调用 strcat 时要保证目标字符串有足够的空间不然就需要开发人员动态分配空间从而增加了编程的复杂度而操作函数的复杂度一旦增加就会影响字符串的操作效率这就不符合 Redis 对字符串高效操作的需求了综合以上在 C 语言中使用 char* 实现字符串的两大不足之处以后现在就对Redis 是如何对字符串的实现进行设计考虑的 SDS 的设计思想 因为 Redis 是使用 C 语言开发的所以为了保证能尽量复用 C 标准库中的字符串操作函数Redis 保留了使用字符数组来保存实际的数据但是和 C 语言仅用字符数组不同Redis 还专门设计了 SDS即简单动态字符串的数据结构 SDS 结构设计 首先SDS 结构里包含了一个字符数组 buf[]用来保存实际数据同时SDS 结构里还包含了三个元数据分别是字符数组现有长度 len、分配给字符数组的空间长度 alloc以及 SDS类型 flags其中Redis 给 len 和 alloc 这两个元数据定义了多种数据类型进而可以用来表示不同类型的 SDS稍后会具体介绍下图显示了 SDS 的结构 另外如果在 Redis 源码中查找过 SDS 的定义那可能会看到Redis 使用 typedef 给char* 类型定义了一个别名这个别名就是 sds如下所示 其实这是因为 SDS 本质还是字符数组只是在字符数组基础上增加了额外的元数据在Redis 中需要用到字符数组时就直接使用 sds 这个别名同时在创建新的字符串时Redis 会调用 SDS 创建函数 sdsnewlensdsnewlen 函数会新建 sds 类型变量也就是 char* 类型变量并新建 SDS 结构体把 SDS 结构体中的数组buf[] 赋给 sds 类型变量最后sdsnewlen 函数会把要创建的字符串拷贝给 sds 变量下面的代码就显示了 sdsnewlen 函数的这个操作逻辑 好了了解了 SDS 结构的定义后再来看看相比传统 C 语言字符串SDS 操作效率的改进之处 SDS 操作效率 因为 SDS 结构中记录了字符数组已占用的空间和被分配的空间这就比传统 C 语言实现的字符串能带来更高的操作效率还是以字符串追加操作为例Redis 中实现字符串追加的函数是 sds.c 文件中的 sdscatlen函数这个函数的参数一共有三个分别是目标字符串 s、源字符串 t 和要追加的长度 len源码如下所示 通过分析这个函数的源码可以看到sdscatlen 的实现较为简单其执行过程分为三步 首先获取目标字符串的当前长度并调用 sdsMakeRoomFor 函数根据当前长度和要追加的长度判断是否要给目标字符串新增空间这一步主要是保证目标字符串有足够的空间接收追加的字符串其次在保证了目标字符串的空间足够后将源字符串中指定长度 len 的数据追加到目标字符串最后设置目标字符串的最新长度下面一张图显示了 sdscatlen 的执行过程 所以到这里就能发现和 C 语言中的字符串操作相比SDS 通过记录字符数组的使用长度和分配空间大小避免了对字符串的遍历操作降低了操作开销进一步就可以帮助诸多字符串操作更加高效地完成比如创建、追加、复制、比较等这一设计思想非常值得学习此外SDS 把目标字符串的空间检查和扩容封装在了 sdsMakeRoomFor 函数中并且在涉及字符串空间变化的操作中如追加、复制等会直接调用该函数这一设计实现就避免了开发人员因忘记给目标字符串扩容而导致操作失败的情况比如使用函数 strcpy (char *dest, const char *src) 时如果 src 的长度大于 dest 的长度代码中也没有做检查的话就会造成内存溢出所以这种封装操作的设计思想同样值得学习那么除了使用元数据记录字符串数组长度和封装操作的设计思想SDS 还有什么优秀的设计与实现值得学习呢这就和刚才给你介绍的 Redis 对内存节省的需求相关了所以接下来就来看看 SDS 在编程技巧上是如何实现节省内存的 紧凑型字符串结构的编程技巧 前面有提到SDS 结构中有一个元数据 flags表示的是 SDS 类型事实上SDS 一共设计了 5 种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64这 5 种类型的主要区别就在于它们数据结构中的字符数组现有长度 len 和分配空间长度 alloc这两个元数据的数据类型不同因为 sdshdr5 这一类型 Redis 已经不再使用了所以这里主要来了解下剩余的 4 种类型以 sdshdr8 为例它的定义如下所示可以看到现有长度 len 和已分配空间 alloc 的数据类型都是 uint8_tuint8_t 是 8 位无符号整型会占用 1 字节的内存空间当字符串类型是 sdshdr8 时它能表示的字符数组长度包括数组最后一位\0不会超过 256 字节2 的 8 次方等于 256而对于 sdshdr16、sdshdr32、sdshdr64 三种类型来说它们的 len 和 alloc 数据类型分别是 uint16_t、uint32_t、uint64_t即它们能表示的字符数组长度分别不超过 2 的 16 次方、32 次方和 64 次方这两个元数据各自占用的内存空间在 sdshdr16、sdshdr32、sdshdr64 类型中则分别是 2 字节、4 字节和 8 字节实际上SDS 之所以设计不同的结构头即不同类型是为了能灵活保存不同大小的字符串从而有效节省内存空间因为在保存不同大小的字符串时结构头占用的内存空间也不一样这样一来在保存小字符串时结构头占用空间也比较少否则假设 SDS 都设计一样大小的结构头比如都使用 uint64_t 类型表示 len 和 alloc那么假设要保存的字符串是 10 个字节而此时结构头中 len 和 alloc 本身就占用了 16 个字节了比保存的数据都多了所以这样的设计对内存并不友好也不满足 Redis 节省内存的需求除了设计不同类型的结构头Redis 在编程上还使用了专门的编译优化来节省内存空间在刚才介绍的 sdshdr8 结构定义中可以看到在 struct 和 sdshdr8 之间使用了__attribute__ ((__packed__))如下所示 其实这里__attribute__ ((__packed__))的作用就是告诉编译器在编译 sdshdr8结构时不要使用字节对齐的方式而是采用紧凑的方式分配内存这是因为在默认情况下编译器会按照 8 字节对齐的方式给变量分配内存也就是说即使一个变量的大小不到 8个字节编译器也会给它分配 8 个字节举个例子假设定义了一个结构体 s1它有两个成员变量类型分别是 char 和 int如下所示虽然 char 类型占用 1 个字节int 类型占用 4 个字节但是如果你运行这段代码就会发现打印出来的结果是 8这就是因为在默认情况下编译器会给 s1 结构体分配 8 个字节的空间而这样其中就有 3 个字节被浪费掉了为了节省内存Redis 在这方面的设计上可以说是精打细算的所以Redis 采用了__attribute__ ((__packed__))属性定义结构体这样一来结构体实际占用多少内存空间编译器就分配多少空间比如用__attribute__ ((__packed__))属性定义结构体 s2同样包含 char 和 int两个类型的成员变量代码如下所示当运行这段代码时可以看到打印的结果是 5表示编译器用了紧凑型内存分配s2结构体只占用 5 个字节的空间好了总而言之如果在开发程序时希望能节省数据结构的内存开销就可以把__attribute__ ((__packed__))这个编程方法用起来 小结 主要介绍了 Redis 中字符串的设计与实现要知道字符串的实现需要考虑操作高效、能保存任意二进制数据以及节省内存的需求而 Redis 中设计实现字符串的方式就非常值得学习和借鉴需要重点关注三个要点分别是C 语言中使用 char* 实现字符串的不足主要是因为使用“\0”表示字符串结束操作时需遍历字符串效率不高并且无法完整表示包含“\0”的数据因而这就无法满足 Redis的需求Redis 中字符串的设计思想与实现方法Redis 专门设计了 SDS 数据结构在字符数组的基础上增加了字符数组长度和分配空间大小等元数据这样一来需要基于字符串长度进行的追加、复制、比较等操作就可以直接读取元数据效率也就提升了而且SDS 不通过字符串中的“\0”字符判断字符串结束而是直接将其作为二进制数据处理可以用来保存图片等二进制数据SDS 中是通过设计不同 SDS 类型来表示不同大小的字符串并使用__attribute__((__packed__))这个编程小技巧来实现紧凑型内存布局达到节省内存的目的
