Pegasus GEO支持

背景

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

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

关于S2的实现原理细节请参考S2官网: http://s2geometry.io/

坐标转换

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

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

其中，"1"代表地球立方体投影的面索引，索引范围是0~5，如下图所示：

"/"是分隔符

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

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

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

编码精度

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

数据存储

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

经纬度经过坐标转换得到一维编码后，就可以把这个一维编码作为key存储起来做GEO索引了，这里需要将这个一维编码划分为hashkey和sortkey，可以根据实际的业务场景采取不同的划分策略。GEO索引数据独立于原始数据，两类数据存储在不同的table内，同时满足原生Pegasus API和新的GEO API。

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

hashkey

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

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

sortkey

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

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

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

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

value

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

数据查询

这里我们只讨论圆形区域的数据查询，其他的比如多边形区域的思想是类似的。

S2提供查询覆盖了指定区域的cell集合的API：

// Returns an S2CellUnion that covers the given region and satisfies the current options.
S2CellUnion GetCovering(const S2Region& region);

默认情况下，集合中总的cell数量尽可能少，但同时单个cell面积尽可能小。比如：

虽然这样的结果更精确，但在实际测试中发现当cell越小时，API返回越慢。同时，在真实的应用场景中，太小的cell意义不大，反而会增加cell的个数，这会带来RPC次数的增加。

所以，在当前的Pegasus实现中，只联合使用两层cell,12层和16层。

对于这些跟目标区域有交集的cell，我们将scan他的key空间。

对于整个hashkey所代表的cell都被目标区域覆盖时，扫描整个hashkey。比如，一个12层cell 1/223320022232被区域完全覆盖，则我们scan("1/223320022232", "", "")。

对于hashkey所代表的cell被目标区域部分覆盖时，按需扫描。比如，一个12层cell 1/223320022232的子区域0001,0002,0003,0100才跟目标区域相交时，则我们scan("1/223320022232", "0001", "0002")、scan("1/223320022232", "0100", "0100")。

灵活性

由于我们存储了完整的30层cellid，所以在实际使用中，可以按照自己的地理数据密度、延迟要求等情况调整数据scan的层级。

修改hashkey长度需要修改代码。注意：hashkey一旦确定，不可修改，因为数据的partition是按hashkey进行的。

// cell id at this level is the hash-key in pegasus
// `_min_level` is immutable after geo_client data has been inserted into DB.
const int _min_level = 12; // edge length at level 12 is about 2km

修改scan的最小cell层级可以直接修改配置文件或调用接口。

// API
void set_max_level(int level)
// config.ini
[geo_client.lib]
max_level = 16

API & redis proxy

Pegasus GEO特性的使用有两种方式，一是直接使用C++ geo client；二是使用redis proxy。

C++ geo client代码中有详细的API说明，这里不再赘述。

redis proxy的使用请参考Redis适配

自定义extrator

目前Pegasus支持从固定格式的value中解析经纬度。用户也可以根据自己的数据格式自定义解析方式。只需继承latlng_extractor类并实现其虚函数：

class latlng_extractor
{
public:
    virtual ~latlng_extractor() = default;
    virtual const char *name() const = 0;
    virtual const char *value_sample() const = 0;
    virtual bool extract_from_value(const std::string &value, S2LatLng &latlng) const = 0;
};

并在创建geo_client时，传递自定义的extractor实例指针，比如：

pegasus::geo::geo_client my_geo("config.ini",
                                cluster_name.c_str(),
                                app_name.c_str(),
                                geo_app_name.c_str(),
                                new pegasus::geo::latlng_extractor_for_lbs());

数据导入

有的使用场景是业务已经有普通的KV数据，需要根据这份已有的KV数据转换成如上述的数据格式，我们可以使用shell工具里的copy_data功能来实现。比如：

copy_data -c target_cluster -a temp -g

此时目标集群是target_cluster，目标表是temp，他存储上述的普通数据，目标GEO索引数据表是temp_geo，他存储上述的GEO索引数据。

在进行copy_data操作之前，目标集群以及两个目标表都需要提前创建好。

数据导入完成后就可以搭建redis_proxy了，具体的说明参考：redis适配，需要注意的是配置项：

[apps.proxy]
; if using GEO APIs, an extra table name which store geo index data should be appened, i.e.
arguments = redis_cluster temp temp_geo

benchmark

测试环境

机器配置：

• CPU：E5-2620v3 *2
• 内存：128GB
• 存储：480G SSD *8

• 网卡：1Gb集群配置：

• 节点数：5个replica server节点 (使用v1.9.2版本)

• 测试表的Partition数：128个
• 单条数据大小：120字节针对接口：

void async_search_radial(double lat_degrees,
                         double lng_degrees,
                         double radius_m,
                         int count,
                         SortType sort_type,
                         int timeout_ms,
                         geo_search_callback_t &&callback);

传递参数：

lat_degrees、lng_degrees：每次都选取北京五环内的随机点

radius_m：如下表第一列，单位米

count：-1，表示不限定结果数量

sort_type：不排序

测试结果