Redis 设计与实现，看 SDS(Simple Dynamic String) 感悟

2022-10-25 14:58:01

Redis 设计与实现，看 SDS(Simple Dynamic String) 感悟

今天在看 Redis 设计与实现这本书的时候，发现了里面系统定义的数据结构 SDS，中文名为简单动态字符串。对其设计的思想挺有收获的。

SDS 的定义，位于 sds.h/sdshdr 中：结构如下：

struct sdshdr{
    // len 为 buf 数组中已使用字节的数量，等于 SDS 所保存的字符串的长度
    int len;
    
    // buf 中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
}

SDS 与 C 字符串的区别：

C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符串最后一个元素总为 \0
C 字符串并不记录自身的长度信息，所以取长度的操作为 O(N)，SDS 的取长度操作为 O(1)
C 语言容易缓冲区溢出，由于其不记录自身长度所带来的。

接下来是关键： 空间预分配和惰性空间释放 这两种优化策略。

空间预分配

主要用于优化 SDS 的字符串增长操作：当 SDS 的API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展时，程序不仅会为 SDS 分配修改所需要必须要的空间，还会为 SDS 分配额外未使用的空间。

额外分配的算法如下：

if len < 1MB
    free = len;
else
     free = 1MB

假设进行修改之后， SDS 的长度小于 1MB，假设修改之后 SDS 的 len 为 13，那么 free 也为 13。 SDS 的 buf 长度将为 13 + 13 + 1 。其中 1 字节为 "\0"；

惰性空间释放

释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性，将这些字节的数量记录起来。并等待将来使用。

假设有个如下的 SDS 结构：

进行 sdstrim(s, "XY");// 移除 SDS 字符串中所有的 'X' 和 'Y'

SDS 就变成了如下这样，

可以看到，SDS 并没有释放多出来的 5 字节空间，而是将这五个字节空间作为未使用空间保留在 SDS 里面。如果将来要对 SDS 进行增长的话，这些未使用的空间就可以排上用场了。

假设我们现在用进行 sdscat(s, "KO");
那么结构就变成了如下：

这样就避免了缩短字符串时所带来的的内存重分配操作。今天在坐公交时看到的这个数据结构的实现，这个设计思想应该是带给我收获最多的。

预分配，预处理，延时的思想。
在 C# 中，我记得有个 LazyInitialization，延时加载这玩意，如有一个对象和类是属于延时加载的，那么只有在真正用到时才会去加载它。
也让我想到了 RFC2616 HTTP/1.1 协议中的一个 HTTP 连接池的这个标准的一个实现，在 HttpWebRequest 中一个 Host 默认的存在的连接池是 2 个，但是可以通过 ServicePointManager.DefaultConnectionLimit 获取到默认的连接限制数

The maximum number of concurrent connections allowed by a ServicePoint object. The default connection limit is 10 for ASP.NET hosted applications and 2 for all others. When an app is running as an ASP.NET host, it is not possible to alter the value of this property through the config file if the autoConfig property is set to true. However, you can change the value programmatically when the autoConfig property is true. Set your preferred value once, when the AppDomain loads.

这种思想可以运用在哪里呢？我思考了一下：
不知道准确不准确，想到了一个缓存的。以博客园首页的前 20 篇文章为例，预分配：设置每篇文章在 Redis 中的缓存时间为10 分钟， 600秒。假设在 600 秒内，有用户点击了第一篇文章，那么更新其缓存失效时间为 1200 秒（基于第一个用户点击，那么可能就会有第二个用户点击之瞎说理论），假设 1200 秒内没有用户点击该文章，那么降低其缓存时间为 600，依次类推。

不太靠谱的伪代码：

set blog_item_1 expired_time 600;
blog_display_time = current_time;

if have one user click blog_item_1
    var blog_click_time = current_Time;
    expired_time = expired_time * 2;

if current_time > blog_click_time.addSecond(600) && have one user click blog_item_1
    expired_time = expired_time * 2;

if current_time < blog_display_time.addSecond(1200)
    expired_time = exipred_time / 2;

码农公寓

Redis 设计与实现，看 SDS(Simple Dynamic String) 感悟

空间预分配

惰性空间释放

相关文章