服务器之家:专注于服务器技术及软件下载分享
分类导航

Mysql|Sql Server|Oracle|Redis|MongoDB|PostgreSQL|Sqlite|DB2|mariadb|Access|数据库技术|

服务器之家 - 数据库 - Redis - Redis中的动态字符串学习教程

Redis中的动态字符串学习教程

2019-10-26 19:57zinss26914 Redis

这篇文章主要介绍了Redis中的动态字符串学习教程,以sds模块的使用为主进行讲解,需要的朋友可以参考下

sds 的用途
Sds 在 Redis 中的主要作用有以下两个:

实现字符串对象(StringObject);
在 Redis 程序内部用作 char* 类型的替代品;
以下两个小节分别对这两种用途进行介绍。

实现字符串对象

Redis 是一个键值对数据库(key-value DB), 数据库的值可以是字符串、集合、列表等多种类型的对象, 而数据库的键则总是字符串对象。

对于那些包含字符串值的字符串对象来说, 每个字符串对象都包含一个 sds 值。

“包含字符串值的字符串对象”,这种说法初听上去可能会有点奇怪, 但是在 Redis 中, 一个字符串对象除了可以保存字符串值之外, 还可以保存 long 类型的值, 所以为了严谨起见, 这里需要强调一下: 当字符串对象保存的是字符串时, 它包含的才是 sds 值, 否则的话, 它就是一个 long 类型的值。
举个例子, 以下命令创建了一个新的数据库键值对, 这个键值对的键和值都是字符串对象, 它们都包含一个 sds 值:

?
1
2
3
4
5
redis> SET book "Mastering C++ in 21 days"
OK
 
redis> GET book
"Mastering C++ in 21 days"

以下命令创建了另一个键值对, 它的键是字符串对象, 而值则是一个集合对象:

?
1
2
3
4
5
6
7
redis> SADD nosql "Redis" "MongoDB" "Neo4j"
(integer) 3
 
redis> SMEMBERS nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"

用 sds 取代 C 默认的 char* 类型

因为 char* 类型的功能单一, 抽象层次低, 并且不能高效地支持一些 Redis 常用的操作(比如追加操作和长度计算操作), 所以在 Redis 程序内部, 绝大部分情况下都会使用 sds 而不是 char* 来表示字符串。

性能问题在稍后介绍 sds 定义的时候就会说到, 因为我们还没有了解过 Redis 的其他功能模块, 所以也没办法详细地举例说那里用到了 sds , 不过在后面的章节中, 我们会经常看到其他模块(几乎每一个)都用到了 sds 类型值。

目前来说, 只要记住这个事实即可: 在 Redis 中, 客户端传入服务器的协议内容、 aof 缓存、 返回给客户端的回复, 等等, 这些重要的内容都是由 sds 类型来保存的。

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 作为一种抽象数据结构来说明, 实际上, 它的实现由以下两部分组成:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef char *sds;
 
 
struct sdshdr {
 
  // buf 已占用长度
  int len;
 
  // buf 剩余可用长度
  int free;
 
  // 实际保存字符串数据的地方
  char buf[];
};

其中,类型 sds 是 char * 的别名(alias),而结构 sdshdr 则保存了 len 、 free 和 buf 三个属性。

作为例子,以下是新创建的,同样保存 hello world 字符串的 sdshdr 结构:

?
1
2
3
4
5
struct sdshdr {
  len = 11;
  free = 0;
  buf = "hello world\0"; // buf 的实际长度为 len + 1
};

通过 len 属性, sdshdr 可以实现复杂度为 θ(1) 的长度计算操作。

另一方面, 通过对 buf 分配一些额外的空间, 并使用 free 记录未使用空间的大小, sdshdr 可以让执行追加操作所需的内存重分配次数大大减少, 下一节我们就会来详细讨论这一点。

当然, sds 也对操作的正确实现提出了要求 —— 所有处理 sdshdr 的函数,都必须正确地更新 len 和 free 属性,否则就会造成 bug 。

数据类型定义
与sds实现有关的数据类型有两个,一个是 sds:

?
1
2
// 字符串类型的别名
typedef char *sds;


另一个是 sdshdr:

?
1
2
3
4
5
6
7
8
9
// 持有sds的结构
struct sdshdr {
  // buf中已经被使用的字符串空间数量
  int len;
  // buf中预留字符串的空间数量
  int free;
  // 实际存储字符串的地方
  char buf[];
};


其中,sds只是字符串数组类型char*的别名,而sdshdr用于持有和保存sds的信息

比如,sdshdr.len可以用于在O(1)的复杂度下获取sdshdr.buf中存储的字符串的实际长度,而sdshdr.free则用于保存sdshdr.buf中还有多少预留空间

(这里sdshdr应该是sds handler的缩写)

将sdshdr用作sds
sds模块对sdshdr结构使用了一点小技巧:通过指针运算,它使得sdshdr结构可以像sds类型一样被传值和处理,并在需要的时候恢复成sdshdr类型

通过下面的函数定义来理解这个技巧

sdsnewlen 函数返回一个新的sds值,实际上,它创建的却是一个sdshdr结构:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
sds sdsnewlen(const void *init, size_t initlen)
{
  struct sdshdr *sh;
 
  if (init) {
    // 创建
    sh = malloc(sizeof(struct sdshdr) + initlen + 1);
  } else {
    // 重分配
    sh = calloc(1, sizeof(struct sdshdr) + initlen + 1);
  }
 
  if (sh == NULL) return NULL;
 
  sh->len = initlen;
  sh->free = 0;  // 刚开始free为0
 
  if (initlen && init) {
    memcpy(sh->buf, init, initlen);
  }
  sh->buf[initlen] = '\0';
 
  // 只返回sh->buf这个字符串部分
  return (char *)sh->buf;
}


通过使用变量持有一个sds的值,在遇到那些只处理sds值本身的函数时,可以直接将sds传给它们。比如说,sdstoupper 函数就是其中的一个例子:

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdslen(const sds s)
{
  // 从sds中计算出相应的sdshdr结构
  struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
 
  return sh->len;
}
 
 
void sdstoupper(sds s)
{
  int len = sdslen(s), j;
 
  for (j = 0; j < len; j ++)
    s[j] = toupper(s[j]);
}


这里有一个技巧,通过指针运算,可以从sds值中计算出相应的sdshdr结构:

sds虽然是指向char *的buf(ps:并且空数组不占用内存空间,数组名即为内存地址),但是分配的时候是分配sizeof(struct sdshdr) + initlen + 1的,通过sds - sizeof(struct sdshdr)可以计算出struct sdshdr的首地址,从而可以得到len和free的信息

Redis中的动态字符串学习教程

sdsavail 函数就是使用这中技巧的一个例子:

 

?
1
2
3
4
5
6
static inline size_t sdsavail(const sds s)
{
  struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
 
  return sh->free;
}


内存分配函数实现
和Reids 的实现决策相关的函数是 sdsMakeRoomFor :

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
sds sdsMakeRoomFor(sds s, size_t addlen)
{
  struct sdshdr *sh, *newsh;
  size_t free = sdsavail(s);
  size_t len, newlen;
 
  // 预留空间可以满足本地拼接 
  if (free >= addlen) return s;
 
  len = sdslen(s);
  sh = (void *)(s - (sizeof(struct sdshdr)));
 
  // 设置新sds的字符串长度
  // 这个长度比完成本次拼接实际所需的长度要大
  // 通过预留空间优化下次拼接操作
  newlen = (len + addlen);
  if (newlen < 1024 * 1024)
    newlen *= 2;
  else
    newlen += 1024;
 
  // 重新分配sdshdr
  newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);
  if (newsh == NULL) return NULL;
 
  newsh->free = newlen - len;
 
  // 只返回字符串部分
  return newsh->buf;
}


这种内存分配策略表明,在对sds 值进行扩展(expand)时,总会预留额外的空间,通过花费更多的内存,减少了对内存进行重分配(reallocate)的次数,并优化下次扩展操作的处理速度

再把redis的如果实现对sds字符串扩展的方法贴一下,很不错的思路:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 按长度len扩展sds,并将t拼接到sds的末尾
 */
sds sdscatlen(sds s, const void *t, size_t len)
{
  struct sdshdr *sh;
 
  size_t curlen = sdslen(s);
 
  // O(N)
  s = sdsMakeRoomFor(s, len);
  if (s == NULL) return NULL;
 
  // 复制
  memcpy(s + curlen, t, len);
 
  // 更新len和free属性
  sh = (void *)(s - (sizeof(struct sdshdr)));
  sh->len = curlen + len;
  sh->free = sh->free - len;
 
  // 终结符
  s[curlen + len] = '\0';
 
  return s;
}
 
/**
 * 将一个char数组拼接到sds 末尾
 */
sds sdscat(sds s, const char *t)
{
  return sdscatlen(s, t, strlen(t));
}

延伸 · 阅读

精彩推荐
  • Redis如何使用Redis锁处理并发问题详解

    如何使用Redis锁处理并发问题详解

    这篇文章主要给大家介绍了关于如何使用Redis锁处理并发问题的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Redis具有一定的参考学习...

    haofly4522019-11-26
  • Redis详解三分钟快速搭建分布式高可用的Redis集群

    详解三分钟快速搭建分布式高可用的Redis集群

    这篇文章主要介绍了详解三分钟快速搭建分布式高可用的Redis集群,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...

    万猫学社4502021-07-25
  • RedisRedis集群的5种使用方式,各自优缺点分析

    Redis集群的5种使用方式,各自优缺点分析

    Redis 多副本,采用主从(replication)部署结构,相较于单副本而言最大的特点就是主从实例间数据实时同步,并且提供数据持久化和备份策略。...

    优知学院4082021-08-10
  • Redis《面试八股文》之 Redis十六卷

    《面试八股文》之 Redis十六卷

    redis 作为我们最常用的内存数据库,很多地方你都能够发现它的身影,比如说登录信息的存储,分布式锁的使用,其经常被我们当做缓存去使用。...

    moon聊技术8182021-07-26
  • RedisRedis Template实现分布式锁的实例代码

    Redis Template实现分布式锁的实例代码

    这篇文章主要介绍了Redis Template实现分布式锁,需要的朋友可以参考下 ...

    晴天小哥哥2592019-11-18
  • Redis关于Redis数据库入门详细介绍

    关于Redis数据库入门详细介绍

    大家好,本篇文章主要讲的是关于Redis数据库入门详细介绍,感兴趣的同学赶快来看一看吧,对你有帮助的话记得收藏一下,方便下次浏览...

    沃尔码6982022-01-24
  • Redisredis缓存存储Session原理机制

    redis缓存存储Session原理机制

    这篇文章主要为大家介绍了redis缓存存储Session原理机制详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪...

    程序媛张小妍9252021-11-25
  • RedisRedis 6.X Cluster 集群搭建

    Redis 6.X Cluster 集群搭建

    码哥带大家完成在 CentOS 7 中安装 Redis 6.x 教程。在学习 Redis Cluster 集群之前,我们需要先搭建一套集群环境。机器有限,实现目标是一台机器上搭建 6 个节...

    码哥字节15752021-04-07