Research On Key Technologies For High-Concurrency Non-Volatile Memory Systems

With the boom in emerging applications such as artificial intelligence and social media,the total amount of data is growing rapidly.To efficiently store massive data,storage systems need to provide high performance without software bugs.The performance of the emerging byte-addressable Non-Volatile Memory(NVM)is close to that of Dynamic Random Access Memory(DRAM).In the meantime,NVM exhibits the characteristic of non-volatility and high storage density.Leveraging NVM as the main memory of a computer system is promising to improve the performance of storage systems.However,NVM systems face the problems of high write overhead and crash consistency.The problem of high write overhead refers to that the write performance of NVM is worse than the read performance and NVM suffers from limited write endurance.Existing studies optimize the write overhead of NVM systems at different layers.At the software system layer,the number of write operations is reduced by existing concurrent NVM data structures of storage systems.At the hardware architecture layer,the amount of NVM write data is reduced by existing data compression schemes.However,the lock-based concurrency control mechanisms in existing NVM data structures face the concurrency performance bottleneck,and the compression efficiency of existing write optimization schemes based on data compression is limited for lots of data that can tolerate precision loss.Therefore,existing studies are difficult to meet the high-concurrency performance requirements for high throughput and low latency.In addition,the persistence of NVM enlarges the persistence domain in the storage system so that the memory data would not be lost upon power failures,thus requiring the crash-consistency guarantee.With the new NVM-based storage architecture,NVM systems are prone to software bugs of crash consistency.However,existing bug detection schemes do not consider the concurrency crash-consistency bugs of NVM systems caused by multi-threaded interleaved executions.In order to address the problems of high write overhead and crash consistency of NVM,this dissertation investigates three key technologies,including concurrent NVM data structures,write optimization based on data compression,and crash-consistency bug detection,for performance optimization and system reliability to build high-throughput,low-latency,and reliable high-concurrency NVM systems.In terms of concurrent NVM data structures,to address the concurrency bottleneck of resizing and query operations in existing data structures,an NVM-friendly lock-free concurrent hashing scheme,called Clevel Hashing,is proposed to improve the performance of concurrent queries to non-volatile memory data.Clevel Hashing leverages a dynamic multi-level structure,where the number of buckets in the upper level in any two adjacent levels is twice as many as the lower level.To expand the capacity,a new top level is added and only the key-value items in the bottom level are migrated to the new top level by background threads,which reduces the amount of migrated data in the hash table and avoids blocking concurrent operations of worker threads.Clevel Hashing co-designs NVM allocators and the index structure with NVM-friendly optimizations,including thread-local lock-free allocation,write-optimized operations,and lightweight crash-consistency guarantee.In terms of concurrency control,by leveraging hardware atomic instructions,Clevel Hashing achieves lock-free concurrent operations.Experimental results show that Clevel Hashing achieves up to 5.7x and 1.6x higher concurrent throughput than representative static and dynamic hash schemes for NVM,respectively,while achieving lower tail latency for operations.In terms of write optimization based on data compression,to address the problem of high overhead of NVM writes and the limited efficiency of existing write optimization designs,a parallel similarity-aware approximate compression scheme,called Sim Com(Similarity-aware Compression),is proposed to reduce the write latency of high-concurrency NVM systems.The analysis of experimental results reveals that there are many image bitmap data that can tolerate minor accuracy loss in some applications such as computer vision and artificial intelligence.Experimental results show that there are lots of similar words in bitmap data in NVM write requests.Sim Com compresses a group of continuous similar words in the write request into a base word with the corresponding count,reducing the write overhead of similar words.In the meantime,the compression modes for different bitmap formats are run in parallel,and the output of the compression mode with the smallest mean difference is selected as the result of adaptive approximate compression.Experimental results show that under 3% image quality loss,compared to representative schemes such as FPC,BDI,and Bi Scaling,Sim Com respectively reduces write latency by 19.6%,26.3%,and 30.0%,and energy consumption by 18.3%,22.2%,and 21.0%.Moreover,Sim Com also reduces the NVM write overhead for video applications.In terms of crash-consistency bug detection,to address the problem of concurrency bugs of crash consistency in NVM systems,two concurrency crash-consistency bug patterns,including Inter-thread Crash Inconsistency and Synchronization Crash Inconsistency,are analyzed and summarized.An NVM-based fuzz testing scheme,called PMRace,for concurrency crash-consistency bugs is proposed to improve the software reliability of high-concurrency NVM systems.PMRace instruments the NVM access and persist instructions of the program to be tested by using a compiler pass,and schedules threads to prioritize the testing of interleavings of read-after-write instructions to the same address to detect the inconsistency issues for reading non-persisted data or modifying synchronization data.Based on the related analysis,the NVM-specific alias coverage is proposed to record the explored interleavings during testing to dynamically tune the fuzzing strategies for subsequent testing.A post-failure validation mechanism is proposed.During the recovery phase,PMRace checks if the previously detected inconsistencies are automatically fixed by the system recovery code,thus reducing the false positive rate of crash-consistency bug detection.In five open-source NVM concurrent systems,PMRace has found 14 software bugs,including 10 new bugs.