2008年3月26日 星期三

Learn To Program

Learn To Program這個站真是超酷的,由一個 ruby program 寫成的 CGI,用來即時產生書的內容(見” About the Original Tutorial”),好處是確保範例code不會有錯,亂數或時間之類的還可以每次看到不同內容。更炫的是,code、code執行結果可以自動產生,有興趣可以對照看一下“Flow Control”裡Branching 開頭的code,包含source code、兩個執行結果和中間的remark,是由下面這段code產生的:

run1 = {:input => ['Chris']} run2 = {:input => ['Chewbacca'], :remark => 'But if we put in a different name...'} progN run1, run2 do <<-END_CODE puts 'Hello, what\\'s your name?' name = gets.chomp puts 'Hello, ' + name + '.' if name == 'Chris' puts 'What a lovely name!' end END_CODE end

至至於內文寫得好不好,我就沒注意啦。花點時間看這份code挺有收獲的。

2008年3月16日 星期日

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負擔。

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