4 个版本
使用旧的 Rust 2015
| 0.1.4 | 2017 年 10 月 28 日 |
|---|---|
| 0.1.3 | 2017 年 3 月 19 日 |
| 0.1.1 | 2017 年 3 月 19 日 |
| 0.1.0 | 2017 年 3 月 19 日 |
#1965 在 算法
96KB
2K SLoC
块数组 Cow
简介
内存数组去重，用于高效存储多个版本的数据。
例如，这适用于存储撤销历史 - 其中结构体的大小可以用作步长，并且对二进制和文本数据都有效。
代码采用 Apache2.0 许可证，且没有依赖。
动机
对于撤销系统（或其他任何历史存储）来说，您可能想存储您数据的多个版本。
在某些情况下，编写一个 持久数据结构 是有意义的，但这在很大程度上取决于您处理的数据类型。
在其他情况下，如果您能够轻松地将数据序列化并存储，而不必担心复制管理细节，那就更好了。
这就是编写这个库的动机。
算法
创建一个新的BArrayStore具有固定步长和块大小。
将新状态添加到数组存储器中，只需将数组划分为块并存储即可。
添加另一个状态时，可以使用任何先前状态作为引用，其中其块尽可能被重复使用。
检查数组的开始/结束处的匹配块，并复制它们，直到找到不匹配。
如果找到不匹配，引用块使用其第一个 N 字节的懒加载哈希。同时计算待添加数据的哈希数据，每个步长偏移量有一个值。
现在可以遍历新添加的状态数据，对引用块执行哈希查找，如果找到匹配项，则进行完整比较。
在这种情况下，会测试以下块以查看它们是否匹配（以避免进一步的查找），否则分配新块。
完成后，将新状态添加，其中可能包含来自先前状态的新块和重复使用的块。
其中 N 目前是步长 * 7，见BCHUNK_HASH_TABLE_ACCUMULATE_STEPS.
注意
这略微侧重于性能，因为此方法用于 3D 模型器撤销系统中。其中更改累积并在运行时释放。
使用固定大小的块更适合内存数据存储，与创建一次性二进制差异的命令行工具相比——在这种情况下，可能更倾向于进行更全面的测试。
支持
- 调用者定义的块大小。
- 调用者定义的数组步长，以避免检测未对齐偏移量时的开销。（字节数组的步长为1也是可以的）
- 即使在块完全重新排序的情况下也能进行去重（去重使用块哈希）。
- 每个状态只需引用其前一个状态，这使得线性结构和树结构都成为可能。
- 乱序添加/释放状态。
不支持
通常避免使用过多计算的运算，因为有许多可能的更改可以在不牺牲性能的情况下提高内存使用率。
重新对齐单用户参考块边界，以减少找到更改时重复块的大小。
检测数据的数值变化（值增加/减少、置零等不检测）。
块要么完全匹配，要么完全不匹配。
进一步工作
一些可能值得考虑的事项。
- 可能有必要使其BCHUNK_HASH_TABLE_ACCUMULATE_STEPS可配置的，以控制每个块数据对其哈希的贡献程度。
- 可能值得使用mmap进行数据存储。
- 块压缩（可能基于调用者定义的规则，即当状态的数据不太可能再次被读取时）。