海量用户实时定位和圈人 - 团圆社会公益系统(位置寻人圈人)

3 minute read

背景

老人、儿童是最容易走丢的人群,一定要看好老人和小孩,但是万一走丢了怎么办呢?

阿里有一个公益系统,团圆,这个系统是用来帮助发布走丢人群信息的,公安通过发布的走丢人的照片,最后一次的位置信息,向社会发布。

通过公益平台的合作伙伴(例如运营商、购物软件等)可以向最后一次走丢人士出现的位置附近的人推送寻人启事,调动社会力量帮助寻找丢失人。

为了实现这个目的,需要收集社会人士的实时位置,现在有很多技术可以实现,例如手机基站定位、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最佳实践》

Flag Counter

digoal’s 大量PostgreSQL文章入口