阿里云代理商-阿里云服务器-阿里云数据库-重庆典名科技

如何实现一个扩容方便且二进制安全的字符串

发布时间: 2020-08-19 10:19:14文章作者: 网站编辑阅读量: 316
  如何实现一个扩容方便且二进制安全的字符串呢?
  
       注意 什么是二进制安全?通俗地讲,C语言中,用“\0”表示字符串的结束,如果字符串中本身就有“\0”字符,字符串就会被截断,即非二进制安全;若通过某种机制,保证读写字符串时不损害其内容,则是二进制安全。
  
  SDS既然是字符串,那么首先需要一个字符串指针;为了方便上层的接口调用,该结构还需要记录一些统计信息,如当前数据长度和剩余容量等,例如:
  
  struct sds {    int len;// buf 中已占用字节数
  
  int free;// buf 中剩余可用字节数
  
  char buf[];// 数据空间
  
  };
  
  SDS结构示意如图2-1所示,在64位系统下,字段len和字段free各占4个字节,紧接着存放字符串。
  
  Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点。
  
  1)有单独的统计变量len和free(称为头部)。可以很方便地得到字符串长度。
  
  2)内容存放在柔性数组buf中,SDS对上层暴露的指针不是指向结构体SDS的指针,而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容,兼容C语言处理字符串的各种函数。
  
  3)由于有长度统计变量len的存在,读写字符串时不依赖“\0”终止符,保证了二进制安全。
  
  注意 上例中的buf[]是一个柔性数组。柔性数组成员(flexible array member),也叫伸缩性数组成员,只能被放在结构体的末尾。包含柔性数组成员的结构体,通过malloc函数为柔性数组动态分配内存。
  
  之所以用柔性数组存放字符串,是因为柔性数组的地址和结构体是连续的,这样查找内存更快(因为不需要额外通过指针找到字符串的位置);可以很方便地通过柔性数组的首地址偏移得到结构体首地址,进而能很方便地获取其余变量。
  图2-1 SDS结构示意
  到这里我们实现了一个最基本的动态字符串,但是该结构是否有改进的空间呢?我们从一个简单的问题开始思考:不同长度的字符串是否有必要占用相同大小的头部?一个int占4字节,在实际应用中,存放于Redis中的字符串往往没有这么长,每个字符串都用4字节存储未免太浪费空间了。我们考虑三种情况:短字符串,len和free的长度为1字节就够了;长字符串,用2字节或4字节;更长的字符串,用8字节。
  
  这样确实更省内存,但依然存在以下问题。
  
  问题1:如何区分这3种情况?
  
  问题2:对于短字符串来说,头部还是太长了。以长度为1字节的字符串为例,len和free本身就占了2个字节,能不能进一步压缩呢?
  
  对于问题1,我们考虑增加一个字段flags来标识类型,用最小的1字节来存储,且把flags加在柔性数组buf之前,这样虽然多了1字节,但通过偏移柔性数组的指针即能快速定位flags,区分类型,也可以接受;对于问题2,由于len已经是最小的1字节了,再压缩只能考虑用位来存储长度了。
  
  结合两个问题,5种类型(长度1字节、2字节、4字节、8字节、小于1字节)的SDS至少要用3位来存储类型(23=8),1个字节8位,剩余的5位存储长度,可以满足长度小于32的短字符串。在Redis 5.0中,我们用如下结构来存储长度小于32的短字符串:
  
  struct __attribute__ ((__packed__))sdshdr5 {
  
  unsigned char flags; /* 低3位存储类型, 高5位存储长度 */    char buf[];/*柔性数组,存放实际内容*/};
  
  sdshdr5结构(图2-2)中,flags占1个字节,其低3位(bit)表示type,高5位(bit)表示长度,能表示的长度区间为0~31(25-1),flags后面就是字符串的内容。
  图2-2 sdshdr5结构
  而长度大于31的字符串,1个字节依然存不下。我们按之前的思路,将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同,sdshdr16结构如图2-3所示。
  图2-3 sdshdr16结构
  其中“表头”共占用了S[2(len)+2(alloc)+1(flags)]个字节。flags的内容与sdshdr5类似,依然采用3位存储类型,但剩余5位不存储长度。
  
  在Redis的源代码中,对类型的宏定义如下:
  
  #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 5.0中,sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下:
  
  struct __attribute__((__packed__))sdshdr8 {
  
  uint8_t len; /* 已使用长度,用1字节存储 */
  
  uint8_t alloc; /* 总长度,用1字节存储*/
  
  unsigned char flags; /* 低3位存储类型, 高5位预留 */
  
  char buf[];/*柔性数组,存放实际内容*/};
  
  struct __attribute__((__packed__))sdshdr16 {
  
  uint16_t len; /*已使用长度,用2字节存储*/
  
  uint16_t alloc; /* 总长度,用2字节存储*/
  
  unsigned char flags; /* 低3位存储类型, 高5位预留 */
  
  char buf[];/*柔性数组,存放实际内容*/};
  
  struct __attribute__((__packed__))sdshdr32 {
  
  uint32_t len; /*已使用长度,用4字节存储*/
  
  uint32_t alloc; /* 总长度,用4字节存储*/
  
  unsigned char flags;/* 低3位存储类型, 高5位预留 */
  
  char buf[];/*柔性数组,存放实际内容*/};
  
  struct __attribute__((__packed__))sdshdr64 {
  
  uint64_t len; /*已使用长度,用8字节存储*/
  
  uint64_t alloc; /* 总长度,用8字节存储*/
  
  unsigned char flags; /* 低3位存储类型, 高5位预留 */
  
  char buf[];/*柔性数组,存放实际内容*/};
  
  可以看到,这4种结构的成员变量类似,唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下。
  
  1)len:表示buf中已占用字节数。
  
  2)alloc:表示buf中已分配字节数,不同于free,记录的是为buf分配的总长度。
  
  3)flags:标识当前结构体的类型,低3位用作标识位,高5位预留。
  
  4)buf:柔性数组,真正存储字符串的数据空间。
  
  注意 结构最后的buf依然是柔性数组,通过对数组指针作“减一”操作,能方便地定位到flags。在2.2节中,我们能更直观地了解该用法。
  
  源码中的__attribute__((__packed__))需要重点关注。一般情况下,结构体会按其所有变量大小的最小公倍数做字节对齐,而用packed修饰后,结构体则变为按1字节对齐。以sdshdr32为例,修饰前按4字节对齐大小为12(4×3)字节;修饰后按1字节对齐,注意buf是个char类型的柔性数组,地址连续,始终在flags之后。packed修饰前后示意如图2-4所示。
  
  这样做有以下两个好处。
  
  ·节省内存,例如sdshdr32可节省3个字节(12-9)。
  

  ·SDS返回给上层的,不是结构体首地址,而是指向内容的buf指针。因为此时按1字节对齐,故SDS创建成功后,无论是sdshdr8、sdshdr16还是sdshdr32,都能通过(char*)sh+hdrlen得到buf指针地址(其中hdrlen是结构体长度,通过sizeof计算得到)。修饰后,无论是sdshdr8、sdshdr16还是sdshdr32,都能通过buf[-1]找到flags,因为此时按1字节对齐。若没有packed的修饰,还需要对不同结构进行处理,实现更复杂。

图2-4 packed修饰前后示意

联系客服免费领取更多阿里云产品新购、续费升级折扣,叠加官网活动折上折更优惠