xp , Nov 20 2017 , hash collision math zh brainhole

软件开发中, 一个hash表, 相当于把n个key随机放入到 b 个bucket, 来实现使用b个单位的空间存储n个数据.

最后key在bucket中的分布, 我们可以看到hash表的一些有趣的现象:

hash表中key的分布规律

当hash表中key和bucket数量一样时(`n/b=1`):

37% 的桶是空的.
37% 的桶里只有1个key.
26% 的桶里有1个以上的key(hash冲突).

下面这个图更直观的展示了当n=b=20的时候, hash表中每个bucket中key的个数的分布, (我们按照key的数量对bucket做了排序):

和直觉不1样, 往往我们对hash表的第一感觉是: 如果key随机的扔到所有的桶里, 桶里的key的数量应该是比较均匀的, 每个桶里key的数量的期望是1.

而实际上, 桶里的key的分布在n比较小的时候是非常不均匀的, 即使平均下来是1! 当n增大的时候, 这种不均匀会逐渐趋于平均.

key的数量对3类bucket数量的影响

下面这个表格表示当b不变, n增大时, n/b 的值如何影响3类bucket的数量占比 (冲突占比也就是含有多于1个key的bucket):

n/b: (每个bucket平均key的数量)	空bucket占比	1个key的bucket占比	冲突占比
n/b=0.5	61%	30%	9%
n/b=0.75	47%	35%	17%
n/b=1.0	37%	37%	26%
n/b=2.0	14%	27%	59%
n/b=5.0	01%	03%	96%
n/b=10.0	00%	00%	100%

更直观1点, 我们用一个图来展示空bucket率和冲突率随n/b的变化趋势:

key的数量对bucket的均匀程度的影响

上面的几组数字是在hash表的n/b比较小的时候比较有意义的参考值, 但是当n/b逐渐增大的时候, 空bucket几乎肯定是0, 1个key的bucket也几乎是0, 绝大多数bucket是含有多个key的.

当n/b超过1的时候(1个bucket允许存储多个key), 我们主要观察的对象就转变成bucket里key的数量的分布规律.

下面这个表表示n/b比较大的时候, 每个bucket的key的数量趋于均匀的时候, 不均匀的程度是多少.

为了描述这种不均匀的程度, 我们使用bucket中key的个数的最大值和最小值之间的比例((most-fewest)/most)来表示.

下面这个表格列出了b=100时, 随着n的增大, key的分布越来越趋于平均的趋势.

n/b: (bucket平均key的数量)	最少key的bucket的key的数量	最大差异(most-fewest)/most
1	0	100.0%
10	2	88.0%
100	74	41.2%
1,000	916	15.5%
10,000	9,735	5.1%
100,000	99,161	1.6%
1,000,000	997,996	0.4%

可以看出, 随着n/b每个bucket里key的平均数量的增加, bucket的不均匀程度也逐渐降低.

和空bucket比例或1个key的bucket比例不同(只取决于n/b), 均匀程度不仅取决于n/b的值, 也会受到b本身的值的影响, 后面会提到.

这里我们没有使用统计里常用的均方差去描述key分布的不均匀程度, 因为在软件开发过程中, 更多的时候要考虑最坏情况, 来准备所需的内存等资源.

Load Factor: `n/b<0.75`

hash表中常用一个概念 load factor $\alpha = \frac{n}{b}$ . 来描述hash表的特征.

通常, 基于内存存储的hash表, 它的 n/b <= 0.75. 这样的设定, 既可以不浪费太多空间, 也可以保持hash表中的key的冲突相对较低, 低冲突率意味着低频率的hash重定位, hash表的插入都会更快.

线性探测是一个经常被使用的解决插入时hash冲突的算法, 它在1个key被放到1个bucket出现冲突的时候, 按照(逐步增加的步长)顺序的向后查看这个bucket后面的bucket, 直到找到1个空的bucket. 因此它对hash的冲突非常敏感.

在n/b=0.75 这个场景中, 如果不使用线性探测 (譬如使用bucket内的链表来保存多个的key), 大约有47% 的bucket是空的. 如果使用线性探测, 这47%中的 bucket, 有大约1半的的bucket 会被线性探测填充.

在很多内存hash表的实现中, 选择 n/b<=0.75 作为hash表的容量上限, 不仅仅是考虑到冲突率随n/b的增大而增大, 更重要的是线性探测的效率会随着n/b的增大而迅速增加, 详细分析大家可以参考线性探测中的实现和分析.

hash表特性小贴士:

hash表本身是1个通过1定的空间浪费来换取效率的算法. 这三者不可同时兼得: 低时间开销(O(1)), 低空间浪费, 低冲突率.
hash表只适合纯内存数据结构的存储:
- 必须很快, 因为hash表实际上是浪费空间换取了访问速度. 很多时候对磁盘的空间浪费是不能忍受的, 对内存的少许浪费是可以接受的.
- hash表只适合随机访问快的存储介质. 硬盘上的数据存储更多使用btree或其他有序的数据结构.
多数高级语言(内建了hash table/hash set等), 都保持 n/b<=0.75.
hash表在n/b比较小的时候, 不会均匀的分配key!

Load Factor: `n/b>1`

另外一种hash表的实现, 专门用来存储比较多的key, 当 n/b 大于 1.0的时候, 线性探测不再能工作(没有足够的bucket来存储每个key). 这时1个bucket里不是存储1个key, 一般用chaining 在一个bucket内, 将所有落在这个bucket里的key用链表连接起来, 来解决冲突时的多个key的存储.

链表只在 n/b 不是很大时适用. 因为链表的查找需要 O(n)的时间开销, 对于非常大的n/b, 有时也会用tree来替代链表来管理bucket内的key.

大的n/b的使用场景之一是: 将一个网站的用户随机分配到多个不同的web-server上, 这时, 每个web-server可以服务很多个用户. 多数情况下, 我们都希望这种用户对web-server分配能尽可能均匀, 从而有效利用每个web-server的资源.

这种情况下, 我们需要关注的是hash的均匀程度, 我们这里要讨论的, 假定hash函数是完全随机的, 均匀程度根据n和b如何变化.

`n/b` 越大, key的分布越均匀.

当 n/b 非常大的时候, 一个bucket是空的概率趋近于0, 而每个bucket中的key的数量趋于平均.

统计上, 每个bucket中key的数量的期望是

${avg} = \frac{n}{b}$

我们定义一个bucket平均key的数量是100%: bucket中key的数量刚好是n/b,

下面3个图模拟了 b=20, n/b分别是 10, 100, 1000时, bucket中key的数量分布.

我们看出当 n/b 增大时, 最多key的bucket和最少key的bucket的差距在逐渐缩小. 下面的表里列出了随着b 和 n/b增大, key分布的均匀程度((most-fewset)/most)的变化:

_b \ ⁿ	10²	10³	10⁴	10⁵	10⁶
100	37.4%	13.6%	4.5%	1.4%	0.5%
1000	47.3%	17.7%	6.0%	1.9%	0.6%
10000	54.0%	20.9%	7.1%	2.3%	0.7%

结论:

场景	趋势
key的数量(n) 确定时	bucket越多越不均匀.
bucket的数量(b) 确定时	key越多越均匀.
bucket和key的数量比例(n/b)一致时	n和b越大越均匀.

计算

大部分上面的结构都来自于程序模拟, 现在我们来看看从数学上怎么来计算这些数值.

每类bucket的数量

bucket的类型	bucket数量
包含`0`个key的bucket的比例	$b \times e^{-\frac{n}{b}}$
包含`1`个key的bucket的比例	$n \times e^{ - \frac{n}{b} }$
包含`>1`个key的bucket的比例	$b - b \times e^{-\frac{n}{b}} - n \times e^{ - \frac{n}{b} }$

空bucket 数量

对1个key, 它不在某个特定的bucket的概率是 $\frac{b-1}{b}$ .

所有key都不在某个特定的bucket的概率是 $(\frac{b-1}{b})^n$

我们知道

$\lim_{b\to \infty} (1+\frac{1}{b})^b = e$ .

某个bucket是空的概率就是:

$(\frac{b-1}{b})^n = ((1- \frac{1}b)^b)^{\frac{n}{b}} = e^{-\frac{n}{b}}$

总的空bucket数量就是:

$b e^{-\frac{n}{b}}$

有1个key的bucket的数量

对某个特定的bucket, 刚好有1个key的概率是: n个key中有1个key有1/b的概率落到这个bucket里, 其他key以1-1/b的概率不落在这个bucket里:

$\begin{align} & {n \choose 1} ( \frac{1}{b} )^1 ( 1 - \frac{1}{b} )^{n-1} \\ = & \frac{n}{b} e^{-\frac{n}{b}} \end{align}$

刚好有1个key的bucket的数量就是:

$b\frac{n}{b} e^{-\frac{n}{b}} = n e^{ - \frac{n}{b} }$

多个key的bucket

就是剩下的咯:

$b - b e^{-\frac{n}{b}} - n e^{ - \frac{n}{b} }$

key在bucket中分布的均匀程度

类似的, 1个bucket中刚好有i个key的概率是 n个key中任选i个出来, i个key都以1/b的概率落在这个bucket里, 其他n-i个都以1-1/b的概率不落在这个bucket里:

$p(i) = {n \choose i} ( \frac{1}{b} )^{ i } ( 1 - \frac{1}{b} )^{n-i}$

上面这个是辣个出名的二项式分布.

我们可以通过二项式分布来估计最大bucket的key的数量, 和最小bucket的key的数量.

通过正太正态分布来近似

当 n, b 都很大时, 二项式分布可以用正态分布正态分布来近似, 来估计key分布的均匀性:

让 $p = \frac{1}{b}$ . 1个bucket中刚好有i个key的概率是:

$\begin{align} p(i) = & {n \choose i}p^i(1-p)^{n-i} \\ \approx & \frac{1} {\sigma \sqrt{2 \pi} } e^{ - \frac{(i-\mu)^2} {2 \sigma^2} } \end{align}$ $\begin{align} \mu = & np \\ \sigma^2 = & np(1-p) \\ \end{align}$

1个bucket中key的数量不多于x的概率是:

$P(x) = \sum_{i=0}^x p(i)$

所以, 所有少于x个key的bucket的数量是:

$b \cdot P(x) = b \cdot \sum_{i=0}^x p(i)$

包含最小bucket的key的数量, 可以用这个方法开估算: 如果少于x个key的bucket的数量是1, 那么这唯一1个bucket就是最少key的bucket. 所以我们只要找到1个最小的x, 让包含少于x个key的bucket总数为1, 这个x就是最小bucket的key的数量

计算最小key数量 `x`

一个bucket里包含不多于x个key的概率是:

$\sum_{i=0}^x p(i) \approx \int_{0}^{x} p(i) di \approx \int_{-\infty}^{x} p(i) di = \Phi( \frac{x-\mu}\sigma )$

$\Phi(x)$ 是正态分布的累计分布函数, 当x-u 趋近于0的时候, 可以使用以下方式来近似:

$\Phi(x)\; =\;0.5+\frac{1}{\sqrt{2\pi}}\cdot e^{-x^2/2}\left[x+\frac{x^3}{3}+\frac{x^5}{3\cdot 5}+\cdots+\frac{x^{2n+1}}{(2n+1)!!} + \cdots\right]$

这个函数还是不太容易计算, 但是如果只是找到x, 我们可以在[0~u]的范围内逆向遍历x, 以找到一个x 使得包含不多于x个key的bucket的期望数量是1.

$b \cdot \Phi(\frac{x-\mu}\sigma) = 1$

这个x就可以粗略地认为是最少key的bucket里key的数量, 而这个hash表中, 不均匀的程度可以用最多key的数量和最少key的数量的差异来描述: 因为正态分布是对称的, 所以最大key的数量可以用 u + (u-x) 来表示. 最终, 最不均匀的最大bucket和最小bucket的比例就是:

$\frac{u+(u-x)-x}{u+(u-x)} = 1 - \frac{x}{2u-x}$

u是均值n/b.

程序模拟

下面这个python脚本模拟了key在bucket中分布的情况, 同时对比计算的结果, 用来验证我们上面的计算结果.

import sys
import math
import time
import hashlib

def normal_pdf(x, mu, sigma):
    x = float(x)
    mu = float(mu)

    m = 1.0 / math.sqrt( 2 * math.pi ) / sigma
    n = math.exp(-(x-mu)**2 / (2*sigma*sigma))

    return m * n

def normal_cdf(x, mu, sigma):
    # integral(-oo,x)

    x = float(x)
    mu = float(mu)
    sigma = float(sigma)

    # to standard form
    x = (x - mu) / sigma

    s = x
    v = x
    for i in range(1, 100):
        v = v * x * x / (2*i+1)
        s += v

    return 0.5 + s/(2*math.pi)**0.5 * math.e ** (-x*x/2)

def difference(nbucket, nkey):

    nbucket, nkey= int(nbucket), int(nkey)

    # binomial distribution approximation by normal distribution
    # find the bucket with minimal keys.
    #
    # the probability that a bucket has exactly i keys is:
    #   # probability density function
    #   normal_pdf(i, mu, sigma)
    #
    # the probability that a bucket has 0 ~ i keys is:
    #   # cumulative distribution function
    #   normal_cdf(i, mu, sigma)
    #
    # if the probability that a bucket has 0 ~ i keys is greater than 1/nbucket, we
    # say there will be a bucket in hash table has:
    # (i_0*p_0 + i_1*p_1 + ...)/(p_0 + p_1 + ..) keys.
    p = 1.0 / nbucket
    mu = nkey * p
    sigma = math.sqrt(nkey * p * (1-p))

    target = 1.0 / nbucket
    minimal = mu
    while True:

        xx = normal_cdf(minimal, mu, sigma)
        if abs(xx-target) < target/10:
            break

        minimal -= 1

    return minimal, (mu-minimal) * 2 / (mu + (mu - minimal))

def difference_simulation(nbucket, nkey):

    t = str(time.time())
    nbucket, nkey= int(nbucket), int(nkey)

    buckets = [0] * nbucket

    for i in range(nkey):
        hsh = hashlib.sha1(t + str(i)).digest()
        buckets[hash(hsh) % nbucket] += 1

    buckets.sort()
    nmin, mmax = buckets[0], buckets[-1]

    return nmin, float(mmax - nmin) / mmax

if __name__ == "__main__":

    nbucket, nkey= sys.argv[1:]

    minimal, rate = difference(nbucket, nkey)
    print 'by normal distribution:'
    print '     min_bucket:', minimal
    print '     difference:', rate

    minimal, rate = difference_simulation(nbucket, nkey)
    print 'by simulation:'
    print '     min_bucket:', minimal
    print '     difference:', rate

Reference

xp , Oct 22 2017 , paxos,network theory distributed consensus tutorial quorum replication

xp的分布式系统系列教程之: 可靠分布式系统基础 Paxos 的直观解释

Paxos 已经逐渐被承认是分布式系统中不可缺少的核心算法, 越来越多的分布式系统都是以paxos或其变种来达到强一致性的.

本文是一篇paxos入门教程, 从基本的分布式中的问题: 主从复制，quorum-rw等算法出发, 通过逐步解决和完善这几个问题, 最后推导出paxos的算法.

本文分为2个部分:

前1部分是分布式一致性问题的讨论和解决方案的逐步完善, 用比较通俗的语言得出paxos算法的过程. 如果你只希望理解paxos而不打算花太多时间深入细节, 只阅读这1部分就可以啦.
第2部分是paxos算法和协议的严格描述. 这部分可以作为paxos原paper的实现部分的概括. 如果你打算实现自己的paxos或类似协议, 需要仔细了解协议细节, 希望这部分内容可以帮你节省阅读原paper的时间.

在线查看 html 版本 paxos.html

可靠分布式系统基础 Paxos的直观解释 on slideshare.net from Yanpo Zhang

Download the paxos.pdf

Paul Yang , Oct 10 2017 , theory distributed tutorial replication erasure code brainhole

白山HTTPS功能升级——ChaCha20算法实现移动端设备节电

结论
- 性能对比
白山CDN支持和建议应用场景
延伸阅读： ChaCha20算法原理
- ChaCha20的keystream生成
- TLS中的ChaCha20

结论

老规矩，先说结论。

ChaCha20是Google大力推广的一种对称加密算法，用于解决不支持AES硬件加速指令的Android设备的HTTPS性能问题。Google在其Chrome浏览器中增加了对这一算法的支持，同时还支持Poly1305摘要算法，形成了ChaCha20-Poly1305组合，并在2015年和2016年将这组算法标准化，形成 RFC 7539 和 RFC 7905 两篇RFC文档。

在对称加密领域，自从AES算法从性能上超越并取代3DES算法，成为NIST指定的加密算法后，再未出现其他广泛使用并且兼顾性能和安全的对称加密算法。这带来了以下几个问题：

未来如果AES被发现存在问题，人们将不得不退而使用老旧的3DES算法，因此业界需要一个备选算法；
在不支持AES硬件加速指令的设备上，AES算法的性能不具备明显优势（尤其是和某些流加密算法相比）；
AES如果实现的不正确，可能存在缓存碰撞时序攻击（AES Cache-Collision Timing Attack）。

而ChaCha20可以较好的解决上述问题。

ChaCha20是一种流加密算法，实现较为简单，并且比纯软件实现的AES性能更好。

性能对比

chacha20-speed-no-hw

上图是在不使用AES硬件加速的情况下，对AES和ChaCha20进行的性能对比测试。其中ChaCha20性能是GCM模式AES256的5倍左右。

我们也将ChaCha20同已经濒临灭绝的RC4算法进行了对比，同为流加密算法，ChaCha20的性能达到了RC4的2倍之多。单位时间内运算次数的提高，表示着单次操作所需的指令周期更短，而在移动端设备上这种特点直接影响电池电量的消耗。

虽然在HTTPS的场景中，一次全握手产生的功耗要远大于对称加密环节产生的，但是在针对大文件加密、解密操作时，更快的对称加密算法依然存在实际应用价值。

但如果设备已经支持AES硬件加速指令，例如iPhone和部分Android系统手机或支持AES-NI指令的Intel CPU等，AES的速度依然具有绝对优势：

chacha20-speed-hw

由上图可见，其性能约为ChaCha20的3倍左右，此外GCM模式的AES比CBC模式在有硬件加速的情况下性能提升的更大，这主要是由于GCM模式可以比CBC模式能更好利用硬件流水线进行并发。（这个话题和本文主题无关，因此就不继续展开了。）

白山CDN支持和建议应用场景

白山CDN在其HTTPS服务中全面支持ChaCha20-Poly1305算法，并采用自动适应客户端算法列表的处理手段：

如果客户端不支持AES硬件加速指令，则优先使用ChaCha20
否则按照服务器的算法优先级顺序选择AES算法
目前我们支持的TLS加密套件有：

TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256
TLS_CHACHA20_POLY1305_SHA256 (TLSv1.3用）

结合以上ChaCha20的性能对比，我们可以认为该算法最适合在不支持AES硬件加速的Android平台中使用。因此作为应用程序，最好可以判断当前运行的平台是否支持AES指令。

如不支持，则将上述TLS加密套件排列在客户端ClientHello消息中最前的位置（根据支持的协议），白山CDN会根据客户端支持的加密套件列表选择最优算法来和客户端握手。

在支持AES指令的硬件平台上，推荐优先选择AES-GCM算法；而CBC模式的AES和RC4算法在很多情况下并非最好选择，应当尽量避免过多使用。

延伸阅读： ChaCha20算法原理

ChaCha20是一种流加密算法，其原理和实现都较为简单，大致可以分成如下两个步骤：

基于输入的对称秘钥生成足够长度的keystream
将上述keystream和明文进行按位异或，得到密文

解密流程同上。以下着重讲解keystream的生成方法。

ChaCha20的keystream生成

ChaCha20算法中的基本操作叫做“quarter round”，一个quarter round定义如下：

a, b, c, d是4个4字节（32位）的无符号整数，对它们进行如下操作（其中‘«<’表示向左轮转）：

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

得到一组新的a, b, c, d，共16个字节。

另一个重要概念是ChaCha state，一个ChaCha state由16个32位数字组成，例如：

879531e0 c5ecf37d 516461b1 c9a62f8a
44c20ef3 3390af7f d9fc690b 2a5f714c
53372767 b00a5631 974c541a 359e9963
5c971061 3d631689 2098d9d6 91dbd320

quarter-round可以应用到state中，我们定义quarter-round(x, y, z, w)为应用到state中的quarter-round操作，例如quater-round(1, 5, 9, 13)是计算如下带星号（*）数字的值：

879531e0 *c5ecf37d 516461b1 c9a62f8a
44c20ef3 *3390af7f d9fc690b 2a5f714c
53372767 *b00a5631 974c541a 359e9963
5c971061 *3d631689 2098d9d6 91dbd320

所以keystream的生成，就是在state上反复应用确定的好的quater-round(x, y, z, w)组合，得到一个新的64字节（即512位）的随机数据，此数据即为一个keystream block。state的内容不是随便定义的，ChaCha20算法存在如下规定：

cccccccc  cccccccc  cccccccc  cccccccc
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
bbbbbbbb  nnnnnnnn  nnnnnnnn  nnnnnnnn

其中：

c：4个32位数字，内容固定为：0x61707865, 0x3320646e, 0x79622d32, 0x6b206574。
k：256位的对称密钥，即32字节
b：count，按明文的block数递增，可以从0或者1开始
n：nouce，其组成根据ChaCha20在不同协议中的使用而有所区别，下文将介绍TLS中的nouce构成

上述所有的数值都以4字节为一组，小端存储。

接下来介绍一个round：

 QUARTERROUND ( 0, 4, 8,12)
 QUARTERROUND ( 1, 5, 9,13)
 QUARTERROUND ( 2, 6,10,14)
 QUARTERROUND ( 3, 7,11,15)
 QUARTERROUND ( 0, 5,10,15)
 QUARTERROUND ( 1, 6,11,12)
 QUARTERROUND ( 2, 7, 8,13)
 QUARTERROUND ( 3, 4, 9,14)

以上是两个round，每个round由4个quarter-round组成，将上述8个quarter round在state上执行10次（一共20个round，即ChaCha20中的20），得到最终结果即是当前block的keystream block。

一个更加清楚的例子：

ChaCha state:

       61707865  3320646e  79622d32  6b206574
       03020100  07060504  0b0a0908  0f0e0d0c
       13121110  17161514  1b1a1918  1f1e1d1c
       00000001  09000000  4a000000  00000000
       

应用上述20轮变换，可得到：

Keystream block:
 
       e4e7f110  15593bd1  1fdd0f50  c47120a3
       c7f4d1c7  0368c033  9aaa2204  4e6cd4c3
       466482d2  09aa9f07  05d7c214  a2028bd9
       d19c12b5  b94e16de  e883d0cb  4e3c50a2

这个keystream block是512位的，因此当一段512位的数据需要加密，直接将待加密数据和上述keystream block按位异或即可。如果数据长度多于512位，则需将其分割成多个512位的block，对每个block都需要计算keystream block（注意：不同block的count不一样），对于最后一个block，如果待加密数据不足512位，则舍弃掉对应keystream block中的多余位数即可。

另外一种思路是先计算全部keystream block，拼接成一个完整的keystream，和整个待加密数据进行异或，当然这种实现会占用较多内存。

解密操作和加密操作一样，因此不再赘述，更多细节及案例，可参考 RFC 7539 。

TLS中的ChaCha20

在TLS中使用ChaCha20，主要是如下几个加密套件：

TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256   = {0xCC, 0xA8}
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256 = {0xCC, 0xA9}
TLS_DHE_RSA_WITH_CHACHA20_POLY1305_SHA256     = {0xCC, 0xAA}
 
TLS_PSK_WITH_CHACHA20_POLY1305_SHA256         = {0xCC, 0xAB}
TLS_ECDHE_PSK_WITH_CHACHA20_POLY1305_SHA256   = {0xCC, 0xAC}
TLS_DHE_PSK_WITH_CHACHA20_POLY1305_SHA256     = {0xCC, 0xAD}
TLS_RSA_PSK_WITH_CHACHA20_POLY1305_SHA256     = {0xCC, 0xAE}

如前所述，白山目前主要支持TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256和TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256

此外TLS中的ChaCha20对nouce的组成，还存在如下规定：

在TLS record sequence的左侧填充4个值为0的字节，形成一个96位的数值
将上述数值和client_write_IV或server_write_IV进行异或，得到最终的nouce

作者简介：

杨洋，白山架构师兼驻辽代表，“白十三的码路”缔造者。

NGINX开发、安全系统研发方向布道师。10年研开发经验，先后就职于东软、阿里云、金山云等，OpenSSL代码贡献榜排名17，擅长安全产品研发及各类开发指南编译工作，Bulletproof SSL and TLS第一译者。爱好不断挑战HTTPS流量与加密底线、持续突破各类防御系统极限。

林胜恩 , Sep 15 2017 , theory distributed tutorial replication erasure code brainhole

白山HTTPS功能升级——TLSv1.3协议

1 协议发展历程

SSL协议起源于1994年，当时网景公司推出首版网页浏览器及HTTPS协议，用于加密的就是SSL。此后相继推出SSL2.0及3.0版本，1999年IETF将SSL标准化，即 RFC 2246 ，并将其命名为TLS。2006年和2008年又分别推出TLS1.1和TLS1.2版本。

在SSL/TLS发展过程中曾出现过各种安全漏洞，如Heartbleed、POODLE，这导致SSL3.0及其之前版本逐渐废弃，目前互联网使用的主流协议是TLS1.2版本。

TLS1.3协议针对安全强化及效率提升等方面进行了大量修改，相继推出21个草案版本，即将完成最终的标准化。完成后，OpenSSL组织将推出OpenSSL 1.1.1版本对TLS1.3协议标准提供支持。

2 安全强化

TLS1.3依循极简主义的设计哲学，移除并修复了旧版本协议中的坏味道，将密钥交换、对称加解密、压缩等环节中可能存在的安全隐患剔除，防范于未然。

2.1 密钥交换

2.1.1 完全支持PFS

TLS1.3协议中选取的密钥交换算法均支持前向安全性。斯诺登事件之后互联网企业开始重视加密算法的前向安全性，防止私钥被破解之后历史数据也能被解密成明文。

为了达到上述安全目的，TLS1.3协议中废除了不支持前向安全性的RSA和静态DH密钥交换算法。

2.1.2 废弃DSA证书

DSA证书作为历史遗留产物，因安全性差，从未被大规模应用，故在TLS1.3协议中被废弃。

2.1.3 RSA填充模式更改

协议中规定RSA填充模式使用PSS。

2.1.4 禁用自定义的DH组参数

如果选用了不“安全”的素数作为DH的组参数，并且使用静态DH密码套件或使用默认OpenSSL配置的DHE加密套件（特别是SSL_OP_SINGLE_DH_USE选项未设置），就很容易受到 Key Recovery Attack 攻击。因此TLS1.3协议中禁用自定义的DH组参数。

2.2 对称加密

2.2.1 禁用CBC模式

针对CBC模式加密算法的攻击，历史上出现过两次，分别是2011年BEAST和2013年Lucky 13，实践证明这种对称加密模式确实存在安全隐患。

2.2.2 禁用RC4流加密算法

2011年9月，研究人员发现了BEAST攻击，该攻击针对所有基于CBC模式的加密算法。为解决这个问题，专家建议采用非CBC模式且普及率较高的RC4算法作为替代方案，由此RC4算法得到广泛应用。

随着TLS版本的演进，BEAST攻击可通过升级到新版本解决，不必要采用RC4这种陈旧算法来替代。另外，2013年英国皇家哈洛威学院的研究人员发现了一种针对TLS的攻击，该攻击可以从RC4算法加密的密文中恢复出少量明文，证明了这种算法无法提供让人放心的安全等级。

为防止RC4算法被彻底破解，导致之前加密的网络流量被解密出现严重的安全事故，互联网公司逐渐废弃了这个算法。2014年，CloudFlare将RC4算法的优先级从最高降为最低。2015年，IETF组织在rfc7465中明确指出要禁用RC4流加密算法。

2.2.3 禁用SHA1

早在2005年研究机构就发现SHA1存在理论上的漏洞，可能造成碰撞攻击。

2013年开始微软、Google、Symantec等相关厂商相继公布SHA1证书的升级计划并宣布2017年将开始停止信任SHA1证书。

2017年初Google与荷兰研究机构CWI Amsterdam共同宣布破解SHA1，将SHA1的碰撞攻击从理论转变为现实。

2.2.4 禁用出口密码套件

出口密码套件是指上世纪90年代美国政府为让NSA能够破解所有加密的外国通讯消息，规定其出口的必须是安全性较弱的密码套件，例如私钥长度不大于512的RSA加密算法，这类加密套件被称为出口密码套件。在当时，安全等级较高的加密套件被是为战争武器禁止出口。

尽管2000年之后美国放宽了密码出口管制，但是由于历史遗留问题，许多实际场景中仍使用出口加密套件进行协商，导致FREAK和LogJam攻击的出现，这两种攻击通过中间人将加密套件降级成出口套件，进而将破解数据。

2.3 禁用TLS压缩

由于TLS压缩存在安全漏洞，TLS1.3协议删除了该特性。该漏洞表现为通过CRIME攻击可窃取启用数据压缩特性的HTTPS或SPDY协议传输的Cookie。在成功解读身份验证Cookie后，攻击者可实行会话劫持并发动进一步攻击。

2.4 加密握手消息

TLS1.3协议中规定在ServerHello消息之后的握手信息需要加密。TLS1.2及之前版本的协议中各种扩展信息在ServerHello中以明文方式发送，新版本中可在加密之后封装到EncryptedExtension消息中，在ServerHello消息之后发送，提高数据安全性。

3 效率提升

对于互联网服务而言更快的页面加载意味着更好的用户体验，从而也能带动产品销售的提升。

HTTPS在提高网络安全的同时却增加了额外的性能消耗，包括额外的SSL握手交互过程，数据加解密对CPU的消耗等。TLS1.3在提高效率方面进行了大量改进，特别是对SSL握手过程进行了重新设计，将握手交互延时从2-RTT降低至1-RTT甚至是0-RTT。在网络环境较差或节点距离较远的情况下，这种优化能节省几百毫秒的时间。这几百毫秒往往就能决定用户下一步的行为是继续浏览网页还是关闭网页。

3.1 2-RTT

下面以ECDHE密钥交换算法为例，介绍下TLS1.2协议完整的SSL握手过程，如下图所示。

tls13a

首先客户端发送ClientHello消息，该消息中主要包括客户端支持的协议版本、加密套件列表及握手过程需要用到的ECC扩展信息；
服务端回复ServerHello，包含选定的加密套件和ECC扩展；发送证书给客户端；选用客户端提供的参数生成ECDH临时公钥，同时回复ServerKeyExchange消息；
客户端接收ServerKeyExchange后，使用证书公钥进行签名验证，获取服务器端的ECDH临时公钥，生成会话所需要的共享密钥；生成ECDH临时公钥和ClientKeyExchange消息发送给服务端；
服务器处理ClientKeyExchange消息，获取客户端ECDH临时公钥；服务器生成会话所需要的共享密钥；发送密钥协商完成消息给客户端；
双方使用生成的共享密钥对消息加密传输，保证消息安全。

从上述过程可以看出，在TLS1.2中需要加密套件协商、密钥信息交换、ChangeCipherSpec协议通告等过程，需要消耗2-RTT的握手时间，这是造成HTTPS协议较慢的一个重要原因。

3.2 1-RTT

TLS1.3中提供1-RTT的握手机制，以ECDHE密钥交换过程为例，握手过程如下。将客户端发送ECDH临时公钥的过程提前到ClientHello ，同时删除了ChangeCipherSpec协议简化握手过程，使第一次握手时只需要1-RTT。

tls13b

客户端发送ClientHello消息，该消息主要包括客户端支持的协议版本、DH密钥交换参数列表KeyShare；
服务端回复ServerHello，包含选定的加密套件；发送证书给客户端；使用证书对应的私钥对握手消息签名，将结果发送给客户端；选用客户端提供的参数生成ECDH临时公钥，结合选定的DH参数计算出用于加密HTTP消息的共享密钥；服务端生成的临时公钥通过KeyShare消息发送给客户端；
客户端接收到KeyShare消息后，使用证书公钥进行签名验证，获取服务器端的ECDH临时公钥，生成会话所需要的共享密钥；
双方使用生成的共享密钥对消息加密传输，保证消息安全。

3.3 0-RTT

为使TLS协议的性能得到极致提升，TLS 1.3提出0-RTT工作模式。对于客户最近访问过的网站，可以在第一次交互时就将加密数据发送给服务器。

具体的实现过程如下：

客户端和服务端通过TLS session复用或外部输入的方式共享PSK，这种情况下，允许客户端在第一次交互的ClientHello消息中包含应用数据，该数据使用PSK加密。

0-RTT模式不具有前向安全性，且消息可能被用作重放攻击，所以安全性较低，需慎重使用。

4 总结

上文已详细阐述TLS 1.3的各种优化改进，为让大家有更加直观的感受，白山搭建了支持TLS 1.3协议的服务器，欢迎大家访问体验。

当前主流浏览器支持的draft-18的服务器地址为https://tls13.baishancloud.com/

最新的draft-21版本的服务器地址为https://tls13.baishancloud.com:44344。

作者简介：

林胜恩，花名“蒙多尔”，白山系统开发工程师

嵌入式Linux系统开发方向及HTTPS相关领域初号机。多年研发经验，曾就职于锐捷网络，主导网络设备管理协议工作。偏爱不断挑战HTTPS性能天花板，加入酒精更易产生反差萌化学反应，故又名“酒后苏轼”。

Paul Yang , May 24 2017 , theory distributed tutorial replication erasure code brainhole

浅谈RSA Padding

一个有意思的问题，如果一段数据用RSA私钥进行加密，针对加密的密文，如果使用和加密私钥不匹配的公钥进行解密，会解密出无意义的内容，还是会解密失败？

答案是：it depends!

首先要了解两个概念：密码学原语（Cryptographic Primitive）和密码体制（Cryptographic Scheme）

Primitive

密码学原语指的是某种数学计算的方式，可以对数据进行某种密码学处理。例如在RSA中，有加密原语和解密原语，顾名思义，这两个原语分别定义了RSA的加密和解密算法。

例如，RSA的公钥加密过程可以表示为：

c = RSAEP((n, e), m)

其中：

c是密文
m是明文
(n, e)是公钥，其中n是modulus，e是RSA的公钥指数
RSAEP是RSA Encryption Primitive的意思，即RSA加密原语

RSAEP的具体内容，就是RSA的加密算法，也就是“数学层面”的内容：

c = m^e mod n

对应的还有一个RSADP，就是解密的原语，解密的原语根据私钥表述类型的不同，除了可以进行和加密原语类似的指数运算之外，还可以利用中国剩余定理，使用分离的素数而不是模数n进行计算，避免了性能开销较大的指数运算，实现优化，这也是实现多素数RSA的基础原理。具体可以参考RFC3447的5.1.2节，在此不再赘述。

那么，再回到最初的问题，如果用于解密的公钥（或私钥）与加密用的私钥（或公钥）不配对，那么结果就是你会经过计算得出一个数值，但是这个数值不是原来的明文，因此从这个意义上来说，解密算法不会“失败”。

Scheme

但是在现实生活中，几乎没有直接对于primitives的使用，我们可以用openssl来对一段数据进行加密，然后用不匹配的秘钥进行解密。

先生成两对公私钥，A对和B对：

$ ./openssl genpkey -algorithm RSA -out priv_A.key -pkeyopt rsa_keygen_bits:2048
...................+++
......................+++

$ ./openssl genpkey -algorithm RSA -out priv_B.key -pkeyopt rsa_keygen_bits:2048
...................+++
......................+++

从私钥导出公钥：

$ ./openssl rsa -pubout -in priv_A.key -out pub_A.key
$ ./openssl rsa -pubout -in priv_B.key -out pub_B.key

这样就有了两个key pair：

-rw-------. 1 paul paul   1704 Nov 28 17:50 priv_A.key
-rw-------. 1 paul paul   1704 Nov 28 17:50 priv_B.key
-rw-rw-r--. 1 paul paul    451 Nov 28 17:54 pub_A.key
-rw-rw-r--. 1 paul paul    451 Nov 28 17:55 pub_B.key

OK，接下来测试一下正常的加密和解密，用pub_A加密，用priv_A解密的效果：

rsa_good

可以正常解密出原文，接下来常使用错误的私钥进行解密，使用priv_B：

rsa_bad

并没有出现无意义的内容，而是openssl直接报错：

rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error
rsa routines:rsa_ossl_private_decrypt:padding check failed

这个就是因为在实际中，一般不会直接使用原语对数据进行操作，因为直接使用原语进行运算会产生很多的安全问题，可以参考：这里

为此，实践中的RSA都会填充（padding）随机数据，然后再进行加密，可以使密文多样化，这种规定如何填充的方法就是scheme。

RSA padding的主要scheme有几种：

加密：
- RSAES-PKCS1-v1_5: PKCS #1中规定的老式方法，从PKCS #1 version 1.5开始使用
- RSAES-OAEP，新式方法，可见：OAEP，有图
签名：
- RSASSA-PKCS-v1_5: 老式方法
- RSASSA-PSS: 新式方法

在openssl命令中可以使用参数来指定使用哪种padding scheme，默认是PKCS #1的老式方法：

rsa_padding

当然，你也可以不padding，那就和直接使用原语无差别了。

我们再基于PKCS的padding方式来看为何openssl能发现解密失败，而不是返回数据。首先要了解一下具体的padding方法，根据RFC 3447的7.2.1节的2.b步骤：

EM = 0x00 || 0x02 || PS || 0x00 || M.

PS，padding string，随机数
M，明文

padding的方式是在固定的pattern之中加上随机数，然后作为明文的前缀进行加密原语的运算。

对于解密，会对上述解密出来的加上了padding的数据进行decode，从而最后拿到明文M，根据RFC 3447 7.2.2的步骤三：

rsa_padding_failed

可以发现padding不对，从而直接判断出解密失败。

xp , Feb 1 2017 , theory,distributed,tutorial,replication,erasure code

xp的分布式系统系列教程之: Erasure-Code: 工作原理, 数学解释, 实践和分析.

内容简介

Erasure-Code, 简称 EC, 也叫做 擦除码 或 纠删码, 指使用范德蒙(Vandermonde) 矩阵的里德-所罗门码(Reed-Solomon) 擦除码算法.

EC 本身是1组数据冗余和恢复的算法的统称.

本文以 Vandermonde 矩阵的 Reed-Solomon 来解释 EC 的原理.

术语定义:

$d_j$ 表示数据块.
$y_i$ 表示通过数据块计算得来的, 作为数据冗余的校验块.
$u_j$ 表示丢失的, 需要恢复的数据块.
k 表示数据块的数量.
m 表示校验块的数量.

本文内容包括:

第1节分布式系统的可靠性问题: 冗余和多副本提出EC需要解决的问题.
希望对分布式存储领域增加了解的同学, 可以只阅读 EC的基本原理部分.

这部分会用到1些中学的数学知识, 逐步用举栗子🌰的方式给出了EC算法的直观解释.

它和真正实现层面的EC原理是一致的, 但不深入到太多数学层面的内容.
已经对EC工作方式有些了解, 希望更深入了解其数学原理的读者, 可以直接从 EC编码矩阵的几何解释开始阅读.

这部分解释了EC的编码矩阵的原理和含义, 但不包括更底层数学的讨论.

伽罗华域GF(7) 和伽罗华域GF(256) 开始介绍如何将EC应用到计算机上的方法, 从这部分开始EC会用到1些抽象代数中的知识.
需要动手扣腚解决分布式存储问题的猿, 如果对数学原理不感兴趣, 但对工程实践方面有兴趣的话, 可以参考实现.
需要对存储策略规划的架构师, 可以直接参考数值分析部分分析.

分布式系统的可靠性问题: 冗余和多副本

在分布式系统中, 第1个要解决的问题是可靠性问题, 因为服务器会宕机,磁盘会掉,光纤会被挖掘机铲断, 机房会被大雨淹没. 数据存储多份才可以达到工业可用的可靠性.

一般还必须让数据的多个副本分布在不同的服务器, 机架或机房里才能真正达到高可靠.

数据可靠了之后才需要讨论数据的一致性和性能等问题. (也可能, 一致性和可靠性是并列第一的😄).

提高可靠性也很直接, 一般的解决方式就是 对一份数据存储多个副本.

副本数一般选择3:
3副本结合当前经验上的磁盘的损坏率(大约是年损坏率7%), 大约可以达到一个工业可接受的可靠性, 这个可靠性的预期大约是11个9以上(99.999999999%的概率不丢数据).

下图摘自 backblaze发布的硬盘故障率统计

如果我有2块数据(每块可能是1个1G大小的电影): $ d_1 $ 和 $ d_2 $, 为了达到高可靠性, 我需要对每个数据复制3份, 并放在不同的服务器上以保证足够分散, 数据在服务器上的保存的位置大概是酱:

$(d_1, d_1, d_1), \\ (d_2, d_2, d_2), \\ ...$

第1列的$d_1, d_2$在第1个服务器上,
第2列的$d_1, d_2$在第2个服务器上,
第3列的$d_1, d_2$在第3个服务器上.

这种3副本的策略下, 总的存储冗余度是 300%
空间浪费是200%

当然有些时候为了降低成本, 只存储2个副本, 这时冗余度是200%, 也浪费了1倍的空间:

$(d_1, d_1), \\ (d_2, d_2), \\ ...$

那么, 能否用较少的冗余, 来实现同样较高的可靠性, 就成了分布式存储的一个重要研发的方向.

这就是本文介绍的 EC 需要解决的问题. 接下来, 我们通过几个例子, 1步步介绍 EC 的原理和实现机制.

EC的基本原理

栗子🌰1: 实现k+1的冗余策略, 大概需要小学3年级的数学知识

Q: 有3个自然数, 能否做到再记录第4个数字, 让任何一个数字丢失的时候都可以将其找回?

这个问题很简单, 记录这3个数字的和: 假设3个数字是: $ d_1, d_2, d_3 $; 再存储一个数: $ y_1 = d_1 + d_2 + d_3 $.

存储的过程就是存储这4个数字: $ d_1, d_2, d_3, y_1 $:
数据丢失后要找回时:
- 这样如果 $ d_1, d_2, d_3 $ 任意一个丢失, 例如 $ d_1 $ 丢失了, 我们都可以通过 $ d_1 = y_1 - d_2 - d_3 $ 来得到 $ d_1 $.
- 如果 $ y_1 $ 丢失, 则再次取 $ d_1 + d_2 + d_3 $ 的和就可以将 $ y_1 $ 找回.

在上面这个简单的系统中, 总共存储了4份数据, 有效的数据是3份.
冗余是133%, 它的可靠性和2副本的存储策略差不多: 最多允许丢失1份数据.

看起来这是一个不错的解决方案:
我们用133%的冗余, 实现了和2副本的 200% 冗余 差不多的可靠性! 如下:

策略	冗余度	可靠性	存储策略示意
2副本	200%	允许丢1块: $ 1 \times 10^{-8} $	$ (d_1,d_1) $, $ (d_2,d_2)$, $(d_3,d_3)… $
3+1求和冗余	133%	允许丢1块: $ 6 \times 10^{-8} $	$ (d_1, d_2, d_3, y_1) $, $ (d_4, d_5, d_6, y_2)… $

这里只是差不多, 还并不是完全一样, 后面分析 1节会详细讨论可靠性的计算.
在讨论可靠性的时候, 一般数据丢失风险没有量级的差异, 就可以认为是比较接近的.

上面这个例子是和我们平时使用的 RAID-5 基本是一样的. RAID-5 通过对k个(可能是11个左右)数据块求出1份校验和的数据块. 存储这份校验块, 并允许1块(数据或校验)丢失后可以找回.

当然在工程上, RAID-5 的计算和自然数的求和还有些差异. 后面继续撩.

以上的这种求和冗余策略, 就是 EC 的核心思路.

如果你对存储感兴趣但不希望太多深入细节, 到这里差不多已经比较直观地了解 EC 的原理了.

如果你还有浓厚的兴趣继续读下去,好极!

接下来将上面的内容做些扩展, 后面章节会继续深入1点点, 逐步把上面提到的求和冗余 推广成1个生产环境可用的存储策略, 同时也会逐步引入更多的数学来完善这个策略.

栗子🌰2: 实现k+m的冗余策略, 大概需要初中2年级的数学知识

现在我们在k+1的冗余策略基础上, 增加更多的校验块, 来实现任意k+m的冗余策略.

增加1个校验块, 变成k+2

现在让我们把问题再推进1步. 上面我们通过多增加1份的冗余, 实现了和2副本差不多的可靠性(允许丢失1块数据). 那么我们如果要实现和3副本差不多的可靠性呢(允许丢失2块数据)?

Q: 有3块数据: $ d_1, d_2, d_3 $
可否另外再存储2个冗余的校验块(共5块), 让整个系统任意丢失2份数据时都能找回?

在k+1求和的策略里, 我们实际上是给所有的数据块和校验块建立了一个方程 $ d_1 + d_2 + d_3 = y_1 $, 来描述他们整体的关系.

现在, 如果要增加可丢失的数据块数, 简单的把 $ y_1 $ 存2次是不够的, 假设计算了2个校验块:

$d_1 + d_2 + d_3 = y_1 \\ d_1 + d_2 + d_3 = y_2 \\ (y_1 = y_2)$

存储的过程定义为: 存储 $ d_1, d_2, d_3, y_1, y_2 $ 这5个数字.
需要恢复数据时: 如果 $ d_1, d_2 $ 都丢失了($ u_1, u_2 $ 表示), 下面这个关于$ u_1, u_2 $的线性方程是有无穷多解的:
$\begin{cases} u_1 + u_2 + d_3 = y_1 \\ u_1 + u_2 + d_3 = y_2 \end{cases}$
我们没有办法从这个方程组里解出 $ u_1, u_2 $ 的值, 因为这2个方程是一样的, 没有提供更多的信息.

所以我们现在需要做的是, 设计一个计算第2个校验块 $ y_2 $ 的方法:
使得当 $ d_1, d_2 $丢失时方程组有解.

一个简单直接的思路是, 计算$ y_2 $ 时, 给每个数据 $ d_j $ 增加1个不同的系数:

计算$y_1$时, 对每个数字乘以1, 1, 1, 1 …
计算$y_2$时, 对每个数字乘以1, 2, 4, 8 …

$\begin{align} d_1 + d_2 + d_3 & = y_1 \\ d_1 + 2 d_2 + 4 d_3 & = y_2 \end{align}$

存储的过程任然定义为: 存储 $ d_1, d_2, d_3, y_1, y_2 $ 这5个数字.
数据恢复的时候, 如果 $ d_1, d_2 $ 丢失, 同样用 $ u_1, u_2 $表示, 我们可以使用剩下的 $ d_3, y_1, y_2 $ 来建里1个关于 $ u_1, u_2 $ 的二元一次方程组:

$\begin{cases} \begin{align} u_1 + u_2 & = y_1 - d_3 \\ u_1 + 2 u_2 & = y_2 - 4 d_3 \end{align} \end{cases}$

解出上面这个方程组, 就找回了丢失的 $ u_1, u_2 $.

感谢对我们负责的初中班主任, 把体育课帮我们改成了数学习题课, 让我们还记得这个二元一次方程组好像通过消元, 就能解出 $ u_1, u_2 $ 的值

<(￣︶￣)>

以上这种加系数计算校验块的方式, 就是RAID-6的基本工作方式:
RAID-6为k个数据块之外再多存储2个校验数据, 当整个系统丢失2块数据时, 都可以找回.

为什么计算 $ y_2 $ 的系数是1, 2, 4, 8…?
系数的选择有很多种方法, 1, 2, 4, 8是其中一个. 只要保证最终丢失2个数字构成的方程组有唯一解就可以. 这里选择1, 2, 3, 4…也可以.

到这里, 有理数下k+2的EC的算法大概就出来了, 我们可以实现k+2的冗余策略, 通过166%的冗余, 实现差不多和三副本300%一样的可靠性.

具体的可靠性计算参见下面的: 分析

实现k+m 的冗余

如果要增加更多的冗余,让EC来实现相当于4副本差不多的可靠性: k+3, 我们需要给上面的策略再增加一个校验块 $ y_3 $,

而 $ y_3 $ 的计算我们需要再为所有的 $ d_j $ 选择1组不同的系数, 例如1,3,9,27…来保证后面数据丢失时,得到的1个3元一次方程组是可解的:

$\begin{cases} \begin{align} d_1 + d_2 + d_3 & = y_1 \\ d_1 + 2 d_2 + 4 d_3 & = y_2 \\ d_1 + 3 d_2 + 9 d_3 & = y_2 \end{align} \end{cases}$

这样我们通过不断的增加不同的系数, 就可以得到任意的k+m的EC冗余存储策略的实现.

到此为止, 有理数下的EC算法就介绍完整了. 接下来的章节中, 我们会深入1点, 讨论下为什么要选择这样1组系数.

实际上,现实中使用的RAID-5和RAID-6都是 EC 的子集. EC 是更具通用性的算法. 但因为实现的成本(主要是计算的开销), RAID-5 和 RAID-6在单机的可靠性实现中还是占主流地位.

但随着存储量的不断增大, 百PB的存储已经不算是很极端场景了. RAID-6 在单机环境下不算高的数据丢失风险在大数据量的场景中显示的越来越明显. 于是在云存储(大规模存储)领域, 能支持更多的冗余校验块的EC成为了主流.

EC编码矩阵的几何解释

上面大概介绍了如何选择 EC 生成校验块(编码过程)的系数, 我们隐约可以预感到它的系数选择可能有某种内涵, 下面我们来从最初的问题入手, 讨论下为什么会得出这样1组系数选择的方法.

EC 可以这样被理解: 为了恢复几块数据, 我们需要预先通过这几块数据 $ d_j $ 另外计算出几个数值(校验块), 校验块和数据块构成1个整体, 这些校验块具备所有数据块的特征, 可以用于和其他几个数据配合起来找回丢失的数据块.

我们从比较简单的情况开始, 看下2个数据块计算(多个)EC校验块的方法:

k=2, 为2个数据块生成冗余校验块

假设现在我们有2个数据块 $ d_1, d_2 $. 要做2个校验块.

我们使用1个直线的方程, 来实现数据的冗余备份和恢复:

$y = d_1 + d_2 x$

这条直线具备这样的特点:

这条直线包含的所有数据块 $ d_j $ 的信息.

任何1对 $ d_1, d_2 $ 的值就确定一条不同的直线. 同样, 任意1条直线也唯一对应1对 $ d_1, d_2 $ 的值.

数据可靠性的问题就转化成了:

我们要保存足够多的关于这条直线的信息, 能够在需要的时候找回这条直线. 然后再提取直线方程的系数来找回最初存储的数据块 $ d_1, d_2 $.

要保存足够多的信息, 最直观的方法就是记录这条直线上的几个点的坐标.

因为2点可以确定一条直线, 只要拿到直线上2个点的坐标, 就能确定直线方程, 从而确定它的系数 $ d_1, d_2 $.

按照这样的思路, 我们重新用直线方程的方式描述数据冗余生成和数据恢复的过程:

生成冗余的校验数据的过程就是:

在直线上取2个点, 记录点的坐标(这里我们总是取x = [1, 2, 3…]的自然数的值, 所以只记录y的值就可以了)

$ d_1, d_2, (1, y_1), (2, y_2) $
恢复数据的过程就是: 已知过直线2点 $ (1, y_1), (2, y_2) $ 来确定直线方程的过程.

再次感谢初中班主任

取 x 分别为 1和2:

$\begin{cases} y_1 = d_1 + d_2 \\ y_2 = d_1 + 2d_2 \end{cases}$

我们得到了1组带冗余的数据: $ d_1, d_2, y_1, y_2 $. 这4个数据中,任意丢失2个,都可以通过等式关系 $ y = d_1 + d_2 · x $ 来恢复.

丢失1个数据块时只用 $ y_1 $ 的方程就够了.
丢失2个数据块时才需要解二元一次方程组.
如果 $ y_1 $或 $ y_2 $丢失, 则通过重新取点的方式恢复.

我们可以在直线上取任意多个点, 但恢复时最多也只需要2个点就够了. 在这个例子中我们实现了 2+m 的冗余策略.

k=3, 4, 5…时的数据块的冗余

现在我们把它再推广到更一般的情况: 直线方程只需要2个值来确定, 但如果要用描点方式来为更多的数据块生成冗余数据, 我们需要使用高次的曲线, 来记录更多的数据.

例如:

二次曲线抛物线 $ y = a x^2 + b x + c $ 需要3个值来确定, 同时也需要知道抛物线上的3个点的坐标来找回这条抛物线.

通过高次曲线生成冗余数据

如果有k个数据块, 我们把k个数据作为系数, 来定义1条关于x的高次曲线:

$y = d_1 + d_2 x + d_3 x^2 + ... + d_k x^{k-1}$

生成m个冗余数据的过程就是:

取m个不同的x的值(1, 2, 3…m), 记录这条曲线上m个不同点的坐标:
$(1, y_1), (2, y_2) ... (m, y_m)$
存储所有的数据块 $ d_1, d_2…d_k $ 和所有的校验块 $ y_1, y_2…y_m $.
恢复数据:

当数据丢失时, 我们知道, 平面直角坐标系上m个点可以唯一确定1条 m-1 次幂的关于x的曲线. 确定了这条关于x的曲线,就找回了它的系数,也就是数据块 $ d_1, d_2 … d_k $

以上就是 EC 的算法的几何解释: 通过曲线上的点来确定曲线的过程.

从曲线方程得到的系数矩阵

在曲线方程上取点的坐标的过程中, 我们直接为x取自然数的位置来计算 y 的值: 1, 2, 3…:

$y_1 = d_1 + d_2 · 1 + d_3 · 1^2 + .. + d_k · 1^{k-1} \\ y_2 = d_1 + d_2 · 2 + d_3 · 2^2 + .. + d_k · 2^{k-1} \\ y_3 = d_1 + d_2 · 3 + d_3 · 3^2 + .. + d_k · 3^{k-1} \\ ... \\$

把上面等式写成矩阵的形式, 得到EC校验块的 生成矩阵 Generator-Matrix:

$\begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ ... \\ y_m \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1^2 & ... & 1^{k-1} \\ 1 & 2 & 2^2 & ... & 2^{k-1} \\ 1 & 3 & 3^2 & ... & 3^{k-1} \\ ... & ... & ... & ... & ... \\ 1 & m & m^2 & ... & m^{k-1} \end{bmatrix} \times \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ ... \\ d_k \end{bmatrix}$

这里 $ y_1, y_2 … y_m $ 就是校验块的数据, 矩阵里就是我们上面使用的这样那组系数.

这个矩阵就是著名的 Vandermonde 矩阵.

Vandermonde 矩阵只是 EC 其中1种系数的选择方式. 其他常用的系数矩阵还有 Cauchy 矩阵等.

EC解码过程: 求解n元一次方程组

现在我们知道, EC 就是:

有1组数字: $d_1, d_2, d_3...d_k$ 另外记录m个校验用的数字 $y_1, y_2, y_3...y_m$ 使得这k+m个数字中任意丢失m个都能从剩下的k个中恢复所有的k+m个数字.

EC生成校验块的过程称之为EC的编码, 当数据丢失需要找回的时候, 使用的是EC的解码过程.

如上面章节所说, EC的编码过程是编码矩阵(Vandermonde)和数据块列相乘:

$\begin{bmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & 2 & 4 & ... & 2^{k-1} \\ 1 & 3 & 9 & ... & 3^{k-1} \\ ... \\ 1 & m & m^1 & ... & m^{k-1} \end{bmatrix} \times \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ ... \\ d_k \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ ... \\ y_m \end{bmatrix}$

解码的过程如下:

假设有q个数字丢失了, $ q \le m $. 从上面的编码矩阵中选择 $ y_1, y_2..y_q $, q行, 组成的一次方程组, 求解丢失的数据.

例如 $ d_2, d_3 $ 丢失了, 下面用 $ u_2, u_3 $ 表示 (只丢失了2块数据, 不需要所有的m个校验块参与, 只需要2个校验块来恢复数据)

$\begin{bmatrix} 1 & 2 & 4 & ... & 2^{k-1} \\ 1 & 3 & 9 & ... & 3^{k-1} \\ \end{bmatrix} \times \begin{bmatrix} d_1 \\ u_2 \\ u_3 \\ ... \\ d_k \end{bmatrix} = \begin{bmatrix} y_2 \\ y_3 \\ \end{bmatrix}$

这个矩阵表示的方程组里有2个未知数 $ u_2, u_3 $, 解方程即可得到 $ u_2, u_3 $ 这2块丢失的数据.

Vandermonde 矩阵保证方程组有解

对于k+m的EC来说, 任意丢失m个数据块都可以将其找回.

Vandermonde 矩阵保证了任意m行m列组成的子矩阵都是线性无关的, 构成的方程肯定有确定解.

$V=\begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1} \\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1} \\ 1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1} \end{bmatrix}$

Vandermonde 的行列式的值为:

$\det(V)=\prod_{1 \leq i \lt j \leq n}(\alpha_j - \alpha_i)$

只要 $ \alpha_i $ 都不同, 则 Vandermonde 矩阵的行列式就不为0, 矩阵可逆, 表示方程有唯一解.

容易证明, Vandermonde 矩阵的任意 $ m \times m $的子矩阵也可以保证永远有唯一解.

到此为止我们讨论了EC在有理数范围内的全部内容. 它是完整的, 但还不能直接应用到计算机的代码开发商.

接下来我们要展开在纯数学和计算机算法之间的问题, 以及我们将通过什么样的手段来解决这些问题, 将EC真正应用到生产环境中.

新世界: 伽罗华域 Galois-Field GF(7)

在实际使用中, 并不像上面的有理数计算那么简单: 就像所有算法在实现中多会面临的问题一样, 在计算机上实现, 必须考虑空间问题. 计算机里不能天然的表示任意自然数, 上面的校验块 $ y_i $ 在计算过程中必然会出现越界问题.

$y = d_1 + d_2 x + d_3 x^2 + ... + d_k x^{k-1}$

如果我们的数据块 $ d_j $ 的取值范围是1个字节大小, 那么计算出来的校验数据 $ y_i $ 随着x的值的选取, 很可能就超出了1个字节大小, 如果仍然使用这种方式生成校验块, 最终冗余的数据的大小就会变得不可控, 实际存储的冗余会大于 k+m : k 的冗余度, 无法达到有效控制冗余数据大小的目的.

因此上面介绍的EC, 在计算机上实现时, 必须解决数字大小的问题. 但总的算法是不变的. 这次我们要从最底层开始入手, 解决这个问题.

这里所说的最底层, 是指曲线, 多元一次方程等依赖的底层的四则运算法则. 我们将找到另外一套四则运算, 既能满足 EC 计算的需要, 又能很好第控制数值的范围. 我们要将 EC 移植到另一套代数结构上.

这也是我自己在学习 EC 时觉得最有趣的地方:

类似于把一段c代码写好后可以编译到intel CPU上也可以编译到ARM CPU上运行(即使这2种CPU的指令完全不同, 但c源代码的正确性是不变的),

现在我们要做的是, 我们设计好 EC 的上层算法后, 把它移植到另1套代数体系中, 而同时也能保证它上层的”源代码” 在另1种不同的底层体系上也可以正确运行!

EC在计算机里的实现: 基于伽罗华域 Galois-Field

上面我们提到的几个数学公式, 高次曲线, 多元一次方程组等: $ y = d_1 + d_2 x + d_3 x^2 + … + d_k x^{k-1} $

他们之所以能正确的工作, 是因为他们依赖于一套底层的基础运算规则, 这就是四则运算: $ + - \times \div $ (实现 EC 的代数中我们没有用到开方运算).

这听起来有点废话, ™不用四则运算用什么?

其实我们平时熟知的四则运算, 在代数里并不是唯一的四则运算法则, 它有很多很多个兄弟, 他们有共同的规律,却有着不同的表现形式.

例如在有1种四则运算建立的代数可能是: $ 5 + 5 = 3 $ 而不是10, $ 5 \times 3 = 1 $ 而不是15. 也可能有1种四则运算里乘法不是加法的叠加.

最常见的是钟表的时间相加, 20点加8个小时不是28点, 而是4点.

我们现在需要做的是, 找到一种四则运算, 来让 EC 的计算可以不会越界!

现在我们来一步步开启这扇新世界的大门…

首先感谢19世纪因为跟情敌决斗被一枪打死的伟大数学家伽罗华.

栗子🌰3: 只有7个数字的新世界: GF(7)

大门, 慢慢开启…

我们来尝试定义一个新的加法规则, 在这个新的世界里只有0~6这7个数字:

其他整数进来时都要被模7, 变成0~6的数字.

在这个模7的新世界里, 四则运算也可以工作:

模7新世界中的加法

我们来尝试定义一个新的加法规则, 在这个只有0~6这7个数字的新世界里, (新的加法被表示为 ⊕ (这里原始的加法还是用+来表示)):

$a ⊕ b \rightarrow (a + b) \pmod 7$

它定义为: a ⊕ b的结果是 a + b后结果再对7取模. 例如:

1 ⊕ 1 = 2
5 ⊕ 2 = 0 ( 7 % 7 = 0 )
5 ⊕ 5 = 3 ( 10 % 7 = 3 )

在这个新世界里, 0 还是和以前的0很相像, 任何数跟0相加都不变:

0 ⊕ 3 = 3
2 ⊕ 0 = 2

0 在新世界 GF(7) 里被称为加法的单位元.

模7新世界中的减法

然后我们再在模7的世界里定义减法. 减法的定义也很直接, 就是加法的逆运算了.

就像自然数里1样, -2 + 2 = 0, 我们称呼-2是2在加法上的逆元(通常称为相反数). 在模7的世界里,我们也很容易找到每个数的加法逆元,例如: $ 3 ⊕ 4 = 0 $ 所以 4 和 3 就互为加法的逆元, 或者说是(新世界的)相反数.

减法定义就是: $ a ⊖ b \rightarrow a ⊕ (-b) $.

例如:

3 ⊖ 4 = 6 ( (-1) % 7 = 6 )
2 ⊖ 6 = 3 ( (-4) % 7 = 3 )

其实我们不需要减法, 我们只需要加法和逆元的定义

模7新世界中的乘法和除法

在模7的新世界里, 我们也可以类似地定义1个乘法:

$\begin{equation} a ⊗ b \rightarrow (a \times b) \mod 7 \end{equation}$

例如:

1 ⊗ 5 = 5 ( 5 % 7 = 5 )
3 ⊗ 4 = 5 ( 12 % 7 = 5 )
2 ⊗ 5 = 3 ( 10 % 7 = 3 )
0 ⊗ 6 = 0

对于模7新世界的乘法⊗来说, 1 是乘法的单位元, 也就是说1 ⊗ 任何数都是它本身.

我们也可以用类似的方法定义每个数字在乘法⊗的逆元:

$a的乘法逆元a^{-1}是b, 如果 a ⊗ b = 1$

例如:

$\begin{align} 3^{-1} & = 5 ( 3 \times 5 \% 7 = 1 ) \\ 4^{-1} & = 2 ( 4 \times 2 \% 7 = 1 ) \end{align}$

除法的定义就是: 乘以它的乘法逆元

栗子🌰4: 模7新世界直线方程-1

现在我们有了新的加法和减法⊕, ⊖ 我们可以像使用旧世界的加减法一样来使用⊕, ⊖. 例如我们可以建立一个简单的, 斜率为1的直线方程:

$y = x ⊕ 3$

新世界里这个直线上的点是: (x,y) ∈ [(0,3), (1,4), (2,5), (3,6), (4,0), (5,1), (6,2)] 只有7个.

如果把这条直线画到坐标系里, 它应该是这个样子的:

y = x ⊕ 3

  y
  ^
|     •
|   •
| •
•
|           •
|         •
+-------•-----> x
1 2 3 4 5 6 

栗子🌰5: 模7新世界直线方程-2

再加上新世界加减乘除四则运算, 我们可以在新世界里进行基本的代数运算了, 例如我们可以设定1个斜率为2的直线方程:

$y = 2 ⊗ x ⊕ 3$

新世界里这个直线上的点是: (x,y) ∈ [(0,3), (1,5), (2,0), (3,2), (4,4), (5,6), (6,1)] 这7个.

如果把这条直线画到坐标系里, 它应该是这个样子的:

y = 2 ⊗ x ⊕ 3

  y
  ^
|          •
| •
|       •
•
|     •
|           •
+---•---------> x
1 2 3 4 5 6 

栗子🌰6: 模7新世界中的二次曲线方程

下面我们来建立1个稍微复杂1点的, 二次曲线的方程:

$y = x^2 ⊕ x ⊕ 2$

这里 $ x^2 $ 表示 $ x ⊗ x $

新世界里这个抛物线上的点集合是: (x,y) ∈ [(0, 2) (1, 4) (2, 1) (3, 0) (4, 1) (5, 4) (6, 2)]

如果把这条抛物线画到坐标系里, 它应该是这个样子的:

y = x^2 ⊕ x ⊕ 2

  y
  ^
|
|
| •       •
|
•           •
|   •   •
+-----•-------> x
1 2 3 4 5 6

可以看出它的图像也遵循了旧世界抛物线的特性: 这条抛物线是以3为轴对称的: 因为类似旧世界的多项式分解一样, 原方程也可以分解成:

$\begin{align} y & = (x ⊕ (-3))^2 \\ & = x^2 ⊕ (-6)x ⊕ 9 \\ & = x^2 ⊕ x ⊕ 2 \end{align}$

模7新世界里的EC

在这个模7的新世界里, 它满足我们旧世界里的四则运算法则, 我们已经可以使用上面提到的 EC 的算法来编码或解码了:

假设模7新世界里我们的数据块 $ d_1 = 3, d_2 = 2 $, 对应上面的直线方程: y = 2 ⊗ x ⊕ 3

我们只要记住2个点的位置, 就能把直线的方程恢复出来:

例如:

我们先记录直线上2个点: (1,5) 和 (3,2)
假设丢失的数据是 $ d_1, d_2 $ 用 $ u_1, u_2 $ 表示, 带入2个点的坐标, 得到一个二元一次方程组:
$\begin{cases} \begin{align} 5 & = u_2 ⊕ u_1 \\ 2 & = u_2 ⊗ 3 ⊕ u_1 \end{align} \end{cases}$
2个方程左右分别相减消元:
$\begin{align} 5 ⊕ (-2) & = u_2 ⊗ (1 ⊕ (-3)) ⊕ u_1 ⊕ (-u_1) \\ 5 ⊕ 5 & = u_2 ⊗ (1 ⊕ 4) \\ 3 & = u_2 ⊗ 5 \end{align}$
最后得到 $ u_2 = 3 ⊗ 5^{-1} = 3 ⊗ 3 = 2 $.

将$ u_2 = 2 $ 带入第1个方程:
$5 = 2 ⊗ 1 ⊕ u_1$
得到 $ u_1 $:
$u_1 = 5 ⊕ (-2) = 3$

至此, 我们用模7新世界的四则运算实现了之前的 EC . 并且我们保证了校验数据的大小是可控的: 不会大于7! 距离我们的目标又接近了1步.

类似的, 我们可以通过模7新世界的抛物线, 来实现k=3, k=4的 EC.

NOTE:
模7下的四则运算构成了1个伽罗华域 Galois-Field: $ GF(7) $.

模7是1个可选的数, 也可以选择模11或其他质数来构造1个 Galois-Field, 但是不能选择模一个合数来建立新的四则运算规则. 假设使用模6, 模6世界里面的2是6的一个因子, 它没有乘法逆元, 也即是说2 乘以 1~5任何一个数在模6的世界里都不是1.

没有乘法逆元就说明模6的世界里没有和旧世界里一样的除法, 不能构成一个完整的四则运算体系.

NOTE:
为了简化本文, 四则里还有几个方面没有提到, 例如乘法加法的分配率. 乘法和加法的结合律也必须满足, 才能在新世界里实现上面例子中的曲线方程等元素. 这部分也很容验证,在上面的模7新世界里是可以满足的.

现在我们有了 EC 的算法, 以及很多个可以选择的四则运算来限定数值的范围. 接下来要在计算机上实现,还有1步,就是: 模7虽然可取,但是它没有办法对计算机里的数字有效利用,因为计算机里的数是二进制的. 如果把数值限定到7或其他质数上,没有办法实现256或65536这样的区间的有效利用.

所以接下来我们需要在所有四则运算里选择一个符合计算机的二进制的四则运算, 作为实现 EC 计算的基础代数结构.

EC使用的新世界 Galois-Field GF(256)

从现在开始, 我们要构造一个现实中真实可以用的伽罗华域, 它比上面模7新世界稍微复杂一点, 得到这个域分为2步:

我们首先选择1个基础的, 只包含2个元素的 Galois-Field $ GF(2) $: {0, 1}.
再在这个 $ GF(2) $ 的基础上建立1个有256个元素的 Galois-Field $ GF(2^8) $.

模2的新世界: Galois-Field GF(2)

首先我们要构建一个最基础的四则运算, 我们先选择了最小的1个Galois-Field, 里面只有2个元素{0,1}:

在这个GF(2)里, 运算的规则也非常简单:

加法(刚好和位运算的异或等价):

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

1的加法逆元就是1 本身.
乘法(刚好和位运算的与等价):

0 ⊗ 0 = 0
0 ⊗ 1 = 0
1 ⊗ 0 = 0
1 ⊗ 1 = 1

1的乘法逆元就是1 本身. 0 没有乘法逆元.

以这个GF(2)为基础, 我们已经可以构建一个1-bit的 EC 算法了:)

下一步我们希望构建1个1 byte大小($ 2^8 $ 个元素)的 Galois-Field $ GF(2^8) $, 在这个 $ GF(2^8) $ 里的 EC 中, 的每个$ d_j $ 和 $ y_i $的取值范围可以是0~255.

有点类似于把0~9这10个自然数通过增加进位这个概念后扩展成能表示任意大小的多位的10进制自然数, 我们通过类似的方法把{0,1}这个$ GF(2) $ 扩大, 引入多项式:

我们使用 GF(2) 的元素作为系数, 定义1个多项式:

$a_n x^n + ... + a_2 x^2 + a_1 x^1 + a_0 \\ a_i \in GF(2) = \{0,1\}$

$ a_i $ 的四则运算还是遵循 GF(2) 的规则的, 而多项式的四则运算,基于它的系数的四则运算建立:

例如多项式的加法:

因为 1 + 1 = 0, 所以:
$(x + 1) + (1) = x$
x的同指数幂的系数相加遵循系数的Field的加法规则, 1 + 1 = 0:
$(x^2 + x + 1) + (x) = x^2 + 1$
2个相同的多项式相加肯定是0:
$(x^2 + x + 1) + (x^2 + x + 1) = 0$

多项式的乘法和旧世界的多项式乘法类似, 仍然是通过乘法的分配率展开多项式:

$\begin{align} (x + 1) (x + 1) & = x (x+1) + (x+1) \\ & = x^2 + x + x + 1 \\ & = x^2 + 1 \end{align}$

多项式的除法依旧使用旧世界的多项式长除法法则, 唯一不同仍旧是系数的四则运算是基于GF(2)的:

例如:

$\begin{align} \frac{x^3 + 1}{x + 1} = x^2 + x + 1 \end{align}$

多项式的除法的取余计算也类似:

$x^2 + x + 1 = x (x+1) + 1 \\ (x^2 + x + 1) = 1 \pmod (x+1)$

现在我们通过把 GF(2) 应用到多项式的系数上, 得到了1个包含无限多个元素的多项式的集合 (它还不是一个伽罗华域, 因为缺少除法逆元. 就像整数全集也不是一个伽罗华域, 它也缺少除法逆元),

然后我们还发现, 这些多项式和二进制数是有一一对应关系的, 多项式中指数为i的项的系数就是二进制数第i位的值:

$\begin{align} 1 & \rightarrow 1 \\ x^2 + 1 & \rightarrow 101 \\ x^3 + x & \rightarrow 1010 \end{align}$

现在我们可以使用多项式表达的二进制整数的全集. 然后就像上面栗子中的 GF(7) 那样, 通过取模的方式, 将多项式的集合构造1个取模的伽罗华域.

类似的, 现在我们需要找到1个质的多项式(Prime-Polynomial), 来替代GF(7)中7的角色, 并应用到GF(2)为系数的多项式的集合中, 最终得到1个有256个元素的多项式的伽罗华域 $ GF(2^8) $.

首先让我们来熟悉下如何从较小的域扩张到较大的域.

域的扩张 Field-Extension

域的扩张大家应该是非常熟悉的, 只是一般并没有用这个专用的称呼去描述我们平时见到的扩展.

域的扩张经常是通过多项式来完成的.

栗子🌰7: 实数到虚数的扩张

例如我们首先有了实数, 以实数为系数的多项式中, 如果我们选择一个多项式来构造一个方程:

$\begin{equation} x^2 + 1 = 0 \end{equation}$

这个方程在实数域里是无解的, 但在复数范围内是有解的: $ x = \pm \sqrt{-1} = \pm i $.

这样通过一个实数系数的, 但在实数域中没有根的方程, 我们得到了复数 Complex-Number 的定义,

复数就是: 所有实系数多项式模 $ x^2+1 $ 的余多项式的集合:

$\mathbb {C} =\mathbb {R} [X]/(X^{2}+1).$

上面所有的余多项式可以表示为: $ a x + b $, a, b都是实数.

这里$ a x + b $ 就是我们熟悉的复数: 多项式 x 对应虚数单位i, 1对应实数单位1.

而任意2个多项式的四则运算, 也对应复数的四则运算, 例如, 设: $ p(x) = x^2 + 1 $

多项式($\pmod{p(x)}$)	复数
$ x + (x+1) = 2x+1 $	$ i + (1+i) = 1+2i $
$ x · x = -1 $	$ i · i = -1 $
$ (3x+1)·(x-2) = -5x-5 $	$ (1+3i)·(-2+i) = -5-5i $

类似于将实数扩张到复数, 我们也可以将GF(2) 扩张到 $ GF(2^8) $.

从2到256: 扩张 GF(2)

域的扩张就是在现有域为系数的多项式中, 找到1个质的多项式 Prime-Polynomial, 再将所有多项式模它得到的结果的集合就是域的扩张.

例如 $ x^2 + 1 $ 在实数域下就是 质多项式, 它无法分解成2个多项式乘积.

栗子🌰8: GF(2) 下的质多项式

1 是1个质多项式.
$ x + 1 $ 是1个质多项式. 因为它最高次幂是1, 肯定不能再拆分成2个多项式乘积了(只能拆分成1次多项式和常数的乘积).
2次的质多项式是: $ P_2(x) = x^2 + x + 1 $. 它在GF(2)的域中不能被拆分成2个1次多项式的乘积.

我们可以像使用7对所有整数取模那样, 用它对所有多项式取模, 模它而产生的所有 余多项式, 包含所有最高次幂小于2的4个多项式: $ 0, 1, x, (x + 1) $

这4个多项式就是 GF(2) 在多项式 $P_2(x)$ 的扩张: 我们把{0, 1} 2个元素的域扩张成 4个元素的域.

这4个多项式可以表示成4个2bit的二进制数:00,01,10,11

GF(2) 扩张成 GF(2^8)

为了扩张到 $ GF(2^8) $ 我们选择的8次幂的质多项式是:

$P_8(x) = x^8 + x^4 + x^3 + x + 1$

这个8次幂的质多项式,模它的所有余多项式,是所有最高次幂不超过7的多项式, 共256个, 它就是 GF(2) 到 GF(256) 的扩张, 扩张后的元素对应0~255这256个二进制数.

因为多项式和二进制数的直接对应关系, $ P_8(x) $ 对应:

二进制: 1 0001 1011
16进制: 0x11b

而GF(256)中的四则运算如下:

加法: $ a ⊕ b $ 对应多项式加法, 同时它表示的二进制数的加法对应: a ^ b
乘法: $ a ⊗ b $ 对应多项式的乘法(模$P_8(x)$):

总结一下GF(256)能够满足EC运算的几个性质:

加法单位元: 0
乘法单位元: 1
每个元素对加法都有逆元(可以实现减法): 逆元就是它本身( (x+1) + (x+1) = 0 )
每个元素对乘法都有逆元(除了0)(可以实现除法):$P_8(x)$是不可约的, 因此不存在a和b都不是0但ab=0; 又因为GF(256)只有255个非0元素, 因此对a,总能找到1个x使得 $ a^x = a $. 所以 $a^{x-2} a = 1$ $ a^{x-2} $是a的乘法逆元.
乘法和加法满足分配率: 基于多项式乘法和加法的定义.

满足这些性质的四则运算, 就可以用来建立高次曲线, 进而在GF(256)上实现EC.

实现

标准EC的实现

以上讨论的是标准的EC的原理, 现在我们将以上的内容总结, 应用到实践上面.

四则运算基于 $ GF(2^8) $ 或 $ GF(2^{16}), GF(2^{32}) $, 分别对应1字节, 2字节或4字节.
$ GF(2^8) $ 下的加减法直接用异或计算, 不需要其他的工作.

$ GF(2^8) $ 下的乘法和除法用查表的方式实现.

首先生成 $ GF(2^8) $ 下对2的指数表和对数表, 然后把乘除法转换成取对数和取幂的操作:

以 $ GF(2^8) $ 为例:

生成指数表 $ 2^0, 2^1, 2^2… $的表, 表中元素 $ p_i = 2^i $.
生成对数表, 表中元素 $ l_i = log_2i $.

生成2个表的代码很简单, 用python表示如下:

power, log = [0] * 256, [0] * 256
n = 1
for i in range(0, 256):

    power[i] = n
    log[n] = i

    n *= 2

    # modular by the prime polynomial: P_8(x) = x^8 + x^4 + x^3 + x + 1
    if n >= 256:
        n = n ^ 0x11b

log[1] = 0 # log[1] is 255, but it should be 0

指数表:
01 02 04 08 10 20 40 80 1d 3a 74 e8 cd 87 13 26
4c 98 2d 5a b4 75 ea c9 8f 03 06 0c 18 30 60 c0
9d 27 4e 9c 25 4a 94 35 6a d4 b5 77 ee c1 9f 23
46 8c 05 0a 14 28 50 a0 5d ba 69 d2 b9 6f de a1
5f be 61 c2 99 2f 5e bc 65 ca 89 0f 1e 3c 78 f0
fd e7 d3 bb 6b d6 b1 7f fe e1 df a3 5b b6 71 e2
d9 af 43 86 11 22 44 88 0d 1a 34 68 d0 bd 67 ce
81 1f 3e 7c f8 ed c7 93 3b 76 ec c5 97 33 66 cc
85 17 2e 5c b8 6d da a9 4f 9e 21 42 84 15 2a 54
a8 4d 9a 29 52 a4 55 aa 49 92 39 72 e4 d5 b7 73
e6 d1 bf 63 c6 91 3f 7e fc e5 d7 b3 7b f6 f1 ff
e3 db ab 4b 96 31 62 c4 95 37 6e dc a5 57 ae 41
82 19 32 64 c8 8d 07 0e 1c 38 70 e0 dd a7 53 a6
51 a2 59 b2 79 f2 f9 ef c3 9b 2b 56 ac 45 8a 09
12 24 48 90 3d 7a f4 f5 f7 f3 fb eb cb 8b 0b 16
2c 58 b0 7d fa e9 cf 83 1b 36 6c d8 ad 47 8e 01

对数表(0没有以2为底的对数):
00 00 01 19 02 32 1a c6 03 df 33 ee 1b 68 c7 4b
04 64 e0 0e 34 8d ef 81 1c c1 69 f8 c8 08 4c 71
05 8a 65 2f e1 24 0f 21 35 93 8e da f0 12 82 45
1d b5 c2 7d 6a 27 f9 b9 c9 9a 09 78 4d e4 72 a6
06 bf 8b 62 66 dd 30 fd e2 98 25 b3 10 91 22 88
36 d0 94 ce 8f 96 db bd f1 d2 13 5c 83 38 46 40
1e 42 b6 a3 c3 48 7e 6e 6b 3a 28 54 fa 85 ba 3d
ca 5e 9b 9f 0a 15 79 2b 4e d4 e5 ac 73 f3 a7 57
07 70 c0 f7 8c 80 63 0d 67 4a de ed 31 c5 fe 18
e3 a5 99 77 26 b8 b4 7c 11 44 92 d9 23 20 89 2e
37 3f d1 5b 95 bc cf cd 90 87 97 b2 dc fc be 61
f2 56 d3 ab 14 2a 5d 9e 84 3c 39 53 47 6d 41 a2
1f 2d 43 d8 b7 7b a4 76 c4 17 49 ec 7f 0c 6f f6
6c a1 3b 52 29 9d 55 aa fb 60 86 b1 bb cc 3e 5a
cb 59 5f b0 9c a9 a0 51 0b f5 16 eb 7a 75 2c d7
4f ae d5 e9 e6 e7 ad e8 74 d6 f4 ea a8 50 58 af

在计算 $ GF(2^8) $中的乘法将 a, b 通过查对数表和指数表实现: $ a \times b = 2^{log_2a+log_2b} $.

NOTE:
Galois-Field 的计算目前实现都是基于查表的, 所以选择大的域虽然可以一次计算多个字节, 但内存中随机访问一个大表也可能会造成cache miss太多而影响性能.

一般CPU都没有支持GF乘除法的指令, 但有些专用的硬件卡专门加速GF的乘除法.

生成GF后, 选择一个系数矩阵, 常用的是 Vandermonde 或 Cauchy.

EC编码: 校验数据生成

通常使用1个矩阵来表示输入和输出的关系 (而不是像上文中只使用校验块的生成矩阵), 这里选择自然数生成的 Vandermonde 矩阵:

$\begin{bmatrix} 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ \hline \\ 1 & 1 & 1 & \dots & 1 \\ 1 & 2 & 2^2 & \dots & 2^{k-1} \\ 1 & 3 & 3^2 & \dots & 3^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & m & m^2 & \dots & m^{k-1} \end{bmatrix} \times \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ ... \\ d_k \end{bmatrix} = \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ ... \\ d_k \\ y_1 \\ y_2 \\ y_3 \\ ... \\ y_m \end{bmatrix}$

这个矩阵里上面是1个大小为k的单位矩阵, 表示 $ d_j $ 的输入和输出不变.

下面一部分是1个 $ m \times k $ 的矩阵表示校验块的计算.

对要存储的k组数据, 逐字节读入, 形成 $ d_1, d_2…d_k $, 进行矩阵乘法运算, 得到最后要存储的 k 个数据块和 m 个校验块.

之所以把单位矩阵也放到编码矩阵上面, 看起来没有什么用, 只是把输入无变化的输出出来的这种风格, 原因在于在编码理论中, 并不是所有的生成的Code都是k个原始数据和 m个校验数据的形式, 有些编码算法是将k个输入变成完全不1样的k+m个输出, 对这类编码算法, 需要1个k*(k+m)的编码矩阵来表示全部的转换过程. 例如著名的 Hamming-7-4 编码的编码矩阵(输入k=4, 输出k+m=7):
$\begin{pmatrix} 1&1&0&1\\ 1&0&1&1\\ 1&0&0&0\\ 0&1&1&1\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ \end{pmatrix}$
EC中也使用了k*(k+m)的编码矩阵.

EC解码

当数据损坏时, 通过生成解码矩阵来恢复数据:

对所有丢失的数据, 将它对应的第i行从编码矩阵中移除, 移除后, 保留编码矩阵的前k行, 构成1个k*k的矩阵.

例如第 2, 3个数据块丢失, 移除第2, 3行, 保留第k+1和k+2行: 这时矩阵, 数据块(没丢失的和丢失的), 没丢失的数据块($ d_1, d_4, d_5… $), 校验块($ y_1, y_2 $)的关系是:

$\begin{bmatrix} 1 & 0 & 0 & 0 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 \\ 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & 2 & 2^2 & 2^3 & \dots & 2^{k-1} \\ \end{bmatrix} \times \begin{bmatrix} d_1 \\ u_2 \\ u_3 \\ d_4 \\ ... \\ d_k \end{bmatrix} = \begin{bmatrix} d_1 \\ d_4 \\ ... \\ d_k \\ y_1 \\ y_2 \\ \end{bmatrix}$

最后求逆矩阵, 和没有丢失的块相乘, 就可以恢复出丢失的数据块 $ u_2, u_3 $:

$\begin{bmatrix} d_1 \\ u_2 \\ u_3 \\ d_4 \\ ... \\ d_k \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 \\ 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & 2 & 2^2 & 2^3 & \dots & 2^{k-1} \\ \end{bmatrix}^{-1} \times \begin{bmatrix} d_1 \\ d_4 \\ ... \\ d_k \\ y_1 \\ y_2 \\ \end{bmatrix}$

因为只有 $ u_2, u_3 $ 丢失了, 矩阵相乘时只需要计算逆矩阵的第2, 3行.

Vandermonde 矩阵的可逆性

实数下的Vandermonde 矩阵是一定可逆的, 但它的任意n行n列组成的子矩阵不一定是可逆的.

假设一个 Vandermonde 矩阵, 如果存在一个 $ [ a_1, a_2, a_3 ] $, 使得乘积为全0, 则矩阵n列是线性相关的:

$\begin{bmatrix} 1 & 1 & 1 \\ 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \\ \end{bmatrix} \times \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}$

因为方程: $ a_1 + a_2 x + a_3 x^2 = 0 $ 最多只有2个解, 但原矩阵要求有3个不同的值 $ 1, x_1, x_2 $ 满足这个方程. 因此不存在这一的 $ a_i $ 使得 Vandermonde 矩阵线性相关.

但如果查看一个 Vandermonde 矩阵的子矩阵($ 0 < u < v $):

$\begin{bmatrix} 1 & 1 & 1 \\ 1 & x_1^u & x_1^v \\ 1 & x_2^u & x_2^v \\ \end{bmatrix} \times \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}$

因为方程: $ a_1 + a_2 x^u + a_3 x^v = 0 $ 最多有v个解, 只要v 大于2, 就可能找到一组 $ a_i $ 和 $ x_i $, 使得上面的子矩阵线性相关.

例如, 一个子矩阵, x=-1 时, 矩阵不可逆:

$\begin{bmatrix} 1 & 1 \\ 1 & x^2 \\ \end{bmatrix}$

GF256 下的 Vandermonde 矩阵的可逆性

在 $ GF(2^8) $ 下的 Vandermonde 矩阵, 除了上面的的不可逆情况外, 还有另外一种情况导致子矩阵不可逆.

举例来说, 以下矩阵是缺失 $ u_1, u_4 $ 情况下的用来恢复数据的矩阵, 它可能不可逆: 如果 $ x^3 == 1 $,

由于2是1个生成元, 容易看出, $ x = 2^{85} $ 是1个不可逆的情况: $ x^3 = 1 $ 于是第1列和第4列完全一样.

$\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & x & x^2 & x^3 & x^4 \\ \end{bmatrix}$

Cauchy 矩阵的任意n行n列组成的矩阵都是可逆的, 因为任意子矩阵还是 Cauchy矩阵.

数据恢复IO优化: LRC: [Local-Reconstruction-Code]

当 EC 进行数据恢复的时候, 需要k个块参与数据恢复, 直观上, 每个数据块损坏都需要k倍的IO消耗.

为了缓解这个问题, 一种略微提高冗余度, 但可以大大降低恢复IO的算法被提出: [Local-Reconstruction-Code], 简称 LRC.

LRC的思路很简单, 在原来的 EC 的基础上, 对所有的数据块分组对每组在做1次 $ k’ + 1 $ 的 EC. k’ 是二次分组的每组的数据块的数量.

LRC 的校验块生成

$\begin{align} \overbrace{d_1 + d_2 + d_3}^{y_{1,1}} + \overbrace{d_4 + d_5 + d_6}^{y_{1,2}} & = y_1 \\ d_1 + 2d_2 + 2^2d_3 + 2^3d_4 + 2^4d_5 + 2^5d_6 & = y_2 \\ d_1 + 3d_2 + 3^2d_3 + 3^3d_4 + 3^4d_5 + 3^5d_6 & = y_3 \end{align}$

最终保存的块是所有的数据块: $ d_1, d_2, d_3, d_4, d_5, d_6 $, 和校验块 $ y_{1,1}, y_{1,2}, y_2, y_3 $.

这里不需要保存 $ y_1 $ 因为 $ y_1 = y_{1,1} + y_{1,2} $

对于 LRC的EC来说, 它的生成矩阵前k行不变, 去掉了标准EC的第k+1行, 多出2个局部的校验行:

$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \hline \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ \hline \\ 1 & 2 & 2^2 & 2^3 & 2^4 & 2^5 \\ 1 & 3 & 3^2 & 3^3 & 3^4 & 3^5 \\ \end{bmatrix} \times \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ d_5 \\ d_6 \end{bmatrix} = \begin{bmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ d_5 \\ d_6 \\ y_{1,1} \\ y_{1,2} \\ y_2 \\ y_3 \\ \end{bmatrix}$

LRC 的数据恢复

LRC 的数据恢复和标准的EC类似, 除了2点不同:

在选择校验块的行生成解码矩阵的时候, 如果某第k+i行没有覆盖到任何损坏的数据的话, 是无法提供有效性信息, 需要跳过的.

例如 $ d_4 $ 损坏时, 不能像标准EC那样选择第7行 1 1 1 0 0 0 这行作为补充的校验行生成解码矩阵, 必须略过第7行, 使用第8行.
不是所有的情况下, m个数据损坏都可以通过加入m个校验行来恢复. 因为LRC的生成矩阵没有遵循 Vandermonde 矩阵的规则, 不能保证任意k行都是满秩的.

工程优化

插播一条广告: 徐同学的博客中给出了很好的EC工程实现的介绍, 推荐!: 实现高性能纠删码引擎

分析

可靠性分析

在可靠性方面, 假设 EC 的配置是k个数据块, m个校验块. 根据 EC 的定义,k+m个块中, 任意丢失m个都可以将其找回. 这个 EC 组的丢失数据的风险就是丢失m+1个块或更多的风险:

$\sum_{i=m+1}^{k+m} {k+m \choose i} p^{i} (1-p)^{k+m-i}$

这里p是单块数据丢失的风险,一般选择磁盘的日损坏率: 大约是0.0001. p一般很小所以近似就只看第1项:

${k+m \choose m+1} p^{m+1} (1-p)^{k-1}$

2个校验块和3副本的可靠性对比(取m=2):

k	m	丢数据风险
1	2	$ 1 \times 10^{-12} $ (1个数据块+2个校验块可靠性和 3副本等价)
2	2	$ 3 \times 10^{-12} $
3	2	$ 9 \times 10^{-12} $
10	2	$ 2 \times 10^{-10} $ (10+2 和 12盘服务器的 RAID-6 等价)
32	2	$ 5 \times 10^{-9} $
64	2	$ 4 \times 10^{-8} $

3个校验块和4副本的可靠性对比(取m=3):

k	m	丢数据风险
1	3	$ 1 \times 10^{-16} $ (1个数据块+3个校验块可靠性和 4副本等价)
2	3	$ 5 \times 10^{-16} $
3	3	$ 2 \times 10^{-15} $
10	3	$ 7 \times 10^{-14} $
32	3	$ 5 \times 10^{-12} $
64	3	$ 7 \times 10^{-11} $

4个校验块和5副本的可靠性对比(取m=4):

k	m	丢数据风险
1	4	$ 1 \times 10^{-20} $ (1个数据块+4个校验块可靠性和 5副本等价)
2	4	$ 6 \times 10^{-20} $
3	4	$ 2 \times 10^{-19} $
10	4	$ 2 \times 10^{-17} $
32	4	$ 4 \times 10^{-15} $
64	4	$ 1 \times 10^{-13} $

IO消耗

以一个 EC 组来分析, 1个块损坏的概率是 $ p $, 这个组中有块损坏的概率是: $ 1 - (1-p)^{k+m} \approx (k+m)p $

每次数据损坏都需要读取全组的数据进行恢复. 不论1块损坏还是多块损坏, 数据恢复都是读取1次, 输出1或多次. 恢复数据的输出比较小, 1般是1, 所以可以忽略.

每存储一个字节一天数据恢复产生的传输量是(blocksize是一个数据块或校验块的大小):

$\frac{(k+m)p \times (k+m) \times blocksize} {(k+m) \times blocksize} = (k+m)p$

也就是说, 使用 EC 每存储1TB的数据, 每天(因为我们取的数据损坏概率是按天计算的)用于数据恢复而产生的IO是 k * 0.1GB / TB

磁盘的IO大致上也等同于网络流量, 因为大部分实现必须将数据分布到不同的服务器上.

NOTE:
随着 k的增加, 整体成本虽然会下降(1+m/k), 但数据恢复的IO开销也会随着k(近似于)线性的增长.

例如:

假设k+m = 12:

如果整个集群有 100PB 数据, 每天用于恢复数据的网络传输是 100TB.

假设单台存储服务器的容量是30TB, 每台服务器每天用于数据恢复的数据输出量是 30GB, 如果数据恢复能平均到每天的每1秒, 最低的带宽消耗是: 30GB / 86400 sec/day = 3.0Mbps.

但一般来说数据恢复不会在时间上很均匀的分布, 这个带宽消耗需要预估10倍到100倍.

参考

实现高性能纠删码引擎

shuwen , Mar 8 2018 , ngx.re.match oom

ngx.re.match()导致内存溢出问题

syntax: captures, err = ngx.re.match(subject, regex, options?, ctx?, res_table?)

Matches the subject string using the Perl compatible regular expression regex with the optional options.

这是ngx_lua对ngx.re.match的定义, 兼容Perl正则表达式的字符串匹配函数，在单次或者几次调用该函数并不会有什么问题，在循环多次执行时就会有可能出现oom问题，具体场景和现象如下文介绍

ngx.re.match() oom现场

测试代码：

use Test::Nginx::Socket 'no_plan';

use Cwd qw(cwd);
my $pwd = cwd();

no_long_string();
run_tests();

__DATA__

=== TEST 1: basic
--- http_config eval: $::HttpConfig
--- config
    location /t {
        content_by_lua '
            local str = "1234, hello"
            local ptn = "[0-9]+"
            local ii = 0

            while ii < 10 * 1000 * 1000 * 1000 do
                local m, err = ngx.re.match(str, ptn)
                ii = ii + 1
            end
        ';
    }

--- request
GET /t HTTP/1.1
--- timeout: 1000000

执行结果：

ngx.re.match

看如上代码和进程11751占用内存情况，重复循环执行10 * 1000 * 1000 * 1000次 ngx.re.match，发现占用了测试机4GB*31%=1.2GB的内存，这是为什么呢？按常理，应该只会占用很少的内存。

ngx.re.match() oom的刨根问底

首先看2个事实：

- 1.每次执行ngx.re.match(str, ptn)都会编译一次
- 2.在一次nginx请求未结束不会释放该请求上下文的内存

根据这2个事实，不难发现在执行10 * 1000 * 1000 * 1000次ngx.re.match()每次都产生了编译的结果，而请求未结束，则该编译结果会一直保存在内存中，所以导致了内存占用了4GB*31%=1.2GB

ngx.re.match() oom的解决之法

ngx.re.match()神奇的 -o 选项, -o 官方解释是：compile-once to enable the worker-process-level compiled-regex cache，就是一次编译编译结果缓存在worker的进程内，每次执行使用缓存的编译结果，那么试试设置 -o后的执行效果。

测试代码：

use Test::Nginx::Socket 'no_plan';

use Cwd qw(cwd);
my $pwd = cwd();

no_long_string();
run_tests();

__DATA__

=== TEST 1: basic
--- http_config eval: $::HttpConfig
--- config
    location /t {
        content_by_lua '
            local str = "1234, hello"
            local ptn = "[0-9]+"
            local ii = 0

            while ii < 10 * 1000 * 1000 * 1000 do
                local m, err = ngx.re.match(str, ptn，"o")
                ii = ii + 1
            end
        ';
    }

--- request
GET /t HTTP/1.1
--- timeout: 1000000

执行结果：

ngx.re.match

同样的代码，只是设置了 -o选项，内存基本保存4G*0.1%=4MB左右，这就比较正常了。

参考

openresty/lua-nginx-module

xp , Nov 22 2017 , socket network close shutdown c EINVAL go brainhole

socket关闭: close()和shutdown()的差异

对于一个tcp连接，在c语言里一般有2种方法可以将其关闭：

close(sock_fd);

或者

shutdown(sock_fd, ...);

多数情况下这2个方法的效果没有区别，可以互换使用。除了：

close() 是针对file的操作
shutdown() 是针对socket的操作

nix系统里socket是1个文件，但文件不1定是1个socket;

所以在进入系统调用后和达到协议层前(发出FIN包这一段), close()和shutdown()的行为会有1点差异。

到达协议层以后，close()和shutdown()没有区别。

举几个栗子示范下close()和shutdown()的差异

下面通过几个例子演示下close()和shutdown()在多线程并发时的行为差异, 我们假设场景是:

sock_fd 是一个blocking mode的socket。
thread-1 正在对sock_fd进行阻塞的recv()，还没有返回。
thread-2 直接对sock_fd调用close() 或 shutdown()。
不考虑linger。

栗子1: socket阻塞在recv()上, 调用close()

// Close a waiting recv()
Time
 |
 |  thread-1                  | thread-2           | tcpdump
 |                            |                    |
 |  recv(sock_fd              |                    |
 |      <unfinished ...>      |                    |
1|                            | close(sock_fd) = 0 |
 |                            |                    | // Some data arrived
 |                            |                    | // after close()
2|                            |                    | < seq 1:36 ... length 35
 |                            |                    | > ack 36 ...
 |  // Data was received.     |                    |
3|  <... recv resumed>) = 35  |                    |
4|                            |                    | > FIN sent
 |                            |                    | < ack of FIN received
 |                            |                    | ...
 |  // Can't be used any more |                    |
5v  recv(sock_fd) = -1        |                    |

在上面的例子里：

(1) thread-2 调用close()立即成功返回，这时recv()还在使用sock_fd。

这里因为有另外1个线程thread-1正在使用sock_fd，所以只是标记这个sock_fd为要关闭的。 socket并没有真正关闭。

这时recv()还继续处于阻塞读取状态。
(2) close()之后，有些数据到了，recv可以读取并返回了。
(3) recv()收到数据, 正确退出。
(4) rece()结束调用，释放socket的引用，这时底层开始关闭socket的流程。
(5) 再次调用recv()就会得到错误。

可以看到，close()没有立即关闭socket的连接，也没有打断等待的recv()。

栗子2: socket阻塞在recv()上, 调用shutdown()

// Shutdown a waiting recv()
Time
 |
 |  thread-1                  | thread-2              | tcpdump
 |                            |                       |
 |  recv(sock_fd              |                       |
 |      <unfinished ...>      |                       |
1|                            | shutdown(sock_fd) = 0 | > FIN sent
 |                            |                       | < ack of FIN received
 |                            |                       | ...
 |  // Woken up by shutdown() |                       |
 |  // no errno set           |                       |
2|  <... recv resumed>) = 0   |                       |
 v                            |                       |

在上面的例子里：

(1) thread-1还在等待sock_fd, thread-2调用shutdown(), 立即开始关闭socket的流程，发FIN 包等。

然后, 内核中tcp_shutdown中会调用sock_def_wakeup 唤醒阻塞在recv()上的thread-1。
(2) 这时recv()阻塞的线程被唤醒等待并立即返回。返回码是0，表示socket已经关了。

可以看到，shutdown()和close()不同，会立即关闭socket的连接，并唤醒等待的recv()。

以上2个例子的代码

close-or-shutdown-recv

栗子3: socket阻塞在accept()上, 调用shutdown()

类似的，对阻塞在accept()上的socket调用shutdown()，accept也会被唤醒:

// Shutdown a waiting accept()
Time
 |
 |  thread-1                      | thread-2
 |                                |
 |  accept(sock_fd                |
 |      <unfinished ...>          |
1|                                | shutdown(sock_fd) = 0
 |                                |
 |  // Woken up by shutdown()     |
 |  // errno set to EINVA         |
2|  <... accept resumed>) = -1    |
 |                                |
 v                                |

(1) thread-1还在等待sock_fd, thread-2调用shutdown(), 立即开始关闭socket的流程，发FIN 包等。

然后, 内核中tcp_shutdown中会调用sock_def_wakeup 唤醒阻塞在accept()上的thread-1。
(2) 这时在accept()上阻塞的线程被唤醒, 并立即返回。

返回码是-1，errno设置为EINVA。
这里如果thread-2调用的是close(), accept不会被唤醒，如果后面有请求connect进来，还能正确接受并返回。

结论

shutdown() 立即关闭socket;

并可以用来唤醒等待线程;
close() 不一定立即关闭socket(如果有人引用, 要等到引用解除);

不会唤醒等待线程。

现在大部分网络应用都使用nonblocking socket和事件模型如epoll的时候，因为nonblocking所以没有线程阻塞, 上面提到的行为差别不会体现出来。

go中不能唤醒的问题和重现方法

(开始写的时候没有记清楚重现步骤，感谢 [foxmailed][foxmailed] 提醒。)

上面的描述不准确，更新一下, 实际上是2个问题在1起引起的TCPListener.Close无法唤醒Accept的goroutine:

go里的socket本来应该都是nonblocking的。

go内部accept的系统调用在没有连接时返回-1，然后进入事件的等待(epoll_wait等)。

执行TCPListener.Accept的goroutine如果没有收到connect请求, 就把自己挂起来, 等待网络事件到来.
TCPListener.Close 本身是有的唤醒机制的。

但和系统调用shutdown()的唤醒不一样， shutdown是线程调度层面的， TCPListener.Close是网络事件层和goroutine层面。

TCPListener.Close实际上是把TCPListener.Accept的goroutine唤醒。所以正常的阻塞的TCPListener.Accept的goroutine在TCPListener.Close调用时会被唤醒.

如果监听的TCPListener内部的fd时blocking模式的, 它在调用系统调用accept()时, accept()不会返回-1, 而是阻塞住, 这时线程被挂起(不是goroutine挂起了). 要唤醒就需要先把它从系统调用中唤醒(例如用shutdown,TCPListener.Close 没有这个步骤)。

所以TCPListener.Close的唤醒机制前提是nonblocking。一旦进入blocking模式并调用了accept, TCPListener.Close就没能力把它唤醒了.

但go里面有1个问题，就是它的dup()实现时，每次dup之后还会顺手把fd设置为blocking模式:

net/fd_unix.go里的实现, 看注释里地描述:

func (fd *netFD) dup() (f *os.File, err error) {
        ns, err := dupCloseOnExec(fd.sysfd)
        if err != nil {
                syscall.ForkLock.RUnlock()
                return nil, &OpError{"dup", fd.net, fd.laddr, err}
        }

        // We want blocking mode for the new fd, hence the double negative.
        // This also puts the old fd into blocking mode, meaning that
        // I/O will block the thread instead of letting us use the epoll server.
        // Everything will still work, just with more threads.
        if err = syscall.SetNonblock(ns, false); err != nil {
                return nil, &OpError{"setnonblock", fd.net, fd.laddr, err}
        }

        return os.NewFile(uintptr(ns), fd.name()), nil
}

简单说就是dup的副作用是把fd变成阻塞的，但go开发者不是很屌这件事情，觉得阻塞就阻塞，无非多用几个线程而已。

可是TCPListener.Close的唤醒机制是必须基于nonblocking的。。。。。

所以只要dup()被调用了1下， TCPListener.Close就无法唤醒等待的TCPListener.Accept了。

哪些场合dup会被调用呢？最简单地就是从Listener里取1下File对象就好了：
```
l.(*net.TCPListener).File()
```
go里File方法实现：
```
net/tcpsock_posix.go:
func (l *TCPListener) File() (f *os.File, err error) { return l.fd.dup() }
```

.File()在我们的代码里用在进程重启过程中的监听fd的继承.

为了解决这个问题, 我们在代码里每次调用.File()后，都加上了1句修正：

syscall.SetNonblock( int(f.Fd()), true )

下面这段代码可以重现go中Close不唤醒的问题：

close-does-not-wake-up-accept.go

package main
import (
	"log"
	"net"
	"runtime"
	"time"
)
func main() {
	runtime.GOMAXPROCS(2)
	l, err := net.Listen("tcp", ":2000")
	if err != nil {
		log.Fatal(err)
	}

	show_bug := true
	if show_bug {
		// TCPListener.File() calls dup() that switches the fd to blocking
		// mode
		l.(*net.TCPListener).File()
	}

	go func() {
		log.Println("listening... expect an 'closed **' error in 1 second")
		_, e := l.Accept()
		log.Println(e)
	}()
	time.Sleep(time.Second * 1)
	l.Close()
	time.Sleep(time.Second * 1)
}

xp , Oct 22 2017 , paxos,network theory distributed consensus tutorial quorum replication

xp的分布式系统系列教程之: 可靠分布式系统基础 Paxos 的直观解释

Paxos 已经逐渐被承认是分布式系统中不可缺少的核心算法, 越来越多的分布式系统都是以paxos或其变种来达到强一致性的.

本文是一篇paxos入门教程, 从基本的分布式中的问题: 主从复制，quorum-rw等算法出发, 通过逐步解决和完善这几个问题, 最后推导出paxos的算法.

本文分为2个部分:

前1部分是分布式一致性问题的讨论和解决方案的逐步完善, 用比较通俗的语言得出paxos算法的过程. 如果你只希望理解paxos而不打算花太多时间深入细节, 只阅读这1部分就可以啦.
第2部分是paxos算法和协议的严格描述. 这部分可以作为paxos原paper的实现部分的概括. 如果你打算实现自己的paxos或类似协议, 需要仔细了解协议细节, 希望这部分内容可以帮你节省阅读原paper的时间.

在线查看 html 版本 paxos.html

可靠分布式系统基础 Paxos的直观解释 on slideshare.net from Yanpo Zhang

Download the paxos.pdf

Paul Yang , Oct 10 2017 , theory distributed tutorial replication erasure code brainhole

白山HTTPS功能升级——ChaCha20算法实现移动端设备节电

结论
- 性能对比
白山CDN支持和建议应用场景
延伸阅读： ChaCha20算法原理
- ChaCha20的keystream生成
- TLS中的ChaCha20

结论

老规矩，先说结论。

未来如果AES被发现存在问题，人们将不得不退而使用老旧的3DES算法，因此业界需要一个备选算法；
在不支持AES硬件加速指令的设备上，AES算法的性能不具备明显优势（尤其是和某些流加密算法相比）；
AES如果实现的不正确，可能存在缓存碰撞时序攻击（AES Cache-Collision Timing Attack）。

而ChaCha20可以较好的解决上述问题。

ChaCha20是一种流加密算法，实现较为简单，并且比纯软件实现的AES性能更好。

性能对比

chacha20-speed-no-hw

上图是在不使用AES硬件加速的情况下，对AES和ChaCha20进行的性能对比测试。其中ChaCha20性能是GCM模式AES256的5倍左右。

但如果设备已经支持AES硬件加速指令，例如iPhone和部分Android系统手机或支持AES-NI指令的Intel CPU等，AES的速度依然具有绝对优势：

chacha20-speed-hw

白山CDN支持和建议应用场景

白山CDN在其HTTPS服务中全面支持ChaCha20-Poly1305算法，并采用自动适应客户端算法列表的处理手段：

如果客户端不支持AES硬件加速指令，则优先使用ChaCha20
否则按照服务器的算法优先级顺序选择AES算法
目前我们支持的TLS加密套件有：

TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256
TLS_CHACHA20_POLY1305_SHA256 (TLSv1.3用）

在支持AES指令的硬件平台上，推荐优先选择AES-GCM算法；而CBC模式的AES和RC4算法在很多情况下并非最好选择，应当尽量避免过多使用。

延伸阅读： ChaCha20算法原理

ChaCha20是一种流加密算法，其原理和实现都较为简单，大致可以分成如下两个步骤：

基于输入的对称秘钥生成足够长度的keystream
将上述keystream和明文进行按位异或，得到密文

解密流程同上。以下着重讲解keystream的生成方法。

ChaCha20的keystream生成

ChaCha20算法中的基本操作叫做“quarter round”，一个quarter round定义如下：

a, b, c, d是4个4字节（32位）的无符号整数，对它们进行如下操作（其中‘«<’表示向左轮转）：

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

得到一组新的a, b, c, d，共16个字节。

另一个重要概念是ChaCha state，一个ChaCha state由16个32位数字组成，例如：

879531e0 c5ecf37d 516461b1 c9a62f8a
44c20ef3 3390af7f d9fc690b 2a5f714c
53372767 b00a5631 974c541a 359e9963
5c971061 3d631689 2098d9d6 91dbd320

quarter-round可以应用到state中，我们定义quarter-round(x, y, z, w)为应用到state中的quarter-round操作，例如quater-round(1, 5, 9, 13)是计算如下带星号（*）数字的值：

879531e0 *c5ecf37d 516461b1 c9a62f8a
44c20ef3 *3390af7f d9fc690b 2a5f714c
53372767 *b00a5631 974c541a 359e9963
5c971061 *3d631689 2098d9d6 91dbd320

cccccccc  cccccccc  cccccccc  cccccccc
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
bbbbbbbb  nnnnnnnn  nnnnnnnn  nnnnnnnn

其中：

c：4个32位数字，内容固定为：0x61707865, 0x3320646e, 0x79622d32, 0x6b206574。
k：256位的对称密钥，即32字节
b：count，按明文的block数递增，可以从0或者1开始
n：nouce，其组成根据ChaCha20在不同协议中的使用而有所区别，下文将介绍TLS中的nouce构成

上述所有的数值都以4字节为一组，小端存储。

接下来介绍一个round：

 QUARTERROUND ( 0, 4, 8,12)
 QUARTERROUND ( 1, 5, 9,13)
 QUARTERROUND ( 2, 6,10,14)
 QUARTERROUND ( 3, 7,11,15)
 QUARTERROUND ( 0, 5,10,15)
 QUARTERROUND ( 1, 6,11,12)
 QUARTERROUND ( 2, 7, 8,13)
 QUARTERROUND ( 3, 4, 9,14)

一个更加清楚的例子：

ChaCha state:

       61707865  3320646e  79622d32  6b206574
       03020100  07060504  0b0a0908  0f0e0d0c
       13121110  17161514  1b1a1918  1f1e1d1c
       00000001  09000000  4a000000  00000000
       

应用上述20轮变换，可得到：

Keystream block:
 
       e4e7f110  15593bd1  1fdd0f50  c47120a3
       c7f4d1c7  0368c033  9aaa2204  4e6cd4c3
       466482d2  09aa9f07  05d7c214  a2028bd9
       d19c12b5  b94e16de  e883d0cb  4e3c50a2

另外一种思路是先计算全部keystream block，拼接成一个完整的keystream，和整个待加密数据进行异或，当然这种实现会占用较多内存。

解密操作和加密操作一样，因此不再赘述，更多细节及案例，可参考 RFC 7539 。

TLS中的ChaCha20

在TLS中使用ChaCha20，主要是如下几个加密套件：

TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256   = {0xCC, 0xA8}
TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256 = {0xCC, 0xA9}
TLS_DHE_RSA_WITH_CHACHA20_POLY1305_SHA256     = {0xCC, 0xAA}
 
TLS_PSK_WITH_CHACHA20_POLY1305_SHA256         = {0xCC, 0xAB}
TLS_ECDHE_PSK_WITH_CHACHA20_POLY1305_SHA256   = {0xCC, 0xAC}
TLS_DHE_PSK_WITH_CHACHA20_POLY1305_SHA256     = {0xCC, 0xAD}
TLS_RSA_PSK_WITH_CHACHA20_POLY1305_SHA256     = {0xCC, 0xAE}

如前所述，白山目前主要支持TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256和TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1305_SHA256

此外TLS中的ChaCha20对nouce的组成，还存在如下规定：

在TLS record sequence的左侧填充4个值为0的字节，形成一个96位的数值
将上述数值和client_write_IV或server_write_IV进行异或，得到最终的nouce

作者简介：

杨洋，白山架构师兼驻辽代表，“白十三的码路”缔造者。

NGINX开发、安全系统研发方向布道师。10年研开发经验，先后就职于东软、阿里云、金山云等，OpenSSL代码贡献榜排名17，擅长安全产品研发及各类开发指南编译工作，Bulletproof SSL and TLS第一译者。爱好不断挑战HTTPS流量与加密底线、持续突破各类防御系统极限。

林胜恩 , Sep 15 2017 , theory distributed tutorial replication erasure code brainhole

白山HTTPS功能升级——TLSv1.3协议

1 协议发展历程

在SSL/TLS发展过程中曾出现过各种安全漏洞，如Heartbleed、POODLE，这导致SSL3.0及其之前版本逐渐废弃，目前互联网使用的主流协议是TLS1.2版本。

2 安全强化

2.1 密钥交换

2.1.1 完全支持PFS

为了达到上述安全目的，TLS1.3协议中废除了不支持前向安全性的RSA和静态DH密钥交换算法。

2.1.2 废弃DSA证书

DSA证书作为历史遗留产物，因安全性差，从未被大规模应用，故在TLS1.3协议中被废弃。

2.1.3 RSA填充模式更改

协议中规定RSA填充模式使用PSS。

2.1.4 禁用自定义的DH组参数

2.2 对称加密

2.2.1 禁用CBC模式

针对CBC模式加密算法的攻击，历史上出现过两次，分别是2011年BEAST和2013年Lucky 13，实践证明这种对称加密模式确实存在安全隐患。

2.2.2 禁用RC4流加密算法

2.2.3 禁用SHA1

早在2005年研究机构就发现SHA1存在理论上的漏洞，可能造成碰撞攻击。

2013年开始微软、Google、Symantec等相关厂商相继公布SHA1证书的升级计划并宣布2017年将开始停止信任SHA1证书。

2017年初Google与荷兰研究机构CWI Amsterdam共同宣布破解SHA1，将SHA1的碰撞攻击从理论转变为现实。

2.2.4 禁用出口密码套件

2.3 禁用TLS压缩

2.4 加密握手消息

3 效率提升

对于互联网服务而言更快的页面加载意味着更好的用户体验，从而也能带动产品销售的提升。

3.1 2-RTT

下面以ECDHE密钥交换算法为例，介绍下TLS1.2协议完整的SSL握手过程，如下图所示。

tls13a

首先客户端发送ClientHello消息，该消息中主要包括客户端支持的协议版本、加密套件列表及握手过程需要用到的ECC扩展信息；
服务端回复ServerHello，包含选定的加密套件和ECC扩展；发送证书给客户端；选用客户端提供的参数生成ECDH临时公钥，同时回复ServerKeyExchange消息；
客户端接收ServerKeyExchange后，使用证书公钥进行签名验证，获取服务器端的ECDH临时公钥，生成会话所需要的共享密钥；生成ECDH临时公钥和ClientKeyExchange消息发送给服务端；
服务器处理ClientKeyExchange消息，获取客户端ECDH临时公钥；服务器生成会话所需要的共享密钥；发送密钥协商完成消息给客户端；
双方使用生成的共享密钥对消息加密传输，保证消息安全。

3.2 1-RTT

tls13b

客户端发送ClientHello消息，该消息主要包括客户端支持的协议版本、DH密钥交换参数列表KeyShare；
服务端回复ServerHello，包含选定的加密套件；发送证书给客户端；使用证书对应的私钥对握手消息签名，将结果发送给客户端；选用客户端提供的参数生成ECDH临时公钥，结合选定的DH参数计算出用于加密HTTP消息的共享密钥；服务端生成的临时公钥通过KeyShare消息发送给客户端；
客户端接收到KeyShare消息后，使用证书公钥进行签名验证，获取服务器端的ECDH临时公钥，生成会话所需要的共享密钥；
双方使用生成的共享密钥对消息加密传输，保证消息安全。

3.3 0-RTT

为使TLS协议的性能得到极致提升，TLS 1.3提出0-RTT工作模式。对于客户最近访问过的网站，可以在第一次交互时就将加密数据发送给服务器。

具体的实现过程如下：

0-RTT模式不具有前向安全性，且消息可能被用作重放攻击，所以安全性较低，需慎重使用。

4 总结

上文已详细阐述TLS 1.3的各种优化改进，为让大家有更加直观的感受，白山搭建了支持TLS 1.3协议的服务器，欢迎大家访问体验。

当前主流浏览器支持的draft-18的服务器地址为https://tls13.baishancloud.com/

最新的draft-21版本的服务器地址为https://tls13.baishancloud.com:44344。

作者简介：

林胜恩，花名“蒙多尔”，白山系统开发工程师

嵌入式Linux系统开发方向及HTTPS相关领域初号机。多年研发经验，曾就职于锐捷网络，主导网络设备管理协议工作。偏爱不断挑战HTTPS性能天花板，加入酒精更易产生反差萌化学反应，故又名“酒后苏轼”。

Paul Yang , May 24 2017 , theory distributed tutorial replication erasure code brainhole

浅谈RSA Padding

答案是：it depends!

首先要了解两个概念：密码学原语（Cryptographic Primitive）和密码体制（Cryptographic Scheme）

Primitive

例如，RSA的公钥加密过程可以表示为：

c = RSAEP((n, e), m)

其中：

c是密文
m是明文
(n, e)是公钥，其中n是modulus，e是RSA的公钥指数
RSAEP是RSA Encryption Primitive的意思，即RSA加密原语

RSAEP的具体内容，就是RSA的加密算法，也就是“数学层面”的内容：

c = m^e mod n

Scheme

但是在现实生活中，几乎没有直接对于primitives的使用，我们可以用openssl来对一段数据进行加密，然后用不匹配的秘钥进行解密。

先生成两对公私钥，A对和B对：

$ ./openssl genpkey -algorithm RSA -out priv_A.key -pkeyopt rsa_keygen_bits:2048
...................+++
......................+++

$ ./openssl genpkey -algorithm RSA -out priv_B.key -pkeyopt rsa_keygen_bits:2048
...................+++
......................+++

从私钥导出公钥：

$ ./openssl rsa -pubout -in priv_A.key -out pub_A.key
$ ./openssl rsa -pubout -in priv_B.key -out pub_B.key

这样就有了两个key pair：

-rw-------. 1 paul paul   1704 Nov 28 17:50 priv_A.key
-rw-------. 1 paul paul   1704 Nov 28 17:50 priv_B.key
-rw-rw-r--. 1 paul paul    451 Nov 28 17:54 pub_A.key
-rw-rw-r--. 1 paul paul    451 Nov 28 17:55 pub_B.key

OK，接下来测试一下正常的加密和解密，用pub_A加密，用priv_A解密的效果：

rsa_good

可以正常解密出原文，接下来常使用错误的私钥进行解密，使用priv_B：

rsa_bad

并没有出现无意义的内容，而是openssl直接报错：

rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error
rsa routines:rsa_ossl_private_decrypt:padding check failed

这个就是因为在实际中，一般不会直接使用原语对数据进行操作，因为直接使用原语进行运算会产生很多的安全问题，可以参考：这里

为此，实践中的RSA都会填充（padding）随机数据，然后再进行加密，可以使密文多样化，这种规定如何填充的方法就是scheme。

RSA padding的主要scheme有几种：

加密：
- RSAES-PKCS1-v1_5: PKCS #1中规定的老式方法，从PKCS #1 version 1.5开始使用
- RSAES-OAEP，新式方法，可见：OAEP，有图
签名：
- RSASSA-PKCS-v1_5: 老式方法
- RSASSA-PSS: 新式方法

在openssl命令中可以使用参数来指定使用哪种padding scheme，默认是PKCS #1的老式方法：

rsa_padding

当然，你也可以不padding，那就和直接使用原语无差别了。

我们再基于PKCS的padding方式来看为何openssl能发现解密失败，而不是返回数据。首先要了解一下具体的padding方法，根据RFC 3447的7.2.1节的2.b步骤：

EM = 0x00 || 0x02 || PS || 0x00 || M.

PS，padding string，随机数
M，明文

padding的方式是在固定的pattern之中加上随机数，然后作为明文的前缀进行加密原语的运算。

对于解密，会对上述解密出来的加上了padding的数据进行decode，从而最后拿到明文M，根据RFC 3447 7.2.2的步骤三：

rsa_padding_failed

可以发现padding不对，从而直接判断出解密失败。

xp , Feb 1 2017 , theory,distributed,tutorial,replication,erasure code

xp的分布式系统系列教程之: Erasure-Code: 工作原理, 数学解释, 实践和分析.

内容简介

Erasure-Code, 简称 EC, 也叫做 擦除码 或 纠删码, 指使用范德蒙(Vandermonde) 矩阵的里德-所罗门码(Reed-Solomon) 擦除码算法.

EC 本身是1组数据冗余和恢复的算法的统称.

本文以 Vandermonde 矩阵的 Reed-Solomon 来解释 EC 的原理.

术语定义:

$d_j$ 表示数据块.
$y_i$ 表示通过数据块计算得来的, 作为数据冗余的校验块.
$u_j$ 表示丢失的, 需要恢复的数据块.
k 表示数据块的数量.
m 表示校验块的数量.

本文内容包括:

第1节分布式系统的可靠性问题: 冗余和多副本提出EC需要解决的问题.
希望对分布式存储领域增加了解的同学, 可以只阅读 EC的基本原理部分.

这部分会用到1些中学的数学知识, 逐步用举栗子🌰的方式给出了EC算法的直观解释.

它和真正实现层面的EC原理是一致的, 但不深入到太多数学层面的内容.
已经对EC工作方式有些了解, 希望更深入了解其数学原理的读者, 可以直接从 EC编码矩阵的几何解释开始阅读.

这部分解释了EC的编码矩阵的原理和含义, 但不包括更底层数学的讨论.

伽罗华域GF(7) 和伽罗华域GF(256) 开始介绍如何将EC应用到计算机上的方法, 从这部分开始EC会用到1些抽象代数中的知识.
需要动手扣腚解决分布式存储问题的猿, 如果对数学原理不感兴趣, 但对工程实践方面有兴趣的话, 可以参考实现.
需要对存储策略规划的架构师, 可以直接参考数值分析部分分析.

分布式系统的可靠性问题: 冗余和多副本

一般还必须让数据的多个副本分布在不同的服务器, 机架或机房里才能真正达到高可靠.

数据可靠了之后才需要讨论数据的一致性和性能等问题. (也可能, 一致性和可靠性是并列第一的😄).

提高可靠性也很直接, 一般的解决方式就是 对一份数据存储多个副本.

副本数一般选择3:
3副本结合当前经验上的磁盘的损坏率(大约是年损坏率7%), 大约可以达到一个工业可接受的可靠性, 这个可靠性的预期大约是11个9以上(99.999999999%的概率不丢数据).

下图摘自 backblaze发布的硬盘故障率统计

$(d_1, d_1, d_1), \\ (d_2, d_2, d_2), \\ ...$

第1列的$d_1, d_2$在第1个服务器上,
第2列的$d_1, d_2$在第2个服务器上,
第3列的$d_1, d_2$在第3个服务器上.

这种3副本的策略下, 总的存储冗余度是 300%
空间浪费是200%

当然有些时候为了降低成本, 只存储2个副本, 这时冗余度是200%, 也浪费了1倍的空间:

$(d_1, d_1), \\ (d_2, d_2), \\ ...$

那么, 能否用较少的冗余, 来实现同样较高的可靠性, 就成了分布式存储的一个重要研发的方向.

这就是本文介绍的 EC 需要解决的问题. 接下来, 我们通过几个例子, 1步步介绍 EC 的原理和实现机制.

EC的基本原理

栗子🌰1: 实现k+1的冗余策略, 大概需要小学3年级的数学知识

Q: 有3个自然数, 能否做到再记录第4个数字, 让任何一个数字丢失的时候都可以将其找回?

这个问题很简单, 记录这3个数字的和: 假设3个数字是: $ d_1, d_2, d_3 $; 再存储一个数: $ y_1 = d_1 + d_2 + d_3 $.

存储的过程就是存储这4个数字: $ d_1, d_2, d_3, y_1 $:
数据丢失后要找回时:
- 这样如果 $ d_1, d_2, d_3 $ 任意一个丢失, 例如 $ d_1 $ 丢失了, 我们都可以通过 $ d_1 = y_1 - d_2 - d_3 $ 来得到 $ d_1 $.
- 如果 $ y_1 $ 丢失, 则再次取 $ d_1 + d_2 + d_3 $ 的和就可以将 $ y_1 $ 找回.

在上面这个简单的系统中, 总共存储了4份数据, 有效的数据是3份.
冗余是133%, 它的可靠性和2副本的存储策略差不多: 最多允许丢失1份数据.

看起来这是一个不错的解决方案:
我们用133%的冗余, 实现了和2副本的 200% 冗余 差不多的可靠性! 如下:

策略	冗余度	可靠性	存储策略示意
2副本	200%	允许丢1块: $ 1 \times 10^{-8} $	$ (d_1,d_1) $, $ (d_2,d_2)$, $(d_3,d_3)… $
3+1求和冗余	133%	允许丢1块: $ 6 \times 10^{-8} $	$ (d_1, d_2, d_3, y_1) $, $ (d_4, d_5, d_6, y_2)… $

这里只是差不多, 还并不是完全一样, 后面分析 1节会详细讨论可靠性的计算.
在讨论可靠性的时候, 一般数据丢失风险没有量级的差异, 就可以认为是比较接近的.

上面这个例子是和我们平时使用的 RAID-5 基本是一样的. RAID-5 通过对k个(可能是11个左右)数据块求出1份校验和的数据块. 存储这份校验块, 并允许1块(数据或校验)丢失后可以找回.

当然在工程上, RAID-5 的计算和自然数的求和还有些差异. 后面继续撩.

以上的这种求和冗余策略, 就是 EC 的核心思路.

如果你对存储感兴趣但不希望太多深入细节, 到这里差不多已经比较直观地了解 EC 的原理了.

如果你还有浓厚的兴趣继续读下去,好极!

栗子🌰2: 实现k+m的冗余策略, 大概需要初中2年级的数学知识

现在我们在k+1的冗余策略基础上, 增加更多的校验块, 来实现任意k+m的冗余策略.

增加1个校验块, 变成k+2

Q: 有3块数据: $ d_1, d_2, d_3 $
可否另外再存储2个冗余的校验块(共5块), 让整个系统任意丢失2份数据时都能找回?

在k+1求和的策略里, 我们实际上是给所有的数据块和校验块建立了一个方程 $ d_1 + d_2 + d_3 = y_1 $, 来描述他们整体的关系.

现在, 如果要增加可丢失的数据块数, 简单的把 $ y_1 $ 存2次是不够的, 假设计算了2个校验块:

$d_1 + d_2 + d_3 = y_1 \\ d_1 + d_2 + d_3 = y_2 \\ (y_1 = y_2)$

存储的过程定义为: 存储 $ d_1, d_2, d_3, y_1, y_2 $ 这5个数字.
需要恢复数据时: 如果 $ d_1, d_2 $ 都丢失了($ u_1, u_2 $ 表示), 下面这个关于$ u_1, u_2 $的线性方程是有无穷多解的:
$\begin{cases} u_1 + u_2 + d_3 = y_1 \\ u_1 + u_2 + d_3 = y_2 \end{cases}$
我们没有办法从这个方程组里解出 $ u_1, u_2 $ 的值, 因为这2个方程是一样的, 没有提供更多的信息.

所以我们现在需要做的是, 设计一个计算第2个校验块 $ y_2 $ 的方法:
使得当 $ d_1, d_2 $丢失时方程组有解.

一个简单直接的思路是, 计算$ y_2 $ 时, 给每个数据 $ d_j $ 增加1个不同的系数:

计算$y_1$时, 对每个数字乘以1, 1, 1, 1 …
计算$y_2$时, 对每个数字乘以1, 2, 4, 8 …

$\begin{align} d_1 + d_2 + d_3 & = y_1 \\ d_1 + 2 d_2 + 4 d_3 & = y_2 \end{align}$

存储的过程任然定义为: 存储 $ d_1, d_2, d_3, y_1, y_2 $ 这5个数字.
数据恢复的时候, 如果 $ d_1, d_2 $ 丢失, 同样用 $ u_1, u_2 $表示, 我们可以使用剩下的 $ d_3, y_1, y_2 $ 来建里1个关于 $ u_1, u_2 $ 的二元一次方程组:

$\begin{cases} \begin{align} u_1 + u_2 & = y_1 - d_3 \\ u_1 + 2 u_2 & = y_2 - 4 d_3 \end{align} \end{cases}$

解出上面这个方程组, 就找回了丢失的 $ u_1, u_2 $.

感谢对我们负责的初中班主任, 把体育课帮我们改成了数学习题课, 让我们还记得这个二元一次方程组好像通过消元, 就能解出 $ u_1, u_2 $ 的值

<(￣︶￣)>

以上这种加系数计算校验块的方式, 就是RAID-6的基本工作方式:
RAID-6为k个数据块之外再多存储2个校验数据, 当整个系统丢失2块数据时, 都可以找回.

为什么计算 $ y_2 $ 的系数是1, 2, 4, 8…?
系数的选择有很多种方法, 1, 2, 4, 8是其中一个. 只要保证最终丢失2个数字构成的方程组有唯一解就可以. 这里选择1, 2, 3, 4…也可以.

到这里, 有理数下k+2的EC的算法大概就出来了, 我们可以实现k+2的冗余策略, 通过166%的冗余, 实现差不多和三副本300%一样的可靠性.

具体的可靠性计算参见下面的: 分析

实现k+m 的冗余

如果要增加更多的冗余,让EC来实现相当于4副本差不多的可靠性: k+3, 我们需要给上面的策略再增加一个校验块 $ y_3 $,

而 $ y_3 $ 的计算我们需要再为所有的 $ d_j $ 选择1组不同的系数, 例如1,3,9,27…来保证后面数据丢失时,得到的1个3元一次方程组是可解的:

$\begin{cases} \begin{align} d_1 + d_2 + d_3 & = y_1 \\ d_1 + 2 d_2 + 4 d_3 & = y_2 \\ d_1 + 3 d_2 + 9 d_3 & = y_2 \end{align} \end{cases}$

这样我们通过不断的增加不同的系数, 就可以得到任意的k+m的EC冗余存储策略的实现.

到此为止, 有理数下的EC算法就介绍完整了. 接下来的章节中, 我们会深入1点, 讨论下为什么要选择这样1组系数.

实际上,现实中使用的RAID-5和RAID-6都是 EC 的子集. EC 是更具通用性的算法. 但因为实现的成本(主要是计算的开销), RAID-5 和 RAID-6在单机的可靠性实现中还是占主流地位.

但随着存储量的不断增大, 百PB的存储已经不算是很极端场景了. RAID-6 在单机环境下不算高的数据丢失风险在大数据量的场景中显示的越来越明显. 于是在云存储(大规模存储)领域, 能支持更多的冗余校验块的EC成为了主流.

EC编码矩阵的几何解释

我们从比较简单的情况开始, 看下2个数据块计算(多个)EC校验块的方法:

k=2, 为2个数据块生成冗余校验块

假设现在我们有2个数据块 $ d_1, d_2 $. 要做2个校验块.

我们使用1个直线的方程, 来实现数据的冗余备份和恢复:

$y = d_1 + d_2 x$

这条直线具备这样的特点:

这条直线包含的所有数据块 $ d_j $ 的信息.

任何1对 $ d_1, d_2 $ 的值就确定一条不同的直线. 同样, 任意1条直线也唯一对应1对 $ d_1, d_2 $ 的值.

数据可靠性的问题就转化成了:

我们要保存足够多的关于这条直线的信息, 能够在需要的时候找回这条直线. 然后再提取直线方程的系数来找回最初存储的数据块 $ d_1, d_2 $.

要保存足够多的信息, 最直观的方法就是记录这条直线上的几个点的坐标.

因为2点可以确定一条直线, 只要拿到直线上2个点的坐标, 就能确定直线方程, 从而确定它的系数 $ d_1, d_2 $.

按照这样的思路, 我们重新用直线方程的方式描述数据冗余生成和数据恢复的过程:

生成冗余的校验数据的过程就是:

在直线上取2个点, 记录点的坐标(这里我们总是取x = [1, 2, 3…]的自然数的值, 所以只记录y的值就可以了)

$ d_1, d_2, (1, y_1), (2, y_2) $
恢复数据的过程就是: 已知过直线2点 $ (1, y_1), (2, y_2) $ 来确定直线方程的过程.

再次感谢初中班主任

取 x 分别为 1和2:

$\begin{cases} y_1 = d_1 + d_2 \\ y_2 = d_1 + 2d_2 \end{cases}$

我们得到了1组带冗余的数据: $ d_1, d_2, y_1, y_2 $. 这4个数据中,任意丢失2个,都可以通过等式关系 $ y = d_1 + d_2 · x $ 来恢复.

丢失1个数据块时只用 $ y_1 $ 的方程就够了.
丢失2个数据块时才需要解二元一次方程组.
如果 $ y_1 $或 $ y_2 $丢失, 则通过重新取点的方式恢复.

我们可以在直线上取任意多个点, 但恢复时最多也只需要2个点就够了. 在这个例子中我们实现了 2+m 的冗余策略.

k=3, 4, 5…时的数据块的冗余

例如:

二次曲线抛物线 $ y = a x^2 + b x + c $ 需要3个值来确定, 同时也需要知道抛物线上的3个点的坐标来找回这条抛物线.

通过高次曲线生成冗余数据

如果有k个数据块, 我们把k个数据作为系数, 来定义1条关于x的高次曲线:

$y = d_1 + d_2 x + d_3 x^2 + ... + d_k x^{k-1}$

生成m个冗余数据的过程就是:

取m个不同的x的值(1, 2, 3…m), 记录这条曲线上m个不同点的坐标:
$(1, y_1), (2, y_2) ... (m, y_m)$
存储所有的数据块 $ d_1, d_2…d_k $ 和所有的校验块 $ y_1, y_2…y_m $.
恢复数据:

当数据丢失时, 我们知道, 平面直角坐标系上m个点可以唯一确定1条 m-1 次幂的关于x的曲线. 确定了这条关于x的曲线,就找回了它的系数,也就是数据块 $ d_1, d_2 … d_k $

以上就是 EC 的算法的几何解释: 通过曲线上的点来确定曲线的过程.

从曲线方程得到的系数矩阵

在曲线方程上取点的坐标的过程中, 我们直接为x取自然数的位置来计算 y 的值: 1, 2, 3…:

$y_1 = d_1 + d_2 · 1 + d_3 · 1^2 + .. + d_k · 1^{k-1} \\ y_2 = d_1 + d_2 · 2 + d_3 · 2^2 + .. + d_k · 2^{k-1} \\ y_3 = d_1 + d_2 · 3 + d_3 · 3^2 + .. + d_k · 3^{k-1} \\ ... \\$

把上面等式写成矩阵的形式, 得到EC校验块的 生成矩阵 Generator-Matrix:

这里 $ y_1, y_2 … y_m $ 就是校验块的数据, 矩阵里就是我们上面使用的这样那组系数.

这个矩阵就是著名的 Vandermonde 矩阵.

Vandermonde 矩阵只是 EC 其中1种系数的选择方式. 其他常用的系数矩阵还有 Cauchy 矩阵等.

EC解码过程: 求解n元一次方程组

现在我们知道, EC 就是:

有1组数字: $d_1, d_2, d_3...d_k$ 另外记录m个校验用的数字 $y_1, y_2, y_3...y_m$ 使得这k+m个数字中任意丢失m个都能从剩下的k个中恢复所有的k+m个数字.

EC生成校验块的过程称之为EC的编码, 当数据丢失需要找回的时候, 使用的是EC的解码过程.

如上面章节所说, EC的编码过程是编码矩阵(Vandermonde)和数据块列相乘:

解码的过程如下:

假设有q个数字丢失了, $ q \le m $. 从上面的编码矩阵中选择 $ y_1, y_2..y_q $, q行, 组成的一次方程组, 求解丢失的数据.

例如 $ d_2, d_3 $ 丢失了, 下面用 $ u_2, u_3 $ 表示 (只丢失了2块数据, 不需要所有的m个校验块参与, 只需要2个校验块来恢复数据)

这个矩阵表示的方程组里有2个未知数 $ u_2, u_3 $, 解方程即可得到 $ u_2, u_3 $ 这2块丢失的数据.

Vandermonde 矩阵保证方程组有解

对于k+m的EC来说, 任意丢失m个数据块都可以将其找回.

Vandermonde 矩阵保证了任意m行m列组成的子矩阵都是线性无关的, 构成的方程肯定有确定解.

Vandermonde 的行列式的值为:

$\det(V)=\prod_{1 \leq i \lt j \leq n}(\alpha_j - \alpha_i)$

只要 $ \alpha_i $ 都不同, 则 Vandermonde 矩阵的行列式就不为0, 矩阵可逆, 表示方程有唯一解.

容易证明, Vandermonde 矩阵的任意 $ m \times m $的子矩阵也可以保证永远有唯一解.

到此为止我们讨论了EC在有理数范围内的全部内容. 它是完整的, 但还不能直接应用到计算机的代码开发商.

接下来我们要展开在纯数学和计算机算法之间的问题, 以及我们将通过什么样的手段来解决这些问题, 将EC真正应用到生产环境中.

新世界: 伽罗华域 Galois-Field GF(7)

$y = d_1 + d_2 x + d_3 x^2 + ... + d_k x^{k-1}$

因此上面介绍的EC, 在计算机上实现时, 必须解决数字大小的问题. 但总的算法是不变的. 这次我们要从最底层开始入手, 解决这个问题.

这也是我自己在学习 EC 时觉得最有趣的地方:

类似于把一段c代码写好后可以编译到intel CPU上也可以编译到ARM CPU上运行(即使这2种CPU的指令完全不同, 但c源代码的正确性是不变的),

现在我们要做的是, 我们设计好 EC 的上层算法后, 把它移植到另1套代数体系中, 而同时也能保证它上层的”源代码” 在另1种不同的底层体系上也可以正确运行!

EC在计算机里的实现: 基于伽罗华域 Galois-Field

上面我们提到的几个数学公式, 高次曲线, 多元一次方程组等: $ y = d_1 + d_2 x + d_3 x^2 + … + d_k x^{k-1} $

他们之所以能正确的工作, 是因为他们依赖于一套底层的基础运算规则, 这就是四则运算: $ + - \times \div $ (实现 EC 的代数中我们没有用到开方运算).

这听起来有点废话, ™不用四则运算用什么?

其实我们平时熟知的四则运算, 在代数里并不是唯一的四则运算法则, 它有很多很多个兄弟, 他们有共同的规律,却有着不同的表现形式.

例如在有1种四则运算建立的代数可能是: $ 5 + 5 = 3 $ 而不是10, $ 5 \times 3 = 1 $ 而不是15. 也可能有1种四则运算里乘法不是加法的叠加.

最常见的是钟表的时间相加, 20点加8个小时不是28点, 而是4点.

我们现在需要做的是, 找到一种四则运算, 来让 EC 的计算可以不会越界!

现在我们来一步步开启这扇新世界的大门…

首先感谢19世纪因为跟情敌决斗被一枪打死的伟大数学家伽罗华.

栗子🌰3: 只有7个数字的新世界: GF(7)

大门, 慢慢开启…

我们来尝试定义一个新的加法规则, 在这个新的世界里只有0~6这7个数字:

其他整数进来时都要被模7, 变成0~6的数字.

在这个模7的新世界里, 四则运算也可以工作:

模7新世界中的加法

我们来尝试定义一个新的加法规则, 在这个只有0~6这7个数字的新世界里, (新的加法被表示为 ⊕ (这里原始的加法还是用+来表示)):

$a ⊕ b \rightarrow (a + b) \pmod 7$

它定义为: a ⊕ b的结果是 a + b后结果再对7取模. 例如:

1 ⊕ 1 = 2
5 ⊕ 2 = 0 ( 7 % 7 = 0 )
5 ⊕ 5 = 3 ( 10 % 7 = 3 )

在这个新世界里, 0 还是和以前的0很相像, 任何数跟0相加都不变:

0 ⊕ 3 = 3
2 ⊕ 0 = 2

0 在新世界 GF(7) 里被称为加法的单位元.

模7新世界中的减法

然后我们再在模7的世界里定义减法. 减法的定义也很直接, 就是加法的逆运算了.

减法定义就是: $ a ⊖ b \rightarrow a ⊕ (-b) $.

例如:

3 ⊖ 4 = 6 ( (-1) % 7 = 6 )
2 ⊖ 6 = 3 ( (-4) % 7 = 3 )

其实我们不需要减法, 我们只需要加法和逆元的定义

模7新世界中的乘法和除法

在模7的新世界里, 我们也可以类似地定义1个乘法:

$\begin{equation} a ⊗ b \rightarrow (a \times b) \mod 7 \end{equation}$

例如:

1 ⊗ 5 = 5 ( 5 % 7 = 5 )
3 ⊗ 4 = 5 ( 12 % 7 = 5 )
2 ⊗ 5 = 3 ( 10 % 7 = 3 )
0 ⊗ 6 = 0

对于模7新世界的乘法⊗来说, 1 是乘法的单位元, 也就是说1 ⊗ 任何数都是它本身.

我们也可以用类似的方法定义每个数字在乘法⊗的逆元:

$a的乘法逆元a^{-1}是b, 如果 a ⊗ b = 1$

例如:

$\begin{align} 3^{-1} & = 5 ( 3 \times 5 \% 7 = 1 ) \\ 4^{-1} & = 2 ( 4 \times 2 \% 7 = 1 ) \end{align}$

除法的定义就是: 乘以它的乘法逆元

栗子🌰4: 模7新世界直线方程-1

现在我们有了新的加法和减法⊕, ⊖ 我们可以像使用旧世界的加减法一样来使用⊕, ⊖. 例如我们可以建立一个简单的, 斜率为1的直线方程:

$y = x ⊕ 3$

新世界里这个直线上的点是: (x,y) ∈ [(0,3), (1,4), (2,5), (3,6), (4,0), (5,1), (6,2)] 只有7个.

如果把这条直线画到坐标系里, 它应该是这个样子的:

y = x ⊕ 3

  y
  ^
|     •
|   •
| •
•
|           •
|         •
+-------•-----> x
1 2 3 4 5 6 

栗子🌰5: 模7新世界直线方程-2

再加上新世界加减乘除四则运算, 我们可以在新世界里进行基本的代数运算了, 例如我们可以设定1个斜率为2的直线方程:

$y = 2 ⊗ x ⊕ 3$

新世界里这个直线上的点是: (x,y) ∈ [(0,3), (1,5), (2,0), (3,2), (4,4), (5,6), (6,1)] 这7个.

如果把这条直线画到坐标系里, 它应该是这个样子的:

y = 2 ⊗ x ⊕ 3

  y
  ^
|          •
| •
|       •
•
|     •
|           •
+---•---------> x
1 2 3 4 5 6 

栗子🌰6: 模7新世界中的二次曲线方程

下面我们来建立1个稍微复杂1点的, 二次曲线的方程:

$y = x^2 ⊕ x ⊕ 2$

这里 $ x^2 $ 表示 $ x ⊗ x $

新世界里这个抛物线上的点集合是: (x,y) ∈ [(0, 2) (1, 4) (2, 1) (3, 0) (4, 1) (5, 4) (6, 2)]

如果把这条抛物线画到坐标系里, 它应该是这个样子的:

y = x^2 ⊕ x ⊕ 2

  y
  ^
|
|
| •       •
|
•           •
|   •   •
+-----•-------> x
1 2 3 4 5 6

可以看出它的图像也遵循了旧世界抛物线的特性: 这条抛物线是以3为轴对称的: 因为类似旧世界的多项式分解一样, 原方程也可以分解成:

$\begin{align} y & = (x ⊕ (-3))^2 \\ & = x^2 ⊕ (-6)x ⊕ 9 \\ & = x^2 ⊕ x ⊕ 2 \end{align}$

模7新世界里的EC

在这个模7的新世界里, 它满足我们旧世界里的四则运算法则, 我们已经可以使用上面提到的 EC 的算法来编码或解码了:

假设模7新世界里我们的数据块 $ d_1 = 3, d_2 = 2 $, 对应上面的直线方程: y = 2 ⊗ x ⊕ 3

我们只要记住2个点的位置, 就能把直线的方程恢复出来:

例如:

我们先记录直线上2个点: (1,5) 和 (3,2)
假设丢失的数据是 $ d_1, d_2 $ 用 $ u_1, u_2 $ 表示, 带入2个点的坐标, 得到一个二元一次方程组:
$\begin{cases} \begin{align} 5 & = u_2 ⊕ u_1 \\ 2 & = u_2 ⊗ 3 ⊕ u_1 \end{align} \end{cases}$
2个方程左右分别相减消元:
$\begin{align} 5 ⊕ (-2) & = u_2 ⊗ (1 ⊕ (-3)) ⊕ u_1 ⊕ (-u_1) \\ 5 ⊕ 5 & = u_2 ⊗ (1 ⊕ 4) \\ 3 & = u_2 ⊗ 5 \end{align}$
最后得到 $ u_2 = 3 ⊗ 5^{-1} = 3 ⊗ 3 = 2 $.

将$ u_2 = 2 $ 带入第1个方程:
$5 = 2 ⊗ 1 ⊕ u_1$
得到 $ u_1 $:
$u_1 = 5 ⊕ (-2) = 3$

至此, 我们用模7新世界的四则运算实现了之前的 EC . 并且我们保证了校验数据的大小是可控的: 不会大于7! 距离我们的目标又接近了1步.

类似的, 我们可以通过模7新世界的抛物线, 来实现k=3, k=4的 EC.

NOTE:
模7下的四则运算构成了1个伽罗华域 Galois-Field: $ GF(7) $.

模7是1个可选的数, 也可以选择模11或其他质数来构造1个 Galois-Field, 但是不能选择模一个合数来建立新的四则运算规则. 假设使用模6, 模6世界里面的2是6的一个因子, 它没有乘法逆元, 也即是说2 乘以 1~5任何一个数在模6的世界里都不是1.

没有乘法逆元就说明模6的世界里没有和旧世界里一样的除法, 不能构成一个完整的四则运算体系.

NOTE:
为了简化本文, 四则里还有几个方面没有提到, 例如乘法加法的分配率. 乘法和加法的结合律也必须满足, 才能在新世界里实现上面例子中的曲线方程等元素. 这部分也很容验证,在上面的模7新世界里是可以满足的.

所以接下来我们需要在所有四则运算里选择一个符合计算机的二进制的四则运算, 作为实现 EC 计算的基础代数结构.

EC使用的新世界 Galois-Field GF(256)

从现在开始, 我们要构造一个现实中真实可以用的伽罗华域, 它比上面模7新世界稍微复杂一点, 得到这个域分为2步:

我们首先选择1个基础的, 只包含2个元素的 Galois-Field $ GF(2) $: {0, 1}.
再在这个 $ GF(2) $ 的基础上建立1个有256个元素的 Galois-Field $ GF(2^8) $.

模2的新世界: Galois-Field GF(2)

首先我们要构建一个最基础的四则运算, 我们先选择了最小的1个Galois-Field, 里面只有2个元素{0,1}:

在这个GF(2)里, 运算的规则也非常简单:

加法(刚好和位运算的异或等价):

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

1的加法逆元就是1 本身.
乘法(刚好和位运算的与等价):

0 ⊗ 0 = 0
0 ⊗ 1 = 0
1 ⊗ 0 = 0
1 ⊗ 1 = 1

1的乘法逆元就是1 本身. 0 没有乘法逆元.

以这个GF(2)为基础, 我们已经可以构建一个1-bit的 EC 算法了:)

下一步我们希望构建1个1 byte大小($ 2^8 $ 个元素)的 Galois-Field $ GF(2^8) $, 在这个 $ GF(2^8) $ 里的 EC 中, 的每个$ d_j $ 和 $ y_i $的取值范围可以是0~255.

我们使用 GF(2) 的元素作为系数, 定义1个多项式:

$a_n x^n + ... + a_2 x^2 + a_1 x^1 + a_0 \\ a_i \in GF(2) = \{0,1\}$

$ a_i $ 的四则运算还是遵循 GF(2) 的规则的, 而多项式的四则运算,基于它的系数的四则运算建立:

例如多项式的加法:

因为 1 + 1 = 0, 所以:
$(x + 1) + (1) = x$
x的同指数幂的系数相加遵循系数的Field的加法规则, 1 + 1 = 0:
$(x^2 + x + 1) + (x) = x^2 + 1$
2个相同的多项式相加肯定是0:
$(x^2 + x + 1) + (x^2 + x + 1) = 0$

多项式的乘法和旧世界的多项式乘法类似, 仍然是通过乘法的分配率展开多项式:

$\begin{align} (x + 1) (x + 1) & = x (x+1) + (x+1) \\ & = x^2 + x + x + 1 \\ & = x^2 + 1 \end{align}$

多项式的除法依旧使用旧世界的多项式长除法法则, 唯一不同仍旧是系数的四则运算是基于GF(2)的:

例如:

$\begin{align} \frac{x^3 + 1}{x + 1} = x^2 + x + 1 \end{align}$

多项式的除法的取余计算也类似:

$x^2 + x + 1 = x (x+1) + 1 \\ (x^2 + x + 1) = 1 \pmod (x+1)$

然后我们还发现, 这些多项式和二进制数是有一一对应关系的, 多项式中指数为i的项的系数就是二进制数第i位的值:

$\begin{align} 1 & \rightarrow 1 \\ x^2 + 1 & \rightarrow 101 \\ x^3 + x & \rightarrow 1010 \end{align}$

现在我们可以使用多项式表达的二进制整数的全集. 然后就像上面栗子中的 GF(7) 那样, 通过取模的方式, 将多项式的集合构造1个取模的伽罗华域.

首先让我们来熟悉下如何从较小的域扩张到较大的域.

域的扩张 Field-Extension

域的扩张大家应该是非常熟悉的, 只是一般并没有用这个专用的称呼去描述我们平时见到的扩展.

域的扩张经常是通过多项式来完成的.

栗子🌰7: 实数到虚数的扩张

例如我们首先有了实数, 以实数为系数的多项式中, 如果我们选择一个多项式来构造一个方程:

$\begin{equation} x^2 + 1 = 0 \end{equation}$

这个方程在实数域里是无解的, 但在复数范围内是有解的: $ x = \pm \sqrt{-1} = \pm i $.

这样通过一个实数系数的, 但在实数域中没有根的方程, 我们得到了复数 Complex-Number 的定义,

复数就是: 所有实系数多项式模 $ x^2+1 $ 的余多项式的集合:

$\mathbb {C} =\mathbb {R} [X]/(X^{2}+1).$

上面所有的余多项式可以表示为: $ a x + b $, a, b都是实数.

这里$ a x + b $ 就是我们熟悉的复数: 多项式 x 对应虚数单位i, 1对应实数单位1.

而任意2个多项式的四则运算, 也对应复数的四则运算, 例如, 设: $ p(x) = x^2 + 1 $

多项式($\pmod{p(x)}$)	复数
$ x + (x+1) = 2x+1 $	$ i + (1+i) = 1+2i $
$ x · x = -1 $	$ i · i = -1 $
$ (3x+1)·(x-2) = -5x-5 $	$ (1+3i)·(-2+i) = -5-5i $

类似于将实数扩张到复数, 我们也可以将GF(2) 扩张到 $ GF(2^8) $.

从2到256: 扩张 GF(2)

域的扩张就是在现有域为系数的多项式中, 找到1个质的多项式 Prime-Polynomial, 再将所有多项式模它得到的结果的集合就是域的扩张.

例如 $ x^2 + 1 $ 在实数域下就是 质多项式, 它无法分解成2个多项式乘积.

栗子🌰8: GF(2) 下的质多项式

1 是1个质多项式.
$ x + 1 $ 是1个质多项式. 因为它最高次幂是1, 肯定不能再拆分成2个多项式乘积了(只能拆分成1次多项式和常数的乘积).
2次的质多项式是: $ P_2(x) = x^2 + x + 1 $. 它在GF(2)的域中不能被拆分成2个1次多项式的乘积.

我们可以像使用7对所有整数取模那样, 用它对所有多项式取模, 模它而产生的所有 余多项式, 包含所有最高次幂小于2的4个多项式: $ 0, 1, x, (x + 1) $

这4个多项式就是 GF(2) 在多项式 $P_2(x)$ 的扩张: 我们把{0, 1} 2个元素的域扩张成 4个元素的域.

这4个多项式可以表示成4个2bit的二进制数:00,01,10,11

GF(2) 扩张成 GF(2^8)

为了扩张到 $ GF(2^8) $ 我们选择的8次幂的质多项式是:

$P_8(x) = x^8 + x^4 + x^3 + x + 1$

因为多项式和二进制数的直接对应关系, $ P_8(x) $ 对应:

二进制: 1 0001 1011
16进制: 0x11b

而GF(256)中的四则运算如下:

加法: $ a ⊕ b $ 对应多项式加法, 同时它表示的二进制数的加法对应: a ^ b
乘法: $ a ⊗ b $ 对应多项式的乘法(模$P_8(x)$):

总结一下GF(256)能够满足EC运算的几个性质:

加法单位元: 0
乘法单位元: 1
每个元素对加法都有逆元(可以实现减法): 逆元就是它本身( (x+1) + (x+1) = 0 )
每个元素对乘法都有逆元(除了0)(可以实现除法):$P_8(x)$是不可约的, 因此不存在a和b都不是0但ab=0; 又因为GF(256)只有255个非0元素, 因此对a,总能找到1个x使得 $ a^x = a $. 所以 $a^{x-2} a = 1$ $ a^{x-2} $是a的乘法逆元.
乘法和加法满足分配率: 基于多项式乘法和加法的定义.

满足这些性质的四则运算, 就可以用来建立高次曲线, 进而在GF(256)上实现EC.

实现

标准EC的实现

以上讨论的是标准的EC的原理, 现在我们将以上的内容总结, 应用到实践上面.

四则运算基于 $ GF(2^8) $ 或 $ GF(2^{16}), GF(2^{32}) $, 分别对应1字节, 2字节或4字节.
$ GF(2^8) $ 下的加减法直接用异或计算, 不需要其他的工作.

$ GF(2^8) $ 下的乘法和除法用查表的方式实现.

首先生成 $ GF(2^8) $ 下对2的指数表和对数表, 然后把乘除法转换成取对数和取幂的操作:

以 $ GF(2^8) $ 为例:

生成指数表 $ 2^0, 2^1, 2^2… $的表, 表中元素 $ p_i = 2^i $.
生成对数表, 表中元素 $ l_i = log_2i $.

生成2个表的代码很简单, 用python表示如下:

power, log = [0] * 256, [0] * 256
n = 1
for i in range(0, 256):

    power[i] = n
    log[n] = i

    n *= 2

    # modular by the prime polynomial: P_8(x) = x^8 + x^4 + x^3 + x + 1
    if n >= 256:
        n = n ^ 0x11b

log[1] = 0 # log[1] is 255, but it should be 0

指数表:
01 02 04 08 10 20 40 80 1d 3a 74 e8 cd 87 13 26
4c 98 2d 5a b4 75 ea c9 8f 03 06 0c 18 30 60 c0
9d 27 4e 9c 25 4a 94 35 6a d4 b5 77 ee c1 9f 23
46 8c 05 0a 14 28 50 a0 5d ba 69 d2 b9 6f de a1
5f be 61 c2 99 2f 5e bc 65 ca 89 0f 1e 3c 78 f0
fd e7 d3 bb 6b d6 b1 7f fe e1 df a3 5b b6 71 e2
d9 af 43 86 11 22 44 88 0d 1a 34 68 d0 bd 67 ce
81 1f 3e 7c f8 ed c7 93 3b 76 ec c5 97 33 66 cc
85 17 2e 5c b8 6d da a9 4f 9e 21 42 84 15 2a 54
a8 4d 9a 29 52 a4 55 aa 49 92 39 72 e4 d5 b7 73
e6 d1 bf 63 c6 91 3f 7e fc e5 d7 b3 7b f6 f1 ff
e3 db ab 4b 96 31 62 c4 95 37 6e dc a5 57 ae 41
82 19 32 64 c8 8d 07 0e 1c 38 70 e0 dd a7 53 a6
51 a2 59 b2 79 f2 f9 ef c3 9b 2b 56 ac 45 8a 09
12 24 48 90 3d 7a f4 f5 f7 f3 fb eb cb 8b 0b 16
2c 58 b0 7d fa e9 cf 83 1b 36 6c d8 ad 47 8e 01

对数表(0没有以2为底的对数):
00 00 01 19 02 32 1a c6 03 df 33 ee 1b 68 c7 4b
04 64 e0 0e 34 8d ef 81 1c c1 69 f8 c8 08 4c 71
05 8a 65 2f e1 24 0f 21 35 93 8e da f0 12 82 45
1d b5 c2 7d 6a 27 f9 b9 c9 9a 09 78 4d e4 72 a6
06 bf 8b 62 66 dd 30 fd e2 98 25 b3 10 91 22 88
36 d0 94 ce 8f 96 db bd f1 d2 13 5c 83 38 46 40
1e 42 b6 a3 c3 48 7e 6e 6b 3a 28 54 fa 85 ba 3d
ca 5e 9b 9f 0a 15 79 2b 4e d4 e5 ac 73 f3 a7 57
07 70 c0 f7 8c 80 63 0d 67 4a de ed 31 c5 fe 18
e3 a5 99 77 26 b8 b4 7c 11 44 92 d9 23 20 89 2e
37 3f d1 5b 95 bc cf cd 90 87 97 b2 dc fc be 61
f2 56 d3 ab 14 2a 5d 9e 84 3c 39 53 47 6d 41 a2
1f 2d 43 d8 b7 7b a4 76 c4 17 49 ec 7f 0c 6f f6
6c a1 3b 52 29 9d 55 aa fb 60 86 b1 bb cc 3e 5a
cb 59 5f b0 9c a9 a0 51 0b f5 16 eb 7a 75 2c d7
4f ae d5 e9 e6 e7 ad e8 74 d6 f4 ea a8 50 58 af

在计算 $ GF(2^8) $中的乘法将 a, b 通过查对数表和指数表实现: $ a \times b = 2^{log_2a+log_2b} $.

NOTE:
Galois-Field 的计算目前实现都是基于查表的, 所以选择大的域虽然可以一次计算多个字节, 但内存中随机访问一个大表也可能会造成cache miss太多而影响性能.

一般CPU都没有支持GF乘除法的指令, 但有些专用的硬件卡专门加速GF的乘除法.

生成GF后, 选择一个系数矩阵, 常用的是 Vandermonde 或 Cauchy.

EC编码: 校验数据生成

通常使用1个矩阵来表示输入和输出的关系 (而不是像上文中只使用校验块的生成矩阵), 这里选择自然数生成的 Vandermonde 矩阵:

这个矩阵里上面是1个大小为k的单位矩阵, 表示 $ d_j $ 的输入和输出不变.

下面一部分是1个 $ m \times k $ 的矩阵表示校验块的计算.

对要存储的k组数据, 逐字节读入, 形成 $ d_1, d_2…d_k $, 进行矩阵乘法运算, 得到最后要存储的 k 个数据块和 m 个校验块.

之所以把单位矩阵也放到编码矩阵上面, 看起来没有什么用, 只是把输入无变化的输出出来的这种风格, 原因在于在编码理论中, 并不是所有的生成的Code都是k个原始数据和 m个校验数据的形式, 有些编码算法是将k个输入变成完全不1样的k+m个输出, 对这类编码算法, 需要1个k*(k+m)的编码矩阵来表示全部的转换过程. 例如著名的 Hamming-7-4 编码的编码矩阵(输入k=4, 输出k+m=7):
$\begin{pmatrix} 1&1&0&1\\ 1&0&1&1\\ 1&0&0&0\\ 0&1&1&1\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ \end{pmatrix}$
EC中也使用了k*(k+m)的编码矩阵.

EC解码

当数据损坏时, 通过生成解码矩阵来恢复数据:

对所有丢失的数据, 将它对应的第i行从编码矩阵中移除, 移除后, 保留编码矩阵的前k行, 构成1个k*k的矩阵.

最后求逆矩阵, 和没有丢失的块相乘, 就可以恢复出丢失的数据块 $ u_2, u_3 $:

因为只有 $ u_2, u_3 $ 丢失了, 矩阵相乘时只需要计算逆矩阵的第2, 3行.

Vandermonde 矩阵的可逆性

实数下的Vandermonde 矩阵是一定可逆的, 但它的任意n行n列组成的子矩阵不一定是可逆的.

假设一个 Vandermonde 矩阵, 如果存在一个 $ [ a_1, a_2, a_3 ] $, 使得乘积为全0, 则矩阵n列是线性相关的:

$\begin{bmatrix} 1 & 1 & 1 \\ 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \\ \end{bmatrix} \times \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}$

但如果查看一个 Vandermonde 矩阵的子矩阵($ 0 < u < v $):

$\begin{bmatrix} 1 & 1 & 1 \\ 1 & x_1^u & x_1^v \\ 1 & x_2^u & x_2^v \\ \end{bmatrix} \times \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \end{bmatrix}$

因为方程: $ a_1 + a_2 x^u + a_3 x^v = 0 $ 最多有v个解, 只要v 大于2, 就可能找到一组 $ a_i $ 和 $ x_i $, 使得上面的子矩阵线性相关.

例如, 一个子矩阵, x=-1 时, 矩阵不可逆:

$\begin{bmatrix} 1 & 1 \\ 1 & x^2 \\ \end{bmatrix}$

GF256 下的 Vandermonde 矩阵的可逆性

在 $ GF(2^8) $ 下的 Vandermonde 矩阵, 除了上面的的不可逆情况外, 还有另外一种情况导致子矩阵不可逆.

举例来说, 以下矩阵是缺失 $ u_1, u_4 $ 情况下的用来恢复数据的矩阵, 它可能不可逆: 如果 $ x^3 == 1 $,

由于2是1个生成元, 容易看出, $ x = 2^{85} $ 是1个不可逆的情况: $ x^3 = 1 $ 于是第1列和第4列完全一样.

$\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & x & x^2 & x^3 & x^4 \\ \end{bmatrix}$

Cauchy 矩阵的任意n行n列组成的矩阵都是可逆的, 因为任意子矩阵还是 Cauchy矩阵.

数据恢复IO优化: LRC: [Local-Reconstruction-Code]

当 EC 进行数据恢复的时候, 需要k个块参与数据恢复, 直观上, 每个数据块损坏都需要k倍的IO消耗.

为了缓解这个问题, 一种略微提高冗余度, 但可以大大降低恢复IO的算法被提出: [Local-Reconstruction-Code], 简称 LRC.

LRC的思路很简单, 在原来的 EC 的基础上, 对所有的数据块分组对每组在做1次 $ k’ + 1 $ 的 EC. k’ 是二次分组的每组的数据块的数量.

LRC 的校验块生成

最终保存的块是所有的数据块: $ d_1, d_2, d_3, d_4, d_5, d_6 $, 和校验块 $ y_{1,1}, y_{1,2}, y_2, y_3 $.

这里不需要保存 $ y_1 $ 因为 $ y_1 = y_{1,1} + y_{1,2} $

对于 LRC的EC来说, 它的生成矩阵前k行不变, 去掉了标准EC的第k+1行, 多出2个局部的校验行:

LRC 的数据恢复

LRC 的数据恢复和标准的EC类似, 除了2点不同:

在选择校验块的行生成解码矩阵的时候, 如果某第k+i行没有覆盖到任何损坏的数据的话, 是无法提供有效性信息, 需要跳过的.

例如 $ d_4 $ 损坏时, 不能像标准EC那样选择第7行 1 1 1 0 0 0 这行作为补充的校验行生成解码矩阵, 必须略过第7行, 使用第8行.
不是所有的情况下, m个数据损坏都可以通过加入m个校验行来恢复. 因为LRC的生成矩阵没有遵循 Vandermonde 矩阵的规则, 不能保证任意k行都是满秩的.

工程优化

插播一条广告: 徐同学的博客中给出了很好的EC工程实现的介绍, 推荐!: 实现高性能纠删码引擎

分析

可靠性分析

$\sum_{i=m+1}^{k+m} {k+m \choose i} p^{i} (1-p)^{k+m-i}$

这里p是单块数据丢失的风险,一般选择磁盘的日损坏率: 大约是0.0001. p一般很小所以近似就只看第1项:

${k+m \choose m+1} p^{m+1} (1-p)^{k-1}$

2个校验块和3副本的可靠性对比(取m=2):

k	m	丢数据风险
1	2	$ 1 \times 10^{-12} $ (1个数据块+2个校验块可靠性和 3副本等价)
2	2	$ 3 \times 10^{-12} $
3	2	$ 9 \times 10^{-12} $
10	2	$ 2 \times 10^{-10} $ (10+2 和 12盘服务器的 RAID-6 等价)
32	2	$ 5 \times 10^{-9} $
64	2	$ 4 \times 10^{-8} $

3个校验块和4副本的可靠性对比(取m=3):

k	m	丢数据风险
1	3	$ 1 \times 10^{-16} $ (1个数据块+3个校验块可靠性和 4副本等价)
2	3	$ 5 \times 10^{-16} $
3	3	$ 2 \times 10^{-15} $
10	3	$ 7 \times 10^{-14} $
32	3	$ 5 \times 10^{-12} $
64	3	$ 7 \times 10^{-11} $

4个校验块和5副本的可靠性对比(取m=4):

k	m	丢数据风险
1	4	$ 1 \times 10^{-20} $ (1个数据块+4个校验块可靠性和 5副本等价)
2	4	$ 6 \times 10^{-20} $
3	4	$ 2 \times 10^{-19} $
10	4	$ 2 \times 10^{-17} $
32	4	$ 4 \times 10^{-15} $
64	4	$ 1 \times 10^{-13} $

IO消耗

以一个 EC 组来分析, 1个块损坏的概率是 $ p $, 这个组中有块损坏的概率是: $ 1 - (1-p)^{k+m} \approx (k+m)p $

每存储一个字节一天数据恢复产生的传输量是(blocksize是一个数据块或校验块的大小):

$\frac{(k+m)p \times (k+m) \times blocksize} {(k+m) \times blocksize} = (k+m)p$

也就是说, 使用 EC 每存储1TB的数据, 每天(因为我们取的数据损坏概率是按天计算的)用于数据恢复而产生的IO是 k * 0.1GB / TB

磁盘的IO大致上也等同于网络流量, 因为大部分实现必须将数据分布到不同的服务器上.

NOTE:
随着 k的增加, 整体成本虽然会下降(1+m/k), 但数据恢复的IO开销也会随着k(近似于)线性的增长.

例如:

假设k+m = 12:

如果整个集群有 100PB 数据, 每天用于恢复数据的网络传输是 100TB.

但一般来说数据恢复不会在时间上很均匀的分布, 这个带宽消耗需要预估10倍到100倍.

参考

实现高性能纠删码引擎

hash表中key的分布规律

当hash表中key和bucket数量一样时(n/b=1):

key的数量对3类bucket数量的影响

key的数量对bucket的均匀程度的影响

Load Factor: n/b<0.75

Load Factor: n/b>1

n/b 越大, key的分布越均匀.

计算

每类bucket的数量

空bucket 数量

有1个key的bucket的数量

多个key的bucket

key在bucket中分布的均匀程度

通过正太正态分布来近似

计算最小key数量 x

程序模拟

Reference

结论

性能对比

白山CDN支持和建议应用场景

延伸阅读： ChaCha20算法原理

ChaCha20的keystream生成

TLS中的ChaCha20

1 协议发展历程

2 安全强化

2.1 密钥交换

2.1.1 完全支持PFS

2.1.2 废弃DSA证书

2.1.3 RSA填充模式更改

2.1.4 禁用自定义的DH组参数

2.2 对称加密

2.2.1 禁用CBC模式

2.2.2 禁用RC4流加密算法

2.2.3 禁用SHA1

2.2.4 禁用出口密码套件

2.3 禁用TLS压缩

2.4 加密握手消息

3 效率提升

3.1 2-RTT

3.2 1-RTT

3.3 0-RTT

4 总结

Primitive

Scheme

内容简介

分布式系统的可靠性问题: 冗余和多副本

EC的基本原理

栗子🌰1: 实现k+1的冗余策略, 大概需要小学3年级的数学知识

栗子🌰2: 实现k+m的冗余策略, 大概需要初中2年级的数学知识

增加1个校验块, 变成k+2

实现k+m 的冗余

EC编码矩阵的几何解释

k=2, 为2个数据块生成冗余校验块

k=3, 4, 5…时的数据块的冗余

通过高次曲线生成冗余数据

从曲线方程得到的系数矩阵

EC解码过程: 求解n元一次方程组

Vandermonde 矩阵保证方程组有解

新世界: 伽罗华域 Galois-Field GF(7)

EC在计算机里的实现: 基于 伽罗华域 Galois-Field

栗子🌰3: 只有7个数字的新世界: GF(7)

模7新世界中的 加法

模7新世界中的 减法

模7新世界中的 乘法 和 除法

栗子🌰4: 模7新世界直线方程-1

栗子🌰5: 模7新世界直线方程-2

栗子🌰6: 模7新世界中的二次曲线方程

模7新世界里的EC

EC使用的新世界 Galois-Field GF(256)

模2的新世界: Galois-Field GF(2)

域的扩张 Field-Extension

栗子🌰7: 实数到虚数的扩张

从2到256: 扩张 GF(2)

栗子🌰8: GF(2) 下的质多项式

GF(2) 扩张成 GF(2^8)

实现

标准EC的实现

EC编码: 校验数据生成

EC解码

Vandermonde 矩阵的可逆性

当hash表中key和bucket数量一样时(`n/b=1`):

Load Factor: `n/b<0.75`

Load Factor: `n/b>1`

`n/b` 越大, key的分布越均匀.

计算最小key数量 `x`

EC在计算机里的实现: 基于伽罗华域 Galois-Field

模7新世界中的加法

模7新世界中的减法

模7新世界中的乘法和除法

EC在计算机里的实现: 基于伽罗华域 Galois-Field

模7新世界中的加法

模7新世界中的减法

模7新世界中的乘法和除法