d=k+1,n=2k,α=2,β=1 Exact Regenerating Code with uncoded repair— CME

文章bibtex

@article{陈勇2012基于组合矩阵的精确修复, title={基于组合矩阵的精确修复 MDS 编码< br/>}, author={陈勇 and 武国强 and 林宝军}, journal={宇航学报}, volume={33}, number={11}, pages={1654--1659}, year={2012} }

文章提出了d=k+1, n=2k, α=2, β=1 精确修复的再生码CME(Compound-Matrix Encoding),CME 是系统码,每个节点都保存了1/n 的原始数据,存放模式如下图,一半原始数据,一半冗余数据。文章在域GF(2) 下给出了详细的构造、修复方法。

20

继续阅读

最近收到推送的文章

这两个月收到不少scholar 推送的文章,有十几篇,抽空看看了。

1  Tree-Structured Parallel Regeneration for Multiple Data Losses in Distributed Storage Systems Based on Erasure Codes(基于纠删码的分布式存储系统中针对多数据失效的树型并行修复技术)

针对多块数据丢失再生冗余数据块进行了讨论,主要是优化速度,通过并行加速修复过程。提出了一种树型修复方式

2  An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes

文章讨论了MSR的系统码(systematic code)中B(文中用sub-packetization l表示)和k 和r=n-k 的关系。(n, k)-MSR系统码要求k不能太大,否则无法修复。文中虽然没有给出k 具体的上限,但给定了一个上限

3  Symmetry in Distributed Storage Systems

文章提出一种可以达到任意码率的精确修复的(n,k,d,,α,β)再生码方案:concatenation scheme

4  Impact of Stripe Unit Size on Performance and Endurance of SSD-Based RAID Arrays

文章讨论了SSD 中RAID 分片大小,4KB 条带更适合SSD RAID

5  RAIDq: A software-friendly, multiple-parity RAID

文章基于plank 和HP anvin 的文章提出了编解码速度非常快的RAIDq ,可以详细看看

6  Rateless codes and random walks for P2P resource discovery in grids

在P2P 存储系统中使用rateless codes 实现网络编码,较少资源更新时的网络开销

7  Efficient Encoding Schedules for XOR-based Erasure Codes

之前会议的文章的republish

8  Erasure coding for cloud storage systems: A survey

从MDS 到Regenerating codes 的survey,入门survey,讲的也不是很全,但普及了概念

9  Enabling Data Integrity Protection in Regenerating-Coding-Based Cloud Storage: Theory and Implementation (Supplementary File)

香港科技大学网络编码实验的一片关于NCCloud 和FMSR 的补充说明:加密和存储开销等

10  基于组合矩阵的精确修复MDS 编码

精确修复和GF(2) 是亮点,希望这篇不会让我失望

GNU gprof 和 graphviz 调优程序

GUN gprof 是一款分析程序运行的工具,可以提供程序调用关系,函数运行次数以及函数运行时间,为程序员最大限度的优化自己的程序提供帮助。记得在《可视化函数调用》中提到了可视化工具graphviz,结合gprof 和graphviz,并利用gprof2dot 可以可视化以上以上信息。

几个工具使用起来都非常方便。使用gprof 只需要在运行参数前加 -g 即可。然后

./test

运行可执行程序,将生成gmon.out 的日志文件(这是程序员也看不懂的二进制文件),使用下面命令

gprof ./test gmon.out >report.txt

生成report.txt 表。

想使用gprof2dot 可视化这个报表就更简单了,在gprof2dot 官网 下载gprof2dot.py 执行(确保你安装了python 和graphviz):

gprof ./test | gprof2dot.py | dot -Tpng -o output.png

怎么样! 是不是生成了一个output.png 的图片,打开看看吧!

继续阅读

Valgrind Tutorial

Valgrind 是用于调试程序的工具套件,其中最有名的工具是Memcheck,它能够检测出C/C++ 中因为内存错误导致程序中断的问题。

一、引言

使用Valgrind 有两个必要条件:一安装了Valgrind;二需要在编译程序参数中加上 -g 选项;尽量不要使用  -O2 或者更高级别的代码优化,这样会导致Memcheck 误报未初始化的参数(uninitialised-value errors )。 调试方法非常简单,如果你的程序如下执行:

MyProg arg1 arg2 ...

那么这样使用如下命令:

valgrind --leak-check=yes MyProg arg1 arg2 ...

Memcheck 是默认工具(也可以用 –tool=memcheck 指定工具),–leak-check 选项打开了内存泄露检查工具。

继续阅读

Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems

原文

本文作者是NCCloud 作者在INFOCOMM13 上发表的短文。作为NCCloud 的理论基础,证明了n = k+2 = d+1 情况下,FMSR 的存在性,并给出了这类编码的一个确定的编码方式。NCCloud 和本文提到的FMSR 具有三点重要性质:

  1. FMSR 码存储效率和容错效率与MDS 相同
  2. FMSR 达到最小修复带宽
  3. FMSR 使用非编码修复(uncoded repair/repair-by-transfer)

继续阅读

Linux 下使用Doxygen

Doxygen 是支持多种语言的文档生成工具。也许在编码前能把设计文档写好,再来编写代码是正确的一件事情,当由于中间编码过程中任务的修改或者代码的优化等原因,会导致开始所写的文档变动非常大,于是在编码前写好文档对于大多数程序员是不太现实的。而在代码写完之后再补上相应的文档则是一件非常常见的做法。Doxygen 就能很好的帮你做好这件事件,在你的代码按照Doxygen 的格式写好注释后,几分钟Doxygen 就能够很快地为你生成文档。最近要使用Doxygen 也是因为代码变多后,之前写的函数往往名字都不记得了,如果能有一份文档查询相应的函数会非常方便。(值得一提的是Hadoop 支持了Doxygen 文档的生成)

继续阅读