Methods and Systems for Performing Efficient Snapshots in Tiered Data Structures

• US 20150286695A1
• Filed: 08/07/2014
• Published: 10/08/2015
• Est. Priority Date: 04/03/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Kadayam, Harihara, Krishnan, Manavalan, O'Krafka, Brian Walter, George, Johann, Neelakanta, Niranjan Patre, Tapse, Ajit Kumar
• Granted Patent: US 9,697,267 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A memory controller detects a request, with a key to a data object and a value, to perform an operation. The memory controller locates the data object by mapping the key to a location of the data object in a tiered data structure and identifies a sequence number of the data object. When the sequence number of the data object is greater than a sequence number of a snapshot of the tiered data structure, the memory controller replaces the data object with a modified data object, including the key and the value, and assigns the modified object a unique sequence number. When the sequence number of the data object is less than the sequence number of the snapshot, the memory controller inserts a new data object, including the key and the value, into the tiered data structure and assigns the new data object the unique sequence number.

Claims

1. A method of managing a datastore storing one or more tiered data structures, comprising:

at a memory controller with one or more processors, wherein the memory controller is operatively coupled with the datastore;

detecting a request to perform an update operation of a first data object in a tiered data structure of the one or more tiered data structures stored in the datastore, the request includes first key information corresponding to the first data object and a new value for the first data object;

locating the first data object using a key-map to map the first key information to a location of the first data object in the datastore;

identifying a sequence number associated with the first data object;

in accordance with a first determination that the sequence number associated with the first data object is greater than a first boundary sequence number corresponding to a first snapshot of the tiered data structure;

replacing the first data object in the tiered data structure with a modified first data object including the first key information and the new value; and

assigning the modified first object a unique sequence number; and

in accordance with a second determination that the sequence number associated with the first data object is less than or equal to the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

while maintaining the first data object in the tiered data structure, inserting a second data object into the tiered data structure, the second data object including the first key information and the new value; and

assigning the second data object the unique sequence number.

2. The method of claim 1, wherein the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes, a respective leaf node of the plurality of leaf nodes stores one or more data objects;

and

wherein each of the one or more data objects includes key information and a corresponding value and each of the one or more data objects is associated with a unique sequence number.

3. The method of claim 2, wherein, in accordance with the first determination, the modified first object is stored in the respective leaf node of the tiered data structure in a first manner corresponding to a sorting scheme associated with the key information;

and

wherein, in accordance with the second determination, the second data object is stored in the respective leaf node in a second manner that is substantially opposite to the first manner.

4. The method of claim 1, wherein the first boundary sequence number corresponds to a highest sequence number assigned to a data object in the tiered data structure prior to the first snapshot.

5. The method of claim 4, wherein snapshot metadata, including the first boundary sequence number, corresponding to one or more snapshots of the tiered data structure, including the first snapshot, is stored in a respective leaf node of the tiered data structure.

6. The method of claim 1, further comprising:

detecting a second request to perform a deletion operation of a third data object in the tiered data structure, the second request includes second key information corresponding to the third data object;

locating the third data object using the key-map to map the second key information to a location of the third data object in the datastore;

identifying a sequence number associated with the third data object;

in accordance with a determination that the sequence number associated with the third data object is greater than the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

replacing the third data object in the tiered data structure with a modified third data object including the second key information and a tombstone; and

assigning the modified third object a second unique sequence number; and

in accordance with a determination that the sequence number associated with the third data object is less than or equal to the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

while maintaining the third data object in the tiered data structure, inserting a fourth data object into the tiered data structure, the fourth data object including the second key information and the tombstone; and

assigning the fourth data object the second unique sequence number.

7. The method of claim 1, further comprising:

after assigning the modified first object or the second data object the unique sequence number, performing a second snapshot of the tiered data structure, wherein the snapshot is associated with a second boundary sequence number different from the first boundary sequence number.

8. The method of claim 7, further comprising:

determining whether one or more requests to perform memory operations on the tiered data structure are complete, wherein the one or more requests include the request to perform the update operation; and

wherein performing the second snapshot comprises performing the second snapshot of the tiered data structure in accordance with a determination that the one or more requests are complete.

9. The method of claim 1, further comprising:

detecting a trigger to perform a cleanup process as to one or more snapshots;

in response to detecting the trigger, performing the cleanup process as to the one or more snapshots, including;

identifying one or more sets of redundant data objects in the tiered data structure that each include two or more data objects that are associated with same key information;

for a respective set of the one or more sets of redundant data objects;

identifying a respective data object associated with a highest sequence number compared to one or more other data objects in the respective set of redundant data objects; and

removing the one or more other data objects, distinct from the respective data object, in the respective set of redundant data objects from the tiered data structure.

10. The method of claim 9, wherein performing the cleanup process as to the one or more snapshots further includes:

deleting information corresponding to the one or more snapshots from snapshot metadata;

wherein the snapshot metadata corresponding to the one or more snapshots of the tiered data structure is stored in a respective leaf node of the tiered data structure.

11. The method of claim 9, wherein the trigger identifies the one or more snapshots on which to perform the cleanup process.

12. The method of claim 1, wherein the datastore includes one or more three-dimensional (3D) memory devices and circuitry associated with operation of memory elements in the one or more 3D memory devices.

13. The method of claim 12, wherein the circuitry and one or more memory elements in a respective 3D memory device, of the one or more 3D memory devices, are on the same substrate.

14. A data storage system, comprising:

a datastore storing one or more tiered data structures; and

a memory controller with one or more processors, memory, and one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

detecting a request to perform an update operation of a first data object in a tiered data structure of the one or more tiered data structures stored in the datastore, the request includes first key information corresponding to the first data object and a new value for the first data object;

locating the first data object using a key-map to map the first key information to a location of the first data object in the datastore;

identifying a sequence number associated with the first data object;

in accordance with a first determination that the sequence number associated with the first data object is greater than a first boundary sequence number corresponding to a first snapshot of the tiered data structure;

replacing the first data object in the tiered data structure with a modified first data object including the first key information and the new value; and

assigning the modified first object a unique sequence number; and

in accordance with a second determination that the sequence number associated with the first data object is less than or equal to the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

while maintaining the first data object in the tiered data structure, inserting a second data object into the tiered data structure, the second data object including the first key information and the new value; and

assigning the second data object the unique sequence number.

15. The data storage system of claim 14, wherein the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes, a respective leaf node of the plurality of leaf nodes stores one or more data objects;

and

wherein each of the one or more data objects includes key information and a corresponding value and each of the one or more data objects is associated with a unique sequence number.

16. The data storage system of claim 14, wherein the one or more programs, when executed by the one or more processors, cause the data storage system to:

store modified first object, in accordance with the first determination, in the respective leaf node of the tiered data structure in a first manner corresponding to a sorting scheme associated with the key information; and

store the second data object, in accordance with the second determination, in the respective leaf node in a second manner that is substantially opposite to the first manner.

17. The data storage system of claim 14, wherein the first boundary sequence number corresponds to a highest sequence number assigned to a data object in the tiered data structure prior to the first snapshot.

18. The data storage system of claim 14, wherein snapshot metadata, including the first boundary sequence number, corresponding to one or more snapshots of the tiered data structure, including the first snapshot, is stored in a respective leaf node of the tiered data structure.

19. The data storage system of claim 14, wherein the one or more programs, when executed by the one or more processors, cause the data storage system to:

detect a second request to perform a deletion operation of a third data object in the tiered data structure, the second request includes second key information corresponding to the third data object;

locate the third data object using the key-map to map the second key information to a location of the third data object in the datastore;

identify a sequence number associated with the third data object;

in accordance with a determination that the sequence number associated with the third data object is greater than the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

replace the third data object in the tiered data structure with a modified third data object including the second key information and a tombstone; and

assign the modified third object a second unique sequence number; and

in accordance with a determination that the sequence number associated with the third data object is less than or equal to the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

while maintaining the third data object in the tiered data structure, insert a fourth data object into the tiered data structure, the fourth data object including the second key information and the tombstone; and

assign the fourth data object the second unique sequence number.

20. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a memory controller with one or more processors, cause the memory controller to:

detect a request to perform an update operation of a first data object in a tiered data structure of one or more tiered data structures stored in a datastore, the request includes first key information corresponding to the first data object and a new value for the first data object;

locate the first data object using a key-map to map the first key information to a location of the first data object in the datastore;

identify a sequence number associated with the first data object;

in accordance with a first determination that the sequence number associated with the first data object is greater than a first boundary sequence number corresponding to a first snapshot of the tiered data structure;

replace the first data object in the tiered data structure with a modified first data object including the first key information and the new value; and

assign the modified first object a unique sequence number; and

in accordance with a second determination that the sequence number associated with the first data object is less than or equal to the first boundary sequence number corresponding to the first snapshot of the tiered data structure;

while maintaining the first data object in the tiered data structure, insert a second data object into the tiered data structure, the second data object including the first key information and the new value; and

assign the second data object the unique sequence number.