arrow-digest

非官方Apache Arrow包，旨在标准化结构化数据的稳定哈希。

动机

如今，像Parquet这样的结构化数据格式在二进制层面上是不稳定的/不可复制的 - 写入相同逻辑数据可能会在不同的文件中，这取决于你使用的编写器实现方式，并且可能随每个版本而变化。

这个包提供了一种基于Apache Arrow内存格式计算结构化数据（逻辑哈希）的稳定哈希的方法和实现。

优点

• 快速检查大型数据集的相等性/等价性的方法
• 双方可以在不传输数据或泄露其内容的情况下比较数据
• 迈向结构化数据（例如，当在IPFS等DHT中存储数据集块时）的内容可寻址的步骤

使用

// Hash single array
let array = Int32Array::from(vec![1, 2, 3]);
let digest = ArrayDigestV0::<Sha3_256>::digest(&array);
println!("{:x}", digest);

// Alternatively: Use `.update(&array)` to hash multiple arrays of the same type

// Hash record batches
let schema = Arc::new(Schema::new(vec![
    Field::new("a", DataType::Int32, false),
    Field::new("b", DataType::Utf8, false),
]));

let record_batch = RecordBatch::try_new(Arc::new(schema), vec![
    Arc::new(Int32Array::from(vec![1, 2, 3])), 
    Arc::new(StringArray::from(vec!["a", "b", "c"])),
]).unwrap();

let digest = RecordsDigestV0::<Sha3_256>::digest(&record_batch);
println!("{:x}", digest);

// Alternatively: Use `.update(&batch)` to hash multiple batches with same schema

状态

虽然我们正在努力实现v1，但我们保留打破哈希稳定性的权利。如果你打算使用此包，请创建一个问题。

• 模式哈希
• 固定大小类型
• 可空性：原始类型
• 二进制
• Uft8变体
• 结构
• 嵌套结构
• 可空性：嵌套结构
• 列表
• 结构列表
• 字典
• 区间
• 联合
• 映射
• 元数据字节序检查
• 更好的测试覆盖和模糊测试
• 性能：基准测试
• 性能：并行性
• 性能：代码优化

设计目标

• 合理快速
• 无论输入被分成多少批，哈希都相同
• 无论是否使用字典编码，哈希都相同

缺点

• 逻辑哈希尚未达到完美的内容可寻址性
  • 逻辑哈希可能需要得到IPFS等工具的支持，但这太过宽泛，因为这不是一个通用哈希算法
  • 完全确定性的二进制编码，与Parquet兼容，可能是一个更好的方法
• 提出的方法是顺序相关的 - 如果记录顺序改变，它将产生不同的哈希
• 布尔哈希可能更有效

哈希过程

从原始类型开始逐步构建

• 字节序 - 总是假设小端序
• 固定大小类型
  • Int, FloatingPoint, Decimal, Date, Time, Timestamp - 使用它们的内存二进制表示进行哈希
  • Bool - 将单独的值作为字节数值进行哈希，1 对应于 false，2 对应于 true
• 可变大小类型
  • Binary, LargeBinary, FixedSizeBinary, Utf8, LargeUtf8 - 哈希长度（作为 u64）后跟值的内存表示
  • List, LargeList, FixedSizeList - 哈希列表长度（作为 u64）后跟根据其数据类型的子数组的哈希
• 可空性 - 每个空值都由一个 0（零）字节表示
  • 没有有效性位图的数组与有有效性位图的数组的哈希相同，所有项都是有效的
• 数组数据
  • （每次哈希会话一次） 根据下表哈希数据类型
  • 按上述规则顺序哈希项目
• 记录批量数据
  • （每次哈希会话一次） 对于每个字段哈希 filed_name as utf8，nesting_level (基于零-的) as u64 递归遍历模式，以 深度优先 的顺序
  • 对于每个叶列
    • 从每个父的可空性中生成一个 组合可空性位图
    • 使用上述规则更新相应列的哈希器
  • （最后一步） 将每个数组的摘要输入到组合哈希器中，以生成最终的摘要

请注意，一些类型（Utf8 和 LargeUtf8，Binary FixedSizeBinary 和 LargeBinary，List FixedSizeList 和 LargeList）在哈希中表示相同，因为它们之间的区别纯粹是编码问题。

参考

• Arrow内存布局
• Arrow Flatbuffers模式