permalink: api/geo

Pegasus GEO支持

背景

业务数据跟Pegasus的普通数据类似,由hashkey、sortkey、value组成。但业务数据隐含有地理信息,比如value中包含有经纬度(latitude,longitude),需要提供API进行GEO特性的支持,比如给定一个中心点坐标和一个半径,查找这个范围内的所有数据;给定两条数据的hashkey和sortkey,求这两条数据地理上的距离。

pegasus的GEO(Geographic)支持使用了S2库, 主要利用其中将二维地理坐标(经纬度)与一维编码的相互转换、基于圆形的范围查询、Hilbert曲线规则等特性。在Pegasus中如何充分利用S2的这些特性,并结合Pegasus的数据分布、数据存储特性,是本文的阐述重点。

关于S2的实现原理细节请参考S2官网

坐标转换

在S2中,可以把二维经纬度编码成一维编码,一维编码由两部分组成:立方体面、平面坐标编码,比如:

经纬度(116.334441,40.030202)的编码是:1/223320022232200331010110113301(32位),在S2中称为cellid。

其中,首位的1代表地球立方体投影的面索引,索引范围是0~5,如下图所示:

geo_faces.png{:class=“img-responsive”}

/是分隔符

223320022232200331010110113301(30位)是经纬度坐标经过一系列转换得到的编码,具体转换过程这里不详细描述。需要指出的是,这是一个名为Hilbert曲线编码,它最大的特点是具有稳定性、连续性。

hilbert.png{:class=“img-responsive”}

编码由前往后按层进行,完整编码是前缀编码的子区域,每个父区域由4个子区域组成,比如00,01,02,030的子区域,且前者的区域范围的并集就是后者的区域范围。最多有30层,每层都有相应的cellid集合,高层cell是底层cell的父区域,高层cellid是底层cellid的前缀。

编码可以看作是一个4进制的数值编码,同时在数值上连续的值,在地理位置上也是连续的

编码精度

S2中的Hilbert曲线编码由30位组成,每一位代表一层划分。下表是各层单个cell的面积和cell个数。

levelmin areamax areaaverage areaunitsNumber of cells
0085011012.1985011012.1985011012.19km^26
0121252753.0521252753.0521252753.05km^224
024919708.236026521.165313188.26km^296
031055377.481646455.501328297.07km^2384
04231564.06413918.15332074.27km^21536
0553798.67104297.9183018.57km^26K
0612948.8126113.3020754.64km^224K
073175.446529.095188.66km^298K
08786.201632.451297.17km^2393K
09195.59408.12324.29km^21573K
1048.78102.0381.07km^26M
1112.1825.5120.27km^225M
123.046.385.07km^2100M
130.761.591.27km^2402M
140.190.400.32km^21610M
1547520.3099638.9379172.67m^26B
1611880.0824909.7319793.17m^225B
172970.026227.434948.29m^2103B
18742.501556.861237.07m^2412B
19185.63389.21309.27m^21649B
2046.4197.3077.32m^27T
2111.6024.3319.33m^226T
222.906.084.83m^2105T
230.731.521.21m^2422T
240.180.380.30m^21689T
25453.19950.23755.05cm^27e15
26113.30237.56188.76cm^227e15
2728.3259.3947.19cm^2108e15
287.0814.8511.80cm^2432e15
291.773.712.95cm^21729e15
300.440.930.74cm^27e18

数据存储

在Pegasus中,数据存储的key是hashkey+sortkey: hashkey用于数据partition,同一hashkey的数据存储在同一replica server下的一块或多块(由rocksdb实际存储的状态决定:数据随机写入后,同一hashkey下连续的sortkey空间可能分布在多个不连续的sst文件中,进行full compact后,会分布在连续sst的内)连续区域; sortkey用于在这块(或多块)区域中做数据排序的依据。

经纬度经过坐标转换得到一维编码(字符串)后,就可以把这个一维编码作为key存储起来做GEO索引数据了,这里需要将这个一维编码拆分成hashkey和sortkey两部分,可以根据实际的业务场景采取不同的划分策略。

GEO索引数据独立于原始数据,两类数据存储在不同的table内,通过geo_client做数据同步,同时支持原生Pegasus API和GEO API访问。

下面讨论GEO索引数据的构造方式。

hashkey

hashkey直接由一维编码的前缀构成。比如在我们的LBS业务场景中,范围查询都是集中在10km半径内的圆形范围,实际测试结果是将hashkey长度定为14(1位face,1位分隔符/,12位Hilbert编码)能取得更好的性能。

最小搜索层为12

               cellid
|--------------32 bytes-------------|
|---14 bytes----|
    hashkey

sortkey

为了满足不同半径范围、不同精度的查询,我们把cellid剩下的18位全部放到sortkey中(这并不会给底层存储带来多少压力),这可以在应用层保持比较高的灵活性,而不用修改底层的数据。在进行较大范围的临近查询时,取更少的sortkey位数(对应的cellid更短)进行数据查询;进行较小范围的临近查询或点查询时,取更多的sortkey位数(对应的cellid更长)进行数据查询。

尽管在30层时,cell的面积已经足够小(<1cm^2),但仍有可能两条数据落在同一个cell里,所以需要区分不同的数据。这里,将原始数据的hashkey和sortkey联合起来,并追加在上述sortkey之后。

               cellid
|--------------32 bytes-------------|
|---14 bytes---||-----18 bytes------||--原始hashkey--||--原始sortkey--|
|--GEO hashkey-||----------------------GEO sortkey-------------------|

在相同地理范围内进行数据查询时,使用短cellid查询数据查询的范围大,查询的次数更少,但得到的在区域外的无用数据更多,反之亦然---这需要在查询次数与查询到的有用数据之间做权衡。

value

GEO API的value必须能够解析出经纬度,具体的解析方式参考自定义extrator

GEO索引数据的value跟原始数据的value完全相同。这里会存在一份冗余,但通常在相对廉价的磁盘存储介质上,这是可以接受的。

我们建议业务层在使用GEO API时value只存储小数据,大数据建议采用二次索引的方式。

数据更新

set

set操作会同时更新两个table的数据: Pegasus原始数据和GEO索引数据(数据构造方式如上所述)。

set操作的hashkey, sortkey是业务自己的格式,使用GEO API时并不做约束, 只是在geo client转存GEO索引数据时,会自动做如上所述的编码转换。

使用Redis API时, 参考 GEO API

实现上,set会首先尝试get出已有的数据,并将已有数据的GEO索引数据清理掉后,再写入新数据。因为新老数据的索引数据hashkey+sortkey可能不一样(即新老value根据extractor解析得到的经纬度不一样),若不清理,在进行地理搜索时将会搜索到脏数据。

del

del操作也会同时删除两个table的数据,原理同上。

数据查询

思路

直观地,集合中总的cell数量尽可能少,但同时单个cell面积尽可能小。比如:

s2_cap_1.png{:class=“img-responsive”}

虽然这样的结果更精确,但在实际测试中发现当参与计算的cell层级越大时,cellid的数量就越多,带来的client-server RPC次数更多,整个API消耗更大、延迟就越高。同时,在真实的应用场景中,太小的cell意义不大(没有数据)。

所以,在当前的Pegasus实现中,只联合使用两层cell,最大搜索层最小搜索层, 以12层和16层为例: