做接口服务最怕的就是"看着简单，一上线就现原形"。最短路径这种需求，单机算是一回事，做成服务、接上任务调度、扛住业务流量，又是另一回事。今天这篇就把我做的这个"发布最短路径 NAService 与 routetask 调用服务"的项目完整拆一遍，从需求到最后发布上线，全部过程、踩坑和取舍都写出来，希望能帮到正准备自己搞路径服务的人。
这个项目本质上要解决三件事：第一，把最短路径计算从业务代码里抽出来，做成独立的服务（NAService）；第二，路径规划不能所有请求都同步算，耗时长的要走异步任务（routetask）；第三，服务要能发布上线，而且能稳定运行。围绕这三件事，我会讲讲整个系统是怎么设计的、核心怎么实现的、发布时验证了什么，以及我踩过的那些坑。
1. 需求背景与服务拆分思路
1.1 为什么需要做一个独立的路径服务
我当时所在的业务线是做同城配送调度的，调度系统里有一个很核心的需求：给每一笔订单计算骑手从当前位置到取货点、再到送达点的最短路径。一开始这个逻辑直接写在调度服务里，用的是一张简单的静态路网表，数据量几千个节点的时候没问题，但业务一旦铺开，节点到了几万个、路线组合到了百万级，直接写在业务代码里的路径计算就开始拖后腿。
最明显的问题是：调度主服务既要管订单状态机、又要管骑手分配、还要管超时重试，本来就忙，路径计算又是一个高 CPU 消耗的操作，两者挤在一起，互相拖累。经常出现的情况是，高峰期订单量上来，路径计算请求一多，调度主服务的接口延迟直接翻倍。
改造的思路很明确：把最短路径计算从业务服务里拆出去，做成一个独立部署、独立扩容、独立监控的服务。拆出来之后有几个直接的好处：第一，路径计算的负载不会影响到订单主流程；第二，路径计算服务可以自己水平扩缩容，扛大促流量；第三，这个能力以后给其他业务线（比如新开的跑腿服务、预估送达时间服务）复用，不需要再写一遍。
1.2 NAService 的职责边界
NAService 这个名字看起来有点抽象，其实内部的含义是 "Navigation Algorithm Service"。它接收起点和终点的坐标（经纬度），在准备好的路网图上计算最短路径，返回给调用方一条由有序坐标点组成的路线。
在设计服务边界的时候，我划得很清楚，NAService 只做三件事：
- 接收路径计算请求（起点、终点、可选途经点）
- 执行最短路径算法，输出有序坐标序列
- 暴露服务运行状态、耗时指标、缓存命中率等监控数据
而所有跟业务状态（订单是否超时、骑手是否接单）、存储状态（路网数据从哪里来）相关的东西，NAService 一概不管。路网数据由另一个离线数据管道统一构建好，定时同步给 NAService，NAService 只负责加载。
这里有个在系统设计里经常被忽略的点：服务边界不是越细越好，而是要让每个服务的职责是可理解、可测试、可扩展的。把路网数据更新也放进 NAService 就会让事情复杂化，因为数据构建和在线查询是两个完全不同的节奏和资源模型。
1.3 routetask 调用服务的定位
routetask 是独立于 NAService 的另一层服务。它解决的问题是：不是所有路径计算都需要同步给调用方。
业务场景里有一类需求：用户下单时，系统需要提前计算骑手可能用到的所有路径，用于预估时间、调度预排、距离计费等。这类计算不要求结果在一两秒内返回，但量很大，而且可以慢慢算。如果所有请求都同步压给 NAService，NAService 的计算线程会被占满，那些真正需要实时响应的高优请求反而会被拖慢。
routetask 的做法是：接收任务、持久化任务状态、返回任务 ID，异步去调用 NAService 批量计算，完成后把结果写回任务表，再由业务方轮询或通过回调拿到结果。它相当于一个"缓冲池+任务调度器"，把同步压力转化为异步吞吐。
2. 技术选型：图结构、算法与任务模型
2.1 最短路径算法选了哪条路线
这是整个项目里我最想聊的部分。一说到最短路径，大家第一时间想到的都是 Dijkstra。Dijkstra 是正确的、通用的，但它在工程上有一个很有意思的问题：在大规模路网里，Dijkstra 会从起点向四周均匀扩展搜索区域，很多明显不可能经过的节点也会被遍历到。坐标（4000, 8000）这种很偏的起点和终点，Dijkstra 可能把半个城市的节点都算一遍，时间会涨得很夸张。
我在这个项目里没有直接裸用 Dijkstra，而是做了"基础优先 + 加速扩展"的方案：核心算法是 A* 搜索，同时保底用 Dijkstra 做备份。
A* 和 Dijkstra 的区别在于，它引入了一个启发函数 h(n)，用来估算"当前节点到终点的直线距离"。搜索的时候，优先扩展那些 f(n) = g(n) + h(n) 最小的节点，其中 g(n) 是已经走过的实际距离。因为 h(n) 是直线距离，它永远不会高估真实路径，所以 A* 在保证最优性的同时，搜索范围比 Dijkstra 小很多。
启发函数我选的是球面距离公式，也就是把经纬度转成弧度，然后算两个坐标在地球表面上的大圆距离。有的实现会直接用欧几里得距离，在经纬度坐标下会导致启发值偏大（因为纬度是度，距离也是度，数值上不匹配），所以这里一定要转成真实距离单位。
还有一种工程上很常用但经常被忽略的折中方案是双向搜索：从起点和终点同时开始扩展，两个方向的搜索前沿相遇时就停止。双向搜索的加速原理很简单，搜索的空间是一个"菱形"而不是"圆形"，面积小了一大半。我的实现里其实保留了双向搜索的开关，线上默认跑 A*，遇到某些特殊图（比如启发估值不准的稀疏图），会切到双向 Dijkstra 对比一下结果，确保正确性。
2.2 图数据的内存模型
路径计算服务要扛高并发，图的加载和访问速度是关键。我测试过几种存储方案，简单对比一下：
| 存储方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 关系型数据库表 | 实现简单、更新方便 | 每次查询都要走 SQL，延迟高，CPU 浪费在协议解析上 | 数据量极小、频率极低 |
| Redis 哈希表 | 读取快 | 无法表达图结构，边的关系要拼 key，内存浪费大 | 静态查询 |
| 进程内邻接表 | 全内存、O(1) 访问 | 内存占用固定，更新需全量加载 | 高并发路径计算首选 |
我最终选了进程内邻接表。所谓邻接表，就是把每个节点作为 key，value 是它的所有邻居节点和对应边权。在 Java/C++ 里实现时，要尽量避免用大量小对象（比如用数组存边、用 int 存数组下标），否则 GC 压力会很大。我单独写了一个图构建模块，在加载阶段把解出来的边数据存成 int 数组，节点和边的关联关系用连续内存段表示，查询的时候直接用下标访问。
这里推荐一个我总结出来的实践：不要用 Map<Integer, List > 这种朴素结构，因为每个 Edge 对象都有对象头，几百万条边算下来内存暴涨。用两个数组，一个存所有边的目标节点和权重，一个存每个节点的出边在边数组里的起始下标，压测效果差了大概 3-4 倍。
2.3 同步接口还是异步任务
NAService 本身提供的是同步计算接口（计算很快，几十毫秒到几百毫秒），而 routetask 是异步任务服务。这里有一个细节很多人第一次做会想不明白：既然 NAService 计算很快，为什么还要异步？
答案是"快"和"稳定"是两回事。NAService 计算一个路径可能只要 30ms，但如果同时有 5000 个任务进来，NAService 会忙于处理这些批量任务，每个任务都占用 CPU 和内存，此时再插进来一个实时路径计算请求，延迟就会从 30ms 变成 300ms 甚至超时。
所以我在设计时，把实时量大的查询走 NAService 的同步接口，把批量耗时的查询走 routetask 的异步队列。routetask 内部有自己的线程池和队列，它会控制同时下发到 NAService 的并发数，而不是一股脑全推过去。这个"限流闸门"设计我花了不少时间调参数，后面会展开讲。
3. 核心实现：NAService 内部是怎么工作的
3.1 路网数据的构建与加载
路网数据并不是 NAService 自己产生的，它有单独的数据管道。原始数据是从众包地图数据里导出得到的一个个路口和连接路段的集合，每一段路都带有距离、道路等级、是否允许步行等信息。数据管道的输出是一个二进制文件，NAService 启动时加载这个文件构建邻接表。
加载的时候有几个坑要注意：
第一个坑是坐标精度。原始数据里经纬度常常是像 116.1234567890 这种高精度小数，但直接用 double 存会浪费内存。我的做法是把经纬度直接放大到整数（乘以 1e7 后取整），存成 int，这样坐标比较和距离计算都会快一点，内存也能省一半。
第二个坑是数据一致性。有些原始数据里会出现孤立节点（没有任何边连进来），有些边可能是单向的，有些边权重是负数。这个项目在构建时做了一轮"实体校验"：负权重的边直接丢弃；孤立节点标记为不可达，计算到它们时直接返回无路径错误。
第三个坑是压缩存储。邻接表构建出来之后，我做了二次压缩：对道路等级相同的边，只用整数 ID 做标记；对多个边权重相同的路段，用查重表去重。这些优化做下来，一个 100 万节点、250 万边的图，内存占用大概能控制在 180MB 左右，普通 4GB 内存的容器就能跑。
加载完成后，NAService 对外暴露一个buildStatus指标，如果数据版本不对或者边数为 0，服务健康检查会直接不通过，不会让流量打进来。
3.2 最短路径的工程化实现
核心算法我以 A* 为主，但写的时候加了不少工程细节。
先说我用的启发函数。因为业务输入是经纬度，我把经纬度转成球面坐标后，算大圆距离（haversine 公式）。这个距离再乘一个系数，系数略大于 1（我线上用 1.15），可以让搜索稍微偏向"更接近终点的方向"，同时还能保证最优性在容差范围内。这个系数是拍脑袋调出来的，但实测效果不错。
然后是优先队列。A* 需要频繁取最小 f 值节点，Java 里我用的是堆（PriorityQueue），但要注意堆里会存在同一个节点的多条记录（因为某个节点可能被多次松弛）。所以我在节点上额外维护了一个closed标记，只有在记录出堆且表示的是最新松弛结果时才处理。
伪代码大概是这样的：
public RouteResult shortestPath(int startId, int targetId) { // gScore 存起点到每个节点的实际距离 // fScore = gScore + hScore PriorityQueue<NodeRecord> openQueue = new PriorityQueue<>(NodeRecord.comparatorByFScore()); openQueue.add(new NodeRecord(startId, 0.0, heuristic(startId, targetId))); while (!openQueue.isEmpty()) { NodeRecord current = openQueue.poll(); if (current.nodeId == targetId) { return reconstructPath(current.nodeId); } if (closed[current.nodeId]) continue; closed[current.nodeId] = true; for (int edge : outgoingEdges(current.nodeId)) { int neighbor = edge.target; double tentativeG = gScore[current.nodeId] + edge.weight; if (tentativeG < gScore[neighbor]) { gScore[neighbor] = tentativeG; double f = tentativeG + heuristic(neighbor, targetId); parent[neighbor] = current.nodeId; openQueue.add(new NodeRecord(neighbor, tentativeG, f)); } } } return RouteResult.notFound(); }这个实现有几个小的优化点。一是用float存 gScore 和 fScore，而不是double，虽然精度低了一点点，但内存减少一半，而且 CPU 上 float 计算会快一些，实测 P99 有 8%-10% 的提升。二是把 heuristic 的结果提前算好存下来，不要在每次入堆时才重新计算，避免重复 compute。
不过要说最关键的，还是"提前终止"条件的判断。A* 里头只要出堆的节点是目标节点，理论上就可以结束了。但这依赖启发函数的一致性或可采纳性。我的 haversine 距离是可采纳的，所以这个终止条件安全。两个方向上如果任何一方搜索了超过一个阈值（比如 50000 个节点），我会直接放弃 A* 改走双向 Dijkstra，避免因为启发失败导致搜索爆炸。
3.3 路径还原与结果构造
算完路径之后，需要输出一串有序的坐标点。这里有一个很容易出错的地方：路径还原不能只还原经过的"节点 ID"，还要还原节点之间的"边上采样点"。因为实际路网中的边是一条有形状的 LineString，节点只是端点，如果不把这些中间形状点写进返回结果，前端展示的路线就是一条拐来拐去的折线，和实际道路完全对不上。
还原过程是这样的：先根据parent数组从终点回溯到起点，得到节点序列。然后遍历每一条连接的边，从边数据里取出这条边的形状点坐标，依次追加到结果列表里。相邻节点之间的形状点可能会有一小段重叠（边是共享的），我做了简单的去重，只在结果里保留每个坐标点一次。
最终返回给调用方的是一份 JSON，里面包含：路径总距离（米）、预计耗时（秒，按不同出行方式计算）、坐标点数组、经过的主要路段名称列表。坐标点数组我不会全量返回，而是做了一次"抽稀"：如果连续坐标点之间的直线距离小于 3 米，就只保留一个。这样既保证了前端能画出精确的路线，又不会让响应体过大。
3.4 接口参数设计与响应格式
NAService 的接口我用的是 RESTful 风格，POST /api/v1/navigation/route。
请求体设计得很精简：
{ "origin": { "lat": 31.2297, "lng": 121.4737 }, "destination": { "lat": 31.2304, "lng": 121.4745 }, "travelMode": "DRIVING", "alternateRouteCount": 1 }响应体：
{ "routeId": "abc123", "distanceMeters": 1832, "durationSeconds": 312, "polyline": [ { "lat": 31.2297, "lng": 121.4737 }, { "lat": 31.2298, "lng": 121.4740 } ], "status": "SUCCESS", "buildVersion": "20240512_control" }travelMode决定了走哪套路网数据（步行、骑行、驾车分别有独立的图，因为同一段路的权重不同）。我在服务里做了按 travelMode 分桶的图实例，互不干扰，加载时并行加载。
响应里的buildVersion是一个很容易被忽略但非常有用的字段。它表示当前服务加载的是哪一版路网数据，一旦线上出现路径异常（比如某条路线绕远路），可以直接通过这个字段快速判断是不是数据版本的问题，省去很多排查时间。
4. routetask 调用服务的实现与联动
4.1 任务模型与状态机
routetask 接收的任务不是单个路径计算，而是一个"批量请求"。比如业务方可能一次性提交 500 个起点终点对，routetask 会把这些坐标对拆分成多个子任务，每个子任务对应一个 NAService 请求。
任务表我设计成了 MySQL 表，核心字段有：task_id、batch_status（PENDING/RUNNING/SUCCESS/FAILED）、total_count、success_count、failed_count、回调地址、创建时间、更新时间。子任务的详细信息放在另一张子任务表里，用 task_id 关联。
状态机很朴素，但足够用：
- PENDING：任务刚创建，还没有任何子任务开始计算
- RUNNING：至少一个子任务在执行中
- SUCCESS：所有子任务全部计算成功
- FAILED：有子任务最终失败（可能部分成功）
为什么不用更复杂的消息队列持久化？因为我考虑到任务量虽然大，但单个任务的生命周期很短（最多几分钟），用数据库做持久化和状态调度已经够了，还省掉了一套消息队列组件的运维成本。等任务量再大 10 倍、需要横向扩展 Worker 时，再考虑拆分到消息队列也不迟。
4.2 异步调用 NAService 的并发控制
routetask 内部有一个线程池，核心线程数和最大线程数都设为 16，队列容量 2000。线程池的工作就是把子任务逐个发给 NAService。
这里最值得讲的是并发控制，不能一次性把所有子任务都压到 NAService 上。
我给 NAService 单独配了一个 QPS 限制器，基于令牌桶实现，默认 500 QPS。routetask 在发送子任务之前，会先调用一个本地 rate limiter 检查令牌，如果拿不到令牌，就进入一个轻量 sleep（5ms），然后重试拿令牌。
这样做的直接效果是：即使业务方一次性提交了 10000 个子任务，routetask 也会把它们按 500 QPS 的节奏平滑地下发，NAService 的计算线程不会被打满。而 NAService 上还留有余量给真正的实时同步请求。
我压测过一组数据：没有限流器时，NAService 在 3000 个并发子任务同时到达的场景下，P99 延迟飙升到 2.3 秒，触发了大量超时；加上限流器后，同样的任务量，NAService 的 P99 稳定在 42ms，几乎没有超时。
4.3 回调与结果聚合
当所有子任务都执行完毕，routetask 会根据任务配置去回调业务方。回调 URL 是创建任务时由业务方传入的，routetask 只需要 POST 一个包含 task_id 和最终聚合统计的结果过去。
回调重试我做了三次：第一次失败后等 1 秒，第二次等 3 秒，第三次等 10 秒。三次都失败就把任务标记为CALLBACK_FAILED，同时写一张补偿表，由离线 job 第二天重抛。
结果聚合的逻辑也不复杂：所有子任务成功，聚合结果为"成功"；有子任务失败，聚合结果为"部分成功"，并把失败原因分类（如超时、无路径、校验失败等）统计出来返回给业务方。业务方拿到这个结果后，可以自己去补偿失败的订单，也可以通过我们提供的一个查询接口重新触发失败子任务。
5. 发布流程与线上验证
5.1 发布前要过的质量关卡
发布是一个动作，但在我这个项目里，我把"发布"理解成一整套验证流程。NAService 是核心路径服务，一旦挂了或算错了，直接影响线上所有人的导航和调度，所以发布比普通 CRUD 服务要谨慎得多。
我自己的发布前检查清单包括：
- 单元测试：覆盖图构建、A* 正确性、边界条件（起点终点重叠、无路可达、超大图）
- 接口压测：设置不同并发数，记录 P50/P95/P99 延迟与错误率
- 数据一致性校验：用同一对起点终点，对比旧版本服务与新版本服务的结果，要求坐标序列完全一致或误差在 0.5% 以内
- 错误注入测试：手动往路网里塞几条坏数据，看服务是否会优雅降级而不是崩溃
一致性校验是非常重要的一步，因为最短路径算法在不同版本的路网数据上，结果是可能变化的。如果变化幅度大，说明数据源或者构建逻辑有 bug。我专门写了个对比脚本，随机抽 2000 对起点终点，分别请求旧新两个服务，比较路径距离的差异。超过 5% 就报警。
5.2 灰度发布策略
NAService 用的是一个标准的三步灰度方式：
第一步，部署一个新版本实例，不接流量，只做健康检查和数据加载验证。第二步，把新实例挂上一个独立的测试入口，让内部测试工具发请求验证正确性。第三步，在流量调度层面，把新版本实例的权重设置为 5%，观察 30 分钟，确认监控指标（错误率、P99 延迟、CPU、内存）没有异常后再逐步上调到 30%、100%。
灰度期间我特别关注的监控指标有三个：路径计算请求成功率、平均耗时、路径距离分布。成功率下降直接报警；平均耗时突然变高说明图加载有问题；路径距离分布如果和发布前明显不一致，说明数据构建出错了。
回滚策略也提前想明白了：在发布平台上保留上一版本的镜像和配置，一旦灰度期间出现任何问题，一条命令切回旧版本的实例，整个过程在 2 分钟内完成。
5.3 线上常见故障演练
发布之后，我其实故意做了几次故障演练来检验系统的韧性：
- 停掉 NAService 实例，看 routetask 会不会一直重试把队列打满（结论：不会，因为有超时和退避）
- 杀掉一个已经加载了图数据但还没就绪的实例，看调度层会不会把流量发到未就绪实例上（结论：健康检查挡住了）
- 让 NAService 内存接近上限，看 GC 会不会引发长停顿（结论：加了堆外缓存和对象复用后，停顿控制在 20ms 内）
这些演练有些是发布后第二天做的，有些是一个月后做的。每次演练都记录了一份问题清单，再反哺到代码里修复，真正让服务从"能跑"变成"扛得住"。
6. 踩坑实录与排查思路
6.1 动态规划半年后才发现的路网数据过期问题
上线三个月后，业务方反馈了一条路线绕远，排查下来发现：路网数据是最初的全量数据，而地面上的路早就有了一条新修的快速路连通，导航里完全没有。
这个问题的根源是：路网数据更新的节奏和线上服务加载的节奏不一致。我后来加了"数据版本热更新"机制，NAService 预留了两个图实例，后台线程每 5 分钟检查一次是否有新版数据文件，有的话就在后台加载新实例，加载完成后原子切换流量。
这一套热更新上线后，路网数据基本能保持 T+1 的新鲜度，绕远路的工单量大幅下降。
6.2 负权重边导致 A* 结果异常
有一次排查发现，个别的 A* 计算返回的路径明明直行更近，却带着用户绕了个大弯。我一开始以为是启发函数写错了，后来把路径轨迹拉出来对比，才注意到绕弯的那段路权重比直行的小。
再往前查，发现是数据管道的清洗逻辑漏掉了负权重边（可能因为某个路段的实际施工导致权重变成 -200）。A* 算法一旦允许负权边，最优性就完全失效了，因为启发函数不再能作为最优性的上界。
处理方式是把负权边在构建阶段全部识别出来，要么修正为正值，要么直接剔除。同时我在服务入口加了一层校验：任意一边的权重小于 0，图构建直接失败，不让异常状态进入线上。
6.3 任务队列堆积导致回调风暴
第一次上线 routetask 后，第二天早高峰经历了一次小事故：某个业务方提交了一大批任务，可能是一次性导入历史订单，所有任务在 5 分钟内全部到达，routetask 的队列瞬间堆了 3 万条子任务。
虽然限流器把 NAService 下游保护住了，但任务调度线程池的等待队列也到了上限，新任务只能拒绝。更麻烦的是，这些任务完成之后，回调请求也是同一时间集中发出，把业务方的回调服务也打满了。
这次之后我做了两个改进：第一，任务队列的长度可配置，超过 5000 任务时直接拒绝新任务并返回明确的错误码；第二，回调请求也走单独的限流渠道，按业务方维度的每秒 100 次限速，防止 "回调风暴"。
6.4 常见问题速查表
结合这个项目以及其他同类型服务踩过的坑，我整理了一份速查表，遇到问题直接对照排查：
| 现象 | 可能原因 | 排查建议 |
|---|---|---|
| 所有路径计算超时 | 图未加载完成或实例未就绪 | 检查健康检查和图构建日志 |
| 部分路线明显绕远 | 路网数据过期 | 对比 buildVersion，拉取新旧数据的差异 |
| 路径距离和线上不一致 | 新旧服务版本并行、数据版本不同 | 强制灰度期间新旧结果对比 |
| 任务状态一直 RUNNING | 子任务被限流卡住或线程池耗尽 | 看线程池活跃线程数和 NAService QPS |
| 回调一直失败 | 业务回调服务过载或恶意重试 | 检查回调限流配置并看重试日志 |
| 内存占用持续上涨 | 堆外缓存失效或图数据重复加载 | 检查图实例切换逻辑，确认只保留两份图实例 |
这里面每个问题都对应过一次线上或者测试环境的真实经历，不是什么"理论上的坑"，花在排查上的时间每一分钟都是实打实的成本。
7. 一些经验之谈
这个项目做下来，我最大的体会是：路径计算本身不是难点，难点在于把它做成一个线上稳定、可观测、可回滚、可扩容的服务。
如果现在让我重新做一次，有几件事我会在一开始就做（而不是等踩坑之后才补）：
第一，优先保证图数据的版本管理。数据版本和代码版本一样重要，每次改动都要留好记录，方便回溯对比。我后来为每份路网文件都生成了 MD5 和版本号，这个成本特别低，但排查问题时作用极大。
第二，异步任务服务一定要自带"熔断"机制。如果下游 NAService 持续超时，routetask 不能傻傻地继续重试，而应该降级到"临时失败"并快速返回给调用方，让业务方自己决定是重试还是走备用逻辑。
第三，发布不是最后一步。上线之后才是真正的开始，监控指标要提前设计好，演练要做，数据对比要做，这样才能知道线上到底稳不稳。
这个项目还有一个让我印象很深的小技巧：路径结果里加上buildVersion字段，这个字段在三次线上工单排查中帮我快速定位到了数据版本错误。强烈建议所有类似服务都把这个字段加上，成本几乎为零，收益远超预期。
如果你正在做类似的最短路径服务或者异步任务调度，欢迎参考这篇拆解，尤其是我提到的那些"看着不起眼但很容易忽略"的实现细节。整个系统的代码结构并不复杂，复杂的是在所有环节里都保持"可观测、可恢复"的工程意识。
