Research On Indexing Method Of Distributed In-Memory Key-Value Storage System

With the gradual popularization of cloud computing,the distributed in-memory key-value storage system has developed rapidly,and it has received more and more attention due to its excellent memory access performance and support for unstructured data.Index designing is a key part of the distributed in-memory key-value storage system,which profoundly affects the time performance and memory overhead of the system.Due to the emergence of low-latency RDMA(Remote Direct Memory Access)technology in recent years,developing a RDMA-friendly indexing method has become a new requirement for designing efficient distributed in-memory key-value storage systems.This thesis uses an index method without index node splitting or merging to build an RDMA-based distributed in-memory key-value storage system,which can reduce the round-trip delay of operations while cutting down on the cost of data consistency maintenance.This thesis first designs the main index on the server side,then builds the low-space index mapping and concurrent access mechanism on the client side,and implements an efficient distributed index system for in-memory key-value storage.The main work and contributions of this thesis are as follows:(1)Server-side high-performance indexIn the distributed in-memory key-value storage system,the tree structure is often used as the server-side index to handle operations such as insertion and deletion,and provide dynamic load support for the system.However,the overhead of maintaining dynamic data in the tree index is large,which is not conducive to the RDMA concurrent access of the client,and there is a problem on optimizing the memory cost of index.To this end,this thesis designs a server-side index based on the van Emde Boas structure and the corresponding basic operation algorithms.The index uses a block containing a bitmap structure as the basic unit of data storage.Inserting and deleting data only involving modification within the block,and data blocks do not need to be split or merged,significantly improving the time performance of basic operations.The experimental results show that,compared with the B-tree index,the throughput on dynamic load of the server-side index based on the van Emde Boas structure is increased by 6.01 times,and the memory occupation is reduced by 76.33%.(2)Client-side low-memory index mappingIn the RDMA-based distributed in-memory key-value storage system,the client reduces accessing the server-side memory and improves the efficiency of remote access by constructing the corresponding mapping of the server-side main index.However,the current Btree-based client-side index mapping method takes up a lot of memory,and each query still requires multiple remote accesses,the memory and time performance of which needs to be optimized.To this end,this thesis designs a client-side index mapping method based on the van Emde Boas structure.The index mapping uses a hash table to compress the memory of the common prefix keys,and stores the accessed data block information on demand,which greatly reduces the memory overhead of the client.In addition,this thesis uses a lightweight concurrent access mechanism based on the version number to improve the concurrent performance of the system.The experimental results show that,compared with the distributed memory key-value storage system XStore using B-tree index and its mapping,the client-side index mapping based on the van Emde Boas structure reduces the memory occupation by 87.7%,and the throughput of remote operations is improved by 47.4%.