Redis设计与实现之String

今天药忘吃喽~ 2023-07-24 13:20 16阅读 0赞

# Redis设计与实现之String #

### 文章目录 ###

*  Redis设计与实现之String
 *   *  Redis简介
     *  SDS
     *  SDS的定义
     *  SDS的优势
     *   *  常数复杂度获取字符串长度
         *  杜绝缓冲区溢出
         *  减少修改字符串时的内存分配次数
         *   *  空间预分配
             *  惰性空间释放
     *  字符串对象编码
     *   *  embstr和raw的区别
     *  扩展

## Redis简介 ##

Redis（Remote Dictionary Server )，即远程字典服务，是一个完全开源(遵守BSD协议)免费的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMyMzY2MzI5_size_16_color_FFFFFF_t_70]

Redis 与其他 key - value 缓存产品有以下三个特点：

*  Redis支持数据的持久化，可以将内存中的数据保存在磁盘中，重启的时候可以再次加载进行使用。
 *  Redis不仅仅支持简单的key-value类型的数据，同时还提供list，set，zset，hash等数据结构的存储。
 *  Redis支持数据的备份，即master-slave模式的数据备份。

## SDS ##

SDS全称是简单动态字符串（simple dynamic string）。

*  Redis只有在无需对字符串值进行修改的地方才会使用C语言原生的字符串，比如日志打印。
 *  对于需要对字符串的值可能会修改的地方，则使用SDS。所以Redis将SDS作为默认的字符串表示。比如存储字符串的时候就是使用SDS表示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMyMzY2MzI5_size_16_color_FFFFFF_t_70 1]

*  键值对的健是一个字符串对象，对象的底层实现是一个保存着字符串“msg”的SDS。
 *  键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world”的SDS。

![在这里插入图片描述][2020041200064335.png]

*  键值对的健是一个字符串对象，对象的底层实现是一个保存着字符串“fruits”的SDS。
 *  键值对的值是一个列表对象，列表对象包含了三个字符串对象，这三个字符串对象分别是由三个SDS对象实现：
    
     *  第一个SDS保存字符串“apple”,
     *  第二个SDS保存字符串“banana”,
     *  第三个SDS保存字符串“cherry”

## SDS的定义 ##

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

![在这里插入图片描述][2020041200075488.png]

*  free属性的值为0，表示这个SDS没有分配任何未使用空间。
 *  len属性的值为5，表示这个SDS保存了一个5字节长度的字符串。
 *  buf属性是一个char类型的数组，数组的前五个字节分别保存了‘R’、‘e’、‘d’、‘i’、‘s’五个字符。
 *  最后一个字节则保存了空字符串’\\0’（这是遵循C字符串以空字符结尾的惯例，这个空字符不计算在SDS的len属性中。）。

## SDS的优势 ##

### 常数复杂度获取字符串长度 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMyMzY2MzI5_size_16_color_FFFFFF_t_70 2]

C字符串本身不记录字符串长度，每次获取字符串长度需要遍历一次数组。这个操作的复杂度为O(N)。

![在这里插入图片描述][20200412000827463.png]  
SDS的len属性记录了本身的长度，所以获取一个SDS长度的复杂度为O(1)。

### 杜绝缓冲区溢出 ###

C字符串本身不记录字符串长度，导致的另外一个问题是容易造成缓冲区溢出。

![在这里插入图片描述][20200412000840907.png]  
假设程序里有2个内存中紧邻的C字符串s1和s2，其中s1保存了字符串“Redis”，而s2则保存了字符串“MongoDB”。

如果有人直接执行：strcat(s1, “ Cluster”);将s1的内容修改为“Redis Cluster”。由于没有提前给s1分配足够的空间，那么在strcat函数执行后，s1数据将溢出到s2所在的空间，导致s2保存的内容被意外修改。

![在这里插入图片描述][20200412000856573.png]

与C字符串不同，SDS空间分配策略完全可以杜绝缓冲区溢出的问题：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需要的要求，如果不满足的话，API会自动将SDS空间扩展至执行修改所需要的大小，然后才执行实际的修改操作，所以使用SDS即不需要手动修改SDS空间大小，有不会前面所说的缓冲区溢出问题。

![在这里插入图片描述][20200412000908966.png]

如上图执行strcat(s1, “ Cluster”)操作，那么空间不够拼接，会先扩展空间然后执行拼接“ Cluster”操作，拼接的结果如下图所示。

![在这里插入图片描述][20200412000922908.png]

### 减少修改字符串时的内存分配次数 ###

正如前面所说，由于C字符串并不记录自身的长度，所以对于一个包含了N个字符的C字符串来说，底层实现总数一个N+1个字符长度的数组。所以每次增长或者缩短一个C字符串，程序总要保存这个C字符串的数组进行一次内存重新分配操作：

*  如果程序执行的是增长字符串操作，比如拼接操作（append）那么在执行这个操作之前，程序需要先通过内存重新分配来扩展底层数组的空间大小，如果忘记了就会导致缓冲区溢出。
 *  如果程序执行的是缩短字符串操作，比如截断操作（trim）那么在执行这个操作之后，程序需要通过内存重分配来释放不再使用的那部分空间，如果忘记了就会导致内存泄露。

为了避免C字符串的频繁分配内存的缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度的关联：在SDS中，buf数组的长度不一定就是数量+1（如下图），数组里面可以包含未使用字节，而这些字节的数量由SDS的free属性记录。

![在这里插入图片描述][20200412000939414.png]

通过未使用空间，SDS实现了**空间预分配**和**惰性空间**释放两种优化策略。

#### 空间预分配 ####

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

*  如果对SDS进行修改之后，SDS的长度（也就是len属性的值）将小于1MB，那么程序分配的len属性同样大小的未使用空间，这时SDS的len属性和free属性的值相同。

例子：如果修改后SDS的len将变成13字节，那么程序会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1（保存空字符）=27字节。

![在这里插入图片描述][2020041200100184.png]  
![在这里插入图片描述][20200412001012430.png]

*  如果对SDS进行修改后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。

例子：如果字符串修改后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度为30MB+1MB+1byte

在扩展SDS空间之前，SDS API会先检查未使用空间是否足够，如果足够的话，API就会使用未使用空间，而无须执行内存重分配。

*  优点：通过这种预分配策略，SDS将连续增长N次字符串所需要的内存重新分配次数从必定需要N次降低为最多N次。

#### 惰性空间释放 ####

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

![在这里插入图片描述][20200412001027621.png]

例子：如果左图的SDS字符串s执行了sdstrim(s, “XY”);移除SDS中所有的X和Y。函数执行后，并没有释放多出来的8个字节空间，而是将这8个字节空间作为未使用空间保留在SDS里面，使用free属性记录。如果有增长操作可以直接使用，而不用重新分配内存空间。

![在这里插入图片描述][20200412001040924.png]

## 字符串对象编码 ##

字符串对象编码可以是int、raw或者embstr。

![在这里插入图片描述][20200412001053826.png]

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示。那么这个字符串对象的编码设置为int。

![在这里插入图片描述][20200412001116730.png]

如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于32字节，那么字符串对象使用一个简单动态字符串（SDS）来保存这个值，并且将对象的编码设置为raw。

![在这里插入图片描述][20200412001132285.png]

如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于32字节，那么字符串对象使用一个简单动态字符串（SDS）来保存这个值，并且将对象的编码设置为embstr。

embstr编码是专门用于保存短字符串的一种编码优化方式。

### embstr和raw的区别 ###

raw编码会调用两次内存分配函数分别创建redisObject结构和sdshdr结构，而embstr编码则通过调用一次内存分配函数来创建一块连续的内存空间，空间中依次包含了redisObject和sdshdr两个结构。

## 扩展 ##

<table> 
 <thead> 
  <tr> 
   <th>对象</th> 
   <th>编码（数据结构）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>列表对象</td> 
   <td>ziplist（压缩列表）</td> 
  </tr> 
  <tr> 
   <td>linkedlist（双端列表）</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>哈希对象</td> 
   <td>ziplist（压缩列表）</td> 
  </tr> 
  <tr> 
   <td>hashtable</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>集合对象</td> 
   <td>intset（整数集合）</td> 
  </tr> 
  <tr> 
   <td>hashtable</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>有序集合对象</td> 
   <td>ziplist（压缩列表）</td> 
  </tr> 
  <tr> 
   <td>skiplist（跳跃表）</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMyMzY2MzI5_size_16_color_FFFFFF_t_70]: /images/20230528/dbd093f6ec7543a7bf291f3615f4807b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMyMzY2MzI5_size_16_color_FFFFFF_t_70 1]: /images/20230528/0c2afe5b7a604723aa675e3331b87c3b.png
[2020041200064335.png]: /images/20230528/522f5410f7ad48488875136ae04b5dc7.png
[2020041200075488.png]: /images/20230528/49d2c5020aa14bf0b232125f79c629ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMyMzY2MzI5_size_16_color_FFFFFF_t_70 2]: /images/20230528/0d4c61c99fda43b3b82c2956f14100aa.png
[20200412000827463.png]: /images/20230528/91b1639b671643d786151b882ce61940.png
[20200412000840907.png]: /images/20230528/057c7f57ca94424fa2e33e2d21649bac.png
[20200412000856573.png]: /images/20230528/c1fb75464b2f4b17b60fc8b44faec79e.png
[20200412000908966.png]: /images/20230528/7bc28951c8be4286a2352a780dbb8de2.png
[20200412000922908.png]: /images/20230528/626b1440667240538fb31f72aef3b68c.png
[20200412000939414.png]: /images/20230528/b9c3e9a89e9844bab8997d7b19262878.png
[2020041200100184.png]: /images/20230528/8ee2b55adcc14577ac671ab50c0353b0.png
[20200412001012430.png]: /images/20230528/e5590a9b1e2545f0a23c6cfbec807a78.png
[20200412001027621.png]: /images/20230528/9e299ef2be1e4bfc90fe60934d13d1f0.png
[20200412001040924.png]: /images/20230528/bdca37f26d98436c8dbdc63a79e7c570.png
[20200412001053826.png]: /images/20230528/cafe8ac546c3414b9bc779352b01a5c6.png
[20200412001116730.png]: /images/20230528/5505307474824d3e8e1cd8cf94d30280.png
[20200412001132285.png]: /images/20230528/97c41198e4724fadbcf137f5de385b43.png