Geometric Partitioning: Explore the Boundary of Optimal Erasure Code Repair

0.Abstract

再生码是特殊的纠删码，目的是减少修复所需的数据量

再生码的修复粒度是块而不是字节（纠删码都是按照块修的吧？）

块大小的选择会导致流降级读时间和修复吞吐量之间的紧张关系（关键在块大小）

文章为了解决这个问题提出了Geometric Partitioning，将每个对象按照其大小和geometric顺序分成一系列块，来获得大块和小块的好处（那是不是同时存在大块和小块的坏处，所以要想办法规避这个问题？），可以达到1.85x RS的性能，同时保持较低的读取时间。

1.Introduction

提了一些经典的对象存储系统

给了个概念修复成本：由于数据丢失而需要修复的数据量

引出了再生码，修复成本最低

Recovery efficiency

系统以多快的速度恢复其原来的容错能力

修复成本的最优化并不一定能提高恢复效率或减少降级的读取时间

为了修复一个块，只从相应的磁盘中读取一小部分子块。这种分散的磁盘访问模式会导致碎片化，从而降低磁盘性能，从而降低恢复效率

分块修复粒度还会增加降级的读时间，RS可以并行修复，再生码需要等待第一个块修复，可能需要与修复对象一样多的时间

当读取小于chunk大小的对象时，也会修复不必要的数据，导致读放大，降低读时间

再生码，对象存储系统通常选择单个块大小作为编码单元，编码前将对象分割为块。

较大的块大小有助于减少磁盘访问时的碎片和不连续读取，从而提高恢复效率。

但是较大的块大小会增加等待第一个修复块的时间，增加读放大的机会

低退化读时间和高恢复效率可以同时实现

关键是在每个对象中使用可变的块大小

我们从小块开始修复，以避免不必要的等待第一个块的修复，然后限制相邻块的大小比例，使当前块的修复可以早于前一个块的转移

Geometric Partitioning

它将每个对象按照几何顺序(例如:例如4MB、8MB、16MB、32MB、64MB等)，并将来自不同对象的块分组到桶中进行编码

比最小块大小更小的对象，使用RS编码，来消除读放大

2.Background

2.1 Repair, Degraded Read and Recovery

修复

降级读

时间是重要指标，修复和传输可以pipelined

降级读时间为传输时间加上第一个块的修复时间

有效的修复可以降低MTTL，增加系统的耐久性，减少降级读的次数减轻系统的负担。

出现故障

恢复效率由吞吐量决定，磁盘带宽成为了恢复吞吐量的决定性因素，因为磁盘带宽更难以充分利用。

2.2 Repair for Different Codes

RS的修复过程

单点故障占98%以上

LRC修复过程

通过连接到更少的节点来减少I/O

再生码的修复过程

从d个节点读取，再生码通过引入粒度更细的子块和它们之间更复杂的连接来减少I/O

α和β越小越好，更好的局部性，α=16，β=4最坏情况下会有16个不连续的子块

讲了一个读取的实例

再生码种类很多，MSR,MBR，Hitchhiker，Simple Regenerating codes

再生码和RS的存储可靠性相同，提供了最佳的维修成本

本文使用clay code,但是方法适用于所有的再生码

灵活的编码参数设置

更低的计算复杂度

 

几种方法的比较

 

 

 

3.Challenges for Applying Regenerating Codes

3.1 The Effect of Chunk Size

再生码和sub-chunking技术混用，减少磁盘I/O。数据被重新编码成块，并利用一个块的大小进行解码，而不会引起像RS代码那种的读放大

Large Chunk Size Benefits Recovery

读放大的现象

修复需要64个子块，16次不连续读，对象大小256KB，每块4KB，1MB以上将不会出现读放大。HDD，I/O，4MB（对应块256MB）甚至8MB，以分摊I/O延迟并更好的利用磁盘带宽。

（从这里面看，块越大对磁盘更充分利用）

Overly Large Chunk Size Harms Degraded Read

块大小大于对象大小会导致读放大，增加降级读时间。对象大小从KB-GB。

如果一个块256MB大小，可能修复256MB对象，只为读取该块中一个64MB对象，这样会造成额外的磁盘读请求

Small Chunk Size Benefits Degraded Read.

两个步骤

从存储服务器修复必要的数据

将修复后的对象从服务器传输给最终用户

再生码块比较大的时候，没办法pipelined，小块可以减少阻塞时间，并使降级的读受益

块大小是一个关键因素。较大的块大小可以提高恢复效率，但代价是更严重的读放大和增加的阻塞时间，从而导致更长的读时间下降，反之亦然

3.2 Case Study: Applying Regenerating Code into Existing Data Layouts

Contiguous Layout

多个对象打包，形成大小相同的大文件，作为一个整体编码。

将再生码应用到连续布局中，可以选择任意大的块大小来实现高效的恢复

读放大，对象与块不是对齐的，可能多个对象打包到一个块中

小对象降级读，可能扩展到整个块或多个块，从而导致降级读时间增加

Stripe Layout

将每个对象分割成小的条带，并将每个条带扩展成为多个节点，生成校验块，会导致读放大

4.Geometric Partitioning

固定块大小不能很好地利用再生码，考虑对不同对象使用不同地块大小，但是仍然存在选择大块，流水线效率降低，小块，恢复效率降低

几何分区的设计基于以下原则:如果一个对象可以被划分成大小可变的块，那么我们就可以使用较小的块来通过流水线减少降级的读时间，使用较大的块来实现效

的顺序读，那么我们就可以同时获得小块和大块的好处

将一个块划分成多块，每个块对应一个bucket，每个bucket是磁盘上的大文件，包含来自不同对象的大小相同的块。这些桶的大小形成了一个几何序列。来自k+r磁盘的桶是使用再生码一起编码的

s0和q，初值和公比

R=S mod s0

n是被分割的块数

4.1 Cut Front to Eliminate Read Amplification

对象对齐的难点在于很难找到足够的相同大小对象，削去一部分，成为s0的倍数，削掉的部分放入单独的bucket中，叫small-size-bucket.

只要s0够大，就容易找到相同大小的块

Small-size-buckets

用于存储对象的front portion

没有特定大小，可以变化，利用RS编码，消除了读放大，降级读的pipeline可以马上开始，从而减少降级读的时间

大于97.7%的容量被大对象占用

4.2 Partition Objects Geometrically to Benefit Recovery and Degraded Read

为了提高恢复效率，应该增加块大小，从理论上讲，对对象进行分区的最佳办法是不进行分区，使块大小最大，但是影响降级读

引入可变块大小

从一个小块开始修复

相邻大小块的比例应该受到限制，以便当前块的修复可以先于之前块的转移

块尽可能大

块应该指数增长，导致了几何分割的设计

举了个32MB的例子

几何分割相对于算术序列和常数序列的好处

可以增加平均块大小

4.3 Help Pipelining by 2-pass Scan

为了pipelining，限制系数不能非0

算法1确定系数，扫描两次几何序列

第一次扫描减去每个bucket的大小，直到剩余的大小太小而不能装入一个bucket。

随后的扫描使用贪婪策略，尝试选择最大的块大小，直到没有桶可以被填满

4.4 Parameter Setting

s0较大可以扩大块大小，增加平均磁盘读写带宽，RS增加的I/O和磁盘流量，增加pipelined的开销

q较小有利于pipelined，但是并不利于恢复效率，对目标工作进行采样来调整s0和q,在降级读和恢复效率之间实现性能平衡，Grid search

5.System Design and Implementation

5.1 System Design

Architecture

RC-Stor

Directory Server

存储元数据并监控整个系统

Storage Server

存储和管理对象，存储索引来跟踪对象

绑在一个盘上

HTTP Server

处理用户请求

恢复任务由Directory Server分配到Storage Server，Directory Server的可靠性用复制来保证

Placement Groups

thousands of PGs

each PG is a group ofk+r=14 disks on 14 different nodes

PG存储在Directory Server上，每个磁盘属于多个PG，每个PG可以独立恢复

当一个磁盘失败，所有的相关PG都开始恢复，将会有更多的磁盘来加速恢复，而不止13个

Directory Server将磁盘分配给PG，以便在磁盘故障时将最大数量的磁盘关联到恢复中

对象首先根据其ID的哈希值映射到PG。然后，选择该PG使用的容量最小的磁盘来放置对象。最后，将对象划分为块并放入相应的bucket中。

Metadata Management

对于每个PG，随机选择r+1个磁盘来存储该PG的复制索引（为什么是r+1），每个索引文件跟踪PG中所有对象的元数据，并在存储服务器重启时加载到内存中。索引文件的每条记录包括对象ID、大小、磁盘ID、校验和和对象的分区块的位置。对象的平均元数据大小约为40字节。

Put and Get

提供了HTTP接口

put

先放入基于复制的对象存储系统，我们使用后台进程将这些对象从基于复制的存储系统导出到基于擦码的存储系统中。批量导出，避免校验块的更新开销

get

HTTP服务器从PG对应的存储服务器获取索引。如果是降级的读请求(相应的磁盘离线或正常读期间发生错误)，HTTP服务器将从storage Servers收集必要的数据，重新生成并将该对象传输到客户端(通过管道)。否则，对象将被直接传输到客户端(也是管道)。

几何分区要求从多个位置上读取数据，但是普通读取的性能损失很小，因为块足够大。

IO Scheduling

每个storage Server都有一个绑定到多个线程的FIFO请求队列，这些线程连续地从该队列提取数据。为了处理请求，存储服务器将读取所有相关数据到256KB(或更小)包，并将它们推到HTTP Server。对storage server的后台请求(恢复、数据导入等)被放到单独的队列中，并以较低的优先级处理

Paralleled Recovery

recover a node

不以对象的粒度恢复，以块恢复

单个对象的块可以并发恢复

directory Server

全局队列

管理所有正在等待恢复的块

HTTP Server不断地从directory Server提取这些任务,并同时恢复，恢复任务按照大小加权

5.2 Implementation

Encoding Optimization

进行了专门的优化，使用SIMD指令和循环展开等标准优化来提高性能，利用软件预取、流写入指令来减少内存访问的开销

实现了22.3GB/s的编码，18.5GB/s的解码，以及5.0GB/s的在12核服务器上使用多线程重新生成Clay(10,4)代码

Memory Management

一个HTTP Server管理修复块的内存池，只允许分配小于或等于256MB的块

Range Access Support

支持范围访问，下载大对象的一部分

6.Evaluation

Hardware Setup

16 servers

dual Intel Xeon E5 2643 v4 CPU

128GB 2133 MHZ DDR4 RAM

512GB SATA3 SSD

6×8TB 7200rpm SAS HDD

56Gbps Infiniband network

所有服务器同时充当HTTP Server和Storage Server。我们选择三个服务器作为目录服务器

XFS用作底层文件系统，实验开始时，清除所有文件系统缓存

每台机器最多8个客户端，每个客户端网络带宽1Gbps

workload

Parameter Settings

(10,4) for Clay code vs RS code VS (10,2,2) for LRC code VS Stripe-Max

ECPipe

weight 512

Hitchhiker code

Implementation Optimizations for Baselines

对于Stripe/RS/LRC的恢复，不是逐条恢复整个磁盘，而是将I/O请求批处理到4MB的数据块(我们发现4MB的块大小可以使性能最大化)

6.2 Evaluation on Production Trace

Methodology

关闭一个磁盘，手动启动恢复，测量恢复的时间来评估效率，同时恢复所有的PG，来衡量系统的最大恢复量

评估恢复前，评估降级读时间

 

 

7. Related Work

再生码在实际存储系统中的实现

过去专注于再生码应用在系统

没有考虑降低的读时间和流水线

Vajha发现了读放大现象

Hybrid Strategies

Panasas针对不同的对象采用不同的RAID方案。

Giza主张对大于4MB的对象使用纠删码存储

autoaid混合擦除编码和复制，以提高性能

这些方法关注传统的RS码，不能解决再生码的挑战

Xia et.al.给i出对热数据使用更快的恢复和更低存储效率的代码，对冷数据使用更高的存储效率和更慢的恢复速度的compact code

但是clay code这样的MSR在存储效率和修复效率都是最优的，所以混合不再是必要的

Geometric Sequences

Buddy利用几何序列来支持动态内存分配

Dartmouth使用buddy allocator来管理其文件系统中的磁盘空间

Geometric Partitioning通过引入对象分区来区别于buddy allocator

Geometric Partitioning通过分区对象来适应连续区域

Network Pipelining

PRB和ECPipe通过消除数据采集节点的网络拥塞，减少修复时间。它们不是试图减少网络带宽消耗，而是通过在集群中更均匀地分配网络流量来减少修复时间。然而，它们是为满足加法结合性的擦除码而设计的，这对Clay code并不适用

8.Discussion

对于降级读，几何分区比分条布局需要读取更多数据，但是通过高效的流水线设计，它们可以被传输时间隐藏，所以读取时间比Stripe-Max要少得多。

几何分区将每个对象放到单个磁盘中，而不是k个中（容错性不会出问题么？）。如果有降级读，将只有一个降级读的几何分区，在CPU上负担小，由于读请求在更短的时间内降级，它对磁盘和网络的额外负担可以通过更快的恢复来补偿（这段话的含义）

RCStor存储不可变对象

再生码比LRC码占用的网络带宽少，恢复效率高（这不是全面优于？），但是LRC有更好的局部性，在跨数据中心EC中有用，因为减少了跨数据中心的流量。通过在再生代码上使用LRC代码，再生代码仍然可以提供帮助，提供更好的局域性和更少的网络带宽消耗（这个第一次见，回头可以看看）

9.Conclusion

揭示了大规模存储系统中应用再生码的实际差距，提出了几何分割，解决了读取时间降低和恢复效率之间的冲突。用真实实际的traces验证了它（本文的亮点）