Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文
1. AWS S3等大公司能100%的保证文件不丢失吗?
/ Z. j0 z& J) \其实不然,他们也只能99.999999999%的保证文件不丢,11个9的保证文件不丢。存储行业称这个服务质量指标(QoS)参数为耐用率。
) J, o# p4 b# n, Y
( s2 l; P1 k. R0 O2. 矿工可能不稳定。; `) G& h4 r0 ^. v, g9 j  |& W
P2P的技术核心,就是在多个不稳定的节点上,实现稳定的服务。回想一下我之前做过的PPTV,也就是P2P直播,正是在多个不稳定的节点上完成了稳定的服务。5 R, }. l* Z4 E# M, w" ]/ Y; T
下面我来详细解释PP.io是如何把这个耐用率做到非常高的。8 @; x3 B  w' p- J% P
PP.io 的2种冗余模式; h5 ~, A/ r" b# F1 c; [
我在设计PP.io的时候,设计2种冗余模式:
( [# B5 |) }0 D: r1.​全副本模式7 K6 v' E, b& ?. l' `
全副本模式就是把文件,完整地拷贝,新文件和老文件一模一样,这样做并不节约空间,但是P2P能多点下载数据,更快,同时可以保证用户下载体验。
4 ?, b7 o2 _1 d  i: y$ ~2.​纠删副本模式
8 I2 b# Y& H1 Z# `* w& Y: ^纠删副本模式就是通过纠删技术来做冗余。简单地说就是,数据分成碎片并编码,使用可配置数量的冗余分片,且不同部件存储在不同矿工上。这样做不利于P2P多点传输,但是可以大大节约冗余空间。1 m8 s* r+ c2 L5 i1 ]
PP.io就是把这两种冗余模式结合起来实现的。不同场景侧重于运用不同的冗余方式。8 E7 R, h# u& d1 h
下面简单说一下纠删技术产生的数学特征:# |* k. n9 x0 `( q; R% d  G5 C" Q
我们用 (k,n) 纠删码来编码数据,其中总共有n个纠删片段,k表示在n个纠删片段中,任何k个7纠删片段就能完全恢复原始数据。如果数据大小是s字节,则每个纠删片段的大小大约是s/k 字节。如果k = 1时就是相当于复制一个全副本。例如,1MB数据, 如果采用(10,16)纠删码,并且每个纠删片段大小是0.1M,则总存储数据大小就是1.6M。它实际总共用了1.6倍的数据空间大小。1 X. L+ v5 t# w5 a. N3 N' b
PP.io的假设和计算
6 S. b! K7 ?/ O7 l7 @做如下假设:  ]9 Y2 x1 l0 C; q
我们令t为单位假设时间,这里先假设t=24小时: H2 P1 r* C" R( d2 K" n
Pt代表矿工的日掉线率,我们这里假设Pt=5%。
1 Z6 p; r$ a# S5 m$ E0 j; Eτ为副本丢失后的修复时间,也就是如果副本丢失了,多少时间能够修复。我们假设τ=2小时。
4 p0 Q9 {/ {( d3 `8 v; l0 _在可以修复的前提下,将以上值带入下面的公式,算得单副本丢失每天丢失的概率是:
) L9 [1 e" O! U4 w$p = 1 – (1-Pt)^{\frac{t}{τ}} = 0.4265318778%$/ V$ e0 }2 m( X* ^5 z& s
PP.io设计的默认全副本数冗余2倍,纠删副本冗余是1.5倍。6 h8 t) M; l0 ?
我们先看全副本模式:
- y& i: T8 x) [由于全副本是完全复制,所以是2倍的冗余,也就是有2个副本。我们称为N=2。2 d' a+ v$ O; n1 d% a
修复时间内的耐用率:
4 a* T1 a. a; w' v& j0 |$$P_a = 1- p^2 = 99.9981807056%$$
3 H1 w$ T7 s( J全年耐用率:% N+ x  E: l; H! ~" ^- ?
$$P_{ya} = Pa^{(365*t/τ)} = 92.3406415922%$$3 y# x. q" n* h3 G/ |3 V
我们再看纠删模式:
  k/ m0 o0 ]$ I2 w假设我们采用的纠删算法是 (k,n)= (6,9)。相当于6M的数据,每个纠删分片是1M,一共要存放9个纠删分片,任意6个分片就能恢复出完整的数据,这样存放在9个矿工上,另外实际占用的空间大小是9M。如果理解了,我们继续往下看。
% X! r' K5 f9 K" Q; q' E5 N由于纠删算法是(k,n), 那么冗余就是 $F = n/k = 1.5$。
$ G$ `. Y0 X. g. A# _8 v在修复时间内分片丢失数就是:8 ^' G3 ^: C) ?( T5 o5 q% W3 j+ V
$m = n*p = 0.038387869$,这是已知发生数。
/ V4 }( O# U/ J  k6 C/ K- s这里讲解一下概率论中的经典公式,泊松分布拟合公式:6 B8 @9 X! n+ V: Q5 c' W( E
$$P(x) = \frac{mx}{x!}e{-m}$$  p, w6 _; X; o+ z$ v+ x
简单理解一下,泊松分布拟合公式就是观察事物平均发生m次的条件下,实际发生x次的概率。要了解推导细节,可以看最后的附录。
& D) ~3 S/ {, `  X2 `1 a) n3 @我们套用泊松分布拟合公式就可以得到:
4 y5 B/ L: V1 x) C" }- y$$Pb=\sum_{i=0}^{n-k}P\left(i\right)$$; j5 v1 q6 l' u$ r; y4 V. K5 w
​即 $P_b = 99.9999912252%$5 `8 J3 p& Y6 T7 t) z4 m: ]" x
那么全年的耐用率:4 g+ d- n: A/ J+ u8 D
$$P_{yb} = Pb^{(365\frac{t}{τ})} = 99.9615738663%$$
6 a2 t! r- A6 ^$ p+ `% A* ~1 V% v可以看到,虽然更小冗余,但纠删模式对比起全副本模式的耐用率高很多。
6 b7 C6 \9 a9 \, A' X- g6 B计算汇总:: q* |$ `/ \  h6 h
我们把2种冗余模式结合起来,可以得到最终的耐用率:/ [! {/ W6 s) L; ~" A% U2 s
修复时间内耐用率:
# u6 g4 A2 ?. ~% `8 j* }% e/ ^) H$$P = 1 – (1-Pa)(1-Pb) = 99.9999999998%$$/ p% C+ z4 a7 v; U% v, w
全年耐用率:: i! i* Q( h. f7 X
$$P_y = P^{(365\frac{t}{τ})} = 99.9999993008%$$
% p! B" o* g: u0 X2 L' ]# L  L7 d看看,已经达到8个9的耐用率。也就是说假设你如果存放了1亿个文件,一年只会丢失1个文件。你说可靠不?5 R  j8 Q$ S) u3 [& Q
还能提高$ _2 E6 M3 F! {2 M
上面的假设,是基于 (k,n)= (6,9), 冗余度为F=1.5。如果适当提高冗余度 F,或者提高k,还能提高全年的耐用率 Py。下面一个表格就是调整 k和F之后对全年耐用率产生的影响。
# C! V* K1 I: g$ t9 a我们这里做了一个新的假设,完全没有全副本,只有纠删分片。这样做,不追求速度,只追求价格最便宜。这时候,Py 就等于 Pyb。即:+ j  r- [7 b: F  I+ C9 c0 k
# p/ f$ i9 }  v
可以看出,冗余度F越高,耐用率越高。同时, 分片数n越多,耐用率越高。n对耐用度的影响更为敏感,但是n越大,也就意味这需要的矿工越多。; _  J2 A  k. z; u+ [# ~
也可以看出,如果要追求12个9,即99.9999999999。采用纠删模式,在冗余度2的情况下,分成16个纠删副本就能做到。同样,在冗余度2.5的情况下,分成12个纠删副本就能做到。这样就超过 AWS S3企业级存储服务的年耐用率(11个9)。3 A$ \, T* ]! ?" R1 b0 _( |0 x, l
还能再提高
" o2 j6 j% o- q6 h8 V: ~, a除了调整 N, (k,n), F 这些参数,可以提高耐用率之外,还可以通过自身的优化努力。其实还有很大的提升空间,前面说过,这个测算是基于2个前提假设的。而这两个假设本身还有很大的提升空间。6 C% ^5 p- e; I( d
单副本的每日丢失率Pt, 我假设是5%。这个假设本身是可以通过token经济系统的设计来降低的。更合理的经济系统可以提高矿工的稳定性和在线率。如果矿工稳定了,这个值就会下降;这个值越低,全年的耐用率就会增加。这个值有望降至1%甚至更低。
+ P9 j  D+ F/ _, P, Z8 `3 Z副本丢失后的修复时间 τ,我假设是2小时。这个假设也可以通过PP.io自身的算法来优化,只要能更快地发现副本丢失,能更快地增加副本数来保证副本数充足,τ值就会越低;τ值越低,全年的耐用率就会增加。如果算法做到极致的话,这个值有望降至15分钟。- ~4 z0 \! W- V+ y2 K6 W
假设做到了极限值Pt=1%,τ=0.25小时,(k,n)=(6,9)纠删副本冗余度 F=1.5。3 \2 R4 |8 L1 ^0 h" Q2 M  _1 F. y
得到 $P_{yb} = 99.9999998852%$
' }9 s5 J) I6 j! U  K% Q  ]. g如果再考虑2个全副本冗余,则全年耐用率:; y# K0 m2 _3 [: }
$P_y = 99.9999999999%$
7 A8 Y  ?! g+ w$ W6 DPP.io将让开发者灵活设置参数" s; B1 P5 t% M7 e3 y5 T0 o9 U' q
我在设计PP.io架构的时候,给予开发者足够的灵活性,可以根据自身的情况设置不同的参数,其中包括:全副本数 N, 纠删算法参数 (k,N)。
; A1 y3 ?  e- T; |6 T  \$ _开发者可以根据自身的需求,如传输速度,价格(冗余度越高,价格越高),能接受的耐用率来配置参数,从而满足自己的产品要求。
( l: O, t/ O: [. wPP.io给开发者提供一个去中心化的存储和分发网络,使得更便宜,更快,更隐私。PP.io的官网是 https://pp.io' H8 m( k$ P) Q' I: b) b+ x. B
附录:泊松分布拟合公式推导6 s: y: B* r7 M7 c2 C
假设 $p$ 为单个设备单位时间内的故障率,则 $n$ 个设备在单位时间内,有 k 个设备发生故障的概率 $P(k)$ 为:5 f% y/ {8 V7 L) m$ m1 l# v+ y* C
$$P(k) = {n \choose k}p{k}(1-p){n-k}$$
. g. A& e, v" S. A: T$ Y展开组合:
) U. r$ K% J( @( q$$P(k) = \frac{n(n-1)\cdots(n-k+1)}{k!}p{k}(1-p){n-k}$$
+ C% C( V# m1 V3 \! Z1 e7 d. C$$P(k) = \frac{n(n-1)\cdots(n-k+1)}{k!}\frac{p{k}(1-p){n}}{(1-p)^{k}}$$  H7 _5 m2 w9 ~; f* C' K
$$P(k) = \frac{(np)(np-p)\cdots(np-kp+p)}{k!}\frac{(1-p)^{ \frac{1}{p} {np}}}{(1-p)^{k}}$$) s' }- S! P+ t3 |' X& u
假设 p 很小,n 很大,一般地当 n > 20, p {-{np}}}{(1){k}}$$6 T, S3 h; |2 P, I! z5 {3 V
$$P(k) \approx \frac{(np)k}{k!}e{-{np}}$$, T7 U3 J; `( W7 X+ T7 @6 A
( S; }4 I$ T! e  q8 [
$$\lambda = np$$$ ?$ {/ e$ ]$ {) P* z
最后得到泊松分布公式,即,已知单位时间内平均有 $\lambda$ 个设备故障,计算单位时间内有$k$个设备故障的概率。
% V/ t, A5 ~$ E3 k4 m$$P(k) = \frac{\lambdak}{k!}e{-\lambda}$$
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

teawang 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    1