数据库分布式数据库后端【免费下载链接】cassandraMirror of Apache Cassandra项目地址https://gitcode.com/gh_mirrors/cassandr/cassandra点击查看免费下载Trie字典树是 Cassandra memtable 中表示分区键到分区数据映射的核心数据结构。本文基于仓库中的设计文档 Trie.md深入讲解 Cassandra 中 Trie 的设计动机、基于 Cursor 的遍历模型、多 Trie 合并与切片subtrie的实现原理并结合 Trie.java、InMemoryTrie.md 及 TrieMemtable.java 等源码帮助读者理解 Cassandra 如何在读路径上高效地组合、裁剪与消费键值数据。图一个经典 Trie 的节点结构示意图节点标签为 InMemoryTrie 节点 IDcontentArray[x]表示该节点带有内容背景Trie 在 Cassandra 中的角色Cassandra 使用 Trie 表示键值映射目前主要用于 memtable 中的分区映射partition map。其设计目标聚焦于高效执行等价于一次读查询的操作需要同时满足合并多个数据源并保持有序例如将多个 shard 的 Trie 合并为一个统一的视图将合并结果限制在某个键范围内即按分区键范围进行切片高效地遍历结果并提取所有键值组合以有序、低开销的方式消费内容。围绕这三个目标Trie.java 中的抽象类TrieT对外提供了一组公开方法用途方法说明消费内容forEachValue/forEachEntry有序调用消费者处理所有值或 (路径, 值) 对迭代转换values/valuesIterator、entrySet/entryIterator转换为有序的迭代器范围切片subtrie返回左右边界之间的子 Trie 视图合并mergeWith/ 静态merge/mergeDistinct合并两个或多个 Trie构造singleton/empty构造单键映射或空 TrieTrie 的内部表示则由Cursor游标给出Cursor 提供按序遍历 Trie 节点的方法合并、求交等各类变换都可以简单高效地构建在它之上。在真实读路径中的使用在 TrieMemtable.java 中每个 memtable 被划分为多个 shard每个 shard 维护一个InMemoryTrie并通过Trie.mergeDistinct(tries)生成统一的合并视图读取时再用mergedTrie.subtrie(left, includeStart, right, includeStop)TrieMemtable.java将读范围限定在查询键区间内flush 时也用subtrie(from, true, to, false)切出待刷盘区间TrieMemtable.java。遍历 Trie从经典回溯到 Cursor 游标经典遍历的缺陷假设要遍历下面这棵 Trie图见 InMemoryTrie.md.w1.svg。经典的深度优先遍历会在每个字符上下降图中浅蓝色并在回溯时上升回父节点图中粉色完整的走法见 InMemoryTrie.md.w2.svg。从图中可以看出很多回溯步骤只是为了紧接着再进行另一次回溯。而实际场景中我们常常预先知道某个节点在回溯时无需再检查如果节点只有一个子节点Chain节点中的所有节点都是如此如果正在下降进入它的最后一个子节点对Sparse节点很容易判断。利用这一信息遍历可以被简化见 InMemoryTrie.md.w3.svg。简化回溯路径还带来一个额外收益遍历状态表示更小从而显著降低 GC 压力。例如在 tractor 节点时回溯状态仅为[(tr, child 2)]下降到 tre 时变为[(tr, child 3)]下降到 tri 时因为 tr 已无更多子节点而清空。进一步优化直接跳到下一个子节点还可以更进一步不经过分支父节点直接跳到下一个子节点黑色箭头表示 Trie 结构本身见 InMemoryTrie.md.wc1.svg。这正是 Cursor 游标遍历的本质。仔细观察该图可以发现游标在每个节点上恰好停留一次节点按字典序被访问不再需要单独的回溯/上升操作因为所有箭头都在 Trie 的表示中前进为了知道下一个转移字符位于路径的什么位置每条转移都携带其结束时的下降深度descend-depth信息。将状态映射回路径的方法可以想象在每次转移时向一个数组的depth-1位置填入字符当前路径即该数组前depth个字符。例如在 tractor 节点数组为[t, r, a, c, t, o, r]下一次前进变为[t, r, e, c, t, o, r]当前路径即前 3 个字符 tre。Cursor 是什么Cursor 是有状态的对象保存遍历的回溯状态即路径上所有仍含有后续子节点的父节点列表以及回溯时应转向哪个子节点。Cursor 不保存路径本身——例如在合并 Trie 的遍历中由消费者自行构造路径比在每个源 Cursor 中复制一份更合理。同一 Trie 上可以并行构造和操作多个 Cursor。这种游标遍历非常高效同时仍携带足够的信息使合并与求交非常容易实现。当遍历单个 Trie或 union Trie 中的单源分支时还可以利用Cursor.advanceMultiple在Chain节点上一次下降多步见 InMemoryTrie.md.wc2.svg。为什么用 Cursor 而不是 Node最直观的 Trie 表示是直接把每个Node作为对象交给用户用户可以查询转移、获取子节点、按任意顺序遍历并保留需要的节点。当节点本身就是内存中的对象时这种表示自然且廉价——但 Cassandra 并非如此Trie 存储在整数 blob 或磁盘文件中并呈现为变换后的视图因此每个交给用户的Node对象都必须被构造出来我们只做深度优先遍历提供那种完全灵活的接口意义不大。只做深度优先遍历时Cursor 表示状态所需的对象远少于 Node 表示。考虑以 Node 为接口的方案在需要单步下降的过程如合并、求交中即使已知中间节点只有一个子节点、无需回溯迭代状态也必须为每个中间节点创建对象无子节点的最终状态需要一个节点对象合并等变换必须把结果呈现为变换后的节点同时还需要每个输入的节点若保留变换节点就必须同时保留其源。而 Cursor 可以在内部状态中表示前两类情况而无需额外回溯状态并且整个遍历只需构造一个变换后的 Cursor。此外Cursor 的回溯状态表示可以与该 Trie 的具体实现紧密耦合带来更多优化机会例如 InMemoryTrie.md 中提到的Split节点处理。为什么不用 VisitorVisitor推送式模式由 Trie 驱动迭代调用方提供 visitor/consumer。这在遍历单源Trie 时工作良好但要实现有序合并就必须引入某种 stop/restart 或 pull拉取机制复杂度反而上升。不过推送式遍历仍是消费最终变换/合并后内容的有效方式因此Trie提供了Walker接口和process方法Trie.javaforEachEntry与dump的实现正是它的直接应用。Cursor 接口Cursor 表示对 Trie 节点一次遍历的状态提供三个主要特征当前深度depth()当前在 Trie 中的下降深度刚创建位于根节点时为 0遍历耗尽时为 -1入转移incomingTransition()到达当前点所用的字节位于根节点时为 -1当前节点关联的内容content()任意节点含根节点都可能非空。并提供前进方法。这些信息足以提取全部路径也足以比较不同 Trie 上一起前进的 Cursor。前进总是有序的——若把 Trie 节点集合连同路径想象成序列Cursor 只能从路径字典序更小的节点前进到更大的节点。advance移动到紧邻的下一个位置也可以跳过若干项如skipChildren跳过当前节点的所有子节点。移动到字典序紧邻的下一个位置的规则若当前节点有子节点移动到其第一个子节点否则沿父链上升返回最近仍含有子节点的父节点的下一个子节点。只要 Trie 未耗尽前进总是从当前节点或父链上的某个节点向下一步。比较前进前后的深度可以判断若newDepth oldDepth 1则是纯下降上升步数为oldDepth 1 - newDepth。沿路径下降时Cursor 会在所有前缀上停留。// Cursor 接口核心方法摘自 Trie.java此处为示意结构 protected interface CursorT { int depth(); // 当前下降深度根为 0耗尽为 -1 int incomingTransition(); // 到达当前节点的字节根节点为 -1 T content(); // 当前节点内容可为 null int advance(); // 移动到字典序紧邻的下一个位置 default int advanceMultiple(TransitionsReceiver receiver) { return advance(); } default T advanceToContent(ResettingTransitionsReceiver receiver) { ... } int skipChildren(); // 忽略当前节点的子节点前进到父链上最近有剩余子节点的下一个子节点 }除单步advance外Cursor 还提供advanceMultiple当已知下降多步是高效的如位于Chain节点时一次下降多层若无法下降没有子节点或取到第一个子节点的子节点需要从磁盘拉取页面则行为与advance完全一致。其默认实现就是回退到advanceTrie.java。为方便起见接口还提供advanceToContent走到下一个内容非 null 的节点基于advanceMultiple实现Trie.java。Cursor 创建时位于根节点depth() 0、incomingTransition() -1由于 Trie 可能映射空键起始位置的content()可能非空。Cursor 不允许以耗尽状态depth() -1启动。并发语义摘自 Trie.java 的类注释Cursor 是有状态的遍历必须始终在单线程中推进若需要并发读取必须分别调用cursor()获取各自的 Cursor。Cursor 构造之前已完成的所有修改必须可见之后发生的并发修改可能被完整、部分或完全不呈现。并行使用 Cursor 的排序原理Cursor 的一个关键特性是可以很容易地并行遍历。当采用只前进较小者相等则都前进的策略时两个 Cursor 的状态可以通过以下规则比较按当前深度的逆序深度更高者更小/更靠前深度相等时按当前入转移的字典序更小者在前。该结论可用归纳法证明。对两个 Cursora、b记mindepth min(a.depth, b.depth)path(cursor)为 Cursor 所在节点对应的路径注意path(cursor)[cursor.depth - 1] cursor.incomingTransition维护三个不变式对任意深度i mindepth - 1有path(a)[i] path(b)[i]若a.depth b.depth则path(a)[mindepth - 1] path(b)[mindepth - 1]若a.depth b.depth则path(a)[mindepth - 1] path(b)[mindepth - 1]。这些条件保证了path(a) path(b)当且仅当a.depth b.depth或a.depth b.depth且a.incomingTransition b.incomingTransition。初态下两个 Cursor 都在深度 0 的根节点条件平凡成立。前进时前驱路径与新路径在新深度减一之前的所有位置必然相同因此若两个 Cursor 前进前相等位于完全相同路径上前进后条件 1 成立两路径中最早可能改变的字节在min(a.depth, b.depth) - 1处若深度不同深度较低的 Cursor 已把depth - 1处的字符前进掉而另一个保持不变因此条件 2、3 也成立。若前进前path(a)较小则a.depth b.depth并行遍历只前进aa的新深度高于b的深度条件 1-3 不变b.depth之前的字节在两个 Cursor 中都未改变与b相同条件 1 仍成立这些字节不可能变化条件 2、3 前提为假低于b的深度a必然前进了索引depth - 1处的字节而由条件 1该位置此前与b相同因此现在必然更大证得条件 2条件 1 仍成立条件 3 因前提为假而成立。b为较小者时对称同理。这构成了后文合并与切片算法正确性的数学基础。合并两个 Trie两个 Trie 可通过Trie.mergeWith合并由MergeTrie类实现MergeTrie.java。实现正是上述并行遍历方案的直接应用合并后的 Cursor 呈现当前较小者的深度和入转移前进时前进较小者两者相等则都前进。其advanceMultiple的取舍值得注意MergeTrie.java当两个 Cursor相等共享位置时必须逐字节下降以维持 Cursor 顺序因此退化为两次单步advance当处于仅由单一源覆盖的分支时可以使用该源的advanceMultiple——因为它与advance的唯一差异是向下多走几步而向下只会让该 Cursor 更深从而保持其更小的性质。为什么相等时不能用advanceMultiple若两者不等可以安全使用advanceMultiple已知较小者下降后深度更大、仍小于另一个。但相等时不能同时对两者使用例如一个下降穿过 a、另一个穿过 bb后者深度更高却并不更小会违反条件 2。content()的处理若两个源在同一位置都有内容调用MergeResolver.resolve(b1, b2)得到合并结果只有一个源有内容时直接返回MergeTrie.java。注意MergeResolver对参数顺序不做保证。另有MergeTrie.Distinct专门用于调用方保证键不重叠的场景可在valuesUnordered()中直接拼接两个源的未排序值列表以获得更高效率MergeTrie.java。合并任意数量的 TrieTrie.merge静态方法把合并扩展到任意数量的源由CollectionMergeTrie实现CollectionMergeTrie.java。它是上述两源合并的推广采用 MergeIterator 的min-heap 方案应用于 Cursor 之上。该方案的一个关键优化在 min-heap之前额外维护一个 head 元素用于优化单源分支——此时只需一次比较head 与堆顶即可前进而普通情形需要两次比较堆顶与其两个后继代价是仅在一般情形下可能多一次比较。与两源合并相同当已知 head 元素不等于堆顶即必然更小时可以安全地对其使用advanceMultiple。针对各源键必须互不相同的场景Trie.mergeDistinct提供了专门的变体合并过程中若多个源在同一路径上都有内容将抛出断言错误默认使用throwingResolverTrie.java。Trie.merge本身则对源数量做了特判0 个源返回empty()1 个源直接返回该源2 个源退化为mergeWith更多源才走CollectionMergeTrieTrie.java。切片Slicingsubtrie 的实现切片由SlicedTrie实现SlicedTrie.java通过Trie.subtrie使用。它同样可以看作并行遍历的变体同时遍历源 Trie 以及左右两个边界各自的单例 Trie。算法要点当源 Cursor小于左边界时不产生任何输出持续循环前进但为避免无谓地遍历子树用skipChildren而不是advance——因为如前所述更小的 Cursor 下降后仍然更小在左边界之前继续深入没有意义当源与左边界的某个节点匹配时两者都下降并把状态交给消费者一旦源被确定为大于左边界就不再处理左边界后续看到的状态全部交给消费者整个过程中同时处理右边界 Cursor一旦源大于右边界立即以depth -1结束迭代。SlicedTrie并不真正构造边界单例 Trie 及其 Cursor而是直接实现它们每个边界用一对depth和incomingTransition隐式表示SlicedTrie.java因为单下降路径的 Trie 只需跟踪当前深度前缀长度与转移字符即可。切片同样可以在确定严格处于切片内部时使用advanceMultiple即已越过左边界且位于右边界的某个前缀之前。此时下降到任意深度都是安全的——结果仍将小于右边界。公开 APITrie.java// 返回键落在 [left, right) 之间的子 Trie 视图左闭右开视图是活的 // 对源的任何写入都会反映在 subtrie 中。 public TrieT subtrie(ByteComparable left, ByteComparable right) // 完整形式可分别控制左右边界是否包含 public TrieT subtrie(ByteComparable left, boolean includeLeft, ByteComparable right, boolean includeRight)注意当left与right都为 null 时直接返回this该方法不校验参数正确性若右边界小于左边界结果可能为空或抛出异常视图是活的live view对源的写入会实时反映到切片中这也是 memtable 读路径能在不拷贝数据的情况下按范围读取的原因。底层实现速览InMemoryTrie 与节点类型理解 Cursor 的设计离不开它的主要实现InMemoryTrie设计文档见 InMemoryTrie.md。它是可变的内存 Trie面向单写线程并发多读场景主要特点完整支持Trie接口使用多种节点类型以提高效率任意节点包括中间前缀节点都可携带内容支持单写线程与多读者并发最大 Trie 大小约 2GB。其核心设计驱动是避免堆内存存储与 Java 对象管理Trie 结构存放在一个UnsafeBuffer可按需在堆上或堆外中以 32 字节的 cell代码中也称 block为分配、更新与复用单元内容目前仍以 Java 对象形式存放在内容数组中。指针编码是理解其布局的关键指针是一个 32 位整数其 27 个高位指定节点起始 cell 在缓冲区中的位置最低 5 位指定节点类型即 cell 内的偏移负值指针表示引用内容数组中的值即叶子节点特殊值NONE(0) 表示无子节点。例如指针0x0109E表示位于字节0x01080-0x0109F的 cell类型为Sparse由末 5 位0x1E指定0xFFFFFFF0是叶子节点内容索引为 0xF。节点类型对应 Trie 中的常见形态Split顶层少数、子节点众多、需要最少分支判断的节点Sparse子节点数少但数量巨大、最需要省空间的节点层Chain大量单子节点链承载键的尾部字节或公共前缀Leaf叶子不占用 cell直接以负指针引用内容数组Prefix罕见地在中间节点放置内容时使用的特殊类型。Split-Sparse-Chain-Leaf/Prefix 的层次模式可以重复出现例如分区键一层、聚簇键第一分量一层、第二分量一层等。测试与验证db.tries包配有完善的单元测试覆盖了本文讨论的各个操作MergeTrieTest.java 与 CollectionMergeTrieTest.java验证两源与多源合并的有序性与 resolver 语义SlicedTrieTest.java验证 subtrie 的边界包含/排除语义InMemoryTriePutTest.java、InMemoryTrieApplyTest.java 与 InMemoryTrieThreadedTest.java覆盖单写多读并发语义TrieToDot.java / TrieToMermaid.java可将 Trie 导出为 DOT/Mermaid 图便于可视化调试。小结Cassandra 的 Trie 设计围绕读查询等价操作展开以Cursor取代 Node/Visitor 作为遍历抽象用更小的回溯状态换取更低的 GC 开销深度优先的有序前进 深度与入转移的二元比较规则使得多 Cursor 的并行推进合并、切片既简单又高效advanceMultiple在可证明安全的场景下跳过Chain节点进一步减少步骤。这套机制最终服务于 memtable 的分区映射——TrieMemtable.java 通过mergeDistinct合并各 shard、以subtrie限定读与 flush 范围构成了 Cassandra 读路径与刷盘路径的核心数据结构基础。赞分享数据库分布式数据库后端【免费下载链接】cassandraMirror of Apache Cassandra项目地址https://gitcode.com/gh_mirrors/cassandr/cassandra点击查看免费下载相关推荐Cassandra Trie 接口深度解析Memtable 分区映射的游标式遍历、合并与切片机制Cassandra Trie 接口深度解析Memtable 分区映射的游标式遍历、合并与切片机制 Cassandra 的 Trie 接口源码位于 src/j数据库分布式数据库大数据后端Cassandra BTI SSTable 格式深度解析基于 Trie 的主索引设计与磁盘布局Cassandra BTI SSTable 格式深度解析基于 Trie 的主索引设计与磁盘布局 BTIBig Trie Indexed是 Apache C数据库分布式数据库大数据后端Tree-sitter 树遍历指南使用 Tree Cursor 高效遍历语法树Tree sitter 树遍历指南使用 Tree Cursor 高效遍历语法树 Tree sitter 为语法树节点提供了基于 TSNode 的 DOM 式访开发工具上一篇LangServe错误排查手册10个常见问题与解决方案的完整清单下一篇AudioNotes性能优化如何提升大文件处理速度和准确性创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考