Fluent Bit 内嵌 rbtree 库：零分配侵入式红黑树的源码级解析

Fluent Bit 内嵌 rbtree 库：零分配侵入式红黑树的源码级解析

【免费下载链接】fluent-bitFast and Lightweight Logs, Metrics and Traces processor for Linux, BSD, OSX and Windows项目地址: https://gitcode.com/GitHub_Trending/fl/fluent-bit

导读

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，能够在 O(log n) 时间内完成插入、删除与查找。本文聚焦于 Fluent Bit 仓库中随附的 lib/monkey/deps/rbtree 子库——一个取自 pvachon/rbtree 项目的简单、侵入式（intrusive）、零分配（zero-allocation）红黑树实现，其设计目标是为对确定性有严格要求的系统服务。读完本文，你将掌握该库的侵入式数据结构设计、完整 API 用法、平衡维护原理，并看到它在 Fluent Bit 流处理器（Stream Processor）聚合与 Monkey HTTP Server MIME 类型注册中的真实落地用法，可直接在自己的 C 项目（尤其是嵌入式、网络服务与日志管道场景）中复用它。

一、仓库中的原始描述与定位

lib/monkey/deps/rbtree/README.md 对这份第三方库的定位写得非常简洁：

A simple, intrusive, zero-allocation Red-Black tree implementation. Designed exclusively for systems where determinism is needed. Licensed under a 2-clause BSD license for the sake of simplicity.

这段描述包含了三个关键设计承诺，也是理解这份代码的钥匙：

1. Simple（简单）：仅由 rbtree.h 与 rbtree.c 两个文件组成，无任何外部运行时依赖（仅依赖标准库<stdlib.h>、<assert.h>、<string.h>），通过 CMakeLists.txt 编译为一个静态库rbtree。
2. Intrusive（侵入式）：树节点struct rb_tree_node是直接嵌入到用户自定义结构体内部的，而非像传统容器那样由容器内部 malloc 节点再拷贝数据。这让"一个对象属于多个集合""对象生命周期完全由所有者掌控"成为可能。
3. Zero-allocation（零分配）：整个插入、删除、查找过程从不调用malloc/free，所有节点内存由调用方预先提供，因此不存在分配失败路径，也不存在内存碎片，行为完全确定（deterministic）。

这一点与 Fluent Bit 的整体设计哲学高度一致——作为运行在资源受限环境中的日志采集器，Fluent Bit 需要内存行为可预期、无 GC、无隐藏分配的核心数据结构。

二、侵入式设计：rb_tree_node与RB_CONTAINER_OF

2.1 节点结构

在 rbtree.h 中，节点被定义为：

struct 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; /* 节点颜色：红或黑 */ };

头文件特别强调：使用者不应直接修改或检查这些成员，所有操作都应通过提供的 API 完成。

将节点嵌入用户结构体的典型写法（头文件自带示例）：

struct my_sample_struct { char *name; int data; struct rb_tree_node rnode; /* 嵌入的树节点 */ };

注意这里key是以const void *存储的指针，因此键值所指向的内存必须与节点在树中的存活期一致——头文件在rb_tree_insert的注释中明确警告：键的生命周期必须与节点本身一样长（"must live as long as the node itself is in the tree"）。

2.2 从节点反推容器：RB_CONTAINER_OF

侵入式容器面临的核心问题是如何从struct rb_tree_node *拿到包含它的用户结构体。该库用 GCC 扩展宏 RB_CONTAINER_OF 解决：

#define RB_CONTAINER_OF(x, type, memb) \ ({ \ const __typeof__( ((type *)0)->memb ) *__member = (x); \ (type *)( (char *)__member - __offsetof__(type, memb) ); \ })

其原理与内核container_of完全一致：用__offsetof__(type, memb)求出成员在结构体内的字节偏移，再用节点指针减去该偏移即得到容器起始地址。这是零分配侵入式容器的标准配套设施。

三、核心 API 全景

3.1 返回值与错误码

所有返回rb_result_t的函数都有统一的错误码体系，定义在 rbtree.h：

参数校验通过 RB_ASSERT_ARG 宏完成：当断言失败时触发assert并返回RB_BAD_ARG；它内部借助RB_UNLIKELY（在非 Windows 平台上展开为__builtin_expect(!!(x), 0)）标记"分支不太可能被走到"，引导编译器做分支预测优化。

3.2 比较函数

树的遍历顺序完全由调用方提供的比较函数决定，支持两种签名：

typedef 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);

返回值约定（两种签名一致）：

• (0, +inf]：lhs > rhs
• 0：lhs == rhs
• [-inf, 0)：lhs < rhs

_ex版本多出的state参数用于传递私有上下文。普通版本rb_tree_new内部通过 __rb_tree_cmp_mapper 把无状态比较函数包装成带状态版本（将函数指针本身当作state传入）。

3.3 生命周期管理

rb_result_t rb_tree_new_ex(struct rb_tree *tree, rb_cmp_func_ex_t compare, void *state); rb_result_t rb_tree_new(struct rb_tree *tree, rb_cmp_func_t compare); rb_result_t rb_tree_destroy(struct rb_tree *tree);

• rb_tree_new_ex（rbtree.c）：初始化树元数据——根节点、rightmost（最右节点，供快速获取最大值）置为 NULL，记录比较函数与私有状态。
• rb_tree_new（rbtree.c）：普通版本的便捷包装。
• rb_tree_destroy（rbtree.c）：仅memset清零树元数据结构，不释放任何节点——文档明确要求调用方用自己的机制回收全部节点内存。这正是零分配语义的体现：树的析构不拥有任何资源的所有权。

3.4 查询与遍历

其中rb_tree_find的查找循环（rbtree.c）直接体现了二叉搜索树的性质：比较结果小于 0 走左子树，等于 0 命中，大于 0 走右子树。

3.5 插入与删除

rb_result_t rb_tree_insert(struct rb_tree *tree, const void *key, struct rb_tree_node *node); rb_result_t rb_tree_remove(struct rb_tree *tree, struct rb_tree_node *node);

• 插入是 O(log n) 的，最坏需要两次树遍历：一次定位插入位置（必然发生），一次用于重平衡（可能发生）。
• 删除则是把节点从树中"拼接"出去（splice），随后视情况重平衡以维持红黑性质。删除同样不释放节点内存。

四、红黑性质与平衡维护（源码级原理）

红黑树之所以能把高度维持在 O(log n)，依靠的是节点颜色（COLOR_BLACK/COLOR_RED，定义在 rbtree.c）与五条经典不变量。该实现在重平衡时使用了一组静态辅助函数：

• __helper_get_sibling：取兄弟节点；
• __helper_get_grandparent：取祖父节点；
• __helper_get_uncle：取叔父节点；
• __helper_rotate_left /__helper_rotate_right：左右旋转，重连指针并维护父指针与tree->root。

以左旋为例，其指针操作为：x的右孩子y上位，x->right接管y->left，y->left指向x，并逐层更新父指针；若x原本是根，则旋转后y成为新根。旋转是插入/删除修复流程的基本动作，配合变色共同恢复红黑性质。

需要说明的是，头文件同时暴露了内联的 __rb_tree_find_minimum /__rb_tree_find_maximum（沿左/右孩子一路下行取最小/最大节点），它们被后继、前驱查询复用。

五、在 Fluent Bit / Monkey 中的真实用法

5.1 Fluent Bit 流处理器：GROUP BY 聚合节点索引

在 Fluent Bit 的 Stream Processor（流式 SQL 处理）中，rbtree 被用来索引聚合（aggregation）节点，是"零分配 + 确定性"特性最典型的应用场景。

在 include/fluent-bit/stream_processor/flb_sp.h 中，聚合节点结构体直接嵌入struct rb_tree_node _rb_head：

struct flb_sp_task_window { ... struct rb_tree aggregate_tree; /* 按 group-by 键组织的聚合树 */ ... }; struct flb_sp_hopping_slot { struct rb_tree aggregate_tree; ... };

聚合数据节点同样内嵌_rb_head作为树节点。实际操作包括：

• 初始化：rb_tree_new(&task->window.aggregate_tree, flb_sp_groupby_compare)（src/stream_processor/flb_sp.c）；
• 命中即取、未命中即插：rb_tree_find_or_insert(&task->window.aggregate_tree, aggr_node, &aggr_node->_rb_head, &rb_result)（src/stream_processor/flb_sp.c）；
• 滑动窗口过期清理：rb_tree_find定位后用rb_tree_remove摘除过期聚合节点（src/stream_processor/flb_sp_window.c）；
• 收尾销毁：rb_tree_destroy清空树元数据（src/stream_processor/flb_sp.c）。

由此可以看出，Stream Processor 利用红黑树在 O(log n) 时间内按 group-by 键查找/更新聚合状态，而窗口数据本身仍由mk_list（链表）管理，两者分工明确。构建层面，src/stream_processor/CMakeLists.txt 通过target_link_libraries(flb-sp rbtree)把 rbtree 静态库链接进流处理模块。

5.2 Monkey HTTP Server：MIME 类型注册表

rbtree 的另一处使用者是 Fluent Bit 内嵌的 Monkey HTTP 服务器：在 lib/monkey/mk_server/mk_mimetype.c 中，服务器启动时用rb_tree_new(&server->mimetype_rb_head, rbtree_compare)初始化 MIME 类型树，随后对每种扩展名调用rb_tree_insert建树（mk_mimetype.c），请求处理时则从server->mimetype_rb_head.root出发按扩展名快速查找（mk_mimetype.c）。这同样是在请求热路径上避免每次 malloc 的确定性设计。

六、构建与集成方式

rbtree 是一个完全独立的静态库，集成方式很轻量：

• 编译：add_library(rbtree STATIC ${src})，源码仅 rbtree.c 一个文件（见 lib/monkey/deps/rbtree/CMakeLists.txt）；
• 使用方只需包含rbtree.h并在链接阶段链接rbtree静态库；
• 整个实现不依赖任何第三方头文件，仅用标准 C 库，extern "C"包裹保证 C++ 项目可直接包含头文件。

七、实用示例：完整的增查删流程

综合头文件自带示例与本库 API，一个典型用法如下（供在自己的项目里按需裁剪）：

#include <rbtree.h> #include <stdio.h> #include <assert.h> struct my_sample_struct { const char *name; /* 键 */ int data; struct rb_tree_node rnode; /* 侵入式节点 */ }; /* 比较函数：按 name 字符串排序 */ static int cmp_names(const void *lhs, const void *rhs) { return strcmp(lhs, rhs); } int main(void) { struct rb_tree tree; struct my_sample_struct a = { "apple", 1, {0} }; struct my_sample_struct b = { "banana", 2, {0} }; struct rb_tree_node *found; assert(rb_tree_new(&tree, cmp_names) == RB_OK); /* 插入 */ assert(rb_tree_insert(&tree, a.name, &a.rnode) == RB_OK); assert(rb_tree_insert(&tree, b.name, &b.rnode) == RB_OK); /* 查找 */ if (rb_tree_find(&tree, "banana", &found) == RB_OK) { struct my_sample_struct *obj = RB_CONTAINER_OF(found, struct my_sample_struct, rnode); printf("found: %s, data=%d\n", obj->name, obj->data); } /* 删除（仅摘除节点，不释放内存） */ assert(rb_tree_remove(&tree, &b.rnode) == RB_OK); assert(rb_tree_destroy(&tree) == RB_OK); return 0; }

注意两个易错点：其一，插入的key指针必须在节点驻留树内期间持续有效；其二，rb_tree_destroy不会释放节点，所有struct my_sample_struct需要调用方自行管理。

八、总结：为什么 Fluent Bit 需要这样一棵树

回到 README.md 的定位——"Designed exclusively for systems where determinism is needed"。对 Fluent Bit 这类日志/指标/链路处理器而言，在接收、聚合、转发的每一条热路径上，隐藏的堆分配都会带来延迟抖动与碎片化风险。rbtree 以侵入式节点 + 零分配的形态，把排序索引能力（O(log n) 查找）以完全确定的内存行为注入到流式聚合和 HTTP 服务中；2-clause BSD 许可也让它能被随包静态集成而无需担心授权负担。理解这份代码，等于同时掌握了一条可复用的确定性容器实现，以及 Fluent Bit 核心数据路径上的一段关键基础设施。

【免费下载链接】fluent-bitFast and Lightweight Logs, Metrics and Traces processor for Linux, BSD, OSX and Windows项目地址: https://gitcode.com/GitHub_Trending/fl/fluent-bit