考慮一個鍵值（key-value, KV）儲存系統。儲存系統中的一筆 KV pair 由一個固定長度的字母字串（alphabetical string）當作鍵（key），以及一個長度可變的位元字串（bit string）作為其對應的值（value）所組成。KV 儲存系統提供 PUT(x,v) 與 v=GET(x) 這兩個 API 給應用程式使用，其中 PUT(x,v) 把指定的鍵值對 $(x,v)$ 存進儲存系統中，GET(x) 則回傳先前存進 KV store 中、給定查詢鍵 $x$ 所對應的值 $v$。此外，KV 儲存系統提供的 SCAN(x1,x2)，會回傳一份 KV pairs 清單，清單中每一筆的鍵都不小於 x1、也不大於 x2。

令這個 KV 儲存系統運作在一個電腦系統上，該系統配備大小為 $x$ 的揮發性記憶體空間（volatile memory space）與大小為 $y$ 的持久性儲存空間（persistent storage），其中 $x \ll y$。

值得注意的是，應用程式對 KV 儲存系統可能會產生兩種工作負載模式（workload patterns）。隨機存取（random access）模式是指 GET(.)、PUT(.)、SCAN(.) 產生的鍵是隨機的；循序存取（sequential access）則代表資料項目是以遞增（或遞減）的鍵依序存取的情境。其次，GET(.)、PUT(.)、SCAN(.) 操作可能會同時（on the fly）被並行執行。第三，儲存在系統中 KV pairs 的總儲存空間大小，可能會大於前述的可用揮發性記憶體空間 $x$。最後，KV 儲存系統可能隨時失效（fail），並且需要支援對已提交（committed）的 PUT(.) 操作進行復原（recovery）。

請討論作業系統要如何設計與實作，才能提供這樣的 KV 儲存服務，同時考量在操作 GET(.)、PUT(.)、SCAN(.) 時，延遲（delays）與輸出量（throughputs）這兩個效能指標。請依序針對以下技術，清楚說明你的設計主張：

(1) [5%] 記憶體內索引（In-memory indexing）

(2) [5%] 磁碟內索引（In-disk indexing）

(3) [5%] 快取（Caching）

(4) [5%] 分頁（Paging）

(5) [5%] 批次 I/O（Batched I/O）

(6) [5%] 多執行緒與執行緒排程（Multithreading and thread scheduling）

(7) [5%] 共享記憶體與一致性（Shared memory and consistency）

(8) [5%] 編碼／解碼（Encoding/Decoding）

(9) [5%] 檔案系統區塊配置（File system block layout）

(10) [5%] 檔案系統壓實（File system compaction）