海量用户实时定位和圈人 - 团圆社会公益系统(位置寻人圈人)
背景
老人、儿童是最容易走丢的人群,一定要看好老人和小孩,但是万一走丢了怎么办呢?
阿里有一个公益系统,团圆,这个系统是用来帮助发布走丢人群信息的,公安通过发布的走丢人的照片,最后一次的位置信息,向社会发布。
通过公益平台的合作伙伴(例如运营商、购物软件等)可以向最后一次走丢人士出现的位置附近的人推送寻人启事,调动社会力量帮助寻找丢失人。
为了实现这个目的,需要收集社会人士的实时位置,现在有很多技术可以实现,例如手机基站定位、GPS定位等。
假设有10亿手机用户,用户的位置实时变动,实时的位置信息需要更新到数据库中。每天可能有千亿次位置更新。
同时发布走失信息后,需要到数据库中,根据走失位置圈出附近的人。
简单粗暴设计1 - geometry + GiST空间索引
1、表结构设计:
create table tbl_pos(
id int primary key, -- 用户ID
pos point -- 用户实时位置
);
2、空间索引
create index idx_tbl_pos on tbl_pos using gist(pos);
性能评测
实时更新10亿用户位置,使用insert on conflict语法。
vi test.sql
\set id random(1,1000000000)
insert into tbl_pos values (:id, point(random()*180,random()*90)) on conflict (id) do update set pos=excluded.pos;
使用32个并发,实时生成用户随机位置.
nohup pgbench -M prepared -n -r -P 5 -f ./test.sql -c 32 -j 32 -T 120000 > ./pos.log 2>&1 &
1、实时位置更新TPS,约18万/s。
179799
服务器负载,服务器还是非常空闲的,有足够的资源提供给查询
top - 01:52:34 up 76 days, 15:32, 2 users, load average: 33.74, 33.56, 31.47
Tasks: 1064 total, 34 running, 1030 sleeping, 0 stopped, 0 zombie
%Cpu(s): 47.6 us, 5.4 sy, 0.0 ni, 46.9 id, 0.2 wa, 0.0 hi, 0.0 si, 0.0 st
KiB Mem : 52807456+total, 32911484+free, 10949652 used, 18801006+buff/cache
KiB Swap: 0 total, 0 free, 0 used. 42997945+avail Mem
2、查询性能。
在位置更新的同时,测试查询性能。
假设走失人口最后位置出现在杭州,那么我们需要查询在某个平面(例如杭州市)内的点。返回500万个点(社会用户),仅需28秒。
使用空间索引,返回速度杠杠的。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl_pos where box(point(1,1), point(25.5,25.5)) @> pos limit 5000000;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.55..412954.11 rows=407872 width=20) (actual time=1.433..27536.623 rows=5000000 loops=1)
Output: id, pos
Buffers: shared hit=6183117 dirtied=31842
-> Index Scan using idx_tbl_pos on public.tbl_pos (cost=0.55..412954.11 rows=407872 width=20) (actual time=1.431..26861.352 rows=5000000 loops=1)
Output: id, pos
Index Cond: ('(25.5,25.5),(1,1)'::box @> tbl_pos.pos)
Buffers: shared hit=6183117 dirtied=31842
Planning time: 0.353 ms
Execution time: 27950.171 ms
(9 rows)
实际查询用,可以使用游标,流式返回。例子
postgres=# begin;
BEGIN
postgres=# declare cur cursor for select * from tbl_pos where box(point(1,1), point(25.5,25.5)) @> pos;
DECLARE CURSOR
postgres=# fetch 10 from cur;
id | pos
-----------+-------------------------------------
680844515 | (2.08381220698357,1.25674836337566)
498274514 | (2.23715107887983,1.27883949782699)
72310072 | (2.1013452205807,1.32945269811898)
301147261 | (2.12246049195528,1.33455505594611)
186462127 | (2.13169047608972,1.24054086394608)
726143191 | (2.27320306934416,1.31862969137728)
902518425 | (2.27059512399137,1.32658164482564)
534516939 | (2.18118946999311,1.29441328346729)
329417311 | (2.27630747482181,1.2547113513574)
853173913 | (2.28139906190336,1.33868838194758)
(10 rows)
postgres=# \timing
Timing is on.
postgres=# fetch 10 from cur;
id | pos
-----------+-------------------------------------
223759458 | (2.24917919375002,1.31508464924991)
215111891 | (2.10541740059853,1.26674327999353)
925178989 | (2.08201663568616,1.2974686967209)
954808979 | (2.10515496321023,1.32548315450549)
514021414 | (2.17867707833648,1.27732987515628)
872436892 | (2.22504794597626,1.31386948283762)
507169369 | (2.05484946258366,1.30171341821551)
317349985 | (2.25962312892079,1.30945896729827)
200956423 | (2.10705514065921,1.30409182514995)
598969258 | (1.98812280781567,1.30866004619747)
(10 rows)
Time: 0.306 ms
通过游标,客户端可以边接收,边发短信或者向软件推送寻人启事。
实现流式推送,节省宝贵的寻人时间。
简单粗暴设计2 - geohash + btree索引
团圆系统对空间数据精度要求并不像一些LBS社交软件那么高,可以使用GEOHASH+btree索引 代替 geometry+GIST空间索引。
转换方法使用 PostGIS的 st_geohash(geometry, int) 函数。不再赘述。
《PostGIS空间索引(GiST、BRIN、R-Tree)选择、优化 - 阿里云RDS PostgreSQL最佳实践》
优化设计 - schemaless分区法
单表十亿空间数据,对于查询来说,前面已经看到了,毫无压力。但是随着频繁的更新,可能到GiST索引的膨胀,膨胀后,PostgreSQL提供了并行创建索引的方法(不影响堵塞,可以在一个列创建同样的索引),来维护索引。但是10亿数据创建索引会变得很久。
为了解决这个问题,建议使用分区表。例如将ID哈希,分成64个分区,每个分区1500万左右数据。
在PostgreSQL中,目前性能最好的分区是pg_pathman插件。或者使用schemaless的方式。下面以schemaless为例子。其实在我曾经写过的另外的案例中也非常常见
《行为、审计日志 (实时索引/实时搜索)建模 - 最佳实践 2》
《PostgreSQL 时序最佳实践 - 证券交易系统数据库设计 - 阿里云RDS PostgreSQL最佳实践》
下面以geometry + gist空间索引为例讲解schemaless分区法。
定义基表
postgres=# create table tbl_pos(id int primary key, pos point);
CREATE TABLE
postgres=# create index idx_tbl_pos_1 on tbl_pos using gist(pos);
CREATE INDEX
定义自动建表函数
create or replace function create_schemaless(
target name, -- 目标表名
src name -- 源表名
) returns void as $$
declare
begin
execute format('create table if not exists %I (like %I including all)', target, src);
execute format('alter table %I inherit %I', target, src);
exception when others then
return;
end;
$$ language plpgsql strict;
定义以schemaless的方式写数据的函数
创建一个插入数据的函数,使用动态SQL,如果遇到表不存在的错误,则调用建表函数进行建表。
create or replace function ins_schemaless(
id int, -- id
md int, -- 取模数
pos point -- 位置
) returns void as $$
declare
target name := 'tbl_pos_'||mod(id,md) ;
begin
execute format('insert into %I values (%L, %L) on conflict (id) do update set pos=point_add(%I.pos, point(random()*10-5, random()*10-5))', target, id, pos, target);
-- 为了模拟真实情况,因为人的移动速度有限,即使驾车,飞机(少数情况),所以用了pos=point_add(%I.pos, point(random()*10-5, random()*10-5))这种方法模拟更真实的情况
-- 实际场景,请改成pos=excluded.pos
exception
WHEN SQLSTATE '42P01' THEN
perform create_schemaless(target, 'tbl_pos');
execute format('insert into %I values (%L, %L) on conflict (id) do update set pos=point_add(%I.pos, point(random()*10-5, random()*10-5))', target, id, pos, target);
-- 为了模拟真实情况,因为人的移动速度有限,即使驾车,飞机(少数情况),所以用了pos=point_add(%I.pos, point(random()*10-5, random()*10-5))这种方法模拟更真实的情况
-- 实际场景,请改成pos=excluded.pos
end;
$$ language plpgsql strict;
数据库端的schemaless会牺牲一部分性能,因为无法使用绑定变量。
如果可能的话,建议业务层实现schemaless(自动拼接表名,自动建表,自动写入),以提高性能。
测试功能
postgres=# select ins_schemaless(2,32,point(1,2));
ins_schemaless
----------------
(1 row)
postgres=# select ins_schemaless(1,32,point(1,2));
ins_schemaless
----------------
(1 row)
postgres=# select tableoid::regclass,* from tbl_pos;
tableoid | id | pos
-----------+----+-------
tbl_pos_2 | 2 | (1,2)
tbl_pos_1 | 1 | (1,2)
(2 rows)
schemaless设计压测
vi ~/test.sql
\set id random(1,1000000000)
select ins_schemaless(:id, 32, point(random()*360-180, random()*180-90));
nohup pgbench -M prepared -n -r -P 5 -f ./test.sql -c 32 -j 32 -T 120000 > ./pos.log 2>&1 &
性能依旧杠杠的。
125977 tps
小结
1、通过PostgreSQL的空间数据类型、空间索引。加上insert on conflict的特性。实现了单机约18万行/s的10亿用户的实时位置更新,同时输出500万个点的量级,仅需20几秒。真正实现了团圆公益系统的时效性。
2、采用游标,流式返回,实现了边获取数据,边向社会各界发送寻人启事的目的。
3、另一方面,用户位置的变更,实际上是有一定过滤性的,比如用户从办公室去上个洗手间,虽然位置可能发生了变化,但是非常细微,这种变化在这套系统中可以过滤(不更新),从而减少数据的更新量。
按照现有的测试数据,可以做到每天155亿次的更新。假设每10条更新仅有1条是有效更新,那么实际上可以支持1550亿次的MOVE采集。
4、PostgreSQL是一个很有爱心的数据库系统哦。
5、将来流计算引擎pipelinedb插件化后,PostgreSQL内部将整合这个流计算引擎,通过流计算引擎,理论上可以轻松实现40万行/s级别的更新速度,每天支撑300多亿次的实时位置更新。
6、采用流计算的方法除了提高性能,同时也降低了XID的消耗,在目前32BIT XID的情形下,可以有效的环节FREEZE带来的负担。如果不使用流计算,也建议合并更新,例如一个事务中更新若干条,比如100条,那么一天的事务数就将到了1.5亿。
7、参考
https://www.postgresql.org/docs/9.6/static/gist-implementation.html#GIST-BUFFERING-BUILD
《行为、审计日志 (实时索引/实时搜索)建模 - 最佳实践 2》
《PostgreSQL 时序最佳实践 - 证券交易系统数据库设计 - 阿里云RDS PostgreSQL最佳实践》