Compression of indirection tables
In general, techniques are described for compressing an indirection table. A device comprising a processor and a memory may be configured to perform the techniques. The processor may be configured to form a plurality of physical containers, each of the plurality of physical containers representative of a plurality of physical block addresses, wherein each of the plurality of physical containers corresponds to one or more logical block address. The memory may be configured to store an indirection table that maps the logical block addresses to the plurality of physical containers. The processor may be further configured to perform run-length encoding of the plurality of physical containers to compress the indirection table.
1. A method comprising:
forming, by a processor, a plurality of physical containers, each of the plurality of physical containers representative of a plurality of physical block addresses, and each of the plurality of physical containers corresponding to one or more logical block addresses;
determining, by the processor, an indirection table that maps the logical block addresses to the plurality of physical containers; and
performing, by the processor, run-length encoding with respect to the plurality of physical containers to compress the indirection table.
2. The method of claim 1 , wherein performing run-length encoding comprises merging a first one of the plurality of physical containers with a second one of the plurality of physical containers adjacent to the first one of the plurality of physical containers in the indirection table to form a single compressed physical container.
3. The method of claim 1 ,
wherein a first one of the plurality of physical containers is adjacent to a second one of the plurality of physical containers in the indirection table,
wherein the first one of the plurality of physical containers includes a same number of logical block addresses as the second one of the plurality of physical containers, and
wherein performing run-length encoding comprises merging the first one of the plurality of physical containers and the second one of the plurality of physical containers to form a single compressed physical container.
4. The method of claim 1 , wherein performing run-length encoding comprises:
merging a first one of the plurality of physical containers with a second one of the plurality of physical containers adjacent to the first one of the plurality of physical containers in the indirection table to form a single compressed physical container;
determining a logical block address shift amount based on a difference in a number of the logical block addresses included in each of the first one of the plurality of physical containers and the second one of the plurality of physical containers; and
updating a number of logical block addresses in each of the plurality of physical containers subsequent to the single compressed physical container in the indirection table based on the logical block address shift amount.
5. The method of claim 4 , wherein determining the logical block address shift amount comprises determining the logical block address shift amount such that the logical block address shift amount is equal to or greater than zero.
6. The method of claim 4 , wherein determining the logical block address shift amount comprises determining the logical block address shift amount based on the difference and a previous logical block address shift amount determined for either the first one of the plurality of physical containers or the second one of the plurality of physical containers.
7. The method of claim 6 , wherein determining the logical block address shift amount comprises:
determining the difference to be a negative difference, wherein the magnitude of the negative difference is less than a magnitude of the previous logical block address shift amount; and
adding the negative difference to the previous logical block address shift amount such that the logical block address shift amount is equal to or greater than zero.
8. The method of claim 1 , wherein performing the run-length encoding comprises iteratively performing the run-length encoding using an iteratively increasing difference between a number of logical block addresses included in adjacent ones of the plurality of physical containers until a threshold amount of compression is achieved.
9. The method of claim 1 , wherein the processor comprises a controller of a hard disk drive.
10. A device comprising:
a processor configured to form a plurality of physical containers, each of the plurality of physical containers representative of a plurality of physical block addresses, wherein each of the plurality of physical containers corresponds to one or more logical block address; and
a memory configured to store an indirection table that maps the logical block addresses to the plurality of physical containers,
wherein the processor is further configured to perform run-length encoding of the plurality of physical containers to compress the indirection table.
11. The device of claim 10 , wherein the processor is further configured to merge a first one of the plurality of physical containers with a second one of the plurality of physical containers adjacent to the first one of the plurality of physical containers in the indirection table to form a single compressed physical container.
12. The device of claim 10 ,
wherein a first one of the plurality of physical containers is adjacent to a second one of the plurality of physical containers in the indirection table,
wherein the first one of the plurality of physical containers includes a same number of logical block addresses as the second one of the plurality of physical containers, and
wherein the processor is further configured to merge the first one of the plurality of physical containers and the second one of the plurality of physical containers to form a single compressed physical container.
13. The device of claim 10 , wherein the processor is further configured to:
merge a first one of the plurality of physical containers with a second one of the plurality of physical containers adjacent to the first one of the plurality of physical containers in the indirection table to form a single compressed physical container;
determine a logical block address shift amount based on a difference in a number of the logical block addresses included in each of the first one of the plurality of physical containers and the second one of the plurality of physical containers; and
update a number of logical block addresses in each of the plurality of physical containers subsequent to the single compressed physical container in the indirection table based on the logical block address shift amount.
14. The device of claim 13 , wherein the processor is further configured to determine the logical block address shift amount such that the logical block address shift amount is equal to or greater than zero.
15. The device of claim 13 , wherein the processor is further configured to determine the logical block address shift amount based on the difference and a previous logical block address shift amount determined for either the first one of the plurality of physical containers or the second one of the plurality of physical containers.
16. The device of claim 15 , wherein the processor is further configured to:
determine the difference to be a negative difference, wherein the magnitude of the negative difference is less than a magnitude of the previous logical block address shift amount; and
add the negative difference to the previous logical block address shift amount such that the logical block address shift amount is equal to or greater than zero.
17. The device of claim 10 , wherein the processor is further configured to iteratively perform the run-length encoding using an iteratively increasing difference between a number of logical block addresses included in adjacent ones of the plurality of physical containers until a threshold amount of compression is achieved.
18. The device of claim 10 , wherein the processor comprises a controller of a hard disk drive.
19. A non-transitory computer-readable storage medium storing instructions that, when executed, cause a processor to:
form a plurality of physical containers, each of the plurality of physical containers representative of a plurality of physical block addresses, and each of the plurality of physical containers corresponding to one or more logical block addresses;
determine an indirection table that maps the logical block addresses to the plurality of physical containers, and
perform run-length encoding with respect to the plurality of physical containers to compress the indirection table.
20. The non-transitory computer-readable storage medium of claim 19 , wherein the instructions cause the processor to merge a first one of the plurality of physical containers with a second one of the plurality of physical containers adjacent to the first one of the plurality of physical containers in the indirection table to form a single compressed physical container.