Lib.rs

geomedea是一种针对远程访问全球数据子集优化的地理空间数据格式。

🚨 此项目处于实验状态，但显示出一些潜力。

此格式深受优秀的flatgeobuf项目启发。

与flatgeobuf类似，一个空间索引（目前是一个压缩的希尔伯特索引）允许高效地选择给定边界框内的要素，即使是通过HTTP范围请求远程操作。

与flatgeobuf不同，flatgeobuf将压缩留作“读者的练习”，而压缩（目前是zstd）以允许利用空间索引的方式内置于格式中。

为了实现这一点，与flatgeobuf的单个要素流不同，要素被分块到页面上。然后对每个页面进行压缩。当使用边界框查询时，您只检索包含您要素的页面。因为页面包含多个要素，这涉及一些浪费，但在实践中，由于必须检索整个页面才能获取部分要素而产生的损失通常被能够利用压缩的收益所抵消。

如果您的情况不同，我很想知道详细信息。

动机/度量

我想下载由指定边界框限制的OpenAddresses数据子集，以馈入非全球部署的Headway。

通过OpenAddresses网站，您可以点击下载您感兴趣的特定区域，但没有为此提供程序化API——这是一个手动过程。

因此，更精确地重述问题，给定一个由HTTP远程托管（1.2G压缩的geojson文件）的全球地址数据，我只想获取给定边界内的条目（例如，西雅图：-122.462 47.394 -122.005 47.831）。这大约有一百万条记录。

我的第一个想法是将整个全局数据集转换成一个单一的flatgeobuf，并利用FGB的边界框查询功能来下载我感兴趣的数据子集。这按预期工作，但我对两件事感到失望。

首先，flatgeobuf文件的磁盘大小远大于压缩的全局geojson。我不觉得惊讶——首先，它包含一个索引。此外，由于它是基于flatbuffers构建的，所以有很多填充。如果您能够在磁盘上压缩FGB，您将找回其中很大一部分，但这样您就失去了在该文件上执行边界框查询的能力，因为索引是基于（未压缩）的文件字节偏移量。也许SOZip在这里会有所帮助——但我还没有看到它在网络环境中被使用。

其次，最终我需要将此数据作为CSV。CSV格式的百万条记录为106MB。获取这些特征数据的传输数据量几乎是CSV编码输出的8倍，这让我感到不舒服。我们不是应该在2023年打败CSV吗？😉 这主要是由于我之前提到的未压缩的flatgeobuf不是一种非常节省空间的格式所致，但尽管整个flatgeobuf在磁盘上的大小会影响文件托管者，但这也影响下载者。多年来，我已经做了一些工作来优化flatgeobuf的网络传输（特别是改进索引遍历和智能特征批处理），但我认为我几乎已经解决了所有可以解决的问题，而不会破坏格式。

以下是数字

FGB

• 转换为flatgeobuf的输入大小：9.3G（比压缩的geojson大7.75倍）
• 针对西雅图的示例请求，模拟网络延迟100ms，50mbps
  • 时间：1:14.30总时间
  • 请求数量：310
  • 传输的字节数：339838864（340 MB）（比输出CSV大3.2倍）

Geomedea

• 转换为geomedea的输入大小：2.5G（比压缩的geojson大2.1倍）
• 针对西雅图的示例请求，模拟网络延迟100ms，50mbps
  • 时间：45.564总时间
  • 请求数量：153
  • 传输的字节数：81175859（81MB）（比输出CSV大0.76倍）

优点

在存储库中存在一个更小的基准，您可以运行它来与flatgeobuf中的类似基准进行比较。它在50mbps w/ 100ms延迟的模拟连接上运行。

FGB - UScounties.fgb 13M

HTTP select_all                 time: [3.0314 s 3.0359 s 3.0399 s]
HTTP select_bbox                time: [629.16 ms 631.99 ms 634.83 ms]

Geomedea压缩：USCounties-compressed.geomedea 5.1M

HTTP select_all (compressed)    time: [994.97 ms 1.0145 s 1.0428 s]
HTTP select_bbox (compressed)   time: [529.22 ms 530.04 ms 530.85 ms]

Geomedea未压缩：USCounties-uncompressed.geomedea 7.5M

HTTP select_all (uncompressed)  time: [1.4355 s 1.4405 s 1.4445 s]
HTTP select_bbox (uncompressed) time: [630.31 ms 632.56 ms 634.58 ms]

注意事项和详细信息

在实际应用中，性能几乎完全由网络主导——往返延迟和吞吐量都起着作用。在这方面，索引格式和遍历逻辑在两种格式之间基本相同。导致改进的最大概念性变化是将功能拆分为可压缩页面，但我还做了其他几个概念上较小但仍然重要的改变。

更节省空间的编码

Flatgeobuf使用flatbuffers来编码其功能（因此得名！）。

使用flatbuffer格式，您可以随机访问flatbuffer中的字段，而无需解析其前面的所有内容。这与像protobuf这样的格式形成对比，后者必须按顺序访问。需要一些巧妙的方法来实现这一点，但其中一个组件只是简单地添加填充来可预测地对齐字段。作为这种“浪费”的填充空间的交换，您获得了这种不错的随机访问功能。

功能由几何数据和属性数据组成。flatgeobuf中的几何编码相当简单——flatbuffer向量中的一些64位浮点数。然而，属性数据在flatbuffer字节数组的基础上有自己的自定义二进制编码——因此您不能在没有首先处理所有先前的属性的情况下随机访问特征的一个属性。

此外，可能更重要的是，flatgeobuf 中的每个特性都被序列化为一个独立的带有大小前缀的缓冲区。仅凭文件中的特性部分，您无法在不先解析前 n - 1 个特性之前访问第 n 个特性。

使用 flatgeobuf 的空间索引，我们可以 随机 访问特性，但这仅仅是由于外部索引，与 flatbuffer 编码无关。

因此，如果索引使我们能够随机访问特性，并且属性也不可随机访问，那么我们通过 flatbuffer 编码获得了什么？可能存在一些用例，能够跳过 所有 属性数据或访问某些几何坐标而不解析所有坐标是非常有用的，但在我自己的用例中，flatbuffer 编码的益处被其开销所抵消。因此，我使用了一种空间高效的序列化编码来代替 flatbuffer。目前我使用的是 bincode，它对我来说很容易使用，并且性能良好，但我实际上并没有认真考虑这个选择。可能还有更好的选择，尤其是在跨语言支持方面。

未来工作 🤔

具有讽刺意味的是，有了压缩，flatbuffer 的填充问题变得更加不那么严重，因此更高效编码方案的总体好处实际上并没有一开始看起来那么大。正因为如此，我甚至考虑回到起点，使用类似 flatbuffer 或 capnproto 这样的随机访问格式来编码特性。我会考虑做出的一个不同之处，而不是一系列带有大小前缀的根 flatbuffer，而是一个页面上的单个根——一个特征向量而不是一系列带有大小前缀的特征，这样可以在页面内高效地随机访问第 n 个特征。当 flatgebuf 被创建时，flatbuffer 不支持足够大的向量来将大量数据放入单个向量中。但现在 flatbuffer 支持了这一点，但无论如何，由于特性被分割成页面，每个页面的数量永远不会很大。在页面内使用随机访问友好的格式可能会使索引策略更加直接，并且访问特定属性更加高效。

坐标存储

flatgeobuf 将几何坐标存储为 64 位浮点数，而 geomedea 当前将坐标存储为表示缩放十进制的 32 位有符号整数，就像 OpenStreetMap 的原生坐标格式。对我来说这很有意义，因为我主要处理 OSM 数据，并且几乎总是处理 lng/lat 而不是某种地方投影。对于这些情况，32 位缩放十进制在赤道附近精度达到 1cm，这对于我的用例来说已经足够好了。flatgeobuf 在这里并不是“错误”，只是做了一个不同的选择。

未来工作 🤔

坐标存储的细节可能会改变，或者可能成为可配置的。在实践中，对于我使用的数据集，升级到 64 位浮点数实际上并没有像我预期的那样增加压缩大小。

我对整数编码的一个扩展，我很乐意尝试，就是类似于 OSM pbf 格式的偏移量编码。由于特征页面是希尔伯特排序的，后续的特性应该相对接近，因此适合高效的偏移量编码。

HTTP 流

为了限制内存使用，FGB客户端采用了“分块”方法，每次获取固定数量的数据（目前默认为1MB）。一旦下载了1MB的数据，就会进行处理，然后下载下一个数据块。与flatgeobuf的rust客户端不同，geomedea使用流式HTTP客户端。这种方法的另一个小优点是它减少了处理和I/O（下载）之间等待的时间。更重要的是，由于我们的请求没有“块大小”限制，我们不再需要将大的连续范围分割成多个请求。您可以通过select_all案例最明显地看到这种优势，现在它可以是一个针对整个文件的单一请求。因为我们正在流式传输，所以我们每次只保留少量数据在内存中，不管整体文件大小如何。格式本身没有内在的东西使流式传输更容易——这种方法可以应用于flatgeobuf。但由于这是一个新的代码库，我想从一开始就利用它。