ReedSolomon为什么要造轮子？Reed-Solomon code已经问世50余年了，是门非常成熟的并且应用广泛的技术。 在优化方面，公认的最佳做法就是利用SIMD技术加速(具体的方法我随后展开)。看上去其并不适宜重新造轮子，而且新轮子极大可能远远不如老轮子。 由于各种机缘巧合我对RS code产生了浓厚的兴趣，同时也发现了由于其过于专业，很难找到学习路径和丰富的资料。倘若我能借这个机会减轻对此感兴趣的其他人的负担和痛苦，这也算是传播一点微小的能量。 技术选型先前有提到SIMD技术，这是一种非常自然的选择。比如，利用AVX2每次可以处理32byte，这可比通用寄存器下的8byte要厉害4倍（实际效果远超4倍）。有这样的技术没理由不想办法使用它。 在SIMD技术之前，最快的解决方案应该是James S. Plank老爷子提出的，详见他的论文CRS,很遗憾我没有认真分析过其原理，大意就是将字节查表运算转换成了关于位的异或运算。 由于我是先阅读了SIMD加速RS的论文，已经被这种方式的巨大威力所折服。原先的计算瓶颈已经转移到IO上了，因此我也没有必要去深究以异或代替RS复杂运算这种曲线救国的方式了。 最后我选择Golang作为编程语言，主要有这么几个原因，一是性能相对还不错，二是其汇编也友好，可以方便的利用SIMD技术。关于Golang汇编的初探可以参考我的这篇博文：使用SIMD为Golang加速 站在巨人的肩膀上最早接触的是Jerasure的实现以及一些科普性的文章，那个时候连hello world都不会写，只留下了粗浅的印象。 后来逐渐发现了更多的开源库,其中:Klauspost参考Backblaze而实现。而我又参考了klauspost的实现。 前人栽树，后人乘凉。非常感谢这些人的贡献。 工作原理我这里并不试图展开细节，一方面事无巨细的介绍容易没有终点，二是因为涉及的知识点着实太多，每一门知识又有其必要的基础知识，这必须根据读者的水平阐述，在一篇文章中要做到这点是不可能的。 同时我又觉得我不能跳过数学原理的介绍,毕竟RS的核心就是这点东西。正所谓“授人以鱼不如授人以渔”，我便分享一下我的学习过程吧。 首先，我们得对群这个概念和性质有基本的认识，这里我推荐台湾国立交通大学的化学应用群论这门公开课。其中有两节课是纯粹讲群的和化学无关，老师很有耐心，每一步的步骤非常清楚。看完两节课，我们已经能手工写一些order非常小的域了。我建议是自己列一列加法表和乘法表以增强印象。通过逐渐熟悉域中的基本运算，可以减少我们对这些概念的恐惧。 接下来可以阅读<<代数编码与密码>>这本书关于多项式的理论（实际上在前面的基础之上只要看几个例子就行了），学习如何通过多项式构建有限域。可以手算几个结果，然后上UNB验证结果。另外在我的代码gentables.go中也可以学习生成本原多项式以及生成表的过程。 我们还需要知道矩阵运算的基本常识，基本上掌握矩阵的乘法，矩阵求逆，行列式的概念就足以应付了。我在这里推荐<<程序员的数学:线性代数>>这一书，尤其需要注意的知识点是Gauss-Jordan方法，这一方法也是目前我的代码中用来求逆矩阵的方法（由于我们使用的矩阵比较特殊，个人觉得求逆还可以再优化） 有了矩阵的基础，我们对选择编码矩阵也有了基本的认识，无非就是要保证线性无关和任意子矩阵可逆。我在代码中使用的是Cauchy matrix,相较于传统的Vandermonde matrix，其使用起来更为便利，直接拼接单位矩阵就可以满足我们所需要的性质。 数学的部分学习过程基本讲完了，还有一丁点数学相关的内容是和优化相关的。非常的简单而优雅，寥寥几句就可以阐明核心,但我还是推荐大家读一下论文Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions 其加速的基本原理就是将一个byte以4bit为界限拆分成左右两个部分从而达到压缩乘法表的目的，如下图所示： 
每一个4byte的乘法表只有16byte的长度，正好可以塞进XMM寄存器里。对于YMM寄存器，我们则可以通过复制塞两张表进去。这里才是SIMD能为RS服务的最大原因，也可以认为是为了使用SIMD带给RS性能的强大的“副作用”。原先我们需要到内存中去查询一张256*256byte的方阵，一方面操作内存本来就慢，另外一方面对于L1 data cache size为32byte的主流CPU来说，一个64KB的矩阵进进出出会严重污染接下来rs运算所需要缓存的数据。 然后利用CPU提供的指令，以数据为MASK，对表进行重新排序，然后异或左右两个部分的值我们就得到了编码后的结果了。 代码分析代码量很少，除去测试和表，只有小几百行。再抛开上层的业务逻辑，核心部分只有矩阵运算和使用SIMD技术的汇编代码。 由于计算过程非常简单，那么很显然的，耗时主要在内存读写上，而且矩阵运算是需要反复读取数据的，数据总的吞吐远远高过表面上的原始数据读入和冗余数据输出（比如，对于10+4的方案来说，表面上IO负担为14，而实际上要读/写的shard数量为76，这是因为每读一份数据都意味着计算并写入一份数据，接下来又要读取之前的计算结果做异或才能写入），基于以上两点，得出了一个很清晰的优化目标：写缓存友好代码。 有了这样的思路，我很自然的采用了分块的方法来进行矩阵运算 我先前有提过Golang的汇编代码是相对友好的，它抽象了出了一些汇编的细节，我们可以不用过分纠结于寄存器的高低位，堆栈的维护，参数的读取。当然一般的汇编代码陷阱依然是存在的。 对于golang没有的指令，我们可以使用asm2plan9s将yasm语言转为plan9风格的byte code,然后写到golang的汇编文件里。 不过golang汇编也有令人迷惑的地方，它的伪寄存器倒是颇为友好，只是其他指令并不是照搬intel手册的名字。比如MOVDQA在GO里是MOVO，MOVDQU变成了MOVOU，O代表octo-word。 汇编中，很容易犯的一个错误是使用了“脏”寄存器的数据，这主要是寄存器重用错误和高低位处理上的疏忽。Golang的汇编帮我们减少了第二种错误的头脑负担，不过XMM,YMM寄存器的高低位问题还是要我们自己小心的。 不过高低位问题带来的不仅仅是烦恼，我们同样可以利用它写出优雅的汇编代码。比如在ssse3_amd64.s中读取“左右表”到YMM寄存器的代码就处理的就比较精彩，充分利用了X0作为Y0的低位这一性质。 为了提高汇编代码的吞吐性能，常见的处理手段是Non-Temporal Hint或者prefetch。我们的数据基本不存在无时态问题，使用non-temporal hint技术去写入内存反倒会大大降低性能表现，比如使用non-temportal hint去读取冗余块，为导致接下来的write miss,那么新算出来的数据就不一定写到cache里了，会大大拖慢性能表现。prefetch也没啥用，值得注意的是对于较新的处理器，PREFETCHT1只会将数据提到L2,L3的位置，要想利用L1，得使用PREFETCHT0，这一点可能和书上或者一些资料说的不一样，这是因为它的行为是和CPU型号相关的。预取对于我的代码没什么用，这主要是因为大部分时候所需要的数据本来就在缓存里了，预取根本没执行。 我这里还需要提一下的是数据对齐的问题，我的代码中并没有使用这样的技巧，一方面是由于golang不方便自定义数据对齐尺寸，另外golang内置的对齐规则恰好可以满足相关指令的需要。另外有资料显示，较新的Intel处理器现在都不用费太多心思去使用内存对齐的MOV指令了。(比如在Skylake下的VMOVDQA/U的latency都是3个clock cycles） 当汇编代码中同时出现XMM,YMM寄存器时，我们需要多一个心眼。道理是非常简单的，对于SSE指令来说，它是“看不见”YMM寄存器的高位的，在执行过程中，只好将YMM的高位先保存下来以备后续使用。而同样是处理128bit的寄存器，AVX指令则没有这个问题，因为它知道高位的存在，在指令执行中顺手把高位清零了。 在我的汇编代码中（avx2版本），我非常小心的去除了SSE指令的痕迹，想办法使用了AVX指令做了替换，这样我就避免AVX-SSE Transition Penalties 这里顺带分享一下我寻找所需要的指令的经验.遍历手册固然是可以，但对于我这种脑容量有限的人来说不一会就迷失于各种细节之中了。因此保持对指令的“大局观”就格外重要了。我们得首先对CPU会提供什么样的指令有粗略的感官体验，然后抱着自己的目的去翻查。最终哪怕这个世界上并没有你想要的指令，事后也可以通过这个过程摸点门道出来。 这里我以SIMD技术下的指令为例，对于CPU少得可怜的功能来说，SIMD的适用范围更窄，无非就是数据传输，算术运算，比较，转换，逻辑操作，位移，排序，插入等。说得再简单一点就是知道从哪里拿数据，简单操作一下，找个地方放回去这三个步骤。对于一项我们想要的功能，分这三步分别找到合适的指令。当发现可以用时，写个简单的测试程序跑跑看，如果找到了更多的类似指令，分别运行对比一下。用不了很长时间，最合适的那一条就出炉了。 下面我将还原找到“将掩码移动到YMM”这个指令的全过程：
比avx2还要强大的是avx512，它意味着单寄存器的吞吐又翻了一倍。但是由于支持的CPU少得可怜，我也就没有探索的欲望了。毕竟万变不离其宗。 相对于avx2，我们还有sse家族以及avx可以参考。毕竟大家用的处理器并不都是那么新，况且simd技术应用于rs也是从sse开始的。 avx作为第一代avx扩展指令集缺少一些整数相关的指令，单凭这一点我就淘汰了它。那么另外一个版本必然是在sse家族产生了。 由于sse有非常多的版本，第一代在奔腾3时代就出现了，具体去了解它们非常没有必要。我的方法是直接开始使用XMM/YMM寄存器写代码，逐步确认扩展指令集。 关于确认扩展指令集有一点需要明确的是，intel不可能在在升级指令集的同时丢失必要的老指令。这是什么意思呢？ 我举个例子，当我们利用VMOVDQU将内存中的128bit移动到XMM寄存器上时，会发现这是一条AVX指令，根据intel的产品手册的简介我并没有看到我的cpu支持avx，那么这条指令不能用了吗？ 这是不可能的。一方面，我们可以通过工具查看详细的cpu信息发现cpu支持avx，另外一方面avx2仅仅是avx的拓展，intel不可能做出有了左膀就砍掉右臂的傻事。 我写了YMM，XMM寄存器两套版本的汇编代码，在YMM版本中，我使用了avx，avx2，因此其要求cpu必须支持avx2;在XMM版本中，使用了sse2和ssse3两种指令集，因此要求cpu支持ssse3。 Performance如果要一句话总结性能表现的话，这可能是市面上第二快的RS引擎。 目前最快的引擎应该就是Intel的ISA-L了，在和它PK前，需要注意的几点是：
我这里放一份在AWS上跑的测试数据，采用的是10+4的方案（测试平台： AWS t2.micro Intel(R) Xeon(R) CPU E5-2676 v3 @ 2.40GHz, Memory 1GB）： 
两份代码性能在伯仲之间，对于大文件来说intel会更优秀一点。大家的核心思想均来自上面我提到的论文，因此不会有质差别。至于我与Intel跑的比别人快的原因也是一致的，即对CPU Cache命中率的重视。性能有差距的原因则是我们的上层逻辑有非常大的差别以及在汇编优化上显然Intel会更胜一筹，比如我在上层做了更多的抽象，更加的接近矩阵运算的本来面貌，而Intel的策略是把工作传向了底下的汇编。因此Intel不得不根据parity数量分别写相应的汇编代码，然后一层层做encode，直到剩余parity为0退出计算过程。这样细致的优化取得了性能上的胜利。 关于通过对data shard切片优化性能的问题，我在上面并没有展开，下面我们来一起分析一下为什么这样的调整会对性能产生巨大影响。 我们再来回顾一下冗余块的计算过程，计算过程中读/写的数据量非常大，若干倍于我们传入以及得到的数据。奥秘就在这里了，我们要争取减少向内存读写数据，尽量在缓存中命中它。 对于一次计算循环（见汇编部分代码）来说，读取的下一份冗余数据均与上一步的写入的内存地址不相同。这里要感谢伟大的乱序执行技术，对于这样的情景乱序执行会将率先执行下一步的读操作，再加上store buffer技术，更新的冗余数据并没有立即被写入内存，如此反复，冗余数据在cache与CPU之间跑来跑去，最终真正被执行写入内存的数据只有其中的一部份。 当我们的尺寸调整的比较恰当时，所需要的数据有不小的几率在L1 Cache中被命中，这样速度自然就被大大提升了。倘若尺寸太大，使得数据落入L2,L3,甚至塞不进缓存，速度自然就下来了。 比较细心的读者可能发现了，我在描述缓存工作的时候用了大量的“可能”二字。这主要是由于cache淘汰用的是pseudo-LRU算法，LRU对于CPU来说开销太大，而且有人研究过使用纯随机策略代替LRU,miss rate也只有1%左右的区别。所以我也不能确切的说在更新缓存的时候究竟发生了什么。 
上面这张图大致反映了数据流动的情况，问题的核心也被表现的非常突出：即缓存命中率，缓存读取速度以及写优化。 代码代码在这里：reedsolomon 我的英文比较捉急，所以代码的README可能读起来会有点费力，不过结合这篇说明应该不会妨碍理解我的意思。 下一步的工作由于计算速度已经吊打N*SATA盘的IO或者服务器出口带宽，关于编码本身的优化暂且可以告一段落了。 接下来要做的就是尽力减少磁盘修复所占用的宝贵带宽资源了，毕竟修一块盘就要跑N块（数据块块数）盘的数据是非常不经济的，尤其在超大集群下，倘若坏盘数量非常多，使用原始的修复策略对可靠性也是巨大的潜在威胁。 值得庆幸的是，我已经找到了一种非常简单干脆的方式现实这样的效果。待我有得闲时再与大家分享。 |