Rateless Invertable Bloom Lookup Table (RIBLT)。

本 Rust 库的目标是允许通过网络接口高效地进行集合校验。这是通过使用 Rateless Invertable Bloom Lookup Tables (RIBLT) 实现的。

本库基于论文《实用的无率集合校验》，作者为 Lei Yang、Yossi Gilad 和 Mohammad Alizadeh。

https://arxiv.org/html/2402.02668v2

此库不要求特定的 '集合' 实现，它只要求集合可迭代。这允许用户使用适合他们用例的任何集合实现，包括从磁盘读取的集合。

请注意，此库不会在集合中查找重复项。无法从 RIBLT 中移除重复项。

术语表

• 符号：集合中的一个项
• 编码符号：RIBLT 的一个元素。
• 剥离：从 RIBLT 中移除符号的过程。

本库提供概述

RatelessIBLT

通过传递一个符号的可迭代集合创建的结构体。

它将根据需要创建 RIBLT 编码符号。

有关更多信息，请参阅 RatelessIBLT 结构体。

UnmanagedRatelessIBLT

类似于 RatelessIBLT，但没有可迭代的集合。

当无法访问创建此 RIBLT 的集合时使用。

还用于将两个 RIBLT 合并或折叠在一起。

有关更多信息，请参阅 UnmanagedRatelessIBLT 结构体。

哈希冲突概率

如生日悖论所述，当集合中的项目数等于可能结果的平方根时，哈希冲突的概率为 50%。我们使用 64 位哈希，因此当项目数约为 40 亿时，我们应该期望出现哈希冲突。

非常大型集合的通用挑战

根据定义，集合不能有重复项。在 Rust 中以内存形式存储集合时，可以使用 HashSet 或 BTreeSet。然而，当集合非常大时，内存需求可能过高。

根据定义，当元素已存在时插入是不执行的。如果将集合存储为磁盘上的无序列表，则强制执行此行为需要扫描整个列表。

伴随数据结构，如常规 Bloom 过滤器，可以减少对全扫描的需求。如果条目不在 Bloom 过滤器中，则已知它尚未在集合中，因此可以安全地插入/附加它。如果条目在 Bloom 过滤器中，它可能在集合中，因此我们需要进行全扫描。

快速变化集合的挑战

考虑到在多个服务器之间保持插入只读集同步的使用场景。在服务器之间共享数据时，有三种机制是实用的。

1. 全集传输，适用于添加新服务器或存在巨大差异的情况。
2. 流式八卦机制。一个服务器上的插入操作会广播到所有其他服务器。
3. 修复机制，定期运行以确保所有服务器拥有相同的集合。

假设使用Rateless IBLT（信息论不可失块传输）作为修复机制。还假设每个项目的原始插入时间已知，并且服务器有一个大致同步的时钟。

由于不同服务器上的不断插入，在繁忙时期，集合不太可能同步。这将导致修复机制被浪费使用，因为大多数差异都将由八卦机制解决。

为了解决这个问题，在计算和共享Rateless IBLT时，我们应该忽略在特定时间窗口内插入的项目。

例如，考虑一个系统，其中99.999%的项目在10秒内达到所有服务器。每个服务器可以每分钟计算一次所有插入超过10秒的项目的时间间隔IBLT，每分钟一次。服务器可以将编码符号从Rateless IBLT共享给多个其他服务器。有了这些信息，服务器可以开始请求缺少的项目。

修复机制也会处理网络分区的情况。然后使用Rateless IBLT来高效地解决差异。

未来工作

异步和多线程

目前，在这个crate中没有使用异步或多线程。我将在未来测试性能提升。

这被认为是一个较低优先级，因为我预计这将在执行其他任务的服务器上使用。

注意事项

目前，当集合发生变化时，调用代码负责重新创建结构。