Geohash

GeoHash(1)-实践篇兄弟篇：GeoHash(2)-实现篇 一、前言最近有个需要，要计算出客户坐标左近5公里的所有门店，并依照步行间隔排序。 最间接的办法就是遍历该城市下的所有门店，然而该办法显著不可取，因为在门店数量微小，且还须要计算步行间隔并排序的状况下，工夫简单度过高。 忽然想到当年做图像遇见一个问题：给定一个视频中间断的三千帧，然而曾经乱序，通知你第一帧，将这三千帧进行排序。遍历图像的所有像素点同样不可取，过后的解决方案是利用感知哈希计算出所有图像的指纹，接着利用明氏间隔计算间隔第一张最近的图像作为第二张，而后计算间隔第二张最近的作为第三张，以此类推。 同样，必定也有哈希办法可将地理位置转换成某种编码，并且编码可用于天文计算。它就是 GeoHash。 二、相干常识进入注释之前，先一起回顾一下初中天文： 本初子午线以西为西经，分十二区，每区15度共180度；以东为东经，同样分十二区，共180度。 赤道以北为北纬，共90度；以南为南纬，同样90度。 那么在计算机中，坐标示意为： 西经为正数，东经为负数，因而经度取值[-180, 180]。 北纬为负数，南纬为正数，因而纬度取值[-90, 90]。 咱们晓得赤道长约四万公里，因而经度上每度约等于111公里。地球实际上是个不规则球体，但为了简便计算，咱们假如把纬度上每度约等于222公里。 三、初识 GeoHash1. 计算二进制编码首先计算二进制编码，经度上以[-180, 180]开始，纬度以[-90, 90]开始，每次将区间进行二分，若输出坐标小于两头值则编码为0，下次区间取左半区间；若大于则编码为1，下次区间取右半区间。以此类推，编码越长，越靠近坐标值，进而越准确。 以 118°04′04, 24°26′46 为例，首先计算经度的编码： 编码长度区间两头值编码阐明精度（千米）1[-180, 180]01118°04′04 大于 0°，因而编码1，取右区间199802[0, 180]901118°04′04 大于 90°99903[90, 180]1350118°04′04 小于 135°，因而编码0，取左区间49954[90, 135]112.51 2497.55[112.5, 135]123.750 1248.756[112.5, 123.75]118.1250 624.375‬7[112.5, 118.125]115.31251 312.1888[115.3125, 118.125]116.71875‬1 156.0949[116.71875‬, 118.125]117.4218751 78.047‬10[117.421875, 118.125]117.7734375‬1 39.024N....... ...同样情理，计算纬度得编码： 编码长度区间两头值编码阐明精度（千米）1[-90, 90]0124°26′46 大于 0°，因而编码1，取右区间199802[0, 90]45024°26′46 小于 45°，因而编码0，取左区间99903[0, 45]22.51 49954[22.5, 45]33.750 2497.55[22.5, 33.75]28.1250 1248.756[22.5, 28.125]25.31250 624.375‬7[22.5, 25.3125]23.9061 312.1888[23.906, 25.3125]24.6090 156.0949[23.906, 24.609]24.2575‬1 78.047‬10[24.2575‬, 24.609]24.4330 39.024N....... ...综上，假如咱们只取十位编码，经度上失去得编码为 1101001111，纬度上编码为 1010001010。 ...

一、业务场景分析基本的业务需求可分为两大部分，第一部分是手机端间隔一定时间上报一次位置信息，第二部分是后台系统可以实时看看手机设备当前所在的位置，并绘制轨迹。总之就是用户安装了此应用，就相当于给自己装上了一个跟踪器，所到之处，都将有所记录。我们先来保守计算一组数据，假定用户基数为10万，每隔5秒上报一次位置信息，而这5秒期间，地图SDK大概会给出2次定位数据，由此得出，一次上报的瞬时峰值大概是20万条数据，一天将会达到300多万的数据。这样的QPS已经算是很高了，当然，绝大多数情况下是不会触顶的。另外一方面，后台系统在查询的时候，也面临着一个巨大的挑战：如何从海量的数据中找寻符合条件的那一部分？查询的条件无非是围绕三个维度展开的：时间、对象和区域。类似“查询某块地理位置栅栏内的所有用户在一段时间内的位置信息”，这就是一个典型的查询业务需求，涵盖了三个维度的条件。当然，还有一些距离的测算和排序的需求也是在所难免的。综上所述，我们要解决两个难点：1、上报用户的实时位置信息； 2、处理海量数据的读写请求。以上两个难点是任何LBS应用不得不攻克的，这是支撑业务发展的关键点。二、抽象的系统架构我们可以将整个请求链接进行拆解，分别用对应的策略解决这部分的难题：1、客户端收集数据。这一部分有四个基本要求：准实时，不丢数据，低功耗，高效率。2、网关限流。主要为了避免涌入大量无效请求，消耗系统资源，拖跨服务器。3、负载均衡。为了应对不断增长的访问量，服务实例必须支持横向扩展，多个实例之间按照一定的策略进行负载均衡。4、异步化读写数据。需要借助中间件，起到削峰的作用，这一部分的设计会重点阐述。5、数据存储层高可用。采集的数据不要求强一致性，依据CAP理论，满足AP两个条件即可。解决办法通常是集群化，避免单点故障，进而实现程序上的读写分离策略。三、技术选型接下来是针对上述五大部分在技术实现上的考量。目前客户端是苹果机和安卓机，未来很可能会接入友商的车载OS。在网络状况良好的时候，可以实时采集，实时上报，倘若网络状况不好，也不会丢数据，采用MMAP实现本地缓冲区。当然，为了上报效率，综合考虑还是按批次上传，过于频繁的上报也会致使耗电量攀升。网关限流和负载均衡交给了nginx，学习和开发成本低，重要的是效果很好，并且能够达到服务横向扩展的目的。我们使用了nginx基于ip地址的限流策略，同一个ip在1秒钟内最多允许3个请求，burst=5，为了应对突然的流量的爆发，还有一个nodelay参数，我们选择不加了，意味着请求队列和缓冲区都被塞满之后，直接返回503错误码，不再等待了。目前，是1个master进程，5个worker子进程，此外，超时时间、最大连接数以及缓冲区的设置值得斟酌，服务器性能好的话，可以设置得高一些。负载均衡的策略不是基于权重的设置，而是使用的最少连接 (least_conn)，因为在我看来，每个服务实例都是可以被同等对待的，哪台空闲，就优先请求哪台。如果非要在此基础上设置一个weight，那就把性能高的服务器设置成较高的权重。为了应对大量的位置上报请求，必然需要引入消息队列。因为技术团队一直在使用RabbitMQ，并且一番压测后，表现依然坚挺，所以成为了我们的不二选择。此外，为了减轻存储层的压力，在数据落盘前有一个缓冲机制，是典型的主从双Buffer缓冲池，避免与存储层频繁交互，占用过多connection，提高了存储层的工作效率，但是缓冲池Flush的时候，会带来一次“IO尖刺”，可以调整缓冲池的Threshold，把“IO尖刺”控制在一个合理的范围内。最后，也是最引人关注的是存储层的选型。我们面临的选择比较多，我们预研了4种有可能的方案：MySQL，Redis，PostGIS，MongoDB。MySQL的方案有两条路可走，第一是使用纯SQL进行计算，很明显这条路子受限于数据量，随着数据量的增大，计算量剧增，系统性能急剧下降。第二是使用MySQL的Spatial Indexes，但是这类空间索引是MySQL5.7版本引入的，不巧的是，我们用的是阿里云RDS，MySQL版本是5.6.16，不得不放弃MySQL的方案。基于Redis GeoHash的方案，在性能方面是没任何问题的，但是有一个重大的缺憾，就是非常受限于距离查询，而无法方便的匹配另外的附加属性，也就是上述三维需求（时间、对象、区域）中，只能满足区域查询的需求，若想进一步过滤，还需要借助其他的存储技术。留下来的PostGIS和MongoDB是现在比较通用的解决方案。PostGIS的专业性很高，是地图服务商的首选，对OGC的标准支持得非常全面，提供的函数库也十分丰富。当然，MongoDB也不赖，3.0版本引入的WiredTiger存储引擎，给MongoDB增色了不少，性能和并发控制都有了较大幅度的提升。单就LBS应用来说，两者都可以很好的满足各方面的业务需求，性能也不是我们首要考虑的因素，因为两者的可扩展性都很强，不容易触及瓶颈。最后我们选择了MongoDB，是因为技术团队对此接受程度更高，MongoDB本来就是公司技术栈中的一员。PostGIS相对来说学习成本较高，因为Postgresql是一种关系型数据库，如果只接入普通的数据类型，其实相当于是维护了另一种MySQL，完全没必要，但是如果想用上GIS相关数据类型，现有的ORM框架支持得并不友好，开发效率低，维护成本高。四、异步读写设计出于对用户体验的考虑，不能因为读写速度慢让用户傻傻的等待，这类问题有一个通用的解决方案：异步化。异步化的写请求很好实现，如前述所说，通过消息中间件来解决此问题，对于客户端的位置上报请求，不需要强一致性，能确定数据被塞入消息队列中即可。除此之外，还在消息队列和存储层之间加入了双Buffer缓冲池，用以增加flush的效率。上图中的Buffer-1和Buffer-2共同组成一个循环队列，每次只有一个Buffer用了缓冲数据。图中的Flush Point表示每个Buffer达到一定的阈值（Threshold）后，将会触发数据落盘，并且会在此刻切换Buffer。图中所示的阈值是50%，可以根据实际情况上下调整。值得注意的是，在Flush Point，应该是先切换Buffer，再flush数据，也就是在flush的同时，还能接收上报的位置信息。如果要等待flush完毕再切换，将会导致流量过渡不平滑，出现一段时间的队列拥塞。接下来要解决大量读请求，应对这种问题，有一个不二法门就是：拆。非常类似“分表”的思想，但是在这个场景下，没有传统意义上“分表”所带来的诸多副作用。“分表”有一个规则，比如按Hash(user_id)进行“横向分表”，按照常用字段进行“纵向分表”。受到Hadoop关于资源管理的启发，在此位置采集系统中，使用了“元数据”来代替分表规则，这里的“元数据”相当于NameNode，是管理数据的数据，将散落在不同位置的数据集中化管理。如上图所示，按城市级别进行分库，每个城市的位置数据相对独立，体现在客户端的功能就是“切换城市”。“分表”意即分成多份Collection，以一天为最小粒度，因为一个城市的当天数据通常是“最热”的，众多查询请求都需要这份数据，分页，聚合，排序等需求都不是问题了，因此一天一个Collection是比较合理的切分。当然，如果一天的数据量过少，可以适当延长数据切分的周期。那么，如果查询请求的时间段跨天了，该怎么办呢？这时候，“元数据”就发挥威力了。查询请求分为两部分，第一个是定位元数据，就是在meta data中找寻符合条件的所有Collection(s)，为了尽可能缩小查询范围，需要指定一定的时间区段，这个也是有现实意义的。所有的位置数据被分为了三种等级：Hot，Cold，Freeze，Hot等级通常是指当天的数据，读写最频繁的部分；Cold等级被界定为过去一个月内的数据，应对的各类查询和分析的需求；Freeze等级是已归档的数据，没有特殊情况不会被解冻。通过时间区段拿到N个Collection(s)后，附加上其他的查询条件，循环N次，成功循环一次，就渲染一次获取到的数据，直到循环结束。上述N>1的业务场景只可能出现在后台管理系统，也就是移动端不会出现跨天的业务需求，提供的API都是针对Hot级别的数据。如果一旦出现了这种情况，可以限制时间区段，比如只能获取两天内的数据。五、总结本文详细阐述了手机定位采集系统的设计，整个系统的复杂性集中在了数据的存储和呈现，我在此文中都给出了相应的解决方案。除此之外，整个采集系统还会有其他的功能模块，诸如日志采集与分析，实时监控等，限于篇幅，不再逐一叙述了。以下是扩展阅读，对于理解整个系统会有所帮助，建议阅读之。1、细说双Buffer缓冲池2、物联网设备网关系统架构设计扫描下方二维码，进入原创干货，搞“技”圣地。

小叽导读：闲鱼是一款闲置物品的交易平台APP。通过这个平台，全国各地“无处安放”的物品能够轻松实现流动。这种分享经济业务形态被越来越多的人所接受，也进一步实现了低碳生活的目标。今天，闲鱼团队就商品与商圈的匹配算法为我们展开详细解读。摘要闲鱼app根据交通条件、商场分布情况、住宅区分布情况综合考虑，将城市划分为一个个商圈。杭州部分区域商圈划分如下图所示。 闲鱼的商品是由用户发布的GPS随机分布在地图上的点数据。当用户处于某个商圈范围内时，app会向用户推荐GPS位于此商圈中的商品。要实现精准推荐服务，就需要计算出哪些商品是归属于你所处的商圈。在数据库中，商圈是由多个点围成的面数据，这些面数据形状、大小各异，且互不重叠。商品是以GPS标记的点数据，如何能够快速高效地确定海量商品与商圈的归属关系呢？传统而直接的方法是，利用几何学的空间关系计算公式对海量数据实施直接的“点—面”关系计算，来确定每一个商品是否位于每一个商圈内部。闲鱼目前有10亿商品数据，且每天还在快速增加。全国所有城市的商圈数量总和大约为1万，每个商圈的大小不一，边数从10到80不等。如果直接使用几何学点面关系运算，需要的计算量级约为2亿亿次基本运算。按照这个思路，我们尝试过使用阿里巴巴集团内部的离线计算集群来执行计算，结果集群在运行了超过2天之后也未能给出结果。经过算法改进，我们采用了一种基于GeoHash精确匹配，结合GeoHash非精确匹配并配合小范围几何学关系运算精匹配的算法，大大降低了计算量，高效地实现了离线环境下海量点-面数据的包含关系计算。同样是对10亿条商品和1万条商圈数据做匹配，可以在1天内得到结果。▌点数据GeoHash原理与算法GeoHash是一种对地理坐标进行编码的方法，它将二维坐标映射为一个字符串。每个字符串代表一个特定的矩形，在该矩形范围内的所有坐标都共用这个字符串。字符串越长精度越高，对应的矩形范围越小。对一个地理坐标编码时，按照初始区间范围纬度[-90,90]和经度[-180,180]，计算目标经度和纬度分别落在左区间还是右区间。落在左区间则取0，右区间则取1。然后，对上一步得到的区间继续按照此方法对半查找，得到下一位二进制编码。当编码长度达到业务的进度需求后，根据“偶数位放经度，奇数位放纬度”的规则，将得到的二进制编码穿插组合，得到一个新的二进制串。最后，根据base32的对照表，将二进制串翻译成字符串，即得到地理坐标对应的目标GeoHash字符串。以坐标“30.280245, 120.027162”为例，计算其GeoHash字符串。首先对纬度做二进制编码：将[-90,90]平分为2部分，“30.280245”落在右区间(0,90]，则第一位取1。将(0,90]平分为2分，“30.280245”落在左区间(0,45]，则第二位取0。不断重复以上步骤，得到的目标区间会越来越小，区间的两个端点也越来越逼近“30.280245”。下图的流程详细地描述了前几次迭代的过程： 按照上面的流程，继续往下迭代，直到编码位数达到我们业务对精度的需求为止。完整的15位二进制编码迭代表格如下： 得到的纬度二进制编码为10101 01100 01000。按照同样的流程，对经度做二进制编码，具体迭代详情如下：得到的经度二进制编码为11010 10101 01101。按照“偶数位放经度，奇数位放纬度”的规则，将经纬度的二进制编码穿插，得到完成的二进制编码为：11100 11001 10011 10010 00111 00010。由于后续要使用的是base32编码，每5个二进制数对应一个32进制数，所以这里将每5个二进制位转换成十进制位，得到28,25,19,18,7,2。 对照base32编码表，得到对应的编码为：wtmk72。 可以在geohash.org/网站对上述结果进行验证，验证结果如下：验证结果的前几位与我们的计算结果一致。如果我们利用二分法获取二进制编码时迭代更多次，就会得到验证网站中这样的位数更多的更精确结果。GeoHash字符串的长度与精度的对应关系如下： ▌面数据GeoHash编码实现上一节介绍的标准GeoHash算法只能用来计算二维点坐标对应的GeoHash编码，我们的场景中还需要计算面数据（即GIS中的POLYGON多边形对象）对应的GeoHash编码，需要扩展算法来实现。算法思路是，先找到目标Polygon的最小外接矩形MBR，计算此MBR西南角坐标对应的GeoHash编码。然后用GeoHash编码的逆算法，反解出此编码对应的矩形GeoHash块。以此GeoHash块为起点，循环往东、往北找相邻的同等大小的GeoHash块，直到找到的GeoHash块完全超出MBR的范围才停止。如此找到的多个GeoHash块，边缘上的部分可能与目标Polygon完全不相交，这部分块需要通过计算剔除掉，如此一来可以减少后续不必要的计算量。 上面的例子中最终得到的结果高清大图如下，其中蓝色的GeoHash块是与原始Polygon部分相交的，橘黄色的GeoHash块是完全被包含在原始Polygon内部的。上述算法总结成流程图如下： ▌求临近GeoHash块的快速算法上一节对面数据进行GeoHash编码的流程图中标记为绿色和橘黄色的两步，分别是要寻找相邻的东边或北边的GeoHash字符串。传统的做法是，根据当前GeoHash块的反解信息，求出相邻块内部的一点，在对这个点做GeoHash编码，即为相邻块的GeoHash编码。如下图，我们要计算"wtmk72"周围的8个相邻块的编码，就要先利用GeoHash逆算法将"wtmk72"反解出4个顶点的坐标N1、N2、N3、N4，然后由这4个坐标计算出右侧邻接块内部的任意一点坐标N5，再对N5做GeoHash编码，得到的“wtmk78”就是我们要求的右边邻接块的编码。按照同样的方法，求可以求出"wtmk72"周围总共8个邻接块的编码。这种方法需要先解码一次再编码一次，比较耗时，尤其是在指定的GeoHash字符串长度较长需要循环较多次的情况下。通过观察GeoHash编码表的规律，结合GeoHash编码使用的Z阶曲线的特性，验证了一种通过查表来快速求相邻GeoHash字符串的方法。还是以“wtmk72”这个GeoHash字符串为例，对应的10进制数是“28，25，19，18，7，2”，转换成二进制就是11100 11001 10011 10010 00111 00010。其中，w对应11100，这5个二进制位分别代表“经 纬 经 纬 经”；t对应11001，这5个二进制位分别代表“纬 经 纬 经 纬”。由此推广开来可知，GeoHash中的奇数位字符（本例中的’w’、’m’、‘7’）代表的二进制位分别对应“经 纬 经 纬 经”，偶数位字符（本例中的’t’、‘k’、‘2’）代表的二进制位分别对应“纬 经 纬 经 纬”。‘w’的二进制11100，转换成方位含义就是“右 上 右 下 左”。’t’的二进制11001，转换成方位含义就是“上 右 下 左 上”。根据这个字符与方位的转换关系，我们可以知道，奇数位上的字符与位置对照表如下： 偶数位上的字符与位置对照表如下：这里可以看到一个很有意思的现象，奇数位的对照表和偶数位对照表存在一种转置和翻转的关系。有了以上两份字符与位置对照表，就可以快速得出每个字符周围的8个字符分别是什么。而要计算一个给定GeoHash字符串周围8个GeoHash值，如果字符串最后一位字符在该方向上未超出边界，则前面几位保持不变，最后一位取此方向上的相邻字符即可；如果最后一位在此方向上超出了对照表边界，则先求倒数第二个字符在此方向上的相邻字符，再求最后一个字符在此方向上相邻字符（对照表环状相邻字符）；如果倒数第二位在此方向上的相邻字符也超出了对照表边界，则先求倒数第三位在此方向上的相邻字符。以此类推。以上面的“wtmk72”举例，要求这个GeoHash字符串的8个相邻字符串，实际就是求尾部字符‘2’的相邻字符。‘2’适用偶数对照表，它的8个相邻字符分别是‘1’、‘3’、‘9’、‘0’、‘8’、‘p’、‘r’、‘x’，其中‘p’、‘r’、‘x’已经超出了对照表的下边界，是将偶数位对照表上下相接组成环状得到的相邻关系。所以，对于这3个超出边界的“下方”相邻字符，需要求倒数第二位的下方相邻字符，即‘7’的下方相邻字符。‘7’是奇数位，适用奇数位对照表，‘7’在对照表中的“下方”相邻字符是‘5’，所以“wtmk72”的8个相邻GeoHash字符串分别是“wtmk71”、“wtmk73”、“wtmk79”、“wtmk70”、“wtmk78”、“wtmk5p”、“wtmk5r”、“wtmk5x”。利用此相邻字符串快速算法，可以大大提高上一节流程图中面数据GeoHash编码算法的效率。▌高效建立海量点数据与面数据的关系建立海量点数据与面数据的关系的思路是，先将需要匹配的商品GPS数据（点数据）、商圈AOI数据（面数据）按照前面所述的算法，分别计算同等长度的GeoHash编码。每个点数据都对应唯一一个GeoHash字符串；每个面数据都对应一个或多个GeoHash编码，这些编码要么是“完全包含字符串”，要么是“部分包含字符串”。a)将每个商品的GeoHash字符串与商圈的“完全包含字符串”进行join操作。join得到的结果中出现的<商品,商圈>数据就是能够确定的“某个商品属于某个商圈”的关系。b)对于剩下的还未被确定关系的商品，将这些商品的GeoHash字符串与商圈的“部分包含字符串”进行join操作。join得到的结果中出现的<商品,商圈>数据是有可能存在的“商品属于某个商圈”的关系，接下来对这批数据中的商品gps和商圈AOI数据进行几何学关系运算，进而从中筛选出确定的“商品属于某个商圈”的关系。如图，商品1的点数据GeoHash编码为"wtmk70j"，与面数据的“完全包含字符串wtmk70j”join成功，所以可以直接确定商品1属于此面数据。商品2的点数据GeoHash编码为“wtmk70r”，与面数据的“部分包含字符串wtmk70r”join成功，所以商品2疑似属于面数据，具体是否存在包含关系，还需要后续的点面几何学计算来确定。 商品3的点数据GeoHash编码与面数据的任何GeoHash块编码都匹配不上，所以可以快速确定商品3不属于此面数据。 实际应用中，原始的海量商品GPS范围散布在全国各地，海量商圈数据也散布在全国各个不同的城市。经过a)步骤的操作后，大部分的商品数据已经确定了与商圈的从属关系。剩下的未能匹配上的商品数据，经过b)步骤的GeoHash匹配后，可以将后续“商品-商圈几何学计算”的运算量从“1个商品 x 全国所有商圈”笛卡尔积的量级，降低为“1个商品 x 1个（或几个）商圈”笛卡尔积的量级，减少了绝大部分不必要的几何学运算，而这部分运算是非常耗时的。在闲鱼的实际应用中，10亿商品和1万商圈数据，使用本文的快速算法，只需要 10亿次GeoHash点编码 + 1万次GeoHash面编码 + 500万次“点是否在面内部”几何学运算，粗略换算为基本运算需要的次数约为1800亿次，运算量远小于传统方法的2亿亿次基本运算。使用阿里巴巴的离线计算平台，本文的算法在不到一天的时间内就完成了全部计算工作。另外，对于给定的点和多边形，通过几何学计算包含关系的算法不止一种，最常用的算法是射线法。简单来说，就是从这个点出发做一条射线，判断该射线与多边形的交点个数是奇数还是偶数。如果是奇数，说明点在多边形内；否则，点在多边形外。▌延伸面对海量点面数据的空间关系划分，本文采用是的通过GeoHash来降低计算量的思路，本质上来说是利用了空间索引的思想。事实上，在GIS领域有多种实用的空间索引，常见的如R树系列（R树、R+树、R*树）、四叉树、K-D树、网格索引等，这些索引算法各有特点。本文的思路不仅能用来处理点—面关系的相关问题，还可以用来快速处理点—点关系、面—面关系、点—线关系、线—线关系等问题，比如快速确定大范围类的海量公交站台与道路的从属关系、多条道路或铁路是否存在交点等问题。本文作者：峰明阅读原文本文来自云栖社区合作伙伴“ 阿里技术”，如需转载请联系原作者。