Memory-efficient object address mapping in a tiered data structure

• US 10,747,676 B2
• Filed: 07/12/2016
• Issued: 08/18/2020
• Est. Priority Date: 02/23/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: O'Krafka, Brian W., Tudor, Frederic H., Neelakanta, Niranjan Patre, Krishnan, Manavalan, George, Johann, Firsov, Evgeniy
• Primary Examiner(s): Lane, John A
• Application Number:
  US15/208,531
• Publication Number:
  US 20170242799A1
• Time in Patent Office: 1,498 Days
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/22 Employing cache memory using specific memory technology
• CPC Class Codes: G06F 2212/65 Details of virtual memory and virtual address translation

Abstract

Systems, methods and/or devices are used to perform memory-efficient mapping of block/object addresses. In one aspect, a method of managing a storage system having one or more storage devices includes a tiered data structure in which each node has a logical ID and entries in the nodes reference other nodes in the tiered data structure using the logical IDs. As a result, when a child node is updated and stored to a new location, but retains its logical ID, its parent node does not need to be updated, because the logical ID in the entry referencing the child node remains unchanged. Further, the storage system uses a secondary mapping table to translate the logical IDs to the corresponding physical locations of the corresponding nodes. Additionally, the secondary mapping table is cached in volatile memory, and as a result, the physical location of a required node is determined without accessing non-volatile memory.

Claims

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

detecting a first request to perform a read operation of a first data object stored in a storage device of the storage system, the first request including first key information corresponding to the first data object;

locating a first entry for the first key information in a tiered data structure, the first entry including a first logical ID for a first leaf node corresponding to the first key information;

determining a first physical location of the first leaf node based on the first logical ID for the first leaf node using a secondary mapping table, the secondary mapping table being used to translate logical IDs for leaf nodes to physical locations of leaf nodes;

reading the first leaf node using the first physical location to obtain a leaf node map entry, the leaf node map entry including size of the first data object and a second physical location of the first data object;

reading from the second physical location to obtain the first data object;

receiving a second request to perform a write operation for a second data object to the storage device, the second request including second data to be written for the second data object and second key information corresponding to the second data object; and

in accordance with a determination that a second entry for the second key information is in a second leaf node of the tiered data structure;

accessing the second leaf node using the secondary mapping table, the second leaf node having (i) a second logical ID, (ii) a third physical location determined using the secondary mapping table, and (iii) a parent node in the tiered data structure; and

modifying content of the second leaf node in accordance with the second request to perform a write operation for the second data object, including;

writing the modified second leaf node to a fourth physical location different from the third physical location,

updating a physical location corresponding to the second logical ID of the second leaf node in the secondary mapping table to the fourth physical location, while leaving unchanged the second logical ID of the second leaf node, to map the second logical ID of the second leaf node to the fourth physical location, and

leaving unchanged the parent node of the second leaf node.

2. The method of claim 1, wherein:

the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes; and

the internal nodes of the tiered data structure and the secondary mapping table are stored in volatile memory.

3. The method of claim 2, wherein a portion of the leaf nodes in the tiered data structure are cached in a volatile memory cache.

4. The method of claim 3, wherein determining the first physical location of the first leaf node includes:

searching the volatile memory cache for the second logical ID for the first leaf node; and

upon confirming that the volatile memory cache does not have a cached node corresponding to the first logical ID for the first leaf node, using the secondary mapping table to determine the first physical location of the first leaf node based on the first logical ID for the first leaf node.

5. The method of claim 2, wherein each leaf node of the plurality of leaf nodes corresponds to at least one data object.

6. The method of claim 5, wherein a respective leaf node of the plurality of leaf nodes includes metadata for a corresponding data object.

7. The method of claim 2, wherein the leaf nodes in the tiered data structure are stored in non-volatile memory.

8. The method of claim 1, further comprising:

receiving a third request to perform a write operation for a third data object to the storage device of the storage system, wherein the third request includes third data to be written for the third data object and third key information corresponding to the third data object;

determining whether a third entry for the third key information is in the tiered data structure; and

in accordance with a determination that the third entry for the third key information is in the tiered data structure;

allocating space at a fifth physical location in the storage device for the third data to be written for the third data object;

writing the third data to be written for the third data object to the fifth physical location;

invalidating data previously associated with the third data object; and

updating the third entry for the third key information in the tiered data structure to include size of the third data object and a sixth physical location.

9. The method of claim 1, further comprising:

concurrently with writing the second data to be written for the second data object to the fourth physical location, updating the second leaf node, in the tiered data structure, corresponding to the second data object to include metadata for the second data object.

10. The method of claim 1, wherein the method is controlled by a host that includes a client on behalf of which data is stored in the storage system.

11. The method of claim 1, wherein the method is controlled by a host that includes a storage system controller of the storage system.

12. The method of claim 1, wherein the method is controlled by a host that includes a cluster controller of the storage system.

13. The method of claim 1, wherein the storage device comprises one or more flash memory devices.

14. A host system, comprising:

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

one or more processors; and

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

detecting a first request to perform a read operation of a first data object stored in a storage device of the storage system, the first request including first key information corresponding to the first data object;

locating a first entry for the first key information in a tiered data structure, the first entry including a first logical ID for a first leaf node corresponding to the first key information;

determining a first physical location of the first leaf node based on the first logical ID for the first leaf node using a secondary mapping table, the secondary mapping table being used to translate logical IDs for leaf nodes to physical locations of leaf nodes;

reading the first leaf node using the first physical location to obtain a leaf node map entry, the leaf node map entry including size of the first data object and a second physical location of the first data object;

reading from the second physical location to obtain the first data object;

receiving a second request to perform a write operation for a second data object to the storage device, the second request including second data to be written for the second data object and second key information corresponding to the second data object; and

in accordance with a determination that a second entry for the second key information is in a second leaf node of the tiered data structure;

accessing the second leaf node using the secondary mapping table, the second leaf node having (i) a second logical ID, (ii) a third physical location determined using the secondary mapping table, and (iii) a parent node in the tiered data structure; and

modifying content of the second leaf node in accordance with the second request to perform a write operation for the second data object, including;

writing the modified second leaf node to a fourth physical location different from the third physical location,

updating a physical location corresponding to the second logical ID of the second leaf node in the secondary mapping table to the fourth physical location, while leaving unchanged the second logical ID of the second leaf node, to map the second logical ID of the second leaf node to the fourth physical location, and

leaving unchanged the parent node of the second leaf node.

15. The host system of claim 14, wherein:

the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes; and

the internal nodes of the tiered data structure and the secondary mapping table are stored in volatile memory.

16. The host system of claim 15, wherein a portion of the leaf nodes in the tiered data structure are cached in a volatile memory cache.

17. The host system of claim 16, wherein the operations further comprise:

receiving a third request to perform a write operation for a third data object to the storage device of the storage system, wherein the third request includes third data to be written for the third data object and third key information corresponding to the third data object;

determining whether a third entry for the third key information is in the tiered data structure; and

in accordance with a determination that the third entry for the third key information is in the tiered data structure;

allocating space at a fifth physical location in the storage device for the third data to be written for the third data object;

writing the third data to be written for the third data object to the fifth physical location;

invalidating data previously associated with the third data object; and

updating the third entry for the third key information in the tiered data structure to include size of the third data object and the fifth physical location.

18. The host system of claim 16,

wherein determining the first physical location of the first leaf node includes:

searching the volatile memory cache for the second logical ID for the first leaf node; and

upon confirming that the volatile memory cache does not have a cached node corresponding to the first logical ID for the first leaf node, using the secondary mapping table to determine the first physical location of the first leaf node based on the first logical ID for the first leaf node.

19. The host system of claim 14, wherein the operations further comprise:

receiving a third request to perform a write operation for a third data object to the storage device of the storage system, wherein the third request includes third data to be written for the third data object and third key information corresponding to the third data object;

determining whether a third entry for the third key information is in the tiered data structure; and

in accordance with a determination that the third entry for the third key information is in the tiered data structure;

allocating space at a fifth physical location in the storage device for the third data to be written for the third data object;

writing the third data to be written for the third data object to the fifth physical location;

invalidating data previously associated with the third data object; and

updating the third entry for the third key information in the tiered data structure to include size of the third data object and the fifth physical location.

20. A storage system, comprising:

one or more storage devices;

one or more subsystems having one or more processors; and

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

means for detecting a first request to perform a read operation of a first data object stored in a storage device of the storage system, the first request including first key information corresponding to the first data object;

means for locating a first entry for the first key information in a tiered data structure, the first entry including a first logical ID for a first leaf node corresponding to the first key information;

means for determining a first physical location of the first leaf node based on the first logical ID for the first leaf node using a secondary mapping table, the secondary mapping table being used to translate logical IDs for leaf nodes to physical locations of leaf nodes;

means for reading the first leaf node using the first physical location to obtain a leaf node map entry, the leaf node map entry including size of the first data object and a second physical location of the first data object;

means for reading from the second physical location to obtain the first data object;

means for receiving a second request to perform a write operation for a second data object to the storage device, the second request including second data to be written for the second data object and second key information corresponding to the second data object; and

in accordance with a determination that a second entry for the second key information is in a second leaf node of the tiered data structure;

means for accessing the second leaf node using the secondary mapping table, the second leaf node having (i) a second logical ID, (ii) a third physical location determined using the secondary mapping table, and (iii) a parent node in the tiered data structure; and

means for modifying content of the second leaf node in accordance with the second request to perform a write operation for the second data object, including;

means for writing the modified second leaf node to a fourth physical location different from the third physical location,

means for updating a physical location corresponding to the second logical ID of the second leaf node in the secondary mapping table to the fourth physical location, and means for leaving unchanged the second logical ID of the second leaf node, to map the second logical ID of the second leaf node to the fourth physical location, and

means for leaving unchanged the parent node of the second leaf node.

21. The storage system of claim 20, wherein the subsystems further comprise:

means for receiving a third request to perform a write operation for a third data object to the storage device of the storage system, wherein the third request includes third data to be written for the third data object and third key information corresponding to the third data object;

means for determining whether a third entry for the third key information is in the tiered data structure; and

in accordance with a determination that the third entry for the third key information is in the tiered data structure;

means for allocating space at a fifth physical location in the storage device for the third data to be written for the third data object;

means for writing the third data to be written for the third data object to the fifth physical location;

means for invalidating data previously associated with the third data object; and

means for updating the third entry for the third key information in the tiered data structure to include size of the third data object and the fifth physical location.