Fault-tolerant precise data access on distributed log-structured merge-tree  

作　　者：Tao ZHU Huiqi HU Weining QIAN Huan ZHOU Aoying ZHOU 

机构地区：[1]School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

出　　处：《Frontiers of Computer Science》2019年第4期760-777,共18页中国计算机科学前沿（英文版）

基　　金：National Hightech R&D Program (2015AA015307);the National Natural Science Foundation of China (Grant Nos. 61702189, 61432006 and 61672232);Youth Science and Technology -“Yang Fan” Program of Shanghai (17YF1427800).

摘　　要：Log-structured merge tree has been adopted by many distributed storage systems. It decomposes a large database into multiple parts: an in?writing part and several read-only ones. Records are firstly written into a memoryoptimized structure and then compacted into in-disk struc? tures periodically. It achieves high write throughput. However, it brings side effect that read requests have to go through multiple structures to find the required record. In a distributed database system, different parts of the LSM-tree are stored in distributed fashion. To this end, a server in the query layer has to issues multiple network communications to pull data items from the underlying storage layer. Coming to its rescue, this work proposes a precise data access strategy which includes: an efficient structure with low maintaining overhead designed to test whether a record exists in the in?writing part of the LSM-tree;a lease-based synchronization strategy proposed to maintain consistent copies of the structure on remote query servers. We further prove the technique is capable of working robustly when the LSM-Tree is re?organizing multiple structures in the backend. It is also fault-tolerant, which is able to recover the structures used in data access after node failures happen. Experiments using the YCSB benchmark show that the solution has 6x throughput improvement over existing methods.

关 键 词：DISTRIBUTED data storage log-structured MERGE TREE LINEARIZABILITY fault tolerance 

分 类 号：TP[自动化与计算机技术]