Fluent Bit 内置红黑树 rbtreeintrusive、零分配的自平衡树实现解析【免费下载链接】fluent-bitFast and Lightweight Logs, Metrics and Traces processor for Linux, BSD, OSX and Windows项目地址: https://gitcode.com/GitHub_Trending/fl/fluent-bit导读本文聚焦 Fluent Bit 仓库中lib/rbtree目录下的红黑树Red-Black Tree实现它是一套专为确定性determinism场景设计的intrusive侵入式、零内存分配自平衡二叉搜索树。该实现源自 Phil Vachon 的 rbtree 项目以 2-clause BSD 许可证收录进 Fluent Bit并被流处理器Stream Processor用于 GROUP BY 聚合节点的快速查找与去重。读完本文你将掌握这套红黑树的完整 API、底层平衡算法原理以及它在 Fluent Bit 真实代码路径中的用法。一、这是什么一套为确定性而生的红黑树lib/rbtree/README.md 对它的定位非常清晰A simple, intrusive, zero-allocation Red-Black tree implementation. Designed exclusively for systems where determinism is needed.三个关键词分别决定了它的设计取向simple简单只暴露树生命周期、查找、插入、删除等核心操作头文件加单个 C 文件即可落地intrusive侵入式节点结构struct rb_tree_node由调用方嵌入自己的业务结构体树本身不感知业务类型不拷贝、不搬运数据zero-allocation零分配插入、删除、旋转、重平衡全程不调用malloc内存完全由调用方提供因此执行时间可预期适用于不允许 GC 停顿、不允许 OOM 的确定性系统——这正是日志/指标处理器这类数据面组件的硬性要求。红黑树保证插入、删除、查找均为O(log n)最坏时间复杂度且从根到任意叶子的最长路径不超过最短路径的两倍黑高约束不会像普通 BST 那样退化成 O(n) 链表。二、源码布局与构建方式lib/rbtree目录结构非常精简文件作用rbtree.h公开 API数据结构定义、比较函数类型、返回码、内联工具函数rbtree.c实现插入/删除的旋转与重平衡算法、生命周期函数CMakeLists.txt构建脚本编译为静态库rbtreeREADME.md项目说明与来源声明构建层面CMakeLists.txt 将其编译为静态库rbtree在 Fluent Bit 主构建中src/CMakeLists.txt 将其加入FLB_SRC依赖列表而流处理器子模块 src/stream_processor/CMakeLists.txt 通过target_link_libraries(flb-sp rbtree)直接链接它。三、侵入式设计把节点嵌入你自己的结构体传统容器如链表、数组、非侵入式树会为每个元素单独分配节点内存而侵入式容器要求你在自己的结构体里内嵌一个容器节点容器只通过指针关系把这些碎片组织起来。3.1 节点结构struct rb_tree_node定义于 rbtree.hstruct rb_tree_node { struct rb_tree_node *left; /* 左孩子为空则为 NULL */ struct rb_tree_node *right; /* 右孩子为空则为 NULL */ struct rb_tree_node *parent; /* 父节点根节点为 NULL */ const void *key; /* 该节点的键 */ int color; /* 节点颜色红/黑 */ };头文件明确要求使用方永远不要直接修改或读取该结构的任何成员一切操作都通过公开函数完成。rb_tree_node也无需提前初始化——插入操作rb_tree_insert会自动初始化它的指针与键字段。3.2 用法示例嵌入与容器宏头文件给出的典型嵌入模式见 rbtree.h 的RB_CONTAINER_OF文档struct my_sample_struct { char *name; int data; struct rb_tree_node rnode; /* 内嵌树节点 */ };当通过树操作拿到一个struct rb_tree_node *后用宏RB_CONTAINER_OF(node, struct my_sample_struct, rnode)即可安全地反推回外层结构体指针。该宏利用__offsetof__计算成员偏移量从节点地址减去偏移量得到容器地址是侵入式容器指针即索引的核心手段#define RB_CONTAINER_OF(x, type, memb) \ ({ \ const __typeof__( ((type *)0)-memb ) *__member (x); \ (type *)( (char *)__member - __offsetof__(type, memb) ); \ })由于节点与业务数据同生命周期、同内存布局不会出现业务对象已释放而树节点仍悬空的额外风险窗口内存局部性也更优。四、比较函数决定树的排序语义红黑树是一棵有序树节点的左右位置完全由比较函数决定。库定义了两个函数指针类型见 rbtree.htypedef int (*rb_cmp_func_t)(const void *lhs, const void *rhs); typedef int (*rb_cmp_func_ex_t)(void *state, const void *lhs, const void *rhs);返回值语义与strcmp(3)一致(0, inf]lhs rhs节点走向右子树0lhs rhs视为重复键[-inf, 0)lhs rhs节点走向左子树。rb_cmp_func_ex_t额外携带一个void *state私有状态参数方便传入上下文。库内部通过__rb_tree_cmp_mapperrbtree.c将无状态的rb_cmp_func_t包装成带状态的rb_cmp_func_ex_t统一在树结构里只保存一种比较器。最简单的字符串键比较可以直接复用strcmpint my_cmp(const void *lhs, const void *rhs) { return strcmp((const char *) lhs, (const char *) rhs); }注意比较函数必须与rb_cmp_func_t签名严格一致否则编译器告警之下可能埋下运行期灾难头文件原话如此强调。五、核心 API 全景全部函数声明于 rbtree.h按职责可分为生命周期、查询、写入三类。5.1 返回值约定所有返回rb_result_t的函数使用统一错误码rbtree.h宏值含义RB_OK0x0操作成功RB_NOT_FOUND0x1未找到元素RB_BAD_ARG0x2非法参数通常是意外的 NULLRB_DUPLICATE0x3节点键与已有节点重复参数检查通过RB_ASSERT_ARG宏完成rbtree.h条件为假时触发assert并直接返回RB_BAD_ARGRB_UNLIKELY借助__builtin_expectMSVC 下退化为!!(x)提示编译器优化分支预测rbtree.h。5.2 生命周期rb_tree_new_ex(tree, compare, state)在调用方提供的内存上初始化一棵空树并绑定带状态比较器与私有 staterbtree.crb_tree_new(tree, compare)无状态版本内部走rb_tree_new_exrbtree.crb_tree_destroy(tree)将树元数据memset清零使其不可再用不会释放任何节点——注释明确说明调用方需通过应用自有的机制释放所有节点rbtree.c。这正是零分配设计的延续树的资源归调用方库只负责结构维护rb_tree_empty(tree, is_empty)以非零值输出树是否为空根为 NULLrbtree.c。5.3 查询操作rb_tree_find(tree, key, value)按给定键迭代查找命中时向value输出节点指针未命中返回RB_NOT_FOUND空树直接短路返回。查找路径为标准的 BST 迭代下降O(log n)rbtree.crb_tree_get_rightmost(tree, rightmost)返回按比较函数定义的最大节点。树结构缓存了rightmost指针O(1) 即可取得rbtree.hrb_tree_find_successor(tree, node, succ)/rb_tree_find_predecessor(tree, node, pred)返回指定节点的中序后继/前驱。右子树非空时取右子树最小/最大值否则沿父链回溯直到从左/右孩子关系中脱出rbtree.h。这两个函数是内联的配合__rb_tree_find_minimum/__rb_tree_find_maximum使用。5.4 写入操作rb_tree_insert(tree, key, node)插入节点并做必要的重平衡。插入的键必须与节点同寿命——注释明确要求 key 的生命周期不得短于节点在树中的驻留时间rbtree.c空树节点直接成为根并染黑否则按 BST 规则下降遇到compare 0返回RB_DUPLICATE不允许重复键新节点初始染红若始终走右子树则同步更新tree-rightmost调用__helper_rb_tree_insert_rebalance恢复红黑性质。rb_tree_find_or_insert(tree, key, candidate, value)查找优先的复合操作——找到同键节点则原样返回、不修改树找不到则插入候选节点。value始终输出已存在节点或刚插入的候选节点若要区分两种情况检查*value candidate即可rbtree.c。这在按键去重聚合场景中非常实用可省去一次先查后插的两次遍历rb_tree_remove(tree, node)摘除指定节点并视情况重平衡。若删除的是最右节点会用其前驱重算rightmost被摘除节点只有单孩子时直接替换有两个孩子时先找中序后继再通过__helper_rb_tree_swap_node交换rbtree.c。删除重平衡由__helper_rb_tree_delete_rebalance处理经典的四种兄弟节点情形rbtree.c。六、底层平衡原理颜色、旋转与重平衡红黑树在 BST 基础上增加红/黑着色约束保证树高近似平衡。本实现的核心算法集中在 rbtree.c颜色常量COLOR_BLACK 0x0、COLOR_RED 0x1rbtree.c关系辅助函数__helper_get_sibling/__helper_get_grandparent/__helper_get_uncle快速定位兄弟、祖父、叔父节点rbtree.c旋转原语__helper_rotate_left/__helper_rotate_right是重平衡的基本动作只改指针不改数据O(1) 完成局部结构调整rbtree.c插入重平衡__helper_rb_tree_insert_rebalancerbtree.c沿父链向上迭代情形 1叔节点为红——父、叔染黑、祖父染红问题上移一层继续处理情形 2叔节点为黑且当前节点是内侧孩子——先对父节点旋转一次把结构转为外侧形态情形 3叔节点为黑且当前节点是外侧孩子——父染黑、祖父染红再对祖父做一次反向旋转循环退出后强制将根染黑保证根为黑这一性质。删除重平衡__helper_rb_tree_delete_rebalancerbtree.c处理删除黑节点后兄弟节点为红/黑时的四种情形含双黑节点的向上传递。这些算法实现与 CLRS《算法导论》中的标准红黑树删除/插入流程一致全部就地完成无任何堆分配。七、在 Fluent Bit 中的真实应用流处理器 GROUP BY 聚合rbtree 并非收藏用的第三方代码它在 Fluent Bit 流处理器Stream Processor支持 SQL 式流查询的模块中承担了GROUP BY 聚合键去重与检索的核心工作。7.1 树初始化聚合窗口初始化时以flb_sp_groupby_compare作为比较器创建树src/stream_processor/flb_sp.crb_tree_new(task-window.aggregate_tree, flb_sp_groupby_compare);在哈希聚合hash aggregate路径同样如此src/stream_processor/flb_sp.c窗口翻转时重建、销毁时清理src/stream_processor/flb_sp_window.c。7.2 比较器实现多键混合类型排序flb_sp_groupby_compare位于 src/stream_processor/flb_sp_groupby.c它逐字段比较两个聚合节点的 GROUP BY 键支持FLB_SP_BOOLEAN、FLB_SP_NUM_I64、FLB_SP_NUM_F64、FLB_SP_STRING四类值并在整数/浮点相遇时做隐式类型提升后比较。这正体现了比较函数决定树的语义——通过一个自定义比较器树就能天然支持多键、混合类型的排序键。7.3 查找优先的插入rb_tree_find_or_insert在sp_process_aggregate_data中src/stream_processor/flb_sp.c每条流入记录都会按 GROUP BY 键尝试复用已有聚合节点rb_tree_find_or_insert(task-window.aggregate_tree, aggr_node, aggr_node-_rb_head, rb_result); if (aggr_node-_rb_head ! rb_result) { /* 键已存在丢弃新建节点复用已存在的聚合节点 */ flb_sp_aggregate_node_destroy(cmd, aggr_node); aggr_node container_of(rb_result, struct aggregate_node, _rb_head); container_of(rb_result, struct aggregate_node, _rb_head)-records; } else { /* 新键初始化聚合计数并把节点挂入聚合链表 */ aggr_node-records 1; mk_list_add(aggr_node-_head, task-window.aggregate_list); }这段代码是该库设计意图的绝佳注脚聚合节点结构体内部嵌有struct rb_tree_node _rb_head侵入式以聚合键集合为比较依据在树中定位find_or_insert一次遍历同时完成查重 插入使O(log n)的复杂度被压缩到极致节点内存由flb_calloc分配、由聚合窗口生命周期管理树本身零分配、零所有权。窗口清理时再通过 src/stream_processor/flb_sp.c 的rb_tree_destroy回收树状态。这一组合侵入式节点 查找优先插入 调用方管理生命周期正是为确定性而生在真实工程中的落地样板。八、把库接到你自己的模块里参考流处理器子模块的链接方式src/stream_processor/CMakeLists.txt在自己的 CMake 目标中链接即可target_link_libraries(your_target rbtree)头文件按#include rbtree.h使用构建时需保证lib/rbtree在头文件搜索路径中。使用步骤可归纳为四步定义业务结构体内嵌struct rb_tree_node成员实现比较函数签名严格匹配rb_cmp_func_t返回正/零/负分别表示大于/等于/小于初始化树rb_tree_new(tree, cmp)或带状态的rb_tree_new_ex操作树rb_tree_insert/rb_tree_find/rb_tree_find_or_insert/rb_tree_remove最后rb_tree_destroy收尾。九、小结lib/rbtree用约 750 行 C 代码交付了一套完整、自洽的红黑树侵入式设计消除分配与拷贝、统一错误码简化健壮性处理、O(log n) 的查找/插入/删除与右边界 O(1) 访问满足高频数据面需求。在 Fluent Bit 内部它已证明自己能在流式 GROUP BY 聚合这种每条记录都要查树的高频路径上稳定工作。如果你的模块也需要有序集合、范围查询或按键去重的数据结构且对分配行为敏感这套实现是现成的、经过生产验证的选择——源码就在 lib/rbtree/rbtree.c 与 lib/rbtree/rbtree.h 中可以放心阅读与复用。【免费下载链接】fluent-bitFast and Lightweight Logs, Metrics and Traces processor for Linux, BSD, OSX and Windows项目地址: https://gitcode.com/GitHub_Trending/fl/fluent-bit创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考