HYDRAstor：可扩展的二级存储

原文：HYDRAstor: a Scalable Secondary Storage.

HYDRAstor（官网）是NEC推出的二级存储系统,先后有多篇关于HYDRAstor的论文发表在FAST（包括后来9livesdata发表的论文）。HYDRAstor是一个完整的存储解决方案,因此涉及的方面很多,包括文件系统、DHT、dedup、erasure code等。这类论文往往是多种技术的汇聚点，可以帮助扩展自己的领域。看这篇文章只能了解有这样的东西，太多技术细节没有说明。

HYDRAstor的目标是商用产品，支持可扩展容量和性能，垃圾回收，负载均衡，高可靠性、可用性等特性。本文关注的是其后端（back-end，或者称为Hydra），一个通过分布式哈希表构建的存储网络，对外界而言就像是一个整体系统。为了支持所有流式数据访问的应用，API是块级的，上层可以实现多种访问协议，包括通用的文件系统（HydraFS）。

0.编程模型

在Hydra中，数据都以变长的，内容寻址的，不可修改的块（block）的形式存在。每个块除了包括数据以外，还有一个指针数组（指向其它的数据块）。变长是为了提高去重率；指针数组可以方便垃圾回收（为什么？）。Hydra只提供最原始的块访问接口，因此为上层应用提供了灵活性。

如图1所示，Hydra将所有的块组织成有向无循环图（DAG）。图中最多的是普通块，每个块的地址由它的内容（包括指针数组）决定；图中每个顶点（SP1、SP2）都开启了一棵树，整棵树可以看作是一个数据流，这些顶点称为可搜索保留根节点（searchable retention root），每个可搜索根结点都由用户指定一个搜索关键字（search key），它的地址是由关键字决定的，而不是块内容；还有一种可搜索删除根节点（searchable deletion root），它是一种特殊的可搜索根节点，用户写入它是为了删除一棵树；图中还有一个特殊的顶点A，它只是个普通块，它存在的原因是树还未构造完成。

Hydra提供写/读普通块，写可搜索保留块，根据关键字搜索可搜索保留块，标记删除可搜索保留块等API。至于对数据流进行分块是交给上层（例如HydraFS）去做。当写入一个数据块时，用户还需指定一个弹性等级（resiliency class），用于确定如何编码。当用户需要删除某棵树时，就写入与其根节点相同关键字的删除根节点。

论文没有提及构建树的过程，因此我们也不知道如何维持块之间的逻辑关系。后面的内容都是如何有效地存储数据块了，可能这种逻辑关系是放在上层（HydraFS）维持的吧。这一小节的目的可能是告诉我们如何去使用后端API，和后面的内容其实没什么关系。

1.体系结构

HYDRAstor由前端和后端组成。后端是一个由存储结点（storage node）组成的网格，提供可扩展的存储容量；前端由一些访问结点（access node）组成，提供可扩展的性能。后端的软件组件包括存储服务器（storage server）、代理服务器（proxy server），都是Linux的用户态进程；以及协议驱动（protocal driver），实现为库。

存储服务器组织成一个覆盖网络，每个存储结点可以运行多个存储服务器，每个存储服务器负责一部分硬盘，这就实际上将一个物理结点虚拟化为多个虚拟结点，充分利用多核资源。代理服务器位于访问结点，向上提供块级接口；协议驱动实现上层访问协议（比如文件系统），都不是本文的重点。

1.1网络

Hydra使用分布式哈希表（DHT）组织后端网络，具体使用的是一个修改过的定长前缀网络（FPN）。在FPN中，每个结点负责一个哈希前缀，图2的顶部显示了一棵哈希前缀树，它包括四个叶子结点，将整个前缀空间分为四个子空间。数据块就根据其哈希的前缀被映射到某个结点。

由于Hydra用纠删码保证数据的弹性（resiliency），而纠删码需要将数据块分片然后放在不同结点，因此每个FPN结点应该要跨越多个物理结点。Hydra并不直接用物理结点（或者应该是存储服务器）作为FPN结点，而是如图2的底部，每个FPN结点都跨越多个物理结点，称之为超级结点（supernode）。每个超级结点跨越的物理结点个数，称为超级结点维度（supernode cardinality），维度是一个重要的参数，Hydra设为12。超级结点涉及的每个物理结点称为超级结点组件（supernode component），同一个超级结点的组件可以称为伙伴（peer）。

因此，Hydra按超级结点为单位分配数据，当一个数据块根据其哈希前缀被分配到超级块时，再由超级结点内部决定如何跨物理结点存储。

1.2读写处理

写一个块时，首先根据其哈希前缀决定由哪个超级结点负责，再根据哈希前缀选出该超级结点的某个组件负责该块，称为写处理伙伴（write-handling peer）。写处理伙伴会判断这个块是否重复，如果重复就直接返回地址；否则，这个块会被压缩、分片，并且按片分布到其它伙伴处。（可见，去重的好处是可以避免压缩、分片）

读一个块时，按照同样原则选出读处理伙伴（read-handling peer）。读处理伙伴会判断最少需要多少个分片才能重构数据块，这个信息放在块的元数据里。接着，读处理伙伴向一定数量的伙伴发送读请求，如果请求都得到满足数据就读完了。如果存在请求失败，读处理伙伴就会尝试去读剩下的所有分片。

1.3负载均衡

后端的负载均衡影响了系统的可用性，如果某个物理结点放置了过多的超级结点组件，那么这个结点的失效将会影响到很多超级结点。最理想的状态是，每个物理结点根据其能力放置一定数量的组件。

Hydra不停地在尝试平衡组件的分布，使得容错性，性能和存储利用率都达到最优。一个特定分布的质量是由一个多维函数评价的，称为系统熵（system entropy）。每个结点都在评估，如果将部分组件传输给邻居结点，系统是否会更加均衡。如果系统发现一个传输能改善分布，就会执行传输。传输是很耗时的。

2.数据组织

前面部分介绍了数据块如何分布，现在介绍的是每个块的分片具体以何种形式存储在物理结点。

2.1 synchrun和synchrun组件

Hydra使用纠删码提供数据冗余，每个分片被分布在某个超级结点的一个伙伴上。由于数据块及其分片都是变长的，不方便管理，所以多个数据块逻辑上组成定长的synchrun，synchrun是数据管理的基本单元，类似于RAID的条带。synchrun物理上被分为若干（超级结点维数）个synchrun组件。因此，超级结点的第i个伙伴，存储着synchrun的第i个组件，存储着数据块的第i个分片。

在任意时刻，写处理伙伴实际上只对一个synchrun写数据，因此所有的synchrun按顺序组成了一个链。一个synchrun组件是以SCC（synchrun component container）数据结构存储的。每个SCC可以包含一个或多个synchrun组件。SCC也组成了类似的链。

图3的第一行显示某个超级结点（该超级结点覆盖了整个哈希空间，即前缀为空）的synchrun，那些叠起来的矩形就是synchrun，每个矩形为synchrun组件，这里每个SCC只包含一个synchrun组件。每个synchrun组件内的小方框代表了一个数据块的分片。一个synchrun链可以表示成维度个SCC链。在图的剩余部分，只显示了一条SCC链。

当超级结点存储了过多数据，或者有新的结点加进系统时，超级结点会分裂为两个新结点。例如图3的第二行，该超级结点分裂为2个超级结点，前缀分别为0和1。每个synchrun也都分裂为二，其中的分片（或者说，synchrun组件）根据其前缀分配到各自结点。这样的就得到了两个新的synchrun链。

分裂后的SCC显然变短了，Hydra会将邻接的SCC合并，防止系统有过多的SCC。图3的第三行显示了合并。SCC的目标大小是一个常量（100MB）。图3的剩余部分显示了删除操作，删除后，SCC也要进行合并。

Hydra是一个动态系统，由于负载均衡导致的数据迁移，需要将一个SCC链传输到另一个物理结点；或者，超级结点发生分裂。这些都不是立刻就能完成的，而是用一个后台进程慢慢进行，因此在任意时刻，Hydra都可能有某个链分裂了一半，或者迁移了一半。所幸Hydra提供了数据冗余，在大多数情况下，都有足够多的完整的链可以提供数据服务（但是，结点分裂时不是应该其所有SCC链都在分裂吗？这该如何解决？）。

3.数据服务

Hydra提供诸如数据重建、去重、删除等数据服务。重建是靠纠删码。Hydra实现的是变长的、在线的、基于哈希比对的、全局数据去重，如果一个块被认定重复，就可以省去编码的时间，所以有潜力提升性能。

删除是其中非常难的部分，因为有数据去重。Hydra引入了一个只读阶段，标记所有引用次数为0的块，引用数不是立即更新的，而是在每次只读阶段时更新自上次只读阶段以来的所有引用数。其中需要注意的问题是各个分片引用次数的一致性。在2013年的FAST上，9livesdata专门讨论了删除问题。