RoBuSt：抗崩溃故障的分布式存储系统

### RoBuSt：抗崩溃故障的分布式存储系统 在当今的分布式系统领域，确保系统在部分组件出现故障时仍能正常运行是一项关键挑战。尤其是在面对崩溃故障时，如何保障数据的可用性和系统的高效性成为了研究的热点。本文将介绍一种名为RoBuSt的分布式存储系统，它能够有效抵抗自适应对手引发的崩溃故障，同时支持查找和写入请求。 #### 1. 背景与挑战 分布式系统面临的一个主要挑战是，即使部分组件出现故障，系统仍需正确运行。崩溃故障是常见的故障类型之一，它可能由多种原因引起，如维护工作、硬件或软件故障、拒绝服务攻击等。拒绝服务攻击尤其具有威胁性，因为它们通常难以预测和防范，可能导致服务器长时间不可用。 为了应对崩溃故障，信息和存储系统中常用的方法是使用冗余。然而，在包含数千台服务器的系统中，对所有服务器进行数据的完全复制是不可行的。因此，需要在冗余量和系统能够处理的崩溃服务器数量之间找到一个合适的平衡点。 #### 2. 相关工作 过去，许多处理分布式系统中崩溃故障的工作主要集中在故障恢复和检测上。然而，据我们所知，之前没有工作考虑过如何在仅使用多项式对数级别的工作、时间和冗余的情况下，保护分布式存储系统免受由自适应对手控制的大量（例如，超过多项式对数数量）同时崩溃故障的影响。 一些基于分布式哈希表（DHT）的系统已经被提出用于抵抗拒绝服务攻击，但这些系统对于自适应对手并不适用。Eikel和Scheideler提出的分布式信息系统IRIS，仅需要恒定的存储冗余就能抵抗自适应对手导致的崩溃故障，但它缺乏处理写入请求的能力。 #### 3. RoBuSt系统概述 RoBuSt是一种可扩展的分布式存储系统，它能够抵抗自适应崩溃故障，并且支持查找和写入请求。具体来说，允许对手完全了解存储系统，并有权使任意一组γn^(1/log log n)台服务器崩溃（γ > 0为常数）。系统的任务是在崩溃故障的情况下高效地处理任何查找和写入请求集合。 ##### 3.1 与IRIS的对比 RoBuSt扩展了IRIS的一些思想，但与IRIS只能处理查找请求不同，RoBuSt还能够处理写入请求。尽管在查找协议中可以借鉴IRIS的一些底层思想，但添加写入功能需要对整个结构进行重大更改。 - **数据组织方式**：IRIS将数据组织成每层n个数据项的层，每层使用涉及所有n台服务器的分布式编码单独编码。这意味着每当一个数据项需要更新时，所有n台服务器都必须更新其对应层的信息。为了解决这个问题，RoBuSt将数据项存储在所谓的桶中，这些桶以二叉树的形式组织。对于每个数据项，有对数数量的桶是其潜在的存储位置。 - **哈希函数的使用**：IRIS使用一组固定的哈希函数来指定数据的锚点位置，以便在对抗性拒绝服务攻击下仍能高效地处理查找请求。然而，在RoBuSt中使用固定的哈希函数会使对手能够破坏桶中数据的公平分布。因此，RoBuSt在处理写入请求时会选择新的随机哈希函数。 - **数据更新问题**：由于服务器可能不知道其信息是否是最新的，RoBuSt的系统组织和协议确保任何回答请求的服务器始终返回数据项的最新版本。 #### 4. 系统模型与预备知识 ##### 4.1 系统组成 假设存储系统由一组静态的n台相同类型的可靠服务器S = {s1, ..., sn}组成。服务器负责存储数据并处理用户请求。所有数据项大小相同，每个数据项d由唯一的键key(d)标识。 ##### 4.2 用户请求类型 - **查找请求（lookup(k)）**：用户请求查找键为k的数据项。如果存在这样的数据项，系统应返回该数据项；否则返回NULL。 - **写入请求（write(k, d)）**：用户请求存储键为k的数据项d，以便后续的查找请求能够正确回答。 ##### 4.3 通信模型 使用标准的同步消息传递模型进行服务器之间的通信。时间以同步的通信轮次进行，每一轮中，每个服务器首先接收上一轮发送给它的所有消息，处理这些消息，然后发送出它想要在本轮发送的所有消息。 ##### 4.4 崩溃故障模型 假设存在一个基于批次的自适应对手。时间被划分为由多项式对数数量的轮次组成的周期。对手完全了解当前系统，但无法预测系统的未来随机选择。基于其知识，对手可以选择任意一组O(n^(1/log log n))台服务器使其崩溃。 #### 5. 系统性能衡量指标 - **冗余度（r）**：如果存储策略使用的存储空间（包括任何控制存储）是存储纯数据所需存储空间的r倍，则称该存储策略的冗余度为r。 - **可扩展性**：如果存储系统的冗余度至多为多项式对数级（polylog(n)），则称该系统是可扩展的。 - **效率**：如果对手指定的任何查找和写入请求集合都能在至多多项式对数数量的通信轮次内正确处理，且每个服务器在这些轮次中发送和接收的消息数量至多为多项式对数级，消息大小也至多为多项式对数级，则称该系统是高效的。 - **健壮性**：如果对手指定的任何查找和写入请求集合都能在对手指定的至多Θ(n^(1/log log n))台服务器崩溃的情况下正确处理，则称该系统是健壮的。 #### 6. 底层数据结构 RoBuSt的数据结构基于一个具有Λ + 1层的二叉树，这些层被称为区域。每个区域的节点被称为桶，每个桶将保存一组数据项。 ##### 6.1 桶的组织 - **根桶（Bε）**：区域0由一个单一的桶Bε组成，它可以容纳任何数据项。 - **子桶**：每个不在区域Λ的桶B有两个子桶，分别表示为0 - child(B)和1 - child(B)。对于每个数据项d，有Λ + 1个可能的桶可以存储它，每个区域一个。 ##### 6.2 数据存储规则 - 初始时，桶不包含任何数据。 - 在系统运行期间