作者简介：赵帅，软件工程师，就职于京东到家后台研发部，负责交易，售后、定位，api网关等系统。
引言
依托达达的高效配送和大量优秀零售合作伙伴，京东到家为消费者提供生鲜蔬果、日用百货、医药健康、鲜花蛋糕、个护美妆等海量商品 1 小时配送到家的极致服务体验，在整个服务过程中，京东到家基于LBS将消费者和线下商家联系到一起，进而促成交易为消费者提供便利，在这背后定位系统是如何为京东到家提供基础的定位能力呢？本文从技术角度介绍了京东到家定位系统的演进过程以及遇到的问题。
定位系统是做什么的？
业务简介
打开京东到家app，进入首页然后下拉，我们可以看到附近的店铺模块，如下图所示，
这个“附近”模块是典型的定位系统的应用，图中蓝色方框区域内容为当前坐标的POI名称，红色方框区域内容为当前坐标附近的门店信息，红色椭圆区域内容为当前坐标与门店之间的距离。
简单介绍下实现流程
- 第一步，打开app,手机可以通过内置的GPS模块获取当前位置的经纬度；
- 第二步，首页网关拿到当前位置的经纬度去请求地址系统，由地址系统访问相应的GIS服务得到POI信息并返回；
- 第三步，首页网关根据POI信息去请求定位系统，定位系统返回附近的门店列表以及距离信息；
- 第四步，首页网关补全门店的其他信息，比如评分、销量、运费等等信息，然后返回给app端展示；
大体流程如下图所示：
除了这个典型的应用外，到家的很多系统都依赖定位系统，比如多门店的搜索、运费的计算、提单时的超区校验、订单时效的计算……统计下来有50+的系统，这些系统几乎涵盖了用户的整个购物过程，仔细想想也是情理之中，到家的许多业务都是基于位置展开的，这也正是o2o电商和传统电商的一个重要区别。
核心职责
从众多的业务场景归纳下来，定位系统有两个核心职责，如下图所示
距离计算
计算两个坐标点的距离，多数为门店坐标与用户坐标之间的距离
定位门店
得到用户坐标附近的门店信息，门店的配送范围多种多样，用户看到的为配送范围覆盖用户坐标的门店
架构演进过程
依据职责不同定位系统划分为距离服务和定位服务，下面分开介绍这两个服务的演进过程。
距离服务
1、直线距离
这是所说的直线距离，实际为球面距离，我们认为地球是一个规则的球体，球面上的两个点，可以通过一系列的几何公式推导得出一个距离公式，将两个点的经纬度代入公式即可算出球面距离，这里就不展开了可自行搜索相关资料。那么我们为什么要升级，直线距离存在怎样的问题呢？如下图所示，
图中，起点到终点之间直线距离为390米，由于两点之间隔着河和桥，实际的步行距离达到了1766米，实际的步行距离为直线距离的四倍之多，类似这种情况下展示给用户直线距离，存在一定的不合理，影响用户的体验；另一方面，由于达达侧计算运费使用的是步行距离，到家侧使用直线距离，两边测算的距离不一致，无形中也给到家平台带来一定的损失，基于以上的原因，距离服务升级为使用步行距离。
2、步行距离
计算两点之间的步行距离，由于涉及到道路的规划、距离的测算等等元素，自己实现不现实，我们采用的是使用GIS服务计算步行距离，但距离服务作为到家的一个基础的服务，同步请求GIS服务显然不能满足我们对性能的要求，因此也催生了我们现在的方案，如下图所示
大体上分为两个阶段
- 阶段一，初始化阶段，初始化服务拉取近半年的订单信息，使用订单中的门店地址经纬度和用户收货地址经纬度结合GIS服务，计算出步行距离并初始化到距离信息库。
- 阶段二，自更新阶段，对于已下过订单的老用户请求步行距离时，可命中返回距离信息库的步行距离；而对于新用户，在距离信息库中不能命中，此时我们采用的是估算步行距离，使用直线距离乘以经验参数作为估算步行距离返回给用户，新用户继续下单，距离服务实时的监听订单系统的订单消息，进一步的丰富距离信息库，此用户再次请求距离时，距离服务即可命中库中的步行距离；随着用户的不断下单，距离服务实时订阅订单消息，实现了自动更新、自我丰富。
定位服务
定位服务的演进基本分为三个阶段，如下图所示
1、朴素匹配
到家发展初期，只有少数几个门店，一一列举出这些门店，判断配送范围是否覆盖用户坐标，从而匹配出覆盖门店，但随着门店的增加，此方案不再适用进入到下一阶段。
2、最小覆盖矩形
计算门店的配送范围的最小覆盖矩形，将所有门店的最小覆盖矩形坐标持久化到数据库中，通过sql语句方式筛选出覆盖用户坐标的门店，此方案支撑了到家一段时间的业务发展，随着用户量的增加，到家访问量也不断增长，通过数据库查询的方式逐渐不能满足我们对性能的要求，进而开始继续演化。
3、基于墨卡托投影倒排
墨卡托投影
墨卡托投影是正轴等角圆柱投影，假设一个与地轴方向一致的圆柱切或割于地球，按等角条件，将经纬网投影到圆柱面上，将圆柱面展为平面后，即得本投影。经过墨卡托投影后的经线是均匀分布的，纬线是垂直于经线的一组平行直线，也就是说经过投影以后我们把球面转化成了平面。
墨卡托坐标
由上述公式经度λ、纬度θ对应的墨卡托坐标就是(x\*R, y\*R)，其中R为地球半径。通过墨卡托投影，将坐标系转换为平面坐标系，由此，可以依照某种规则将我国所覆盖的区域分成若干大小相同的正方形区域进行标记编号,这些方格就是我们构建倒排索引的基础。
倒排索引
假设现在有三个门店s1、s2、s3,三个门店有不同形状的配送范围，每个方格都有自己的编号，如上图所示。
正排索引
构建出每个门店覆盖的方格列表，即正排索引
- s1: B2,C2,D2,B3,C3,D3,B4,C4,D4
- s2: C1,D1,C2,D2
- s3: C0,D0,E0,C1,D1,E1,D2
倒排索引
依赖正排索引，构建出方格对应的覆盖门店的列表，即倒排索引
- C0: s3
- C1: s2, s3
- D2: s1, s2, s3
- ……
构建倒排
门店配送范围的倒排索引构建过程如下：
定位过程
依赖于倒排索引，定位门店的流程如下：
定位服务架构
采用倒排索引方案实现定位服务，极大的提升了定位服务的性能，系统不再是业务发展的瓶颈，架构图如下所示：
- 服务节点：对外提供定位服务，本地内存存储全量倒排、门店基本信息，门店覆盖范围变更，节点需要重新构建对应的倒排信息，并且同步门店的基本信息。
- 后台web：处理门店变更消息，构建对应正排索引，产生门店变更任务供服务节点使用。
问题以及优化
架构趋于稳定，但随着业务的发展，还是出现了一些新的问题，针对这些问题，我们也做了进一步的优化。
新的问题
- 定位精准度不足，如下图所示，虽然门店的配送范围覆盖了方格，但是红色标记区域实际不在门店的配送范围内，实际的运营过程中出现了不少类似的问题，给商家和用户造成了困扰。
