菜鸟末端轨迹揭秘：如何支撑每天251亿个包裹的数据库

标签

PostgreSQL , PostGIS , 多边形 , 面 , 点 , 面点判断 , 菜鸟

背景

菜鸟末端轨迹项目中涉及的一个关键需求，面面判断。

在数据库中存储了一些多边形记录，约几百万到千万条记录，例如一个小区，在地图上是一个多边形。

不同的快递公司，会有各自不同的多边形划分方法（每个网点负责的片区(多边形)，每个快递员负责的片区(多边形)）。

用户在寄件时，根据用户的位置，查找对应快递公司负责这个片区的网点、或者负责该片区的快递员。

一、需求

1、在数据库中存储了一些静态的面信息，代表小区、园区、写字楼等等。所有的面不相交。

2、为了支持不同的业务类型，对一个地图，可能划分为不同的多边形组成。

例如不同的快递公司，会有各自不同的多边形划分方法（网点负责的片区(多边形)，某个快递员负责的片区(多边形)）。

因此在一张地图上，有多个图层，每个图层的多边形划分方法可能不一样。

3、快速的根据快递公司、客户的位置，求包含这个点的多边形（即得到对应快递公司负责这个片区的网点、或者负责该片区的快递员）。

二、架构设计

用到阿里云的RDS PostgreSQL，以及PG提供的PostGIS插件。

我们需要用到PostGIS的函数有两个

http://postgis.net/docs/manual-2.3/ST_Within.html

1、ST_within

ST_Within — Returns true if the geometry A is completely inside geometry B

boolean ST_Within(geometry A, geometry B);

Returns TRUE if geometry A is completely inside geometry B. For this function to make sense, the source geometries must both be of the same coordinate projection, having the same SRID. It is a given that if ST_Within(A,B) is true and ST_Within(B,A) is true, then the two geometries are considered spatially equal.

This function call will automatically include a bounding box comparison that will make use of any indexes that are available on the geometries. To avoid index use, use the function _ST_Within.

-- a circle within a circle

2、ST_Contains

ST_Contains — Returns true if and only if no points of B lie in the exterior of A, and at least one point of the interior of B lies in the interior of A.

boolean ST_Contains(geometry geomA, geometry geomB);

Returns TRUE if geometry B is completely inside geometry A. For this function to make sense, the source geometries must both be of the same coordinate projection, having the same SRID. ST_Contains is the inverse of ST_Within. So ST_Contains(A,B) implies ST_Within(B,A) except in the case of invalid geometries where the result is always false regardless or not defined.

This function call will automatically include a bounding box comparison that will make use of any indexes that are available on the geometries. To avoid index use, use the function _ST_Contains.

-- A circle within a circle

三、DEMO与性能

1 PG内置几何类型 面点搜索 压测

为了简化测试，采样PG内置的几何类型进行测试，用法与PostGIS是类似的。

1、创建测试表

postgres=# create table po(id int, typid int, po polygon);

2、创建分区表或分区索引

create extension btree_gist;

3、创建空间排他约束，可选

如果要求单个typid内的po不重叠，可以创建空间排他约束

create table tbl_po(id int, typid int, po polygon)

4、写入1000万多边形测试数据

insert into po select id, random()*20, polygon('(('||x1||','||y1||'),('||x2||','||y2||'),('||x3||','||y3||'))') from (select id, 180-random()*180 x1, 180-random()*180 x2, 180-random()*180 x3, 90-random()*90 y1, 90-random()*90 y2, 90-random()*90 y3 from generate_series(1,10000000) t(id)) t;

5、测试面点判断性能

查询包含point(1,1)的多边形，响应时间0.57毫秒。

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from po where typid=1 and po @> polygon('((1,1),(1,1),(1,1))') limit 1;

6、压测

vi test.sql

惊不惊喜、意不意外

TPS：29万 ，平均响应时间：0.2毫秒

2 PostGIS空间数据库 面点搜索 压测

阿里云 RDS PostgreSQL，HybridDB for PostgreSQL 已经内置了PostGIS空间数据库插件，使用前创建插件即可。

create extension postgis;

1、建表

postgres=# create table po(id int, typid int, po geometry);

2、创建空间索引

postgres=# create extension btree_gist;

3、写入1000万多边形测试数据

postgres=# insert into po

4、测试面点判断性能

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from po where typid=1 and st_within(ST_PointFromText('POINT(1 1)'), po) limit 1;

5、压测

vi test.sql

惊不惊喜、意不意外

TPS：19.8万 ，平均响应时间：0.32毫秒

四、技术点

1、空间排他约束

这个约束可以用于强制记录中的多边形不相交。例如地图这类严谨数据，绝对不可能出现两个多边形相交的，否则就有领土纷争了。

PostgreSQL就是这么严谨，意不意外。

2、分区表

本例中不同的快递公司，对应不同的图层，每个快递公司根据网点、快递员负责的片区(多边形)划分为多个多边形。

使用LIST分区，每个分区对应一家快递公司。

3、空间索引

GiST空间索引，支持KNN、包含、相交、上下左右等空间搜索。

效率极高。

4、空间分区索引

《分区索引的应用和实践 - 阿里云RDS PostgreSQL最佳实践》

5、面面、点判断

面面判断或面点判断是本例的主要需求，用户在寄包裹时，根据用户位置在数据库的一千万多边形中找出覆盖这个点的多边形。

五、云端产品

阿里云 RDS PostgreSQL

六、类似场景、案例

《PostgreSQL 物流轨迹系统数据库需求分析与设计 - 包裹侠实时跟踪与召回》

七、小结

菜鸟末端轨迹项目中涉及的一个关键需求，面面判断。

在数据库中存储了一些多边形记录，约几百万到千万条记录，例如一个小区，在地图上是一个多边形。

不同的快递公司，会有各自不同的多边形划分方法（网点负责的片区(多边形)，某个快递员负责的片区(多边形)）。

用户在寄件时，根据用户的位置，查找对应快递公司负责这个片区的网点、或者负责该片区的快递员。

使用阿里云RDS PostgreSQL，用户存放约1千万的多边形数据，单库实现了每秒29万的处理请求，单次请求平均响应时间约0.2毫秒。

惊不惊喜、意不意外。

八、参考

http://postgis.net/docs/manual-2.3/ST_Within.html

《分区索引的应用和实践 - 阿里云RDS PostgreSQL最佳实践》