Page 100 - My FlipBook
P. 100
內
合計 GraphStor：從裝置到系統和應用程式整體設計的
作
畫 高效能兼高可靠度圖形計算處理系統
IIS Collaborative Projects 計畫主持人：陳郁方博士、張原豪博士
計畫期程：2020/1~2022/12
由於在大數據時代資料量的爆增，為了有效率的將各式資料轉為可以被利用的資訊，圖形計算 (graph
computing) 近年來受到高度的關注。圖形計算的一大瓶頸就是大量的資料輸出 / 輸入造成效能下降。從
過去的發展歷程中，我們可以發現資料的成長速度遠大於記憶體設備成長速度，因此有越來越多的資料
無法在執行過程中持續存放在記憶體中。記憶體和儲存設備 ( 如固態硬碟 ) 間的大量資料交換，在目前架
構下是無法避免的。在目前的電腦架構下，為了增加系統的穩定性，每個層級 ( 如硬碟，檔案系統，資
料庫系統 ) 都會各自維護自己的系統備份或日誌。這樣才能在遇到意外斷電或當機時，還能將資料回復
到一個可讀取的狀態。然而，這些系統備份需要很大的空間，也會產生大量的資料輸出 / 輸入。
在此一背景下，於今年一月起，我們三年期 (2020/1~2022/12) 的 GraphStor 計畫通過審核，獲得每年台
幣 250 萬元的補助。GraphStor 計畫的目標是設計一個「高效率」和「高可靠度 ( 或稱『穩定』)」的處理
系統，以因應大數據時代下的圖形計算需求。我們的設計大方向是減少系統分層，以減低資料搬運和備
份的需求。例如我們會考慮在記憶體中做運算 (in-memory computing)，利用超低延遲 (ultra-low-latency)
的儲存設備直接取代記憶體，重新設計「檔案」的概念，選擇比較適合儲存圖形的結構。換言之，本計
畫結合兩位主持人在「形式化驗證」及「儲存系統」研究專長，目標為 (1) 近期發展高效率及高可靠度的
crash-deterministic 固態硬碟的儲存系統，並基於此一儲存系統，(2) 中長期將進一步發展高效能兼高可靠
度圖形計算處理系統。
在近期目標中，我們有鑑於資料儲存系統無法避免意外斷電或當機，因此當機回復 (crash recovery) 機制
乃設計中必要的一環。為了同時達成「高效率」和「穩定」的要求，我們一開始的研究目標是設計一個
從儲存裝置出發直到應用層的當機回復 (crash recovery) 機制，以減少層級之間多餘的備份和額外的系統
日誌作業，同時也確保系統在每次當機後，都能回朔到上次系統狀態的紀錄點 (check-point)。這牽涉到
許多複雜的資料結構與演算法。為了確保在這樣複雜的結構下能達成系統穩定的設計目標，我們計劃使
用形式化驗證（formal veri cation）的技術來增加系統的可靠度。這是目前唯一已知，可以證明一個軟體
不存在錯誤的方法。也幾乎是軟體可靠度的最高要求。
我們預設的儲存裝置是主流的固態硬碟 (solid-state drive, SSD)。在傳統的設計下，一但發生當機，在下次
開機後，系統並不能保證回到一個穩定的狀態。所有在最後一次刷新 ( ush) 動作後寫入的資料，都有可
能遺失。以下圖的簡單例子為例，我們有一個有八個區段 (sector) 的硬碟，W1 發生在最後一次刷新動作
之前，而 W2 和 W3 都發生在最後一次刷新之後。W2 寫入一個區段，W3 寫入三個區段。當 W3 完成之
後發生當機，下次開機時，所有 W2 和 W3 的寫入區段都有可能被執行或是沒被執行。所以可能的系統
狀態會有 16 種。這會造成上層檔案系統或圖形處理系統很大的負擔。常見的解決方法，是檔案系統（例
如 ext4）自己維持一份日誌，在當機發生時，利用自己的內部機制和日誌的內容進行系統狀態的回復。
98
合計 GraphStor：從裝置到系統和應用程式整體設計的
作
畫 高效能兼高可靠度圖形計算處理系統
IIS Collaborative Projects 計畫主持人：陳郁方博士、張原豪博士
計畫期程：2020/1~2022/12
由於在大數據時代資料量的爆增，為了有效率的將各式資料轉為可以被利用的資訊，圖形計算 (graph
computing) 近年來受到高度的關注。圖形計算的一大瓶頸就是大量的資料輸出 / 輸入造成效能下降。從
過去的發展歷程中，我們可以發現資料的成長速度遠大於記憶體設備成長速度，因此有越來越多的資料
無法在執行過程中持續存放在記憶體中。記憶體和儲存設備 ( 如固態硬碟 ) 間的大量資料交換，在目前架
構下是無法避免的。在目前的電腦架構下，為了增加系統的穩定性，每個層級 ( 如硬碟，檔案系統，資
料庫系統 ) 都會各自維護自己的系統備份或日誌。這樣才能在遇到意外斷電或當機時，還能將資料回復
到一個可讀取的狀態。然而，這些系統備份需要很大的空間，也會產生大量的資料輸出 / 輸入。
在此一背景下，於今年一月起，我們三年期 (2020/1~2022/12) 的 GraphStor 計畫通過審核，獲得每年台
幣 250 萬元的補助。GraphStor 計畫的目標是設計一個「高效率」和「高可靠度 ( 或稱『穩定』)」的處理
系統，以因應大數據時代下的圖形計算需求。我們的設計大方向是減少系統分層，以減低資料搬運和備
份的需求。例如我們會考慮在記憶體中做運算 (in-memory computing)，利用超低延遲 (ultra-low-latency)
的儲存設備直接取代記憶體，重新設計「檔案」的概念，選擇比較適合儲存圖形的結構。換言之，本計
畫結合兩位主持人在「形式化驗證」及「儲存系統」研究專長，目標為 (1) 近期發展高效率及高可靠度的
crash-deterministic 固態硬碟的儲存系統，並基於此一儲存系統，(2) 中長期將進一步發展高效能兼高可靠
度圖形計算處理系統。
在近期目標中，我們有鑑於資料儲存系統無法避免意外斷電或當機，因此當機回復 (crash recovery) 機制
乃設計中必要的一環。為了同時達成「高效率」和「穩定」的要求，我們一開始的研究目標是設計一個
從儲存裝置出發直到應用層的當機回復 (crash recovery) 機制，以減少層級之間多餘的備份和額外的系統
日誌作業，同時也確保系統在每次當機後，都能回朔到上次系統狀態的紀錄點 (check-point)。這牽涉到
許多複雜的資料結構與演算法。為了確保在這樣複雜的結構下能達成系統穩定的設計目標，我們計劃使
用形式化驗證（formal veri cation）的技術來增加系統的可靠度。這是目前唯一已知，可以證明一個軟體
不存在錯誤的方法。也幾乎是軟體可靠度的最高要求。
我們預設的儲存裝置是主流的固態硬碟 (solid-state drive, SSD)。在傳統的設計下，一但發生當機，在下次
開機後，系統並不能保證回到一個穩定的狀態。所有在最後一次刷新 ( ush) 動作後寫入的資料，都有可
能遺失。以下圖的簡單例子為例，我們有一個有八個區段 (sector) 的硬碟，W1 發生在最後一次刷新動作
之前，而 W2 和 W3 都發生在最後一次刷新之後。W2 寫入一個區段，W3 寫入三個區段。當 W3 完成之
後發生當機，下次開機時，所有 W2 和 W3 的寫入區段都有可能被執行或是沒被執行。所以可能的系統
狀態會有 16 種。這會造成上層檔案系統或圖形處理系統很大的負擔。常見的解決方法，是檔案系統（例
如 ext4）自己維持一份日誌，在當機發生時，利用自己的內部機制和日誌的內容進行系統狀態的回復。
98
