用于寻路的 mgo 优化

Question

我已经在 Go 中实现了一个 A* 算法来找到地图上两个坐标之间的路径。地图数据是使用 mgo 从 MongoDB 集合中获取的。

但是速度很慢。 1000 米路线大约需要 4 秒。我对算法的不同部分进行了计时，并得出结论，瓶颈在于从数据库中获取数据。或者更准确地说：在从二进制数据到 Go 理解的数据结构的转换中。

我尽量少做请求，多线程请求更快，有一定的帮助。但它并没有我希望的那么快。

看来我做的事情从根本上是错误的。任何建议都会有所帮助。

mongoDB 中的数据结构：（从 OSM 获取的节点）

{ "_id" : NumberLong(194637483),
  "lat" : 55.7079899, 
  "lon" : 13.3756414,
  "neighbours" : [ NumberLong(1566264689), NumberLong(1566264806) ] 
}

Go 中的数据结构

type Node struct {
    ID         int64   `bson:"_id" json:"id"`
    Lat        float64 `bson:"lat" json:"lat"`
    Lon        float64 `bson:"lon" json:"lon"`
    Neighbours []int64 `bson:"neighbours" json:"neighbours"`
}

获取一条数据的代码：

func addToBufferLong(buffer *WriteLockMap, session *mgo.Session, at, goal geo.Node, lowerLat, higherLat, lowerLon, higherLon float64) {
    c := session.DB("collectionName").C("nodes")
    query := c.Find(bson.M{"lat": bson.M{"$gt": lowerLat, "$lt": higherLat}, "lon": bson.M{"$gt": lowerLon, "$lt": higherLon}})

    var nodes []geo.Node
    query.All(&nodes)
    for _, node := range nodes {
        tmp := PathNode{0, node.DistanceTo(goal), 0, node}
        buffer.Lock()
        buffer.m[node.ID] = tmp
        buffer.Unlock()
    }
}

编辑：

多线程策略基于将我希望查询的区域分成 4 个不同的正方形，如果你愿意的话，也可以是象限，然后使用 addToBufferLong(...)

分别进行

编辑 2：

在其他堆栈溢出用户的帮助下，我设法显着缩短了执行时间。当前打印输出：

> time GOMAXPROCS=8 ./toystar

Starting A star
Thread A: 0.210783141s
Thread B: 0.380938949s
Thread C: 0.441447793s
Thread D: 0.507361847s

Total database fetch:  0.507543875 s
number of fetches:  1
Total A star:  0.826343287s

real    0m0.860s

主要区别在于多线程策略和使用 *mgo.Iter 而不是 query.All(&nodes)

Answer 1

根据可用的信息，这是我可以推断的：

您的机器似乎很慢，可能是嵌入式设备？

您调用的阶段db-fetch实际上并没有访问数据库。 c.Find(...) 唯一做的就是建立一个 *mgo.Query 值。该方法有 6 行长。这不应超过一毫秒。除非对数据库对象的内部会话状态存在争用，但情况似乎并非如此，因为您只使用了 4 个 goroutines。

瓶颈似乎是网络and/or反射

query.All(&nodes) 是在您的数据库上实际执行查询的位置。此外，此阶段分配它需要的节点切片，然后通过反射迭代地将 bson 解码为您的结构定义。

你可以尝试一件事：*mgo.iter

您可以使用 query.Iter() 而不是 query.All(...) 来获取 *mgo.Iter 并分批迭代您的数据集。随着时间的推移，这可能会通过更好地分配网络负载来提高性能。

使用地理空间索引，Mongo支持

参见the documentation。也许你已经在这样做了。如果不是，它可能会缩短查找时间。

递归地将您的象限拆分为子象限。

我认为这个很明显。分而治之，对吧？ :)

用于寻路的 mgo 优化

Optimization of mgo for pathfinding

go

mgo

编辑：

编辑 2：