Apparatus, system, and method for efficient mapping of virtual and physical addresses

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.

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, the apparatus further comprising:
 a map rebuild module that rebuilds the forward map and the reverse map using the source parameters stored with the data;   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; and   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.   
     
     
         3 . 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. 
     
     
         4 . 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. 
     
     
         5 . 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, the apparatus further comprising one or more additional forward and reverse maps, each stored as data and indexed by additional forward and reverse maps. 
     
     
         6 . 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. 
     
     
         7 . 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. 
     
     
         8 . The apparatus of  claim 8 , 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. 
     
     
         9 . The apparatus of  claim 9 , 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. 
     
     
         10 . The apparatus of  claim 1 , wherein the apparatus emulates a random access, block storage device storing data as directed by the storage request. 
     
     
         11 . 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. 
     
     
         12 . 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. 
     
     
         13 . The apparatus of  claim 1 , wherein the apparatus receives the storage request substantially without data. 
     
     
         14 . The apparatus of  claim 14 , 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. 
     
     
         15 . 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. 
     
     
         16 . 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. 
   
     
     
         17 . The system of  claim 16 , wherein the storage request is received from a client in communication with the storage controller over a computer network. 
     
     
         18 . The system of  claim 16 , further comprising a server, wherein one or more of the storage controller and the data storage device are within the server. 
     
     
         19 . The system of  claim 16 , 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. 
     
     
         20 . A method, 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.