Construction method and operation method of DRAM-NVM hybrid index structure

A technology of DRAM-NVM and index structure, which is applied in the field of information storage, can solve problems such as fault recovery that cannot take into account high read and write performance, and achieve the effect of speeding up the process of fault recovery, reducing blocking, and ensuring read and write performance

Pending Publication Date: 2021-11-02
HUAZHONG UNIV OF SCI & TECH +1
View PDF0 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] Aiming at the above defects or improvement needs of the prior art, the present invention provides a construction method and operation method of a DRAM-NVM hybrid index structure to solve the technical problem that the prior art cannot take into account high read / write performance and fast fault recovery

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Construction method and operation method of DRAM-NVM hybrid index structure
  • Construction method and operation method of DRAM-NVM hybrid index structure
  • Construction method and operation method of DRAM-NVM hybrid index structure

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0060] A method for constructing a DRAM-NVM hybrid index structure, comprising: constructing an index layer, an intermediate layer and a data layer to obtain a DRAM-NVM hybrid index structure; specifically, as figure 1 As shown, wherein, the index layer is a tree structure, preferably a B+ tree, stored in DRAM; the middle layer includes one or more metadata nodes, stored in DRAM, and there is a backup in NVM; and when the metadata When there are multiple nodes, each metadata node is connected back and forth to form a linked list structure, preferably a two-way linked list structure; the data layer includes a log persistence tree LogTree; LogTree is a tree structure, preferably a B+ tree, and its number is the same as that of the metadata node. The number is the same, corresponding to metadata nodes one by one; in the initial state, LogTree is stored in NVM, which is recorded as NvmTree; in the process of reading and writing, if the access heat of LogTree is greater than the pre...

Embodiment 2

[0068] The reading and writing request processing method of the index structure constructed by the construction method of the DRAM-NVM hybrid index structure described in Embodiment 1, taking the insertion request and the query request as an example, such as Figure 6 shown, including:

[0069] When an insert request is received, perform the insert operation:

[0070] S11. Query the index layer based on the target keyword key in the request, obtain the metadata node pointer corresponding to the target keyword key, determine the metadata node in the middle layer, and accumulate the access heat of the LogTree corresponding to the metadata node; in NVM Allocate a persistent space for the value in the request, and persist it, and get a pointer to the value;

[0071] S12. Determine whether the CacheTree in the LogTree corresponding to the metadata node is under the creation or synchronization operation of the CacheTree, if so, go to step S13; otherwise, go to step S14;

[0072] S...

Embodiment 3

[0100] When the system is powered off or fails, the data on the DRAM will be lost, and the structure on the NVM may also appear in an inconsistent state. Therefore, when the system where the index structure is located is powered off or fails, fault recovery is required to ensure normal and Serve. Specifically, the power-down or fault recovery method of the index structure constructed by the construction method of the DRAM-NVM hybrid index structure described in Embodiment 1 includes the following steps:

[0101] 1), the restoration of the middle layer: when restoring, first traverse the metadata nodes backed up in the middle layer of NVM, and judge whether there is data overlap in the NvmTree root node of the LogTree corresponding to the adjacent metadata nodes, if there is data overlap, Split the NvmTree root node with overlapping data, and correct the problem that the precursor pointer of the corresponding metadata node points to the wrong node, so as to ensure that the midd...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention discloses a construction method and an operation method of a DRAM-NVM hybrid index structure. The constructed index structure comprises an index layer, a middle layer and a data layer; the index layer is stored in the DRAM; the middle layer comprises metadata nodes which are stored in the DRAM, and backup exists in the NVM; the data layer comprises LogTree, the LogTree is of a tree structure, the number of the LogTree is the same as that of the metadata nodes, and the LogTree is in one-to-one correspondence with the metadata nodes; in an initial state, the LogTree is stored in an NVM (Non-Volatile Memory) and is recorded as NvmTree; in the read-write process, backing up the LogTree with the access heat greater than a preset access heat threshold and caching the LogTree in a DRAM to create a Cache Tree; at the moment, the LogTree comprises an NvmTree initially stored in an NVM, a Cache Tree cached in a DRAM and a log stored in the NVM; the log is used for storing a record for carrying out write operation on the Cache; and a LogTree in the data layer is used for storing a target keyword key in a key value pair written by a user and a pointer pointing to a value. The fault recovery process can be greatly accelerated on the premise of ensuring the read-write performance.

Description

technical field [0001] The invention belongs to the technical field of information storage, and more specifically relates to a construction method and an operation method of a DRAM-NVM hybrid index structure. Background technique [0002] In the past ten years, with the continuous development of computer and network technology, the scale of information data has exploded. Various storage devices in the current computer system have great differences in performance, capacity, persistence, etc., which have brought a huge impact on the way data is stored. Index structure is the core component of modern databases. Changes in storage architecture and characteristics of persistent memory bring opportunities and challenges to optimize index structure, so it is of great significance to study an index structure. [0003] The new type of non-volatile memory (Non-Volatile Memory, NVM) has become the next generation due to its byte-addressable, non-volatile, low power consumption, high s...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(China)
IPC IPC(8): G06F16/22G06F16/242G06F11/14
CPCG06F16/2246G06F16/242G06F11/1458
Inventor 万继光谢长生盛涛涛周元辉陶伟
Owner HUAZHONG UNIV OF SCI & TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap