empiredan commented on code in PR #56: URL: https://github.com/apache/incubator-pegasus-website/pull/56#discussion_r1448399241
########## _docs/zh/api/geo.md: ########## @@ -296,23 +312,19 @@ void async_search_radial(double lat_degrees, ``` 传递参数： - -lat_degrees、lng_degrees：每次都选取北京五环内的随机点 - -radius_m：如下表第一列，单位米 - -count：-1，表示不限定结果数量 - -sort_type：不排序 +- lat_degrees、lng_degrees：每次都选取北京五环内的随机点 +- radius_m：如下表第一列，单位米 +- count：-1，表示不限定结果数量 +- sort_type：不排序 ### 测试结果 -| 半径(m) | 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 | +| radius(m) | P50(ms) | P75(ms) | P99(ms) | P99.9(ms) | Avg result count | QPS per node | Review Comment: ```suggestion | Radius(m) | P50(ms) | P75(ms) | P99(ms) | P99.9(ms) | Avg result count | QPS per node | ``` ########## _docs/zh/api/geo.md: ########## @@ -221,19 +237,21 @@ min_level = 12 ## 自定义extrator -目前Pegasus支持从固定格式的value中解析经纬度。经纬度以字符串形式嵌入在value中，以`|`分割， 比如:`.*|115.886447|41.269031|.*`，他们的索引由配置文件中的`latitude_index`和`longitude_index`确定。 +目前 Pegasus 支持从固定格式的 value 中解析出经纬度。经纬度以字符串形式嵌入在 value 中，以`|`分割。 + +比如:`.*|115.886447|41.269031|.*`，经纬在 value 中的索引由配置文件中的`latitude_index`和`longitude_index`确定。 -## API & redis proxy +## API & Redis Proxy -Pegasus GEO特性的使用有两种方式，一是直接使用C++ geo client；二是使用redis proxy。 +Pegasus GEO 特性的使用有两种方式，一是直接使用 C++ GEO client，二是使用 Redis Proxy。 Review Comment: ```suggestion Pegasus GEO 特性的使用有两种方式，一是直接使用 C++ GEO Client，二是使用 Redis Proxy。 ``` ########## _docs/zh/api/geo.md: ########## @@ -2,197 +2,211 @@ permalink: api/geo --- -# Pegasus GEO支持 +# Pegasus GEO 支持 ## 背景 -业务数据跟Pegasus的普通数据类似，由hashkey、sortkey、value组成。但业务数据隐含有地理信息，比如value中包含有经纬度(latitude,longitude)，需要提供API进行GEO特性的支持，比如给定一个中心点坐标和一个半径，查找这个范围内的所有数据；给定两条数据的hashkey和sortkey，求这两条数据地理上的距离。 +用户数据存储在 Pegasus 中，由 hashkey、sortkey、value 组成。但用户数据中含有地理信息，比如 value 中包含有经纬度，需要 Pegasus 提供 API 进行 GEO 特性的支持。比如给定一个中心点坐标和一个半径，查找这个范围内的所有数据；给定两条数据的 hashkey 和 sortkey，求这两条数据地理上的距离等。 -pegasus的GEO(Geographic)支持使用了[S2](https://github.com/google/s2geometry)库, 主要利用其中将二维地理坐标（经纬度）与一维编码的相互转换、基于圆形的范围查询、Hilbert曲线规则等特性。在Pegasus中如何充分利用S2的这些特性，并结合Pegasus的数据分布、数据存储特性，是本文的阐述重点。 +Pegasus 的 GEO (Geographic) 支持使用了 [S2](https://github.com/google/s2geometry) 库, 主要用于将二维地理坐标（经度 + 纬度）与一维编码的相互转换、基于圆形的范围查询、Hilbert 曲线规则等特性。 -关于S2的实现原理细节请参考[S2官网](http://s2geometry.io/) +本文将说明在 Pegasus 中是如何充分利用 S2 的特性，并结合 Pegasus 的数据分布与数据存储特性，来支持 GEO 特性的。 + +关于 S2 的实现原理请参考 [S2官网](http://s2geometry.io/)。 ## 坐标转换 -在S2中，可以把二维经纬度编码成一维编码，一维编码由两部分组成：立方体面、平面坐标编码，比如： +在 S2 中，可以把二维经纬度编码成一维编码，一维编码由两部分组成：立方体面、平面坐标编码，比如： -经纬度(116.334441,40.030202)的编码是：`1/223320022232200331010110113301`（32位），在S2中称为cellid。 +经纬度(116.334441, 40.030202)的编码是：`1/223320022232200331010110113301`（总共32位），这个编码在 S2 中称为 **CellId**。 -其中，首位的`1`代表地球立方体投影的面索引，索引范围是0~5，如下图所示： +其中： +- 首位的`1`代表地球立方体投影的面索引，索引范围是0~5，如下图所示： {:class="img-responsive"} - -`/`是分隔符 - -`223320022232200331010110113301`(30位)是经纬度坐标经过一系列转换得到的编码，具体转换过程这里不详细描述。需要指出的是，这是一个名为Hilbert曲线编码，它最大的特点是具有稳定性、连续性。 +- `/`是分隔符 +- `223320022232200331010110113301`(30位)，是经纬度坐标经过一系列转换得到的编码，具体转换过程这里不详细描述。需要指出的是，这是一个名为 Hilbert 曲线编码，它最大的特点是具有稳定性、连续性。 {:class="img-responsive"} -编码由前往后按层进行，完整编码是前缀编码的子区域，每个父区域由4个子区域组成，比如`00`,`01`,`02`,`03`是`0`的子区域，且前者的区域范围的并集就是后者的区域范围。最多有30层，每层都有相应的cellid集合，高层cell是底层cell的父区域，高层cellid是底层cellid的前缀。 - -编码可以看作是一个4进制的数值编码，同时**在数值上连续的值，在地理位置上也是连续的**。 +S2 中的 Hilbert 曲线编码： +- 编码可以看作是一个4进制的数值编码 +- 编码由左往右按层进行，最多30层 +- 一个编码代表地理上的一个方块区域，编码越长，区域越小 +- 完整编码是前缀编码的子区域，每个父区域由4个子区域组成，比如`00`,`01`,`02`,`03`是`0`的子区域，且前者的区域范围的并集就是后者的区域范围 +- 在数值上连续的值，在地理位置上也是连续的，比如`00`和`01`的区域范围是相邻的，`0122`和`0123`的区域范围也是相邻的 ## 编码精度 -S2中的Hilbert曲线编码由30位组成，每一位代表一层划分。下表是各层单个cell的面积和cell个数。 +S2 中的 Hilbert 曲线编码由30位组成，每一位代表一层划分。下表是各层单个 cell 的面积和 cell 个数。 | **level** | **min area** | **max area** | **average area** | **units** | **Number of cells** | -| --------- | ------------ | ------------ | ---------------- | --------- | ------------------- | -| 00 | 85011012.19 | 85011012.19 | 85011012.19 | km^2 | 6 | -| 01 | 21252753.05 | 21252753.05 | 21252753.05 | km^2 | 24 | -| 02 | 4919708.23 | 6026521.16 | 5313188.26 | km^2 | 96 | -| 03 | 1055377.48 | 1646455.50 | 1328297.07 | km^2 | 384 | -| 04 | 231564.06 | 413918.15 | 332074.27 | km^2 | 1536 | -| 05 | 53798.67 | 104297.91 | 83018.57 | km^2 | 6K | -| 06 | 12948.81 | 26113.30 | 20754.64 | km^2 | 24K | -| 07 | 3175.44 | 6529.09 | 5188.66 | km^2 | 98K | -| 08 | 786.20 | 1632.45 | 1297.17 | km^2 | 393K | -| 09 | 195.59 | 408.12 | 324.29 | km^2 | 1573K | -| 10 | 48.78 | 102.03 | 81.07 | km^2 | 6M | -| 11 | 12.18 | 25.51 | 20.27 | km^2 | 25M | -| 12 | 3.04 | 6.38 | 5.07 | km^2 | 100M | -| 13 | 0.76 | 1.59 | 1.27 | km^2 | 402M | -| 14 | 0.19 | 0.40 | 0.32 | km^2 | 1610M | -| 15 | 47520.30 | 99638.93 | 79172.67 | m^2 | 6B | -| 16 | 11880.08 | 24909.73 | 19793.17 | m^2 | 25B | -| 17 | 2970.02 | 6227.43 | 4948.29 | m^2 | 103B | -| 18 | 742.50 | 1556.86 | 1237.07 | m^2 | 412B | -| 19 | 185.63 | 389.21 | 309.27 | m^2 | 1649B | -| 20 | 46.41 | 97.30 | 77.32 | m^2 | 7T | -| 21 | 11.60 | 24.33 | 19.33 | m^2 | 26T | -| 22 | 2.90 | 6.08 | 4.83 | m^2 | 105T | -| 23 | 0.73 | 1.52 | 1.21 | m^2 | 422T | -| 24 | 0.18 | 0.38 | 0.30 | m^2 | 1689T | -| 25 | 453.19 | 950.23 | 755.05 | cm^2 | 7e15 | -| 26 | 113.30 | 237.56 | 188.76 | cm^2 | 27e15 | -| 27 | 28.32 | 59.39 | 47.19 | cm^2 | 108e15 | -| 28 | 7.08 | 14.85 | 11.80 | cm^2 | 432e15 | -| 29 | 1.77 | 3.71 | 2.95 | cm^2 | 1729e15 | -| 30 | 0.44 | 0.93 | 0.74 | cm^2 | 7e18 | - +|-----------|--------------|--------------|------------------|-----------|---------------------| +| 00 | 85011012.19 | 85011012.19 | 85011012.19 | km^2 | 6 | +| 01 | 21252753.05 | 21252753.05 | 21252753.05 | km^2 | 24 | +| 02 | 4919708.23 | 6026521.16 | 5313188.26 | km^2 | 96 | +| 03 | 1055377.48 | 1646455.50 | 1328297.07 | km^2 | 384 | +| 04 | 231564.06 | 413918.15 | 332074.27 | km^2 | 1536 | +| 05 | 53798.67 | 104297.91 | 83018.57 | km^2 | 6K | +| 06 | 12948.81 | 26113.30 | 20754.64 | km^2 | 24K | +| 07 | 3175.44 | 6529.09 | 5188.66 | km^2 | 98K | +| 08 | 786.20 | 1632.45 | 1297.17 | km^2 | 393K | +| 09 | 195.59 | 408.12 | 324.29 | km^2 | 1573K | +| 10 | 48.78 | 102.03 | 81.07 | km^2 | 6M | +| 11 | 12.18 | 25.51 | 20.27 | km^2 | 25M | +| 12 | 3.04 | 6.38 | 5.07 | km^2 | 100M | +| 13 | 0.76 | 1.59 | 1.27 | km^2 | 402M | +| 14 | 0.19 | 0.40 | 0.32 | km^2 | 1610M | +| 15 | 47520.30 | 99638.93 | 79172.67 | m^2 | 6B | +| 16 | 11880.08 | 24909.73 | 19793.17 | m^2 | 25B | +| 17 | 2970.02 | 6227.43 | 4948.29 | m^2 | 103B | +| 18 | 742.50 | 1556.86 | 1237.07 | m^2 | 412B | +| 19 | 185.63 | 389.21 | 309.27 | m^2 | 1649B | +| 20 | 46.41 | 97.30 | 77.32 | m^2 | 7T | +| 21 | 11.60 | 24.33 | 19.33 | m^2 | 26T | +| 22 | 2.90 | 6.08 | 4.83 | m^2 | 105T | +| 23 | 0.73 | 1.52 | 1.21 | m^2 | 422T | +| 24 | 0.18 | 0.38 | 0.30 | m^2 | 1689T | +| 25 | 453.19 | 950.23 | 755.05 | cm^2 | 7e15 | +| 26 | 113.30 | 237.56 | 188.76 | cm^2 | 27e15 | +| 27 | 28.32 | 59.39 | 47.19 | cm^2 | 108e15 | +| 28 | 7.08 | 14.85 | 11.80 | cm^2 | 432e15 | +| 29 | 1.77 | 3.71 | 2.95 | cm^2 | 1729e15 | +| 30 | 0.44 | 0.93 | 0.74 | cm^2 | 7e18 | ## 数据存储 -在Pegasus中，数据存储的key是hashkey+sortkey: hashkey用于数据partition，同一hashkey的数据存储在同一replica server下的一块或多块（由rocksdb实际存储的状态决定：数据随机写入后，同一hashkey下连续的sortkey空间可能分布在多个不连续的sst文件中，进行full compact后，会分布在连续sst的内）连续区域; sortkey用于在这块（或多块）区域中做数据排序的依据。 +在 Pegasus 中，数据存储的 key 是 hashkey + sortkey：hashkey 用于确定数据所处的 partition，同一 hashkey 的数据存储在同一 Replica Server 的一块逻辑连续的区域中，sortkey 用于在这块区域中做数据排序。 -经纬度经过坐标转换得到一维编码(字符串)后，就可以把这个一维编码作为key存储起来做**GEO索引数据**了，这里需要将这个一维编码拆分成hashkey和sortkey两部分，可以根据实际的业务场景采取不同的划分策略。 +经纬度经过坐标转换得到一维编码 CellId 后，就可以把这个一维编码作为 key 存储起来做**GEO索引数据**了，Pegasus 将这个一维编码拆分成 hashkey 和 sortkey 两部分，可以根据实际的用户场景采取不同的位数划分策略。 -GEO索引数据独立于原始数据，两类数据存储在不同的table内，通过[geo_client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h)做数据同步，同时支持原生Pegasus API和GEO API访问。 +GEO 索引数据独立于原始数据，两类数据存储在不同的 Pegasus 表中，通过 [GEO client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h) 做数据同步，同时支持原生 Pegasus API 和 GEO API 的访问。 -下面讨论GEO索引数据的构造方式。 +所以，在使用 Pegasus GEO 特性时，需要创建两个 Pegasus 表，一个是原始表，用于存储用户写入的原始数据，一个是 GEO 索引表，用于存储 GEO client 自动转换原始数据生成的 GEO 索引数据。 Review Comment: ```suggestion 所以，在使用 Pegasus GEO 特性时，需要创建两个 Pegasus 表，一个是原始表，用于存储用户写入的原始数据，一个是 GEO 索引表，用于存储 GEO Client 自动转换原始数据生成的 GEO 索引数据。 ``` ########## _docs/zh/api/geo.md: ########## @@ -2,197 +2,211 @@ permalink: api/geo --- -# Pegasus GEO支持 +# Pegasus GEO 支持 ## 背景 -业务数据跟Pegasus的普通数据类似，由hashkey、sortkey、value组成。但业务数据隐含有地理信息，比如value中包含有经纬度(latitude,longitude)，需要提供API进行GEO特性的支持，比如给定一个中心点坐标和一个半径，查找这个范围内的所有数据；给定两条数据的hashkey和sortkey，求这两条数据地理上的距离。 +用户数据存储在 Pegasus 中，由 hashkey、sortkey、value 组成。但用户数据中含有地理信息，比如 value 中包含有经纬度，需要 Pegasus 提供 API 进行 GEO 特性的支持。比如给定一个中心点坐标和一个半径，查找这个范围内的所有数据；给定两条数据的 hashkey 和 sortkey，求这两条数据地理上的距离等。 -pegasus的GEO(Geographic)支持使用了[S2](https://github.com/google/s2geometry)库, 主要利用其中将二维地理坐标（经纬度）与一维编码的相互转换、基于圆形的范围查询、Hilbert曲线规则等特性。在Pegasus中如何充分利用S2的这些特性，并结合Pegasus的数据分布、数据存储特性，是本文的阐述重点。 +Pegasus 的 GEO (Geographic) 支持使用了 [S2](https://github.com/google/s2geometry) 库, 主要用于将二维地理坐标（经度 + 纬度）与一维编码的相互转换、基于圆形的范围查询、Hilbert 曲线规则等特性。 -关于S2的实现原理细节请参考[S2官网](http://s2geometry.io/) +本文将说明在 Pegasus 中是如何充分利用 S2 的特性，并结合 Pegasus 的数据分布与数据存储特性，来支持 GEO 特性的。 + +关于 S2 的实现原理请参考 [S2官网](http://s2geometry.io/)。 ## 坐标转换 -在S2中，可以把二维经纬度编码成一维编码，一维编码由两部分组成：立方体面、平面坐标编码，比如： +在 S2 中，可以把二维经纬度编码成一维编码，一维编码由两部分组成：立方体面、平面坐标编码，比如： -经纬度(116.334441,40.030202)的编码是：`1/223320022232200331010110113301`（32位），在S2中称为cellid。 +经纬度(116.334441, 40.030202)的编码是：`1/223320022232200331010110113301`（总共32位），这个编码在 S2 中称为 **CellId**。 -其中，首位的`1`代表地球立方体投影的面索引，索引范围是0~5，如下图所示： +其中： +- 首位的`1`代表地球立方体投影的面索引，索引范围是0~5，如下图所示： {:class="img-responsive"} - -`/`是分隔符 - -`223320022232200331010110113301`(30位)是经纬度坐标经过一系列转换得到的编码，具体转换过程这里不详细描述。需要指出的是，这是一个名为Hilbert曲线编码，它最大的特点是具有稳定性、连续性。 +- `/`是分隔符 +- `223320022232200331010110113301`(30位)，是经纬度坐标经过一系列转换得到的编码，具体转换过程这里不详细描述。需要指出的是，这是一个名为 Hilbert 曲线编码，它最大的特点是具有稳定性、连续性。 {:class="img-responsive"} -编码由前往后按层进行，完整编码是前缀编码的子区域，每个父区域由4个子区域组成，比如`00`,`01`,`02`,`03`是`0`的子区域，且前者的区域范围的并集就是后者的区域范围。最多有30层，每层都有相应的cellid集合，高层cell是底层cell的父区域，高层cellid是底层cellid的前缀。 - -编码可以看作是一个4进制的数值编码，同时**在数值上连续的值，在地理位置上也是连续的**。 +S2 中的 Hilbert 曲线编码： +- 编码可以看作是一个4进制的数值编码 +- 编码由左往右按层进行，最多30层 +- 一个编码代表地理上的一个方块区域，编码越长，区域越小 +- 完整编码是前缀编码的子区域，每个父区域由4个子区域组成，比如`00`,`01`,`02`,`03`是`0`的子区域，且前者的区域范围的并集就是后者的区域范围 +- 在数值上连续的值，在地理位置上也是连续的，比如`00`和`01`的区域范围是相邻的，`0122`和`0123`的区域范围也是相邻的 ## 编码精度 -S2中的Hilbert曲线编码由30位组成，每一位代表一层划分。下表是各层单个cell的面积和cell个数。 +S2 中的 Hilbert 曲线编码由30位组成，每一位代表一层划分。下表是各层单个 cell 的面积和 cell 个数。 | **level** | **min area** | **max area** | **average area** | **units** | **Number of cells** | -| --------- | ------------ | ------------ | ---------------- | --------- | ------------------- | -| 00 | 85011012.19 | 85011012.19 | 85011012.19 | km^2 | 6 | -| 01 | 21252753.05 | 21252753.05 | 21252753.05 | km^2 | 24 | -| 02 | 4919708.23 | 6026521.16 | 5313188.26 | km^2 | 96 | -| 03 | 1055377.48 | 1646455.50 | 1328297.07 | km^2 | 384 | -| 04 | 231564.06 | 413918.15 | 332074.27 | km^2 | 1536 | -| 05 | 53798.67 | 104297.91 | 83018.57 | km^2 | 6K | -| 06 | 12948.81 | 26113.30 | 20754.64 | km^2 | 24K | -| 07 | 3175.44 | 6529.09 | 5188.66 | km^2 | 98K | -| 08 | 786.20 | 1632.45 | 1297.17 | km^2 | 393K | -| 09 | 195.59 | 408.12 | 324.29 | km^2 | 1573K | -| 10 | 48.78 | 102.03 | 81.07 | km^2 | 6M | -| 11 | 12.18 | 25.51 | 20.27 | km^2 | 25M | -| 12 | 3.04 | 6.38 | 5.07 | km^2 | 100M | -| 13 | 0.76 | 1.59 | 1.27 | km^2 | 402M | -| 14 | 0.19 | 0.40 | 0.32 | km^2 | 1610M | -| 15 | 47520.30 | 99638.93 | 79172.67 | m^2 | 6B | -| 16 | 11880.08 | 24909.73 | 19793.17 | m^2 | 25B | -| 17 | 2970.02 | 6227.43 | 4948.29 | m^2 | 103B | -| 18 | 742.50 | 1556.86 | 1237.07 | m^2 | 412B | -| 19 | 185.63 | 389.21 | 309.27 | m^2 | 1649B | -| 20 | 46.41 | 97.30 | 77.32 | m^2 | 7T | -| 21 | 11.60 | 24.33 | 19.33 | m^2 | 26T | -| 22 | 2.90 | 6.08 | 4.83 | m^2 | 105T | -| 23 | 0.73 | 1.52 | 1.21 | m^2 | 422T | -| 24 | 0.18 | 0.38 | 0.30 | m^2 | 1689T | -| 25 | 453.19 | 950.23 | 755.05 | cm^2 | 7e15 | -| 26 | 113.30 | 237.56 | 188.76 | cm^2 | 27e15 | -| 27 | 28.32 | 59.39 | 47.19 | cm^2 | 108e15 | -| 28 | 7.08 | 14.85 | 11.80 | cm^2 | 432e15 | -| 29 | 1.77 | 3.71 | 2.95 | cm^2 | 1729e15 | -| 30 | 0.44 | 0.93 | 0.74 | cm^2 | 7e18 | - +|-----------|--------------|--------------|------------------|-----------|---------------------| +| 00 | 85011012.19 | 85011012.19 | 85011012.19 | km^2 | 6 | +| 01 | 21252753.05 | 21252753.05 | 21252753.05 | km^2 | 24 | +| 02 | 4919708.23 | 6026521.16 | 5313188.26 | km^2 | 96 | +| 03 | 1055377.48 | 1646455.50 | 1328297.07 | km^2 | 384 | +| 04 | 231564.06 | 413918.15 | 332074.27 | km^2 | 1536 | +| 05 | 53798.67 | 104297.91 | 83018.57 | km^2 | 6K | +| 06 | 12948.81 | 26113.30 | 20754.64 | km^2 | 24K | +| 07 | 3175.44 | 6529.09 | 5188.66 | km^2 | 98K | +| 08 | 786.20 | 1632.45 | 1297.17 | km^2 | 393K | +| 09 | 195.59 | 408.12 | 324.29 | km^2 | 1573K | +| 10 | 48.78 | 102.03 | 81.07 | km^2 | 6M | +| 11 | 12.18 | 25.51 | 20.27 | km^2 | 25M | +| 12 | 3.04 | 6.38 | 5.07 | km^2 | 100M | +| 13 | 0.76 | 1.59 | 1.27 | km^2 | 402M | +| 14 | 0.19 | 0.40 | 0.32 | km^2 | 1610M | +| 15 | 47520.30 | 99638.93 | 79172.67 | m^2 | 6B | +| 16 | 11880.08 | 24909.73 | 19793.17 | m^2 | 25B | +| 17 | 2970.02 | 6227.43 | 4948.29 | m^2 | 103B | +| 18 | 742.50 | 1556.86 | 1237.07 | m^2 | 412B | +| 19 | 185.63 | 389.21 | 309.27 | m^2 | 1649B | +| 20 | 46.41 | 97.30 | 77.32 | m^2 | 7T | +| 21 | 11.60 | 24.33 | 19.33 | m^2 | 26T | +| 22 | 2.90 | 6.08 | 4.83 | m^2 | 105T | +| 23 | 0.73 | 1.52 | 1.21 | m^2 | 422T | +| 24 | 0.18 | 0.38 | 0.30 | m^2 | 1689T | +| 25 | 453.19 | 950.23 | 755.05 | cm^2 | 7e15 | +| 26 | 113.30 | 237.56 | 188.76 | cm^2 | 27e15 | +| 27 | 28.32 | 59.39 | 47.19 | cm^2 | 108e15 | +| 28 | 7.08 | 14.85 | 11.80 | cm^2 | 432e15 | +| 29 | 1.77 | 3.71 | 2.95 | cm^2 | 1729e15 | +| 30 | 0.44 | 0.93 | 0.74 | cm^2 | 7e18 | ## 数据存储 -在Pegasus中，数据存储的key是hashkey+sortkey: hashkey用于数据partition，同一hashkey的数据存储在同一replica server下的一块或多块（由rocksdb实际存储的状态决定：数据随机写入后，同一hashkey下连续的sortkey空间可能分布在多个不连续的sst文件中，进行full compact后，会分布在连续sst的内）连续区域; sortkey用于在这块（或多块）区域中做数据排序的依据。 +在 Pegasus 中，数据存储的 key 是 hashkey + sortkey：hashkey 用于确定数据所处的 partition，同一 hashkey 的数据存储在同一 Replica Server 的一块逻辑连续的区域中，sortkey 用于在这块区域中做数据排序。 -经纬度经过坐标转换得到一维编码(字符串)后，就可以把这个一维编码作为key存储起来做**GEO索引数据**了，这里需要将这个一维编码拆分成hashkey和sortkey两部分，可以根据实际的业务场景采取不同的划分策略。 +经纬度经过坐标转换得到一维编码 CellId 后，就可以把这个一维编码作为 key 存储起来做**GEO索引数据**了，Pegasus 将这个一维编码拆分成 hashkey 和 sortkey 两部分，可以根据实际的用户场景采取不同的位数划分策略。 -GEO索引数据独立于原始数据，两类数据存储在不同的table内，通过[geo_client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h)做数据同步，同时支持原生Pegasus API和GEO API访问。 +GEO 索引数据独立于原始数据，两类数据存储在不同的 Pegasus 表中，通过 [GEO client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h) 做数据同步，同时支持原生 Pegasus API 和 GEO API 的访问。 Review Comment: ```suggestion GEO 索引数据独立于原始数据，两类数据存储在不同的 Pegasus 表中，通过 [GEO Client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h) 做数据同步，同时支持原生 Pegasus API 和 GEO API 的访问。 ``` ########## _docs/zh/api/geo.md: ########## @@ -2,197 +2,211 @@ permalink: api/geo --- -# Pegasus GEO支持 +# Pegasus GEO 支持 ## 背景 -业务数据跟Pegasus的普通数据类似，由hashkey、sortkey、value组成。但业务数据隐含有地理信息，比如value中包含有经纬度(latitude,longitude)，需要提供API进行GEO特性的支持，比如给定一个中心点坐标和一个半径，查找这个范围内的所有数据；给定两条数据的hashkey和sortkey，求这两条数据地理上的距离。 +用户数据存储在 Pegasus 中，由 hashkey、sortkey、value 组成。但用户数据中含有地理信息，比如 value 中包含有经纬度，需要 Pegasus 提供 API 进行 GEO 特性的支持。比如给定一个中心点坐标和一个半径，查找这个范围内的所有数据；给定两条数据的 hashkey 和 sortkey，求这两条数据地理上的距离等。 -pegasus的GEO(Geographic)支持使用了[S2](https://github.com/google/s2geometry)库, 主要利用其中将二维地理坐标（经纬度）与一维编码的相互转换、基于圆形的范围查询、Hilbert曲线规则等特性。在Pegasus中如何充分利用S2的这些特性，并结合Pegasus的数据分布、数据存储特性，是本文的阐述重点。 +Pegasus 的 GEO (Geographic) 支持使用了 [S2](https://github.com/google/s2geometry) 库, 主要用于将二维地理坐标（经度 + 纬度）与一维编码的相互转换、基于圆形的范围查询、Hilbert 曲线规则等特性。 -关于S2的实现原理细节请参考[S2官网](http://s2geometry.io/) +本文将说明在 Pegasus 中是如何充分利用 S2 的特性，并结合 Pegasus 的数据分布与数据存储特性，来支持 GEO 特性的。 + +关于 S2 的实现原理请参考 [S2官网](http://s2geometry.io/)。 ## 坐标转换 -在S2中，可以把二维经纬度编码成一维编码，一维编码由两部分组成：立方体面、平面坐标编码，比如： +在 S2 中，可以把二维经纬度编码成一维编码，一维编码由两部分组成：立方体面、平面坐标编码，比如： -经纬度(116.334441,40.030202)的编码是：`1/223320022232200331010110113301`（32位），在S2中称为cellid。 +经纬度(116.334441, 40.030202)的编码是：`1/223320022232200331010110113301`（总共32位），这个编码在 S2 中称为 **CellId**。 -其中，首位的`1`代表地球立方体投影的面索引，索引范围是0~5，如下图所示： +其中： +- 首位的`1`代表地球立方体投影的面索引，索引范围是0~5，如下图所示： {:class="img-responsive"} - -`/`是分隔符 - -`223320022232200331010110113301`(30位)是经纬度坐标经过一系列转换得到的编码，具体转换过程这里不详细描述。需要指出的是，这是一个名为Hilbert曲线编码，它最大的特点是具有稳定性、连续性。 +- `/`是分隔符 +- `223320022232200331010110113301`(30位)，是经纬度坐标经过一系列转换得到的编码，具体转换过程这里不详细描述。需要指出的是，这是一个名为 Hilbert 曲线编码，它最大的特点是具有稳定性、连续性。 {:class="img-responsive"} -编码由前往后按层进行，完整编码是前缀编码的子区域，每个父区域由4个子区域组成，比如`00`,`01`,`02`,`03`是`0`的子区域，且前者的区域范围的并集就是后者的区域范围。最多有30层，每层都有相应的cellid集合，高层cell是底层cell的父区域，高层cellid是底层cellid的前缀。 - -编码可以看作是一个4进制的数值编码，同时**在数值上连续的值，在地理位置上也是连续的**。 +S2 中的 Hilbert 曲线编码： +- 编码可以看作是一个4进制的数值编码 +- 编码由左往右按层进行，最多30层 +- 一个编码代表地理上的一个方块区域，编码越长，区域越小 +- 完整编码是前缀编码的子区域，每个父区域由4个子区域组成，比如`00`,`01`,`02`,`03`是`0`的子区域，且前者的区域范围的并集就是后者的区域范围 +- 在数值上连续的值，在地理位置上也是连续的，比如`00`和`01`的区域范围是相邻的，`0122`和`0123`的区域范围也是相邻的 ## 编码精度 -S2中的Hilbert曲线编码由30位组成，每一位代表一层划分。下表是各层单个cell的面积和cell个数。 +S2 中的 Hilbert 曲线编码由30位组成，每一位代表一层划分。下表是各层单个 cell 的面积和 cell 个数。 | **level** | **min area** | **max area** | **average area** | **units** | **Number of cells** | -| --------- | ------------ | ------------ | ---------------- | --------- | ------------------- | -| 00 | 85011012.19 | 85011012.19 | 85011012.19 | km^2 | 6 | -| 01 | 21252753.05 | 21252753.05 | 21252753.05 | km^2 | 24 | -| 02 | 4919708.23 | 6026521.16 | 5313188.26 | km^2 | 96 | -| 03 | 1055377.48 | 1646455.50 | 1328297.07 | km^2 | 384 | -| 04 | 231564.06 | 413918.15 | 332074.27 | km^2 | 1536 | -| 05 | 53798.67 | 104297.91 | 83018.57 | km^2 | 6K | -| 06 | 12948.81 | 26113.30 | 20754.64 | km^2 | 24K | -| 07 | 3175.44 | 6529.09 | 5188.66 | km^2 | 98K | -| 08 | 786.20 | 1632.45 | 1297.17 | km^2 | 393K | -| 09 | 195.59 | 408.12 | 324.29 | km^2 | 1573K | -| 10 | 48.78 | 102.03 | 81.07 | km^2 | 6M | -| 11 | 12.18 | 25.51 | 20.27 | km^2 | 25M | -| 12 | 3.04 | 6.38 | 5.07 | km^2 | 100M | -| 13 | 0.76 | 1.59 | 1.27 | km^2 | 402M | -| 14 | 0.19 | 0.40 | 0.32 | km^2 | 1610M | -| 15 | 47520.30 | 99638.93 | 79172.67 | m^2 | 6B | -| 16 | 11880.08 | 24909.73 | 19793.17 | m^2 | 25B | -| 17 | 2970.02 | 6227.43 | 4948.29 | m^2 | 103B | -| 18 | 742.50 | 1556.86 | 1237.07 | m^2 | 412B | -| 19 | 185.63 | 389.21 | 309.27 | m^2 | 1649B | -| 20 | 46.41 | 97.30 | 77.32 | m^2 | 7T | -| 21 | 11.60 | 24.33 | 19.33 | m^2 | 26T | -| 22 | 2.90 | 6.08 | 4.83 | m^2 | 105T | -| 23 | 0.73 | 1.52 | 1.21 | m^2 | 422T | -| 24 | 0.18 | 0.38 | 0.30 | m^2 | 1689T | -| 25 | 453.19 | 950.23 | 755.05 | cm^2 | 7e15 | -| 26 | 113.30 | 237.56 | 188.76 | cm^2 | 27e15 | -| 27 | 28.32 | 59.39 | 47.19 | cm^2 | 108e15 | -| 28 | 7.08 | 14.85 | 11.80 | cm^2 | 432e15 | -| 29 | 1.77 | 3.71 | 2.95 | cm^2 | 1729e15 | -| 30 | 0.44 | 0.93 | 0.74 | cm^2 | 7e18 | - +|-----------|--------------|--------------|------------------|-----------|---------------------| +| 00 | 85011012.19 | 85011012.19 | 85011012.19 | km^2 | 6 | +| 01 | 21252753.05 | 21252753.05 | 21252753.05 | km^2 | 24 | +| 02 | 4919708.23 | 6026521.16 | 5313188.26 | km^2 | 96 | +| 03 | 1055377.48 | 1646455.50 | 1328297.07 | km^2 | 384 | +| 04 | 231564.06 | 413918.15 | 332074.27 | km^2 | 1536 | +| 05 | 53798.67 | 104297.91 | 83018.57 | km^2 | 6K | +| 06 | 12948.81 | 26113.30 | 20754.64 | km^2 | 24K | +| 07 | 3175.44 | 6529.09 | 5188.66 | km^2 | 98K | +| 08 | 786.20 | 1632.45 | 1297.17 | km^2 | 393K | +| 09 | 195.59 | 408.12 | 324.29 | km^2 | 1573K | +| 10 | 48.78 | 102.03 | 81.07 | km^2 | 6M | +| 11 | 12.18 | 25.51 | 20.27 | km^2 | 25M | +| 12 | 3.04 | 6.38 | 5.07 | km^2 | 100M | +| 13 | 0.76 | 1.59 | 1.27 | km^2 | 402M | +| 14 | 0.19 | 0.40 | 0.32 | km^2 | 1610M | +| 15 | 47520.30 | 99638.93 | 79172.67 | m^2 | 6B | +| 16 | 11880.08 | 24909.73 | 19793.17 | m^2 | 25B | +| 17 | 2970.02 | 6227.43 | 4948.29 | m^2 | 103B | +| 18 | 742.50 | 1556.86 | 1237.07 | m^2 | 412B | +| 19 | 185.63 | 389.21 | 309.27 | m^2 | 1649B | +| 20 | 46.41 | 97.30 | 77.32 | m^2 | 7T | +| 21 | 11.60 | 24.33 | 19.33 | m^2 | 26T | +| 22 | 2.90 | 6.08 | 4.83 | m^2 | 105T | +| 23 | 0.73 | 1.52 | 1.21 | m^2 | 422T | +| 24 | 0.18 | 0.38 | 0.30 | m^2 | 1689T | +| 25 | 453.19 | 950.23 | 755.05 | cm^2 | 7e15 | +| 26 | 113.30 | 237.56 | 188.76 | cm^2 | 27e15 | +| 27 | 28.32 | 59.39 | 47.19 | cm^2 | 108e15 | +| 28 | 7.08 | 14.85 | 11.80 | cm^2 | 432e15 | +| 29 | 1.77 | 3.71 | 2.95 | cm^2 | 1729e15 | +| 30 | 0.44 | 0.93 | 0.74 | cm^2 | 7e18 | ## 数据存储 -在Pegasus中，数据存储的key是hashkey+sortkey: hashkey用于数据partition，同一hashkey的数据存储在同一replica server下的一块或多块（由rocksdb实际存储的状态决定：数据随机写入后，同一hashkey下连续的sortkey空间可能分布在多个不连续的sst文件中，进行full compact后，会分布在连续sst的内）连续区域; sortkey用于在这块（或多块）区域中做数据排序的依据。 +在 Pegasus 中，数据存储的 key 是 hashkey + sortkey：hashkey 用于确定数据所处的 partition，同一 hashkey 的数据存储在同一 Replica Server 的一块逻辑连续的区域中，sortkey 用于在这块区域中做数据排序。 -经纬度经过坐标转换得到一维编码(字符串)后，就可以把这个一维编码作为key存储起来做**GEO索引数据**了，这里需要将这个一维编码拆分成hashkey和sortkey两部分，可以根据实际的业务场景采取不同的划分策略。 +经纬度经过坐标转换得到一维编码 CellId 后，就可以把这个一维编码作为 key 存储起来做**GEO索引数据**了，Pegasus 将这个一维编码拆分成 hashkey 和 sortkey 两部分，可以根据实际的用户场景采取不同的位数划分策略。 -GEO索引数据独立于原始数据，两类数据存储在不同的table内，通过[geo_client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h)做数据同步，同时支持原生Pegasus API和GEO API访问。 +GEO 索引数据独立于原始数据，两类数据存储在不同的 Pegasus 表中，通过 [GEO client](https://github.com/apache/incubator-pegasus/blob/master/src/geo/lib/geo_client.h) 做数据同步，同时支持原生 Pegasus API 和 GEO API 的访问。 -下面讨论GEO索引数据的构造方式。 +所以，在使用 Pegasus GEO 特性时，需要创建两个 Pegasus 表，一个是原始表，用于存储用户写入的原始数据，一个是 GEO 索引表，用于存储 GEO client 自动转换原始数据生成的 GEO 索引数据。 ### hashkey -hashkey直接由一维编码的前缀构成。比如在我们的LBS业务场景中，范围查询都是集中在10km半径内的圆形范围，实际测试结果是将hashkey长度定为`14`（1位face，1位分隔符`/`，12位Hilbert编码）能取得更好的性能。 +hashkey 直接由一维编码的前缀构成。比如在一个用户场景中，范围查询都是集中在 10km 半径内的圆形范围，实际测试结果是将 hashkey 长度定为`14`（1位face，1位分隔符`/`，12位Hilbert编码）能取得更好的性能。 -> `最小搜索层`为12 +> 那么，最小搜索层就为12 ``` - cellid -|--------------32 bytes-------------| -|---14 bytes----| + CellId +|1/223320022232..................| +|-------------32 bytes-----------| +|---14 bytes--| hashkey ``` ### sortkey -为了满足不同半径范围、不同精度的查询，我们把cellid剩下的18位全部放到sortkey中（这并不会给底层存储带来多少压力），这可以在应用层保持比较高的灵活性，而不用修改底层的数据。在进行较大范围的临近查询时，取更少的sortkey位数（对应的cellid更短）进行数据查询；进行较小范围的临近查询或点查询时，取更多的sortkey位数（对应的cellid更长）进行数据查询。 +为了满足不同半径范围、不同精度的查询，我们把 CellId 剩下的 18 位全部放到 sortkey 中。 +- 在进行较大范围的临近查询时，取更少的 sortkey 位数（对应的 CellId 更短）作为前缀，进行数据 scan 查询，这样可以减少数据 scan 的次数 +- 在进行较小范围的临近查询或点查询时，取更多的 sortkey 位数（对应的 CellId 更长）作为前缀，进行数据 scan 查询，这样可以减少数据 scan 的范围 -尽管在30层时，cell的面积已经足够小（<1cm^2），但仍有可能两条数据落在同一个cell里，所以需要区分不同的数据。这里，将原始数据的hashkey和sortkey联合起来，并追加在上述sortkey之后。 +这可以在不修改底层存储数据的前提下，让应用层保持比较高的灵活性。 - cellid - |--------------32 bytes-------------| - |---14 bytes---||-----18 bytes------||--原始hashkey--||--原始sortkey--| - |--GEO hashkey-||----------------------GEO sortkey-------------------| +> 查询相同地理区域内（例如一个圆形区域）的数据时，使用短 CellId 查询数据查询的范围更大，查询的次数更少，但得到的在区域外的无用数据更多。而使用长 CellId 查询数据查询的范围更小，得到的在区域外的无用数据更少，但查询的次数更多 +> +> 参考：[S2 coverings](http://s2geometry.io/devguide/examples/coverings) +尽管在第30层时，cell 的面积已经足够小（<1cm^2），但仍有可能两条数据落在同一个 cell 里，所以需要在 CellId 编码的基础上，解决 key 冲突问题。Pegasus 将**原始表**的 hashkey 和 sortkey 联合起来，追加在 GEO 表的 sortkey 之后。 -> 在相同地理范围内进行数据查询时，使用短cellid查询数据查询的范围大，查询的次数更少，但得到的在区域外的无用数据更多，反之亦然---这需要在查询次数与查询到的有用数据之间做权衡。 +``` + CellId +|1/223320022232200331010110113301| +|-------------32 bytes-----------| +|---14 bytes--||-----18 bytes----||--原始hashkey--||--原始sortkey--| +|-GEO hashkey-||-------------------GEO sortkey-------------------| +``` ### value -GEO API的value必须能够解析出经纬度，具体的解析方式参考[自定义extrator](https://pegasus.apache.org/api/geo#%E8%87%AA%E5%AE%9A%E4%B9%89extrator)。 +使用 GEO 特性所存储的 value 必须能够解析出经纬度，具体的解析方式参考[自定义extrator](/api/geo#%E8%87%AA%E5%AE%9A%E4%B9%89extrator)。 -GEO索引数据的value跟原始数据的value完全相同。这里会存在一份冗余，但通常在相对廉价的磁盘存储介质上，这是可以接受的。 +GEO 索引表的 value 跟原始表的 value 完全相同。这里会存在一份冗余数据，使用空间换时间的方式避免二次索引。 -> 我们建议业务层在使用GEO API时value只存储小数据，大数据建议采用二次索引的方式。 +> 如果确实有在 GEO 的单条 value 中存储较大数据的需求，又想节省磁盘空间，可以手动实现二次索引，即在 GEO value 中存储二级索引的 key，再在另外的表中存储真实的大 value。 ## 数据更新 ### set -`set`操作会同时更新两个table的数据: Pegasus原始数据和GEO索引数据（数据构造方式如上所述）。 +`set` 操作会同时更新上述两个表的数据，即 Pegasus 原始表数据和 GEO 索引表数据，数据构造方式也如上所述。 -> `set`操作的hashkey, sortkey是业务自己的格式，使用GEO API时并不做约束， 只是在geo client转存GEO索引数据时，会自动做如上所述的编码转换。 +`set`操作的 hashkey，sortkey 是用户自己的格式，使用 GEO API 时并不做约束。两个表的数据转储对用户是透明的，由 GEO client 自动完成。 Review Comment: ```suggestion `set`操作的 hashkey，sortkey 是用户自己的格式，使用 GEO API 时并不做约束。两个表的数据转储对用户是透明的，由 GEO Client 自动完成。 ``` -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
