江苏龙网

  1. 主页 > 生活百科 > >

Redis Stream 数据结构实现原理真的很强( 三 )

Redis


没毛病，小老弟很聪明 。为了节省内存，我使用了 Radix Tree 和 listpack 。Radix Tree 的 key 存储消息 ID，value 使用 listpack 数据结构存储多个消息，listapck 中的消息 ID 都大于等于 key 存储的消息 ID 。
我在前面已经讲过 listpack，这是一个紧凑型列表，非常节省内存 。而 Radix Tree 数据结构的最大特点是适合保存具有相同前缀的数据，从而达到节省内存 。
到底 Radix Tree 是怎样的数据结构，继续往下看 。
Radix TreeRadix Tree，也被称为 Radix Trie，或者 Compact Prefix Tree)，用于高效地存储和查找字符串集合 。它将字符串按照前缀拆分成一个个字符，并将每个字符作为一个节点存储在树中 。
当插入一个键值对时，Redis 会将键按照字符拆分成一个个字符，并根据字符在 Radix tree 中的位置找到合适的节点，如果该节点不存在，则创建新节点并添加到 Radix tree 中 。
当所有字符都添加完毕后，将值对象指针保存到最后一个节点中 。当查询一个键时，Redis 按照字符顺序遍历 Radix tree，如果发现某个字符不存在于树中，则键不存在；否则，如果最后一个节点表示一个完整的键，则返回对应的值对象 。
如下图展示一个简单的前缀树，将根节点到叶子节点的路径对应字符拼接起来，就得到了两个 key（“他说碉堡了”、“他说碉炸了”） 。

Redis Stream 数据结构实现原理真的很强

文章插图
你应该发现了，这两个 key 拥有公共前缀（他说碉），前缀树实现了共享使用，这样就可以避免相同字符串重复存储 。如果采用散列表的保存方式，那个 key 的相同前缀就会被多次存储，导致内存浪费 。
Radix Tree 改进每个节点只保存一个字符，一是会浪费内存空间，二是在进行查询时，还需要逐一匹配每个节点表示的字符，对查询性能也会造成影响 。
所以，Redis 并没有直接使用标准前缀树，而是做了一次变种——Compact Prefix Tree（压缩前缀树） 。通俗来说，当多个 key 具有相同的前缀时，那就将相同前缀的字符串合并在一个共享节点中，从而减少存储空间 。
如下几个 key（test、toaster、toasting、slow、slowly）在 Radix Tree 上的布局 。
Redis Stream 数据结构实现原理真的很强

文章插图
由于 Compact Prefix Tree 可以共享相同前缀的节点，所以在存储一组具有相同前缀的键时，Redis 的 Radix tree 比其他数据结构（如哈希表）具有更低的空间消耗和更快的查询速度 。
Radix Tree 节点的数据结构由 rax.h文件中的 raxNode 定义 。
typedef struct raxNode {uint32_t iskey:1;uint32_t isnull:1;uint32_t iscompr:1;uint32_t size:29;unsigned char data[];} raxNode;
  • iskey：从 Radix Tree 根节点到当前节点组成的字符串是否是一个完整的 key 。是的话 iskey 的值为 1 。
  • isnull：当前节点是否为空节点，如果当前节点是空节点的话，就不需要为该节点分配指向 value 的指针内存 。
  • iscompr，是否为压缩节点 。
  • size，当前节点的大小，具体指会根据节点类型而改变 。如果是压缩节点，该值表示压缩数据的长度；如果是非压缩节点，该值表示节点的子节点个数 。
  • data[]，实际存储的数据，根据节点类型不同而有所不同 。
  • 压缩节点，data 数据包括子节点对应的字符、指向子节点的指针，节点为最终 key 对应的 value 指针 。
  • 压缩节点，data 数据包含子节点对应的合并字符串、指向子节点的指针，以及节点为最终 key 的 value 指针 。
  • value 指针指向一个 listpack 实例，里面保存了消息实际内容 。
Radix Tree 最大的特点就是适合保存具有相同前缀的数据，实现节省内存的目标，以及支持范围查找 。而这个就是 Stream 采用 Radix Tree 作为底层数据结构的原因 。

【Redis Stream 数据结构实现原理真的很强】


推荐阅读


上一篇：ELK 处理 Spring Boot 日志，不错！

下一篇：分布式架构和微服务架构的区别