Study On High Performance And Scalable Key-Value Stores

Large-scale data-intensive applications have gained great popularity in the past few years,in the mean time,Key-Value stores have been getting more attention over tradi-tional relational database,and are widely used as the fundamental storage infrastructure in many applications.Key-Value stores adopt a flat data organization and a much sim-plified interface to operate data,which makes Key-Value stores naturally suitable for the unstructured data and more scalable.However,due to the exponential growth of data volume and the complexity of data types,the scalability of Key-Value stores will limited by the metadata management and the load imbalance problem.Therefore,how to optimize metadata management and system load balancing mechanism is the key is-sue to build a high performance and scalable key-value stores.This dissertation mainly studies the in-memory and on-disk Bloom filter management for the single node Key-Value stores,and the multi-dimensional load balancing mechanism for the distributed Key-Value Stores.The main research contents and contributions are as follows:(1)Research on Memory Oriented Bloom Filter Management StrategyLSM-Tree based Key-Value stores adopts a multi-layer design to organize data.In order to find a Key-Value pair,the system needs to check multiple SSTable files,re-sulting in multiple I/Os,which will lead to serious read amplification problems.To re-duce extra I/Os,Bloom filters are usually deployed in Key-Value stores to improve read performance.However,Bloom filters suffer from false positives,and simply enlarg-ing the size of Bloom filters introduces large memory overhead,so it still causes extra I/Os in memory-constrained systems.To solve this problem,we develop ElasticBF,a fine-grained heterogeneous Bloom filter management scheme with dynamic adjustment according to data hotness.ElasticBF generates multiple smaller Bloom filter for each data region,and then dynamically adjust the number of filters in memory according to the hotness of data region,so as to achieve the purpose of dynamic adjustment of over-all false positive rate,therefore reduces the extra I/Os caused by false positive so as to improve read performance.We build ElasticBF atop of LevelDB,RocksDB,and Peb-blesDB,and our experimental results show that ElasticBF increases the read throughput of the above KV stores to 2.34×,2.35× and 2.58×,respectively,while keeps almost the same write and range query performance.(2)Research on Disk Oriented Bloom Filter Management StrategyFor a giver capacity,smaller Key-Value pairs demand more Bloom filter to lo-cate them,which results in the volume of Bloom filters exceeds the memory capacity,some filters will be swapped out to secondary storage,which induces extra I/Os and in-creases the read amplification.Existing solutions develop the strategy by gathering the separate Bloom filters into a single disk block,therefore only one disk read of Bloom filters is needed during the lookup procedure.However,these strategies need to fre-quently reorganize the on-disk Bloom filter layout,and the total read size of Bloom filter will increase with the database size,which will lead to serious read and write am-plification problems.To solve these problems,we propose SegmentBF,a Bloom filter management strategy based on grouping layout,which can efficiently manage the on-disk Bloom filters.SegmentBF redesigns the on-disk Bloom filter layout based on the idea of segmenting and grouping.Specifically,we first divide each Bloom filter into blocks based on hashing,so each lookup only needs to read one of the blocks.Next,We divide Bloom filters of different files into multiple groups,therefore only one group of Bloom filters needs to be reorganized when new file is written to the disk.Finally,we periodically merge the groups of Bloom filters on the disk so as to reduce the number of I/Os to fetch Bloom filter.Experimental results show that,SegmentBF can reduce the write amplification caused by reorganizing Bloom Filter layout,and reduce the amount of I/Os during lookups.As a result,SegmentBF improves the write and read throughput performance by 36.4%and 36.2%,respectively.(3)Research on Load Balancing for Distributed Key-Value StoresExisting works reveal that the accessing of real-world workloads have strong spa-tial locality,that is,a few Regions in the system absorb most of the accesses.Besides,we observe that the size distribution of Key-Value pairs also exhibits spatial locality,that is,Key-value pairs of similar size are usually clustered in the same Region.These work-load characteristics can lead to an asymmetric distribution between QPS and through-put,which makes some Regions absorb many requests but the total amount of accessed data is small,while other regions are opposite.As a result,CPU and disk bandwidth resources become imbalance between nodes,which limits the system performance.To solve this problem,we propose a lightweight multi-dimensional load balancing strat-egy,namely MultiSched.Specifically,we first formulate the multi-dimensional load balancing problem as an integer linear programming(ILP)problem,and then provide a sufficient condition that the ILP is feasible.Base on these theoretical result,we de-velop a lightweight multi-dimensional load balancing algorithm,which schedules re-gions through local decisions so as to gradually achieve the equilibrium.Further,to deploy the algorithm in the practical system,we design a scheduling strategy based on timing to avoid affecting the system scheduling decisions due to load fluctuations,and design a selective Region splitting mechanism to reduce the splitting overhead.Finally,we implement the load-based Region splitting mechanism based on sampling method,which enables us to split the high-loaded Region into several less-loaded re-gions with low overhead.Experimental results show that MultiSched can effectively solve the multi-dimensional load imbalance problem,and can significantly reduce the tail latency.