Valhalla路径引擎中零长度边导致的无限循环问题分析

问题背景

Valhalla是一款开源的高性能路径规划引擎，广泛应用于地理位置服务中。在使用Valhalla生成等时线(isochrone)时，开发团队发现了一个严重的性能问题：当处理某些特定位置时，服务会陷入无限循环，导致整个服务器无响应。

问题现象

开发团队在对160,000个位置生成等时线时，发现其中2个位置会导致API无响应。更严重的是，重复尝试会逐渐锁定每个处理线程，最终使整个服务器完全无法响应。

技术分析

通过调试发现，问题出现在bresenham_line()函数中的无限循环。深入分析后，发现根本原因是：

1. 在OriginEdgeShape()函数中，当计算边(edge)长度时返回了0.0值
2. 这导致了后续的除法运算产生了NaN(非数字)结果
3. NaN值在后续处理中传播，最终导致bresenham_line()函数陷入无限循环

具体来说，问题出现在以下处理流程中：

1. 路径引擎尝试计算某条边的形状
2. 发现该边长度为0(可能由于两个节点坐标完全相同)
3. 在计算插值点时，由于除零操作产生了NaN
4. NaN值传递到Bresenham画线算法中，导致循环条件永远无法满足

解决方案

Valhalla核心开发团队提出了两种解决方案思路：

1. 数据预处理方案：在图形构建阶段检测并处理零长度边。但这种方法实现复杂，可能引入其他问题。

2. 算法防御方案：在关键函数中添加边界条件检查。这是更简单可靠的方案，具体实现包括：

   • 在OriginEdgeShape()函数开始处检查零长度情况
   • 处理中间形状点相同的情况
   • 跳过零长度线段继续处理

核心开发团队更倾向于第二种方案，因为它更安全且易于实现。示例修复代码如下：

template <typename PrecisionT>
std::vector<GeoPoint<PrecisionT>> OriginEdgeShape(const std::vector<GeoPoint<PrecisionT>>& pts,
                                                 double distance_along) {
  // 处理零长度情况
  if (distance_along == 0) {
    return {pts.back(), pts.back()};
  }
  
  double suffix_len = 0;
  for (auto from = std::next(pts.rbegin()), to = pts.rbegin(); from != pts.rend(); ++from, ++to) {
    PrecisionT len = from->Distance(*to);
    suffix_len += len;
    
    // 跳过零长度线段
    if (len == 0)
      continue;
      
    // 计算插值点
    if (suffix_len >= distance_along) {
      auto interpolated = from->PointAlongSegment(*to, (suffix_len - distance_along) / len);
      std::vector<GeoPoint<PrecisionT>> res(pts.rbegin(), from);
      res.push_back(interpolated);
      std::reverse(res.begin(), res.end());
      return res;
    }
  }
  return pts;
}

经验总结

这个案例为我们提供了几个重要的工程实践启示：

1. 边界条件处理：算法实现必须考虑所有可能的边界条件，包括零长度、NaN等特殊情况。

2. 防御性编程：关键路径上的函数应该具备自我防御能力，防止错误条件传播。

3. 数值稳定性：涉及浮点运算和几何计算的代码需要特别注意数值稳定性问题。

4. 资源管理：长时间运行的算法应该考虑加入超时或进度检查机制，避免无限循环。

对于使用Valhalla的开发者，建议在遇到类似服务无响应问题时，首先检查是否遇到了特殊几何条件，并考虑升级到包含此修复的版本。