kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

逆元

https://blog.csdn.net/baidu_35643793/article/details/75268911

1.什么是逆元

当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:

设c是b的逆元,则有b*c≡1(mod m);

则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);

即a/b的模等于a*b的逆元的模;

逆元就是这样应用的;

2.求逆元的方法

(1).费马小定理

在是素数的情况下,对任意整数都有。 如果无法被整除,则有。 可以在为素数的情况下求出一个数的逆元,,即为逆元。

题目中的数据范围1<=x<=109,p=1000000007,p是素数;

所以x肯定就无法被p整除啊,所以最后就得出xp-2为x的逆元啦。

复杂度O(logn);

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int mod = 1000000009;  
long long quickpow(long long a, long long b) {  
	if (b < 0) return 0;  
	long long ret = 1;  
	a %= mod;  
	while(b) {  
		if (b & 1) ret = (ret * a) % mod;  
		b >>= 1;  
		a = (a * a) % mod;  
	}  
	return ret;  
}  
long long inv(long long a) {  
	return quickpow(a, mod - 2);  
}  

(2)扩展欧几里得算法求逆元

可扩展欧几里得求逆元ax≡1(mod n)其中a,n互质;

复杂度:O(logn);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll extend_gcd(ll a, ll b, ll &x, ll &y) {  
	if (b == 0) {  
		x = 1, y = 0;  
		return a;  
	}  
	else {  
		ll r = extend_gcd(b, a % b, y, x);  
		y -= x * (a / b);  
		return r;  
	}  
}  
ll inv(ll a, ll n) {  
	ll x, y;  
	extend_gcd(a, n, x, y);  
	x = (x % n + n) % n;  
	return x;  
}  

(3) 逆元线性筛 ( P为质数 )

求1,2,…,N关于P的逆元(P为质数)

复杂度:O(N)

代码:

1
2
3
4
5
6
const int mod = 1000000009;  
const int maxn = 10005;  
int inv[maxn];  
inv[1] = 1;  
for(int i = 2; i < 10000; i++)  
	inv[i] = inv[mod % i] * (mod - mod / i) % mod;  

伽罗华域(Galois Field)上的四则运算

https://blog.csdn.net/shelldon/article/details/54729687

伽罗华域(Galois Field)上的四则运算

Évariste Galois ,伽罗华(也译作伽瓦罗),法国数学家,群论的创立者。用群论彻底解决了根式求解代数方程的问题,而且由此发展了一整套关于群和域的理论。 本文介绍伽罗华域,以及在伽罗华域上的四则运算方式。伽罗华域上的四则运算实际上是多项式计算,后文中详细介绍。

一、相关数学概念

1、域

一组元素的集合,以及在集合上的四则运算,构成一个域。其中加法和乘法必须满足交换、结合和分配的规律。加法和乘法具有封闭性,即加法和乘法结果仍然是域中的元素。
域中必须有加法单位元和乘法单位元,且每一个元素都有对应的加法逆元和乘法逆元。但不要求域中的 0有乘法逆元。

2、有限域

仅含有限多个元素的域。因为它由伽罗华所发现,因而又称为伽罗华域。

所以当我们说伽罗华域的时候,就是指有限域。 GF(2w)表示含有2w个元素的有限域。

3、单位元

Identity Element,也叫幺元(么元),通常使用e来表示单位元。单位元和其他元素结合时,并不会改变那些元素。 对于二元运算,若ae=a,e称为右单位元;若ea=a,e称为左单位元,若ae=e*a=a,则e称为单位元。

4、逆元

对于二元运算,若ab=e,则a称为b的左逆元素,b称为a的右逆元素。若ab=ba=e,则称a为b的逆元,b为a的逆元。

5、本原多项式

域中不可约多项式是不能够进行因子分解的多项式, 本原多项式 (primitive polynomial)是一种特殊的不可约多项式。当一个域上的本原多项式确定了,这个域上的运算也就确定了。本原多项式一般通过查表可得,同一个域往往有多个本原多项式。

通过将域中的元素化为多项式形式,可以将域上的乘法运算转化为普通的多项式乘法再模本原多项式。

二、多项式运算

由于GF(2w)上的四则运算是基于多项式运算的,这里先介绍多项式运算。 多项式一般长这个样子:f(x) = x6 + x^ 4 + x2 + x + 1。

1、多项式加减法

将两个多项式中相同阶数的项系数相加或相减。 例如 (x2 + x ) + (x + 1) = x2 + 2x +1

2、多项式乘法

将其中一个多项式的各项分别与另一个多项式的各项相乘,然后把相同指数的项的系数相加。 例如 (x2 + x) * (x + 1) = x2 * (x + 1) + x * (x + 1) = x3 + x2 + x2 + x

3、多项式除法

使用长除法。例如计算x3-12x2-42,除以x-3。使用长除法计算,商x2-9x-27,余数-123。

4、GF(2w)上的多项式运算

对于GF(2w)上的多项式计算,多项式系数只能取 0或1。(如果是GF(3w),那么系数可以取 0、 1、 2) GF(2w)的多项式加法中,合并阶数相同的同类项时,由于0+0=0,1+1=0,0+1=1+0=1,因此系数不是进行加法操作,而是进行异或操作。

GF(2w)的多项式减法等于加法,例如x ^4 – x4就等于x4 + x4

三、伽罗华域

1、有限域GF(p):

有限域GF(p),其中p为素数。GF(p)里面的加法和乘法与一般的加法和乘法差不多,区别是结果需要mod p,以保证结果都是域中的元素。GF(p)的加法和乘法单位元分别是 0和1。 GF(p)加法是(a+b) mod p,乘法是(a*b)mod p。

对于域中的乘法,当p为素数时,才能保证集合中的所有的元素都有乘法逆元(0除外)。即对于域中的任一个元素a,总能在域中找到另外一个元素b,使得a*b mod p 等于1。

说明:假如p等于10,其乘法单位元为1。对于元素2,找不到一个数a,使得2*a mod 10 等于1,即2没有乘法逆元。这时,在域上就不能进行除2运算。

2、有限域GF(2w):

GF(p)中p必须是一个素数,才能保证集合中的所有元素都有加法和乘法逆元(0除外)。但实际应用中,很多场合需要 0到255这256个数字能组成一个域。但256不是素数,小于256的最大素数为251,如果直接把大于等于251的数截断为250,则会丢失一部分数据。

因此引入了GF(pw),其中p为素数,通常取p=2。计算机领域中经常使用的是GF(28),8刚好是一个字节的比特数。为了保证单位元性质,GF(2w)上的加法运算和乘法运算,不再使用一般的加法和乘法,而是使用多项式运算。

四、本原多项式

伽罗华域的元素可以通过该域上的本原多项式生成。通过本原多项式得到的域,其加法单位元都是 0,乘法单位元是1。

以GF(23)为例,指数小于3的多项式共8个: 0, 1, x, x+1, x2, x2+1, x2 + x, x2+x+1。其系数刚好就是000,001, 010, 011, 100, 101, 110, 111,是0 到7这8个数的二进制形式。

GF(23)上有不只一个本原多项式,选一个本原多项式x3+x+1,这8个多项式进行四则运算后 mod (x3+x+1)的结果都是8个之中的某一个。因此这8个多项式构成一个有限域。

对于GF(23),取素多项式为x3 + x+1,那么多项式x2+x的乘法逆元就是x+1。系数对应的二进制分别为110和011。此时,我们就认为对应的十进制数6和3互为逆元。

部分 GF(2w)域经常使用的本原多项式如下:

通过本原多项式生成元素

设P(x)是GF(2w)上的某一个本原多项式,GF(2w)的元素产生步骤是:
1、给定一个初始集合,包含0,1和元素x,即 {0,1,x};
2、将这个集合中的最后一个元素,即x,乘以x,如果结果的度大于等于w,则将结果mod P(x)后加入集合;
3、直到集合有2w个元素,此时最后一个元素乘以x再mod P(x)的值等于1。

例如,GF(24)含有16个元素,本原多项式为P(x)=x4+x+1,除了 0、1外,另外14个符号均由本原多项式生成。 注意到x14=x3+1,此时计算x15=x14x=(x3+1)x=x4+x=1,生成结束。

生成元素 多项式表示 二进制表示 数值表示 推导过程
0 0 0000 0
x^0 x^0 0001 1
x^1 x^1 0010 2
x^2 x^2 0100 4
x^3 x^3 1000 8
x^4 x+1 0011 3 x^3*x = x^4 mod P(x) = x+1
x^5 x^2+x 0110 6 x^4*x = (x+1)*x = x^2+x
x^6 x^3+x^2 1100 12
x^7 x^3+x+1 1011 11 x^6*x = (x^3+x^2)*x = x^4 +x^3 mod P(x) = x^3+x+1
x^8 x^2+1 0101 5
x^9 x^3+x 1010 10
x^10 x^2+x+1 0111 7 x^9*x=(x^3+x)*x = x^4+x^2 mod P(x) = x^2+x+1
x^11 x^3+x^2+x 1110 14
x^12 x^3+x^2+x+1 1111 15 x^11*x=(x^3+x^2+x)*x = x^4+x^3+x^2 mod P(x) = x^3+x^2+x+1
x^13 x^3+x^2+1 1101 13 x^12*x=(x^3+x^2+1 )*x = x^4+x^3+x mod P(x)= x^3+1
x^14 x^3+1 1001 9 x^13*x=(x^3+x^2+1)*x = x^4+x^3+x mod P(x) = x^3+1
x^15 1 0001 1 x^14*x = (x^3+1)*x = x^4+x mod P(x) = 1

五、伽罗华域上的运算

加法和减法:

加法和减法就是多项式计算中说的异或运算。

乘法和除法:

伽罗华域上的多项式乘法,其结果需要mod P(x),可以通过以下方式简化计算。

首先,考虑x8,x8 mod P(x) = P(x) – x8 = x4 + x3 +x2 +1 。

对于一般形式的多项式f(x)=a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0,乘以x得到 xf(x) = (a7x8 + a6x7 + a5x6 + a4x5 + a3x4 + a2x3 + a1x1 + a0x) mod P(x)

这时有两种情况:

1)a7 == 0,此时结果是一个小于指数小于8的多项式,不需要取模计算。

2)a7 == 1,则将x8替换为x4 + x3 + x2 +1,而不用进行除法取模计算,结果为:

xf(x) = (x4 + x3 + x2 +1) + a6x7 + a5x6 + a4x5 + a3x4 + a2x3 + a1x1 + a0x

虽然可以通过替换减少除法计算,但还是过于复杂。尤其是在需要大量运算的场合,比如图像处理。于是牛人提出通过查表来减少计算。

六、查表的原理

首先介绍一个概念,生成元。

生成元是域上的一类特殊元素,生成元的幂可以遍历域上的所有元素。假设g是域GF(2w)上生成元,那么集合 {g0 ,g1 , ……,g(2w-1) } 包含了域GF(2w)上所有非零元素。在域GF(2w)中2总是生成元。

将生成元应用到多项式中, GF(2w)中的所有多项式都是可以通过多项式生成元g通过幂求得。即域中的任意元素a,都可以表示为a = gk

GF(2w)是一个有限域,就是元素个数是有限的,但指数k是可以无穷的。所以必然存在循环。这个循环的周期是2w-1(g不能生成多项式 0)。所以当k大于等于2w-1时,gk =gk%(2w-1)

对于gk = a,有正过程和逆过程。知道指数k求a是正过程,知道值a求指数k是逆过程。

对于乘法,假设a=gn,b=gm。那么ab = gn gm = gn+m。查表的方法就是根据a和b,分别查表得到n和m,然后查表gn+m即可。

因此需要构造正表和反表,在GF(2w)域上分别记为gflog和gfilog。gflog是将二进制形式映射为多项式形式,gfilog是将多项式形式映射为二进制形式。

注意:多项式0 ,是无法用生成元生成的。g0等于多项式1,而不是 0。

根据上文的GF(24)的元素表示,生成gflog表和gfilog表如下:

查表进行乘法和除法运算的例子

在GF(24)域上的乘法和除法,已知2w-1 = 24 -1 = 15:

乘法:

7 * 9 = gfilog[gflog[7] + gflog[9]] = gfilog[10 + 14] = gfilog[24 mod 15] = gfilog[9] = 10

除法:

13 / 11 = gfilog[gflog[13] - gflog[11]] = gfilog[13 - 7] = gfilog[6] = 12

五、生成GF(2w)gflog表和gfilog表的python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# coding=UTF-8  

# key : value => w : primitive_polynomial  
primitive_polynomial_dict = {4: 0b10011,                            # x**4  + x     + 1  
			    8: (1 << 8) + 0b11101,                 # x**8  + x**4  + x**3 + x**2 +1  
			    16: (1 << 16) + (1 << 12) + 0b1011,    # x**16 + x**12 + x**3 + x    + 1  
			    32: (1 << 32) + (1 << 22) + 0b111,     # x**32 + x**22 + x**2 + x    + 1  
			    64: (1 << 64) + 0b11011                # x**64 + x**4  + x**3 + x    + 1  
			    }  


def make_gf_dict(w):  
	gf_element_total_number = 1 << w  
	primitive_polynomial = primitive_polynomial_dict[w]  

	gfilog = [1]  # g(0) = 1  
	for i in xrange(1, gf_element_total_number - 1):  
		temp = gfilog[i - 1] << 1  # g(i) = g(i-1) * g  
		if temp & gf_element_total_number:  # if overflow, then mod primitive polynomial  
			temp ^= primitive_polynomial  # mod primitive_polynomial in GF(2**w) == XOR  
		gfilog.append(temp)  

	assert (gfilog[gf_element_total_number - 2] << 1) ^ primitive_polynomial  
	gfilog.append(None)  

	gflog = [None] * gf_element_total_number  
	for i in xrange(0, gf_element_total_number - 1):  
		gflog[gfilog[i]] = i  

	print "{:>8}\t{:>8}\t{:>8}".format("i", "gfilog[i]", "gflog[i]")  
	for i in xrange(0, gf_element_total_number):  
		print "{:>8}\t{:>8}\t{:>8}".format(i, gfilog[i], gflog[i])  


if __name__ == "__main__":  
	make_gf_dict(4)  

参考

http://blog.csdn.net/luotuo44/article/details/41645597 http://blog.csdn.net/mengboy/article/details/1514445 http://www.tuicool.com/articles/RZjAB3 http://ouyangmy.is-programmer.com/posts/41256.html

基于柯西矩阵的Erasure Code技术详解

http://blog.51cto.com/alanwu/1410132

http://blog.51cto.com/alanwu/1406312 http://www.doc88.com/p-4085136791897.html

一、概述

Erasure Code可以应用于分布式存储系统中,替代多份数据拷贝的数据冗余方式,从而可以提高存储空间利用率。此外,Erasure code还可以应用于传统RAID系统中,增加数据冗余度,支持多块盘同时发生故障,从而可以提高数据可靠性。

采用范德蒙矩阵可以构建Erasure code(关于范德蒙矩阵的编解码方法,可以参考文章《基于范德蒙矩阵的Erasure code技术详解》),其生成矩阵表示如下:

采用范德蒙矩阵作为编码矩阵的问题在于算法复杂度太高,其解码算法复杂度为O(n3)。采用目前的处理器技术,还是会影响IO的性能,增加IO延迟。因此,找到一种更加合理的编码矩阵,降低算法复杂度是Erasure code得以广泛应用的一个前提条件。

二、基于柯西矩阵的编解码过程

基于柯西矩阵的李德-所罗门(RS)码是在范德蒙矩阵的RS码基础上作了两点重要改进:

1,用柯西矩阵来代替范德蒙矩阵。由于范德蒙矩阵求逆运算的复杂度为O(n3),而柯西矩阵求逆运算的复杂度仅为O(n2)。因此,采用柯西矩阵可以降低解码的运算复杂度。

2,采用有限域二进制矩阵的方式来提高运算效率,直接将乘法转换成XOR逻辑运算,大大降低了运算复杂度。

大家知道,柯西矩阵可以描述如下:

X(i)和Y(i)都是迦罗华域GF(2w)中的元素。柯西矩阵有两个特点:第一,任意一个子方阵都是奇异矩阵,存在逆矩阵;第二,柯西矩阵在迦罗华域上的求逆运算,可以在O(n2)的运算复杂度内完成。

采用柯西矩阵进行Erasure code编码过程描述如下:

其运算过程和范德蒙矩阵编码过程是一样的,只不过采用柯西矩阵替换了范德蒙矩阵。从运算过程来看,编码过程是迦罗华域的系列乘法、加法运算。

柯西解码方程描述如下:

当任何一个数据元d(i)遭到损坏时,需要通过解码过程进行数据恢复。数据解码过程可以分成如下几大步骤:

1,选取剩余有效的数据块,构成一个解码列向量。例如,d1、d3数据块损坏了,那么可以选取剩余数据d0、d2、c0、c2作为解码列向量。

2,摘取生成矩阵(柯西矩阵)中解码列向量所对应的行,构成方阵A,该矩阵的逆矩阵就是解码生成矩阵inv(A)。

3,解码生成矩阵inv(A)和解码列向量的乘积就可以得到丢失的数据d1和d3。

从整个过程来看,矩阵求逆过程是最大的运算开销。解码过程和范德蒙矩阵编码是一样的,但是柯西矩阵的求逆运算复杂度要低于范德蒙矩阵,因此,具有更好的性能。

三、柯西编解码过程优化

从编解码过程来看,柯西编解码最大的运算量是乘法和加法运算。在范德蒙编码的时候,我们可以采用对数/反对数表的方法将乘法运算转换成了加法运算,并且在迦罗华域中,加法运算转换成了XOR运算。

柯西编解码为了降低乘法复杂度,采用了有限域上的元素都可以使用二进制矩阵表示的原理,将乘法运算转换成了迦罗华域“与运算”和“XOR逻辑运算”,提高了编解码效率。

从数学的角度来看,在迦罗华有限域中,任何一个GF(2w)域上的元素都可以映射到GF(2)二进制域,并且采用一个二进制矩阵的方式表示GF(2w)中的元素。例如,GF(23)域中的元素可以表示成GF(2)域中的二进制矩阵:

图中,黑色方块表示逻辑1,白色方块表示逻辑0。通过这种转换,GF(2w)域中的阵列就可以转换成GF(2)域中的二进制阵列。生成矩阵的阵列转换表示如下:

在GF(2w)域中的生成矩阵为K(K+m),转换到GF(2)域中,变成了(wk) * (w*(k+m))二进制矩阵。采用域转换的目的是简化GF(2w)域中的乘法运算。在GF(2)域中,乘法运算变成了逻辑与运算,加法运算变成了XOR运算,可以大大降低运算复杂度。和范德蒙编解码中提到的对数/反对数方法相比,这种方法不需要构建对数/反对数表,可以支持w为很大的GF域空间。采用这种有限域转换的方法之后,柯西编码运算可以表示如下:

四、总结

可以说柯西编码是在范德蒙编码基础之上的一种优化。其主要有两点:第一降低了矩阵求逆的运算复杂度;第二通过有限域转换,将GF(2w)域中的元素转换成二进制矩阵,简化了乘法运算。所以,柯西编解码要优于范德蒙矩阵的方法,柯西编码的运算复杂度为O(n(n- m)),解码复杂度为O(n2)。

高性能纠删码编码

https://www.jianshu.com/p/024f96a0d56a

ISA-L 是什么东西?

intel®-storage-acceleration-library Intel存储加速库,包括两个大类:加密和非加密的。非加密的 crc,izip,erase-code,加密的包括sha512,sha256,md5,sha1等。

核心技术就是使用intel sse/avx/avx2/avx256的扩展指令,并行运算多个流的方法。单线程比openssl要快2~8倍。

现在ISA-L已经开源:

https://github.com/01org/isa-l

https://github.com/01org/isa-l_crypto


http://www.zhixing123.cn/computer/57905.html

随着数据的存储呈现出集中化(以分布式存储系统为基础的云存储系统)和移动化(互联网移动终端)的趋势,数据可靠性愈发引起大家的重视。集群所承载的数据量大大上升,但存储介质本身的可靠性进步却很小,这要求我们必须以更加经济有效的方式来保障数据安全。

副本与纠删码都是通过增加冗余数据的方式来保证数据在发生部分丢失时,原始数据不发生丢失。但相较于副本,纠删码能以低得多的存储空间代价获得相似的可靠性。比如3副本下,存储开销为3,因为同样的数据被存储了三份,而在10+3(将原始数据分为10份,计算3份冗余)的纠删码策略下,存储开销为为1.3。采用纠删码能够极大地减少存储系统的存储开销,减少硬件、运维和管理成本,正是这样巨大的收益驱使各大公司纷纷将纠删码应用于自己的存储系统,比如Google、Facebook、Azure、EMC等等国际巨头,在国内以淘宝、华为、七牛云等为代表的公司也在自己的存储系统上应用了纠删码。

最典型的纠删码算法是里德-所罗门码(Reed-Solomon码,简称RS码)。RS码最早应用于通信领域,经过数十年的发展,其在存储系统中得到广泛应用,比如光盘中使用RS码进行容错,防止光盘上的划痕导致数据不可读;生活中经常使用的二维码就利用了RS码来提高识别的成功率。近年RS码在分布式存储系统中的应用被逐渐推广,一方面是分布式存储系统存储的存储容量和规模增大的需求;另一方面是由于纠删码编码速度在近年得到迅猛提升。随着对高性能纠删码引擎在实际系统中应用需要,也催生了对纠删码在具体系统中实现的各种优化手段。并为相关的决策者带来了困扰——究竟什么样的编码引擎才是高效的呢?

我们将以这个问题展开对纠删码技术的剖析,帮助企业更全面,深入的了解纠删码在存储系统中的应用并更好地做出技术选型。本系列文章将从纠删码的基本原理开始,随后引出如何判断编码引擎优劣这个问题,接下来将深度分析代码实现,帮助开发者顺利完成定制开发。

本文作为系列首篇,我们将一起探讨纠删码的编码原理与如何选择编码引擎这两个问题。

一、纠删码编码原理

在展开分析之前,我们先来看一看RS码是如何工作的。

下图展示了3+2(3份数据,2份冗余)下对2字节长度的数据进行编码与数据修复过程:

为了计算冗余数据,首先我们需要选举出一个合适的编码矩阵。编码矩阵的上部为一个单位矩阵,这样保证了在编码后原始数据依然可以直接读取。通过计算编码矩阵和原始数据的乘积,可以到最终的结果。

下面介绍解码过程,当1,2两块数据丢失,即:

当数据块发生丢失,在编码矩阵中去掉相应行,等式仍然保持成立。这为我们接下来恢复原始数据提供了依据。

原始数据的修复过程如下:

为了恢复数据,首先我们求剩余编码数据的逆矩阵,等式两边乘上这个逆矩阵仍然保持相等。与此同时,互逆矩阵的乘积为单位矩阵,因此可以被消掉。那么所求得的逆矩阵与剩余块的数据的乘积就是原始数据了。

数据编码以字节为单位,如果将被编码数据看做一个「数组」,「数组」中每个元素是一个字节,数据按照字节顺序被编码。编码过程是计算编码矩阵中元素和「数组」的乘积过程。为保证乘积的运算结果仍旧在一个字节大小以内(即0-255),必须应用到有限域[1]。有限域上的算术运算不同于通常实数的运算规则。我们通常事先准备好乘法表,并在算术运算时对每一次乘法进行查表得到计算结果。早期的编码引擎之所以性能不佳,是因为逐字节查表的性能是非常低的。倘若能一次性对多字节进行查表以及相应的吞吐和运算,引擎的工作效率必将大幅度提升。

许多CPU厂商提供了包含更多位数的寄存器(大于64位),这类寄存器和相应支持的运算使得用户程序可以同时对大于机器位数的数据进行运算,支持这类寄存器和运算的指令称之为SIMD(SingleInstructionMultipleData)指令集,比如Intel支持的SSE指令集最大支持128bits的数据运算,AVX2指令集最大支持512bits的数据运算。它们为我们对一个「数组」数据分别执行相同的操作,提高了数据运算的并行性。目前,市面上所有高性能的纠删码引擎均采用了该项技术以提高编解码性能。

二、编码引擎评判标准

我们将从以下几个关键指标来对编码引擎进行分析:

1、高编/解码速度;

2、参数可配置;

3、代码简洁、稳定;

4、降低修复开销等。

2.1 高编/解码速度

无须多言,编/解码性能是最基本也是最重要的指标。对于一款性能优异的引擎来说,应该同时满足以下几个指标:

根据CPU的特性自动选择最优的指令集进行加速。上文提到,依赖于SIMD技术RS码编码性能有了大幅度的提高。其中,我们可以利用多种指令集扩展以供加速,引擎应该能够自主发现最优解

不亚于目前最出色的几款引擎的性能表现(详见第三章著名引擎对比)

通过SIMD加速,性能会有大幅度攀升。我们还可以将逐字节查表(下称基本方法)的编码速度与利用SIMD技术加速的编码速度做对比,两者应该有数倍的差距

编/解码速度稳定,对于不同尺寸的数据块会有相近的性能表现。由于系统缓存的影响,当被编码数据的大小和缓存大小相当时,编码应该具有最快的速度。当编码数据的大小大于缓存大小时,内存带宽成为编码速度的瓶颈,文件大小和编码时间呈现近似线性关系。这样,数据编码时间是可预期的,用户的服务质量也是可保障的。在实际中,我们对于大文件进行定长分块,依次编码,分块大小和缓存大小保持一定关系。

下图展示了在10+4策略下,不同大小的数据块的编码速度变化趋势[2]:

注:

测试平台:MacBookPro(Retina,13-inch,Mid2014),2.6GHzi5-4278U(3MBL3CacheSize),8GB1600MHzDDR3

编/解码速度计算公式:在k+m策略下,每一个数据块的尺寸计作s,编/解码m个数据块的耗时计作t,则速度=(k*s)/t

测试方法:在内存中生成随机数据,运行若干次编/解码,取平均值

分别执行了avx2指令集,ssse3指令集,基本方法(base)这三种编码方案

被编码文件尺寸指,每一个数据块的尺寸与总的数据块个数的乘积,即原始数据的总大小

作为对比,利用go语言自带的copy函数(copy),对k个数据块进行内存拷贝。copy同样使用了SIMD技术进行加速

另外,解码速度应该大于或等于编码速度(视丢失的数据块数量而定),下图为10+4策略下修复不同数量的原始数据的速度对比[2]:

注:

测试平台与上文的编码测试相同

lostdata=丢失数据块数目(个)

原始数据块每块大小为128KB,总大小为1280KB

2.2 参数可配置

一款合理的纠删码引擎必须能做到编码策略在理论范围内可随意切换,这指的是如果要将编码策略进行变化时,仅需从接口传入不同参数而不需要改动引擎本身。这大大降低了后续的开发和维护所需要的精力。一个可配置参数的编码引擎可以根据数据的冷热程度和数据重要程度选择不同的编码系数,比如可靠性要求高的数据可以选择更多冗余。

2.3 代码简洁、稳定

为了利用SIMD加速我们不得不引入汇编代码或者封装后的CPU指令,因此代码形式并不常见。为了增强可读性可将部分逻辑抽离到高级语言,然而会损失部分性能,这其中的利弊需要根据团队的研发实力进行权衡。

接下来的可维护性也非常重要。首先是接口稳定,不会随着新技术的引入而导致代码大规模重构;另外代码必须经过有合理的测试模块以便在后续的更新中校验新算法。

比如早先的SIMD加速是基于SSE指令集扩展来做的,随后Intel又推出AVX指令集进一步提高了性能,引擎应该能即时跟上硬件进步的步伐。再比方说,再生码[5](可以理解为能减少修复开销的纠删码)是将来发展的趋势,但我们不能因为算法的升级而随意改变引擎的接口。

2.4 降低修复开销

纠删码的一大劣势便是修复代价数倍于副本方案。k+m策略的RS码在修复任何一个数据块时,都需要k份的其他数据从磁盘上读取和在网络上传输。比如10+4的方案下,丢失一个数据块将必须读取10个块来修复,整个修复过程占用了大量磁盘I/O和网络流量,并使得系统暴露在一种降级的不稳定状态。因此,实际系统中应该尽量避免使用过大的k值。

再生码便是为了缓解数据修复开销而被提出的,它能够极大减少节点失效时所需要的吞吐的数据量。然而其复杂度大,一方面降低了编码速度,另外一方面牺牲了传统RS码的一些优秀性质,在工程实现上的难度也大于传统纠删码。

三、著名引擎对比

目前被应用最广泛并采用了SIMD加速的引擎有如下几款:

1.Intel出品的ISA-L[4]

2.J.S.Plank教授领导的Jerasure[5]

3.klauspost的个人项目(inGolang)[6]

这三款引擎的执行效率都非常高,在实现上略有出入,以下是具体分析:

3.1 ISA-L

纠删码作为ISA-L库所提供的功能之一,其性能应该是目前业界最佳。需要注意的是Intel采用的性能测试方法与学术界常用的方式略有出路,其将数据块与冗余块的尺寸之和除以耗时作为速度,而一般的方法是不包含冗余块的。另外,ISA-L未对vandermonde矩阵做特殊处理,而是直接拼接单位矩阵作为其编码矩阵,因此在某些参数下会出现编码矩阵线性相关的问题。好在ISA-L提供了cauchy矩阵作为第二方案。

ISA-L之所以速度快,一方面是由于Intel谙熟汇编优化之道,其次是因为它将整体矩阵运算搬迁到汇编中进行。但这导致了汇编代码的急剧膨胀,令人望而生畏。

另外ISA-L支持的指令集扩展丰富,下至SSSE3,上到AVX512,平台适应性最强。

3.2 Jerasure2.0

不同于ISA-L直接使用汇编代码,Jerasure2.0使用C语言封装后的指令,这样代码更加的友好。另外Jerasure2.0不仅仅支持GF(28)有限域的计算,其还可以进行GF(24)-GF(2128)之间的有限域。并且除了RS码,还提供了CauchyReed-Solomoncode(CRS码)等其他编码方法的支持。它在工业应用之外,其学术价值也非常高。目前其是使用最为广泛的编码库之一。目前Jerasure2.0并不支持AVX加速,尽管如此,在仅使用SSE的情况下,Jerasure2.0依然提供了非常高的性能表现。不过其主要作者之一JamesS.Plank教授转了研究方向,另外一位作者Greenan博士早已加入工业界。因此后续的维护将是个比较大的问题。

3.3 klauspost的ReedSolomon

klauspost利用Golang的汇编支持,友好地使用了SIMD技术,此款引擎的SIMD加速部分是目前我看到的实现中最为简洁的,矩阵运算的部分逻辑被移到了外层高级语言中,加上Golang自带的汇编支持,使得汇编代码阅读起来更佳的友好。不过Go并没有集成所有指令,部分指令不得不利用YASM等汇编编译器将指令编译成字节序列写入汇编文件中。一方面导致了指令的完全不可读,另外一方面这部分代码的语法风格是Intel而非Golang汇编的AT&T风格,平添了迷惑。这款引擎比较明显的缺陷有两点:1.对于较大的数据块,编码速度会有巨大的下滑;2.修复速度明显慢于编码速度。

3.4 编码速度对比

我在这里选取了IntelISA-L(图中intel),klauspost的ReedSolomon(图中k),以及自研的一款引擎2这三款引擎进行编码效率的对比,这三款引擎均支持avx2加速。测试结果如下:

注:

编码速度计算公式,测试方法与上一节相同。其中isa-l默认的速度计算方式与公式有冲突,需要修改为一致

测试平台:AWSt2.microIntel®Xeon®CPUE5-2676v3@2.40GHz,Memory1GB

编码方案:10+4

klauspost的引擎默认开了并发,测试中需要将并发数设置为1

四、自己实现一款引擎

可能是由于对开源库后续维护问题的担忧,也有可能是现有方案并不能满足企业对某些特定需求和偏好,很多公司选择了自研引擎。那么如何写出高效的代码呢?在上面的简单介绍中,受限于篇幅我跳过了很多细节。比如SIMD技术是如何为纠删码服务的,以及如何利用CPUCache做优化等诸多重要问题。我们会在后续的文章中逐步展开其实现,欢迎大家继续关注。

我们简单了解了Reed-SolomonCodes(RS码)的编/解码过程,以及编码引擎的评判标准。但并没有就具体实现进行展开,本篇作为《纠删码技术详解》的下篇,我们将主要探讨工程实现的问题。

这里先简单提炼一下实现高性能纠删码引擎的要点:首先,根据编码理论将矩阵以及有限域的运算工程化,接下来主要通过SIMD指令集以及缓存优化工作来进行加速运算。也就是说,我们可以将RS的工程实现划分成两个基本步骤:

将数学理论工程化

进一步的工程优化

这需要相关研发工程师对以下内容有所掌握:

有限域的基本概念,包括有限域的生成与运算

矩阵的性质以及乘法规则

计算机体系结构中关于CPU指令以及缓存的理论

接下来,我们将根据这两个步骤并结合相关基础知识展开实现过程的阐述。

一理论工程化

以RS码为例,纠删码实现于具体的存储系统可以分为几个部分:编码、解码和修复过程中的计算都是在有限域上进行的;编码过程即是计算生成矩阵(范德蒙德或柯西矩阵)和所有数据的乘积;解码则是计算解码矩阵(生成矩阵中某些行向量组成的方阵的逆矩阵)和重建数据的乘积。

1.1有限域运算

有限域是纠删码中运算的基础域,所有的编解码和重建运算都是基于某个有限域的。不止是纠删码,一般的编码方法都在有限域上进行,比如常见的AES加密中也有有限域运算。使用有限域的一个重要原因是计算机并不能精确执行无限域的运算,比如有理数域和虚数域。

此外,在有限域上运算另一个重要的好处是运算后的结果大小在一定范围内,这是因为有限域的封闭性决定的,这也为程序设计提供了便利。比如在RS中,我们通常使用GF(28),即0~255这一有限域,这是因为其长度刚好为1字节,便于我们对数据进行存储和计算。

在确定了有限域的大小之后,通过有限域上的生成多项式可以找到该域上的生成元[1],进而通过生成元的幂次遍历有限域上的元素,利用这一性质我们可以生成相应的指数表。通过指数表我们可以求出对数表,再利用指数表与对数表最终生成乘法表。关于本原多项式的生成以及相关运算表的计算可以参考我在开源库中的数学工具。[2]

有了乘法表,我们就可以在运算过程中直接查表获得结果,而不用进行复杂的多项式运算了。同时也不难发现,查表优化将会成为接下来工作的重点与难点。

1.2选择生成矩阵

生成矩阵(GM,generatormatrix)定义了如何将原始数据块编码为冗余数据块,RS码的生成矩阵是一个n行k列矩阵,将k块原始数据块编码为n块冗余数据块。如果对应的编码是系统码(比如RAID),编码后包含了原始数据,则生成矩阵中包含一个k×k大小的单位矩阵和(n−k)×k的冗余矩阵,单位矩阵对应的是原始数据块,冗余矩阵对应的是冗余数据块。非系统码没有单位矩阵,整个生成矩阵都是冗余矩阵,因此编码后只有冗余数据块。通常我们会使用系统码以提高数据提取时的效率,那么接下来我们需要找到合适的冗余矩阵。

在解码过程中我们要对矩阵求逆,因此所采用的矩阵必须满足子矩阵可逆的性质。目前业界应用最多的两种矩阵是Vandermondematrix(范德蒙矩阵)和Cauchymatrix(柯西矩阵)。其中范德蒙矩阵历史最为悠久,但需要注意的是我们并不能直接使用范德蒙矩阵作为生成矩阵,而需要通过高斯消元后才能使用,这是因为在编码参数(k+m)比较大时会存在矩阵不可逆的风险。

柯西矩阵运算简单,只不过需要计算乘法逆元,我们可以提前计算好乘法逆元表以供生成编码矩阵时使用。创建以柯西矩阵为生成矩阵的编码矩阵的伪代码如下图所示:

1.3矩阵求逆运算

有限域上的求逆方法和我们学习的线性代数中求逆方法相同,常见的是高斯消元法,算法复杂度是O(n3)。过程如下:

在待求逆的矩阵右边拼接一个单位矩阵

进行高斯消元运算

取得到的矩阵左边非单位矩阵的部分作为求逆的结果,如果不可逆则报错

我们在实际的测试环境中发现,矩阵求逆的开销还是比较大的(大约6000ns/op)。考虑到在实际系统中,单盘数据重建往往需要几个小时或者更长(磁盘I/O占据绝大部分时间),求逆计算时间可以忽略不计。

二进一步的工程优化

2.1利用SIMD加速有限域运算

从上一篇文章可知,有限域上的乘法是通过查表得到的,每个字节和生成矩阵中元素的乘法结果通过查表得到,图1给出了按字节对原始数据进行编码的过程(生成多项式为x8+x4+x3+x2+1)。对于任意1字节来说,在GF(28)内有256种可能的值,所以没有元素对应的乘法表大小为256字节。每次查表可以进行一个字节数据的乘法运算,效率很低。

图 1, 按字节对原始数据进行编码

目前主流的支持SIMD相关指令的寄存器有128bit(XMM指令)、256bit(YMM指令)这两种容量,这意味着对于64位的机器来说,分别提供了2到4倍的处理能力,我们可以考虑采用SIMD指令并行地为更多数据进行乘法运算。

但每个元素的乘法表的大小为256Byte,这大大超出了寄存器容纳能力。为了达到利用并行查表的目的,我们采用分治的思想将两个字节的乘法运算进行拆分。

字节y与字节a的乘法运算过程可表示为,其中y(a)表示从y的乘法表中查询与x相乘结果的操作:

y(a)=y*a 我们将字节a拆分成高4位(al)与低4位(ar)两个部分,即(其中⊕为异或运算):

a=(al<<4)⊕ar

这样字节a就表示为0-15与(0-15<<4)异或运算的结果了。

于是原先的y与a的乘法运算可表示为:

y(a)=y(al<<4)⊕y(ar)

由于ar与al的范围均为0-15(0-1111),字节y与它们相乘的结果也就只有16个可能的值了。这样原先256字节的字节y的乘法表就可以被2张16字节的乘法表替换了。

下面以根据本原多项式x8+x4+x3+x2+1生成的GF(28)为例,分别通过查询普通乘法表与使用拆分乘法表来演示16*100的计算过程。

16的完整乘法表为:

计算16*100可以直接查表得到:

table[100] = 14

16 的低 4 位乘法表,也就是 16 与 0-15 的乘法结果:

lowtable=[0163248648096112128144160176192208224240]

16的高4位乘法表,为16与0-15<<4的乘法结果:

hightable=[02958391161057883232245210207156129166187]

将100(01100100)拆分,则:

100 = 0110 << 4 ⊕ 0100

在低位表中查询0100(4),得:

lowtable[4]=64 在高位表中查询 0110(6),得:

hightable[6]=78

将两个查询结果异或:

result=6478=10000001001110=1110=14

从上面的对比中,我们不难发现采用SIMD的新算法提高查表速度主要表现在两个方面:

减少了乘法表大小; 提高查表并行度(从1个字节到16甚至32个字节) 采用SIMD指令在大大降低了乘法表的规模的同时多了一次查表操作以及异或运算。由于新的乘法表每一部分只有16字节,我们可以顺利的将其放置于XMM寄存器中,从而利用SIMD指令集提供的指令来进行数据向量运算,将原先的逐字节查表改进为并行的对16字节进行查表,同时异或操作也是16字节并行的。除此之外,由于乘法表的总体规模的下降,在编码过程中的缓存污染也被大大减轻了,关于缓存的问题我们会在接下来的小节中进行更细致的分析。 以上的计算过程以单个字节作为例子,下面我们一同来分析利用SIMD技术对多个字节进行运算的过程。基本步骤如下: 拆分保存原始数据的XMM寄存器中的数据向量,分别存储于不同的XMM寄存器中 根据拆分后的数据向量对乘法表进行重排,即得到查表结果。我们可以将乘法表理解为按顺序排放的数组,数组长度为16,查表的过程可以理解为将拆分后的数据(数据范围为0-15)作为索引对乘法表数组进行重新排序。这样我们就可以通过排序指令完成查表操作了 将重排后的结果进行异或,得到最终的运算结果 以下是伪代码:

需要注意的是,要使用SIMD加速有限域运算,对CPU的最低要求是支持SSSE3扩展指令集。另外为了充分提高效率,我们应该事先对数据进行内存对齐操作,在SSSE3下我们需要将数据对齐到16Bytes,否则我们只能使用非对齐指令进行数据的读取和写入。在这一点上比较特殊的是Go语言,一方面Go支持直接调用汇编函数这为使用SIMD指令集提供了语言上的支持;但另外一方面Golang又隐藏了内存申请的细节,这使得指定内存对齐操作不可控,虽然我们也可以通过cgo或者汇编来实现,但这增加额外的负担。所幸,对于CPU来说一个Cacheline的大小为64byte,这在一定程度上可以帮助我们减少非对齐读写带来的惩罚。另外,根据Golang的内存对齐算法,对于较大的数据块,Golang是会自动对齐到32byte的,因此对齐或非对齐指令的执行效果是一致的。

2.2 写缓存友好代码

缓存优化通过两方面进行,其一是减少缓存污染;其二是提高缓存命中率。在尝试做到这两点之前,我们先来分析缓存的基本工作原理。

CPU缓存的默认工作模式是Write-Back,即每一次读写内存数据都需要先写入缓存。上文提到的Cacheline即为缓存工作的基本单位,其大小为固定的64byte,也就说哪怕从内存中读取1字节的数据,CPU也会将其余的63字节带入缓存。这样设计的原因主要是为了提高缓存的时间局域性,因为所要执行的数据大小通常远远超过这个数字,提前将数据读取至缓存有利于接下来的数据在缓存中被命中。

2.2.1 矩阵运算分块

矩阵运算的循环迭代中都用到了行与列,因此原始数据矩阵与编码矩阵的访问总有一方是非连续的,通过简单的循环交换并不能改善运算的空间局域性。因此我们通过分块的方法来提高时间局域性来减少缓存缺失。

分块算法不是对一个数组的整行或整列进行操作,而是对其子矩阵进行操作,目的是在缓存中的数据被替换之前,最大限度的利用它。

分块的尺寸不宜过大,太大的分块无法被装进缓存;另外也不能过小,太小的分块导致外部逻辑的调用次数大大上升,产生了不必要的函数调用开销,而且也不能充分利用缓存空间。

2.2.2 减少缓存污染

不难发现的是,编码矩阵中的系数并不会完全覆盖整个GF(28),例如10+4的编码方案中,编码矩阵中校验矩阵大小为4×10,编码系数至多(可能会有重复)有10×4=40个。因此我们可以事先进行一个乘法表初始化的过程,比如生成一个新的二维数组来存储编码系数的乘法表。缩小表的范围可以在读取表的过程中对缓存的污染。

另外在定义方法集时需要注意的是避免结构体中的元素浪费。避免将不必要的参数扔进结构体中,如果每一个方法仅使用其中若干个元素,则其他元素白白侵占了缓存空间。

三指令级并行与数据级并行的深入优化

本节主要介绍如何利用AVX/AVX2指令集以及指令级并行优化来进一步提高性能表现。除此之外,我们还可以对汇编代码进行微调以取得微小的提升。比如,尽量避免使用R8-R15这8个寄存器,因为指令解码会比其他通用寄存器多一个字节。但很多汇编优化细节是和CPU架构设计相关的,书本上甚至Intel提供的手册也并不能提供最准确的指导(因为有滞后性),而且这些操作带来的效益并不显著,在这里就不做重点说明了。

3.1利用AVX2

在上文中我们已经知道如何将乘法表拆分成128bits的大小以适应XMM寄存器,那么对于AVX指令集来说,要充分发挥其作用,需要将乘法表复制到256bit的YMM寄存器。为了做到这一点,我们可以利用XMM寄存器为YMM寄存器的低位这一特性,仅使用一条指令来完成表的复制(Intel风格):

vinserti128ymm0,ymm0,xmm0,1

这条指令作用是将xmm0寄存器中的数据拷贝到ymm0中,而剩余128位数据通过ymm0得到,其中立即数1表明xmm0拷贝的目的地是ymm0的高位。这条指令提供了两个sourceoperand(源操作数)以及一个destinationoperand(目标操作数),我们在这里使用ymm0寄存器同时作为源操作数和目标操作数来实现了表的复制操作。接下来我们便可以使用与SSSE3下同样的方式来进行单指令32byte的编码运算过程了。

由于使用了SSE与AVX这两种扩展指令集,我们需要避免AVX-SSETransitionPenalties[3]。之所以会有这种性能惩罚主要是由于SSE指令对YMM寄存器的高位一无所知,SSE指令与AVX指令的混用会导致机器不断的执行YMM寄存器的高位保存与恢复,这大大影响了性能表现。如果对指令不熟悉,难以避免指令混用,那么可以在RET前使用VZEROUPPER指令来清空YMM寄存器的高位。

3.2指令级并行(ILP)优化

程序分支指令的开销并不仅仅为指令执行所需要的周期,因为它们可能影响前端流水线和内部缓存的内容。我们可以通过如下技巧来减少分支指令对性能的影响,并且提高分支预测单元的准确性:

尽量少的使用分支指令

当贯穿(fall-through)更可能被执行时,使用向前条件跳转

当贯穿代码不太可能被执行时,使用向后条件跳转

向前跳转经常用在检查函数参数的代码块中,如果我们避免了传入长度为0的数据切片,这样可以在汇编中去掉相关的分支判断。在我的代码中仅有一条向后条件跳转指令,用在循环代码块的底部。需要注意的是,以上2、3点中的优化方法是为了符合静态分支预测算法的要求,然而在市场上基于硬件动态预测方法等处理器占主导地位,因此这两点优化可能并不会起到提高分支预测准确度的作用,更多的是良好的编程习惯的问题。

对于CPU的执行引擎来说,其往往包含多个执行单元实例,这是执行引擎并发执行多个微操做的基本原理。另外CPU内核的调度器下会挂有多个端口,这意味着每个周期调度器可以给执行引擎分发多个微操作。因此我们可以利用循环展开来提高指令级并行的可能性。

循环展开就是将循环体复制多次,同时调整循环的终止代码。由于它减少了分支判断的次数,因此可以将来自不同迭代的指令放在一起调度。

当然,如果循环展开知识简单地进行指令复制,最后使用的都是同一组寄存器,可能会妨碍对循环的有效调度。因此我们应当合理分配寄存器的使用。另外,如果循环规模较大,会导致指令缓存的缺失率上升。Intel的优化手册中指出,循环体不应当超过500条指令。[4]

四小结

以上内容较为完整的还原了纠删码引擎的实现过程,涉及到了较多的数学和硬件层面的知识,对于大部分工程师来说可能相对陌生,我们希望通过本系列文章的介绍能够为大家的工程实践提供些许帮助。但受限于篇幅,很多内容无法全面展开。比如,部分数学工具的理论与证明并没有得到详细的解释,还需要读者通过其他专业资料的来进行更深入的学习。

G9300 CROM锁

crom(BL)锁是管能不能刷第三方rom的,

oem锁是管能不能重置刷机的,相当于防止你手机被偷了,小偷拿去刷机重新用。

港版机刷国行rom,只需要开发者选项里面解oem锁,这个也就是港版rom会有这一限制,国行rom好像没有。

1.解锁和关闭 激活锁定(已经操作过的忽略)

–解锁BL:
搜索CROM 1.0.4 ,下载安装解锁工具按照提示解锁

https://pan.baidu.com/s/1hqCdX1E

CROM Service1.0.4.apk

–关闭重新激活锁定(没的打开过的也忽略):
设定,搜索重新激活锁定,然后登陆三星账号,关闭。