Data structure storage and data management

Patent metadata

Field	Value
Publication number	US-11301177-B2
Application number	US-201916584124-A
Country	US
Kind code	B2
Filing date	Sep 26, 2019
Priority date	Mar 23, 2015
Publication date	Apr 12, 2022
Grant date	Apr 12, 2022

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 comprising:
determining an erasure coding group based upon reliability criteria;
selecting an erasure coding scheme for the erasure coding group based upon the erasure coding scheme satisfying a reliability level specified by the reliability criteria, wherein the erasure coding scheme indicates a number of memory chunks, having at least the reliability level, as the erasure coding group; and
performing erasure coding upon an object using the erasure coding scheme to create erasure coding objects distributed to the erasure coding group, wherein the performing comprises:
in response to determining that less than the number of memory chunks having at least the reliability level are available, redundantly storing multiple instance of an erasure coding object within memory chunks having less than the reliability level.

2. The method of claim 1 , wherein the determining the erasure coding group comprises:
selecting a group of storage devices as the erasure coding group based upon the group of storage devices satisfying the reliability level specified by the reliability criteria.

3. The method of claim 1 , wherein the determining the erasure coding group comprises:
selecting a group of memory chunks as the erasure coding group based upon the group of memory chunks satisfying the reliability level specified by the reliability criteria.

4. The method of claim 1 , comprising:
identifying parameters for the erasure coding scheme based upon a size of the erasure coding group.

5. The method of claim 1 , where the performing erasure coding comprises:
breaking the object into a set of fragments populated with portions of data of the object.

6. The method of claim 1 , where the performing erasure coding comprises:
storing fragments of the object with parity information across the erasure coding group.

7. The method of claim 1 , wherein a first fragment of the object and first parity information is stored within a first storage device of the erasure coding group and a second fragment of the object and second parity information is stored within a second storage device of the erasure coding group.

8. The method of claim 1 , comprising:
populating a metadata object with identities of storage devices of the erasure coding group that store fragments of encoded data of the object.

9. The method of claim 1 , wherein a first fragment of the object and first parity information is stored within a first memory chunk of the erasure coding group and a second fragment of the object and second parity information is stored within a second memory chunk of the erasure coding group.

10. The method of claim 1 , wherein the performing erasure coding comprises:
creating the erasure coding objects as data elements organized in a stack.

11. The method of claim 1 , wherein the performing erasure coding comprises:
creating the erasure coding objects as data elements organized in a queue.

12. The method of claim 1 , wherein the performing erasure coding comprises:
creating the erasure coding objects as data elements organized in a tree structure.

13. The method of claim 1 , comprising:
determining that the erasure coding scheme indicates a specified number of memory chunks having at least the reliability level as the erasure coding group.

14. The method of claim 1 , comprising:
in response to the erasure coding scheme requiring N number of memory chunks and that there are N−1 memory chunks available with at least the reliability level, writing the erasure coding object twice to two memory chunks with reliability less than the reliability level.

15. A non-transitory machine readable medium comprising instructions for performing a method, which when executed by a machine, causes the machine to:
select a set of memory chunks and an erasure coding scheme based upon the set of memory chunks and the erasure coding scheme satisfying a reliability level specified by a client device for an object, wherein the erasure coding scheme indicates a number of memory chunks, having at least the reliability level, as the erasure coding group;
perform erasure coding upon the object using the erasure coding scheme to create a set of fragments comprising data of the object; and
distribute the set of fragments and parity information across the set of memory chunk, comprising:
in response to determining that less than the number of memory chunks having at least the reliability level are available, redundantly storing multiple instance of a fragment within memory chunks having less than the reliability level.

16. The non-transitory machine readable medium of claim 15 , wherein the instructions cause the machine to:
compress a first set of data structures corresponding to fragments of the object based upon the first set of data structures being categorized as being accessed above a threshold frequency.

17. The non-transitory machine readable medium of claim 15 , wherein the instructions cause the machine to:
decompress a first set of data structures corresponding to fragments of the object based upon a change in access to the first set of data structures indicating the first set of data structures are accessed below a threshold frequency.

18. The non-transitory machine readable medium of claim 15 , wherein the instructions cause the machine to:
map data elements to nodes within a data structure, wherein a node represents a data element of the object and comprises redundant paths to other nodes of the data structure, and wherein a number of additional references are assigned to each node within the data structure based upon a level of fault tolerance to provide for the data elements.

19. The non-transitory machine readable medium of claim 15 , wherein the instructions cause the machine to:
identify and provide a notification of a fault based upon a new checksum, calculated from a request for data of the object, being different than a checksum stored for the data.

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:
identify a set of storage devices and an erasure coding scheme as satisfying a reliability level for an object, wherein the erasure coding scheme indicates a number of storage device, having at least the reliability level, as the erasure coding group;
perform erasure coding upon the object using the erasure coding scheme to create a set of fragments comprising data of the object; and
distribute the set of fragments across the set of storage devices, comprising:
in response to determining that less than the number of storage devices having at least the reliability level are available, redundantly storing multiple instance of a fragment within storage devices having less than the reliability level.

Assignees

• Netapp Inc

Inventors

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

Classifications

• G06F3/064

  Management of blocks · CPC title

• G06F11/1004

  to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00) · 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

• G06F11/10

  Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's · CPC title