Research On Integrated Append-and-Merge Trees

Cheap and numerous information-sensing devices,social networking,e-commerce and on-line gaming produce data at unprecedented rates.The increasingly large data volumes are becoming commonplace nowadays.An index tree meets the challenge to effectively load,update,search and analyze large amounts of data.The classic ones,such as B-Tree,have poor write performance and are inept for write-intensive workloads under big data.However,the Log-Structured Merge Tree(LSM-tree)is adopted widely for write demands in key-value stores.Substitution of sequential reads and writes for random ones greatly improves the write performance over the classical B-tree.However,with large amounts of data inserted,LSM suffers from high write amplification because of frequent node merges.Consequently,the write throughput deteriorates and storage devices with limited write life span are easier to wear out.At the same time,it also decreases the read performance since it incurs massive competitive on-disk writes with the original user reads.To address the issue,we first design a new tree named the Log-Structured Append-tree(LSA-tree)to substitute appends for merges in LSM.However,LSA incurs large read amplification for scan and large space amplification.Furthermore,by integrating LSA with merges,we propose the Integrated Append-and-Merge Tree(IAM-tree)with the advantages of both LSM and LSA.I AM utilizes the size of the memory-cached data to make the choice between appends and merges.We implement IAM in a user library named IamDB.The write amplification of IAM is much smaller than that of LSM,that is,only 8.71 vs.19.00 for 1TB data with 64GB memory.Furthermore,IAM obtains the same read and space amplifications as LSM.Compared to both nicely tuned LevelDB and RocksDB,IAM respectively provides 1.4-2.7 and 1.6-1.9 X better write throughput,the same read performance and comparable scan performance,and respectively saves 12%and 10%disk space.