# OS HW3: Key-Value Storages - **學號: F74076124** - **姓名: 向景亘** - **系級: 資訊 111** ## 開發環境 - OS: Ubuntu 20.04 - CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz - CPU cores: 4 - Memory: 16 GB - Programming Language: C11, gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0 ## 程式執行時間 ```shell $ ./kv_store hw3example.input execution time: 0.004542 ``` ## 程式編譯及使用說明 ### 編譯流程 使用 `Makefile` 進行編譯 ```shell $ make CC kv_store.o CC include/bucket.o LD kv_store ``` ### 清除編譯擋案 ```shell $ make clean ``` ### 使用 `clang-format` 進行格式整理 ```shell $ make format ``` ### `kv_store` 使用方式 使用下列指令執行 `kv_store`，其中 `INPUT_FILE` 的副檔名必須是 `.input` ```shell $ ./kv_store [INPUT_FILE] ``` ## 程式開發記錄 原本的我考慮的做法是類似 memory paging 的手法。 因為 `key` 的範圍介於 0 ~ 2^63^ - 1，也就是我們可以在 64 bit 的資料結構中保存，所以我想利用這 64 bit 中的 28 bit 作為 page 的編號，剩下的 36 bit 作為該資料的 offset 來使用。 因此當我們從 input 中讀取到 `key` 的數值的時候，我們就可以從這個 `key` 計算出該資料需要從哪個檔案中取出或是寫入到哪裡。寫入時間與讀取的時間複雜度就會是 $O(1)$。 但是考量到 Ubuntu 所使用到的 [ext4](https://en.wikipedia.org/wiki/Ext4) 這個檔案系統對於儲存檔案有數量的上限，所以我改以 hash table 的方式來實作。 若我們將 `key` 存放在一個 `int64_t` 的變數中，我們可以想像他是一個 8 byte 長度的字串，所以我們可以對這樣一個字串進行 hash，在沒有發生 collision 的情況下，我們可以取得一個數值作為該筆資料的 index，因為每個 `key` 不重複的情況下，每個 index 的會是獨一無二的，因此寫入與讀取的時間複雜度也會是 $O(1)$。 並且考慮到實際測試檔案沒有辦法完整的存放在記憶體中，所以我們必須建立儲存與查詢檔案的機制。 在這個部分我參考了 LSM tree 的部份結構：當我們將當前記憶體中的 hash table 存滿之後，我們會將這張 hash table 存到硬碟當中。 如果我們在當前記憶體中的 hash table 找不到我們想要的數值時，我們會將儲存在記憶體中的資料從最新到最舊的檔案依序讀取並查找是否存在該筆資料，如果確定沒有的話我們才會輸出 `EMPTY`。 而在 LSM 的概念中，資料庫會週期性的整理與會並資料。但是因為我們所寫的程式並不會像資料庫保持開啟與連線。所以我們對於 `PUT` 的操作只會不停的往 hash table 存入資料，而不會刪除與合併就有的資料，以維持寫入的效率。若我們在過程中有更新其中一筆資料的 `value` 時，因為我們讀取的順序是從新的讀到舊的，所以更新過後的數值也會被優先存取，達到更新的效果。 ## 效能測量 ### 將 disk 作為 paging 來實作的讀寫效率 我們將不包含 cache 版本的 `kv_store` 以 200000 筆 `PUT` 的測試資料進行測試 ```shell $ ./kv_store puts200000.input execution time: 3.608744 ``` 我們可以發現如果 PUT 的資料很散的話，我們就會生成很多的檔案。也就是說如果我們今天這 200000 筆資料都個別對應到不同的 bucket，我們將會在執行的過程中依序地建立這些檔案出來，並且我們只有使用到其中的一小部分而已。因此會對檔案系統造成巨大的負擔，且執行的時間也會變慢。 ### 以 LSM-like hash table 之寫入效率 ```shell $ ./kv_store puts200000.input execution time: 0.124984 ``` 我們可以看到因為改善了儲存資料的方式，所以我們有機會將大部分的資料保存在其中一個 bucket 中，而不會受到測試資料範圍過大的影響，且因為使用 hash table 的方式，我們可以快速地找到我們想要儲存與讀取的位置，因此在效能上不會比原先的方式慢，而更可以提升處理的速度。 但是在同一筆測資中，若包含讀取與寫入兩種操作的話，讀取的效能將有可能受到 `storage` 內檔案數量的影響，以下是重複執行 10 次後的測量結果 ```shell $ ./kv_store hw3example.input execution time: 0.083315 ``` ### 只取出單一筆資料的效能改善 但是在上述的情況中因為在讀取硬碟中的資料時我們選擇將整個資料讀到記憶體中在尋找其中指定位置的資料是不是我們想要的，所以執行的速度會受到當前 `storage` 目錄中檔案數量所影響。 為了降低這樣的影響，我嘗試只讀入指定位置的資料，來進行加速，以下是重複執行 9 次後執行的測量結果： ```shell $ ./kv_store hw3example.input execution time: 0.004495 ``` 可以看到與上一個測試的結果相比效能上有了明顯提升。 ## 分析與結論 在本次作業中，我們嘗試實作出一個具備讀寫功能的 key-value store 程式。 為了能夠達到快速的寫入與讀取，資料的結構變成最直接影響效能的關鍵之一。 如果我們嘗試將 disk 作為 memory paging 來實作的話，雖然我們可以利用 key 的數值直接計算出 data 的 index 與 offset 進而直接從目錄中把資料取出來使用。但是因為數值範圍太大，我們所儲存的檔案數目有可能會遠遠的大過我們的檔案系統所能負荷的大小，而導致檔案系統損壞的情形發生。 為了避免這樣的情況，我們改以其他折衷的方式來實作。考慮的存取與寫入的方便性，我認為實作 LSM tree 與 hash table 一部分的特徵可以幫助我們達成這樣的目的。 因為 LSM tree 並不在意我們有沒有更新到既有的資料，而是不斷的寫入新的資料，並週期性的整併。但是因為我們沒有辦法確保我們可以在背景持續維護與整併整個資料庫，所以我採取的方式是維持不斷寫入的特性，而不去更新原先就已經存在的資料，而是透過改變查找檔案的順序，讓新的資料會優先被找到，使得舊的資料不至於影響到我們的輸出結果。 接著若記憶體中的資料已經存滿了，我們就將這整張 table 寫入到 disk 之中。考慮到之後可能還需要回來讀取這些檔案，所以我們會需要一個可以快速載入資料的資料結構，這個時候就會發現 hash table 的好處了。因為他與一般的 array 有類似的結構，所以我們可以將 table 所在的連續記憶體內容寫入到檔案系統中。下次當我們要找尋其中的資料時，只要將對應的檔案讀取的一塊連續的記憶體中就可以做使用，達到讀寫功能的實現了。 而在測試的過程中我注意到在測試的過程中如果我們累積了大量的 bucket 時，我們會需要將所有 bucket 依序讀入記憶體中才可以確定該筆資料是否存在，進而造成執行時間加長的問題，所以我也嘗試透過只讀入部分檔案內容來減少 disk I/O 所造成的影響，從而達到減緩大量輸出入所造成的效能問題。 所以從上述的測量與分析中，我們可以推論 OS 應該要提供程式在寫入與讀取過程中 buffer 與 cache 的功能。 因為我們不應該讓使用者在每次寫入硬碟的時候都需要等待硬碟寫好檔案後才執行其他的作業。相對的，硬碟也不該只寫入少量的資料。因此我們應該要先將這些要寫入的資料保存在記憶體的暫存區中，等到累積到一定的數量後才將整批資料一起寫入硬碟當中。 而在讀取資料的時候，因為我們沒辦法預測使用者想要讀取什麼樣的資料，所以我們無法對資料先進行 prefetch，但是我們可以一次讀進較多的資料，如果下一次使用者想要使用的資料剛好在上一次讀取的過程中被讀到了記憶體中，我們就可以直接提供這些資料而不需要再從硬碟把這些資料讀取出來，從而提升存取的速度。 ###### tags: `os`