公司网站开发文档,外包公司好不好,一件代发货源网1688,网站分为目录 一、内部数据结构
二、简单动态字符串
1、sds的用途
实现字符串对象
将sds代替C默认的char*类型
2、Redis中的字符串
sds的实现
3、优化追加操作
4、sds 模块的 API
三、Redis动态字符串的内存分配和释放是如何进行的#xff1f;
四、Redis动态字符串的扩容策略…目录 一、内部数据结构
二、简单动态字符串
1、sds的用途
实现字符串对象
将sds代替C默认的char*类型
2、Redis中的字符串
sds的实现
3、优化追加操作
4、sds 模块的 API
三、Redis动态字符串的内存分配和释放是如何进行的
四、Redis动态字符串的扩容策略是什么
五、Redis动态字符串在存储数据时有什么注意事项
六、Redis动态字符串与常规字符串的区别是什么
七、小结 一、内部数据结构
Redis和其他很多 key-value 数据库的不同之处在于 Redis不仅支持简单的字符串键值对它还提供了一系列数据结构类型值比如列表、哈希、集合和有序集并在这些数据结构类型上定义了一套强大的 API。
通过对不同类型的值进行操作 Redis可以很轻易地完成其他只支持字符串键值对的 key-value数据库很难或者无法完成的任务。
在 Redis的内部数据结构类型值由高效的数据结构和算法进行支持并且在 Redis自身的构建当中也大量用到了这些数据结构。
这一部分将对 Redis内存所使用的数据结构和算法进行介绍。
二、简单动态字符串
SdsSimple Dynamic String 简单动态字符串是 Redis底层所使用的字符串表示它被用在几乎所有的 Redis模块中。
本章将对 sds的实现、性能和功能等方面进行介绍并说明 Redis使用 sds而不是传统 C字符串的原因。
1、sds的用途
Sds在 Redis中的主要作用有以下两个
1.实现字符串对象 StringObject
2.在 Redis程序内部用作 char*类型的替代品
以下两个小节分别对这两种用途进行介绍。
实现字符串对象
Redis是一个键值对数据库 key-value DB 数据库的值可以是字符串、集合、列表等多种类型的对象而数据库的键则总是字符串对象。
对于那些包含字符串值的字符串对象来说每个字符串对象都包含一个 sds值。
Note:“包含字符串值的字符串对象”这种说法初听上去可能会有点奇怪但是在 Redis中一个字符串对象除了可以保存字符串值之外还可以保存 long类型的值所以为了严谨起见这里需要强调一下当字符串对象保存的是字符串时它包含的才是 sds值否则的话它就是一个long类型的值。
举个例子以下命令创建了一个新的数据库键值对这个键值对的键和值都是字符串对象它们都包含一个 sds值
redisSET book Mastering C in 21 days OKredisGET bookMastering C in 21 days
以下命令创建了另一个键值对它的键是字符串对象而值则是一个集合对象
redisSADD nosql RedisMongoDBNeo4j(integer) 3redisSMEMBERS nosql1)Neo4j2)Redis3)MongoDB
将sds代替C默认的char*类型
因为char*类型的功能单一抽象层次低并且不能高效地支持一些 Redis常用的操作比如追加操作和长度计算操作 所以在 Redis程序内部绝大部分情况下都会使用 sds而不是char*来表示字符串。
性能问题在稍后介绍 sds定义的时候就会说到因为我们还没有了解过 Redis的其他功能模块所以也没办法详细地举例说那里用到了 sds不过在后面的章节中我们会经常看到其他模块几乎每一个都用到了 sds类型值。
目前来说只要记住这样一个事实即可在 Redis中客户端传入服务器的协议内容、 aof缓存、返回给客户端的回复等等这些重要的内容都是由都是由 sds类型来保存的。
2、Redis中的字符串
在 C语言中字符串可以用一个 \0结尾的char数组来表示。
比如说 hello world 在 C语言中就可以表示为 hello world\0 。这种简单的字符串表示在大多数情况下都能满足要求但是它并不能高效地支持长度计算和追加 append这两种操作
•每次计算字符串长度 strlen(s) 的复杂度为 (N)。
•对字符串进行 N次追加必定需要对字符串进行 N次内存重分配 realloc 。
在 Redis内部字符串的追加和长度计算并不少见而 APPEND 和 STRLEN 更是这两种操作在 Redis命令中的直接映射这两个简单的操作不应该成为性能的瓶颈。
另外 Redis除了处理 C字符串之外还需要处理单纯的字节数组以及服务器协议等内容所以为了方便起见 Redis的字符串表示还应该是 二进制安全的 程序不应对字符串里面保存的数据做任何假设数据可以是以 \0结尾的 C字符串也可以是单纯的字节数组或者其他格式的数据。
考虑到这两个原因 Redis使用 sds类型替换了 C语言的默认字符串表示 sds既可以高效地实现追加和长度计算并且它还是二进制安全的。
sds的实现
在前面的内容中我们一直将 sds作为一种抽象数据结构来说明实际上它的实现由以下两部分组成
typedef char*sds;structsdshdr {// buf已占用长度intlen;// buf剩余可用长度intfree;//实际保存字符串数据的地方charbuf[];};
其中类型 sds是char *的别名 (alias)而结构 sdshdr则保存了 len、free和buf三个属性。
作为例子以下是新创建的同样保存 hello world 字符串的 sdshdr结构
structsdshdr {len11;free0;bufhello world \0;// buf的实际长度为 len 1};
通过len属性sdshdr可以实现复杂度为 (1)的长度计算操作。
另一方面通过对 buf分配一些额外的空间并使用 free记录未使用空间的大小 sdshdr可以让执行追加操作所需的内存重分配次数大大减少下一节我们就会来详细讨论这一点。
当然 sds也对操作的正确实现提出了要求——所有处理 sdshdr的函数都必须正确地更新len和free属性否则就会造成 bug。
3、优化追加操作
在前面说到过利用 sdshdr结构除了可以用 (1)复杂度获取字符串的长度之外还可以减少追加 (append) 操作所需的内存重分配次数以下就来详细解释这个优化的原理。
为了易于理解我们用一个 Redis执行实例作为例子解释一下当执行以下代码时 Redis内部发生了什么
redisSET msg hello world OKredisAPPEND msg again!(integer) 18redisGET msghello world again!
首先SET命令创建并保存 hello world 到一个sdshdr中这个 sdshdr的值如下
structsdshdr {len11;free0;}
当执行 APPEND 命令时相应的 sdshdr被更新字符串 again! 会被追加到原来的hello world 之后:
struct sdshdr { len 18;free 18;// 空白的地方为预分配空间共 18 18 1 个字节 buf hello world again!\0 ;
} 注意当调用 SET 命令创建 sdshdr 时sdshdr 的 free 属性为 0 Redis 也没有为 buf 创建 额外的空间——而在执行 APPEND 之后Redis 为 buf 创建了多于所需空间一倍的大小。
在这个例子中保存 hello world again! 共需要 18 1 个字节但程序却为我们分配了 18 18 1 37 个字节——这样一来如果将来再次对同一个 sdshdr 进行追加操作只要 追加内容的长度不超过 free 属性的值那么就不需要对 buf 进行内存重分配。
比如说执行以下命令并不会引起 buf 的内存重分配因为新追加的字符串长度小于 18 :
redis APPEND msg again!
(integer) 25 再次执行 APPEND 命令之后msg 的值所对应的 sdshdr 结构可以表示如下:
struct sdshdr { len 25;free 11;// 空白的地方为预分配空间共 18 18 1 个字节buf hello world again! again!\0 ;
}
sds.c/sdsMakeRoomFor 函数描述了 sdshdr 的这种内存预分配优化策略以下是这个函数的 伪代码版本:
def sdsMakeRoomFor(sdshdr, required_len):# 预分配空间足够无须再进行空间分配 if (sdshdr.free required_len):return sdshdr
# 计算新字符串的总长度
newlen sdshdr.len required_len
# 如果新字符串的总长度小于 SDS_MAX_PREALLOC
# 那么为字符串分配 2 倍于所需长度的空间
# 否则就分配所需长度加上 SDS_MAX_PREALLOC 数量的空间
if newlen SDS_MAX_PREALLOC:newlen * 2
else:newlen SDS_MAX_PREALLOC
# 分配内存
newsh zrelloc(sdshdr, sizeof(struct sdshdr)newlen1)
# 更新 free 属性
newsh.free newlen - sdshdr.len
# 返回
return newsh
在目前版本的 Redis 中SDS_MAX_PREALLOC 的值为 1024 * 1024 也就是说当大小小于 1MB 的字符串执行追加操作时sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间;当 字符串的大小大于 1MB 那么 sdsMakeRoomFor 就为它们额外多分配 1MB 的空间。
Note: 这种分配策略会浪费内存吗?
执行过 APPEND 命令的字符串会带有额外的预分配空间这些预分配空间不会被释放除非 该字符串所对应的键被删除或者等到关闭 Redis 之后再次启动时重新载入的字符串对象将 不会有预分配空间。
因为执行 APPEND 命令的字符串键数量通常并不多占用内存的体积通常也不大所以这一 般并不算什么问题。
另一方面如果执行 APPEND 操作的键很多而字符串的体积又很大的话那可能就需要修 改 Redis 服务器让它定时释放一些字符串键的预分配空间从而更有效地使用内存。
4、sds 模块的 API
sds 模块基于 sds 类型和 sdshdr 结构提供了以下 API : 三、Redis动态字符串的内存分配和释放是如何进行的
Redis中的动态字符串类型redisObject内部实现了引用计数和惰性释放机制来管理内存分配和释放。 内存分配Redis使用malloc函数分配内存块来存储动态字符串。动态字符串结构体包含了当前字符串长度、可用空间大小和字符数组其中字符数组的长度至少是当前字符串长度加一。 引用计数每个redisObject对象都包含一个refcount字段记录了指向该对象的指针数量。当其他对象引用一个动态字符串时它们会增加该动态字符串的引用计数。 惰性释放当一个动态字符串不再被引用时其引用计数会减少。如果引用计数变为0Redis会将其标记为可释放状态并不立即释放其内存。而是在合适的时机例如内存紧张或者执行一次RDB或AOF持久化操作时Redis会对所有可释放的动态字符串进行释放。
通过引用计数和惰性释放的组合Redis可以减少内存分配和释放的次数提高性能。同时惰性释放机制也能够在需要释放内存时一次性释放多个动态字符串减少系统调用的开销。
四、Redis动态字符串的扩容策略是什么
Redis动态字符串的扩容策略是通过预分配的方式来保证字符串的扩容操作效率。具体策略如下 增长策略当字符串长度增长时Redis会根据当前字符串长度选择适当的增长策略。 如果当前字符串长度小于1MB每次增长会以当前长度的2倍来进行。如果当前字符串长度大于等于1MB每次增长会增加1MB的长度。 预分配策略Redis会预分配更大的空间在每次扩容时会为字符串分配比当前长度更大的空间。这样可以减少频繁地进行内存重新分配的次数提高性能。 惰性空间释放策略当字符串长度缩小时Redis并不会立即释放多余的空间而是将其保留起来。这样可以避免频繁地进行内存分配和释放操作提高性能。
需要注意的是Redis动态字符串是通过结构体sdsSimple Dynamic Strings来实现的结构体中记录了字符串的长度和剩余空间等信息。扩容策略可以保证字符串长度的增长和缩小的效率同时避免了频繁进行内存分配和释放的操作。
五、Redis动态字符串在存储数据时有什么注意事项
在存储数据时使用Redis的动态字符串需要注意以下事项 动态字符串可以存储任意的二进制数据但需要注意数据的大小限制。Redis的最大字符串长度是512MB如果要存储较大的数据需要进行分片或者压缩等处理。 动态字符串是可修改的但是在修改字符串时需要注意原来字符串的引用计数。如果有其他地方引用了该字符串修改时需要先拷贝一份副本再进行修改。 当动态字符串的长度超过预分配的空间时需要进行重新分配和拷贝。这个过程可能会引发内存分配和拷贝的开销因此在使用动态字符串时需要合理预估字符串的最大长度。 如果需要频繁地对字符串进行拼接、截取等操作使用动态字符串性能更高。因为动态字符串的底层实现是一个char数组可以直接通过索引访问和修改。
总而言之使用动态字符串在存储数据时需要注意数据大小限制、引用计数、内存分配等问题以及合理预估字符串的最大长度。
六、Redis动态字符串与常规字符串的区别是什么
Redis的动态字符串与常规字符串有以下区别 内存预分配Redis的动态字符串会根据字符串的长度进行内存预分配以减少字符串长度改变时的内存重新分配的次数。而常规字符串则需要每次长度改变都进行内存重新分配。 缓冲区溢出Redis的动态字符串会维护一个字节缓冲区用于保存字符串的内容。当字符串的长度超过缓冲区的大小时会自动扩展缓冲区的大小避免缓冲区溢出。而常规字符串没有这样的缓冲区当字符串的长度超过字符串本身分配的空间时会导致缓冲区溢出。 修改操作效率Redis的动态字符串通过修改字符串结构体的方式进行字符串操作可以在O(1)的时间内进行字符串长度的修改并且不需要进行内存拷贝。而常规字符串需要在O(N)的时间内进行字符串长度的修改并且需要进行内存拷贝。 字符串共享Redis的动态字符串支持字符串共享即多个键值对可以共享相同的字符串内容节约内存。而常规字符串不支持字符串共享每个字符串在内存中都有一份独立的拷贝。
总的来说Redis的动态字符串相比常规字符串在内存管理、性能和内存占用等方面有一定的优势。
七、小结
• Redis 的字符串表示为 sds 而不是 C 字符串(以 \0 结尾的 char*)。
• 对比 C 字符串sds 有以下特性: – 可以高效地执行长度计算(strlen); – 可以高效地执行追加操作(append); – 二进制安全;
• sds 会为追加操作进行优化:加快追加操作的速度并降低内存分配的次数代价是多占 用了一些内存而且这些内存不会被主动释放。
