Mapping table compression using a run length encoding algorithm
View Patent ↗Apparatus and methods are disclosed, including using a memory controller to generate an encoded physical address using a run length encoding (RLE) algorithm on a physical address to reduce a length of the encoded physical address, and storing the encoded physical address as a map entry of a logical-to-physical (L2P)) table in a cache random access memory of the memory controller.
1. A storage system comprising:
a memory array;
a map automation logic;
a random access memory; and
a memory controller, wherein the memory controller is programmed to perform operations comprising:
generating an encoded physical address using a run length encoding (RLE) algorithm on a physical address of the memory array to reduce a length of the encoded physical address, wherein the RLE algorithm is based on differences from a current logical block address (LBA) to a next sequential LBA;
storing the encoded physical address as a map entry in the random access memory; and
using the map automation logic to compress and read the map entry, including performing a local unpacking and discarding intermediate results.
2. The storage system of claim 1 , wherein the map entry is included in a cached logical-to-physical (L2P) table.
3. The storage system of claim 1 , wherein using the RLE algorithm includes removing reserved bits from the physical address.
4. The storage system of claim 1 , wherein using the RLE algorithm includes removing static bits from the physical address.
5. The storage system of claim 1 , wherein storing the encoded physical address includes using a first-in, first-out (FIFO) structure.
6. The storage system of claim 1 , wherein the memory controller is programmed to perform operations comprising:
retrieving a map page from remote storage;
packing the map page into a reduced-sized packed map page by generating encoded physical addresses using the run length encoding (RLE) algorithm on each physical address in the map page; and
storing the packed map page in the random access memory.
7. The storage system of claim 6 , wherein the memory controller is programmed to perform operations comprising:
storing a length and an address of the packed map page in the random access memory.
8. The storage system of claim 6 , wherein the memory controller is programmed to perform operations comprising:
retrieving the packed map page from the random access memory; and
unpacking the packed map page by translating encoded physical addresses using the run length encoding (RLE) algorithm to obtain each physical address.
9. A method comprising:
generating, by a memory controller, an encoded physical address using a run length encoding (RLE) algorithm on a physical address to reduce a length of the encoded physical address, wherein the RLE algorithm is based on differences from a current logical block address (LBA) to a next sequential LBA;
storing, by the memory controller, the encoded physical address as a map entry in a random access memory of the memory controller; and
compressing and reading the map entry, by map automation logic, including performing a local unpacking and discarding intermediate results.
10. The method of claim 9 , wherein the map entry is included in a cached logical-to-physical (L2P) table.
11. The method of claim 9 , wherein using the RLE algorithm includes removing reserved bits from the physical address.
12. The method of claim 9 , wherein using the RLE algorithm includes removing static bits from the physical address.
13. The method of claim 9 , wherein storing the encoded physical address includes using a first-in, first-out (FIFO) structure.
14. The method of claim 9 , further comprising:
retrieving a map page from remote storage;
packing the map page into a reduced-sized packed map page by generating encoded physical addresses using the run length encoding (RLE) algorithm on each physical address in the map page; and
storing the packed map page in the random access memory.
15. The method of claim 14 , further comprising:
storing a length and an address of the packed map page in the random access memory.
16. The method of claim 14 , further comprising:
retrieving the packed map page from the random access memory; and
unpacking the packed map page by translating encoded physical addresses using the run length encoding (RLE) algorithm to obtain each physical address.
17. A non-transitory computer readable storage medium comprising instructions thereon that, when executed by a processor, cause the processor to perform operations comprising:
generating an encoded physical address using a run length encoding (RLE) algorithm on a physical address to reduce a length of the encoded physical address, wherein the RLE algorithm is based on differences from a current logical block address (LBA) to a next sequential LBA;
storing the encoded physical address as a map entry in a random access memory; and
using map automation logic to compress and read the map entry, including performing a local unpacking and discarding intermediate results.
18. The non-transitory computer readable storage medium of claim 17 , wherein the map entry is included in a cached logical-to-physical (L2P) table.
19. The non-transitory computer readable storage medium of claim 17 , wherein using the RLE algorithm includes removing reserved or static bits from the physical address.
20. The non-transitory computer readable storage medium of claim 17 , wherein storing the encoded physical address includes using a first-in, first-out (FIFO) structure.