為什麼去中心化存儲也能保證數據不丟失
最近,我寫了不少文章之後,不少熱心網友留言,去中心化存儲最擔心的問題是數據丟失問題。我往裡面存放了數據之後,雖然有更便宜,更快,更隱私等特點,但是數據畢竟存在於礦工的礦機上,由於礦工的不穩定性,可能導致文件的丟失。就像滴滴的司機一樣,大部分時間是靠譜的,偶爾不靠譜,不靠譜的時候,體驗非常差,這樣的產品我不敢用。而大公司提供的服務,如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)(τ/t)=0.4265318778 p = 1 – (1-Pt)^{(τ/t)} = 0.4265318778%p=1–(1?Pt)
(τ/t)
=0.4265318778
PP.io設計的默認全副本數冗餘2倍,糾刪副本冗餘是1.5倍。
我們先看全副本模式:
由於全副本是完全複製,所以是2倍的冗餘,也就是有2個副本。我們稱為N=2。
修復時間內的耐用率:
Pa=1?p2=99.9981807056 P_a = 1- p^2 = 99.9981807056%
P
a
=1?p
2
=99.9981807056
全年耐用率:
Pya=Pa(365?t/τ)=92.3406415922 P_{ya} = Pa^{(365*t/τ)} = 92.3406415922%
P
ya
=Pa
(365?t/τ)
=92.3406415922
我們再看糾刪模式:
假設我們採用的糾刪演算法是 (k,n)= (6,9)。相當於6M的數據,每個糾刪分片是1M,一共要存放9個糾刪分片,任意6個分片就能恢復出完整的數據,這樣存放在9個礦工上,另外實際佔用的空間大小是9M。如果理解了,我們繼續往下看。
由於糾刪演算法是(k,n), 那麼冗餘就是 F=n/k=1.5 F = n/k = 1.5F=n/k=1.5。
在修復時間內分片丟失數就是:
m=n?p=0.038387869 m = n*p = 0.038387869m=n?p=0.038387869,這是已知發生數。
這裡講解一下概率論中的經典公式,泊松分布擬合公式:
P(x)=mxx!e?m P(x) = frac{m^x}{x!}e^{-m}
P(x)=
x!
m
x
e
?m
簡單理解一下,泊松分布擬合公式就是觀察事物平均發生m次的條件下,實際發生x次的概率。要了解推導細節,可以看最後的附錄。
我們套用泊松分布擬合公式就可以得到:
Pb=∑n?ki=0P(i) Pb=sum_{i=0}^{n-k}Pleft(i
ight)
Pb=
i=0
∑
n?k
P(i)
即 Pb=99.9999912252 P_b = 99.9999912252%P
b
=99.9999912252
那麼全年的耐用率:
Pyb=Pb(365?t/τ)=99.9615738663 P_{yb} = Pb^{(365*t/τ)} = 99.9615738663%
P
yb
=Pb
(365?t/τ)
=99.9615738663
可以看到,雖然更小冗餘,但糾刪模式對比起全副本模式的耐用率高很多。
計算匯總:
我們把2種冗餘模式結合起來,可以得到最終的耐用率:
修復時間內耐用率:
P=1–(1?Pa)(1?Pb)=99.9999999998 P = 1 – (1-Pa)(1-Pb) = 99.9999999998%
P=1–(1?Pa)(1?Pb)=99.9999999998
全年耐用率:
Py=P(365?t/τ)=99.9999993008 P_y = P^{(365*t/τ)} = 99.9999993008%
P
y
=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 P_{yb} = 99.9999998852%P
yb
=99.9999998852
如果再考慮2個全副本冗餘,則全年耐用率:
Py=99.9999999999 P_y = 99.9999999999%P
y
=99.9999999999
PP.io將讓開發者靈活設置參數
我在設計PP.io架構的時候,給予開發者足夠的靈活性,可以根據自身的情況設置不同的參數,其中包括:全副本數 N, 糾刪演算法參數 (k,N)。
開發者可以根據自身的需求,如傳輸速度,價格(冗餘度越高,價格越高),能接受的耐用率來配置參數,從而滿足自己的產品要求。
PP.io給開發者提供一個去中心化的存儲和分發網路,使得更便宜,更快,更隱私。
附錄:泊松分布擬合公式推導
假設 p 為單個設備單位時間內的故障率,則 n 個設備在單位時間內,有 k 個設備發生故障的概率 P(k) 為:
展開組合:
假設 p 很小,n 很大,一般地當 n > 20, p < 0.05 時。
令
最後得到泊松分布公式,即,已知單位時間內平均有 λ 個設備故障,計算單位時間內有k個設備故障的概率。
※13個Python Web框架比較,你想使用哪個呢?
※詳解 RestTemplate 操作
TAG:程序員小新人學習 |