setsum

setsum 是一种无序校验和，它操作数据集的集合。大多数校验和算法以流式方式处理数据并生成每个流唯一的校验和，而 setsum 处理离散元素流，并生成对元素唯一的校验和，无论它们在流中的顺序如何。

在代码中看起来像这样

use setsum::Setsum;

let mut setsum1 = Setsum::default();
setsum1.insert("A".as_bytes());
setsum1.insert("B".as_bytes());

let mut setsum2 = Setsum::default();
setsum2.insert("B".as_bytes());
setsum2.insert("A".as_bytes());

assert_eq!(setsum1.digest(), setsum2.digest());

实际用途

setsum 解决了许多无法用普通校验和轻松解决的问题。本节重点介绍了 setsum 的两种主要使用模式

复制流校验和

基于复制的系统可能会导致副本之间的差异。有一些工具可以解决这个问题（如 MySQL 的 pt-tc），但这些工具需要擦洗整个集群以查找主节点与其副本之间的差异，并且擦洗本身可能需要几天才能发现问题。

可以通过修改复制流来使用 setsum 早期检测这些问题；实际上，setsum 维护整个数据集的滚动校验和。

这样做的办法是有一个表示数据库状态的 setsum 对象，并定期持久化以实现恢复。然后，对于每个事务，setsum 都会使用正在复制的数据的先验和后验图像更新。在这些更新完成后，setsum 反映了已复制的整个数据库的校验和。

与其它方案相比，这里有一个权衡。如果使用具有内置标识符的复制方案（如 MySQL 的 GTIDs 或 Raft 的日志），此方案允许对所有副本进行即时比较。它不会做的是保护已写入磁盘的数据不受损坏。为此，需要获取快照并比较快照的 setsum 与新计算的 setsum；否则，始终可以继续运行 pt-tc 等工具。

记录 LSM 树

日志结构合并（LSM）树现在无处不在，最常见的来源于谷歌的LevelDB。这些变体的定义特征是大多数数据存储在不可变文件中，新数据通过称为“压缩”的方式整合到树中。压缩过程是用另一组不可变文件替换这些文件的过程。数据在这个过程中被重写，旧数据被垃圾回收。因为数据本身是不可变的，所以压缩是LSM树中软件驱动数据损坏的薄弱环节。

使用setsum解决此问题的一种方法是简单地记录压缩的输入和输出。如果我们把压缩看作是一个转换过程，数据既不会被创建也不会被销毁，所以输入的校验和必须等于输出的校验和。当然，这种对压缩的看法并没有直接考虑到垃圾回收——要做到这一点，我们需要考虑垃圾回收的数据以及剩余的输出。

之后必要的步骤是添加一个验证器，以确保文件的内容与它们的关联setsum匹配。如果文件不匹配，压缩就出了问题。如果输入在验证之后保存，错误可以安全地回滚。

这里也存在权衡：由setsum保护的LSM树无法执行更复杂的压缩逻辑，比如合并值。虽然它可以追踪文件是否与它们的校验和匹配，但压缩无法平衡输入和输出的校验和。

状态

维护跟踪。如果一年内没有变化，该库将被视为稳定并进入维护模式。

范围

这个库提供了阿贝尔群和逆运算符以及SHA256的简化操作。

缺陷

• 缺少setsum-merge工具
• 缺少setsum-diff工具

更新

• 版本0.5从sha2切换到sha3作为单元素哈希函数，以提高性能。

文档

最新文档始终可在docs.rs获取。