Logical to physical data storage mapping

Abstract

A method operable with a storage system comprises processing an Input/Output (I/O) request to a storage device, extracting a logical mapping unit from the I/O request, determining that the I/O request is for variable length data, and accessing a map that links the logical mapping unit to one or more physical addresses of the storage device. The method also comprises calculating a number of physical mapping units at the physical addresses to service the I/O request.

What is claimed is: 
     
         1 . A method, comprising:
 processing an Input/Output (I/O) request to a storage device;   extracting a logical mapping unit from the I/O request;   determining that the I/O request is for variable length data;   accessing a map that links the logical mapping unit (LMU) to one or more physical addresses of the storage device; and   calculating a number of physical mapping units at the physical addresses to service the I/O request.   
     
     
         2 . The method of  claim 1 , wherein:
 the I/O request is a read I/O request.   
     
     
         3 . The method of  claim 1 , wherein calculating the number of physical mapping units at the physical addresses comprises:
 extracting a length of the variable length data from the map; and   dividing the length by a number of data bytes stored in one physical mapping unit.   
     
     
         4 . The method of  claim 1 , wherein:
 the storage device is a NAND flash storage device, phase-change memory, Random Access Memory (RAM), resistive RAM, a magnetoresistive storage device, a magnetic recording medium, or a combination thereof.   
     
     
         5 . The method of  claim 1 , further comprising:
 processing another I/O request to the storage device;   extracting another logical mapping unit from the other I/O request;   determining that the other I/O request is for fixed length data;   accessing a mapping structure in the map that links the other logical mapping unit to one physical address of the storage device, wherein the mapping structure omits a length of the data to service the I/O request.   
     
     
         6 . The method of  claim 1 , further comprising:
 determining that the data is a duplicate of previously written data in the storage device;   reordering the data to improve deduplication efficiency;   and   generating a header associated with the LMU to point to the previously written data, the previously written data having another header associated with another LMU.   
     
     
         7 . A storage system, comprising:
 a storage device; and   a controller operable to process an Input/Output (I/O) request to the storage device, to extract a logical mapping unit from the I/O request, to determine that the I/O request is for variable length data, to access a map that links the logical mapping unit to one or more physical addresses of the storage device, and to calculate a number of physical mapping units at the physical addresses to service the I/O request.   
     
     
         8 . The storage system of  claim 7 , wherein:
 the I/O request is a read I/O request.   
     
     
         9 . The storage system of  claim 7 , wherein:
 the controller is further operable to calculate a number of physical mapping units at the physical addresses by:   extracting a length of the variable length data from the map; and   dividing the length by a number of data bytes stored in one physical mapping unit.   
     
     
         10 . The storage system of  claim 7 , wherein:
 the storage device is a NAND flash storage device, phase-change memory, Random Access Memory (RAM), resistive RAM, a magnetoresistive storage device, a magnetic recording medium, or a combination thereof.   
     
     
         11 . The storage system of  claim 7 , wherein:
 the controller is further operable to processing another I/O request to the storage device, to extract another logical mapping unit from the other I/O request, to determine that the other I/O request is for fixed length data, and to access a mapping structure in the map that links the other logical mapping unit to one physical address of the storage device, wherein the mapping structure omits a length of the data to service the I/O request.   
     
     
         12 . The storage system of  claim 7 , wherein:
 the controller is further operable to determine that the data is a duplicate of previously written data in the storage device, and to generate a header associated with the LMU to point to the previously written data, the previously written data having another header associated with another LMU.   
     
     
         13 . A method of garbage collection in a storage device, the method comprising:
 upon a write of data to a first garbage collection unit (GCU):   incrementing a number of logical mapping units stored in the first GCU;   incrementing a number of logical mapping units with valid data stored in the first GCU;   decrementing a number of logical mapping units with invalid data stored in a second GCU based on the incremented number of logical mapping units with valid data stored in the first GCU; and   erasing the second GCU when a valid data rate of the second GCU is below a valid data rate of the first GCU.   
     
     
         14 . The method of  claim 13 , further comprising:
 erasing the second GCU comprises when a valid number of logging mapping units is less than a valid number of logging mapping units of the first GCU.   
     
     
         15 . The method of  claim 13 , further comprising:
 computing an average compression rate or a deduplication rate of the data written to the second GCU.   
     
     
         16 . The method of  claim 15 , wherein computing comprises:
 computing a compressed length of the data written to the second GCU based on the average compression rate or a deduplication rate of the data written to the second GCU and a size of a logical mapping unit stored in the second GCU.   
     
     
         17 . The method of  claim 16 , wherein computing a compressed length of the data written to the second GCU comprises:
 computing the size of a logical mapping unit stored in the second GCU and dividing the size by the average compression rate or a deduplication rate.   
     
     
         18 . The method of  claim 15 , further comprising:
 computing a size of valid data bytes of the second GCU based on the number of logical mapping units with valid data stored in the second GCU, the size of a logical mapping unit stored in the second GCU, and the average compression rate.   
     
     
         19 . The method of  claim 13 , further comprising:
 computing the valid data rate of the second GCU based on a number of logical mapping units with valid data stored in the second GCU and a total number of logical mapping units stored in the second GCU.   
     
     
         20 . A method of garbage collection in a storage device, the method comprising:
 upon a write of data to a first garbage collection unit (GCU):   incrementing a number of logical mapping units stored in the first GCU;   incrementing a number of logical mapping units with valid data stored in the first GCU;   decrementing a number of logical mapping units with invalid data stored in a second GCU based on the incremented number of logical mapping units with valid data stored in the first GCU; and   erasing the second GCU when the number logical mapping units with invalid data stored in the second GCU reaches a total number of physical mapping units of the second GCU.