推荐：Minisketch - BCH码基的集和调和库

Minisketch是一个优化的独立MIT许可的C语言API库，用于构建和解码基于BCH编码的“集和素描”，特别适用于紧凑型集和调和以及其他应用。它实现了PinSketch算法，详细解释可参见文档。

集合调和概览

Minisketch产生的“集和素描”可以理解为带有两种特殊属性的“集合校验和”：

• 素描具有预设容量，只要集合元素数量不超过容量，库就能从素描中恢复整个集合。一个b-位元素的容量c的素描只需要bc位来存储。
• 可以通过异或（XOR）操作将两个集合的素描结合，得到两集合的对称差素描，即只存在于其中一个集合但不在另一个集合中的元素。

这使得它们非常适合实现高效带宽的集和调和协议。假设Alice和Bob各自拥有一个元素集合，并且他们认为两个集合大部分重叠，但不完全相同，那么他们可以通过以下步骤让双方学习所有元素：

1. Alice和Bob都计算他们的集合素描。
2. Alice将其素描发送给Bob。
3. Bob合并两个素描，得到对称差异素描。
4. Bob尝试从中恢复差异元素。
5. Bob把他在差异中有的，但Alice没有的每个元素发给Alice。

如果元素较大，可能更倾向于在集合元素上计算素描而不是直接使用元素。在这种情况下，协议会增加一步，Bob还会把他的缺失元素的哈希发给Alice，Alice再回应所需的元素。

在doc目录下还有更多关于使用libminisketch设计调和协议的提示。

性能评估

如上图所示，Minisketch与三种其他集和调和算法/实现进行了基准测试。测试在单核Intel Core i7-7820HQ处理器（时钟速度锁定在2.4 GHz）上进行。第一个图表显示了各种算法在合并两个素描和解码结果所需的时间。在同一个机器上创建素描大约需要5 ns/容量和/集合元素。其他实现包括：

• pinsketch，原始的PinSketch实现。
• cpisync，一个实现了多个集和调和算法和协议的软件项目。基准测试仅分析了非概率性的原版CPISync算法^[5]。
• 一个使用4个哈希函数和32位校验和的高性能自定义IBLT实现。

对于作者当前感兴趣的最大规模，例如具有4096容量和1024差异的集合，Minisketch比pinsketch快四十九倍，比cpisync快八千多倍。Minisketch性能足以在计算资源有限的高流量网络服务器上实时使用。

即使在网络延迟限制性能的情况下，小的Minisketch也可以足够快速地提高性能。在上述i7-7820HQ上，当集和大小为2500个30位条目，差异为20时，如果通信带宽低于1 Gbps，使用Minisketch比发送原始集合更快；如果差异为8，则可以在千兆链路上以五分之一的时间完成。

第二个图展示了保持容量固定在128时，不同差异数对各种算法性能的影响，显示出cpisync的调和速度主要依赖于容量，而pinsketch/libminisketch则更多地依赖于差异数。

第三个图显示了典型的IBLT方案相对于其他算法（接近最优带宽）的大小开销，对于不同的失败概率水平。当集合差异大小较小并且要求的失败率较低时，IBLT占用的带宽是libminisketch素描的几十倍。

第四个图显示了字段大小对Minisketch速度的影响。三条线分别对应：

• CLMUL 64位：Intel Core i7-7820HQ系统，2.4 GHz
• 通用64位：POWER9 CP9M06系统，2.8 GHz（Talos II）
• 通用32位：Cortex-A53，1.2 GHz（Raspberry Pi 3B）

它说明CLMUL实现对于某些字段（特别是存在形式为x^b + x + 1的GF(2)上的不可约多项式时，以及32位字段的倍数时）的速度更快。也表明，目前在32位平台上，字段大于32位时存在显著的性能下降（Raspberry Pi 3B比Core i7慢约10倍，而POWER9慢约1.3倍）。

以下是PinSketch算法（libminisketch的实现）与其他集和调和算法的对比：

算法	素描大小	解码成功	解码复杂度	差异类型	安全素描
CPISync[2]	(b+1)c	始终	O(n^3)	两者	是
PinSketch[1]	bc	始终	O(n^2)	对称仅	是
IBLT[6][7]	αbc（见图3）	概率性	O(n)	根据情况	否

• 素描大小： 这一列显示了为协调c个不同b-位元素设计的素描的位数。PinSketch和CPISync有接近最优^[11]的通信开销，意味着素描大小非常接近（或等于）bc位。这是与差异大小相等的朴素传输所需的空间（令人惊讶的是，因为发送者甚至不知道差异是什么）。对于IBLT有一个开销因子α，取决于各种设计参数，通常在2到10之间。
• 解码成功： 当素描设计的容量不小于实际差异大小时，CPISync和PinSketch保证解码差异始终会成功。IBLT总是有可能失败，尽管可以通过增加通信开销使其概率变得极低。
• 解码复杂度： 几乎最优算法的空间节省是以性能为代价的，因为它们的解码复杂度是二次或三次，而IBLT是线性的。这意味着当差异足够大时，使用几乎最优算法可能会过于昂贵。
• 差异类型： PinSketch只能从合并的素描中计算对称差异，而CPISync和IBLT可以区分元素在哪个集合中缺失。当解码器访问其中一个集合时，这一点通常无关紧要，因为他可以用其中一个集合查找对称差异中的每个元素。
• 安全素描： 是否满足安全素描^[1]的定义，意味着对于不了解大多数元素的人来说，从素描中只能提取出最少的信息。使该算法适用于指纹认证等应用。

构建与使用

目前构建系统非常简单，欢迎提供改进建议。

以下命令可能有效，生成名为libminisketch.a的链接库文件：

git clone https://github.com/sipa/minisketch
cd minisketch
./autogen.sh && ./configure && make

使用示例

在此部分中，Alice和Bob正在寻找他们集合之间的差异。Alice有集合*[3000 ... 3009]，Bob有[3002 ... 3011]*。

首先，Alice创建一个素描：

#include <stdio.h>
#include <assert.h>
#include "../include/minisketch.h"

int main(void) {
  minisketch *sketch_a = minisketch_create(12, 0, 4);
  // ...
}

这里的参数是：

• 字段大小b，指定要调和的元素的大小。字段大小为b时，支持的元素范围是从1到2^b-1（含），注意元素不能为零。
• 实现编号。实现0总是可用的，但在某些硬件上可能存在更高效的算法。素描的序列化形式与其实现无关，因此不同实现之间可以互换。

现在，让我们一起探索如何利用Minisketch的效率和灵活性来解决更多的集合处理挑战，提升你的应用性能。无论是数据同步、分布式系统的状态一致性，还是任何需要高效集合并的场景，Minisketch都是值得信赖的选择！