Diff-Index: Differentiated Index in Distributed Log-Structured Data Stores
Wei Tan, Sandeep Tata, Yuzhe Tang, Liana Fong · 2014
Log-Structured-Merge (LSM) Tree gains much attention re-cently because of its superior performance in write-intensive workloads. LSM Tree uses an append-only structure in memory to achieve low write latency; at memory capac-ity, in-memory data are flushed to other storage media (e.g. disk). Consequently, read access is slower comparing to write. These specific features of LSM, including no in-place update and asymmetric read/write performance raise unique challenges in index maintenance for LSM. The structural difference between LSM and B-Tree also prevents mature B-Tree based approaches from being directly applied. To address the issues of index maintenance for LSM, we pro-pose Diff-Index to support a spectrum of index maintenance schemes to suit different objectives in index consistency and performance. The schemes consist of sync-full, sync-insert, async-simple and async-session. Experiments on our HBase implementation quantitatively demonstrate that Diff-Index offers various performance/consistency balance and satisfac-tory scalability while avoiding global coordination. Sync-insert and async-simple can reduce 60%-80 % of the overall index update latency when compared to the baseline sync-full; async-simple can achieve superior index update per-formance with an acceptable inconsistency. Diff-Index ex-ploits LSM features such as versioning and the flush-compact process to achieve goals of concurrency control and failure