Reduction of write amplification in object store

• US 10,133,764 B2
• Filed: 05/02/2016
• Issued: 11/20/2018
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Cheru, Tomy Ammuthan, O'Krafka, Brian W., Samuels, Allen, Krishnan, Manavalan
• Primary Examiner(s): Alam, Shahid
• Application Number:
  US15/144,704
• Publication Number:
  US 20170091243A1
• Time in Patent Office: 932 Days
• Field of Search: 707744
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method of managing a storage system having one or more storage devices includes receiving a request to access, in a tiered data structure, a data object and one or more attributes of the data object and processing the access request. The request includes a first key value for the data object and respective second key values for the one or more attributes of the data object. Modified key values for the attributes of the data object are generated in accordance with at least a portion of the first key value and used to access tree entries for the data object attributes in one or more leaf nodes of the tiered data structure. A tree entry for the data object is also accessed from the same set of one or more leaf nodes.

Claims

1. A method of managing a storage system having one or more storage devices, the method comprising:

receiving a request to access, in a tiered data structure stored at least in part in the one or more storage devices of the storage system, a data object and one or more attributes of the data object, wherein the tiered data structure is stored in the storage system, the request including a first key value corresponding to the data object and one or more second key values corresponding to the one or more attributes of the data object; and

processing the access request, including;

generating one or more modified key values for the one or more attributes of the data object in accordance with at least a portion of the first key value, each modified key value differing from but corresponding to a respective second key value of the one or more second key values in the received request;

accessing a plurality of tree entries in one or more leaf nodes of the tiered data structure, the plurality of tree entries comprising a data object entry that includes the first key value and a reference to the data object and further comprising one or more attribute entries corresponding to the data object, each attribute entry including a respective attribute of the one or more attributes of the data object and the modified key value corresponding to the respective attribute; and

accessing the data object in a data node of the tiered data structure;

including, after generating the one or more modified key values, accessing, in the one or more storage devices of the storage system, a respective attribute of the data object, requested by the received request, in an attribute entry having the modified key value corresponding to the respective attribute.

2. The method of claim 1, wherein generating the one or more modified key values for the one or more attributes of the data object comprises prepending at least a portion of the first key value to each of the one or more second key values.

3. The method of claim 1, wherein, in accordance with the first key value and the one or more modified key values, the data object entry and one or more attribute entries comprise a contiguous set of tree entries in a single leaf node of the tiered data structure.

4. The method of claim 3, wherein:

said accessing comprises only two I/O operations, including a first I/O operation to access the single leaf node from non-volatile memory of the storage system and a second I/O operation to access the data node from said non-volatile memory of the storage system.

5. The method of claim 1, wherein the request to access comprises a read command to read, from the tiered data structure, the data object and the one or more attributes of the data object.

6. The method of claim 5, wherein:

the data object, as stored in the storage system, comprises encoded data; and

the method includes decoding the data object, reading from the tiered data structure, and providing the decoded data object to a requester.

7. The method of claim 1, wherein the request to access comprises a write command to write, to the tiered data structure, the data object and the one or more attributes of the data object.

8. The method of claim 7, wherein said accessing operations comprises two I/O operations, including a first I/O operation to write, to a non-volatile memory of the storage system, a single leaf node that includes the data object entry and the one or more attribute entries, and a second I/O operation to write, to the non-volatile memory of the storage system, the data node.

9. The method of claim 1, wherein the tiered data structure comprises a tree of nodes, including non-leaf nodes, leaf nodes, and data nodes, wherein at least the leaf nodes and data nodes are stored in non-volatile flash memory of the storage system.

10. The method of claim 9, wherein at least the generating of the one or more modified key values is performed by a host system separate from the storage system, and at least the non-leaf nodes are stored in volatile memory of the host system.

11. A host system, the system comprising:

an interface for operatively coupling to a storage system having one or more storage devices;

one or more hardware processors; and

memory storing one or more programs, which when executed by the one or more processors, cause the host system to perform operations comprising;

receiving a request to access, in a tiered data structure that is stored in the storage system, a data object and one or more attributes of the data object, the request including a first key value corresponding to the data object and one or more second key values corresponding to the one or more attributes of the data object;

generating one or more modified key values for the one or more attributes of the data object in accordance with at least a portion of the first key value, each modified key value differing from but corresponding to a respective second key value of the one or more second key values in the received request; and

accessing, in the tiered data structure, a data node storing the data object and a plurality of tree entries in one or more leaf nodes, the plurality of tree entries comprising a data object entry that includes the first key value and a reference to the data object, and further comprising one or more attribute entries corresponding to the data object, each attribute entry including a respective attribute of the one or more attributes of the data object and the modified key value corresponding to the respective attribute;

including, after generating the one or more modified key values, accessing, in the one or more storage devices of the storage system, a respective attribute of the data object, requested by the received request, in an attribute entry having the modified key value corresponding to the respective attribute.

12. The host system of claim 11, wherein the one or more programs includes a tiered data access module that generates the one or more modified key values for the one or more attributed of the data object.

13. The host system of claim 12, wherein the tiered data access module includes instructions for accessing, in the tiered data structure, the data node storing the data object.

14. The host system of claim 11, wherein generating the one or more modified key values for the one or more attributes of the data object comprises prepending at least a portion of the first key value to each of the one or more second key values.

15. The host system of claim 11, wherein, in accordance with the first key value and the one or more modified key values, the data object entry and one or more attribute entries comprise a contiguous set of tree entries in a single leaf node of the tiered data structure.

16. A storage system, the system comprising:

an interface for operatively coupling to a host system;

one or more processors; and

controller memory storing one or more programs, which when executed by the one or more processors, cause the storage system to perform operations comprising;

receiving a request from the host system to access, in a tiered data structure that is stored in the storage system, a data object and one or more attributes of the data object, the request including a first key value corresponding to the data object and one or more respective second key values corresponding to each of the one or more attributes of the data object;

generating one or more modified key values for the one or more attributes of the data object in accordance with at least a portion of the first key value, each modified key value differing from but corresponding to a respective second key value of the one or more second key values in the received request; and

accessing, in the tiered data structure, a data node storing the data object and a plurality of tree entries in one or more leaf nodes, the plurality of tree entries comprising a data object entry that includes the first key value and a reference to the data object, and further comprising one or more attribute entries, each attribute entry including a respective attribute of the one or more attributes of the data object and the modified key value corresponding to the respective attribute;

including, after generating the one or more modified key values, accessing, in the tiered data structure, a respective attribute of the data object, requested by the received request, in an attribute entry having the modified key value corresponding to the respective attribute.

17. The storage system of claim 16, wherein the one or more programs includes a tiered data access module that generates the one or more modified key values for the one or more attributes of the data object.

18. The storage system of claim 17, wherein the tiered data access module includes instructions for accessing, in the tiered data structure, the data node storing the data object.

19. The storage system of claim 16, wherein generating the one or more modified key values for the one or more attributes of the data object comprises prepending at least a portion of the first key value to each of the one or more second key values.

20. The storage system of claim 16, wherein, in accordance with the first key value and the one or more modified key values, the data object entry and one or more attribute entries comprise a contiguous set of tree entries in a single leaf node in the tiered data structure.