APPARATUS, SYSTEM, AND METHOD FOR EFFICIENT MAPPING OF VIRTUAL AND PHYSICAL ADDRESSES

• US 20090150641A1
• Filed: 04/06/2008
• Published: 06/11/2009
• Est. Priority Date: 12/06/2007
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Atkisson, David, Thatcher, Jonathan, Zappe, Michael, Strasser, John
• Granted Patent: US 8,195,912 B2
• Time in Patent Office: Days
• US Class Current: 711/202
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• 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/0674 Disk device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 Complex or three-dimensional-arrangements; Stepped or dual mother boards

Abstract

An apparatus, system, and method are disclosed for efficiently mapping virtual and physical addresses. A forward mapping module uses a forward map to identify physical addresses of data of a data segment from a virtual address. The data segment is identified in a storage request. The virtual addresses include discrete addresses within a virtual address space where the virtual addresses sparsely populate the virtual address space. A reverse mapping module uses a reverse map to determine a virtual address of a data segment from a physical address. The reverse map maps the data storage device into erase regions such that a portion of the reverse map spans an erase region of the data storage device erased together during a storage space recovery operation. A storage space recovery module uses the reverse map to identify valid data in an erase region prior to an operation to recover the erase region.

Claims

1. An apparatus to efficiently map physical and virtual addresses, the apparatus comprising:

a forward mapping module that uses a forward map to identify one or more physical addresses of data of a data segment, the one or more physical addresses identified from one or more virtual addresses of the data segment, the data segment identified in a storage request directed to a data storage device, the forward map comprising a map of one or more virtual addresses to one or more physical addresses of data stored in the data storage device, the one or more virtual addresses comprising discrete addresses within a virtual address space wherein the virtual addresses sparsely populate the virtual address space;

a reverse mapping module that uses a reverse map to determine a virtual address of a data segment from a physical address, wherein the reverse map maps the one or more physical addresses to one or more virtual addresses, the physical addresses in the reverse map associated with the forward map, the one or more virtual addresses corresponding to one or more data segments relating to the data stored in the data storage device, the reverse map mapping the data storage device into erase regions such that a portion of the reverse map spans an erase region of the data storage device erased together during a storage space recovery operation, the storage space recovery operation recovering erase regions for future storage of data; and

a storage space recovery module that uses the reverse map to identify valid data in an erase region prior to an operation to recover the erase region, the identified valid data moved to another erase region prior to the recovery operation.

2. The apparatus of claim 1, wherein one or more source parameters are stored with the data, the source parameters comprising at least the virtual address corresponding to the data segment related to the data and a data length of the stored data.

3. The apparatus of claim 2, further comprising a map rebuild module that rebuilds the forward map and the reverse map using the source parameters stored with the data.

4. The apparatus of claim 3, further comprising a checkpoint module that stores information related to the forward map and the reverse map, the checkpoint related to a point in time, the information sufficient to restore the forward map and the reverse map to a status related to the checkpoint.

5. The apparatus of claim 4, further comprising a map sync module that updates the forward map and the reverse map from the status related to the checkpoint to a current status by sequentially applying source parameters and physical addresses, the source parameters stored with data that was sequentially stored after the checkpoint, the physical addresses derived from a location of the data on the data storage device.

6. The apparatus of claim 1, wherein the forward map and the reverse map are independent of one or more of a file structure, a name space, and a directory that organize data for a requesting device transmitting the storage request.

7. The apparatus of claim 1, wherein a virtual address of the data segment of the storage request comprises one or more of a file name, an object name, and a block storage address, the block storage address comprising at least a physical address where a requesting device transmitting the storage request intends for the storage device to store the data segment and a length of the data segment.

8. The apparatus of claim 1, wherein the forward map and the reverse map comprise a first forward map and a first reverse map and wherein the first forward map and the first reverse map are stored as data and are stored independent of the data mapped by the first forward map and the first reverse map, the data comprising the first forward map, the first reverse map, and timestamp data stored with the first forward map and the first reverse map, the data of the first forward map and the first reverse map being indexed by a second forward map and a second reverse map.

9. The apparatus of claim 8, further comprising one or more additional forward and reverse maps, each stored as data and indexed by additional forward and reverse maps.

10. The apparatus of claim 1, wherein the forward map comprises information for valid data stored in the data storage device and the reverse map comprises information for valid data and invalid data stored on the data storage device.

11. The apparatus of claim 1, further comprising an invalidate module that marks an entry for data in the reverse map indicating that data referenced by the entry is invalid in response to an operation resulting in the data being invalidated.

12. The apparatus of claim 11, wherein the storage space recovery module further comprises determining a quantity of invalid data in an erase region by scanning the reverse map for the erase region to determine a quantity of invalid data in relation to a storage capacity of the erase region, the storage space recovery module using the quantity of invalid data in an erase region to select an erase region for recovery.

13. The apparatus of claim 12, wherein the storage space recovery module further comprises selecting an erase region for recovery, writing valid data from the selected erase region to a new location in the data storage device where data is currently being written, updating the reverse map to indicate that the valid data written to the new location is invalid in the selected erase region, and updating the forward map and the reverse map based on the valid data written to the new location.

14. The apparatus of claim 1, wherein the apparatus emulates a random access, block storage device storing data as directed by the storage request.

15. The apparatus of claim 1, wherein the forward map comprises one or more of a B-tree, a content addressable memory (“

CAM”

), a binary tree, and a hash table.

16. The apparatus of claim 1, further comprising a map update module that updates one or more of the forward map and the reverse map in response to altering contents of the data storage device, the map update module receiving information linking a physical address of stored data to a virtual address from the data storage device based on a location where the data storage device stored the data.

17. The apparatus of claim 1, wherein the apparatus receives the storage request substantially without data.

18. The apparatus of claim 17, wherein the apparatus initiates one or more of a direct memory access (“

DMA”

) process and a remote DMA (“

RDMA”

) process to transfer data to the data storage device in response to the storage request.

19. The apparatus of claim 1, wherein at least a portion of one or more of the forward mapping module, the reverse mapping module, and the storage space recovery module is located within one or more of a requesting device that transmits the storage request, the data storage device, the storage device controller, and a computing device separate from the requesting device, the data storage device, and the storage device controller.

20. A system to efficiently map physical and virtual addresses, the system comprising:

a data storage device;

a storage controller controlling data storage on the data storage device, the storage controller comprising

a forward mapping module that uses a forward map to identify one or more physical addresses of data of a data segment, the one or more physical addresses identified from one or more virtual addresses of the data segment, the data segment identified in a storage request directed to the data storage device, the forward map comprising a map of one or more virtual addresses to one or more physical addresses of data stored in the data storage device, the one or more virtual addresses comprising discrete addresses within a virtual address space wherein the virtual addresses sparsely populate the virtual address space;

a reverse mapping module that uses a reverse map to determines a virtual address of a data segment from a physical address, wherein the reverse map maps the one or more physical addresses to one or more virtual addresses, the physical addresses in the reverse map associated with the forward map, the one or more virtual addresses corresponding to one or more data segments relating to the data stored in the data storage device, the reverse map mapping the data storage device into erase regions such that a portion of the reverse map spans an erase region of the data storage device erased together during a storage space recovery operation, the storage space recovery operation recovering erase regions for future storage of data; and

a storage space recovery module that uses the reverse map to identify valid data in an erase region prior to an operation to recover the erase region, the identified valid data moved to another erase region prior to the recovery operation.

21. The system of claim 20, wherein the storage request is received from a client in communication with the storage controller over a computer network.

22. The system of claim 20, further comprising a server, wherein one or more of the storage controller and the data storage device are within the server.

23. The system of claim 20, wherein the storage device comprises a solid-state storage device and wherein the data of the data segment is stored in the solid-state storage.

24. A computer program product comprising a computer readable medium having computer usable program code executable to perform operations for efficiently mapping physical and virtual addresses, the operations of the computer program product comprising:

using a forward map to identify one or more physical addresses of data of a data segment, the one or more physical addresses identified from one or more virtual addresses of the data segment, the data segment identified in a storage request directed to a data storage device, the forward map comprising a map of one or more virtual addresses to one or more physical addresses of data stored in the data storage device, the one or more virtual addresses comprising discrete addresses within a virtual address space wherein the virtual addresses sparsely populate the virtual address space;

using a reverse map to determine a virtual address of a data segment from a physical address, wherein the reverse map maps the one or more physical addresses to one or more virtual addresses, the physical addresses in the reverse map associated with the forward map, the one or more virtual addresses corresponding to one or more data segments relating to the data stored in the data storage device, the reverse map mapping the data storage device into erase regions such that a portion of the reverse map spans an erase region of the data storage device erased together during a storage space recovery operation, the storage space recovery operation recovering erase regions for future storage of data; and

using the reverse map to identify valid data in an erase region prior to an operation to recover the erase region, the identified valid data moved to another erase region prior to the recovery operation.