Envoy CompiledStringMap 解析为静态头部查找定制的三叉式字符串映射结构【免费下载链接】envoyCloud-native high-performance edge/middle/service proxy项目地址: https://gitcode.com/GitHub_Trending/en/envoy导读CompiledStringMap是 Envoy 数据面在source/common/common目录下提供的一种针对静态字符串键集合优化的查找结构被 HTTP 头部映射HeaderMap的静态查找表StaticLookupTable用作底层实现。阅读完本文你将掌握该结构的三种节点设计长度分支节点、分支节点、叶子节点、编译期建树流程、查找期命中/未命中的判定路径以及它与标准字典树trie、absl::flat_hash_map、gperf哈希在性能与适用场景上的取舍。设计背景为什么需要一种编译过的字符串映射Envo 的 HTTP 请求处理路径上静态头部如:authority、content-type、x-envoy-*等的查找是超高频操作。在 header_map_impl.h 中可以看到StaticLookupTable直接继承了CompiledStringMapstd::functionStaticLookupResponse(HeaderMapImpl)struct StaticLookupTable : public CompiledStringMapstd::functionStaticLookupResponse(HeaderMapImpl) { StaticLookupTable(); ... };该表以ConstSingleton单例形式存在header_map_impl.h在第一次创建 HeaderMap 时把静态头部集合编译成查找结构之后每次查找都走find(key)这个 O(1) 起步的路径。文档明确说明该结构的核心定位是intended for static header maps即面向编译一次、只读查找的场景。三叉式结构长度表 分支节点 叶子节点依据 compiled_string_map.md 与 compiled_string_map.h 的实现整个结构由三类节点构成1. 长度分支节点length branch node字符串按键长分组生成一张从 0 开始的长度查找表。表中每个槽位要么是nullptr表示不存在该长度的字符串要么是指向该长度子树的节点指针。实现上对应CompiledStringMap的成员std::vectorstd::unique_ptrNode table_compile()时按键长对输入排序后逐段填充compiled_string_map.h。2. 分支节点branch node与标准 trie 按第一个字符固定分支不同这里在任意索引位上分支——编译时选择能产生最多分支的字符位置。节点内保存用于分支的字符索引index_分支中最低的字符值min_一个从低到高的字符槽位向量branches_如存在 c 与 f 两个分支向量就是[c][d][e][f]其中[d]、[e]为nullptr。对应 compiled_string_map.h 中BranchNode的find实现Value find(const absl::string_view key) override { const uint8_t k static_castuint8_t(key[index_]); if (k min_ || k min_ branches_.size() || branches_[k - min_] nullptr) { return {}; } return branches_[k - min_]-find(key); }先做下界/上界范围检查再检查槽位是否为空最后递归进入子树。3. 叶子节点leaf node叶子节点保存完整字符串用于最终校验和命中时返回的 value。其find在长度已经相等的前提下直接用memcmp做整串比较省略了逐字符比较compiled_string_map.hValue find(const absl::string_view key) override { // String comparison unnecessarily checks size equality first, we can skip // to memcmp here because we already know the sizes are equal. if (memcmp(key.data(), key_.data(), key.size())) { return {}; } return value_; }注释特别说明因为这是超级热路径连 ASSERT 都不加以避免拖慢 debug 构建。编译步骤按长度切分再选最分散的分支位文档以x-envoy-banana、x-envoy-pineapple、x-envoy-babana、x-envoy-grape、x-envoy-bacana、x-envoy-banara、something-else七个键为例完整展示了建树流程┌───────────────────┐ │ x-envoy-banana │ │ x-envoy-pineapple │ │ x-envoy-babana │ │ x-envoy-grape │ │ x-envoy-bacana ├──┐ │ x-envoy-banara │ │ │ something-else │ │ └───────────────────┘ │ ▼ split by length │ ▼ ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │ 0│ 1│ 2│ 3│ 4│ 5│ 6│ 7│ 8│ 9│10│11│12│13│14│15│16│17│ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴┬─┴┬─┴──┴──┴┬─┘ │ │ │ ┌────────────────────────────────────────────────┘ │ │ ▼ ┌────────────────────────────────┘ │ ┌─────────────┐ │ ▼ │x-envoy-grape│ │ ┌─────────────────┐ └─────────────┘ │ │x-envoy-pineapple│ ▼ └─────────────────┘ ┌────────────────┐ │ x-envoy-banana │ │ x-envoy-babana │ │ x-envoy-bacana │ │ x-envoy-banara │ │ something-else │ └─┬──────────────┘ │ Find best branch index (maximum unique branches) ▼ x-envoy-banana b r c something-else 22222222224232 ^ best index is here with 4 branches, n b c and e │ ▼ branch node at position 10, index 0 b ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │b │c │d │e │f │g │h │i │j │k │l │m │n │ └┬─┴┬─┴──┴┬─┴──┴──┴──┴──┴──┴──┴──┴──┴┬─┘ │ │ │ │ ▼ │ ▼ ▼ x-envoy-babana │ something-else ┌────────────────┐ ▼ │ x-envoy-banana │ x-envoy-bacana │ x-envoy-banara │ └───────┬────────┘ │ ▼ Find best index its position 12 with 2 branches │ branch node at position 12, index 0 n ▼ ┌──┬──┬──┬──┬──┐ │n │o │p │q │r │ └┬─┴──┴──┴──┴┬─┘ │ │ ▼ ▼ x-envoy-banana x-envoy-banara流程分四步按长度切分17 长度的x-envoy-pineapple单独成叶12 长度的x-envoy-grape单独成叶其余五个键进入同一子树。找最优分支位在x-envoy-banana、x-envoy-babana、x-envoy-bacana、x-envoy-banara、something-else这组中位置 10 上出现了n、b、c、e四个不同字符计数串22222222224232中的4是分支数最多的索引。建分支节点在位置 10 建立以b为最低值的槽位向量b→x-envoy-babana、c→x-envoy-bacana、e→something-else、n→ 下一层子树四个分支被填充。递归切分x-envoy-banana与x-envoy-banara在位置 12 上分支n与r各自成为叶子节点。源码中负责找最佳分支点的是findBestSplitPointcompiled_string_map.h对每个索引位用std::arraybool, 256统计不同字符数取count_最大者createEqualLengthNodecompiled_string_map.h则递归建树——单个键直接生成 LeafNode多个键先找最佳分支位再按字符排序分组递归。需要留意的是compile()会按键长排序并假设同一长度内键唯一重复键会触发ASSERT。查找流程长度表 逐层分支 叶节点整串校验查找与普通 trie 类似从上往下走树。文档用三个例子说明三种结束路径对应 compiled_string_map.h 的入口find先查长度表越界或槽位为空立即返回默认值查sponge长度 6长度表对应槽位是nullptr直接返回空值null value查x-envoy-banaka长度命中后进入最长子树位置 10 走n分支位置 12 的分支节点发现k低于向量最小值n范围检查失败返回空值查y-envoy-banara一路走到位置 12 的r分支的叶子节点最终memcmp整串比较发现y-envoy-barana≠x-envoy-banara返回空值。由此可见未命中的键在越早的层级被剪枝就越快长度表过滤掉所有不同长度的键分支节点的范围检查与空槽检查过滤掉同长度但字符不匹配的键只有一路走到底的键才付出整串memcmp的代价。性能命中大幅领先未命中基本持平文档给出的基准测试对静态头部映射对比固定 256 分支的标准 trie数据如下| Benchmark | trie | compiled | trieStdDev | compiledStdDev | change | | -- | -- | -- | -- | -- | -- | | bmHeaderMapImplRequestStaticLookupHits | 47.2ns | 16.4ns | 0.629 | 0.378 | -65.3% | | bmHeaderMapImplResponseStaticLookupHits | 34.7ns | 14.3ns | 0.571 | 0.085 | -58.8% | | bmHeaderMapImplRequestStaticLookupMisses | 6.89ns | 6.83ns | 0.044 | 0.034 | -0.01% | | bmHeaderMapImplResponseStaticLookupMisses | 6.40ns | 7.31ns | 0.028 | 0.057 | 14.2% |hit 基准在全量静态头部范围内查找miss 基准使用一小撮任意的、不匹配的头部。结论要点命中场景请求方向提升 65.3%、响应方向提升 58.8%。原因正如文档所说匹配x-envoy-banana从标准 trie 的 14 步降到 3 步加一次最终内存比较memcmp比逐字符比较快得多未命中场景部分情况更快当目标键与某条目共享前缀、能在中间层被剪枝时部分情况略慢如响应方向 14.2%源于更复杂的比较逻辑和编译版中动态函数选择的开销对比absl::flat_hash_map命中略快、未命中显著更快文档注明该基准数据已随时间丢失内存占用与常规 trie 不同叶子节点必须保存完整键例如x-envoy-前缀会在多个叶子中重复存储但节点数量更少不必为每个字符建节点且相比旧的固定节点 256 分支 trie单节点 8KB本结构的平均节点小于 60 字节单节点内存下降两个数量级以上。需要强调的是这些数字来自 Envoy 官方文档与当时的基准环境具体数值会随硬件与编译器变化但其相对趋势命中显著更快、未命中基本持平、节点更小可以反映结构本身的特性。局限性与适用前提文档明确列出三点限制理解它们才能正确选型只适用于非动态数据compile()是可以相当慢的多遍操作大输入下如果内容需要频繁修改编译开销会超过查找收益文档注释也提醒一旦第一次创建 HeaderMap静态头部集合就不允许再变化header_map_impl.h 提到这限制了通过 xDS/API 动态扩展 O(1) 头部的能力。不支持前缀匹配与常规 trie 不同无法做最近前缀或最长公共前缀查找只能精确匹配。gperf的取舍gperf哈希命中可能更快、未命中略慢但它要求内容在二进制编译期之前已知Envoy 的使用场景允许扩展在运行期动态加入静态头部内容这排除了gperf或使其不切实际。测试验证与可运行示例测试文件 compiled_string_map_test.cc 提供了可直接对照的行为契约FindsEntriesCorrectly编译 6 组键值对含不同长度、共享前缀、单长度键验证key-1/key-2/longer-key/bonger-key/bonger-bey/only-key-of-this-length均能命中key-0/key-3同长度不同字符、songer-key前缀相似但字符不同、absent-length-key长度表中不存在均返回空值EmptyMapReturnsNull空表编译后任何键都返回空值。测试同时印证了查找的三个剪枝层级同长度同分支才走到叶子key-0这类键被分支节点剪掉absent-length-key被长度表直接过滤。小结CompiledStringMap是 Envoy 对静态字符串键集合 极高频精确查找这一场景的专门优化以长度表做第一级过滤以最大分散索引位构建紧凑分支节点以整串memcmp做最终确认。它在静态头部映射上的命中性能相比传统 256 分支 trie 提升约六成节点内存从 8KB 级降到 60 字节级同时以不支持动态更新与前缀匹配换取了这一收益。对于需要为扩展注册的、编译期可枚举的只读字符串集合这一结构依然是值得参考的实践范本。【免费下载链接】envoyCloud-native high-performance edge/middle/service proxy项目地址: https://gitcode.com/GitHub_Trending/en/envoy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Envoy CompiledStringMap 解析：为静态头部查找定制的三叉式字符串映射结构
Envoy CompiledStringMap 解析为静态头部查找定制的三叉式字符串映射结构【免费下载链接】envoyCloud-native high-performance edge/middle/service proxy项目地址: https://gitcode.com/GitHub_Trending/en/envoy导读CompiledStringMap是 Envoy 数据面在source/common/common目录下提供的一种针对静态字符串键集合优化的查找结构被 HTTP 头部映射HeaderMap的静态查找表StaticLookupTable用作底层实现。阅读完本文你将掌握该结构的三种节点设计长度分支节点、分支节点、叶子节点、编译期建树流程、查找期命中/未命中的判定路径以及它与标准字典树trie、absl::flat_hash_map、gperf哈希在性能与适用场景上的取舍。设计背景为什么需要一种编译过的字符串映射Envo 的 HTTP 请求处理路径上静态头部如:authority、content-type、x-envoy-*等的查找是超高频操作。在 header_map_impl.h 中可以看到StaticLookupTable直接继承了CompiledStringMapstd::functionStaticLookupResponse(HeaderMapImpl)struct StaticLookupTable : public CompiledStringMapstd::functionStaticLookupResponse(HeaderMapImpl) { StaticLookupTable(); ... };该表以ConstSingleton单例形式存在header_map_impl.h在第一次创建 HeaderMap 时把静态头部集合编译成查找结构之后每次查找都走find(key)这个 O(1) 起步的路径。文档明确说明该结构的核心定位是intended for static header maps即面向编译一次、只读查找的场景。三叉式结构长度表 分支节点 叶子节点依据 compiled_string_map.md 与 compiled_string_map.h 的实现整个结构由三类节点构成1. 长度分支节点length branch node字符串按键长分组生成一张从 0 开始的长度查找表。表中每个槽位要么是nullptr表示不存在该长度的字符串要么是指向该长度子树的节点指针。实现上对应CompiledStringMap的成员std::vectorstd::unique_ptrNode table_compile()时按键长对输入排序后逐段填充compiled_string_map.h。2. 分支节点branch node与标准 trie 按第一个字符固定分支不同这里在任意索引位上分支——编译时选择能产生最多分支的字符位置。节点内保存用于分支的字符索引index_分支中最低的字符值min_一个从低到高的字符槽位向量branches_如存在 c 与 f 两个分支向量就是[c][d][e][f]其中[d]、[e]为nullptr。对应 compiled_string_map.h 中BranchNode的find实现Value find(const absl::string_view key) override { const uint8_t k static_castuint8_t(key[index_]); if (k min_ || k min_ branches_.size() || branches_[k - min_] nullptr) { return {}; } return branches_[k - min_]-find(key); }先做下界/上界范围检查再检查槽位是否为空最后递归进入子树。3. 叶子节点leaf node叶子节点保存完整字符串用于最终校验和命中时返回的 value。其find在长度已经相等的前提下直接用memcmp做整串比较省略了逐字符比较compiled_string_map.hValue find(const absl::string_view key) override { // String comparison unnecessarily checks size equality first, we can skip // to memcmp here because we already know the sizes are equal. if (memcmp(key.data(), key_.data(), key.size())) { return {}; } return value_; }注释特别说明因为这是超级热路径连 ASSERT 都不加以避免拖慢 debug 构建。编译步骤按长度切分再选最分散的分支位文档以x-envoy-banana、x-envoy-pineapple、x-envoy-babana、x-envoy-grape、x-envoy-bacana、x-envoy-banara、something-else七个键为例完整展示了建树流程┌───────────────────┐ │ x-envoy-banana │ │ x-envoy-pineapple │ │ x-envoy-babana │ │ x-envoy-grape │ │ x-envoy-bacana ├──┐ │ x-envoy-banara │ │ │ something-else │ │ └───────────────────┘ │ ▼ split by length │ ▼ ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │ 0│ 1│ 2│ 3│ 4│ 5│ 6│ 7│ 8│ 9│10│11│12│13│14│15│16│17│ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴┬─┴┬─┴──┴──┴┬─┘ │ │ │ ┌────────────────────────────────────────────────┘ │ │ ▼ ┌────────────────────────────────┘ │ ┌─────────────┐ │ ▼ │x-envoy-grape│ │ ┌─────────────────┐ └─────────────┘ │ │x-envoy-pineapple│ ▼ └─────────────────┘ ┌────────────────┐ │ x-envoy-banana │ │ x-envoy-babana │ │ x-envoy-bacana │ │ x-envoy-banara │ │ something-else │ └─┬──────────────┘ │ Find best branch index (maximum unique branches) ▼ x-envoy-banana b r c something-else 22222222224232 ^ best index is here with 4 branches, n b c and e │ ▼ branch node at position 10, index 0 b ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │b │c │d │e │f │g │h │i │j │k │l │m │n │ └┬─┴┬─┴──┴┬─┴──┴──┴──┴──┴──┴──┴──┴──┴┬─┘ │ │ │ │ ▼ │ ▼ ▼ x-envoy-babana │ something-else ┌────────────────┐ ▼ │ x-envoy-banana │ x-envoy-bacana │ x-envoy-banara │ └───────┬────────┘ │ ▼ Find best index its position 12 with 2 branches │ branch node at position 12, index 0 n ▼ ┌──┬──┬──┬──┬──┐ │n │o │p │q │r │ └┬─┴──┴──┴──┴┬─┘ │ │ ▼ ▼ x-envoy-banana x-envoy-banara流程分四步按长度切分17 长度的x-envoy-pineapple单独成叶12 长度的x-envoy-grape单独成叶其余五个键进入同一子树。找最优分支位在x-envoy-banana、x-envoy-babana、x-envoy-bacana、x-envoy-banara、something-else这组中位置 10 上出现了n、b、c、e四个不同字符计数串22222222224232中的4是分支数最多的索引。建分支节点在位置 10 建立以b为最低值的槽位向量b→x-envoy-babana、c→x-envoy-bacana、e→something-else、n→ 下一层子树四个分支被填充。递归切分x-envoy-banana与x-envoy-banara在位置 12 上分支n与r各自成为叶子节点。源码中负责找最佳分支点的是findBestSplitPointcompiled_string_map.h对每个索引位用std::arraybool, 256统计不同字符数取count_最大者createEqualLengthNodecompiled_string_map.h则递归建树——单个键直接生成 LeafNode多个键先找最佳分支位再按字符排序分组递归。需要留意的是compile()会按键长排序并假设同一长度内键唯一重复键会触发ASSERT。查找流程长度表 逐层分支 叶节点整串校验查找与普通 trie 类似从上往下走树。文档用三个例子说明三种结束路径对应 compiled_string_map.h 的入口find先查长度表越界或槽位为空立即返回默认值查sponge长度 6长度表对应槽位是nullptr直接返回空值null value查x-envoy-banaka长度命中后进入最长子树位置 10 走n分支位置 12 的分支节点发现k低于向量最小值n范围检查失败返回空值查y-envoy-banara一路走到位置 12 的r分支的叶子节点最终memcmp整串比较发现y-envoy-barana≠x-envoy-banara返回空值。由此可见未命中的键在越早的层级被剪枝就越快长度表过滤掉所有不同长度的键分支节点的范围检查与空槽检查过滤掉同长度但字符不匹配的键只有一路走到底的键才付出整串memcmp的代价。性能命中大幅领先未命中基本持平文档给出的基准测试对静态头部映射对比固定 256 分支的标准 trie数据如下| Benchmark | trie | compiled | trieStdDev | compiledStdDev | change | | -- | -- | -- | -- | -- | -- | | bmHeaderMapImplRequestStaticLookupHits | 47.2ns | 16.4ns | 0.629 | 0.378 | -65.3% | | bmHeaderMapImplResponseStaticLookupHits | 34.7ns | 14.3ns | 0.571 | 0.085 | -58.8% | | bmHeaderMapImplRequestStaticLookupMisses | 6.89ns | 6.83ns | 0.044 | 0.034 | -0.01% | | bmHeaderMapImplResponseStaticLookupMisses | 6.40ns | 7.31ns | 0.028 | 0.057 | 14.2% |hit 基准在全量静态头部范围内查找miss 基准使用一小撮任意的、不匹配的头部。结论要点命中场景请求方向提升 65.3%、响应方向提升 58.8%。原因正如文档所说匹配x-envoy-banana从标准 trie 的 14 步降到 3 步加一次最终内存比较memcmp比逐字符比较快得多未命中场景部分情况更快当目标键与某条目共享前缀、能在中间层被剪枝时部分情况略慢如响应方向 14.2%源于更复杂的比较逻辑和编译版中动态函数选择的开销对比absl::flat_hash_map命中略快、未命中显著更快文档注明该基准数据已随时间丢失内存占用与常规 trie 不同叶子节点必须保存完整键例如x-envoy-前缀会在多个叶子中重复存储但节点数量更少不必为每个字符建节点且相比旧的固定节点 256 分支 trie单节点 8KB本结构的平均节点小于 60 字节单节点内存下降两个数量级以上。需要强调的是这些数字来自 Envoy 官方文档与当时的基准环境具体数值会随硬件与编译器变化但其相对趋势命中显著更快、未命中基本持平、节点更小可以反映结构本身的特性。局限性与适用前提文档明确列出三点限制理解它们才能正确选型只适用于非动态数据compile()是可以相当慢的多遍操作大输入下如果内容需要频繁修改编译开销会超过查找收益文档注释也提醒一旦第一次创建 HeaderMap静态头部集合就不允许再变化header_map_impl.h 提到这限制了通过 xDS/API 动态扩展 O(1) 头部的能力。不支持前缀匹配与常规 trie 不同无法做最近前缀或最长公共前缀查找只能精确匹配。gperf的取舍gperf哈希命中可能更快、未命中略慢但它要求内容在二进制编译期之前已知Envoy 的使用场景允许扩展在运行期动态加入静态头部内容这排除了gperf或使其不切实际。测试验证与可运行示例测试文件 compiled_string_map_test.cc 提供了可直接对照的行为契约FindsEntriesCorrectly编译 6 组键值对含不同长度、共享前缀、单长度键验证key-1/key-2/longer-key/bonger-key/bonger-bey/only-key-of-this-length均能命中key-0/key-3同长度不同字符、songer-key前缀相似但字符不同、absent-length-key长度表中不存在均返回空值EmptyMapReturnsNull空表编译后任何键都返回空值。测试同时印证了查找的三个剪枝层级同长度同分支才走到叶子key-0这类键被分支节点剪掉absent-length-key被长度表直接过滤。小结CompiledStringMap是 Envoy 对静态字符串键集合 极高频精确查找这一场景的专门优化以长度表做第一级过滤以最大分散索引位构建紧凑分支节点以整串memcmp做最终确认。它在静态头部映射上的命中性能相比传统 256 分支 trie 提升约六成节点内存从 8KB 级降到 60 字节级同时以不支持动态更新与前缀匹配换取了这一收益。对于需要为扩展注册的、编译期可枚举的只读字符串集合这一结构依然是值得参考的实践范本。【免费下载链接】envoyCloud-native high-performance edge/middle/service proxy项目地址: https://gitcode.com/GitHub_Trending/en/envoy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考