Memory-efficient block/object address mapping
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.
1. A method of managing a storage system having a plurality of 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, wherein:
the first request includes first key information corresponding to the first data object; and
the storage device in which the first data object is stored comprises a volatile memory cache and a non-volatile memory;
locating a first entry for the first key information in a tiered data structure, wherein:
the tiered data structure includes a plurality of internal nodes stored in the volatile memory cache and a plurality of leaf nodes stored in the non-volatile memory, and
locating the first entry includes determining a logical identifier (ID) for a leaf node corresponding to the first key information from an entry in a parent node of the leaf node, the parent node being one of the plurality of internal nodes of the tiered data structure stored in the volatile memory cache and the leaf node being one of the plurality of leaf nodes in the tiered data structure stored in the non-volatile memory;
determining a first physical location in the non-volatile memory of the leaf node based on the logical ID for the leaf node using a secondary mapping table to translate the logical ID for the leaf node to the physical location of the leaf node in the non-volatile memory;
reading the leaf node using the first physical location to obtain a leaf node map entry, wherein the leaf node map entry includes a size of the first data object and a second physical location in the non-volatile memory of the first data object; and
reading from the second physical location in the non-volatile memory to obtain the first data object.
2. The method of claim 1 , wherein locating the first entry for the first key information in the tiered data structure includes:
obtaining from a respective internal node of the tiered data structure, a respective logical ID for another internal node of the tiered data structure that includes the first entry; and
searching the volatile memory cache for the another internal node of the tiered data structure using the respective logical ID.
3. The method of claim 1 , wherein determining the first physical location of the leaf node includes:
searching the volatile memory cache for the logical ID for the leaf node;
confirming that the volatile memory cache does not have a cached node corresponding to the logical ID for the leaf node; and
in accordance with the confirming, using the secondary mapping table to determine the first physical location of the leaf node based on the logical ID for the leaf node.
4. The method of claim 1 , wherein each leaf node of the plurality of leaf nodes corresponds to at least one data object.
5. The method of claim 4 , wherein a respective leaf node of the plurality of leaf nodes includes metadata for a corresponding data object.
6. The method of claim 1 , wherein the secondary mapping table is stored in a dynamic random-access memory (DRAM).
7. The method of claim 1 , further comprising:
detecting a second request to perform a write operation for a second data object to the storage device of the storage system, wherein the second request includes data to be written for the second data object and second key information corresponding to the second data object;
determining whether a second entry for the second key information is in the tiered data structure;
in accordance with a determination that the second entry for the second key information is not in the tiered data structure:
allocating space at a third physical location in the storage device for the data to be written for the second data object;
writing the data to be written for the second data object to the third physical location; and
inserting the second entry for the second key information in the tiered data structure, wherein the second entry includes size of the second data object and the third physical location; and
in accordance with a determination that the second entry for the second key information is in the tiered data structure:
invalidating data previously associated with the second data object;
allocating space at the third physical location in the storage device for the data to be written for the second data object;
writing the data to be written for the second data object to the third physical location; and
updating the second entry for the second key information in the tiered data structure to include the size of the second data object and the third physical location.
8. The method of claim 7 , further comprising:
concurrently with writing the data to be written for the second data object to the third physical location, updating a leaf node, in the tiered data structure, corresponding to the second data object to include metadata for the second data object.
9. 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.
10. The method of claim 1 , wherein the method is controlled by a host that includes a storage system controller of the storage system.
11. The method of claim 1 , wherein the method is controlled by a host that includes a cluster controller of the storage system.
12. The method of claim 1 , wherein the storage device comprises one or more flash memory devices.
13. A host system, comprising:
an interface for operatively coupling to a storage system;
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, wherein:
the first request includes first key information corresponding to the first data object; and
the storage device in which the first data object is stored comprises a volatile memory cache and a non-volatile memory;
locating a first entry for the first key information in a tiered data structure, wherein:
the tiered data structure includes a plurality of internal nodes stored in the volatile memory cache and a plurality of leaf nodes stored in the non-volatile memory, and
locating the first entry includes determining a logical identifier (ID) for a leaf node corresponding to the first key information from an entry in a parent node of the leaf node, the parent node being one of the plurality of internal nodes of the tiered data structure stored in the volatile memory cache and the leaf node being one of the plurality of leaf nodes in the tiered data structure stored in the non-volatile memory;
determining a first physical location in the non-volatile memory of the leaf node based on the logical ID for the leaf node using a secondary mapping table to translate the logical ID for the leaf node to the physical location of the leaf node in the non-volatile memory;
reading the leaf node using the first physical location to obtain a leaf node map entry, wherein the leaf node map entry includes a size of the first data object and a second physical location in the non-volatile memory of the first data object; and
reading from the second physical location in the non-volatile memory to obtain the first data object.
14. The host system of claim 13 , wherein locating the first entry for the first key information in the tiered data structure includes:
obtaining from a respective internal node of the tiered data structure, a respective logical ID for another internal node of the tiered data structure that includes the first entry; and
searching the volatile memory cache for the another internal node of the tiered data structure using the respective logical ID.
15. The host system of claim 13 , wherein determining the first physical location of the leaf node includes:
searching the volatile memory cache for the logical ID for the leaf node;
confirming that the volatile memory cache does not have a cached node corresponding to the logical ID for the leaf node; and
in accordance with the confirming, using the secondary mapping table to determine the first physical location of the leaf node based on the logical ID for the leaf node.
16. The host system of claim 13 , wherein:
the storage system includes a storage controller in communication with the storage device; and
detecting the first request to perform the read operation includes receiving, at the storage device, the first request from the storage controller.
17. The host system of claim 16 , wherein:
the storage controller is a solid-state drive (SSD) controller; and
the storage device is a NAND-type flash memory device or a NOR-type flash memory device.
18. A host system, comprising:
an interface for operatively coupling to a storage system;
one or more processors; and
controller memory 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, wherein:
the first request includes first key information corresponding to the first data object; and
the storage device in which the first data object is stored comprises a volatile memory cache and a non-volatile memory;
means for locating a first entry for the first key information in a tiered data structure, wherein:
the tiered data structure includes a plurality of internal nodes stored in the volatile memory cache and a plurality of leaf nodes stored in the non-volatile memory, and
the means for locating the first entry includes means for determining a logical identifier (ID) for a leaf node corresponding to the first key information from an entry in a parent node of the leaf node, the parent node being one of the plurality of internal nodes of the tiered data structure stored in the volatile memory cache and the leaf node being one of the plurality of leaf nodes in the tiered data structure stored in the non-volatile memory;
means for determining a first physical location in the non-volatile memory of the leaf node based on the logical ID for the leaf node using a secondary mapping table to translate the logical ID for the leaf node to the physical location of the leaf node in the non-volatile memory;
means for reading the leaf node using the first physical location to obtain a leaf node map entry, wherein the leaf node map entry includes a size of the first data object and a second physical location in the non-volatile memory of the first data object; and
means for reading from the second physical location in the non-volatile memory to obtain the first data object.
19. The method of claim 1 , wherein:
the storage system includes a storage controller in communication with the storage device; and
detecting the first request to perform the read operation includes receiving, at the storage device, the first request from the storage controller.
20. The method of claim 19 , wherein:
the storage controller is a solid-state drive (SSD) controller; and
the storage device is a NAND-type flash memory device or a NOR-type flash memory device.