Go语言打车软件后端系统算法与实践

 
社区导读：各位，本篇为大家介绍如何构建一个打车软件，使用Go语言和相关后端算法。类似于滴滴或Uber，包括在内存中保存出租车的行进动态，如何以动画形式将行进路线显示、路径最优等算法。

概述

这个故事的起源是在2015年，我的设计课题就是开发一款移动端软件，叫做“移动打车应用”。在这款应用中，可以实时显示出租车/或共享汽车的行驶和移动状态。
类似于下面的界面：

我想让用户在手机屏上实时监测到汽车的行驶动态。但是会遇到一些挑战：
第一缺乏数据。我们需要15秒钟就要取得汽车的新的位置。我们不能只缩减更新时间间隔。
因为当司机端程序上行数据时，同时需要获取当前订单和下一个订单，另外还有报警功能（给司机使用的一个SOS按钮，当司机有难按下此按钮时，其它的司机会收到后来帮助他）。
另外，如果我们只是减少更新间隔，后端系统承载的流量会变大。
到底有多大，我心里也没底。
于是我开始做一些尝试。

第一步

第一步开始尝试，我做了如下处理：
1、处理请求，保存汽车的坐标
2、创建另一个请求并为汽车创新动画
大家在Uber、滴滴、易到之类打车软件所看到的，汽车画面是动态的。
因为我们取得的机动车坐标比较粗糙，时间也比较长，泡车们可以跑在田野，森林或者开在河里，甚至开在小区的楼顶，想象一下这是一群什么神奇的车？如下画面：

我开始为此问题寻找解决方案。我找到并使用一款被称为开放街景路线机器OSRM(OpenStreetMap Routering Machine)的工具来规划路线，以改善我们的算法。这里，我们仍然使用同样的时间间隔设置。
如下步骤：
1、发起请求
2、获取坐标
3、把坐标发送到服务器
4、通过OSRM规划路线
5、返回数据给手机客户端
通过上面增加的路线规划体系，现在似乎可以工作了。
但是我们又面临着单向道路的问题：

比如，一位司机和车是停在红点中的十字路口。因为设备位置的精确性不够准确，数据标记在十字路口的对面或者旁边。客户端获取到地址信息坐标，发送给服务器后端。接着OSRM开始规划一个看似完整无暇的线路出来，再返回给客户端。
因为汽车一直在移动，且移动速度很快，这个路线规则的起点位置就不正确，所以造成的结果也肯定是错误的。
这个场景和在中国使用百度、高德地图很相似，于是这位老司机被规划的线路整蒙圈，结果可能绕了远或走错了路。
我们用较简单的方式来解决此问题：检查两点之间的最短距离，并且不建立距离小于20米的线路规划。使用这样的算法，经过几天测试后，我们决定发布更新我们的应用，以获取用户的反馈。
接着，我进行第二次的产品迭代。如下：
1、车费交易的结算。放在司机客户端完成，这样避免无用的请求发送，可节约更多服务端资源。此外，在安全、完整性方面考虑，我们要会将交易数据复制并保存。
2、从使用场景上看，当用户打开客户端查看车辆信息后，因为15秒的地址上报时间原因，他需要等15秒后才能看到车的移动。
3、另外，在司机端的GPS模块也存在诸多问题，可能和司机的手机也有一定关系。
4、最后，我们想在屏幕上对车的移动加入动画渲染效果。
我们还想解决如下之问题：
1、从司机端收集更多的数据
2、在屏幕上显示车移动的动画轨迹
3、如何节省手机端流量
4、能够每秒收集一次数据
我们再谈谈关于节省带宽流量的事儿。在白俄罗斯，出租车价格很低廉，就像我们坐公交车一样便宜。比如，从某城市的东边跑到西边大概也就需要2欧元，大概合14.5元人民币，这和中国的二三线城市的出租车价格差不多。
但是和中国一样，手机的流量费用也不低，如果我们每秒节约100字节，那我们就为公司节省大概20000美金以上。

需要跟踪的数据

1、司机（车）的位置（经度，纬度）
2、司机的会话信息。如司机登录后，后端给到司机端的sessionid
3、订单记录，包括订单ID（Order Id）和车费（Trip Cost）
我们说过，要在每次反馈的信息上小于100字节。那么，我们就在传输协议上来找寻求解决方案。
TCP/IP协议栈的几个协议：
1、HTTP
2、Web Socket
3、TCP
4、UDP
从性能、速度等综合因素考量，我们决定选择UDP。原因如下：
1、我们只发送数据报文
2、不需确认是否送达
3、极精简
4、能够保存更多数据
5、只有20个字节开销
6、在我们国家没有阻挡该协议
数据格式采用序列化方式。我们从以下格式中选择：
1、JSON
2、MsgPack
3、ProtoBuff
我们选了ProtoBuff，因为它对小数据非常有效。如之对比图：
　　
从上面图中，你可以看到后两种格式的长度是ProtoBuff的2倍。
那么我们的数据包有多少数据？
数据一共仅有42个字节
+ 20个字节的IP头
=每次跟踪仅有62个字节。
当我们获得到数据，需要存储它，对吗？

需要存储的数据

数据需要持久化存储。我们要保存哪些数据：
1、司机同志的会话信息（Session Id）
2、车辆的车牌号
3、订单号（Order Id）和计费记录
4、每次查询后的最后位置
5、第N次的最后位置以规划路线

用什么数据库系统保存

1、使用Perconna数据库做持久化存储
2、使用了Redis做为缓存
3、使用ElasticSearch做为地理编码查询
如上所述，比如有600个司机同时在线，在这些地方搜索数据并不方便，因此需要geo地理信息索引。
我们观察到有两个地理索引算法：
1、KD树
2、R树
我们对地理索引的需求：
1、我们需要搜索N个最近的点
2、我们需要一个平衡树，以便在最差的情况下提供最佳的搜索
KD树
关于KD树，请看下图：

我们评估了KD树，因为它不是一个平衡树，并不合适我们的需求。虽然可以在KD树上实现k-nearest邻居算法。但是我们并不需要再重复造一个轮子，因为R树已解决了这个问题。
如下图：

如你所见，它们长得是这个样子的。这样我们就可以执行搜索N个最近点，且它是一个平衡树。因此我们选择了它。
你可以点击查看详情找到用Go语言实现的源码包。
以下是我们的存储结构：
1、我们将所有数据存储在内存中
2、使用R-tree来搜索最近的司机
3、因此，我们用了两张检索图上，分别对应车牌号搜索与按会话Session进行搜索。

完整的算法

以下介绍后端使用的最终算法。
1、使用UDP协议取得数据
2、尝试从持久化存储中取得司机数据
3、如果存储不存在，则从Redis缓存获取
4、检查并验证数据的完整性与有效性
5、将司机数据持久化存储
6、如果不存在，则初始化LRU
7、更新 R-tree
HTTP接口与结点
我们实现了以下结点并集成到系统中：
1、返回最近的司机
2、通过车牌号或会话（session id）在存储中删除司机
3、获取行程信息
4、获取司机信息

小结

我们实现的打车软件界面如下：

总结一下打车软件后端的几点：
1、使用UDP+ProtoBuff精简数据来节省带宽
2、使用内存数据库存储
3、使用R-tree（R树）来获取最近的司机
4、使用LRU 缓存用来存储最后的N个位置
5、使用OSRM来匹配地图以及定制化行进线路
相关样例，可以到以下地址获取：
https://github.com/maddevsio/openfreecabs
代码看似简单，但本篇文章的大多数功能在里面均已实现。

　　作者：21CTO社区 综合编译
　　说明：若转载请注明出处。技术原创类文章请注册21CTO网站发表
　　来源：https://blog.maddevs.io/how-we … yp5od