The Design And Implementation Of Persistent In-memory Key-value Database For Non-volatile Memory

In order to make sure that the data will not be lost,the current main memory database will back up the data in main memory to disk.The efficiency of the memory database will be inevitably reduced because of the backup operation and the introduction of I/O operations.In recent years,nonvolatile memory(NVM)has the characteristics of power loss without loss of data,byte addressability and read and write speed.If the memory database is deployed on NVM,it can greatly improve the efficiency of the database.However,the existing main memory database cannot make good use of the advantages of NVM,there are three main problems: 1)The existing main memory database using the operating system managing the temporary memory and data structure,it may be recovered or replaced to external memory,2)The consistency mechanism of the existing main memory database depends on the block device file system,cannot use NVM by byte addressing and other characteristics to improve performance;3)The database data size mostly is small,need to be memory space management with fine Granularity.Therefore,the main idea of this paper is to design a new the key-value memory database based on non-volatile memory.Compared with the traditional main memory database,the database based on non-volatile memory should make sure the access efficiency,but also avoid data loss,database backup and I/O operation.Our work has done three main tasks.First,we design a non-volatile memory physical space management system.Operation on non-volatile memory is done directly on non-volatile memory by mapping it directly to the address of user space.We manage free space through free space links and bitmaps.Large space allocation is allocated directly on the free list,and the small space allocation adopts the pre-distribution method to reduce the operation on the free list.This allocation strategy reduces internal fragmentation and increases the efficiency of small spaces allocation.Second,to make sure database persistently store on non-volatile memory,we need to design the database metadata information.When the database is stored in non-volatile memory,although it is non-volatile,but the specific location information and index information is disappear,we cannot recovery the database.Therefore,we save the database index and organizational structure information at a fixed location in the non-volatile memory device.In the situation of restart or system power-down,we can still quickly restore the database.Finally,due to the usage of nonvolatile memory,we redesign a consistency strategy.Ordinary disk database ensure consistency relying on the consistency of the file system mechanism,but it is not applicable on non-volatile memory.We through the log and Copy-on-write(COW)strategy to ensure the consistency of the database.This way can ensure strong consistency,while also ensure high concurrency.According to the technology proposed in this paper,we achieve a non-volatile memory based persistent main memory database based on the open source key-value memory database Redis,Persistent Redis(PRedis).Compared to Redis,PRedis has nonvolatile memory management units,database metadata,and consistency algorithms.We use standard tools to verify PRedis performance.In the case of the amount of data is 10 million,our database startup and shutdown efficiency has 1000 times upgrade.In the same condition,our database running performance is 1,000 times higher than the Redis persistency on disk,compared to the persistence on the EXT4-DAX main memory file system,our database efficiency also has 84.5% improvement.