Linux 内核文档PDF版(Linux kernel v5.8 documents pdf version)

accounting.pdf

doc-guide.pdf

ide.pdf

maintainer.pdf

process.pdf

timers.pdf

admin-guide.pdf

driver-api.pdf

iio.pdf

mhi.pdf

RCU.pdf

trace.pdf

arm64.pdf

fault-injection.pdf

infiniband.pdf

mips.pdf

riscv.pdf

translations.pdf

arm.pdf

fb.pdf

input.pdf

misc-devices.pdf

s390.pdf

usb.pdf

block.pdf

filesystems.pdf

isdn.pdf

netlabel.pdf

scheduler.pdf

userspace-api.pdf

bpf.pdf

firmware-guide.pdf

kbuild.pdf

networking.pdf

scsi.pdf

virt.pdf

cdrom.pdf

fpga.pdf

kernel-hacking.pdf

openrisc.pdf

security.pdf

vm.pdf

core-api.pdf

gpu.pdf

leds.pdf

parisc.pdf

sh.pdf

w1.pdf

cpu-freq.pdf

hid.pdf

PCI.pdf

sound.pdf

watchdog.pdf

crypto.pdf

hwmon.pdf

livepatch.pdf

pcmcia.pdf

sparc.pdf

x86.pdf

devicetree.pdf

i2c.pdf

locking.pdf

powerpc.pdf

spi.pdf

xtensa.pdf

dev-tools.pdf

ia64.pdf

m68k.pdf

power.pdf

target.pdf

你也可以在自己的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 配置内核

配置内核主要参考下面的资料:

如果你的配置文件是从其他老的内核里拷贝过来的,首先应执行:

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

  1.  0 1 0 0 1 0 0 1 0 0 1 0  不是S
  2.  0 1 0 0 1 0 0 1 0 0 1 0  不是S
  3.  0 1 0 0 1 0 0 1 0 0 1 0  是S

结束,最小子串长度为3,即010 。

例子二:S =  abaaabaaabaa

SS = abaaabaaabaaabaaabaaabaa

  1.   a b a a a b a a a b a a a b a a a b a a a b a a
  2.   a b a a a b a a a b a a a b a a a b a a a b a a
  3.   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.   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轴)关系。

可见,自循环字符串个数和概率与其字符串长度有关,总的来说:

  1. 长度越长,包含的自循环的字符串个数越多,呈指数增加
  2. 长度越长,字符串可能是自循环的概率降低,呈指数下降
  3. 素数只有两个自循环字符串(全0,全1)
  4. 包含分解因子越多,越可能包含更多自循环字符串

 

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 修复该节点失效只需要第二层和第三层的剩余数据块(如上图(中)所示),修复步骤如下:

  1. 两个耦合的数据块(b_3,d_1) 和[b_3, d_1] 解耦得到b3 和d1,如上图(右)
  2. 第二层通过b1,b3 的MDS 解码得到b_0, b_2,第四层MDS 解码得到d_0,d_2
  3. 利用第二层中[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 个行向量,达到了最小修复开销。