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

A novel strategy for write-amplification reduction in LSM-tree-based Key-Value Store

蕭智陽(Zhi-Yang Xiao)

指導教授 ： 張立平

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2017年)

摘要

近年來鍵值儲存在許多方面都被廣泛地運用，包含大型的資料中心或是一些資料密集的應用，如:社交網路、資料重複刪除，和線上遊戲方面等。以日誌結構合併樹為基準的鍵值儲存，由於其能將隨機寫入消除，適合用於寫入密集的工作負載環境，但不幸地，它卻有很高的寫入放大率問題。因此對於日誌結構合併樹，我們以一個著名的鍵值儲存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.

並列關鍵字

Key-Value Store ； Log-Structured Merge Tree ； Write Amplification ； Spatial Locality

參考文獻

[10] O’Neil, Patrick, et al. "The log-structured merge-tree (LSM-tree)." Acta Informatica 33.4 (1996): 351-385.

[23] Zhang, Hao, et al. "Efficient in-memory data management: An analysis." Proceedings of the VLDB Endowment 7.10 (2014): 833-836.

[24] Chang, Yisong, et al. "Extending On-chip Interconnects for rack-level remote resource access." Computer Design (ICCD), 2016 IEEE 34th International Conference on. IEEE, 2016.

[1] http://cassandra.apache.org/

[2] http://dynamobim.org/