为什么去中心化存储也能保证数据不丢失

作者: omnigeeker | 来源:发表于2018-11-26 10:02 被阅读0次

最近，我写了不少文章之后，不少热心网友留言，去中心化存储最担心的问题是数据丢失问题。我往里面存放了数据之后，虽然有更便宜，更快，更隐私等特点，但是数据毕竟存在于矿工的矿机上，由于矿工的不稳定性，可能导致文件的丢失。就像滴滴的司机一样，大部分时间是靠谱的，偶尔不靠谱，不靠谱的时候，体验非常差，这样的产品我不敢用。而大公司提供的服务，如AWS S3，是专业机房，专业机器，专业硬盘，能保证数据不丢失。

其实不是这样的，我在设计PP.io的时候，早就考虑到这个问题，所以我专门写篇文章来解释这个问题。

首先，我先纠正几个认知误区：

1. AWS S3等大公司能100%的保证文件不丢失吗?

其实不然，他们也只能99.999999999%的保证文件不丢，11个9的保证文件不丢。存储行业称这个服务质量指标(QoS)参数为耐用率。

2. 矿工可能不稳定。

P2P的技术核心，就是在多个不稳定的节点上，实现稳定的服务。回想一下我之前做过的PPTV，也就是P2P直播，正是在多个不稳定的节点上完成了稳定的服务。

下面我来详细解释PP.io是如何把这个耐用率做到非常高的。

PP.io 的2种冗余模式

我在设计PP.io的时候，设计2种冗余模式：

1.全副本模式

全副本模式就是把文件，完整地拷贝，新文件和老文件一模一样，这样做并不节约空间，但是P2P能多点下载数据，更快，同时可以保证用户下载体验。

2.纠删副本模式

纠删副本模式就是通过纠删技术来做冗余。简单地说就是，数据分成碎片并编码，使用可配置数量的冗余分片，且不同部件存储在不同矿工上。这样做不利于P2P多点传输，但是可以大大节约冗余空间。

PP.io就是把这两种冗余模式结合起来实现的。不同场景侧重于运用不同的冗余方式。

下面简单说一下纠删技术产生的数学特征：

我们用 (k,n) 纠删码来编码数据，其中总共有n个纠删片段，k表示在n个纠删片段中，任何k个7纠删片段就能完全恢复原始数据。如果数据大小是s字节，则每个纠删片段的大小大约是s/k 字节。如果k = 1时就是相当于复制一个全副本。例如，1MB数据, 如果采用（10,16）纠删码，并且每个纠删片段大小是0.1M，则总存储数据大小就是1.6M。它实际总共用了1.6倍的数据空间大小。

PP.io的假设和计算

做如下假设：

我们令t为单位假设时间，这里先假设t=24小时

Pt代表矿工的日掉线率，我们这里假设Pt=5%。

τ为副本丢失后的修复时间，也就是如果副本丢失了，多少时间能够修复。我们假设τ=2小时。

在可以修复的前提下，将以上值带入下面的公式，算得单副本丢失每天丢失的概率是：

$p = 1 – (1-Pt)^{\frac{t}{τ}} = 0.4265318778%$

PP.io设计的默认全副本数冗余2倍，纠删副本冗余是1.5倍。

我们先看全副本模式：

由于全副本是完全复制，所以是2倍的冗余，也就是有2个副本。我们称为N=2。

修复时间内的耐用率:

$P_a = 1- p^2 = 99.9981807056%$

全年耐用率:

$P_{ya} = Pa^{(365*t/τ)} = 92.3406415922%$

我们再看纠删模式：

假设我们采用的纠删算法是 (k,n）= (6,9)。相当于6M的数据，每个纠删分片是1M，一共要存放9个纠删分片，任意6个分片就能恢复出完整的数据，这样存放在9个矿工上，另外实际占用的空间大小是9M。如果理解了，我们继续往下看。

由于纠删算法是(k,n), 那么冗余就是 $F = n/k = 1.5$ 。

在修复时间内分片丢失数就是：

$m = n*p = 0.038387869$ ，这是已知发生数。

这里讲解一下概率论中的经典公式，泊松分布拟合公式：
$P(x) = \frac{m^x}{x!}e^{-m}$

简单理解一下，泊松分布拟合公式就是观察事物平均发生m次的条件下，实际发生x次的概率。要了解推导细节，可以看最后的附录。

我们套用泊松分布拟合公式就可以得到：
$Pb=\sum_{i=0}^{n-k}P\left(i\right)$

即 $P_b = 99.9999912252%$

那么全年的耐用率：

$P_{yb} = Pb^{(365\frac{t}{τ})} = 99.9615738663%$

可以看到，虽然更小冗余，但纠删模式对比起全副本模式的耐用率高很多。

计算汇总：

我们把2种冗余模式结合起来，可以得到最终的耐用率：

修复时间内耐用率：

$P = 1 – (1-Pa)(1-Pb) = 99.9999999998%$

全年耐用率：

$P_y = P^{(365\frac{t}{τ})} = 99.9999993008%$

看看，已经达到8个9的耐用率。也就是说假设你如果存放了1亿个文件，一年只会丢失1个文件。你说可靠不？

还能提高

上面的假设，是基于 (k,n）= (6,9), 冗余度为F=1.5。如果适当提高冗余度 F，或者提高k，还能提高全年的耐用率 Py。下面一个表格就是调整 k和F之后对全年耐用率产生的影响。

我们这里做了一个新的假设，完全没有全副本，只有纠删分片。这样做，不追求速度，只追求价格最便宜。这时候，Py 就等于 Pyb。即：

可以看出，冗余度F越高，耐用率越高。同时, 分片数n越多，耐用率越高。n对耐用度的影响更为敏感，但是n越大，也就意味这需要的矿工越多。

也可以看出，如果要追求12个9，即99.9999999999。采用纠删模式，在冗余度2的情况下，分成16个纠删副本就能做到。同样，在冗余度2.5的情况下，分成12个纠删副本就能做到。这样就超过 AWS S3企业级存储服务的年耐用率(11个9)。

还能再提高

除了调整 N, (k,n), F 这些参数，可以提高耐用率之外，还可以通过自身的优化努力。其实还有很大的提升空间，前面说过，这个测算是基于2个前提假设的。而这两个假设本身还有很大的提升空间。

单副本的每日丢失率Pt, 我假设是5%。这个假设本身是可以通过token经济系统的设计来降低的。更合理的经济系统可以提高矿工的稳定性和在线率。如果矿工稳定了，这个值就会下降；这个值越低，全年的耐用率就会增加。这个值有望降至1%甚至更低。

副本丢失后的修复时间 τ，我假设是2小时。这个假设也可以通过PP.io自身的算法来优化，只要能更快地发现副本丢失，能更快地增加副本数来保证副本数充足，τ值就会越低；τ值越低，全年的耐用率就会增加。如果算法做到极致的话，这个值有望降至15分钟。

假设做到了极限值Pt=1%，τ=0.25小时，（k,n）=（6,9）纠删副本冗余度 F=1.5。

得到 $P_{yb} = 99.9999998852%$

如果再考虑2个全副本冗余，则全年耐用率：

$P_y = 99.9999999999%$

PP.io将让开发者灵活设置参数

我在设计PP.io架构的时候，给予开发者足够的灵活性，可以根据自身的情况设置不同的参数，其中包括：全副本数 N, 纠删算法参数 (k,N)。

开发者可以根据自身的需求，如传输速度，价格（冗余度越高，价格越高），能接受的耐用率来配置参数，从而满足自己的产品要求。

PP.io给开发者提供一个去中心化的存储和分发网络，使得更便宜，更快，更隐私。

附录：泊松分布拟合公式推导

假设 $p$ 为单个设备单位时间内的故障率，则 $n$ 个设备在单位时间内，有 k 个设备发生故障的概率 $P(k)$ 为：
$P(k) = {n \choose k}p^{k}(1-p)^{n-k}$

展开组合：
$P(k) = \frac{n(n-1)\cdots(n-k+1)}{k!}p^{k}(1-p)^{n-k}$
$P(k) = \frac{n(n-1)\cdots(n-k+1)}{k!}\frac{p^{k}(1-p)^{n}}{(1-p)^{k}}$
$P(k) = \frac{(np)(np-p)\cdots(np-kp+p)}{k!}\frac{(1-p)^{ \frac{1}{p} {np}}}{(1-p)^{k}}$

假设 p 很小，n 很大，一般地当 n > 20, p < 0.05 时。
$\because \lim \limits_{p \to 0} (1-p)^{-\frac{1}{p}} \to e$
$n \to +\infty, p \to 0$
$\therefore P(k) \approx \frac{(np)(np-p)\cdots(np-kp+p)}{k!}\frac{e^{-{np}}}{(1)^{k}}$
$P(k) \approx \frac{(np)^k}{k!}e^{-{np}}$
令
$Latex: \lambda = np$
最后得到泊松分布公式，即，已知单位时间内平均有 $\lambda$ 个设备故障，计算单位时间内有 $k$ 个设备故障的概率。

$Latex: P(k) = \frac{\lambda^k}{k!}e^{-\lambda}$

参考：

1.ttps://www.scality.com/blog/durability-availability-managing-fragile-scarce/

2.Hakim Weatherspoon and John D. Kubiatowicz, Erasure Coding vs. Replication: A Quantitative Comparison.

3.Byung-Gon Chun, Frank Dabek, Andreas Haeberlen, Emil Sit, Hakim Weatherspoon, M. Frans Kaashoek, John Kubiatowicz, and Robert Morris, Efficient Replica Maintenance for Distributed Storage Systems.

文章作者：Wayne Wong

转载请注明出处

如果有关于PPIO学习的交流，可以通过下面的方式联系我：

加我微信，注意备注: 区块链

wechat：omnigeeker

为什么去中心化存储也能保证数据不丢失

PP.io 的2种冗余模式

下面简单说一下纠删技术产生的数学特征：

PP.io的假设和计算

计算汇总：

还能提高

还能再提高

PP.io将让开发者灵活设置参数

附录：泊松分布拟合公式推导

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读