Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity

在驱动现代世界的庞大且无形的底层基础设施中，数据不断地在计算机网络中被写入、存储和检索。这些系统必须足够健壮，即使在单个机器故障、崩溃或受到恶意攻击者破坏时，也能确保信息的安全。为了实现这一目标，工程师通常将单个文件分解成许多碎片，并将它们分散存储在不同的位置，这种技术被称为信息分发（information dispersal）。这确保了如果部分碎片丢失，仍能从剩余的碎片中重建原始文件。然而，一个持久的挑战在于如何平衡这种保护机制的成本。安全地存储数据通常需要保留额外的副本，这会消耗空间；而移动这些数据以修复损坏的部分或将其用于检索，则会消耗大量的带宽。多年来，最高效的数据存储方法在修复时速度缓慢且成本高昂，而修复损坏节点最快的方法又极其浪费存储空间。

研究人员托马斯·洛赫（Thomas Locher）和伊冯娜-安妮·皮格诺莱特（Yvonne-Anne Pignolet）开发了一种新方法，打破了这种权衡，提供了一种能在所有维度上同时实现高效存储、分发和恢复数据的方式。他们的工作聚焦于一种被称为“异步可验证信息分发”（asynchronous verifiable information dispersal）的特定系统，在这种系统中，计算机不需要对消息的精确时间达成一致即可正常运行，同时仍能验证其持有的数据是否有效且一致。该团队引入了一种新型协议，将数据组织成类似于网格的结构，使得节点只需共享足够的信息即可重建缺失的部分，而无需下载整个文件。这种方法显著减少了必须存储的数据量以及修复失效计算机所需的带宽，同时保持了检索信息时所需的处理速度。

这一新系统的核心在于数据在发送出去之前是如何排列的。研究人员并没有将信息视为简单的碎片列表，而是将其编码为一个二维矩阵，即行与列组成的网格。想象一下，数据就像一个大型电子表格，每个单元格都包含原始文件的一小部分。系统随后应用一种数学过程来填充这个网格中的空白单元格，从而创建一个冗余网络。网络中的每台计算机都被分配了该网格中的特定行和特定列。它仅存储属于该行和该列的数据，以及一段用于验证数据正确性的微型加密证明。这种结构是该系统高效的关键。因为每台计算机都持有其他所有计算机行与列的一部分，所以如果一台机器发生故障，它们可以互相协作来填补空白，而无需联系中央机构或下载整个数据集。

当需要存储新的数据片段时，过程始于客户端向网络发送初始的网格信息。研究人员设计了一种巧妙的握手机制，以确保这一过程快速进行且不浪费带宽。客户端向每台计算机发送必要的数据，并等待确认收到数据的反馈。如果某台计算机未能响应，客户端不会简单地向所有人重发整个文件，而是向需要这些数据的特定计算机发送一个包含缺失部分的微型定向更新。网络中的其他计算机由于在其自身的存储中已经持有缺失数据的一部分，随后会将这些特定的碎片转发给那些遇到困难的节点。这一协作步骤意味着，与以往通常需要多次发送完整数据集以确保每个人都拥有一份副本的方法相比，该网络完成存储过程所产生的总数据移动量要少得多。

检索数据的过程同样精简。当用户想要读取一个文件时，他们会向足够数量的计算机请求其行数据。由于网格构建的方式，用户仅凭这些行数据即可重建原始文件，而无需联系网络中的每一个节点。系统利用存储在碎片旁边的加密证明来验证数据的完整性，确保返回的信息既没有损坏也没有恶意。这种检索过程与现有的最佳方法一样高效，这意味着在获得其他改进的同时，并未牺牲读取数据的速度。

或许最显著的进步在于系统如何处理计算机失效时的修复工作。在旧系统中，更换一个损坏的节点通常需要新机器从网络中下载整个数据集来重建其份额，对于大型文件而言，这个过程可能耗时数天并消耗大量带宽。而在这种新协议中，替换节点只需要联系几台其他计算机，即可找回其特定的行和列数据。这些邻居节点会发送与新节点在网格中位置相交的微小数据片段。随后，新节点利用这些碎片通过数学手段重建其完整的存储份额。这大幅减少了修复过程中传输的数据量，使得该系统能够适用于节点频繁加入或离开的大规模现实应用场景。

研究人员将他们的协议与现有标准进行了对比分析，发现其在各个方面都表现优异。对于一个存储一吉字节（GB）文件的百台计算机网络，他们的方法要求每个节点仅需存储三十兆字节（MB），而一种领先的替代方案则需要四十五兆字节。对于单个文件来说，这种差异看似微小，但当扩展到全球网络中的拍字节（PB）级数据时，这意味着总存储需求减少了一个半拍字节。同样，当一个节点失效时，新系统要求替换节点下载的数据量为四十五太字节（TB），而使用之前的最佳方法则需要七十五太字节。这节省了三十太字节的流量，在全网络容量下，这代表着不再需要的近三天修复流量。

团队还探索了其协议的一种变体，允许用户根据特定需求对系统进行调节。通过调整一个单一参数，操作员可以选择进一步最小化存储空间的使用，代价是增加用于修复和检索的带宽需求。这种灵活性使该协议适用于广泛的场景，从优先考虑长期存储效率的去中心化存档，到需要快速数据访问的高性能系统。这项工作证明，设计出的分布式存储系统不仅可以在一个领域达到理论上的最优，而且可以在数据的整个生命周期内——从写入到修复或检索——实现实际上的高效。

这项研究为下一代分布式存储系统提供了具体的路径，解决了限制其扩展性的瓶颈问题。通过证明低存储开销、低写入通信成本和高效的节点恢复可以共存，作者们消除了部署稳健的去中心化数据网络的一个主要障碍。研究结果并非仅仅是理论上的，其推导出的特定常数可以直接转化为运营成本和网络容量方面的切实收益。随着去中心化存档和区块链解决方案等系统的不断增长，能够高效管理数据而不牺牲可靠性的协议将变得日益重要，而这种新方法为那个未来提供了一个平衡且高性能的基础。