mochengqian opened a new issue, #1045: URL: https://github.com/apache/dubbo-go-pixiu/issues/1045
### ✅ 验证清单 - [x] 🔍 我已经搜索过 [现有 Issues](https://github.com/apache/dubbo-go-pixiu/issues)，确信这不是重复请求 - [x] 📋 我已经查看了 [发布说明](https://github.com/apache/dubbo-go-pixiu/releases)，确信此功能尚未实现 ### 🎯 功能描述 **需要帮忙，如果有不清楚的或者有更好的方案设计，可以和我讨论。** 本提案作为 #905 的后续优化，聚焦“必须重新构建哈希结构时”的成本。 ### 提案摘要 优化 RingHash 和 Maglev 的全量重建： - **RingHash：批量生成虚拟节点，最后只排序一次。** - **Maglev：按需计算排列位置，移除每个主机完整的排列数组。** 目标是降低首次构建、健康成员增删、节点地址或哈希参数变化后的 CPU、内存开销，以及关联的首批请求延迟。保留不可变快照、已有缓存复用、健康过滤和请求哈希语义。 当前实现并非所有情况都重建：同一快照上的请求读取缓存；满足条件的新快照复用旧缓存；无法复用且仍有健康节点时，首次访问才构建新结构。 ### 问题一：RingHash 全量构建反复排序 [[NewRingHash](https://github.com/apache/dubbo-go-pixiu/blob/cd1843dcdf4c28728d1951cad2ade2a3afbcb2a0/pkg/cluster/loadbalancer/ringhash/ring_hash.go#L40-L58)](https://github.com/apache/dubbo-go-pixiu/blob/cd1843dcdf4c28728d1951cad2ade2a3afbcb2a0/pkg/cluster/loadbalancer/ringhash/ring_hash.go#L40-L58) 创建空环，再逐个主机调用 Add；底层 [[gost v1.14.3 的 add](https://github.com/dubbogo/gost/blob/v1.14.3/hash/consistent/consistent.go#L141-L175)](https://github.com/dubbogo/gost/blob/v1.14.3/hash/consistent/consistent.go#L141-L175) 每加入一个不同主机，都会重新遍历位置 map 并排序。 因此，1024 个不同主机的一次全量构建，会执行 1024 次排序。 **实现建议：** 1. 增加真正的批量构建入口：按原输入顺序生成全部虚拟节点并确定位置归属，最后提取最终位置集合，统一排序一次。 2. 优先通过 gost 新增批量 API 后接入；如果采用 Pixiu 内部兼容构建器，需要明确维护边界。现有 Set 方法不能直接实现“一次排序”的目标。 3. 保持默认参数、哈希函数、虚拟节点 key 格式、取模规则、重复 host 去重及碰撞覆盖顺序一致；不擅自排序主机或改变选址映射。 4. 新环独立构建，不修改旧快照的 map/slice，不浅拷贝已使用的锁。 令 H_i 为加入第 i 个主机后的有效位置数，H 为最终有效位置数。该方案把排序部分从多次 Σ H_i log H_i 收敛到一次 H log H；虚拟节点哈希计算仍然需要完成。 ### 问题二：Maglev 预生成并保留 N×M 个排列位置 [[generatePerm](https://github.com/apache/dubbo-go-pixiu/blob/cd1843dcdf4c28728d1951cad2ade2a3afbcb2a0/pkg/cluster/loadbalancer/maglev/permutation.go#L147-L168)](https://github.com/apache/dubbo-go-pixiu/blob/cd1843dcdf4c28728d1951cad2ade2a3afbcb2a0/pkg/cluster/loadbalancer/maglev/permutation.go#L147-L168) 为每个主机创建长度 M 的 uint32 数组，并提前计算所有候选位置。N 为参与构建的主机条目数，M 为查找表长度。 N=1024、M=131071 时，仅这些数组的载荷为： `1024 × 131071 × 4 = 536,866,816 bytes ≈ 512 MiB` 这不包含最终查找表、map、endpoint 和 GC 开销；新旧快照同时存活时，内存压力还会增加。该数值是源码分配量推导，不是实测 RSS。 **实现建议：** 1. 每个主机只保存 offset、skip、游标及必要的填表状态；填表时按需计算下一候选位置，取消完整的 pos 数组。 2. 仍然完整构建新的查找表，将主要数据结构空间从 O(N×M + M) 降到 O(N+M)。填表仍有位置探测成本，不承诺总构建时间为 O(N+M)。 3. 进一步评估用连续主机列表和 uint32 槽位索引替换字符串槽位，明确空槽标记、索引边界，并验证额外一次索引访问对稳态请求的影响。 4. 如跨快照复用，只复用不可变的主机散列值或小规模排列参数；M 变化后重新推导 offset/skip。不共享可变游标和新表，不长期缓存整张 N×M 排列矩阵。 ### 兼容性与范围 - **RingHash 碰撞归属：** 当前 Remove 会直接删除目标主机计算出的位置。因此“复制旧环后直接 Remove”不能保证等价于全量重建；本次先提供正确、高效的全量基线，增量派生后续再评估。 - **Maglev 遍历顺序：** 当前通过 map 遍历主机，填表顺序不固定。新旧实现的性能和正确性比较必须使用相同显式顺序；若引入确定性排序，需要明确请求重映射的兼容性影响。 - **Maglev 整数运算：** 当前 `(offs + j*skip) % m` 使用 uint32 中间运算，大表下可能溢出。按需生成器应先保持已有算术语义；如修复溢出，需要独立的测试与路由变化说明，不能静默混入存储优化。 - **接口和健康语义：** 保留请求哈希、主机格式、重复主机处理、错误/fallback 契约，以及现有 Add/Remove 和只读视图的行为；新快照不能修改旧快照。 - **构建时机：** 本次保持已有按需构建与缓存复用。后台预构建、更新合并和发布调度单独评估，不能延迟健康摘除，也不能把大规模构建移进全局更新锁。 ### 验收标准 - [ ] RingHash 非空全量构建最多进行一次最终排序。 - [ ] RingHash 与现有逐项 Add 的参照实现，在相同有序输入和参数下保持位置归属及 Get/GetHash 结果一致，覆盖高碰撞、重复 host、默认和显式参数。 - [ ] Maglev 不再分配 N 个长度 M 的排列数组；通过 allocation/heap profile 验证主要数据结构达到 O(N+M) 空间。 - [ ] Maglev 与完整排列参照在相同顺序和算术语义下得到一致候选序列和最终表，覆盖大表下的整数溢出场景。 - [ ] 两个算法均覆盖空/单/多节点、健康节点增删、地址替换、健康摘除/恢复及哈希参数变化；新表只能返回该快照的健康主机。 - [ ] 旧快照不受新构建影响；同一快照及满足复用条件的新快照不重复构建；并发测试和 race 检查通过。 - [ ] 对 1/32/256/1024 个主机及多组合理参数进行多轮构建 benchmark，记录 ns/op、B/op、allocs/op、CPU 和内存峰值。大型 Maglev 参照单独运行并明确内存配额。 - [ ] 进行真实 Pixiu HTTP A/B：分别测试预热稳态和更新期间持续流量，报告更新耗时、变更到首批请求完成时间、P50/P95/P99、吞吐、错误率及 GC/内存峰值，并验证实际后端命中。 - [ ] 固定提交基线、Go 版本、CPU、请求 key 和算法参数；分别报告两个算法的构建收益和端到端收益，避免把选址微基准提升直接当作整体请求提升。 ### 📋 使用场景 本 issue 统一跟踪两个算法的实现和验证。上述内容为源码分析与优化提案，可落地的方案仍需深入分析、人工设计。 ### ⚖️ 复杂性与风险评估 _No response_ ### 🔗 外部依赖 _No response_ ### 📚 附加信息 _No response_ -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
