共计 4454 个字符，预计需要花费 12 分钟才能阅读完成。
背景
逆天文编码（将经纬度转换为具体结构化的地址）调用目前是整个地图服务调用量最大的接口，业务主流程多个节点依赖逆天文服务，接口不可用会间接阻塞订单。目前高峰期高德逆天文接口的 QPS（Queries Per Second 每秒查问率）常常会几倍的超掉，超限报错的申请会通过哈啰地图平台的 LBS（Location Based Services 基于地位的服务）兜底返回数据。
目前的逆天文调用量日均在 2 - 3 亿左右远超现有业务体量，面对业务在业务冲单时预估的几倍调用量增长与供应商较昂扬的提额价格，虽有 LBS 兜底但高峰期大量流量打到 LBS 也会极大减少服务压力，可能引发连锁反应，在冲单前优化调用量的问题保障接口稳定性火烧眉毛。
整体方案设计
首先是要明确每个节点的调用量是多少，针对调用量头部的节点咱们想通过 code review 和与业务同学沟通调用节点的业务诉求，看能不能间接删除或通过其余形式进行优化，对于不好优化的，咱们想通过缓存机制来缩小一部分调用。
信息补充
目前报表只能从业务维度来拆分，并不能晓得具体每个节点的调用量是多少，是哪个节点的调用量过大。所以第一步就是埋点补充调用节点参数。粗疏的埋点是我认为所有优化的第一步，它能明确线上到底是什么样的，能力更好的针对性优化，并在后续的优化回收，监控等过程中提供数据撑持。拆分后报表示意如下：
一一击破
基于第一步的拆分，咱们曾经能晓得调用量较高的节点都是哪些，针对这些节点咱们将联合业务应用诉求与代码细化场景，寻找问题和优化空间进行了一一优化。这步优化总结下来有两局部：
以后节点并不需要调用
因信息不对称导致的业务场景使用不当，如：
1. 业务页面有监控到地位更新就用以后地位触发逆天文的逻辑，理论高德定位组件外部会触发一次以后地位的逆天文调用并返回给业务，业务并不需要额定调用。
2. 地图缩放时中心点并没发生变化，不须要申请逆天文。
优化调用节点缩小调用
联合业务应用场景上下文，尽可能的缩小调用，如：
1. 业务有一个性能会检测用户如果间隔以后地图中心点超过 50m，就把用户以后地位变成地图核心地位并会触发逆天文的申请，但性能上线后因为在 APP 首页失效无奈开释导致整个 APP 生命周期始终在触发地位追随性能造成不必要的调用，相似问题的解决办法是对性能限度作用域，感知页面与 APP 的生命周期，如 APP 不在前台或不在以后页面就敞开性能。
2.POI（Point Of Interest 趣味点）搜寻后会触发的上车点检索并进行逆天文的调用，上车点吸附胜利时须要的逆天文数据 POI 数据中均蕴含，上车点吸附失败时逻辑是应用 POI 搜寻的数据也不须要逆天文调用，所以咱们省去了 POI 搜寻后触发的上车点检索后的逆天文调用，均用 POI 数据填充逆天文的数据。
阶段产出
这部分优化完结后咱们 APP 调用量级从日均 2 - 3 亿降到了 3 - 4 千万左右。
应用缓存
咱们心愿能通过缓存来进步数据的使用率，用内存 + 磁盘缓存的形式长久化缓存数据以进步命中率。
应用逆天文接口申请的参数（经纬度 + 申请半径）生成 key，将申请后果存入到内存缓存 + 磁盘缓存中，获取缓存时先从内存中查找，没有再从磁盘中查找。
经纬度的聚合问题
因为定位自身就会因为各种起因产生偏差（基站定位？信号遮挡？）或者用户在短距离内挪动，间接以经纬度生成 key 会重大影响缓存命中率，咱们心愿能聚合肯定范畴内的经纬度，这样能够无效晋升缓存命中率。
GeoHash 算法
GeoHash 是一种地址编码方法，他可能把二维的空间经纬度数据编码成一个字符串。
算法思维
GeoHash 示意的并不是一个点，而是一个矩形区域，编码越长，示意的范畴越小，地位也越准确，GeoHash 编码的前缀能够示意更大的区域。例如 wx4g0ec1，它的前缀 wx4g0e 示意蕴含编码 wx4g0ec1 在内的更大范畴。
算法原理
经度范畴是东经 180 到西经 180，纬度范畴是南纬 90 到北纬 90，咱们设定西经为负，南纬为负，所以地球上的经度范畴就是[-180，180]，纬度范畴就是[-90，90]。如果以本初子午线、赤道为界，地球能够分成 4 个局部。
如果纬度范畴 [-90°, 0°) 用二进制 0 代表，（0°, 90°]用二进制 1 代表，经度范畴 [-180°, 0°) 用二进制 0 代表，（0°, 180°]用二进制 1 代表，那么地球能够分成如下 4 个局部：
会生成相似于 Z 的曲线，如果在小块范畴内递归对半划分呢？
当咱们递归的将各个块分解成更小的子块时，编码的程序是自类似的（分形），每一个子快也造成 Z 曲线，这种类型的曲线被称为 Peano 空间填充曲线，Peano 空间填充曲线有突变性问题（有些编码相邻但间隔却相差很远，比方 0111 与 1000，编码是相邻的，但间隔相差很大）和临界问题（与雷同 GeoHash 编码的点的间隔有可能大于临界不同 GeoHash 编码的点的间隔 如上图红点蓝点的间隔是远大于红点与绿点之间的间隔），评估后对于咱们的应用场景可承受。
编码长度就是对方块的划分次数。执行逻辑：
- 依据设定的编码长度对以后经纬度别离进行划分，失去两组二进制串（10101、01010）后以偶数位放经度，奇数位放纬度的形式合并成一个二进制串（1001100110）
- 将二进制串划分每 5 位一组，有余 5 位补 0（10011、00110）
- 将各组的 5 位二进制串转成十进制，5bits 对应着 10 进制的数值为 0 -31（19、6）
- 用 0 -9、b-z（去掉 a、i、l、o）这 32 个字母进行 Base32 编码，即对照下标将其转换为字符串（m、6）
- 最初拼在一起失去的字符串就是 GeoHash 编码（m6）
编码长度对应的偏差范畴
目前缓存设置的编码长度为 GeoHash9（5m 左右误差）。
缓存淘汰机制
采纳业界支流的 LRU 算法策略（Least Recently Used，即最近起码应用，是一种罕用的页面置换算法，抉择最近最久未应用的页面予以淘汰）。
算法思维
如果数据最近被拜访过，那么未来被拜访的几率也更高。原理解析新数据插入到链表头部；每当缓存命中（即缓存数据被拜访），则将数据移到链表头部；当链表满的时候，将链表尾部的数据抛弃。
其余淘汰机制
因为高德逆天文数据偶然也会有 badcase 须要高德更新数据 fix，咱们心愿数据除了 LRU 被淘汰以外还能有其余维度的机制来更新数据：
- 工夫维度：咱们限度只应用 2 天内的数据，如超过则淘汰数据，从新申请并缓存
- 拜访次数维度：咱们限度数据应用 10 次后，会被动淘汰数据，从新申请并缓存
阶段产出
冲单当日数据回收缓存命中占比 iOS 为 26% 安卓为 29.4%。
缓存算法优化
缓存命中剖析
目前日均的缓存命中率在 25% 左右，跟咱们的预期相比还是会低一些，起因剖析如下：目前因为防止占用大量内存（依据左近 POI 多少不同一条数据在 2 -8kb 之间）造成 OOM 问题（Out Of Mana 法力耗尽 Out Of Memory 内存溢出 占用内存过大会被零碎强制杀死 造成闪退），规定了缓存最大数量为 50 个，那是否调大缓存个数就能进步命中率呢？比方进步到 200-300 个，咱们认为也不能晋升太高，而且会减少 OOM 的危险。从咱们的实现与场景剖析下：
1.LRU 算法剖析
长处：LRU 算法实现简略，并且在大量频繁拜访热点页面时非常高效。
毛病：因为 LRU 的机制，遇到偶发性或周期性的批量操作会导致 LRU 的命中率急剧下降，缓存净化状况比较严重。
2. 联合场景剖析
依据咱们的出行场景，咱们心愿命中缓存的数据分为两局部：一是短时间内的反复申请，这部分目前曾经能够满足；二是依据用户的应用习惯缓存下家或公司学校等罕用地左近的逆地理信息，这部分权重较高比拟容易命中缓存，但用户在行程过程中会有大量数据写入造成“缓存净化”。所以，咱们须要一种减少权重机制的缓存淘汰算法来解决行程过程中的缓存净化。
LRU- K 算法
算法思维
LRU- K 中的 K，其实是指最近拜访页面的次数，LRU 算法其实就是 LRU-1，然而因为仅拜访 1 次就能代替他人，可能会造成“缓存净化”的问题，因而提出了 LRU- K 的概念，其核心思想就是将拜访一次就能代替的“1”晋升为 ”K”。
原理解析
LRU- K 算法须要保护两个队列：历史队列和缓存队列。
历史队列保留着缓存的对象（内存中），当对象拜访次数达到了 K 次，该对象出栈，并保留至缓存队列；若尚未达到 K 次则持续保留，直至历史队列也满了，那就依据肯定的缓存策略 (FIFO、LRU、LFU) 进行淘汰。
缓存队列则是保留曾经拜访 K 次的对象，当该队列满了之后，则淘汰最初一个对象，也就是第 K 次访问间隔当初最久的那个对象。
对应到咱们的实现里就是历史队列的数据获取超过 K 次后才会退出到内存缓存 + 磁盘缓存进行长久化保留，而历史队列自身也在充当内存缓存的角色不会有反复的存储, 且因为有了历史队列进行权重过滤，会大大减少数据库写入，缩小整体性能耗费。下图为选用的磁盘缓存（YYCache）的读写性能图。
这部分正在进行中，预计能进步缓存 10-20% 的命中率。
容灾计划
如果在上述优化后还呈现高德 QPS 超限降级到自研实现且自研实现 QPS 也超限的状况，此时持续调用也没有任何意义了，咱们心愿能通过升高本身的申请的形式来加重以后服务器的压力（是一种较自私的计划）。
满足上述条件后会触发端上的容灾策略，会去以 GeoHash7（80m 左右误差）生成 key 获取缓存，如获取不到则进行服务调用 2s 间接报错以加重以后服务器的压力。
防裂化
接入到 MapService（地图团队保护的新组建）后，会有独立的报表与 LBS 的流量监控，对调用量超过原 QPS 的接入方会钉钉收回告警告诉。
并可通过 LBSAdmin 平台（LBS 治理平台）对流量异样的节点进行动静降级，无需发版就能复原线上异样节点对其余业务的影响。
整体流程如下：
收益
地图平台挪动端通过对数据起源的细化、与业务同学深刻交换剖析、正当应用算法能力、与地图后端能力深度联合一直进行优化降级，残缺的撑持了公司冲单的流动，日均调用从 2 - 3 亿降到了 2 - 3 千万左右。
总结
最初总结出咱们认为在任何优化中都很重要的点：
1. 放弃敬畏：优化前要十分明确这段代码的作用与影响面，并且每个优化都要可灰度，可复原（有些代码怎么看都是多余的，删除了看似也没啥影响，一公布就呈现线上事变）操之过急不要事与愿违。
2. 白盒优化：还原线上运行的实在样貌，要明确晓得要优化哪里，优化后的实在成果，不能只靠 YY。
3. 做久远建设：久远建设会成为后续继续优化打下牢固的根底。
4. 防裂化：不要漠视防裂化建设，否则前面将变成“一年一度整活大赛”。后续咱们将会持续针对调用量、稳定性、业务隔离、多数据源等方向做更多乏味的尝试。
作者简介：
陈东冉、刘大白、任赛龙等，均来自哈啰人工智能与地图团队 - 地图平台。
招聘信息：
哈啰地图团队诚招高级、资深工程师，Base 上海、杭州。咱们致力于为哈啰提供高性能、高可用、高体验的端到端出行解决方案服务，涵盖简单架构设计、深度性能优化、算法撑持赋能等技术畛域，端侧地图解决方案，欢送有趣味的同学投送简历至：https://careers.hellobike.com/。
