ytblog
11 min read

路由策略与分片机制：当前 ShardRouter 的实现方式

基于当前仓库实现分析 Seastar Log Engine 的路由策略，包括 hash_modulo、consistent_hashing、空 route_key 策略以及 append_batch 的分发快路径。

路由问题的本质

项目里的每条日志消息最终都要落到某个 shard 的 AsyncWriter。

路由策略需要同时满足几件事：

  1. 相同 route_key 尽量稳定落到同一个 shard
  2. 空 route_key 也要有明确策略
  3. 不同 shard 之间尽量均衡
  4. 给 append_batch() 留出优化空间

当前项目里的真实实现类型名是 ShardRouter，不是额外抽象出来的 RoutingEngine。

当前支持的路由配置

路由策略

当前只支持两种：

  • hash_modulo
  • consistent_hashing

空 route_key 策略

当前支持两种：

  • local
  • round_robin

这两组配置都在 EngineConfig 中：

RoutingStrategy routing_strategy = RoutingStrategy::hash_modulo;
EmptyRoutePolicy empty_route_policy = EmptyRoutePolicy::local;
std::size_t routing_virtual_nodes = 128;

真实的哈希实现

1. 非空 key 的稳定哈希

项目当前不是直接用 std::hash<std::string> 做路由基础，而是自己实现了一套稳定哈希。

原因很简单：

  1. std::hash 的行为不适合作为跨实现、跨环境的稳定分布基础
  2. 项目希望路由结果由自己控制

当前实现使用的是 FNV 风格哈希：

std::uint64_t ShardRouter::stable_hash(std::string_view value) noexcept

因此这里更值得关注的是稳定哈希带来的可预期分布，以及它与 shard 路由语义的配合方式。

2. 一致性哈希 ring 的数据结构

当前 consistent hashing ring 也不是 std::map<size_t, size_t>，而是：

std::vector<std::pair<std::uint64_t, unsigned>> _ring;

构建方式是：

  1. 对每个 shard
  2. 为每个虚拟节点生成 token
  3. push 到 _ring
  4. 最后排序

查询时通过 lower_bound() 找第一个 >= hash 的 token。

这个实现比 std::map 更接近“预构建排序数组 + 二分查找”的模式。

Rendering diagram...

hash_modulo 的当前语义

非空 route_key

对非空 key：

stable_hash(route_key) % shard_count

空 route_key

对空 key，不直接取模，而是根据 EmptyRoutePolicy 走 fallback：

  • local 落到当前 shard
  • round_robin 落到 empty_route_index % shard_count

所以“空 key 时总是 this_shard_id()”也不是完整说法，要看空 key 策略。

consistent_hashing 的当前语义

Rendering diagram...

ring 构建

构建流程：

  1. virtual_nodes 至少被修正为 1
  2. 对每个 shard 和每个 vnode 生成 token
  3. token 由 hash_parts(shard_id, vnode_id) 生成
  4. 所有 token 排序

因此 ring 大小满足：

ring_size = shard_count * virtual_nodes

这点在单测里也有直接验证。

路由

  1. 先计算 stable_hash(route_key)
  2. 在 _ring 中找第一个 token >= hash
  3. 若没找到，则回绕到 _ring.front()

返回结果不只是 shard，还包括：

  • shard
  • hash
  • token
  • used_local_fallback

这也是为什么 /v1/route 和 gRPC RouteReply 能直接把这些字段返回出来。

空 route_key 的当前处理

这是当前实现里比很多简化描述更重要的一部分。

local

empty_route_policy=local 时：

  • 空 key 直接落到当前 shard
  • used_local_fallback=true

优点：

  • 避免跨 shard 通信
  • 本地提交链路更短

代价：

  • 如果上层大量使用空 key，可能形成局部倾斜

round_robin

empty_route_policy=round_robin 时：

  • 空 key 不再固定写本地
  • 使用递增计数轮转分配 shard
  • used_local_fallback=false

这对多 shard 空 key 场景更均衡，但会增加跨 shard 分发开销。

append_batch 的路由优化

如果只从 ShardRouter 看，会以为“每条消息都各算一次 shard”；但 LogEngine::append_batch() 其实在上层做了多种快路径优化。

1. consistent hashing 下的同 key 快路径

如果：

  1. 使用 consistent_hashing
  2. 整批第一条消息的 route_key 非空
  3. 整批所有消息的 route_key 都和第一条相同

则整批直接发往同一个 shard。

2. local 策略下的全空 key 快路径

如果整批消息的 route_key 都为空，且策略是 local，则整批直接提交到当前 shard。

3. round_robin 策略下的全空 key 快路径

如果整批消息全是空 key，且策略是 round_robin，则先按 shard 均摊，再并发 fanout。

4. all_same_shard 快路径

即使 route key 不同，只要最终全部算出来都落到同一个 shard，也会直接一次 submit_many()。

5. 普通慢路径

只有在以上快路径都不命中时，才会：

  1. 预统计每个 shard 的消息数
  2. 构建 per_shard buckets
  3. 对每个 shard 发一次 submit_many()
  4. 用 when_all_succeed() 汇总

所以当前实现真正优化的重点，不只是“hash 算得快”，而是“尽量减少跨 shard fanout 次数”。

这套路由模型的实现边界

下面这些说法在当前项目里都应该避免：

  1. “RoutingEngine 使用 std::hash”
  2. “一致性哈希 ring 用 std::map”
  3. “空 key 永远回退本地 shard”
  4. “批量写入只会简单按 shard 分组”

这些都只描述了某种常见设计，不是当前仓库事实。

性能上应该怎么理解

当前仓库已有文档能支持的结论是：

  1. hash_modulo 路径更简单
  2. consistent_hashing 能提供更稳定的映射和 ring 可观测性
  3. empty_route_policy=round_robin 在空 key 密集场景下能提升吞吐，但会引入更多跨 shard 协调成本

但当前仓库并没有足够可靠的统一实测数据支持“某策略一定是 1.8M msg/s、另一策略一定是 1.6M msg/s”这种精确宣传。

因此文章更适合写“实现差异和工程权衡”，而不是虚构绝对性能表。

查询接口如何暴露路由信息

当前 query_server 和 query_client 都能直接查看路由结果：

HTTP

curl "http://127.0.0.1:18080/v1/route?key=route-a"

gRPC CLI

./build/log_engine_query_client --target 127.0.0.1:19090 --method route --route-key route-a

返回字段包括：

  • route_key
  • shard
  • hash
  • token
  • used_local_fallback

这使得当前路由设计不仅是“写入内部逻辑”，也是一个可直接观测的运维能力。

当前默认值与使用建议

默认值

当前默认是：

routing_strategy = hash_modulo
empty_route_policy = local
routing_virtual_nodes = 128

什么时候用 hash_modulo

适合：

  1. shard 数稳定
  2. 更关注实现简单和路径短
  3. 不准备做 shard 数变动实验

什么时候用 consistent_hashing

适合：

  1. 想保留 ring token 级别可观测性
  2. 需要更稳定的 key 分布语义
  3. 希望未来做 shard 数变化实验时更自然

什么时候考虑 round_robin

适合：

  1. 上层经常不传 route_key
  2. 空 key 流量占比很高
  3. 希望尽量让空 key 请求分散到多 shard

但代价也要明确：

  • 会增加跨 shard 提交
  • 并不总是比 local 更好

总结

当前项目的路由设计可以概括为：

  1. 用 ShardRouter 统一封装 hash_modulo 和 consistent_hashing
  2. 用稳定哈希而不是 std::hash
  3. 用排序后的 vector ring 而不是 map ring
  4. 明确区分空 key 的 local 与 round_robin
  5. 在 append_batch() 上层做多种分发快路径

如果只记一句话：

当前路由优化的核心，不只是“选哪种 hash”，而是“让写入批次尽量少跨 shard、少 fanout、少不必要调度”。

下一篇：《数据一致性与恢复模型：Checkpoint 与 Crash Recovery 的实现》