Redis字符串SDS（simple dynamic string）

落日映苍穹つ 2023-03-04 06:44 65阅读 0赞

Redis字符串SDS（simple dynamic string）

一 SDS结构定义

  1. struct { 
  2.   int len;  //记录buf中已使用的字节数量
  3.   int free;  //buf中未使用的字节数量
  4.   char buf[]; //字节数组
  5. }

format_png

二 SDS与C字符串的区别

  • C字符串获取字符串长度需要遍历字节数组，时间复杂度O(N)。SDS设置和更新长度在API执行时完成，获取长度时间复杂度O(1)
  • 由于C字符串扩容可能导致buffer overflow，缩减字符串会导致内存泄漏。SDS具有一套内存分配策略，可以杜绝这些问题

三 SDS内存分配策略

  • 对SDS修改后小于1M的情况，会计算出扩容后的len*2+1，1是为了保留空字符串。例如”hello”,len=5,free=0，buf=6，拼接为”hello world”后，len=11，free=11，buf=27。这样做是为了减少分配次数以提高性能。
  • 修改后大于1M，会分配1M对free空间。例如扩容后len=2M，buf=3M+1byte。
  • 惰性空间释放，当使用SDS API进行字符串缩减，并不会立即释放free空间，避免再此扩容造成性能损耗。SDS提供了相应的API真正的释放空间
  • 兼容部分C字符串函数，部分函数同样支持SDS字符串
  • 二进制安全，因为SDS通过len判断字符串是否结束。

发表评论

表情：
评论列表 （有 0 条评论，65人围观）

还没有评论，来说两句吧...

相关阅读