Low-cost address mapping for storage devices with built-in transparent compression
AssigneeScaleflux, Inc.
InventorsJiangpeng Li, Qi Wu
Life of this patent
Estimating the term…
Abstract
An infrastructure for mapping between logic block addresses (LBAs) and physical block addresses (PBAs). A disclosed method includes: receiving a request the specifies an LBA; determining an applicable zone based on the LBA from a set of zones, wherein the set of zones expose an LBA address space of the storage device; identifying at least one tree from a set of trees having a root node associated with the applicable zone; traversing the at least one tree to identify a set of leaf nodes based on the LBA, wherein each leaf node points to an mpage; and determining corresponding PBA information for the LBA by examining mapping information contained in each mpage.
Claims20
A solid state storage device, comprising:
- a compression system that compresses and decompresses data stored in the storage device;
- and
- a controller that utilizes a three tiered logical block address (LBA)/physical block address (PBA) map to map between logical storage and physical storage, wherein the LBA/PBA map includes:
- a zone layer having a set of zones that expose an LBA address space of the storage device, wherein each zone spans a contiguous region of LBA addresses;
- a routing layer having a set of trees, wherein each tree is indexed by an LBA address and includes a root node and a set of leaf nodes, wherein each root node is associated with a zone from the zone layer, and each leaf node includes a pointer;
- and
- an mpage layer that includes a set of mpages, each mpage pointed to by a pointer from the routing layer, wherein each mpage contains LBA/PBA mapping information for LBAs within a contiguous range of LBAs.
A method, implemented on a solid state storage device, for mapping between logic block addresses (LBAs) and physical block addresses (PBAs), comprising:
- receiving a request the specifies an LBA;
- determining an applicable zone based on the LBA from a set of zones, wherein the set of zones expose an LBA address space of the storage device;
- identifying at least one tree from a set of trees having a root node associated with the applicable zone;
- traversing the at least one tree to identify a set of leaf nodes based on the LBA, wherein each leaf node points to an mpage;
- and
- determining corresponding PBA information for the LBA by examining mapping information contained in each mpage.
Dependencies are inferred from the claim text.