Data structure storage and data management

Patent metadata

Field	Value
Publication number	US-11954373-B2
Application number	US-202217717487-A
Country	US
Kind code	B2
Filing date	Apr 11, 2022
Priority date	Mar 23, 2015
Publication date	Apr 9, 2024
Grant date	Apr 9, 2024

Abstract

The instant disclosure provides a data structure store system and a method of managing data in the store. The method includes receiving, by a data structure store management system, a request for storing data from a client. In the created data structure, each data element includes a portion of the data. On receiving a read request for at least part of the data, the data structure store management system provides at least part of the data to a recipient device. The data elements are stored in persistent memory in the form of one or more non-volatile random access devices, wherein during a time interval between receiving the storing request and providing the at least part of the data by the data structure store management system to the recipient device, the data structure store management system provides no portion of the data for writing to a hard disk drive.

First claim

What is claimed:

1. A method, executed by a processor utilizing instructions stored within memory, comprising:
scan, by a data structure store management system, data structures to identify access rates of clients accessing the data structures, wherein a data structure is classified as a cold data structure based upon an access rate of the data structure being below a first threshold or is classified as a hot data structure based upon the access rate of the data structure exceeding a second threshold;
in response to determining that operations to a first data structure will be read-mostly, convert data within the first data structure into a succinct version of the first data structure, wherein the first data structure is classified as a first cold data structure;
compress data of a set of data structures identified as cold data structures to create compressed data; and
provide the clients with access to the compressed data of the cold data structures and access to uncompressed data of the hot data structures.

2. The method of claim 1 , comprising:
selecting a compression algorithm for compressing the data based upon a type of the data stored in the cold data structures, wherein an encoding scheme is selected as the compression algorithm based upon the cold data structures storing a linked list including elements of a string data type.

3. The method of claim 1 , comprising:
in response to the cold data structure comprising a linked list of elements having a string data type, selecting a compression algorithm for compressing the cold data structure based upon the compression algorithm being tailored for compressing data having the string data type.

4. The method of claim 1 , comprising:
monitoring access to the cold data structure whose data is compressed as the compressed data to determine a current access rate to the cold data structure; and
in response to the current access rate indicating an access rate change exceeding the second threshold:
decompressing the compressed data to create uncompressed data;
modifying a classification of the data structure from being the cold data structure to being the hot data structure; and
providing the clients with access to the uncompressed data of the hot data structure.

5. The method of claim 1 , comprising:
selecting a compression algorithm based upon a cold data structure comprising a tree data structure associated with a fanout type of metadata.

6. The method of claim 1 , comprising:
classifying the data structure as either being the cold data structure or the hot data structure based upon at least one of a type or a size of data stored within the data structure.

7. The method of claim 1 , comprising:
classifying a first portion of the data structure as being the cold data structure and a second portion of the data structure as being the hot data structure.

8. The method of claim 1 , wherein the data structure comprises a stack data structure, and the method comprising:
classifying a top set of elements of the stack data structure as being the hot data structure and remaining elements of the stack data structure as being the cold data structure.

9. The method of claim 1 , comprising:
classifying the data structure as being a warm data structure based upon the access rate of the data structure being between the first threshold and the second threshold.

10. The method of claim 1 , wherein the data structure is a sub-tree of a binary tree, and wherein the method comprises:
converting data of the sub-tree into a succinct binary tree.

11. The method of claim 1 , comprising:
utilizing non-volatile memory to enable an application to request persistence of the data structure during computation, wherein byte addressable access is provided to the data structure.

12. The method of claim 1 , comprising:
performing deduplication upon the data structures utilizing a chunk size and boundaries that are aware of hidden patterns.

13. The method of claim 1 , comprising:
in response to determining that the data structure is a binary tree with a low access count below the first threshold and is marked as ready only, convert the binary tree into a succinct binary tree.

14. The method of claim 1 , comprising:
in response to determining that the data structure is a sub-tree of a binary tree with a low access count below the first threshold and is marked as ready only, convert the binary tree into a succinct binary tree.

15. The method of claim 1 , comprising:
implementing a metadata API to support querying, setting, and resetting metadata attributes for the data structures.

16. A non-transitory machine readable medium comprising instructions for performing a method, which when executed by a machine, causes the machine to:
scan, by a data structure store management system, data structures to identify access rates of clients accessing the data structures, wherein a data structure is classified as a cold data structure based upon an access rate of the data structure being below a first threshold or is classified as a hot data structure based upon the access rate of the data structure exceeding a second threshold;
in response to determining that a majority of operations to a first data structure will be read-mostly, convert data within the first data structure into a succinct version of the first data structure, wherein the first data structure is classified as a first cold data structure;
compress data of a set of data structures identified as cold data structures to create compressed data; and
provide the clients with access to the compressed data of the cold data structures and access to uncompressed data of the hot data structures.

17. The non-transitory machine readable medium of claim 16 , wherein the instructions cause the machine to:
select a compression algorithm for compressing the data based upon a type of the data stored in the cold data structures.

18. The non-transitory machine readable medium of claim 16 , wherein the instructions cause the machine to:
in response to the cold data structure comprising a linked list of elements having a string data type, select a compression algorithm for compressing the cold data structure based upon the compression algorithm being tailored for compressing data having the string data type.

19. The non-transitory machine readable medium of claim 16 , wherein the instructions cause the machine to:
monitor access to the cold data structure whose data was compressed as the compressed data to determine a current access rate to the cold data structure; and
in response to the current access rate indicating an access rate change exceeding the second threshold:
decompress the compressed data to create uncompressed data;
modify a classification of the data structure from being the cold data structure to being the hot data structure; and
provide the clients with access to the uncompressed data of the hot data structure.

20. A computing device comprising:
a memory comprising machine executable code; and
a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
scan, by a data structure store management system, data structures to identify access rates of clients accessing the data structures, wherein a data structure is classified as a cold data structure based upon an access rate of the data structure being below a first threshold or is classified as a hot data structure based upon the access rate of the data structure exceeding a second t

Assignees

• Netapp Inc

Inventors

• Sivananainthaperumal Anusha
• Yasa Giridhar Appaji Nag
• Bakre Ajay Vijay

Classifications

• G06F3/0685 Primary

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title