3

内容可寻址存储系统使用存储数据的哈希值作为标识符和地址。碰撞非常罕见，但如果系统长时间大量使用，它可能会发生。如果有两条数据产生相同的哈希值会怎样？最近存储的一个获胜并且数据丢失是不可避免的，还是有可能设计一种方法来存储两者并允许访问两者？

为了缩小问题的范围，我想专注于 Camlistore。如果永久节点碰撞会发生什么？

4

3 回答 3

1

假设没有发生碰撞。考虑到强大的哈希函数和随意的、非恶意的用户输入，这是一个完全合理的假设。Camlistore 目前使用的 SHA-1 也可以抵抗恶意尝试产生冲突。

如果哈希函数随时间变弱并需要停用，Camlistore 支持迁移到新 blobref 的新哈希函数，同时保持旧 blob ref 可访问。

据我所知，如果确实发生了冲突，那么第一个存储的带有该哈希的 blobref 将获胜。

来源：https ://groups.google.com/forum/#!topic/camlistore/wUOnH61rkCE

于 2015-05-16T12:19:56.653 回答
1

在理想的抗碰撞系统中，当摄取新文件/对象时：

  1. 计算传入项目的哈希值。
  2. 如果传入的哈希在存储中不存在：
    1. 项目数据被保存并与哈希关联作为其标识符
  3. 如果传入的哈希与存储中的现有哈希 匹配：
    1. 检索现有数据
    2. 对现有数据与新数据进行逐位比较
    3. 如果发现两个副本相同，则将新条目链接到现有哈希
    4. 如果新副本不相同，则新数据要么
      1. 被拒绝，或
      2. 附加或前缀* 附加数据（例如时间戳或用户 ID）并重新散列；然后重复整个过程。

所以不，信息在内容可寻址存储系统中丢失并非不可避免。

* 理想情况下，现有的存储数据将以相同的方式重新散列，并以某种方式标记原始散列条目（例如链接到零字节有效负载）以表示有多个存储对象最初解析为该散列（在概念上类似于维基百科上的“消歧义页面”）。这是否有必要取决于需要如何从系统中检索数据。

虽然故意引起冲突对于给定的算法可能在天文上是不切实际的，但随机冲突可能会在第二次存储事务时立即发生。

注意：一些小型/非关键系统会跳过二进制比较步骤，以换取带宽或处理时间的风险。（通常，只有在某些元数据匹配时才会这样做，例如文件名或数据长度。）

这种系统（例如单个git存储库）的风险状况与摄取大量二进制数据的企业/云规模环境大不相同，特别是如果该数据是明显的随机二进制数据（例如加密/压缩文件）组合与滑动窗口重复数据删除之类的东西。

另见，例如：

于 2022-02-14T22:48:44.420 回答
0

复合键，例如 hash + userId

于 2022-01-04T14:29:24.883 回答