Google File System

最近 Google 在推 MapReduce 這個平行計算 framework，讀完 paper 後，覺得滿有意思的，若有些 network programming 和 functional language 的基礎，讀起來應該滿輕鬆的。除了好奇之外，一方面也是想讀點技術性的論文，看看和平常讀的 data mining、information retrieval 論文有什麼差，又找了 GFS 的 paper 來讀，結果還滿有趣的。

先提個技術無關的事，這篇的 Acknowledgments 最後一句寫著：

Many of our colleagues at Google bravely trusted their data to a new file system and gave us useful feedback.

令人會心一笑。

這篇論文一開始先說明作者的需求。依他們的使用環境，提了些使用上的假設，像是硬碟常壞掉、設備不可靠，可是 file system 的可靠度是首要目標；random write 少、append 多；還有 small random read、large sequential read。接著依這些操作特性，自訂需要的 file system，對我這類看重實務面的人來說，這種開頭很合我的喜好，有些學術性論文討論的是尚未存在的需求，較難接受作者的假設。描述整篇論文太累了，這裡摘要一些我認為有趣的設計：

• GFS 是架在 Linux file system 之上的 file system，這樣做的好處是善用Linux既有開發，簡省開發時間。雖然作者也提到因為Linux kernel bug，使得系統有些不穩，逼迫他們自行改 Linux kernel，整體來說，作者認為這個決定是正確的。我原本還以為GFS會自己重弄一個file system。
• GFS的主要目的是穩定和處理大量資料，所以分散式系統是理所當然的設計。但有趣的是，GFS 採用 single master server，理由是設計簡單。
• GFS由 one master、many chunkservers、many GFS clients組成。
• 為了達到single master，整體設計做了許多對應措施，如盡可能減少master的負擔，GFS client直接和chukserver拿資料；要寫入資料時，也是chunkserver之間互傳，master只記meta data。
• 為了讓 meta data能全塞入memory，metadata格式很簡單，並有做 file path 的 prefix compression。實驗部份指出上百TB的data，meta data只占數十MB。
• 沒有「目錄」的存在，所有檔案的是用絕對路徑表示，這樣做的好處有：省下目錄的資料結構；可以同時多個client新增同一目錄下的檔案，沒有目錄，自然不需要對目錄要write lock（但「目錄」仍然有 read/write lock，用在別的場合）。
• 整體採用duplicate data確保availability，chunkserver有存各個data block的checksum，送出資料時有先確認沒有損毀，確保reliability。
• 不同檔案可以有不同的replication factor，預設值為3；常被使用的執行檔可以設為上百，避免同時多個application client用到而造成bottleneck。
• 寫入檔案時，為確保各個replication一致，做起來不簡單；master會指派一個chunkserver負責資料更新。值得注意的是，由於寫入動作的複雜度，有時會先等一會，再批次處理對同一檔案的不同寫入。
• 更新資料分兩部份：資料流會依chunkserver相對位置傳，並把資料切成數小塊，行成一直線的pipeline傳資料，減少傳輸的lantency。
• 接著由master指派的chunkserver指示所有有關的chunkserver用同一順序寫入資料，確保即使同時有多種寫入同一資料的操作，寫入完後同一份資料在不同chunkserver上仍然一致。
• replicate data時，不止要考慮放在不同chunkserver，還要放在不同rack，使得swtich壞了或某機房停電時，仍能保證資料的存取。
• master待load較輕時，會在background簡查metadata的正確性、data replication是否有達到正確的數量，並依確少的程度補救，比方只剩一份replication的優先性比剩兩份大很多。
• master若掛了，外部的monitor會發現，重新開一個master (一分鐘內即能完成）。
• 為了確保master掛了也沒問題，所有master的操作都是先將log寫入disk後，才正式執行。加上log很精簡，master重新啟動載入log不需多少時間。
• 事實上，不管是master還是chunkserver，都沒有「停止」的指令，直接kill即可。它們都是設計成可以隨時掛掉，隨時快速複活。
• 刪除檔案即在master內將檔名改為特殊名稱並隱藏起來，仍可讀取和復原；待一段時間（三天）後，master會在background執行的garbage collection中正式清掉標記為刪除的檔案，好處是減少master短時間的high load，還有避免使用者犯錯，壞處是disk space可能實際上夠卻無法拿來使用。
• chunkserver若發現檔案無法在master內查到meta data，即表示檔案已被砍了，減少master和chunkserver互相sync meta data的問題。master則是在新啟動時，向所有chunkserver要資料，減少master記錄的負擔。
• 雖然GFS沒實作POSIX，卻有另外提供特殊功能：append record和snapshot
• append record常用在 many-to-one producer-consumer queues。append可以同時對同一檔案操作，write則需要指定offset，不能同時執行。
• snapshot指複製某個namespace下的所有檔案 (e.g. /home/www )，snapshot採用類似 copy-on-write 的設計，沒被寫入的data chunk不會被複製。
• chunk有reference count，當chunkserver發現reference count > 1又被寫入時，就會先複製一個新chunk，再把reference拆開，並更新各自的reference count。透過reference count達成copy-on-write的設計很漂亮，為了避免snapshot途中檔案有變（e.g. 多了新檔案)，執行snapshot時會要求該namespace下的write lock。
• shadow master以慢一點點的時間達到和master一樣的狀態，當作 read-only master，減輕master負擔。

整體來說，這篇論文相當有意思，許多設計都是簡單易懂，概念看來也很實用。唯一奇怪的是，實驗部份的表現看來不太好，還有我看不懂部份實驗說明，概念和設計細節都懂，反而是實驗看不懂，這到是很少碰到的情況，怪哉。