你也可以在自己的Linux kernel 源码目录执行以下命令生成自己的pdf,但何必自己造轮子呢。
sudo apt-get install sphinxsearch
sudo apt-get install python-sphinx-rtd-theme
sudo apt-get install texlive-latex-recommended
sudo apt-get install texlive-base
sudo apt-get install graphviz
sudo apt-get install imagemagick
/usr/bin/virtualenv ~/sphinx_version
. ~/sphinx_version/bin/activate
pip install -r Documentation/sphinx/requirements.txt
make pdfdocs
安装RTAI5.2 基于Ubuntu18.04和4.14.111 内核
本文记录在我笔记本上安装最新版本RTAI(5.2)的过程和中间遇到的问题及解决方法,虽然不能覆盖所有问题,但希望能给后来者一些帮助。
安装的主要步骤:
1、安装操作系统和工具;
2、给内核打补丁并配置;
3、安装打补丁的内核与RTAI。
步骤一:安装操作系统和工具
1.1 安装操作系统
我选择的是Ubuntu18.04,因为这是带Linux 4.**.***内核的最新Ubuntu 版本(Ubuntu19.04 是以Linux5.**内核开始了)。而RTAI5.2 支持的最新内核版本即为4.14.111;
1.2 安装工具
这些工具是内核编译时需要的,下面命令可以保存为脚本执行
sudo apt install libncurses5-dev
sudo apt install libssl-dev
sudo apt install bison
sudo apt install flex
sudo apt install libssl-dev
sudo apt install libelf-dev
sudo apt install make gcc
sudo apt install patch
sudo apt install unzip
sudo apt install autoconf
注意:如果你使用的是不同的Linux 发布版(Redhat或openSUSE),有些包的名称是不同的,比如对于Redhat,libssl的安装包是libssl-devel。
注意:如果你采用的是Ubuntu16.04,那么可能因为包依赖的原因,你无法用apt install 命令安装libssl1.1,而这个包是在编译4.14.111 内核时必须的,所以建议你要么换更高版本OS,要么在Ubuntu 网站( https://packages.debian.org/stretch/amd64/libssl1.1/download )手动安装该包(sudo dpkg -i libssl1.1_1.1.0k-1~deb9u1_amd64.deb)。
1.3 安装已编译的Linux 内核4.14.111 (可选的)
该步骤是可选的,它会给系统安装上Linux4.14.111 的内核,从而获得一个默认的内核配置文件供后面使用,如果你是第一次安装RTAI,建议你执行该步骤。
在内核网站 https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/ 下载内核安装包:
cd ~/Downloads/
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-headers-4.14.111-0414111_4.14.111-0414111.201904052241_all.deb
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-headers-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-image-unsigned-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb`
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-modules-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb
然后使用dpkg -i 命令安装
sudo dpkg -i *.deb #执行该命令是可能会遇到错,再重新执行该命令可以解决;
sudo update-grub
sudo reboot
重启后可以在Grub (长按shift进入Grub)中看到安装后的内核有“Generic” 和“lowlatency” 两种。如果进入Grub 有困难,在Grub 配置文件(/etc/default/grub)中修改配置`GRUB_TIMEOUT_STYLE=hidden` 为`GRUB_TIMEOUT_STYLE=false`并更新Grub 菜单`sudo update-grub`。
步骤二:内核打补丁和编译
2.1 下载内核 (https://cdn.kernel.org/pub/linux/kernel/v4.x/)
内核的名称为 linux-4.1.111.tar.gz,为之后编译和安装方便,将源码解压到`/usr/src` 中,并创建一个软链接到该源码目录。
cd /usr/src
sudo tar xvf linux-4.1.111.tar.gz
sudo ln -sf linux-4.1.111 linux
然后,从`/boot` 中拷贝配置文件:
cd /usr/src/linux
sudo cp /boot/config-4.14.111-0414111-lowlatency .config
如果你已经有了一个配置文件(比如你安装过老版本RTAI,在其Linux 内核中拷贝其配置文件即可)uIf you already have a configuration file (e.g. in your old RTAI patched Linux system), just copy it to the source path(`/usr/src/linux`).
2.2 给内核打补丁(Ubuntu 的补丁和RTAI 的补丁)
Ubuntu 是Linux 的一个发行版本,并对Linux 内核代码做了少量修改,所以在编译内核前应该打上Ubuntu 的补丁(https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/)。
cd ~/Downloads/
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0001-base-packaging.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0002-UBUNTU-SAUCE-add-vmlinux.strip-to-BOOT_TARGETS1-on-p.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0003-UBUNTU-SAUCE-tools-hv-lsvmbus-add-manual-page.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0004-adhoc-from-__future__-import-syncconfig.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0005-UBUNTU-SAUCE-no-up-disable-pie-when-gcc-has-it-enabl.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0006-debian-changelog.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0007-configs-based-on-Ubuntu-4.14.0-11.13.patch
cd /usr/src/linux
sudo patch -p1 < ~/Downloads/0001-base-packaging.patch
sudo patch -p1 < ~/Downloads/0002-UBUNTU-SAUCE-add-vmlinux.strip-to-BOOT_TARGETS1-on-p.patch
sudo patch -p1 < ~/Downloads/0003-UBUNTU-SAUCE-tools-hv-lsvmbus-add-manual-page.patch
sudo patch -p1 < ~/Downloads/0004-adhoc-from-__future__-import-syncconfig.patch
sudo patch -p1 < ~/Downloads/0005-UBUNTU-SAUCE-no-up-disable-pie-when-gcc-has-it-enabl.patch
sudo patch -p1 < ~/Downloads/0006-debian-changelog.patch
sudo patch -p1 < ~/Downloads/0007-configs-based-on-Ubuntu-4.14.0-11.13.patch
下载RTAI5.2 并给内核打上相应的补丁 :
wget https://www.rtai.org/userfiles/downloads/RTAI/rtai-5.2.tar.bz2
sudo cp rtai-5.2.tar.bz2 /usr/src/
sudo tar xvf rtai-5.2.tar.bz2
sudo ln -sf rtai-5.2 rtai
cd /usr/src/linux
sudo patch -p1 < /usr/src/rtai/base/arch/x86/patches/hal-linux-4.14.111-x86-3.patch
同样方便起见,我们也为rtai 的源码创建了一个软链接。
注意:安装RTAI补丁和PREEMPT-RT补丁的过程是类似的,如果你想安装PREEMPT-RT补丁,它的地址在这里。下载xz或gz格式后的补丁,可以用xz工具解压发现,是一个个编了序号的补丁,通过下面命令逐个应用补丁
patch -p1 -i /path/to/004-patch.x.y.z
也可以通过下面命令应用所有补丁
xzcat /path/to/patch.xz | patch -p1
bzcat /path/to/patch.xz | patch -p1
2.3 配置内核
配置内核主要参考下面的资料:
- RTAI-5.2 源码目录下的关于配置的备注文件 README.CONF_RMRKS
- https://github.com/relacs/makertai
- https://www.rtai.org/userfiles/downloads/RTAILAB/RTAI-TARGET-HOWTO.txt
- https://github.com/relacs/makertai
如果你的配置文件是从其他老的内核里拷贝过来的,首先应执行:
cd /usr/src/linux
sudo make oldconfig
否则直接执行:
sudo make menuconfig
下面是配置项中应修改的部分:
[改为 -rtai] General setup -> Local Version
[改为 None] General setup -> Stack Protector buffer overflow detection
[Enable] Processor type and features -> Interrupt pipeline
[Disable] Power management and ACPI options -> CPU Frequency Scaling
[Disable] Power management and ACPI options -> ACPI Support -> Processor
[Disable] Power management and ACPI options -> CPU Idle -> CPU idle PM support
[Disable] Kernel hacking -> Compile-time checks and compiler options -> Compile the kernel with debug info
[Disable] Kernel hacking -> Tracers
[Disable] Device Drivers -> Microsoft Hyper-V guest support
[Disable] Device Drivers -> Staging drivers -> Data acquisition support (comedi)
在 README.CONF_RMRKS 文件中要求disable `AUDITSYSCALL`,但是我们在选项中没有找到这一项。一个可替代的方法是编辑 `/usr/src/linux/init/Kconfig`文件,找到`AUDITSYSCALL` 如下部分:
config AUDITSYSCALL
def_bool y
depends on AUDIT && HAVE_ARCH_AUDITSYSCALL
替换为:
config AUDITSYSCALL
bool “Enable system-call auditing support”
depends on AUDIT && HAVE_ARCH_AUDITSYSCALL
default y if SECURITY_SELINUX
help
Enable low-overhead system-call auditing infrastructure that
can be used independently or with another kernel subsystem,
such as SELinux.
然后,你就可以在‘General Setup’选项下看到`ADUITSYSCALL`,取消即可。
如果你的主机是多CPU 或多核的,那么 `Processor type and features` 下的SMP 选项要使能(enabled),并且最大CPU 个数(`Maximum numbers of CPUs`)不应小于物理核心个数(即不考虑Hyperthreading)。因此,建议你在BIOS 中取消Hyperthreading。
步骤三:编译安装内核和RTAI
3.1 编译和安装Linux 内核
cd /usr/src/linux
sudo touch REPORTING-BUGS
sudo make -j3
sudo make modules
sudo make modules_install
sudo make install
sudo update-initramfs –c -k 4.14.111-rtai [注意修改这里的版本名称]
sudo update-grub [注意修改/etc/default/grub 启动项为自己的内核]
sudo reboot
从Linux 内核网站下载的4.14.111 版本的源码目录下没有`REPORTING-BUGS`这个文件,可能会导致你在编译的时候遇到`recipe for target ‘kernel_headers’ failed` 的错误,所以我们首先创建了这个文件。
如果一切顺利的的话,你重启后将在Grub 上看到你自己编译的内核选项:ubuntu18.04_4.14.111-rtai 。
3.2 安装RTAI5.2
RTAI 需要autotools 生成链接编译工具:
cd /usr/src/rtai
sudo autoconf
sudo ./configure
接着配置RTAI :
sudo cp ../linux/.config .rtai_config
sudo make menuconfig
将CPU 个数(`number of CPUs`)设置为实际的物理核心个数即可。
sudo make
sudo make install
如果在编译时遇到下面的错误:
make:execup: .//config.guess: Permission denied
make:execup: .//config.sub: Permission denied
手动修改权限后再编译:
chmod 764 ./config.guess
chmod 764 ./config.sub
RTAI 默认的安装路径是`/usr/realtime`,其中`modules`目录下是编译后的模块库, `testSuite` 目录下是RTAI 的测试程序,通过手动加载模块和运行测试程序可以验证RTAI是否安装成功。
cd /usr/realtime/modules
sudo insmod rtai_hal.ko
sudo insmod rtai_sched.ko
sudo insmod rtai_fifos.ko
sudo insmod rtai_sem.ko
sudo insmod rtai_shm.ko
sudo insmod rtai_rtdm.ko
一般来说,负责进程调度的 rtai_sched.ko 模块如果加载后无死机,则安装成功。
可能遇到的问题
最后罗列一些可能遇到的问题:
1 编译内核时, `implicit declaration of function ‘ipipe_root_**_syscalls’ did you mean ‘ipipe_handle_syscall’ ……` 错误
原因:在内核配置里,ipipeline 没有使能(Enable);
2 加载`sudo insmod rtai_hal.ko` 和`sudo insmod rtai_` 后,系统冻死,键盘和鼠标均无响应
可能原因:General setup -> Stack Protector buffer overflow detection 选项默认是`Strong`,应设置为`None`或 `Regular`,更多配置项参考 README.CONF_RMRKS 。
3 不能进入编译Linux内核后的系统,提示`Gave up waiting for root file system device. Common problems: …… ALERT! UUID=8e478c20-25e4-49c0-…… does not exist. Drop to the shell`.
可能原因:系统无法识别存储设备,注意配置内核时关于存储的驱动(SATA/PATA)要使能,因为我是在U盘中安装的系统,因此U盘相关的驱动也得使能。
4 当准备加载 rtai_hal.ko 模块时,提示`ERROR: Could not insert module rtai_hal.ko: Operation not permitted`错误,系统日志Syslog(`/var/log/syslog`) 提示`RTAI[hal] RTAI configured with less than num online CPUs`。
可能原因:RTAI 配置的CPU 个数比实际CPU 核心数要多,切记不要算上超线程(Hyperthreading)。
以上错误远不能包含所有你在安装RTAI 时遇到的问题,但你还可以借助下面的工具来帮助你的调试。
一些有用的命令和工具
- Dmesg
dmesg
- Syslog
sudo cat /var/logsys
- Systemctl
Systemctl -failed # 查看哪些内核没有被正常加载
- RTAI 官网和邮件列表
www.rtai.org
- Dpkg
dpkg –list | grep linux-image
- mkinitramfs
寻找最大容错的扁平XOR 码
参考:
[1] Finding the most fault-tolerant flat XOR-based erasure codes for storage systems [PDF]
[2] Determining fault tolerance of XOR-based erasure codes efficiently [PDF]
本文内容主要来源于上面两篇文章,主要讨论暴力搜寻方法具有最大容错能力(most fault-tolerant)的扁平(Flat)XOR 码。
XOR 码是通过异或运算(exclusive OR)进行数据编码、解码和重建的编码方法,其生成矩阵可以用1/0 二进制矩阵表示。
扁平码是一种每个节点只保存一个符号(数据块),即生成矩阵的每一行(列)对应一个节点。k 和m 分别表示原始数据块个数和校验块个数的话,扁平码的生成矩阵是一个(k+m)×k 大小的0/1 矩阵。常见的RS 码是扁平码,但不是XOR 码;CRS 码不是扁平码,是XOR 码。
暴力搜索通过遍历所有的解空间(所有可能的(k, m) 编码),通过计算每个解的性质,找到满足条件的编码。一个(k+m)×k 大小的0/1 矩阵有2^((m+k)×k) 种可能的二进制矩阵,如果将编码限制在系统码中,则有2^(m×k) 种可能的二进制矩阵。
[2] 中介绍了一种ME (Minimal Erasures)算法,是暴力搜索的关键,该算法通过找到最小失效列表(Minimal Erasure List)寻找某种编码的最大容错能力。ME 算法会用到几个术语:
汉明距离(Hamming distance):如果一个编码的汉明矩阵是d,那么它能容忍的最大失效节点少于d 个。
失效样式(Erasure pattern):一组失效(的数据块)使得有一个原始数据块无法被恢复。
失效列表(Erasure list):所有失效样式的集合。
失效矢量(Erasure vector):长度为m 的矢量,其中第i 个元素是失效列表中长度为i 的失效样式个数的总和。比如 < 0, 0, 3, 7, …> 表示有失效列表中有3 个长度为3 的失效样式,有7 个长度为4 的失效样式。失效矢量中第d 个值是第一个非零值(小于d 的失效均可恢复)。
最小失效(Minimal Erasure,ME)是一种特殊的失效样式,它的每个失效元素都是必须的,如果去掉其中之一,它就不再是失效样式。
最小失效列表(Minimal Erausre List,MEL)是一个编码的所有最小失效的集合。
最小失效矢量(Minimal Erasure Vector,MEV)是一个长度为m 的矢量,其第i 个元素是MEL 中长度为i 的ME 的个数。
ME 算法具体详见[2] ,其输入是编码的生成矩阵(或Tanner 图),输出为MEL 和MEV。下图给出了 m < 8 和 k < 8 的结果。
下图是m < 11 和 k < 21 所有扁平XOR 码的最大汉明距离。
下图是m < 11 和 k < 21 所有扁平XOR 码中具有最优容错的个数。
下图是下图是m < 11 和 k < 21 所有扁平XOR 码中能够达到最大汉明距离的个数。
[1] 还介绍了如何减少搜索的解空间等优化的方法,并指出搜索算法有部分是Python 写的,用C 能够进一步提高运算速度,并增加m 和k 的值。
遗传算法解决数学等式(续)
之前的文章(http://blog.foool.net/2017/08/用遗传算法解决简单的数学等式问题/) 中介绍了过如何使用遗传算法解决数学等式问题,即寻找满足等式
(a + 2b + 3c + 4d) – 30 = 0
的一组解。适应函数确定后,影响算法好坏的主要依赖于交叉概率(crossover ratio),变异概率(mutation ratio)、初始基因组大小(即用于交叉变异的基因个数)和基因初始阈值。基因初始阈值指的是基因的取值范围,比如等式中变量a/b/c/d 的取值范围,我在实验中限定变量为大小不超过100 的整数。下面给出本文的几个结论。
一、遗传算法也可以用于寻找唯一解
之前的文章 中寻找的是四元一次等式的一个解,这个解的个数是无穷的,遗传算法能够找到一个解,但每次找到的解也不相同。但如果要用遗传算法解一个包含四个等式的四元一次方程组(唯一解)也是可行的,只是时间话的需要更长。比如遗传算法解四元一次等式平均需294 次迭代,解四元一次方程组需11400 次迭代(所有参数同之前的文章)。本文使用的四元一次方程组为:
(a + 2b + 3c + 4d) – 30 = 0
(2a + 2b + 2c + 2d) – 24 = 0
(3a + 1b + 7c + 1d) – 60 = 0
(4a + 3b + 2c + 1d) – 30 = 0
二、增加初始基因组大小有可能加速算法速度
增加基因组中基因数量,那么每次迭代/循环中的基因数量更多,可能出现解的概率增大。在以四元一次等式为例的实验中,增加基因组大小的确显著减少了迭代的次数,即使考虑了增加基因数目而带来的增量计算,算法仍减少了程序的整体运行时间。
三、增加初始基因组大小也有可能不能加速算法速度
有点调皮了,这个结论是和第二点结论是相左的,如在其他参数相同情况下,随着基因组大小增大,遗传算法在解四元一次方程组需要迭代的次数增加。
四、对于特定问题,参数大小影响算法性能大
下图是在基因组大小为18 时, 遗传算法1000 次测试四元一次等式求解所需要迭代次数的热力图,横坐标是变异率,从5% 到43%,纵坐标是交叉率,从5% 到70% 。热力图颜色范围是0-300,最深颜色表示300 次或300次以上迭代(比如在交叉率是70%,变异率是43%,实际迭代次数是9268次)。
综上,1.借助于适应函数,交叉、变异过程,遗传算法给出了一个在较大解空间快速求解的途径,但具体设计交叉、变异过程需要考虑特定问题;2.选取合适的参数极大影响了遗传算法性能,一般可以通过相似问题(复杂度更低)的参数选择作为参考(但是这种参考也不一定可靠,比如上面例子中,四元一次方程中增大基因组个数可以减少迭代次数,但在四元方程组中增加基因组个数却增加了迭代次数)。
自循环字符串/周期性字符串的判别和概率
问题来源:需要判断一个长度为N 的0/1 二进制字符串是自循环的概率是多少?自循环指的是一个字符串循环移位s 位仍然可以得到其本身,s 小于字符串长度。比如,010010 是自循环的,因为将这个字符串循环右移三个bits 字符串还是其本身。
通过自循环字符串特征很容易推导出:自循环字符串是周期性字符串,即字符串完全由若干个相同子串拼接得到,上面例子中重复的子串是 010。并且,自循环字符串移位得到其本身需要的最少步数s 和最小子串长度相同,也就是说,计算得到字符串最小重复子串也就得到了其自循环需要移位数s。
那么问题归结为如何找到一个周期性字符串的最小重复子串?
算法:令周期性字符串为S,那么SS 是两个S 的拼接,从SS 第二个字符开始,利用字符串匹配寻找S,如果SS 从第c 个字符开始包含了S 字符串,则S 的最小周期子串长度为c。下面是两个例子:
例子一:S = 010010
SS = 010010010010
- 0 1 0 0 1 0 0 1 0 0 1 0 不是S
- 0 1 0 0 1 0 0 1 0 0 1 0 不是S
- 0 1 0 0 1 0 0 1 0 0 1 0 是S
结束,最小子串长度为3,即010 。
例子二:S = abaaabaaabaa
SS = abaaabaaabaaabaaabaaabaa
- a b a a a b a a a b a a a b a a a b a a a b a a
- a b a a a b a a a b a a a b a a a b a a a b a a
- a b a a a b a a a b a a a b a a a b a a a b a a
- a b a a a b a a a b a a a b a a a b a a a b a a
结束,最小子串长度为4,即abaa 。
接着统计了下二进制字符长度(X轴)和周期性字符串个数/概率(Y轴)关系。
可见,自循环字符串个数和概率与其字符串长度有关,总的来说:
- 长度越长,包含的自循环的字符串个数越多,呈指数增加
- 长度越长,字符串可能是自循环的概率降低,呈指数下降
- 素数只有两个自循环字符串(全0,全1)
- 包含分解因子越多,越可能包含更多自循环字符串
Clay Codes — 从生成矩阵的角度来看
Clay Codes ( Clay Codes: Moulding MDS Codes to Yield an MSR Code ) 是FAST18 上提出的一种编码方法,文章地址,Clay 码能够将一般的MDS 码(最优容错)转化为具有最优修复的编码方法,具有以下性质:
- Minimum Storage (最小存储开销,同经典RS码和最小存储再生码,MSR)
- Maximum Failure Tolerance(最大容错,即 (n,k)-Clay 码可以容任意n-k 失效)
- Optimal Repair Bandwidth (最优修复开销,能够达到理论最优值)
- All-Node Optimal Repair (最小开销修复所有节点的数据,包括原始数据和校验数据)
- Disk Read Optimal (最优磁盘读)
- Low Sub-packetization (低分包数,即码字长度短)
首先介绍下Clay 码的设计思想,第二部分从生成矩阵的角度来看看Clay 码如何实现。
一 Clay 码的设计思想
1.1 术语
首先文章介绍了一些基础概念:
纠删码:纠删码将一段原始数据等分为k 份,进而编码为m 份,共计n=k+m 份,通过将这n 份数据分别存储在n 个不同的存储节点上,达到抵御数据丢失的风险。
标量码/向量码(Scalar code/Vector code):标量码每个码字在每个节点上包含一个字节,向量码在每个节点上包含若干个字节,共同组合为一个超字节(superbyte),不同节点上超字节共同组成一个码字。
上图表示标量码,下图表示向量码。在磁盘阵列中,每个条带(stripe)也是横跨n 个节点,对应的一个码字,而码字中一个字节(标量码)或者超字节(向量码)则对应着条带中的一个数据块。一个(n,k) 标量码和向量码在生成矩阵中对应的是一个n×k 和nw×kw 矩阵,其中一个超字节包含w 个字节。
MDS 码:最大距离可分(Maximum Distance )码是一种最优容错编码方法,即编码后的n 份数据最大可容忍任意m 份数据失效,原始数据也不会丢失。常见的RS、CRS、Evenodd、RDP 码都是MDS 码。
修复开销:修复开销指的是重建一个节点数据或单个数据块所需要的数据量(从磁盘读取、从网络传输的数据量)。在存储系统中,单点失效是常态,因此研究更注意单点失效的修复开销。
MSR 码:最小存储再生码(Minimum Storage Regenerating codes,MSR 码)是一类具有最小存储开销下的再生码。再生码是一类能够减少修复开销的纠删码。
原始数据量为M,再生码在每个节点存储的数据量为α。如果每个节点存储量最小,即α=M/k,那么这个再生码是MSR 码,和其他经典(n,k)-MDS 码存储开销相同。当一个节点失效,需要从剩余d<(n-1) 个节点中每个取β<α 数据完成修复,修复开销为dβ。当n-1 时,修复开销最小,为(n-1)α/m。
磁盘开销:再生码是网络编码研究者提出的,在数据修复时在网络上传输的数据量能够达到理论最小,但需要在磁盘上读取大量数据,进而计算得到少量修复数据进行数据修复,因此需要额外的磁盘访问和计算。Clay 码能够减少磁盘开销,即在网络上传输的数据就是从磁盘哦读取的数据。
系统码:系统码编码后保留了原始数据,非系统码编码后只有校验数据。实际存储系统中常见的是系统码,这样数据读取不用解码。
1.2 编码方法
下面以(n=4,k=2) 来介绍Clay 码,一种将一般MDS 码转化为MSR 码的方法。
Clay 是Coupled Layer 的结合,包含了Clay 码的两个特点:1 将MDS 码分层处理;2 分层之间耦合数据。
一个(4,2)-MDS 码编码后的数据有4 份,可以摆放成一个正方形。
四个(4,2)-MDS 码编码后的数据可以形成一个四层的棱柱,四棱柱的四个边对应着四个存储节点,边上的四个点所代表的数据存储于同一个节点。(下图a_0/b_0/c_o/d_0 都存在同一个节点)
耦合是将分层中不同数据进行线性组合,以实现最小修复开销。
图中被耦合的数据块用黄色表示,没有参与耦合的数据块用红色表示,两两耦合对应的数据块如上右图所示。如何选择耦合的数据块对文章中有也介绍,但为什么这样选择文章未提及。
下面谈谈什么是耦合,耦合即通过线性组合两个数据块,不管这两个数据块是原始数据块还是校验数据块。然后再将两个线性组合后的数据块(Coupled)取代两个原来未耦合的数据块(Uncoupled)。下图中(a_0, b_0),[a_0,b_0] 表示的就是数据块a_0 和b_0 的线性组合。注意:实际中Clay 码在节点上存储的是耦合后的数据,这样才能保证Clay 码的最优修复。
两个数据块的线性组合可以表示为数据块的乘法,解耦同理,如果用C(p) C*(p)表示两个耦合的数据块,解耦即乘以解耦矩阵,
γ 为不等于0的值,使得矩阵(在对应的有限域)满秩即可,比如2。
1.3 最优修复单点失效
下面以一个节点的修复来展示Clay 的最小修复开销,(4,2) 编码最小修复开销为(n-1)α/m = 3α/2 = 6,这也是其他MSR 的最小理论修复开销。下图给出了原a_2 数据块所在节点的修复过程。
Clay 修复该节点失效只需要第二层和第三层的剩余数据块(如上图(中)所示),修复步骤如下:
- 两个耦合的数据块(b_3,d_1) 和[b_3, d_1] 解耦得到b3 和d1,如上图(右)
- 第二层通过b1,b3 的MDS 解码得到b_0, b_2,第四层MDS 解码得到d_0,d_2
- 利用第二层中[a_2, b_0] 和步骤2 得到的b_0 得到a_2,同理得到c_2;
简单推导可以发现其他三个节点也可以以最小开销完成数据修复。
1.4 系统码
需要注意的是Clay 码这时虽然满足了所有节点的最优修复,但耦合的过程中某些数据已经不再是系统码,因为某些原始数据已经线性组合为校验数据。作者因此提出了一种“耦合-编码-再解耦”的方式来保证Clay 码的系统性(systematic),如下图所示。
首先对原始数据进行耦合,经过MDS 编码后再解耦,这样原始数据还是原始数据,但校验数据不再是MDS 编码后的校验数据了。
但如果是这样理解的话,会存在一个问题:MDS 编码前,耦合的校验数据为空,导致一个原始数据和空数据耦合,那么解耦后的数据能延续刚才的最优修复么?
换个角度,如果耦合的两个数据块中有一个是原始数据,是不是可以选课合适的耦合方程来保证原始数据不发生变化,即数据块a,b 耦合后可以是a,xa+yb(a 是原始数据)或xa+yb,b(b是原始数据)的形式么?但如果需耦合数据都是校验数据块呢?
这几个问题可以通过生成矩阵的方法来解释。
二 Clay 码的生成矩阵
本节用生成矩阵这个工具来展示如何实现Clay 码,即生成(4,2)-Clay 码的生成矩阵并验证其最优修复性质。
首先利用Clay 码“耦合 – MDS编码 – 解耦” 的变换过程构建其生成矩阵。因为三个变换都是线性变换,所以可以用三个矩阵来代替。
注意:前面我们提到解耦矩阵和耦合矩阵是互逆的,这是针对两个需要耦合/解耦数据块而言的,本节所讲的耦合、解耦矩阵是针对所有数据块,且需要在中建添加MDS 编码过程,所以本节耦合、结构矩阵大小不同,更不互逆。
|G| 是Clay 码的生成矩阵,那么
|G| = |U|×|GM|×|C|
|U|是解耦矩阵,|GM| 是MDS编码的生成矩阵,|C| 是耦合矩阵。
首先从最简单的MDS 编码矩阵 |GM| 开始,一层MDS 编码生成矩阵是一个2×2 单位矩阵和2×2 校验矩阵组合得到的4×2 的生成矩阵(如下左图所示)。四层的MDS 编码矩阵如下右图(在生成矩阵右边标出了该行向量对应的数据块)。
为了使得一个码字中原始数据部分放在一起,可以进行一个对齐操作,即将单位矩阵放在上面,新的生成矩阵为|GM|。
根据所对应数据块位置和耦合规则,可以得到解耦矩阵 |U|,如下图所示。
因为MDS 编码后,有16个数据块,所以解耦矩阵|U| 大小为16×16。
耦合矩阵是一个8×8 大小的矩阵(因为四层MDS码有8 个原始数据块,|GM| 大小是16×8)。那么利用|G| 矩阵上半部分是单位矩阵可解出耦合矩阵|C|
|G| = [I P] = |U|×|GM|×|C| → |C| = |I+L×GP|^{-1}
耦合矩阵|C| 是 |I+L×GP| 的逆矩阵,L 是解耦矩阵|U| 右上分块矩阵,GP是MDS 编码生成矩阵|GM| 下半部分的校验部分。
下面介绍程序验证过程。首先是测试当λ=2 时,两个数据块的耦合和解耦矩阵。
当λ=2 时,计算得到的耦合矩阵|C| = |I+L×GP|^{-1} 为
MDS 码采用RS码,|GM| 为
耦合矩阵乘积为 |GM|×|C| 为
最终(4,2)-Clay 码生成矩阵|G|为
最后,用程序验证了这个矩阵的最优修复性质,具体而言,首先将该矩阵等分为4×8 的4个子矩阵,依次失效每个子矩阵,从失效子矩阵以外的矩阵中选取行向量重建该失效子矩阵,所需要选取的子矩阵的行向量个数即需要重建数据块的数量,验证发现所有子矩阵修复都只需要6 个行向量,达到了最小修复开销。