Clay Codes: Moulding MDS Codes to Yield an MSR Code

0.Abstract

为了保证可靠性，引入RS码，MDS码满足存储需求，但是不满足其他需要（我理解主要是网络），MSR码很多都是只有理论结构，clay code是MSR码，通过在任意单个MDS代码的多个堆叠层之间使用成对耦合，提供了一种简化的解码/修复结构。（设计思想，这部分还需要再看看）

clay code提供了MSR码的第一个实际实现

低存储开销

在三个关键参数方面同时优化:修复带宽、子分组级别和磁盘I/O

数据和奇偶校验节点的统一修复性能

支持单节点和多节点修复，同时允许更快和更有效的修复

MSR是向量码（一个新的概念）

本文对clay code性能进行了评估，存储开销增加1.25x，带宽减少2.9倍

1.Introduction

介绍了MDS码的优点，节省存储容量。介绍了缺点，修复成本高，增加带宽和修复时间。

MSR具有MDS所有优点，并且需要较小的修复带宽。

但是对于实际系统来说缺乏几个关键属性

计算上更加复杂

对不同类型的节点故障表现出不一致的修复特征

有限的容错（1，2）

缺乏常用RS的结构

本文提出了扩展之前理论的Clay codes

主要思想

Clay codes are constructed by placing any MDS code in multiple layers and performing pair-wise coupling across layers.

本文实现了Clay,集成到了Ceph

存储开销为1.25x，修复网络流量降低2.9倍

2.Background and Preliminaries

Erasure Code

介绍了下有限域，利用上标区分矢量与标量

Scalar Codes

每个chunk由L个字节组成，标量码，每个块中选择1字节，总共k字节，通过m种不同的方式，得到m字节，n=k+m称之为码字，重复L次，创造L个码字

Vector Codes

使用的是α > 1的有序集合

称之为superbyte

编码过程中，从k个数据块中挑选一个超字节，并且以m不同的方式线性组合这些超字节，以获得m校验超字节

n=k+m叫做 (vector) codeword

N=L/α

α是超字节的子分组级

Scalar Codes可以认为是α为1

Vector Codes可以认为用一个向量码替代α标量码字

故障节点中的编码修复可以通过访问超字节中α字节的一个子集来实现

故障节点中的编码块的修复可以通过访问超字节中α字节的一个子集来实现，该子集存在于每个剩余的编码块中

减少了由于节点修复而引起的网络流量

Sub-chunking through Interleaving

上图与超字节相关联的α字节被连续存储，当sub-packetization level α比较大时，考虑到涉及多个码字的操作时并行执行的，从易于记忆访问的观点，交叉字节是有利的，以便不同码字的对应字节被连续存储

当一个块中的超字节数很大时，通过交叉，每个数据块被划分为α子集，称之为子块，因此，节点内的每个子块从存储在节点内的N个码字中的每个字持有一个字节。（这部分不太理解）

MDS Codes

无论时矢量还是标量，（n,k）都可以从任何n-k节点恢复，称之为MDS，有最小的冗余开销。

RS

Row-Diagonal Parity

EVENODD

Node Repair

节点修复操作，产生了大量的网络流量，RS码，流量消耗大

MSR Codes

Vector MDS的一种，具有最小的可能修复带宽

介绍了一些相关的参数

除了MSR低存储开销和低带宽开销的特点，还希望具有以下特点

uniform-repair capability

minimal disk read

low value of sub-packetization parameter α

a small size of underlying finite field over which the code is constructed

2.1 Related Work

节点有效修复工作

Locally repairable codes

Xorbas

piggy-backed RS codes

都没达到MSR的属性

目前各种MSR都没达到所有想要的性能

FMSR codes

允许有效的修复，但是重构数据的功能不一定与故障数据相同，需要执行额外的解码操作来检索原始数据

Butterfly

通过实验验证了减少数据下载对节点修复的理论证明好处

sub-packetization比较大

m=2，对修复带宽限定较大

HashTag

α≤(n?k)k/n?k

允许以修复带宽为代价灵活的选择α

仅支持系统节点的有效修复，需要在辅助节点上进行计算，并且涉及大的有限域运算

product-matrixMSR

具有非常低的子分组

很小的有限域大小

但是需要很大的存储开销

zig-zag codes

提出了第一个理论结构

当d=n-1 时，每个n，k的低存储开销的MSR码

构造是非显式的，决定parities的有限域系数必须由计算机搜索找到

尽管有许多理论构造和较少的实际实现，但寻找具有上述所有理想性质和实际评估的MSR代码仍然是难以实现的

Ye and Barg的理论，改变了之前的情况

提供了一种结构，允许存储开销尽可能接近于1，子分组水平接近于可能的最小值，有限域大小不大于n，最佳磁盘I/O和全节点最优修复

Clay code实现了上述理论的结构，并且还具有一些额外的优势。

2.2 Refinements over Ye-Barg Code

Clay code

从耦合层的角度实现

数据解码算法和节点修复算法，都可以用两种操作

scalar MDS code

字节对之间的基本线性变换（Ye-Barg Code隐式，Clay Code显式）

Clay使用任意MDS，Ye-Barg code基于Vandermonde-RS codes

在耦合层架构中使用相同的MDS代码，并获得MSR的额外好处，Clay Code提出了一种用于修复多个故障的通用算法，允许我们在减少修复带宽的情况下修复多个节点。我们的改进针对于实现。

3. Construction of the Clay Code

Single Codeword Description

N=1,L=α

Parameters of Clay Codes Evaluated

通过增加d-k+1，减小修复带宽

例子（n=4,k=2） d = 3, α = 4,β=2,M=8

存储开销n/k=2,修复带宽降到了0.75

Starting Point

(4,2)Scalar RS Code

有相同的y，称之为由相同的y-coordinate

The Uncoupled Code

存储在相同的4个节点上，相同的RS码，4个码字

每个节点存储4个字节，每个字节与一个不同的码字相关联，用z来索引

由4个垂直的列组成，每个列由4个柱面组成，每一个列存储一个超字节，每个柱面存储一个字节

Using a Pair of Coordinates to Represent a Layer

层的耦合用层的z索引来表示 z=2z0+z1

用x=zy

Pairing of V ertices and Bytes

用p来代替（x,y,z）,p和p*耦合

被染成红色的是未配对的，剩余的顶点成对，有相同的y

16个顶点中，由8个是未配对的

图7中黄色线连接起来是配对的

Transforming from Uncoupled to Coupled-Layer Code

Encoding the Clay code

具体过程再看看

Intersection Score(IS)

4. Ceph and Vector MDS Codes

4.1 Introduction to Ceph

Ceph

分布式存储系统，将数据存储为对象

OSD

守护进程，与存储单元(如固态或硬盘)相关联，用于存储用户数据

支持多个EC，对象存储在逻辑分区被称之为pool

每个pool有多个PG，一个PG是n个OSDs,n是与池关联的纠删码块长度

OSDs分配是动态的，由CRUSH算法执行。

当一个对象流到Ceph时，分配一个PG，每当有新对象添加时，或者active osds失效时，会进行动态负载均衡

有一个OSD被指定为主OSD（p-OSD）,需要存储一个对象时，该对象被传递给已分配PG的p-OSD，该p-OSD还负责发起编码和恢复操作

从data object到数据块的传递时两步完成的。对于大对象，执行编码和解码操作所需的缓冲内存量会很大。先被划分为称之为stripes，大小用S表示，不够补0

4.2 Sub-Chunking through Interleaving

补0，确保S可以被kα整除

编码相当于码字为N=s/kα,下一步，从每个OSD的末尾获得α子块，每个N字节，我们使用之前L的定义，L=S/k

向量码的优点是，通过传递α子块的子集来修复被擦除的编码块，但是会导致分段读取。

4.3 Implementation in Ceph

实现了Jerasure和GF-Complete

实现中，多了一块额外的缓冲区，U-buffer，用来存储U，大小为nL=Sn/k

Pairwise Transforms

给了sure_matrix_dotprod()和galois_w08_region_multiply()来实现{U,U?,C,C?},剩下两个块求解另外两个

Encoding

对一个对象的编码，通过p-OSD,假设m个校验块已经被erased

然后通过初始化码的解码算法，使用这些数据块恢复m个块。

与MDS编码相比，对正向和反向转换是Clay编码所需要的唯一额外计算

Enabling Selection Between Repair & Decoding

当多个OSDs出故障，会影响多个PG，触发所有相关对象的恢复操作，引入is_repair()，以便在带宽、磁盘I/O高效修复算法和默认解码算法之间进行选择

Helper-Chunk Identification

mini-mum_to_repair()，选择d个helper

Fractional Read

对于有效的修复，我们只读取块的一部分，通过ECSubRead

Decode and Repair

4.4 Contributions to Ceph

Enabling vector codes in Ceph

增加了向量码的插件

Clay codes in Ceph

实现了Clay Code

5.Experiments and Results

单节点的性能

5.1 Overview and Setup

我们对选定的参数集和实际比较相近的实验评价

C1 VS RDP

C2 VS LRC

C3 VS RS（used in Backblaze ）

C4 C5 C6和（14，10）RS对比，主要是multiple-erasure的情况

Experimental Setup

M4.xlarge

(16GB RAM, 4 CPU cores)

500G ssd

Ceph storage cluster

consists of 26 nodes

One server

dedicated for the MON daemon

remaining 25 nodes

each run one OSD

总存储12.2TB

Overview

两种负载，固定和可变

可变

64MB

82.5%

32MB

10%

1MB

7.5%

故障域是一个节点，我们通过移除OSDs将节点故障注入系统。

利用nmon和NMONVisualizer工具进行测量

单个PG和多个PG的方案

测量

repair network traffic

repair disk read

repair time

encoding time

I/O performance for degraded

5.2 Evaluations

Network Traffic: Single Node Failure

Disk Read: Single Node Failure

非连续读会引起性能下降

最坏和最好的情况分析

 

 

 

 

6 Handling Failure of Multiple Nodes

 

6.1 Evaluation of Multiple Erasures

这部分结合附录来看

 

7. Conclusions

Clay code理论上在MDS中由最小可能的修复带宽和磁盘I/O。在MSR码类中，Clay code具有最小可能水平的子分组。我们通过实验验证了这些特性的存在。

Clay code的构造分为两步

stacks in layers, 从MDS代码中提取的α码字

将不同层的元素配对并转换以生成Clay代码

实现了从理论到实践的飞跃