畢業後的第一篇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可在此下載

http://smahesh.com/HadoopUSC/