計算機論文精選-20180530

來自專欄計算機論文精選

1. The Design and Implementation of a Log-Structured File System [TOCS 1992]

本文設計的Log-Structured File System（LFS）是基於一個假設：隨著內存的不斷增大，文件系統讀緩存的命中率將會變得很高，因此磁碟的寫I/O將取代讀I/O成為系統的性能瓶頸。為了解決磁碟寫I/O的性能瓶頸，LFS在修改磁碟數據和元數據時均是追加到文件的末尾，並沒有在原地進行更新， 這種設計能將磁碟的隨機寫轉變為順序寫，從而重複利用了磁碟寫操作的帶寬。具體而言，LFS像磁帶驅動器一樣將新數據順序地附加在磁碟中，而不隨機訪問磁碟中的數據。LFS避免了代價高昂的磁頭移動，這樣可以使數據寫入速度提高10倍，並且還能夠更快地從計算機崩潰中恢復。另外，為了更好管理硬碟上的大空間塊，LFS把多個log整合為一個segment，利用基於代價的清理策略對大空間塊進行壓縮和回收。論文在此理論上實現了Sprite LFS的文件系統，它的傳輸利用率高達70%（大大超越了Unix的5-10%)。

LFS是專門針對寫操作進行優化的文件系統，這類文件系統的特點是使用日誌結構管理數據。然而，當時設計LFS所基於的假設很長時間並沒有成為現實，所以LFS最初找不到應用場景，只停留在研究階段。除了Sprite LFS文件系統，其後比較典型的是NILFS2（New Implementation of Log Structured File System），因為NILFS2已經被linux 內核2.6.30採用了。 當Google（Google File System）和DataDomain等開始使用LFS構建分散式系統並處理可變大小的塊時，LFS開始流行。最近，LFS成為SSD不可或缺的一部分，因為LFS就是SSD如何管理內部快閃記憶體晶元的關鍵技術。

2. Tenex, A Paged Time Sharing System for the PDP-10 【SOSP 1971】

本文提出的TENEX是一個新的分時系統，實現在由BBN開發的特殊分頁硬體增強的DEC PDP-10上。它包括一個完整的虛擬內存系統，也就是說，程序不僅可以訪問完整的內存空間，而且每個程序可以同時進行這樣的訪問。分頁系統將像往常一樣處理映射，根據需要將數據拷貝到後備存儲或者從後備存儲中拷貝出來。唯一需要改變的是分頁器能夠在RAM和存儲之間維持多組映射，每組對應於一個正在使用系統的程序。TENEX的一個顯著特點是其面向用戶的命令行解釋器。不同於那個時代的典型系統，TENEX故意使用長命令名稱，甚至包括非重要雜訊字，以進一步擴展命令。

本文描述了TENEX的設計和實現是如何實現一些對所有分時系統都很重要的目標的，包括詳述一個強大的多進程大內存虛擬機，無隙的終端交互，全面的統一的文件和I / O功能，以及清晰靈活的系統結構。

3. Distributed Snapshots: Determining Global States of a Distributed System 【TOCS 1985】

本文是由Mani Chandy 與 Leslie Lamport共同完成，提出了一種用於在分散式系統中記錄非同步系統的一致全局狀態的快照演算法。該演算法以兩個作者的名字命名，稱為Chandy-Lamport演算法。

據Leslie Lamport的網站稱，「這裡描述的分散式快照演算法是在我訪問當時在德克薩斯大學奧斯丁分校的Chandy時誕生的。他在晚飯時向我提出了這個問題，但是我們兩個當時都喝了太多的葡萄酒，沒辦法思考合適的解決辦法。第二天早晨，在洗澡時，我想出了解決辦法。當我到達Chandy的辦公室時，他正在用相同的解決辦法等著我。「

分散式系統的許多問題可以歸於檢測全局狀態的問題。例如穩定性檢測（stable property detection）和檢查點（checkpointing）。

演算法的假設如下：

1）沒有故障，所有的消息到達的時候都是完整的但只有一次

2）通信信道是單向的，先進先出

3）在系統中的任何兩個進程之間都有通信路徑

4）任何進程都可以啟動快照演算法

5）快照演算法不會干擾進程的正常執行

6）系統中的每個進程記錄其本地狀態和傳入信道的狀態

該演算法使用標記消息工作。想要啟動快照的進程記錄其本地狀態，並在其每個傳出信道上發送一個標記。所有其他進程，在接收到一個標記後，會記錄它們的本地狀態，把標記傳入信道的狀態記為空，並在其所有的傳出信道上發送標記消息。如果一個進程在記錄了其本地狀態之後接收到一個標記，那麼它將標記傳入信道的狀態記錄為它從首次記錄其本地狀態以來接收到的所有消息的序列。

演算法的工作原理如下：

1.觀察者進程（進程拍攝快照）：

a）保存自己的本地狀態

b）向所有其他進程發送帶有快照令牌的快照請求消息

2.在任何消息上首次接收快照令牌的進程：

a）向觀察者進程發送自己保存的狀態

b）將快照令牌附加到所有的後續消息上（以幫助傳播快照令牌）

3.當已經接收到快照令牌的進程接收到不攜帶快照令牌的消息時，此進程會將該消息轉發給觀察者進程。該消息顯然是在快照「切斷」之前發送的（因為它不帶有快照令牌，因此必然來自快照令牌發送之前），並且需要包含在快照中。

基於此，觀察者建立了一個完整的快照：保存了每個進程的狀態以及所有「在乙太網」中的消息。

更多內容請關注微信公眾號「論文精選」以及微信小程序「SkimPaper」，每天準時為您推薦體系結構、分散式系統、人工智慧等相關領域優秀論文解讀。同時也歡迎大家積極投稿，分享您讀到的優秀論文。