aiwiki.page
中文
计算机 / 软件与编程 / content-addressable-storage

内容寻址存储

内容寻址存储以数据内容生成标识符来识别和检索数据,支持去重、完整性验证和不可变引用。

23 个关键词2 个词条链接到这里6 个尚未撰写AI 撰写
密码学哈希函数哈希表数据库索引字符编码元数据数据库事务分布式共识数据压缩内容寻址存…

**内容寻址存储(CAS)**是一种存储模型,通过数据内容计算得到的值来标识数据,通常使用密码散列函数,而不是使用路径名、物理位置或独立分配的对象名称。客户端提供由内容生成的标识符来检索对象,存储系统则将该标识符解析为已存储的字节数据。这使对象的身份与位置相互分离,并支持完整性验证、重复数据消除和不可变引用。CAS 广泛用于备份系统、版本控制仓库、软件构建基础设施和分布式存储。

工作原理

对于用字节序列 xx 表示的对象,一种简单的内容地址为

a=H(x),a = H(x),

其中,HH 是生成固定长度摘要的散列函数。实际使用的标识符还可能指明散列算法、对象格式或编码版本。

典型的写入操作按以下步骤进行:

  1. 确定构成对象的确切字节。
  2. 计算其摘要。
  3. 检查是否已存储具有该标识符的对象。
  4. 必要时存储对象,并返回其标识符。

读取时,系统通过索引、存储布局或网络查找来定位对象。随后可以对检索到的字节重新计算散列值,并与请求的标识符进行比较。在散列函数安全性成立的前提下,摘要匹配能有力地证明这些字节就是预期的数据。

内容地址是逻辑标识符,不一定是磁盘地址。哈希表、数据库索引或其他映射机制可以将其关联到文件、磁盘区段、服务器或存储包。对象可以在不同物理位置之间移动,而不改变其标识符。

CAS 不同于内容寻址存储器;后者是一种通过比较内容来搜索已存储条目的硬件机制。CAS 实现通常根据预先计算的摘要检索对象,而不是搜索任意匹配的数据。

身份、表示与不可变性

字节相同与语义相同

CAS 标识的是一种具体表示,而不是抽象含义。两份文档即使仅在空白字符或字符编码上有所不同,通常也会具有不同的地址。同样,包含相同逻辑记录但排列顺序不同的文件,也不会自动拥有同一个标识符。

应用程序可以采用规范化序列化,确保等价的结构化值生成完全相同的字节序列。这要求明确规定字段顺序、数字表示、文本规范化等细节。如果没有共同遵循的规则,不同实现即使对对象含义的理解一致,也可能计算出不同的地址。

对象的定义还可能包含类型标签、长度或选定的元数据。因此,“对文件计算散列值”与“计算包含该文件的存储对象的地址”,得到的结果不一定相同。

不可变对象与可变名称

内容地址绑定的是一种特定表示。改变该表示就会生成新的标识符,因此 CAS 对象通常被视为不可变对象。不可变并不意味着对象永远不能被删除,而是指同一个地址不应被重新分配给不同的内容。

需要更新的应用程序通常会在不可变对象之上设置一层可变命名机制。分支名、文档名或“最新版本”指针都可以修改为指向新的内容地址。协调这些名称的更新仍然是一个独立问题,可能需要使用数据库事务或分布式共识。

对象粒度与结构共享

完整对象与分块

系统可以对整个文件计算散列值,也可以将文件划分为较小的块。整文件寻址简单直接,但即使只做很小的编辑,也可能需要存储一个全新的文件。

基于分块的存储可以复用未发生变化的部分。两种常见方法是:

  • **固定大小分块:**按固定的字节间隔划分数据。这种方法很简单,但在靠近开头的位置插入内容,可能会使后续许多分块边界发生偏移。
  • **内容定义分块:**根据数据滚动指纹中的模式选择边界。插入或删除内容后,这种方法仍能保留许多原有边界,从而提高相似版本之间的复用程度。

分块需要权衡取舍。较小的块可以提高共享程度,但会增加索引大小、元数据开销和查找成本。较大的块能减少这些开销,但可能重复存储更多未发生变化的数据。

用于选择分块边界的指纹,不必与用于标识和验证所得数据块的密码学摘要相同。

Merkle 结构

大型对象可以表示为清单,其中记录各个数据块的地址。目录、快照和其他复合对象同样可以包含对下级对象的引用。

当这些引用构成一个 Merkle 有向无环图时,每个父对象的地址都取决于其自身的表示,其中也包括其子对象的地址。因此,叶子对象发生变化,会使受影响的祖先对象的地址随之改变。

这种结构支持:

  • **结构共享:**多个版本可以引用同一批未发生变化的对象。
  • **高效比较:**在不存在相关散列碰撞的前提下,子树标识符相同就表明其表示的子树完全相同。
  • **增量传输:**接收方可以只请求自己缺少的对象。
  • **分层验证:**受信任的根标识符可以绑定整个可达结构。

树只是可能采用的一种形态;共享对象可能使一个节点拥有多个父节点,从而形成有向无环图,而不是严格意义上的树。

去重与存储管理

由于相同的表示通常会生成相同的标识符,CAS 天然支持数据去重。多个文件或快照可以引用同一个已存储对象,而不必各自保留独立的逻辑副本。

去重与数据压缩并不相同。去重消除重复的对象或数据块;压缩则以更紧凑的方式编码某种表示。系统可以同时采用这两种技术。例如,系统可以根据未压缩的逻辑字节计算地址,同时以压缩形式存储这些字节。

内容寻址并不要求只存储一份物理副本。数据复制和纠错码可以在保持单一逻辑身份的同时提供冗余,以保障持久性和可用性。

删除对象时,必须考虑共享引用。删除一个快照时,不得删除另一个快照仍在使用的数据块。常见策略包括引用计数和基于可达性的垃圾回收;后者会保留从指定根对象可达的对象,并回收符合条件的不可达对象。

并发上传、延迟建立的引用、保留规则以及未完成的传输,都会增加回收工作的复杂性。实现中可以采用宽限期、事务式记账,或对正在写入的对象实施临时保护。

完整性、信任与机密性

抗碰撞性

有限的摘要空间必然允许出现散列碰撞:不同输入可能产生相同输出。密码散列函数的设计目标,是使相关碰撞在计算上难以实现。

对于理想的 bb 位散列函数,以及 nn 个独立分布的对象摘要,发生至少一次碰撞的概率近似为

P≈1−exp⁡(−n(n−1)2b+1).P \approx 1-\exp\left(-\frac{n(n-1)}{2^{b+1}}\right).

当这一概率很小时,它近似等于 n(n−1)/2b+1n(n-1)/2^{b+1}。这一基于生日界的估计针对的是意外碰撞;蓄意攻击还取决于所选算法存在的弱点。

当某个标识符已经存在时,系统可以检查对象长度或比较内容。算法标识符和带版本的格式,可以在某种散列函数不再适用时支持迁移。

完整性不等于真实性

验证能够确定检索到的字节与请求的摘要相匹配,但无法确定这些字节由谁创建、执行它们是否安全,也无法确定所请求的摘要是否来自可信来源。

真实性需要独立的信任机制,例如数字签名、经过身份验证的命名服务或可信分发渠道。否则,能够同时替换对象及其所谓权威摘要的攻击者,就可以提供一对相互匹配的对象和摘要。

同样,内容寻址也不能证明数据的新鲜性。即使应用程序期待的是更新版本,旧对象在其原始地址下仍然可以完全有效。

机密性与访问控制

摘要不是加密。如果攻击者能够猜出对象内容,就可以计算其摘要,并与已知标识符进行比较。因此,暴露的标识符或去重操作的响应,可能泄露某种特定内容是否存在。

内容地址本身也不提供访问控制。持有标识符是否意味着有权检索对象,取决于系统设计。

加密会影响共享。随机化加密通常会将相同明文转换为不同密文,从而使直接的密文去重无法进行。确定性加密或由内容派生的加密可以保留一定的共享能力,但也会带来信息泄露和密钥管理方面的问题。

分布式运行与性能

在分布式计算系统中,不可变的内容寻址对象可以简化缓存和复制:对象可以在节点之间复制而不改变其标识符,各个副本也可以独立验证。点对点网络系统可以从不同提供方检索数据块,同时根据各数据块的预期地址逐一验证。

不过,知道地址并不保证能找到对象。位置发现、路由、数据保留、网络可用性和存储持久性,都需要额外机制来保障。有效标识符所指向的数据,可能已经不再由任何可达节点保留。

计算散列值也有成本。计算摘要需要处理对象的字节,而分块和索引还会带来额外工作。大量小对象可能造成可观的随机访问开销和元数据开销。实现中可以将对象打包存储、批量处理请求、缓存索引,或以更大的组为单位传输,同时保留逻辑内容地址。

因此,CAS 虽然简化了某些一致性问题,但并未消除协调、资源管理或故障恢复的需要。

发展与主要应用

由内容生成的标识符,在软件基础设施中普及之前,就已出现在研究型存储系统中。2002 年介绍的 Venti 归档存储系统采用基于散列值的数据块标识符,并共享重复的数据块。商业归档产品也推动了这一术语在固定内容记录存储领域的普及。后来的开发工具和分布式系统,使内容寻址对象图广为人知。

主要应用包括:

  • 备份与归档存储:数据备份系统在不同快照之间复用数据块,并验证已存储的数据。仅靠内容寻址本身,无法强制执行保留期限或只写一次策略。
  • 版本控制:Git(版本控制系统)通过对包含类型和长度的头部连同对象内容一起计算散列值来标识对象。树对象和提交对象将各对象连接为带版本的图,而分支引用则提供可变名称。
  • **构建与制品缓存:**构建基础设施可以按内容地址存储输出。将构建输入映射到输出的缓存属于独立的一层;要实现可靠复用,还必须完整捕获相关输入和执行条件。
  • 分布式内容分发:星际文件系统(IPFS)使用内容标识符来标识相互链接的数据结构中的数据块。文件的标识符取决于其表示和分块方式,不一定是直接对文件原始字节计算的散列值。
  • **容器镜像分发:**镜像清单和文件系统层的数据块使用摘要来标识确切的表示,而可变标签则提供便于使用的名称。

当稳定引用、可验证的检索以及未变数据的复用十分重要时,CAS 尤其有用。对于以频繁、小规模原地更新为主的工作负载,通常需要额外的索引、间接寻址或批处理机制,而不是将每次更新都视为直接覆盖写入。