論文筆記 [SOSP '03] The Google File System
google file system， 谷歌經典論文之一。GFS通過single master，Garbage Collection，control path 與data path分離等機制，很好的在便宜機器上實現了Availability, recoverability, High throughput。但是GFS針對的是特定的workloads（寫一次，讀多次，大批量的讀等），並且需要appication支援, 以避免不一致資料的情況。
Assumptions
既然是google file system，當然是針對google的應用場景做的優化。這篇發在03年的sosp，現在workloads已經變了很多了，gfs已經有了第二代Colossus，不過沒paper出來。
- 便宜的裝置，會經常損壞(fault tolerate)
- 大量的大檔案，基本都在100MB以上或者更大，GB級別的檔案是很常見的
- read workloads: Mostly large streaming reads（1MB or more）和Some sorted random reads(a few KB)。
- write workloads: many large，sequential write。append居多。寫一次，讀多次。
- 多使用者併發向同一個檔案進行append操作
- google的大都是高速批量寫入的應用，所以它更要求持久穩定的頻寬。
Architecture
GFS是一個single master，multiple chunkserver的架構。 比較有意思的是GFS將control path 和data path做了分離。所有的control path從master走，data path由client直接與chunkserver通訊。
master存metadata，比如namespace，控制權限等。這些資訊都是存在記憶體裡的，用WAL保證持久。WAL會有副本（replication state machine），防止master掛掉導致不可用。這裡注意的是，儘管所有chunk的metadata都存在master記憶體中，但這並不會成為一個瓶頸。因為資料量非常小，每個檔案64bytes（利用字首壓縮）。
master和chunkserver直接通過heartbeat（心跳包）通訊來監測chunk 的位置等資訊。
chunk
每一個檔案被分成了多個固定大小的chunk（64MB）。chunk就是直接存在chunkserver上的，就是一個單個機器上就是一個普通的檔案存在ext4或別的檔案系統。chunk會存在多個副本在不同的chunkserver上。需要注意的是chunk比linux上普通的block要大很多，這是基於google應用場景做的優化（large streaming read）。這麼做存在一些優缺點。
- advantages
- 減少了client和master通訊的次數。因為同一個chunk，client只需要最開始的時候向mater要一下location即可。
- 減少網路通訊。
- 減少master需要管理的metadata。
- disadvantages
- 當檔案很小時，單個chunk就是一個檔案。假如這個檔案是熱點資料。同時幾百個client同時請求同一個chunk，chunkserver會過載。這種情況可以通過調整chunk副本數量來做負載均衡。或者讓client從別的client那裡讀chunk（減少chunkserver壓力）。
Consistency Model
首先gfs提出了幾個名詞來表示consistency。
- consistent: 所有client都看到相同的資料，無所是從哪個副本讀的。
- defined: 當發出一個mutation後，所有client都能看到這個mutation修改後的資料。
- consistent but undefined: 所有client都看到相同的資料，但並不反映任何一個mutation修改後的結果。（多個client併發操作）
如下圖。
metadata修改都是原子的，master內部會用鎖和全域性有序的log來保證這個。這也是single master的好處。
data修改的順序是由primary server定的。序列寫可以保證所有副本的defined。但是多個client併發寫，資料就會出現被覆蓋等情況，即consistent but undefined。這是write的情況，即由使用者指定offset的情況。
而GFS的大部分的wrokload都是append模式的。這種情況下，gfs可以保證原子性的completes at least once（通過失敗之後重複請求等方式）。但還是會有重複的record或者padding這種情況，這需要application自己來檢測（chunksum，unique id）。
Implemention
系統的實現目標是儘可能的減少與master的互動。master會選擇一個副本作為primary，同時授予primary 一個60s的lease。在lease有效期內，由primary來決定每個副本mutation的順序。lease是可以被master 收回或者延長的（heartbeat更新lease）。
Mutation
下圖是mutation的順序圖。
- client詢問master，chunk的location。master會選擇一個副本作為primary（授予lease，如果沒有的話）
- master返回副本的location和primary資訊。client會快取這些資訊。直到lease過期，或者副本掛掉。
- client將data push到所有副本（任意order，這裡可以利用網路結構做優化，pipelining）。
- 當所有副本收到data之後，client傳送寫請求給primary。primary會選擇一個序列的順序，並按順序修改本地data
- primary轉發寫請求到所有副本，另外的副本按同樣的順序修改。
- 副本返回給primary，表明寫入完成
- primary回覆client。若有錯誤，client進行重試（3-7）
Snapshot
snapshot操作就是快速copy 一份檔案或者目錄，並減少對正在進行中的mutation的干擾。GFS利用copy-on-write的方式。當master收到snapshot請求之後，master會立即收回所有相關chunk的lease。
- snapshout 某一個檔案
- master回收所有相關chunk的lease（保證後續寫操作會和master互動）
- log snapshot操作
- copy一份這個檔案的metadata，指向相同的chunk
- 延遲到client發起寫相關檔案的chunk時，master會讓chunkserver建立一個新的chunk，並修改metadata指向新的chunk，並授予lease，返回給client。
Garbage Collection
當一個檔案被刪除時，並不會立即刪除。master先log 刪除操作，然後將這個file修改成特殊的名字(比如.xxx)隱藏起來。在進行垃圾回收的時候才刪除那些已經存在了3天以上的隱藏檔案（天數是可配置的）。然後通過和chunkserver進行heartbeat通訊，將這個資訊告訴chunkserver，讓chunkserver進行物理刪除data。
也就是隻要是master所不知道的副本都是garbage。這種lazy 刪除的方法，將刪除的操作batch到一起，更高效。
Stale Replica Detection
chunk的副本還有可能過期。當chunkserver掛掉的時候，有mutation操作的話。所以為每一個chunk，master會維護一個版本號來追蹤是否是最新的版本。version number在master授予lease的時候更新。在垃圾回收的時候刪除過期的版本。