Translation lookup and garbage collection optimizations on storage system with paged translation table
A system comprising a processor and a memory storing instructions that, when executed, cause the system to receive a request for garbage collection, identify a range of physical blocks in a storage device, query a bitmap, the bitmap having a bit for each physical block in the range of physical blocks, determine a status associated with a first bit from the bitmap, in response to determining the status associated with the first bit is a first state, add a first physical block associated with the first bit to a list of physical blocks for relocation, and relocate the list of physical blocks.
1. A method comprising:
receiving a request to map a first physical block to a first logical block;
assigning a first state to a first bit associated with the first physical block;
receiving a write request for the first logical block;
mapping a second physical block to the first logical block;
assigning a second state to the first bit associated with the first physical block;
assigning the first state to a second bit associated with the second physical block;
updating a bitmap using the second state associated with the first bit and the first state associated with the second bit;
receiving a write request for a second logical block;
mapping the second logical block to a third physical block;
allocating a third bit associated with the third physical block;
assigning the first state to the third bit associated with the third physical block; and
updating the bitmap based on the first state assigned to the third bit.
2. The method of claim 1 , wherein a size of the bitmap corresponds to a size of a storage device receiving the write request.
3. The method of claim 1 , further comprising:
receiving a request for garbage collection;
identifying a range of physical blocks in a storage device;
querying the bitmap, the bitmap having a bit for each physical block in the range of physical blocks;
determining a status associated with a first bit from the bitmap;
in response to determining the status associated with the first bit is a first state, adding a first physical block associated with the first bit to a list of physical blocks for relocation; and
using the list of physical blocks, to relocate data stored at the first physical block.
4. The method of claim 1 , wherein the first state indicates an active mapping associated with the second physical block.
5. The method of claim 1 , further comprising:
receiving a request to pre-fetch a translation table entry; and
in response to receiving the request to pre-fetch, marking the translation table entry in a memory; and
generating a non-zero reference count for the marked translation table entry.
6. The method of claim 5 , wherein the marked translation table entry is associated with an expiration timeout.
7. The method of claim 1 , wherein the mapping the second physical block to the first logical block is responsive to an overwrite request for the first logical block.
8. The method of claim 1 , wherein the first state is an ON state, and the second state is an OFF state.
9. An apparatus, comprising:
a storage device;
a processor coupled to the storage device and configured to:
receive a request to map a first physical block to a first logical block;
assign a first state to a first bit associated with the first physical block;
receive a write request for the first logical block;
map a second physical block to the first logical block;
assign a second state to the first bit associated with the first physical block;
assign the first state to a second bit associated with the second physical block;
update a bitmap using the second state associated with the first bit and the first state associated with the second bit;
receive a write request for a second logical block;
map the second logical block to a third physical block;
allocate a third bit associated with the third physical block;
assign the first state to the third bit associated with the third physical block; and
update the bitmap based on the first state assigned to the third bit.
10. The apparatus of claim 9 , wherein a size of the bitmap corresponds to a size of a storage device receiving the write request.
11. The apparatus of claim 9 , wherein the processor is further configured to:
receive a request for garbage collection;
identify a range of physical blocks in a storage device;
query the bitmap, the bitmap having a bit for each physical block in the range of physical blocks;
determine a status associated with a first bit from the bitmap;
in response to determining the status associated with the first bit is a first state, add a first physical block associated with the first bit to a list of physical blocks for relocation; and
use the list of physical blocks, to relocate data stored at the first physical block.
12. The apparatus of claim 9 , wherein the first state indicates an active mapping associated with the second physical block.
13. The apparatus of claim 9 , wherein the processor is further configured to:
receive a request to pre-fetch a translation table entry; and
in response to receiving the request to pre-fetch, mark the translation table entry in a memory; and
generate a non-zero reference count for the marked translation table entry.
14. The apparatus of claim 13 , wherein the marked translation table entry is associated with an expiration timeout.
15. The apparatus of claim 9 , wherein the processor configured to map the second physical block to the first logical block is responsive to an overwrite request for the first logical block.
16. The apparatus of claim 9 , wherein the first state is an ON state, and the second state is an OFF state.
17. A method comprising:
receiving a request to map a first physical block to a first logical block;
assigning a first state to a first bit associated with the first physical block;
receiving a write request for the first logical block;
mapping a second physical block to the first logical block;
assigning a second state to the first bit associated with the first physical block;
assigning the first state to a second bit associated with the second physical block;
receiving a request to pre-fetch a translation table entry; and
in response to receiving the request to pre-fetch, marking the translation table entry in a memory; and
generating a non-zero reference count for the marked translation table entry.
18. An apparatus, comprising:
a storage device;
a processor coupled to the storage device and configured to:
receive a request to map a first physical block to a first logical block;
assign a first state to a first bit associated with the first physical block;
receive a write request for the first logical block;
map a second physical block to the first logical block;
assign a second state to the first bit associated with the first physical block;
assign the first state to a second bit associated with the second physical block;
receive a request to pre-fetch a translation table entry; and
in response to receiving the request to pre-fetch, mark the translation table entry in a memory; and
generate a non-zero reference count for the marked translation table entry.