- 浏览: 131656 次
文章分类
最新评论
Redis 虽说由 C 语言实现,但用户直接操作的字符串绝大多数情况下均非 C 语言中以空字符结尾的字符串,而是一种封装了 C 字符串的称作简单动态字符串(simple dynamic string, SDS)的抽象结构,并将其作为 Redis 的默认字符串表示。
SDS 结构的定义如下:
之所以采用 SDS 结构而非直接使用 C 风格字符串,主要是为了满足 Redis 对字符串在安全性、效率以及功能方面的要求。这主要表现在以下几方面。
1、获取字符串长度的复杂度
因为访问 C 字符串的长度则需要 O(N)(N 为字符串的长度),而根据 SDS 结构的定义可知,要获取其保存的字符串的长度,只需访问 len 属性即可,时间复杂度为 O(1),这避免了在 Redis 中反复执行 STRLEN 命令对系统性能造成的影响。
2、杜绝缓冲区溢出
SDS 的内存分配策略能保证在每次修改 SDS 底层存储的字符串时,buf 数组有足够的空间容纳新的字符串,从而避免了缓冲区溢出的可能。
3、使用了空间预分配和惰性空间释放来优化内存分配
当剩余的未使用空间 free 不能容纳修改后增长的字节长度时,使用空间预分配能减少连续执行字符串增长操作所需的内存重分配次数。具体的预分配策略算法如下:
a)若修改后 SDS 的字符串长度 len 小于 1MB,则分配和 len 同样大小的未使用空间 free,此时 SDS 的属性 len 和 free 的值相同。
b)若修改后 SDS 的字符串长度 len 不小于 1MB,则额外分配 free 为 1MB 的未使用空间。
而使用惰性空间释放则是指:在需要缩短 SDS 保存的字符串时,程序并不立即释放缩短后多出来的空间,而是追加到 free 属性中,以备将来使用。
4、二进制安全
由于 C 字符串是以空字符来区分字符串是否结束,所以这使得其只能保存文本数据,而不能保存数据中可能含有空字符的二进制数据(如图片、音频、视频和压缩文件等)。为了确保 Redis 可以适用于多种场景,SDS 的 API 都是二进制安全的(binary-safe)。这也是将 buf 称为字节数组的原因,因为 Redis 不是用它来保存字符,而是用来保存一系列二进制数据。因此 SDS 是使用 len 属性而非空字符来判断字符串是否结束。
5、兼容部分 C 字符串函数
尽管 SDS 的 API 都是二进制安全的,但它们依然遵循 C 字符串以空字符串结尾的惯例,这主要是为了让那些保存文本数据的 SDS 可以重用一部分 C 中的字符串函数。
Redis 中的列表结构是基于双端链表的,因此它既支持栈操作,也支持队列操作。除列表键值外,Redis 中的发布与订阅、慢查询、监视器等功能也都用到了链表结构。每个链表节点都使用一个 listNode 结构来表示,此外,为了方便操作,Redis 用了一个 list 结构来封装了 listNode 结构组成的链表。这两种结构的定义如下:
为实现多态,以便链表可以用于保存各种不同类型的值,listNode 结构中使用了“void *”空指针来保存节点值,并通过 list 结构中的 dup、free 和 match 三个属性来为节点值设置类型特定函数。
参考:
1、《Redis 设计与实现》第二章——简单动态字符串。
2、《Redis 设计与实现》第三章——链表。
SDS 结构的定义如下:
struct sdshdr{ int len; // 记录 buf 数组中已使用的字节数,等于 SDS 所保存的字符串的长度 int free; // 记录 buf 数组中未使用的字节数 char buf[]; // 保存真正的字节数据,长度为:len + free + 1(额外的一字节用于保存末尾的空字符) };
之所以采用 SDS 结构而非直接使用 C 风格字符串,主要是为了满足 Redis 对字符串在安全性、效率以及功能方面的要求。这主要表现在以下几方面。
1、获取字符串长度的复杂度
因为访问 C 字符串的长度则需要 O(N)(N 为字符串的长度),而根据 SDS 结构的定义可知,要获取其保存的字符串的长度,只需访问 len 属性即可,时间复杂度为 O(1),这避免了在 Redis 中反复执行 STRLEN 命令对系统性能造成的影响。
2、杜绝缓冲区溢出
SDS 的内存分配策略能保证在每次修改 SDS 底层存储的字符串时,buf 数组有足够的空间容纳新的字符串,从而避免了缓冲区溢出的可能。
3、使用了空间预分配和惰性空间释放来优化内存分配
当剩余的未使用空间 free 不能容纳修改后增长的字节长度时,使用空间预分配能减少连续执行字符串增长操作所需的内存重分配次数。具体的预分配策略算法如下:
a)若修改后 SDS 的字符串长度 len 小于 1MB,则分配和 len 同样大小的未使用空间 free,此时 SDS 的属性 len 和 free 的值相同。
b)若修改后 SDS 的字符串长度 len 不小于 1MB,则额外分配 free 为 1MB 的未使用空间。
而使用惰性空间释放则是指:在需要缩短 SDS 保存的字符串时,程序并不立即释放缩短后多出来的空间,而是追加到 free 属性中,以备将来使用。
4、二进制安全
由于 C 字符串是以空字符来区分字符串是否结束,所以这使得其只能保存文本数据,而不能保存数据中可能含有空字符的二进制数据(如图片、音频、视频和压缩文件等)。为了确保 Redis 可以适用于多种场景,SDS 的 API 都是二进制安全的(binary-safe)。这也是将 buf 称为字节数组的原因,因为 Redis 不是用它来保存字符,而是用来保存一系列二进制数据。因此 SDS 是使用 len 属性而非空字符来判断字符串是否结束。
5、兼容部分 C 字符串函数
尽管 SDS 的 API 都是二进制安全的,但它们依然遵循 C 字符串以空字符串结尾的惯例,这主要是为了让那些保存文本数据的 SDS 可以重用一部分 C 中的字符串函数。
Redis 中的列表结构是基于双端链表的,因此它既支持栈操作,也支持队列操作。除列表键值外,Redis 中的发布与订阅、慢查询、监视器等功能也都用到了链表结构。每个链表节点都使用一个 listNode 结构来表示,此外,为了方便操作,Redis 用了一个 list 结构来封装了 listNode 结构组成的链表。这两种结构的定义如下:
typedef struct listNode{ struct listNode *prev; // 前置节点 struct listNode *next; // 后置节点 void *value; // 节点值 }listNode; typedef struct list{ listNode *head; // 表头节点 listNode *tail; // 表尾节点 unsigned long len; // 列表所包含的节点数量 void *(*dup)(void *ptr); // 节点值复制函数 void (*free)(void *ptr); // 节点值释放函数 int (*match)(void *ptr, void *key); // 节点值对比函数 }list;
为实现多态,以便链表可以用于保存各种不同类型的值,listNode 结构中使用了“void *”空指针来保存节点值,并通过 list 结构中的 dup、free 和 match 三个属性来为节点值设置类型特定函数。
参考:
1、《Redis 设计与实现》第二章——简单动态字符串。
2、《Redis 设计与实现》第三章——链表。
发表评论
-
Lua 脚本
2019-10-07 19:49 586Redis 2.6 版本开始引入对 Lua 脚 ... -
Redis事务的实现
2019-09-22 18:56 420Redis 事务是 ... -
Redis集群之复制、故障转移及消息实现
2019-09-14 21:04 451在Redis集群 ... -
Redis集群实现原理
2019-09-14 12:19 590Redis 集群是 Redis 提供的分布式数 ... -
sentinel 系统介绍
2019-08-04 18:35 451Sentinel(哨兵)是 Redis 的高可 ... -
数据库复制
2019-07-13 22:02 336在连接到一 ... -
redis 客户端实现
2019-06-02 15:06 331Redis 服务器是典型的一对多服务器程序,通 ... -
AOF 持久化
2019-05-12 13:36 370除了前面提到的 RDB 持久化功能外,Redi ... -
RDB 文件结构
2019-04-27 12:10 534在RDB 持久化一节中,我们对 RDB 持久化 ... -
RDB 持久化
2019-04-14 17:20 373RDB 持久化功能可以将 Redis 在某个时 ... -
Redis 数据库通知功能的实现
2019-04-07 11:56 1242Reids 数据库通知功能可以让客户端通过订阅 ... -
数据库实现
2019-03-24 13:58 398Redis 服务器将其所有的数据库都保存在 r ... -
Redis 五种对象
2019-01-20 11:13 333阅读本节前需要阅读 Redis 对象系统概览一 ... -
Redis 对象系统概览
2019-01-06 13:10 740前面介绍了 Redis 中用到的所有主要数据结 ... -
整数集合与压缩列表
2018-12-09 21:19 550在 Redis 中,当一 ... -
跳跃表在 Redis 中的应用
2018-08-23 16:30 1992前提申明,因篇幅 ... -
字典实现
2018-08-20 15:49 520字典在 Redis 中的应用相当广泛,如 Redis ...
相关推荐
Redis字符串的实现 Redis字符串的性能优势 Redis字符串的实现 Redis虽然是用C语言写的,但却没有直接用C语言的字符串,而是自己实现了一套字符串。目的就是为了提升速度,提升性能,可以看出Redis为了高性能也是...
简单来说就是用java实现远程操作redis,ip地址要找到自己linux上连网后的ip地址,在每个case文件中修改后就可以实现了,对应的test文件是实现操作文件,你可以自己写一个主程序把他们包括起来。哦,对了这里面包括了...
SpringBoot中利用Redis实现消息队列,代码亲测可用, 可以传输字符串,或java对象都可以
Redis 提供数据结构,例如字符串、散列、列表、集合、带有范围查询的排序集、位图、超日志、地理空间索引和流。Redis 具有内置复制、 Lua 脚本编写、 LRU 垃圾清理、事务处理和不同级别的磁盘持久性,并通过 Redis ...
SDS(Simple Dynamic Strings, 简单动态字符串)是 Redis 的一种基本数据结构,主要是用于存储字符串和整数。 这篇文章里,我们就来探讨一下 Redis SDS 这种数据结构的底层实现原理。 学习之前,首先我们要明确,...
Redis是Remote Dictionary Server的缩写,它使用字典结构存储数据,并允许其他应用通过TCP协议读写字典中的内容。同大多数脚本语言中的字典一样,Redis...Redis 支持的数据类型有字符串、散列、列表、集合、有序集合。
和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)和zset(有序集合)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作,而且这些操作都是原子...
Redis 和其他很多 key-value 数据库的不同之处在于,Redis 不仅支持简单的字符串键值对,它 还提供了一系列数据结构类型值,比如列表、哈希、集合和有序集,并在这些数据结构类型上 定义了一套强大的 API 。 通过...
Redis 是一个键值对数据库(key-value DB), 数据库的值可以是字符串、集合、列表等多种类型的对象, 而数据库的键则总是字符串对象。 对于那些包含字符串值的字符串对象来说, 每个字符串对象都包含一个 sds 值。 ...
Redis 中,键的数据类型是字符串,值的数据类型有很多,常⽤的数据类型有字符串、列表、字典、集合、有序集合。 1. 字符串( 字符串(string) ) "字符串(string)"这种数据类型⾮常简单,对应到数据结构⾥,就是...
Redis 安装1、Redis的数据类型: 字符串、列表(lists)、集合(sets)、有序集合(sorts sets)、哈希表(hashs)2、Redis和memcache相比的独特之处: (1)redis可以用来做存储(storge)、而memcache是来做缓存...
和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更...
Redis是一个快速、开源、高性能的内存键值数据库,它支持多种不同类型的数据结构,如字符串、列表、散列、集合和有序集合,应用于缓存、队列、发布/订阅等多种场景下。 以下是Redis的一些特点: 1. 内存存储 ...
和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更...
8、一个字符串类型的值能存储最大容量是多少? 9、为什么 Redis 需要把所有数据放到内存中? 10、Redis 集群方案应该怎么做?都有哪些方案? 11、Redis 集群方案什么情况下会导致整个集群不可用? 12、MySQL 里有 ...
新的“嵌套字符串”对象编码减少缓存遗漏,大幅提高某些工作负荷的速度;等等。开发者Salvatore Sanfilippo表示,Redis 3.0.0是第一个原生支持集群的稳定版本,可能需要1到2年才能成熟,它对Redis生态系统具有重要...
新增加的Stream(流)数据类型,这样redis就有了6大数据类型,另外五种是String(字符串),Hash(哈希),List(列表),Set(集合)及Zset(sorted set有序集合)。它弥补了其它5种数据类型不能实现的功能,比如List...
和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)和zset(有序集合)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作,而且这些操作都是原子...
和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更...
和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(集合)、zset(sorted set --有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更...