| 摘要: | 基於 Log-Structured Merge-tree (LSM-tree) 的鍵值儲存系統（如
RocksDB）因其高寫入吞吐量而廣泛應用於現代儲存系統。然而，其效能在壓縮
（compaction）過程中會顯著下降。壓縮是一項維護操作，需進行大規模的鍵
值排序以維持資料組織結構，而排序階段往往成為主要的效能瓶頸，消耗大量
的 CPU 資源。在本研究中，我們提出 MAC-Sort，一種基於運算式記憶體
（Compute-In-Memory, CIM）的排序加速器，用於卸載並加速壓縮過程中的排
序操作。MAC-Sort 採用以電阻式記憶體（Resistive RAM, ReRAM）為基礎的類
比內容可尋址記憶體（Analog Content Addressable Memory, ACAM）。 ReRAM
是一種新興的非揮發性記憶體技術，具有高密度、低存取延遲及適合記憶體內
運算的特性。構建於 ReRAM 之上的 ACAM 擴展了傳統 CAM 的能力，能夠透過
多位元類比狀態進行並行的範圍比較。憑藉 ACAM 的大規模平行性與範圍匹配
能力，MAC-Sort 能在記憶體中實現高通量的基數排序。該架構整合了
histogram、prefix-sum 與 scatter 等專用運算模組，並採用混合的最高有效
位元（Most Significant Digit, MSD）與最低有效位元（Least Significant
Digit, LSD）排序策略，對 DRAM 與 SRAM 的鍵值處理皆進行最佳化。實驗評
估結果顯示，MAC-Sort 能顯著降低壓縮操作中的排序延遲，從而有效解決
LSM-tree 鍵值儲存系統在可擴展性上的關鍵挑戰。;Log-Structured Merge-tree (LSM-tree) based key–value stores, such as RocksDB, are
widely used in modern storage systems due to their high write throughput. However,
their performance suffers significantly during compaction—a maintenance operation
that involves large-scale key sorting to maintain data organization. This sorting phase
often becomes the dominant performance bottleneck, consuming substantial CPU time.
In this work, we present MAC-Sort, a Compute-In-Memory (CIM) sorting accelerator
that offloads and accelerates the compaction sorting process using ReRAM based
Analog Content Addressable Memory (ACAM).Resistive RAM (ReRAM) is an
emerging non-volatile memory technology known for its high density, low access
latency, and suitability for in-memory computing. ACAM, built atop ReRAM, extends
the capabilities of traditional CAMs by enabling parallel, range based comparisons
using multi-bit analog states. By leveraging the massive parallelism and range
matching capabilities of ACAM, MAC-Sort performs high-throughput radix sorting
within memory. The architecture includes dedicated histogram, prefix-sum, and scatter
phases, integrated with a hybrid Most Significant Digit (MSD) and Least Significant
Digit (LSD) sorting strategy, and is optimized for both DRAM and SRAM-based key
handling. Evaluations show that MAC-Sort significantly reduces sorting latency in
compaction operations, addressing a critical scalability challenge in LSM-tree key
value stores. |
