细品Redis高性能数据结构之SDS

背景

redis之所以快，除了他是基于内存存储的，还有优秀的IO框架外更离不了其底层高性能数据结构的设计。现在我们来细细品一下redis的高新能数据结构是如何设计的。

Redis数据结构

redis有五种数据结构，分别是String，list（列表），Set（集合），Hash（哈希），Zset（有序结合）。这五种数据结构代表的是他的Value值的数据结构。今天我们来看redis的String类型。动态字符串SDS。

SDS（Simple Dynamic String）

1. redis中的字符串是一个动态可修改的字符串，类似于java中的ArrayList，可以进行动态扩容，采用的是预分配冗余空间的方式来减少内存空间频繁的扩容。也可以想一下hashMap的扩容方式(其中的负载因子的作用)
2. 在这里就需要和java的String做一下区分了，java中的string是通过char数组实现的，并且它是不可变的。因为char数组被final修饰了（如果"+"拼接是通过编译的时候转译为STringBuilder进行拼接的），所以说redis的String和java的string还是千差万别的。
3. Redis的动态字符串在占用内存大小为1M以下的时候，是以翻倍的形式增长的。当超过1M的时候是以每次1M进行增长的。 需要注意的是最大扩展的空间为512M.
4. 当有其值是一个整数的时候还可以进行自增的操作的（）在这里我就就有点蒙蔽了。那他既然是一个String字符串 为什么是整数？是整数字符串吗？ //todo

redis SDS源码理解

1. redis时使用C语言写的，那为什么不直接使用C语言函数库里里面的字符串呢？拿来即用。

由于C语言函数哭的字符串是以NULL为结束符，而获取BNULL结尾字符串的长度是通过strlen把标准库函数，这个函数的复杂度为O（n）所以这是redis无法忍受的，所以redis就自己实现了SDS，可变的动态字符串。

1. redis SDS 的结构体

struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}

2. 其中的数组容量和数组长度为什么需要两个呢？

也就是我们上文说的为了扩容的时候的性能问题，在扩容的时候当没有预留空间的话，每次都要进行copy的工作，创建一个新的content数组然后copy数据，原来的数据被回收。这个过程是很耗费性能的。所以加了预留空间的话但添加不大的数据量的时候可以减少扩容次数。（其中hashMap的数组扩容加负载因子为0.75，也是类似的道理（遵循0.75的计算像是根据泊松分布））

3. 容量大小为什么用泛型T表示呢？

我们可以注意到他的长度都是泛型来表示的那么为什么不使用int 或者 long 等类型呢。Redis 为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。那这么一个判断选择类型的的过程岂不是也是浪费性能（时间换空间的概吧）。

4. redis字符串的两种存储方式emstr 和 raw 存储形式

1. Redis 的字符串有两种存储方式，在长度特别短时，使用 emb 形式存储 (embeded)，当 长度超过 44 时，使用 raw 形式存储。
2. redis底层的对象都有RedisObject对象头的结构体（说到这里是否有想到java中的对象头的作用呢）下面时对象头的信息
3. 那也就是说我们每存储一个String 最起码有19个字节。

struct RedisObject {
int4 type; // 4bits
int4 encoding; // 4bits
int24 lru; // 24bits
int32 refcount; // 4bytes
void *ptr; // 8bytes，64-bit system
} robj;

5. 那为什么要分两种存储方式？为什么两种方式的区分是44呢？

• 内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等 等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符 串再稍微长一点，那就是 64 字节的空间。如果总体超出了 64 字节，Redis 认为它是一个 大字符串，不再使用 emdstr 形式存储，而该用 raw 形式 （来自redis深度历险）
• 通俗一点说吧，redis的内存开辟是有规格的，只能开辟32，64这些。由于redis string 的基础数据就得占用19 所以默认分配 32 这个32大小的也就是rmbstr的存储方式。 而raw 格式是分配64 而基础数据是19， content的字符串是以/0结尾的。所以也就是剩下44了，那就是在44的时候redis会认为这个 字符串为大字符串而采用raw方式存储（这里是我自己的理解）。

在这里插入图片描述

6. 扩容方式

1. SDS扩容在低于1M的时候是以2倍进行扩容的，这里也就是为了保证冗余空间，防止多次扩容带来性能损耗。但是超过1M后，在性能和空间上的衡量后采用的是1M进行扩容。

总结

• SDS 简单的动态字符串，他是可变的字符串。
• 为了提高字符串的追加性能，拥有冗余空间
• 在小于1M的时候是翻倍扩容，在大于1M的时候是扩容增加1M
• 底层拥有两种存储方式 emdstr 存储方式和 raw 存储方式。