基於LSM-tree鍵值儲存用於減少寫入放大率之策略

Abstract

近年來鍵值儲存在許多方面都被廣泛地運用，包含大型的資料中心或是一些資料密集的應用，如:社交網路、資料重複刪除，和線上遊戲方面等。以日誌結構合併樹為基準的鍵值儲存，由於其能將隨機寫入消除，適合用於寫入密集的工作負載環境，但不幸地，它卻有很高的寫入放大率問題。因此對於日誌結構合併樹，我們以一個著名的鍵值儲存LevelDB為模擬對象。關於其壓縮操作會涉及的犧牲者選擇策略，本篇論文在針對具有空間區域性的工作負載下，提出另一種新的選擇策略，藉由挑選關聯度最小的SSTable當作犧牲者，以減少寫入放大率。從實驗結果顯示，我們的方法和預設的輪流方法相比，寫入放大率改善了30%左右。

In recently year, key value stores are widely used for various ways, including large-scale data centers or in some data-intensive applications, such as social networking, data deduplication, and online gaming. The log-structured merge tree based key value stores are applicable for write-intensive workload because they can eliminate random writes. Unfortunately, there also exists a problem which is high write amplification in LSM-tree. In order to study about LSM-tree, we simulated a key value store based on LevelDB which is well –known. Our study presents a novel selection policy under spatial locality workload, which is a victim selection policy in compaction operation. By choosing the SSTable with the minimal number of the associativity as the victim, it can reduce the write amplification ratio. The experimental results show that our strategy compared to the LevelDB’s default Round-Robin method improves about 30% in write amplification ratio under spatial locality.