redis的String数据结构底层实现

redis的String数据结构底层实现

SDS结构（simple dynamic string）

一个SDS值的数据结构，主要由len、free、buf[]这三个属性组成。

1
2
3
4
5
6
7
8

struct sdshdr{

  int free; // buf[]数组未使用字节的数量

  int len; // buf[]数组所保存的字符串的长度

  char buf[]; // 保存字符串的数组
}

• 其中buf[]为实际保存字符串的char类型数组；
• free表示buf[]数组未使用字节的数量；
• len表示buf[]数组所保存的字符串的长度。

特点

• 效率高

  使用redis，经常会通过STRLEN命令得到一个字符串的长度，在SDS结构中len属性记录了字符串的长度，所以我们获取一个字符串长度直接取len的值，复杂度是O(1)。

  而如果用C字符串，在获取一个字符串长度时，需对整个字符串进行遍历，直至遍历到空格符结束（C中遇到空格符代表一个完整字符串），此时的复杂度是O(N)。

  在高并发场景下频繁遍历字符串，获取字符串的长度很有可能成为redis的性能瓶颈，所以SDS性能更好一些。

• 数据溢出

  当我们需要修改数据时，首先会检查当前SDS空间len是否满足，不满足则自动扩容空间至修改所需的大小，然后再执行修改

• 内存重分配策略

  • 空间预分配

    空间预分配策略用于优化SDS字符串增长操作，当修改字符串并需对SDS的空间进行扩展时，不仅会为SDS分配修改所必要的空间，还会为SDS分配额外的未使用空间free，下次再修改就先检查未使用空间free是否满足，满足则不用在扩展空间。

    通过空间预分配策略，redis可以有效的减少字符串连续增长操作，所产生的内存重分配次数。

    额外分配未使用空间free的规则：

    • 如果对 SDS 字符串修改后，len 值小于 1M，那么此时额外分配未使用空间 free 的大小与len相等。
    • 如果对 SDS 字符串修改后，len 值大于等于 1M，那么此时额外分配未使用空间 free 的大小为1M。

  • 惰性空间释放

    惰性空间释放策略则用于优化SDS字符串缩短操作，当缩短SDS字符串后，并不会立即执行内存重分配来回收多余的空间，而是用free属性将这些空间记录下来，如果后续有增长操作，则可直接使用。

• 数据格式多样性

  C字符串中的字符必须符合某些特定的编码格式，C字符串以\0空字符结尾标识一个字符串结束，所以字符串里边是不能包含\0的，不然就会被误认是多个。

  由于这种限制，使得C字符串只能保存文本数据，像音视频、图片等二进制格式的数据是无法存储的。

  redis 会以处理二进制的方式操作Buf数组中的数据，所以对存入其中的数据未做任何的限制、过滤，只要存进来什么样，取出来还是什么样。