为什么去中心化存储也能保证数据不丢失?
最近,我写了不少文章之后,不少热心网友留言,去中心化存储最担心的问题是数据丢失问题。我往里面存放了数据之后,虽然有更便宜,更快,更隐私等特点,但是数据毕竟存在于矿工的矿机上,由于矿工的不稳定性,可能导致文件的丢失。就像滴滴的司机一样,大部分时间是靠谱的,偶尔不靠谱,不靠谱的时候,体验非常差,这样的产品我不敢用。而大公司提供的服务,如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种冗余模式:全副本模式全副本模式就是把文件,完整地拷贝,新文件和老文件一模一样,这样做并不节约空间,但是P2P能多点下载数据,更快,同时可以保证用户下载体验。纠删副本模式纠删副本模式就是通过纠删技术来做冗余。简单地说就是,数据分成碎片并编码,使用可配置数量的冗余分片,且不同部件存储在不同矿工上。这样做不利于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)^(τ/t) = 0.4265318778%PP.io设计的默认全副本数冗余2倍,纠删副本冗余是1.5倍。我们先看全副本模式:由于全副本是完全复制,所以是2倍的冗余,也就是有2个副本。我们称为N=2。修复时间内的耐用率:Pa = 1- p^2 = 99.9981807056%全年耐用率:Pya = 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,这是已知发生数。这里讲解一下概率论中的经典公式,泊松分布拟合公式:
简单理解一下,泊松分布拟合公式就是观察事物平均发生m次的条件下,实际发生x次的概率。要了解推导细节,可以看最后的附录。我们套用泊松分布拟合公式就可以得到:
即 Pb = 99.9999912252%那么全年的耐用率:Pyb = Pb^(365*t/τ) = 99.9615738663%可以看到,虽然更小冗余,但纠删模式对比起全副本模式的耐用率高很多。计算汇总:我们把2种冗余模式结合起来,可以得到最终的耐用率:修复时间内耐用率:P = 1 – (1-Pa)(1-Pb) = 99.9999999998%全年耐用率:Py = P^(365*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。得到Pyb = 99.9999998852%如果再考虑2个全副本冗余,则全年耐用率:Py = 99.9999999999%PP.io将让开发者灵活设置参数我在设计PP.io架构的时候,给予开发者足够的灵活性,可以根据自身的情况设置不同的参数,其中包括:全副本数 N, 纠删算法参数 (k,N)。开发者可以根据自身的需求,如传输速度,价格(冗余度越高,价格越高),能接受的耐用率来配置参数,从而满足自己的产品要求。PP.io给开发者提供一个去中心化的存储和分发网络,使得更便宜,更快,更隐私。附录:泊松分布拟合公式推导假设 p 为单个设备单位时间内的故障率,则 n 个设备在单位时间内,有 k 个设备发生故障的概率 P(k) 为:
展开组合:
假设 p 很小,n 很大,一般地当 n > 20, p < 0.05 时。
令
最后得到泊松分布公式,即,已知单位时间内平均有 λ 个设备故障,计算单位时间内有k个设备故障的概率。
参考: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.