redis简单动态字符串

Redis使用SDS(simple dynamic string)用作字符串默认实现。

1
2
3
4
5
6
7
8

struct sdshdr{
	//已使用buf数组的字节数量，也就是字符串长度
	int len;
	//未使用的长度
	int free;
	//保存字符串
	char buf[];
}

• SDS遵循C语言字符串以空字符串结尾，保留1个字节的空字符串’ ’，该空串不记入len中。

• C语言中，获取字符串长度需要遍历整个字符串，时间复杂度为O(n)，SDS中有len属性维护长度，时间复杂度为O(1)，Java里面String不可变，初始化的时候就记录了长度，时间复杂度啊也是O(n)。

• SDS空间分配策略杜绝缓冲区溢出的可能。当需要对SDS进行修改时，API会先检查SDS剩余空间是否满足需求，如不满足会自动扩容。

• SDS内存分配策略：

1. 空间预分配: 当SDS长度(len)小于1MB，程序会分配和len同样大小的未使用空间，这是len===free。例如修改后字符串长度为13字节，就会分配13字节的未使用空间，此时buf=len+free+1=13+13+1=27字节，其中1是’ ’。当SDS被修改后长度大于1MB，程序会分配1MB的未使用空间。即使len=50MB，也还是分配1MB的未使用空间。通过空间预分配策略，Redis可以有效减少连续修改字符串操作引起的内存分配次数。

2. 惰性空间释放: 当SDS字符串进行缩短操作时，程序不会立即重新分配内存来回收多的字节，而是用free记录，等待将来使用。例如SDS：abcxyz，修改成abc，SDS并不会释放多余出来的3个字节，而是将free=free+3，以备将来字符串增长操作时使用。

• SDS是二进制安全的。