02 | 键值对中字符串的实现，用char*还是结构体？

精选留言(13)

• 

  Kaito

  char* 的不足：
  - 操作效率低：获取长度需遍历，O(N)复杂度
  - 二进制不安全：无法存储包含 \0 的数据
  
  SDS 的优势：
  - 操作效率高：获取长度无需遍历，O(1)复杂度
  - 二进制安全：因单独记录长度字段，所以可存储包含 \0 的数据
  - 兼容 C 字符串函数，可直接使用字符串 API
  
  另外 Redis 在操作 SDS 时，为了避免频繁操作字符串时，每次「申请、释放」内存的开销，还做了这些优化：
  - 内存预分配：SDS 扩容，会多申请一些内存（小于 1MB 翻倍扩容，大于 1MB 按 1MB 扩容）
  - 多余内存不释放：SDS 缩容，不释放多余的内存，下次使用可直接复用这些内存
  
  这种策略，是以多占一些内存的方式，换取「追加」操作的速度。
  
  这个内存预分配策略，详细逻辑可以看 sds.c 的 sdsMakeRoomFor 函数。
  
  课后题：SDS 字符串在 Redis 内部模块实现中也被广泛使用，你能在 Redis server 和客户端的实现中，找到使用 SDS 字符串的地方么？
  
  1、Redis 中所有 key 的类型就是 SDS（详见 db.c 的 dbAdd 函数）
  
  2、Redis Server 在读取 Client 发来的请求时，会先读到一个缓冲区中，这个缓冲区也是 SDS（详见 server.h 中 struct client 的 querybuf 字段）
  
  3、写操作追加到 AOF 时，也会先写到 AOF 缓冲区，这个缓冲区也是 SDS （详见 server.h 中 struct client 的 aof_buf 字段）
  

  2021-07-29

  6

  14
• 

  悟空聊架构

  课后题：使用 SDS 字符串的地方？
  
  1. server.h 文件中的 `redisObject` 对象，key 和 value 都是对象，key （键对象）都是 SDS 简单动态字符串对象
  2. cluter.c 的 clusterGenNodesDescription 函数中。这个函数代表以 csv 格式记录当前节点已知所有节点的信息。
  3. client.h 的 clusterLink 结构体中。clusterLink 包含了与其他节点进行通讯所需的全部信息，用 SDS 来存储输出缓冲区和输入缓冲区。
  4. server.h 的 client 结构体中。缓冲区 querybuf、pending_querybuf 用的 sds 数据结构。
  5. networking.c 中的 catClientInfoString 函数。获取客户端的各项信息，将它们储存到 sds 值 s 里面，并返回。
  6. sentinel.c 中的 sentinelGetMasterByName 函数。根据名字查找主服务器，而参数名字会先转化为 SDS 后再去找主服务器。
  7. server.h 中的结构体 redisServer，aof_buf 缓存区用的 是 sds。
  8. slowlog.h 中的结构体 slowlogEntry，用来记录慢查询日志，其他 client 的名字和 ip 地址用的是 sds。
  
  还有很多地方用到了，这里就不一一列举了，感兴趣的同学加我好友交流：passjava。
  
  ----------------------------------
  
  详细说明：
  
  （1）Redis 使用对象来表示数据库中的键和值，每次创建一个键值对时，都会创建两个对象：一个键对象，一个值对象。而键对象都是 SDS 简单动态字符串对象，值对象可以字符串对象、列表对象、哈希对象、集合对象或者有序集合对象。
  
  对象的数据结构：
  
  server.h 文件中的 `redisObject` 结构体定义如下：
  
  ```c
  typedef struct redisObject {
      // 类型
      unsigned type:4;
      // 编码
      unsigned encoding:4;
      // 对象最后一次被访问的时间
      unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                              * LFU data (least significant 8 bits frequency
                              * and most significant 16 bits access time). */
      // 引用计数
      int refcount;
      // 指向实际值的指针
      void *ptr;
  } robj;
  ```
  
  再来看添加键值对的操作，在文件 db.c/
  
  ```C
  void dbAdd(redisDb *db, robj *key, robj *val)
  ```
  
  第一个参数代表要添加到哪个数据库（Redis 默认会创建 16 个数据库，第二个代表键对象，第三个参数代表值对象。
  
  dbAdd 函数会被很多 Redis 命令调用，比如 sadd 命令。
  
  （Redis sadd 命令将一个或多个成员元素加入到集合中，已经存在于集合的成员元素将被忽略。
  
  假如集合 key 不存在，则创建一个只包含添加的元素作成员的集合。
  
  当集合 key 不是集合类型时，返回一个错误。2）
  
  类似这样的命令：myset 就是一个字符串。
  ```SH
  redis 127.0.0.1:6379> SADD myset "hello"
  ```
  
  （2）集群中也会用到，代码路径： cluter.c/clusterGenNodesDescription
  
  所有节点的信息（包括当前节点自身）被保存到一个 sds 里面，以 csv 格式返回。
  
  （3）cluster.h 的 clusterLink 结构体中。clusterLink 包含了与其他节点进行通讯所需的全部信息
  
  ```C
  // 输出缓冲区，保存着等待发送给其他节点的消息（message）。
  sds sndbuf; /* Packet send buffer */
  
  // 输入缓冲区，保存着从其他节点接收到的消息。
  sds rcvbuf;
  ```
  
  （4）Redis 会维护每个 Client 的状态，Client 发送的请求，会被缓存到 querybuf 中。

  2021-07-29

  2

  3
• 

  frankylee

  既然这篇是讲解SDS的,那按道理来说 SDS内存空间分配策略,以及空间释放册罗 这块就应该讲清楚,但是通篇读下来好像并没提到这块,读完下面的精选留言部分读者可能仍然云里雾里

  2021-07-30

  

  
• 

  BrightLoong

  mac版本过高，5.0.8编译因为debug.c文件报错的问题，我这边参照最新版本的源文件修改了下，现在可以编译成功了，有需要可以自己下载替换
  链接: https://pan.baidu.com/s/1dKC9n2a9CmaQCkxn2OuZPw 提取码: 6d6v

  2021-07-30

  

  
• 

  ZmJ

  我记得sds还用到了c中的柔性数组

  2021-07-30

  

  
• 

  BrightLoong

  Mac系统太新，无法成功编译老版本的源码，最新版本的可以编译，看到最新版本debug.c里面如下
  #if defined(__APPLE__) && !defined(MAC_OS_X_VERSION_10_6)
      /* OSX < 10.6 */
      #if defined(__x86_64__)
      return (void*) uc->uc_mcontext->__ss.__rip;
      #elif defined(__i386__)
      return (void*) uc->uc_mcontext->__ss.__eip;
      #else
      return (void*) uc->uc_mcontext->__ss.__srr0;
      #endif
  #elif defined(__APPLE__) && defined(MAC_OS_X_VERSION_10_6)
      /* OSX >= 10.6 */
      #if defined(_STRUCT_X86_THREAD_STATE64) && !defined(__i386__)
      return (void*) uc->uc_mcontext->__ss.__rip;
      #elif defined(__i386__)
      return (void*) uc->uc_mcontext->__ss.__eip;
      #else
      /* OSX ARM64 */
      return (void*) arm_thread_state64_get_pc(uc->uc_mcontext->__ss);
      #endif
  #elif defined(__linux__)
      /* Linux */
      #if defined(__i386__) || ((defined(__X86_64__) || defined(__x86_64__)) && defined(__ILP32__))
      return (void*) uc->uc_mcontext.gregs[14]; /* Linux 32 */
      #elif defined(__X86_64__) || defined(__x86_64__)
      return (void*) uc->uc_mcontext.gregs[16]; /* Linux 64 */
      #elif defined(__ia64__) /* Linux IA64 */
      return (void*) uc->uc_mcontext.sc_ip;
      #elif defined(__arm__) /* Linux ARM */
      return (void*) uc->uc_mcontext.arm_pc;
      #elif defined(__aarch64__) /* Linux AArch64 */
      return (void*) uc->uc_mcontext.pc;
      #endif
  #elif defined(__FreeBSD__)
      /* FreeBSD */
      #if defined(__i386__)
      return (void*) uc->uc_mcontext.mc_eip;
      #elif defined(__x86_64__)
      return (void*) uc->uc_mcontext.mc_rip;
      #endif
  #elif defined(__OpenBSD__)
      /* OpenBSD */
      #if defined(__i386__)
      return (void*) uc->sc_eip;
      #elif defined(__x86_64__)
      return (void*) uc->sc_rip;
      #endif
  #elif defined(__NetBSD__)
      #if defined(__i386__)
      return (void*) uc->uc_mcontext.__gregs[_REG_EIP];
      #elif defined(__x86_64__)
      return (void*) uc->uc_mcontext.__gregs[_REG_RIP];
      #endif
  #elif defined(__DragonFly__)
      return (void*) uc->uc_mcontext.mc_rip;
  #else
      return NULL;
  请问老师有什么解决办法吗

  2021-07-30

  

  
• 

  一步

  SDS 的定义中 如 sdshdr16 中的 hdr 代表什么意思的？

  2021-07-29

  1

  
• 

  可怜大灰狼

  对比之前3.0版本改变：1.考虑字符串不同长度的场景。2.支持最大长度由4字节到8字节。3.free变成了alloc。
  代码比之前复杂些，味道还是之前的味道

  2021-07-29

  

  
• 

  Milittle

  设计着实牛逼：
  1. 使用sds这个字符数组保存所有8 16 32 64的结构体。
  2. 结构体中的len alloc 对应不同类型占不同字节数，flags始终是相同的，后面char buf[]就是真实的字符串。
  3. SDS_HDR 这个宏定义，一键让sds回到指针初始的地方，对变量进行设置。
  4. 一开始纳闷在取flags的时候，直接使用s[-1],不会数据越界么，但是你仔细瞧一瞧，发现这个s指向的位置，刚好是char buf[]这里，-1 的位置刚好是flags。害，还是发现c牛逼。一个指针掌控的死死的。
  
  望赐教
  

  2021-07-29

  

  
• 

  Milittle

  第一行set 命令后面的dict可以设置进去么？ 为啥我的报了格式错误：
  1. 文中命令存在中文双引号
  2. 文中的value，没有进行字符串的序列化，无法识别。
  望赐教

  2021-07-29

  1

  
• 

  曾轼麟

  Redis设计sds的意图：
      1、满足存储传输二进制的条件（避免\0歧义）
      2、高效操作字符串（通过len和alloc,快速获取字符长度大小以及跳转到字符串末尾）
      3、紧凑型内存设计（按照字符串类型，len和alloc使用不同的类型节约内存，并且关闭内存对齐来达到内存高效利用，在redis中除了sds，intset和ziplist也有类似的目底）
      4、避免频繁的内存分配，除了sds部分类型存在预留空间，sds设计了sdsfree和sdsclear两种字符串清理函数，其中sdsclear，只是修改len为0以及buf为'\0'，并不会实际释放内存，避免下次使用带来的内存开销（老师可能忘记提及了）
  
  
  此外sds的使用几乎可以贯穿整个redis，在server.h文件中以redisServer 和 client 为例子（client既可以是普通客户端，也可以是slave）
  
  client:
      1、querybuf（查询缓冲区使用sds，RESP的协议数据）
      2、pending_querybuf（易主时候的等待同步缓冲区）
      等等
  
  
  redisServer：
      1、aof_buf（aof缓冲区）
      等等

  2021-07-29

  

  
• 

  Fan

  看redis源代码用什么工具比较好用呢？

  2021-07-29

  4

  
• 

  Geek_f71330

  老师你好，对今天这节课的理解有下:
  1. \0会导致无法存储包含\0的字符串
  2. sds加了当前字符串长度，分配的空间大小，主要作用是为了在对字符串进行修改时的方法能够更高效，同时也解决了\0字符无法存储的问题。当然，这样相对于char*的方式，这应该是增加了内存消耗，但这是值得的。
  3. 在结构体中设置flag标记位，区别不同长度的字符串，是为了减少空间浪费。
  4. 告诉编译器打包时更紧凑，能节约更多空间。
  
  我想请问老师:
  关于第4点，让编译器不以8个字节作为单位去生成结构体定义，固然优化了空间，但是不是会导致读写变慢？这里不理解，如果以8个字节为单位没有好处，为什么编译器会这么去做？

  2021-07-29

  1

  