110 年 國立成功大學資訊工程系碩士班《計算機組織與系統》

核心觀念

題目要將兩個已載入浮點暫存器的雙精度數相乘，並把結果寫回代表 $C[x+yN]$ 的暫存器。MIPS 的 mul.d 指令執行雙精度浮點乘法，格式為：

mul.d 目的暫存器, 來源暫存器1, 來源暫存器2

解題方法

依題意，$A[x+zN]$ 在 $f6，$B[z+yN]$ 在 $f8，而結果要放入 $f4。因此直接以 $f6 和 $f8 相乘，並覆寫 $f4：

mul.d $f4, $f6,

核心觀念

本題考查依照程式中的運算種類與資料存取方式，判斷 CPU 哪些資料路徑會影響執行速度。每次內層迴圈主要執行一次雙精度浮點乘法，並讀取兩個矩陣元素、寫入一個矩陣元素。

解題方法

內層運算為：

因此應優先考慮兩類資料路徑：

1. 浮點運算資料路徑：運算使用雙精度浮點數，CPU 的浮點乘法器會直接執行乘法。提升雙精度浮點乘法的吞吐量或縮短其延遲，可加速此運算。
2. 記憶體資料路徑：每次內層迴圈都要讀取 $A$、$B$ 的元素並寫入 $C$，每個元素為 8 位元組。載入／儲存單元、快取與記憶體頻寬會影響資料供應速度。

核心觀念

這題考的是以整數運算近似浮點運算的技術：定點運算（fixed-point arithmetic）。它不直接儲存浮點數的指數與尾數，而是把數值乘上固定倍率後，以整數表示。

解題方法

選定小數位數 $k$，將實數 $v$ 編碼成整數：

運算時使用整數指令。例如，兩個定點數相乘後，乘積多帶了 $k$ 個小數位，因此要右移 $k$ 位，恢復原本的倍率：

題意

承上一小題：嵌入式處理器沒有浮點硬體時，浮點運算有兩種模擬方式：

1. 軟體浮點函式庫（soft-float）：以程式（函式庫常式）完整模擬 IEEE 754 浮點運算——拆出符號、指數、尾數，對齊指數、整數相加／相乘、正規化、捨入、處理特殊值。
2. 以整數運算模擬（定點數，fixed-point arithmetic）：把實數乘上固定的比例 $2^q$ 後存成整數（例如 Q15、Q16.16 格式），之後直接用整數加減乘除運算，乘法後再右移 $q$ 位調回比例。

核心觀念

計算效率取決於「每一次浮點運算需要多少條整數指令」。軟體浮點函式庫每次運算都要呼叫函式並執行數十到上百條整數指令（解包、對齊、正規化、捨入、例外處理）；定點數的一次加法就是一條整數加法，一次乘法只是一條整數乘法加一次移位。

解題方法

核心觀念

本題考查資料平行性，以及如何用 SIMD（Single Instruction, Multiple Data，單指令多資料）指令一次處理多筆資料。SIMD 指令讓同一個運算指令同時作用於多個資料通道（lane）；例如一條向量乘法指令可同時完成 $W$ 組浮點數乘法。

程式中的 $A$ 與 $C$ 都以 $x$ 為連續索引，因此沿著 $x$ 方向分組，可一次載入 $W$ 個 $A$ 的元素、對它們乘上同一個 $B$ 元素，再一次寫回 $W$ 個 $C$ 的元素。

解題方法

令向量寬度為 $W$，每個向量可容納 $W$ 個雙精度浮點數。固定 $y$ 與 $z$ 時，$B[z+yN]$ 對所有 $x$ 都相同，因此先將它廣播到向量的每個 lane，再沿 $x$ 方向執行向量乘法。

核心觀念

快取容量以可存放的資料量計算。三個矩陣都必須同時留在 L1 資料快取中，因此先計算 $A$、$B$、$C$ 的總資料大小，再向上取到不小於總容量的 2 的冪次。

解題方法

每個矩陣有 $64 \times 64$ 個元素，每個雙精度浮點數占 8 bytes，因此單一矩陣大小為：

三個矩陣合計：

核心觀念

區塊化（blocking）會讓計算集中在三個 $M \times M$ 子矩陣上。每個元素占 $8$ bytes，因此三個子矩陣同時放入資料快取所需的空間為：

解題方法

$16\text{ KB}$ 資料快取可容納 $16 \times 1024 = 16384$ bytes。要讓三個子矩陣都放得進快取，必須滿足：

核心觀念

這題考的是迴圈分塊（blocking／tiling）：將矩陣運算切成大小為 $M \times M$ 的區塊，使運算所需的資料較容易留在快取中，減少主記憶體存取。

題目中的索引 x + z*N 與 z + y*N 表示矩陣以欄主序方式儲存。分塊後，外層迴圈逐一走訪區塊，內層迴圈處理區塊內的元素。若 $N$ 不能被 $M$ 整除，區塊的結束位置須以 $N$ 為上限。

解題方法

題目未附前小題計算出的 $M$ 數值，以下以 $M$ 表示已計算好的區塊邊長；實際作答時將它代入。外層的 xb、yb、zb 分別指定 $x$、$y$、$z$ 方向的區塊起點。

核心觀念

「記憶體內索引」是把索引常駐於揮發性記憶體，索引項目記錄鍵值與其在持久儲存中的位置；實際 KV 資料則放在持久儲存中。如此一來，查詢先搜尋小型索引，再依位置讀取資料，不必把全部 KV 資料載入記憶體。

本題的鍵是定長英文字串，能依字典序比較；而 SCAN($x_1,x_2$) 需要依鍵的範圍取回資料。因此，索引除了支援單筆查找，還要保留鍵的順序。

解題方法：採用有序記憶體索引

可在記憶體中維護平衡搜尋樹，例如 AVL 樹、紅黑樹，或跳躍表。每個索引項目記錄：

其中 record_location 指向持久儲存中該筆資料的位置。資料可採追加寫入方式存放；同一個鍵更新時，寫入新版資料，再將索引改指向新位置。舊版本由背景程序回收。

令 $N$ 為 KV 筆數，$K$ 為 SCAN 回傳筆數：

• GET($x$)：在有序索引中搜尋鍵，時間為 $O(\log N)$；找到後依位置讀取持久儲存中的值。
• PUT($x,v$)：寫入持久資料並更新索引，索引操作時間為 $O(\log N)$。持久寫入延遲另受儲存裝置與同步寫入策略影響。
• SCAN($x_1,x_2$)：先以 $O(\log N)$ 找到第一個不小於 $x_1$ 的索引項目，再沿有序索引走訪至鍵大於 $x_2$，並讀取對應資料，總計 $O(\log N+K)$。

平衡樹讓插入、刪除及搜尋維持 $O(\log N)$，可避免資料量增加後，單筆操作退化成線性搜尋。

隨機與循序存取的效能

隨機 GET 會在索引中跳躍搜尋，時間複雜度為 $O(\log N)$；若被查詢的值所在資料頁也不在快取中，還會產生持久儲存讀取延遲。可搭配作業系統頁面快取，保留常用索引頁或資料頁，降低重複讀取的延遲。

核心觀念

這一小題要求討論「把索引放在磁碟上」的設計（in-disk indexing）。KV 資料總量可能大於記憶體 $x$；當鍵的數量很多、索引本身也大到無法全部常駐記憶體，或希望索引在故障後能直接從磁碟復原時，就要把索引本身也存放在持久儲存裝置上（只放得下時，也可以只把熱門的索引節點快取在記憶體）。設計時要同時考慮：

• GET(x) 的查詢延遲。
• PUT(x,v) 的寫入吞吐量與提交後的持久性。
• SCAN(x₁,x₂) 的範圍查詢效率。
• 多個操作同時執行時的正確性與併發度。
• 當機後如何還原已提交的寫入。

適合此需求的主要索引結構是磁碟式 B+ 樹。B+ 樹將索引分成固定大小的頁面，以頁面為單位讀寫儲存裝置；內部節點負責導引搜尋，所有資料項目依鍵值排序並存放在葉節點。葉節點彼此串連，因此能有效執行範圍掃描。

解題方法：以磁碟式 B+ 樹索引 KV 資料

索引與資料的配置

每筆 KV 資料以鍵值作索引。葉節點可存放：

• 鍵值 $x$。
• 對應的值 $v$，或指向值所在資料頁面的位址。

由於 $v$ 是可變長度位元字串，直接把大型值放進索引頁面會減少每頁可容納的索引項目，增加樹高與分裂次數。因此，可將鍵值與短值放在葉節點；大型值則存放於資料頁面，葉節點保留其位址及長度。若值跨越多個頁面，資料頁面再以鏈結或區段描述方式記錄其位置。

索引頁面與資料頁面皆透過作業系統的緩衝區快取管理。常用的根節點與上層索引頁面可優先留在記憶體，使多數查詢少做磁碟讀取；當快取不足時，系統以替換策略選出頁面寫回或淘汰。

GET(x)：由根節點逐層搜尋

查詢從根節點開始，在每個內部節點依分隔鍵選出下一個子節點，直到抵達葉節點，再找到鍵值 $x$ 及其對應的值或資料位址。

若每個頁面可容納約 $B$ 個索引項目，資料共有 $N$ 筆，B+ 樹高度約為 $O(\log_B N)$。因此，冷快取下的查詢需要約 $O(\log_B N)$ 次頁面讀取；若根節點及上層節點已在記憶體，實際磁碟讀取次數會更少。找到資料位址後，讀取值所在的資料頁面；大型值可能需要額外讀取多個頁面。

SCAN(x₁,x₂)：找到起點後順序掃描葉節點

先像 GET 一樣搜尋第一筆鍵值不小於 $x₁$ 的資料，之後沿葉節點鏈結依序讀取，直到鍵值大於 $x₂$。若回傳 $K$ 筆資料，掃描成本約為 $O(\log_B N + K/B)$ 次頁面讀取，另加上讀取各筆值所需的資料頁面 I/O。

葉節點依鍵值排序並相互串連，使相鄰鍵值通常位於相鄰或鄰近頁面。順序存取時可使用連續讀取、讀取預取及批次回傳，降低每筆資料各自發出 I/O 的成本。隨機存取仍需沿樹搜尋，但索引頁面的快取可減少重複讀取。

PUT(x,v)：更新葉節點並維持樹的平衡

核心觀念

本題的 Caching（快取），是在容量有限的揮發性記憶體中保留常用的鍵值資料或索引資訊，減少對較慢持久性儲存的存取。題目給定 $x\ll y$，且全部鍵值資料可能大於記憶體，因此快取不能假設能保存整個資料集；設計重點是讓有限記憶體盡量保留近期或常用資料，同時避免掃描大量冷資料時把熱門資料擠出快取。

快取命中時可直接由記憶體回覆；快取未命中時，需至持久性儲存查找資料，再視策略決定是否放入快取。若快取命中率為 $h$，記憶體命中延遲為 $T_m$，持久性儲存存取延遲為 $T_p$，則平均讀取延遲可近似表示為：

提高命中率通常能降低延遲、提升吞吐量，但快取管理、同步及寫回也會消耗資源。

解題方法：分別設計查詢快取與寫入快取

GET：快取鍵值資料與查找所需索引

對隨機 GET，可在記憶體建立以 key 為索引的快取目錄，例如雜湊表，記錄快取中的值、資料位置或版本。命中時直接回傳；未命中時由持久性儲存讀取，再依快取策略決定是否載入記憶體。

由於值為變長位元串，快取須計算實際佔用空間，不能只按項目數量計算容量。逐出資料時，也要移除對應的目錄項目；若快取保存的是資料區塊而非完整 KV，則還需維護 key 至區塊位置的索引。

PUT：以持久性記錄保障已提交資料

PUT 除了更新快取，也必須確保資料在系統故障後可復原。可採用寫回式設計：先將 PUT 的操作記錄寫入持久性的寫入前記錄（WAL）並確保已落盤，接著在同步保護下更新記憶體快取／索引，讓新值對後續的 GET 可見，然後才回覆應用程式成功；資料本體可先留在記憶體，之後再批次寫回持久性儲存。這個順序保證「回覆成功之後的 GET 一定讀到新值」。

故障復原時，系統可重播已提交但尚未寫回資料本體的 WAL 記錄。若不使用 WAL，另一種方式是採寫穿式快取：資料寫入持久性儲存後才回覆 PUT。寫穿式較容易維持耐久性，但每次寫入都要等待持久性儲存，延遲較高，吞吐量也較低。

寫回式快取要追蹤髒資料；逐出髒資料前必須先將其寫回，或確保其對應的持久性記錄足以在復原時重建。不得只將尚未持久化的資料從記憶體逐出，否則可能遺失已回覆為提交的 PUT。

SCAN：抑制循序讀取造成的快取污染

核心觀念

Paging（分頁）把連續的虛擬位址空間切成固定大小的「頁」（page），把實體記憶體切成同樣大小的「頁框」（frame）。程式存取尚未載入記憶體的頁時，會發生 page fault，由作業系統從儲存裝置載入該頁；記憶體不足時，作業系統會將部分頁面逐出，以便載入新的頁面。

本題中，KV 資料總量可能大於可用記憶體 $x$，而持久儲存容量為 $y$ 且 $x\ll y$。可將 KV 檔案映射到虛擬位址空間，讓作業系統以分頁方式按需載入資料。記憶體不足時，頁面由作業系統管理，因此不必把整份 KV 資料一次放進 RAM。

解題方法與設計

可將鍵值資料及其有序索引存放在持久儲存的檔案中，再以記憶體映射或作業系統頁面快取提供資料存取。索引可採用 B+ 樹等有序結構，讓 GET 依鍵查找、SCAN 依鍵範圍走訪葉節點。

• GET($x$)：先查索引，找到包含鍵 $x$ 的索引頁，再讀取對應資料頁。若頁面已在 RAM，直接存取；若不在，則由 page fault 載入。查找時間主要取決於索引高度及缺頁次數。
• PUT($x,v$)：找到或配置對應資料頁，更新鍵值資料與索引，並將被修改的頁標記為 dirty page。記憶體中的修改可延後寫回，但只有完成持久化協定後，才能向應用程式確認 PUT 已提交。
• SCAN($x_1,x_2$)：從索引定位至第一個符合 $x_1$ 的位置，再依序走訪鍵不大於 $x_2$ 的項目。若連續資料位於相鄰頁面，作業系統可預讀後續頁面，減少等待儲存裝置的時間。

存取型態與效能

隨機存取的鍵分散在不同頁面，工作集超過 RAM 時，反覆讀入和逐出頁面會增加 page fault，造成延遲上升、吞吐量下降。可讓索引頁優先留在記憶體，並依近期存取情形保留熱門資料頁；快取容量不足時，使用 LRU 或其近似策略逐出較少使用的頁面。

核心觀念

**Batched I/O（批次輸入／輸出）**是先將多個 I/O 操作收集成一批，再一起送往儲存裝置或檔案系統處理。它主要降低每次 I/O 的固定成本，例如系統呼叫、核心與裝置間的切換、命令提交，以及磁碟定位；因此通常能提高吞吐量。

若每筆 I/O 的固定成本為 $h$、傳輸成本為 $d$，逐筆執行 $n$ 次約需：

若每批處理 $b$ 筆，固定成本可由整批分攤，總成本約為：

批次愈大，固定成本分攤愈多；但等待更多請求湊成一批也會增加單筆延遲。

解題方法與設計

系統可在核心或 KV 儲存服務端設置有界 I/O 佇列，將併發操作收集後，以非同步 I/O、io_uring、多命令佇列等方式提交。佇列需設最大批次大小與等待時間上限，避免低流量時請求久候，也避免佇列無上限成長。

**GET 與隨機讀取：**多個讀取可一起提交，讓裝置同時處理多筆請求。若讀取的資料位於相鄰區塊，可合併成較大的讀取；若位置分散，仍可藉由併發提交提高裝置利用率。隨機讀取不一定能合併成連續 I/O，因此效益主要來自減少提交成本與提高並行度。對延遲敏感的 GET，可採短等待時間或立即提交。

**SCAN 與連續讀取：**SCAN 會取回一段鍵值範圍，適合一次讀取多個相鄰區塊，並預先讀取後續區塊。這可減少逐筆查詢及小型 I/O 的開銷，增加連續傳輸比例。遇到大型 SCAN 時，批次大小仍需受緩衝區與記憶體限制，避免排擠其他請求。

核心觀念

本題的重點是利用多執行緒同時處理 GET、PUT、SCAN，提升 KV 儲存服務的吞吐量，同時避免共享資料競爭、長時間等待與執行緒資源耗盡。

執行緒可共享同一程序的位址空間與資料結構，建立成本通常低於程序，但共享索引、記憶體快取與持久化緩衝區必須同步。鎖保護的範圍越大，管理越簡單，但競爭越嚴重；範圍越小，並行度越高，但同步與死鎖管理越複雜。

解題方法：把工作拆成請求處理與共享資源同步

1. 以有限大小的工作執行緒池處理請求
   將到達的請求放入佇列，由多個工作執行緒取出並執行。相較於每個請求都建立新執行緒，固定大小的執行緒池可避免高負載時建立過多執行緒，減少排程與記憶體開銷。執行緒數量應配合 CPU 核心數及儲存裝置的 I/O 延遲調整：執行緒過少會讓執行緒等待 I/O 時閒置 CPU；過多則會增加切換與同步成本。

2. 按操作性質安排並行處理
   GET 常受儲存裝置讀取延遲影響；PUT 除了更新資料，也需要處理持久化；SCAN 則可能連續讀取大量資料。執行緒等待 I/O 時，作業系統可排程其他就緒執行緒使用 CPU，提升 CPU 與儲存裝置的重疊利用率。

   若 SCAN 長時間佔用一般工作執行緒，短小的 GET、PUT 會在佇列中延遲。因此可限制單次 SCAN 的處理批次，分段交還排程，或為掃描與一般請求配置不同的工作佇列及執行緒配額。排程應兼顧短請求延遲與各類請求的公平性，避免大量掃描使其他操作長時間飢餓。

3. 以適當粒度同步共享資料
   若所有索引與資料都由單一全域鎖保護，任一操作持鎖時，其餘操作都得等待，吞吐量會受限。可依鍵值範圍、索引節點或資料分片設鎖，使存取不同區域的請求並行執行。

核心觀念

本題考查以共享記憶體支援多個執行緒或處理程序同時操作 KV 儲存時，如何兼顧資料一致性、操作併行度與故障復原。

共享記憶體讓多個執行緒或處理程序映射並存取同一份記憶體區域。它省去程序間傳送資料的複製成本，但多個操作若同時讀寫索引或資料，會產生競爭條件，因此必須搭配同步機制。

一致性可用線性化性描述：每個操作看起來都在呼叫與回傳之間的某一瞬間完成，且所有操作都能排列成符合即時先後關係的序列。對 KV 服務而言，這代表並行執行的 GET、PUT、SCAN，對外呈現的結果等同於某個合法的循序執行結果。

解題方法

採用「共享記憶體放索引與快取、持久儲存保存正式資料、鎖定保護共享狀態、寫前日誌確保提交可復原」的設計。

共享記憶體中可放置索引、快取資料、鎖與日誌緩衝區。當 KV 資料量超過可用記憶體 $x$ 時，記憶體只保留索引與熱資料；冷資料留在容量較大的持久儲存 $y$。索引可依鍵排序，以支援範圍查詢。共享記憶體本身是易失性記憶體，不能單獨提供已提交資料的持久性保證。

同步與一致性

最直接的實作是以一把全域讀寫鎖保護索引與共享資料：

• GET 取得讀鎖，查詢索引並讀取資料；多個 GET 可同時執行。
• PUT 取得寫鎖，更新索引與共享資料；寫鎖期間不允許其他操作讀寫受保護狀態。
• SCAN 取得讀鎖並完成整段範圍掃描，確保掃描過程中沒有 PUT 插入或刪除項目。

此設計容易達成線性化性，但全域寫鎖會使寫入彼此序列化，且長時間的 SCAN 會阻塞 PUT，降低吞吐量。

為提高併行度，可把索引切分成多個分區，各分區使用獨立讀寫鎖。不同分區的 GET、PUT 可同時執行；跨分區 SCAN 則依固定順序取得各分區讀鎖，再釋放鎖。固定鎖定順序可避免死鎖。若要讓 SCAN 在長時間執行時仍取得一致視圖，可使用版本號或多版本併發控制（MVCC）：掃描開始時記錄資料版本，只讀取該版本以前已提交的資料。

共享記憶體中的同步物件可由作業系統提供，例如程序間互斥鎖、讀寫鎖、信號量或 futex。若共享狀態涉及多個欄位，需以鎖保護整段更新；若使用原子變數，也需搭配適當的記憶體順序，確保一個處理器的更新在另一個處理器讀取時可見。

持久性與故障復原

核心觀念

編碼與解碼的目標，是把應用程式中的鍵值資料轉成可持久化、可定位且可還原的位元組格式。編碼格式必須能明確界定每筆資料的邊界，並保留鍵的排序關係，才能支援 GET 的單筆讀取與 SCAN 的範圍查詢。

題目中的鍵長度固定、值長度不固定，因此適合將鍵以固定長度表示，並在值之前儲存其長度。若另外使用壓縮，可減少磁碟與 I/O 使用量，但會增加編碼、解碼的 CPU 時間；是否採用須以整體延遲與吞吐量衡量。

解題方法：設計資料格式

令鍵長為 $L$，並假設鍵使用固定字元集，例如固定大小寫規則的英文字母。將每個字元編碼為固定寬度位元組，則鍵占用固定空間。為了讓磁碟上的鍵順序與查詢排序一致，編碼應採用能保留字典序的表示方式；若大小寫或字元排序未先正規化，SCAN 的範圍邊界可能與應用程式預期不同。

值是變長位元串，需先記錄其位元長度 $b$，再記錄值本身。概念上的一筆記錄可表示為：

其中 $\Vert$ 表示串接。若以位元組為單位儲存，位元長度可用來區分末尾補齊位元與真正的值內容；否則不同長度的位元串可能無法正確還原。長度欄位本身採固定寬度或變長整數編碼，需依值大小範圍與解析成本取捨。

編碼與解碼流程如下：

核心觀念

本題考查如何安排檔案系統中的資料區塊，讓 KV 儲存同時支援隨機查詢、區間掃描、併發操作與故障復原。關鍵是把邏輯上的鍵值順序映射到磁碟上的區塊位置，並盡量讓相鄰鍵落在相鄰或鄰近的區塊。

磁碟以固定大小的區塊讀寫，而 value 長度可變，因此需要索引來找到資料位置。適合的配置是以 B+ 樹維護鍵的排序：內部節點保存搜尋用的分隔鍵，葉節點保存鍵、value 位置等資料。葉節點按鍵值順序連結，便於執行 SCAN。

解題方法

採用「索引區塊＋排序資料區塊＋日誌區塊」的檔案配置：

1. 索引區塊：以 B+ 樹內部節點組成索引。每個節點放入多個鍵與子區塊指標，降低樹高與磁碟讀取次數。
2. 資料區塊：B+ 樹葉節點依鍵值順序保存 KV 記錄或 value 指標，並以兄弟指標連接相鄰葉節點。
3. 大型 value 區塊：短 value 可直接放在葉節點；較長的 value 放在獨立資料區塊，由葉節點記錄起始區塊與長度，避免大型 value 擠壓索引節點。
4. 日誌區塊：在正式更新資料區塊前，先將更新寫入預寫日誌（WAL）。確認日誌已持久化後，才回覆 PUT 成功。

區塊配置與操作流程

在檔案系統中，應優先以 extent 配置資料區塊：一個 extent 對應一段連續或相鄰的磁碟區塊。當葉節點或 value 空間不足時，盡量從附近配置新的 extent，降低磁碟讀寫頭移動並提高連續讀寫效率。實際磁碟位置由檔案系統管理，應使用連續配置或預先配置等機制改善區塊區域性。

• GET(x)：從根節點開始，依分隔鍵逐層找到含有 $x$ 的葉節點，再讀取 value。B+ 樹高度約為 $\log_B N$，其中 $B$ 是每個索引區塊可容納的分支數，$N$ 是鍵值筆數。

核心觀念

這題的「檔案系統壓縮整理」可用**日誌式儲存與合併（compaction）**實作：更新資料先以追加方式寫入持久儲存，避免每次更新都在原位置改寫；背景工作再整理舊資料、回收空間。這也就是 LSM-tree 常用的資料整理方式，與日誌結構檔案系統的清理概念相近。

追加寫入能讓 PUT 主要執行循序寫入；代價是磁碟上會累積同一個 key 的多個版本、已失效資料與刪除標記。Compaction 將多個已排序的資料檔合併，保留有效資料並回收空間。

解題方法

將持久資料分成不可變的排序檔案（SSTable），每個檔案內的 key 依序排列，並保存索引與最小、最大 key 範圍。記憶體中的新資料先寫入追加式日誌及記憶體表；記憶體表滿後，凍結並輸出成新的排序檔案。背景 compaction 按 key 順序讀取多個檔案，再按 key 順序寫出合併後的檔案。

例如，若不同檔案中有下列版本：

• 檔案 A：$(a,1)$、$(c,3)$
• 檔案 B：$(b,2)$、$(c,4)$

合併時按 key 排序；同一 key 有多個版本時，保留最新版本，因此輸出 $(a,1)$、$(b,2)$、$(c,4)$。若某 key 有刪除標記，compaction 可在確定舊版本不會再被較舊資料復活時，一併移除該 key 的舊資料與標記。

對 GET、PUT 與 SCAN 的影響

• GET：合併可減少同一 key 分散在多個檔案的情況，使讀取時需要查詢的檔案數下降。索引與 key 範圍資訊可先排除不可能包含該 key 的檔案。
• PUT：前景寫入採追加方式，避免隨機覆寫；但 compaction 會在背景搬移資料，增加磁碟讀寫量，形成寫入放大。