비 휘발성 메모리의 일관성 보장 비용 최소화에 대한 연구

Abstract

Non-volatile Memory(NVM) can improve the I/O performance and capacity of the system by providing persistence and high density that conventional DRAM did not. Because NVM can have both I/O performance and storage continuity close to DRAM through these device characteristics, NVM can be widely used in both main memory and storage. In order to take advantage of this advantage of NVM, the operating system must also be designed based on NVM. However, since the traditional operating system is optimized to operate based on DRAM, many parts of the operating system have limitations that cannot achieve the maximum hardware performance of NVM. In particular, since NVM moves the persistence layer up from storage to memory, it is essential to ensure consistency based on the write order guarantee technique. In other words, journaling or logging, which is a technique for ensuring consistency between memory and storage in a traditional system, is also required between the CPU's Last Level Cache(LLC) and the NVM in the NVM system. This was done through expensive instructions such as clflush/mfence designed on DRAM basis.

In this paper, we focused on the consistency guarantee overhead, and studied the improvement in the areas where the consistency guarantee overhead is severe in the existing operating system. First, in the bootting area, because NVM can eliminate the reallocation and decompression overhead of the kernel, the boot process can be finished faster than traditional system. However, booting is the process of initializing of the kernel, so if an uninitialized object which NVM made exists in the kernel boot process, the process will not operate properly. In this regard, we studied the way to achieve high boot speed while ensuring consistency. We named this technique bootless boot, which eliminates the relocation and decompression overhead that occurs during the boot process of the kernel, while at the same time finding and initializing uninitialized objects to make the system run normally. Bootless Boot consists of (i) object filter which identifies the kernel objects which need to be initialized every time OS boots up, (ii) explicit initialization module which explicitly re-initializes the objects identified by the object filter. Explicit initialization module is added to the linux kernel. This technique reduced the boot speed by 343.7\% compared to the traditional kernel boot method.

Another challenge in NVM system is the persistence control problem. An object allocated in NVM can live permanently even when the power is turned off. If the persistent object becomes garbage, it causes fatal space overhead in the NVM system. To address this, we proposed the Two-Tier Garbage Collection(TTGC), a technique that can minimize the persistence control overhead in the garbage collection area. This method has a two-tier structure with different GC policies based on the mapping information of memory space, and proposes a new garbage searching algorithm for speeding up the GC. This technique was implemented in HEAPO, a persistent heap technique, and showed garbage collection performance 4 to 11 times faster than other garbage collection techniques.

Indexing is one of the fields where the non-volatile memory (NVM) has the advantages of byte-addressable characteristics and fast read/write speed. In particular, b+tree is useful for range queries, so it is a data structure used in multiple databases or file systems. However, the b+tree requires a lot of writes to maintain the ordering of nodes, and the expensive clflush/mfence operation is forced because they must guarantee their order. In this study, we propose a b+tree data structure that minimizes clfush/mfence based on cache line size atomic write in order to maximize the device performance of NVM. We named this technique as Cache line sized Atomic Write B+tree(CAWBT), which is a minimal b+tree structure that shows higher performance than a basic b+tree and designed for NVM. CAWBT has almost same performance compared to basic B+tree without consistency guarantee and shows remarkable performance improvement compared to other B+tree indexes for NVM.