Address mapping table compression

• US 9,946,462 B1
• Filed: 02/15/2016
• Issued: 04/17/2018
• Est. Priority Date: 02/15/2016
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Li, Peng, Gomez, Kevin Arthur, Goss, Ryan James
• Primary Examiner(s): Chappell, Daniel C
• Application Number:
  US15/044,007
• Time in Patent Office: 792 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/466 Metadata, control data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Mapping table entries that map logical block addresses to physical block addresses can be intercepted and compressed to save space. In some cases, the mapping table entries can be compressed into compression units, which can hold multiple mapping table entries. Portions of the mapping table entries can be arranged into groups, and a group can be compressed with a unique compression method. The compression method used to compress a group may be based on data characteristics of the group. When data corresponding to the mapping table entries are read or modified, the compressed data can be decompressed and provided to a requesting controller or processor. When the mapping table entry is modified, the updated mapping entry may be arranged into groups, and the groups can be compressed and stored to the compression units.

Claims

1. An apparatus comprising:

a circuit configured to;

intercept a mapping table entry and a command to store the mapping table entry to a mapping table, the intercept occurring between a controller that generates the command and a memory that stores the mapping table;

determine a first data field and a second data field in the mapping table entry;

compress the first data field using a first data compression method to produce a compressed first data field;

compress the second data field using a second, different data compression method to produce a compressed second data field; and

store the compressed first data field and the compressed second data field to the memory.

2. The apparatus of claim 1 further comprising:

the circuit configured to;

combine the first compressed data field and the second compressed data field into a compression unit; and

store the compression unit to the memory.

3. The apparatus of claim 1 further comprising:

the first data compression method is selected based on data characteristics of the first data field; and

the second data compression method is selected based on data characteristics of the second data field.

4. The apparatus of claim 3 further comprising:

the data characteristics of the first data field and the data characteristics of the second data field include at least one of unique data patterns, repeated data patterns, sequential data patterns, and data patterns that rarely change.

5. The apparatus of claim 1 further comprising:

the circuit configured to;

intercept the first compressed data field and the second compressed data field when the memory sends the first compressed data field and the second compressed data field to the controller in response to a command from the controller for the mapping table entry.

6. The apparatus of claim 5 further comprising:

the circuit configured to;

decompress the first compressed data field to produce the first data field;

decompress the second compressed data field to produce the second data field;

combine the first data field and the second data field to reconstruct the mapping table entry; and

transmit the mapping table entry to the controller.

7. A system comprising:

a memory including a mapping table, where the mapping table includes a mapping table entry;

a circuit configured to;

intercept the mapping table entry and a command to store the mapping table entry to the mapping table;

determine a first data field and a second data field in the mapping table entry;

compress the first data field using a first data compression method to produce a compressed first data field;

compress the second data field using a second, different data compression method to produce a compressed second data field; and

store the compressed first data field and the compressed second data field to the memory.

8. The system of claim 7 further comprising:

the circuit configured to;

combine the first compressed data field and the second compressed data field into a compression unit; and

store the compression unit to the memory.

9. The system of claim 8 further comprising:

the compression unit includes metadata to indicate a compression status of the first compressed data field and the second compressed data field.

10. The system of claim 8 further comprising:

the compression unit is configured to store data fields corresponding to multiple mapping table entries, where a number of multiple mapping table entries is based on workload.

11. The system of claim 7 further comprising:

the mapping table entry is an updated mapping table entry, where the updated mapping table entry is provided by the controller when user data is stored to a second memory.

12. The system of claim 11 further comprising:

the first data compression method is selected based on data characteristics of the first data field;

the second data compression method is selected based on data characteristics of the second data field; and

the data characteristics of the first data field and the data characteristics of the second data field include at least one of unique data patterns, repeated data patterns, sequential data patterns, and data patterns that rarely change.

13. The system of claim 7 further comprising:

the circuit configured to;

intercept the first compressed data field and the second compressed data field when the memory sends the first compressed data field and the second compressed data field to the controller in response to a command from the controller for the mapping table entry.

14. The system of claim 13 further comprising:

the circuit configured to;

decompress the first compressed data field to produce the first data field;

decompress the second compressed data field to produce the second data field;

combine the first data field and the second data field to reconstruct the mapping table entry; and

transmit the mapping table entry to the controller.

15. The system of claim 7 further comprising:

the memory is a volatile solid state memory;

the second memory is a non-volatile solid state memory (“

NVSSM”

); and

the controller includes the circuit.

16. A method comprising:

determining a selected logical block address (“

LBA”

) mapping to update, the LBA mapping including a mapping table entry identifying a physical storage location to which data corresponding to the LBA is stored;

determining a compression unit corresponding to the selected LBA mapping, the compression unit including a plurality of compressed mapping table entries;

determining a first compressed data group in the compression unit into which a first portion of the selected LBA mapping has been compressed and a second compressed data group in the compression unit into which a second portion of the selected LBA mapping has been compressed; and

decompressing the compression unit using a first circuit to decompress the first compressed data group and a second circuit to decompress the second compressed data group to produce the selected LBA mapping, where the first circuit and the second circuit are different.

17. The method of claim 16 further comprising:

prior to decompressing the compression unit, determining if the selected LBA mapping is already in a buffer; and

providing the selected LBA mapping to a requesting controller when the selected LBA mapping is already in the buffer.

18. The method of claim 17 further comprising:

determining if the first compressed data group was successfully compressed, where a data group is successfully compressed when a compressed version of the data group is smaller than an uncompressed version of the data group;

storing the first portion of the LBA mapping to the buffer when the first compressed data group was not successfully compressed;

decompressing the first compressed data group to produce the first portion of the LBA mapping, and storing the first portion of the LBA mapping to the buffer when the first compressed data group was successfully compressed;

determining if the second compressed data group was successfully compressed, and storing the second portion of the LBA mapping to the buffer when the second compressed data group was not successfully compressed;

decompressing the second compressed data group to produce the second portion of the LBA mapping, and storing the second portion of the LBA mapping to the buffer when the second compressed data group was successfully compressed; and

combining the first portion of the LBA mapping and the second portion of the LBA mapping to produce the selected LBA mapping.

19. The method of claim 16 further comprising:

receiving the selected LBA mapping;

updating the selected LBA mapping with updated LBA mapping data to produce an updated LBA mapping;

arranging a first portion of the updated LBA mapping into a first uncompressed data group and the second portion of the updated LBA mapping into a second uncompressed data group;

compressing the first uncompressed data group with the first circuit to produce the first compressed data group where the first circuit is selected based on data characteristics of the first uncompressed data group; and

compressing the second uncompressed data group with the second circuit to produce the second compressed data group where the second circuit is selected based on data characteristics of the second uncompressed data group.

20. The method of claim 19 further comprising:

combining the first compressed data group and the second compressed data group, and storing them to the compression unit.