Data storage method, electronic device, and computer non-volatile storage medium

• US 10,642,515 B2
• Filed: 07/02/2018
• Issued: 05/05/2020
• Est. Priority Date: 10/08/2016
• Status: Active Grant

• Current Assignee: Tencent Technology Company Limited (Tencent Holdings Limited)
• Original Assignee: Tencent Technology Company Limited (Tencent Holdings Limited)
• Inventors: Xiao, Tao
• Primary Examiner(s): Rossiter, Sean D
• Assistant Examiner(s): Wu, Stephanie
• Application Number:
  US16/025,562
• Publication Number:
  US 20180307428A1
• Time in Patent Office: 673 Days
• Field of Search: None
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A data storage system may obtain data, a size of the data, and a data structure type of the data. The system may allocate a memory block for the data based on the size of the data and a predetermined block size. The system may store the data in the allocated memory block. The allocated memory block may include a block attribute that includes the data and a head comprising management information corresponding to the block attribute. The management information may include a first block identifier for an antecedent memory block and a second block identifier for a succeeding memory block. The system may link, based on the data structure type, the allocated memory block to a plurality of memory blocks arranged in at least one of a block list structure or a tree structure.

Claims

1. A data storage method for a key-value storage system, comprising:

obtaining data, a size of the data, and a data structure type of the data;

allocating a memory block for the data based on the size of the data and a predetermined block size;

storing the data in the allocated memory block, the allocated memory block comprising a block attribute that includes the data and a head comprising management information corresponding to the block attribute, and the management information comprising a first block identifier for an antecedent memory block and a second block identifier for a succeeding memory block; and

linking, based on the data structure type, the allocated memory block to a plurality of memory blocks arranged in a block list structure in response to the data structure type being at least one of a list type or a string type.

2. The method of claim 1, further comprising:

linking the allocated memory block to a tree-shaped structure in response to the data structure type being at least one of a hash value type, a string set type, or a sorted string set type.

3. The method of claim 1, wherein the data structure type comprises at least one of a list type, a hash type, a hash value type, a string set type, or a sorted string set type, the method further comprising:

obtaining a size of a string of an element of the data;

comparing the size of the string of the element with a size of a remaining space of the memory block;

in response to the size of the string of the element being smaller than or equal to the size of the remaining space of the memory block, storing the string of the element in the memory block;

in response to the size of the string of the element being greater than the size of the remaining space of the memory block;

obtaining a size of an index of the string of the element, and

determining whether the size of the index of the string of the element is smaller than or equal to the size of the remaining space of the memory block; and

in response to the size of the index of the string of the element being smaller than or equal to the size of the remaining space of the memory block;

storing the index of the string of the element in the memory block, and

storing the string of the element in an external block list corresponding to the index.

4. The method of claim 3, wherein storing the string of the element in an external block list corresponding to the index further comprises:

determining whether the size of the string of the element is smaller than or equal to a size of an external memory block;

in response to the size of the string of the element being less than or equal to the size of the external memory block, storing the string of the element in the external memory block as the external block list;

in response to the size of the string of the element being greater than the size of the external memory block, splitting the string of the element into multiple sections according to the size of the external memory block;

configuring a corresponding quantity of external memory blocks;

associating the corresponding quantity of external memory blocks to form the external block list; and

storing the string of the element in the external block list.

5. The method of claim 1, further comprising:

obtaining an element included in the data, a first target block from the plurality of memory blocks, and an insertion position in the first target block;

determining a size of the element is larger than a size of a remaining space of the first target block; and

in response to the size of the element being larger than the size of the remaining space of the first target block;

storing a portion of the element starting at the insertion position in the first target block,

configuring a new memory block of a fixed size, and

storing a remainder of the element in the new memory block.

6. The method of claim 1, further comprising:

obtaining an element deletion instruction that comprises a specified element and a target block where the specified element is located;

deleting the specified element from the target block according to the element deletion instruction;

determining a size of a string of an element in a succeeding memory block of the target block is smaller than or equal to a size of a remaining space of the target block; and

in response to the size of the string of the element in the succeeding memory block of the target block being less than or equal to the size of the remaining space of the target block, combining the string of the element in the succeeding memory block of the target block into the target block.

7. The method of claim 1, further comprising:

obtaining a hash value of a key in each memory block in response to the data structure type being at least one of a hash value type, a string set type, or a sorted string set type;

dividing the key into multiple parts according to a hash value of the key;

storing the multiple parts of the key in an independent balanced tree;

obtaining a query instruction corresponding to the key; and

searching for the key from the independent balanced tree according to the query instruction.

8. The method of claim 1, wherein linking, based on the data structure type, the allocated memory block to the plurality of memory blocks arranged in the block list structure further comprises:

obtaining a block identifier of the allocated memory block;

recording the block identifier of the memory block in a head of a previous memory block; and

recording an identifier of the previous memory block in a head of the allocated memory block.

9. The method of claim 1, further comprising:

obtaining a data access request; and

locating a corresponding memory block in the plurality of memory blocks according to the data access request and traversing the corresponding memory block to obtain data based on the data access request.

10. A data storage system, comprising a processor, the processor configured to:

obtain data, a size of the data, and a data structure type of the data;

allocate a memory block for the data based on the size of the data and a predetermined block size;

store the data in the allocated memory block, the allocated memory block comprising a block attribute that includes the data and a head comprising management information corresponding to the block attribute, and the management information comprising a first block identifier for an antecedent memory block and a second block identifier for a succeeding memory block; and

link, based on the data structure type, the allocated memory block to a plurality of memory blocks arranged in a block list structure, wherein to link the allocated memory block to the block list structure, the processor is further configured to;

associate the allocated memory block with the block list structure in response to the data structure type being at least one of a list type or a string type.

11. The data storage system of claim 10, wherein the processor is further configured to:

associate the allocated memory block with a tree structure in response to the data structure type being at least one of a hash value type, a string set type, or a sorted string set type.

12. The data storage system of claim 10, wherein the data structure type comprises at least one of a list type, a hash type, a hash value type, a string set type, or a sorted string set, the processor further configured to:

obtain a size of a string of an element of the data;

compare the size of the string of the element with a size of a remaining space of the memory block;

in response to the size of the string of the element being smaller than or equal to the size of the remaining space of the memory block, store the string of the element in the memory block;

in response to the size of the string of the element being greater than the size of the remaining space of the memory block;

obtain a size of an index of the string of the element, and

determine the size of an index of the string of the element is smaller than or equal to the size of the remaining space of the memory block; and

in response to the size of the index of the string of the element being smaller than or equal to the size of the remaining space of the memory block;

store the index of the string of the element in the memory block, and

store the string of the element in an external memory block list corresponding to the index.

13. The data storage system of claim 12, wherein to store the string of the element in an external block list corresponding to the index, the processor is further configured to:

determine whether the size of the string of the element is smaller than or equal to a size of an external memory block;

in response to the size of the string of the element being less than or equal to the size of the external memory block, storing the string of the element in the external memory block;

in response to the size of the string of the element being greater than the size of the external memory block, splitting the string of the element into multiple sections according to the size of the external memory block;

configure a corresponding quantity of external memory blocks;

associate the corresponding quantity of external memory blocks to form the external block list; and

store the string of the element in the external block list.

14. The data storage system of claim 10, wherein the processor is further configured to:

obtain an element included in the data, a first target block from the plurality of memory blocks, and an insertion position in the first target block;

determine a size of the element is larger than a size of a remaining space of the first target block; and

in response to the size of the element being larger than the size of the remaining space of the first target block;

store a portion of the element starting at the insertion position in the first target block,

configure a new memory block of a fixed size, and

store a remainder of the element in the new memory block.

15. The data storage system of claim 10, wherein the processor is further configured to:

obtain an element deletion instruction that comprises a specified element and a target block where the specified element is located;

delete the specified element from the target block according to the element deletion instruction;

determine a size of a string of an element in a succeeding memory block of the target block is smaller than or equal to a size of a remaining space of the target block; and

in response to the size of the string of the element in the succeeding memory block of the target block being less than or equal to the size of the remaining space of the target block, combine the string of the element in the succeeding memory block of the target block into the target block.

16. The data storage system of claim 10, wherein the processor is further configured to:

obtain a hash value of a key in each block in response to the data structure type being at least one of a hash value type, a string set type, or a sorted string set type;

divide the key into multiple parts according to a hash value of the key;

store the multiple parts of the key in an independent balanced tree;

obtain a query instruction corresponding to the key; and

search for the key from the independent balanced tree according to the query instruction.

17. The data storage system of claim 10, wherein to link, based on the data structure type, the allocated memory block to the plurality of memory blocks arranged in the block list structure, the processor is further configured to:

obtain a block identifier of the allocated memory block;

record the block identifier of the memory block in a head of a previous memory block; and

record an identifier of the previous memory block in a head of the allocated memory block.

18. The data storage system of claim 10, wherein the processor is further configured to:

obtain a data access request; and

locate a corresponding memory block in the plurality of memory blocks according to the data access request and traversing the corresponding memory block to obtain data based on the data access request.