畢業後的第一篇paper

最近我們跟USC的研究人員合發了一篇Paper
http://smahesh.com/HadoopUSC/
講的是一種用在分散儲存系統的糾錯碼

我來用白話介紹一下,不過會有點長,要有耐心跟好奇心的小朋友才可以看下去哦。(之前在另一篇<上班以來做過的事>有簡單介紹過一點點)

分散儲存系統就像是現在很流行的詞「雲端」,可以把大量的內容存到這系統裡,這系統裡面的構成是上千上萬台電腦,最終會把你在客戶端的內容存到系統中某台電腦的某個硬碟上,這樣的系統存在相當多複雜的問題,像是怎麼分配那個檔案存在那台機器,怎麼讓很多人會同時讀寫

其中一個困難的問題就是:在機器故障的時候,怎麼讓系統還能正常工作

為什麼機器故障這麼重要,如果你家裡一台電腦一年才壞一次,照這速率,Data center裡的幾千台電腦,每天都會壞掉幾十台


上圖取自paper,顯示在Facebook一個3000台機器的機群裡,每天故障機器的數目。如果說我們對故障不做任何處理,讀寫就會失敗,還有可能會永久失去資料

一般的做法把資料分成小塊,每個小塊都存三個副本,這樣子如果有一個副本壞了,可以去讀其他兩個副本,而且在這時候要快點再多複製一個副本,以保持副本數為三,這方法可以抵抗兩台機器同時故障,但三台就不能保證,這方法的缺點就是三個副本會讓成本變三倍

我們在Facebook做了一個Project叫做HDFS-RAID。不同於三個副本的方法,我們用的是一份原來的副本,再加上一些糾錯碼(Error Correcting Code)。糾錯碼在通訊領域是已經非常成熟的技術,在DVD、WIFI、3G,有通訊的地方就有這技術。你想想看DVD為什麼常常刮得亂七八糟還是能看,就是歸功於這個技術

這個方法的好處有兩個,第一就是空間變小很多,因為加上的糾錯碼只有副本的0.4倍大,原本變大三倍的資料變得只有1.4倍,第二就是容錯能力變強,原本可以抵抗兩個錯誤,現在可以抵抗四個錯誤,也就是能在四台機器同時故障的情況下讀取

因為我的背景是無線通訊,做這件工作讓我學以致用,非常開心。在一次Hackathon裡我就寫好了ReedSolomon(某種糾錯碼)的encoder/decoder,之後又用了以前學過的矩陣計算的方法讓它加快許多,現在這些Code都已經上線跑了很久,節省了很多儲存成本,為公司省下了可觀的金錢

但是這方法有一個缺點,就是修復的時候,要讀取十個不同的副本才有辦法修復一個副本,也就是說修復的成本增加了十倍,在我們的系統中讀取是硬碟的讀取,是一個重要的資源,而且修復時間短是很重要的,因為沒修複之前如果有更多機器故障,就有可能失去資料。在一般通訊中的用的糾錯碼(像DVD、3G用的),通常讀取是沒有成本的(這些資訊通常已存在電路的暫存之中),所以這種問題和通訊的問題是很不同的

跟我們合作的USC教授學生們想出了一個新的糾錯碼可以降低讀取的成本,並且跟我們一起測試這些糾錯碼的好壞,我本來覺得這些學information theory的人應該是眼高手低,但是他們很快看懂code而且自己改了很多東西,讓我很驚訝,而且這個教授對實務的問題很有興趣,他一直說他想解決真正的問題,他的理論也很強,讓我很佩服,我覺得做研究就應該做到像這樣才有意義

不過這個Project已經是一年多前的了,學術界的速度龜慢,一年前做的東西到現在才發表,我早已經換到不同的組,做完全不同的事了

Paper和source code可在此下載


留言

匿名表示…
"一般的做法把資料分成小塊,每個小塊都存三個副本..."

請問粉紅大師:

當使用者刪除照片, FB 如何刪除呢? 是去找出所有副本的位置嗎?

Data Center有重兵,裝甲看守嗎? 萬一被攻擊摧毀, 股價不就崩盤
pinky寫道…
要依法要全數刪除。data都有備份再備份,除非所有data center都出問題,但機率非常低,還是擔心自己家會不會地震失火比較實際


Kenneth寫道…
原來 HDFS-RAID 的作者有台灣人啊~~ 厲害~

這個網誌中的熱門文章

斷食期間吃黑巧克力會怎樣

下一站: Facebook

可持續的健身之道