本文使用postgis实现了数亿活跃用户的附近xx功能。比如,摇一摇。更多功能关注小姐姐味道微信公众号:xjjdog.

假如动物们也用GPS,突然有那么一天北极的公北极熊有点冲动,想刷一下附近有没有母熊。要求距离越近越好,不是澳大利亚动物园那只,也不是格陵兰岛上被囚禁的那群呆企鹅,要是有点共同的嗜好就再好不过了。这种应用场景如何解决?

一个基于LBS的社交应用或者电商应用,或多或少的包含一些地理信息,如经纬度(lat、lng)。如何在既定的时限内响应用户的请求,如何低成本的存储这些数据,是LBS应用最关键的问题。我们以附近的人为例,看一下如何去做一个生产级别的应用。

方案

你可能已经了解到,目前有多种方法可以实现这样的功能,如solr、es、mongodb、redis等scheme free的数据库,也有使用mysql+geohash来实现这些功能的。

为什么不用geohash将问题一纬化呢?

因为这种做法无法准确计算距离,而且扩展性和维护性都是问题

为什么不用solr、es、mysql、sphinx呢?

因为这几位都是gis函数库的阉割版,多个维度查询会有问题,优化困难

为什么不用mongodb

因为mongodb会随数据量的增加在地理位置查询时性能会急剧下降,而pg是线性的

为什么不用redis geo呢?

redis数据全部放在内存中,不支持排序。有谁用在生产环境中了,请告诉我...

本文采用postgis方案,相比较其他方案,开发人员对SQL都比较熟悉。技术选择上,你选择了最优,你就节约了时间和成本,人生苦短,作为使用者没必要在一些半成品上浪费时间。postgresql本身是最优秀的开源RDBMS,postgis是功能最多、最成熟的开源gis数据库。GIS方面,支持:

1、空间数据类型,包括:点(POINT)、线(LINESTRING)、多边形(POLYGON)、多点(MULTIPOINT)、 多线(MULTILINESTRING)、多多边形(MULTIPOLYGON)和集合对象集(GEOMETRYCOLLECTION)

2、空间分析函数,包括:面积(Area)、长度(Length)和距离(Distance)

3、元数据以及函数,包括:GEOMETRY_COLUMNS和SPATIAL_REF_SYS

4、二元谓词,包括:Contains、Within、Overlaps和Touches

5、空间操作符,包括:Union和Difference

实现/单机

我们首先看下单机版的附近的人:
首先,安装之。以centos7为例。

echo 'exclude=postgresql*' >> /etc/yum.repos.d/CentOS-Base.repo
cat /etc/readhat-release
sudo rpm -ivh http://yum.postgresql.org/9.5/redhat/rhel-7-x86_64/pgdg-centos95-9.5-2.noarch.rpm
yum install postgresql95 postgresql95-server postgresql95-libs postgresql95-contrib postgresql95-devel
 
 service postgresql-9.5 initdb
 chkconfig postgresql-9.5 on
 service postgresql-9.5 restart

Postgis的依赖比较多,由于CentOS默认是有pg源的,要首先排除它,安装专用源。
基本数据结构如下:

CREATE EXTENSION postgis;

drop table if exists nearby_user;
create table nearby_user(
userid varchar,
sex varchar,
age int,
loc geometry,
updateTime timestamp
); 

CREATE INDEX geom_loc_index ON nearby_user USING GIST(loc);
CREATE INDEX geom_time_index ON nearby_user USING BTREE(updateTime);
CREATE UNIQUE INDEX userid_index ON nearby_user  USING BTREE(userid);

有三个比较重要的点

1、 通过create extension语句创建postgis插件,每个库只能创建一次

2、创建一个gis类型字段,支持POINT、POLYGON等多种数据类型,我们后续的排序和计算都将使用此字段

3、为loc字段创建空间索引(GIST索引),可以进行排序、计算距离等

如图,我们要查询某个用户最近N天附近的人,根据距离有近到远进行排序,查询第一页,每页25条



1、使用planar degrees 4326坐标系计算两个点之间的距离(Point(x,y))

2、将查询的结果转换为meters 26986坐标系表示的距离,此即普通单位米。为什么将这一步单独做一个嵌套查询呢?因为ST_Transform是不走索引的,距离排序要全表扫,代价太大

3、ST_X,ST_Y等,将坐标转化为可读的经纬度,而不是0101000020E61000005C5E792FA2075D4026BC259C750C4440这种天文数字

如图,查看执行计划,使用了geom_loc_index索引进行排序,其他条件走过滤匹配。单表300W+数据,2k+ QPS下,执行只花费了7ms(24核、32G、SATA),算得上是非常神奇了。

实现/集群

分布式计算第一定律:如果不是真正需要就不要让系统分布式。但随着业务扩张,DAU不断上涨,逐渐达到百万+,就不得不考虑可用性和扩展性了。我们从以下几个方面探讨如何做一个可伸缩的高可用附近的XX。

需求

  • 要求较高的实时性,不做缓存,读取和写入都比较频繁(1w+ TPS/s)
  • 能够按照查询距离进行排序,能够分页
  • 支持除位置意外的其他条件过滤(如年龄,性别,用户标签等)
  • 支持GIS其他扩展功能,如三维、区块包含查询
  • 要求大部分查询能够在100ms内返回,部分长尾请求不超过1s
  • 要求支持集群环境基本的failover、SLB功能

分析

系统实时性要求比较高,所以并不能通过折衷方案进行结果缓存。用户的每次请求都需要实际的计算,这注定了CPU将成为系统的主要争夺点。由于RDBMS的特性,在内存有限的环境中,IO也会成为瓶颈,建议有条件的尽量挂载SSD硬盘。

由于GIS应用会有热点问题和各种数据调整问题,传统的sharding技术(mod、hash、random)并不能很好的工作,我们需要自定义路由表。这种情况下,Greenplum或者Postgresql-XL(GTM会成为瓶颈)这类分布式解决方案就不在考虑之内,避免陷入额外的技术陷阱和成本陷阱。

路由表可以使用geohash进行分块或者按照实际的城市区域代码进行分片映射。使用区域代码进行分片,会有比较好的效果,因为地理的分界线一般都是山川河流等数据不敏感的地区,但这种方式需要你有一个逆地理服务(根据经纬度查询城市编码),搭建成本是比较高的。

geohash就简单的多,但会有一定的数据瑕疵,假定我们采用的是geohash编码(请自行解决geohash的问题,简单来讲,就是将地球上的一个区域块,一维化为一个固定的编码,然后把地球切分成这么一群区域块)。使用这种方式,就可以将热点进行分片,一个可能的数据映射如下:

每一组机器有一台master,N台slave通过WAL日志进行复制。每个geohash块属于一组或多组机器,都有一个标识来表明节点的权重,以及是否可用。

然后我们将geohash分成十几个组,比如12个,那么需要的pg实例个数就为 12*(masterNum+slavesNum) = 36个。实例个数增长,就需要一种集群管理方法,避免被服务瘫痪的报警叫起床。

架构

可以使用如下的架构:
- Location Service提供用户位置服务,可以使用简单的KV数据库进行保存,目的是可以随时查看到用户的位置信息

  • 用户的位置更新,最好打到Queue里进行缓冲。这种模式有很多好处,比如你可以订阅一份数据专门去做用户的轨迹服务
  • PgRouter 将经纬度转化为geohash,根据路由表信息,定位到pg集群中的一批节点,进行查询计算
  • 节点的启停、主从关系,使用repmgr进行管理。Master故障Slave能够自动提权
  • PgMonitor 是一组脚本,能够监控节点的存活状态和主从关系,然后将存活信息更新到Zookeeper或者Etcd中,当然也可以是consul。

    • PgRouter监听到节点变化,会重建内存路由表信息,隔离故障节点

问题解决

接下来我们分析这些问题如何解决。

热点问题如何解决,如何应对突发流量?

热点取决于你对geohash划分的粒度,你可以通过挂载多个从库或者将一批cluster进行拆分

复制的效率和一致性如何解决?

数据库采用standby WAL日志进行复制,速度很快,延迟小。如果从机太多,可以采用级联复制方式(slave的slave)。由于采用了单master,可以保证一致性问题。唯一的问题是master宕机切换过程会造成写入失败,所以消息队列有必要采用失败重试的策略。案例中pg既作为一个存储节点,又作为一个计算节点。如果你的应用对数据的一致性要求不是那么高,完全可以将事务隔离级别设置为"read uncommitted"

负载均衡放在哪个层面去做?

曾经考虑过使用HA或者LVS,再或者kubernetes将pg打造成一个微服务。但万变不离其宗,这些花拳绣腿会引入额外的复杂性,远不如简单的自定义路由来的方便快捷,我们引入节点权重的意义就在这里,如某些节点因为IO等运算缓慢,就可以降低其权重来解决。

迭代过程需要变更scheme,postgis如何动态添加某个字段?

可以直接添加,并不影响服务,但要注意删除操作可能会有较大的影响。

如何动态添加删除索引?

不建议这么做,如果确实有这部分需求,建议业务低峰进行此操作

如何实现如QQ中用户标签的过滤?比如查询一批拥有"逗逼"标签的人

我们采用pg的另外一个原因就是,它的数据类型非常丰富,这在使用中就显得特别简洁和方便。pg是一个学术派很浓的数据库,能够试用一些最前沿功能。比如标签就可以用hstore或者jsonb数据类型来实现。在可预见的项目生命周期中,pg的支持足够了

如何去做监控?

自己编写zabbix插件、或者接入nagios,也可以接入grafana,取决于你所使用的监控平台。也有pgcluu等工具。

如何监控节点的上下线?

这个比较简单,可以使用脚本轮训检测,也可以使用repmgr的主动通知功能,构造事件写入配置中心。

下面是一个简单的脚本例子:

END

更复杂的,如果PostGIS也无法满足你的性能需求,你可能已经是行业巨头了,可以考虑用PostGIS做数据存储源,用Solr/ES专门提供搜索等。但目前为止,北极熊也已经找到了它的小伙伴,多快乐啊。

参考链接:
postgis: http://www.postgis.net/
postgresql: https://www.postgresql.org/docs/9.5/static/index.html
repmgr: https://github.com/2ndQuadrant/repmgr

更多精彩文章。

《微服务不是全部,只是特定领域的子集》

《“分库分表" ?选型和流程要慎重,否则会失控》

这么多监控组件,总有一款适合你

《Linux生产环境上,最常用的一套“vim“技巧》

《使用Netty,我们到底在开发些什么?》

Linux五件套之类的。

《Linux之《荒岛余生》(一)准备篇》

《Linux之《荒岛余生》(二)CPU篇》

《Linux之《荒岛余生》(三)内存篇》

《Linux之《荒岛余生》(四)I/O篇》

《Linux之《荒岛余生》(五)网络篇》

更多请关注。当然也可以关注公众号。