Geo Support

[qinzuoyan]

User demand

• Near query
• With​in query

Related work

• ​RocksDB
  https://github.com/facebook/rocksdb/blob/master/include/rocksdb/utilities/geo_db.h
  https://github.com/facebook/rocksdb/tree/master/utilities/geodb
• Spatial indexing in RocksDB​
  https://rocksdb.org/blog/2015/07/17/spatial-indexing-in-rocksdb.html
  https://code.facebook.com/videos/632343316893163/geo-spatial-features-in-rocksdb-scale-presentation/
• GeoHash
  http://www.cnblogs.com/LBSer/p/3310455.html
• Spatial Keys: Memory Efficient Geohashes
  https://karussell.wordpress.com/2012/05/23/spatial-keys-memory-efficient-geohashes/
• Google S2
  http://s2geometry.io/​
  https://www.jianshu.com/p/7332dcb978b2
  https://s2.sidewalklabs.com/regioncoverer/
• Mongodb Geo2d
  https://cloud.tencent.com/developer/article/1004794

[acelyc111]

code preview: #74

[qinzuoyan]

测试环境：
tjwqtst-staging
5个Replica-Server节点
机型：金山云I2.16C | 1TB SSD

测试数据：
LBS的线上真实数据

测试接口：
geo库的search_radial​接口：

int search_radial(double lat_degrees,
                            double lng_degrees,
                            double radius_m,
                            int count,
                            SortType sort_type,
                            int timeout_milliseconds,
                            std::list<SearchResult> &result);

参数：

• lat_degrees、lng_degrees：每次都选取北京五环内的随机点
• radius_m：如下表第一列，单位米
• count：-1，表示不限定结果数量
• sort_type：不排序

测试结果：
接口耗时，单位ms

搜索半径(m)	P50​	P75	P99	P99.9
50	5.74500703	6.61061453	16.88	29.33333333
100	6.755	9.255	23.57142857	160
200	11.16315789	17.24050633	46.33333333	58.407519
300	17.82186235	28.5245098	71.33333333	106.7272727
500	35.95890411	57.41176471	131.4285714	157.1428571
1000	102.6530612	159.6453901	368.8571429	510.877916
2000	277.5409836	437.406639	838.4659091	921.878034
5000	1166.537468	1677.319588	2416.807227	2416.807227
10000	4015.98878	5372.027972	7470.800489	7470.800489

[qinzuoyan]

使用线上环境重新测试：
c4tst-geo
5个Replica-Server节点
机型：i2 | E5-2620v3 *2 | 8* 480G SSD(RAID 50) | 8* 16G

测试结果：

	P50	P75	P99	P99.9
50	3.64939416	4.14832502	8.27692308	14
100	3.82015066	4.85101289	9.43780488	14
200	5.15465686	6.50816832	16.57142857	21.71428571
300	6.57623762	9.2990099	21.83333333	33
500	11.13965517	17.17241379	39.85714286	47.094414
1000	30.9528536	47.34599156	105.4482759	137.157581
2000	90.95535714	138.5869565	260.9090909	293.528327
5000	420.0909091	607.0136519	844.556314	977.725444
10000	1497.988827	1889.050279	2771.933472	2872.54099

[qinzuoyan]

测试数据和环境与上面c4tst-geo一样。
LBS的线上真实数据，请求北京五环内的随机点，半径50~2000米。

经过优化，目前的测试数据如下：

半径(m)\metric	P50(ms)	P75(ms)	P99(ms)	P99.9(ms)​	平均结果条数	单节点QPS
50	1.63071622	1.84607433	4.04545455	6.28	9.4608	740.287
100	1.76	2.33614794	5.4	6.45319149	38.0296	656.66
200	2.41017042	3.31062092	6.41781609	9.60588235	154.3682	536.624
300	3.30833333	4.21979167	9.4310559	18	350.9676	434.491
500	5.07763975	6.84964682	16.84931507	21.78082192	986.0826	347.231
1000	12.28164727	18.70972532	43.18181818	57.049698	3947.5294	204.23
2000	35.78666667	54.7300885	108.7331378	148.616578	15674.1198	98.7633