最短路径服务发布实战：NAService与routetask调用全拆解

做接口服务最怕的就是看着简单一上线就现原形。最短路径这种需求单机算是一回事做成服务、接上任务调度、扛住业务流量又是另一回事。今天这篇就把我做的这个发布最短路径 NAService 与 routetask 调用服务的项目完整拆一遍从需求到最后发布上线全部过程、踩坑和取舍都写出来希望能帮到正准备自己搞路径服务的人。这个项目本质上要解决三件事第一把最短路径计算从业务代码里抽出来做成独立的服务NAService第二路径规划不能所有请求都同步算耗时长的要走异步任务routetask第三服务要能发布上线而且能稳定运行。围绕这三件事我会讲讲整个系统是怎么设计的、核心怎么实现的、发布时验证了什么以及我踩过的那些坑。1. 需求背景与服务拆分思路1.1 为什么需要做一个独立的路径服务我当时所在的业务线是做同城配送调度的调度系统里有一个很核心的需求给每一笔订单计算骑手从当前位置到取货点、再到送达点的最短路径。一开始这个逻辑直接写在调度服务里用的是一张简单的静态路网表数据量几千个节点的时候没问题但业务一旦铺开节点到了几万个、路线组合到了百万级直接写在业务代码里的路径计算就开始拖后腿。最明显的问题是调度主服务既要管订单状态机、又要管骑手分配、还要管超时重试本来就忙路径计算又是一个高 CPU 消耗的操作两者挤在一起互相拖累。经常出现的情况是高峰期订单量上来路径计算请求一多调度主服务的接口延迟直接翻倍。改造的思路很明确把最短路径计算从业务服务里拆出去做成一个独立部署、独立扩容、独立监控的服务。拆出来之后有几个直接的好处第一路径计算的负载不会影响到订单主流程第二路径计算服务可以自己水平扩缩容扛大促流量第三这个能力以后给其他业务线比如新开的跑腿服务、预估送达时间服务复用不需要再写一遍。1.2 NAService 的职责边界NAService 这个名字看起来有点抽象其实内部的含义是 Navigation Algorithm Service。它接收起点和终点的坐标经纬度在准备好的路网图上计算最短路径返回给调用方一条由有序坐标点组成的路线。在设计服务边界的时候我划得很清楚NAService 只做三件事接收路径计算请求起点、终点、可选途经点执行最短路径算法输出有序坐标序列暴露服务运行状态、耗时指标、缓存命中率等监控数据而所有跟业务状态订单是否超时、骑手是否接单、存储状态路网数据从哪里来相关的东西NAService 一概不管。路网数据由另一个离线数据管道统一构建好定时同步给 NAServiceNAService 只负责加载。这里有个在系统设计里经常被忽略的点服务边界不是越细越好而是要让每个服务的职责是可理解、可测试、可扩展的。把路网数据更新也放进 NAService 就会让事情复杂化因为数据构建和在线查询是两个完全不同的节奏和资源模型。1.3 routetask 调用服务的定位routetask 是独立于 NAService 的另一层服务。它解决的问题是不是所有路径计算都需要同步给调用方。业务场景里有一类需求用户下单时系统需要提前计算骑手可能用到的所有路径用于预估时间、调度预排、距离计费等。这类计算不要求结果在一两秒内返回但量很大而且可以慢慢算。如果所有请求都同步压给 NAServiceNAService 的计算线程会被占满那些真正需要实时响应的高优请求反而会被拖慢。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) 访问内存占用固定更新需全量加载高并发路径计算首选我最终选了进程内邻接表。所谓邻接表就是把每个节点作为 keyvalue 是它的所有邻居节点和对应边权。在 Java/C 里实现时要尽量避免用大量小对象比如用数组存边、用 int 存数组下标否则 GC 压力会很大。我单独写了一个图构建模块在加载阶段把解出来的边数据存成 int 数组节点和边的关联关系用连续内存段表示查询的时候直接用下标访问。这里推荐一个我总结出来的实践不要用 MapInteger, 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 PriorityQueueNodeRecord 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_statusPENDING/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 检查令牌如果拿不到令牌就进入一个轻量 sleep5ms然后重试拿令牌。这样做的直接效果是即使业务方一次性提交了 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 分钟检查一次是否有新版数据文件有的话就在后台加载新实例加载完成后原子切换流量。这一套热更新上线后路网数据基本能保持 T1 的新鲜度绕远路的工单量大幅下降。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字段这个字段在三次线上工单排查中帮我快速定位到了数据版本错误。强烈建议所有类似服务都把这个字段加上成本几乎为零收益远超预期。如果你正在做类似的最短路径服务或者异步任务调度欢迎参考这篇拆解尤其是我提到的那些看着不起眼但很容易忽略的实现细节。整个系统的代码结构并不复杂复杂的是在所有环节里都保持可观测、可恢复的工程意识。