Hash-based one-level mapping for storage clusters
A method comprising: storing, in a memory, a mapping tree that is implemented by using an array of mapping pages, the mapping tree having a depth of D, wherein D is an integer greater than or equal to 0; receiving a write request that is associated with a first type-1 address; storing, in a storage device, data associated with the write request, the data associated with the write request being stored in the storage device based on a first type-2 address; generating a map entry that maps the first type-1 address to the first type-2 address; calculating a first hash digest of the first type-1 address; and storing the map entry in a first mapping page.
1. A method comprising:
storing, in a memory, a mapping tree that is implemented by using an array of mapping pages, the mapping tree having a depth of D, wherein D is an integer greater than or equal to 0;
receiving a write request that is associated with a first type-1 address;
storing, in a storage device, data associated with the write request, the data associated with the write request being stored in the storage device based on a first type-2 address;
generating a map entry that maps the first type-1 address to the first type-2 address;
calculating a first hash digest of the first type-1 address; and
storing the map entry in a first mapping page, the first mapping page being located at a first index in the array, wherein the first index is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the first hash digest.
2. The method of claim 1 , further comprising:
receiving a read request that is associated with a second type-1 address
calculating a second hash digest of the second type-1 address;
retrieving a second mapping page that is located at a second index in the array, wherein the second index is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the second hash digest
performing search of the second mapping page to identify a second type-2 address that is mapped to the second type-1 address;
retrieving data from the storage device based on the second type-2 address; and
returning the retrieved data to a sender of the read request.
3. The method of claim 1 , wherein storing the map entry includes:
retrieving a mapping page P 1 that is stored at an index I 1 in the array, wherein the index I 1 is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the first hash digest;
detecting whether the mapping page P 1 is full;
when the mapping page P 1 is not full: storing the map entry in the mapping page P 1 ;
when the mapping page P 1 is full; generating a mapping page P 2 , adding the mapping page P 2 at an index I 2 in the array, transferring one or more mapping entries from the mapping page P 1 to the mapping page P 2 , and storing the map entry in one of the mapping page P 1 or the mapping page P 2 .
4. The method of claim 3 , wherein the index I 2 is greater than the index I 1 , and the map entry is stored in the mapping page P 2 only when the index I 2 can be represented by D or fewer least significant bits of the first hash digest.
5. The method of claim 3 , wherein the index I 2 is generated by setting a least significant unset bit of the index I 1 .
6. The method of claim 1 , wherein the first type-1 address is a logical block address (LBA) in a first address space of a data volume and the first type-2 address is an address in a second address space of the storage device.
7. The method of claim 1 , wherein the first type-1 address is a logical block address (LBA) in a first address space of a data volume and the first type-2 address is an address in a second address space of a storage array including the storage device.
8. A system, comprising:
a memory configured to store storing a mapping tree that is implemented by using an array of mapping pages, the mapping tree having a depth of D, wherein D is an integer greater than or equal to 0; and
a processing circuitry operatively coupled to the memory, the processing circuitry being configured to perform the operations of:
receiving a write request that is associated with a first type-1 address;
storing, in a storage device, data associated with the write request, the data associated with the write request being stored in the storage device based on a first type-2 address;
generating a map entry that maps the first type-1 address to the first type-2 address;
calculating a first hash digest of the first type-1 address; and
storing the map entry in a first mapping page, the first mapping page being located at a first index in the array, wherein the first index is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the first hash digest.
9. The system of claim 8 , wherein the processing circuitry is further configured to perform the operations of:
receiving a read request that is associated with a second type-1 address
calculating a second hash digest of the second type-1 address;
retrieving a second mapping page that is located at a second index in the array, wherein the second index is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the second hash digest,
performing search of the second mapping page to identify a second type-2 address that is mapped to the second type-1 address;
retrieving data from the storage device based on the second type-2 address; and
returning the retrieved data to a sender of the read request.
10. The system of claim 8 , wherein storing the map entry includes:
retrieving a mapping page P 1 that is stored at an index I 1 in the array, wherein the index I 1 is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the first hash digest;
detecting whether the mapping page P 1 is full;
when the mapping page P 1 is not full: storing the map entry in the mapping page P 1 ;
when the mapping page P 1 is full: generating a mapping page P 2 , adding the mapping page P 2 at an index I 2 in the array, transferring one or more mapping entries from the mapping page P 1 to the mapping page P 2 , and storing the map entry in one of the mapping page P 1 or the mapping page P 2 .
11. The system of claim 10 , wherein the index I 2 is greater than the index I 1 , and the map entry is stored in the mapping page P 2 only when the index I 2 can be represented by D or fewer least significant bits of the first hash digest.
12. The system of claim 10 , wherein the index I 2 is generated by setting a least significant unset bit of the index I 1 .
13. The system of claim 8 , wherein the first type-1 address is a logical block address (LBA) in a first address space of a data volume and the first type-2 address is an address in a second address space of the storage device.
14. The system of claim 8 ,
wherein the first type-1 address is a logical block address (LBA) in a first address space of a data volume and the first type-2 address is an address in a second address space of a storage array including the storage device.
15. A non-transitory computer-readable medium storing one or more processor-executable instructions, which when executed by at least one processor, cause the at least one processor to perform the operations of:
storing, in a memory, a mapping tree that is implemented by using an array of mapping pages, the mapping tree having a depth of D, wherein D is an integer greater than or equal to 0;
receiving a write request that is associated with a first type-1 address;
storing, in a storage device, data associated with the write request, the data associated with the write request being stored in the storage device based on a first type-2 address;
generating a map entry that maps the first type-1 address to the first type-2 address;
calculating a first hash digest of the first type-1 address; and
storing the map entry in a first mapping page, the first mapping page being located at a first index in the array, wherein the first index is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the first hash digest.
16. The non-transitory computer-readable medium of claim 15 , wherein the processor-executable instructions, when executed by the at least one processor, further cause the at least one processor to perform the operations of:
receiving a read request that is associated with a second type-1 address
calculating a second hash digest of the second type-1 address;
retrieving a second mapping page that is located at a second index in the array, wherein the second index is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant bits of the second hash digest,
performing search of the second mapping page to identify a second type-2 address that is mapped to the second type-1 address;
retrieving data from the storage device based on the second type-2 address; and
returning the retrieved data to a sender of the read request.
17. The non-transitory computer-readable medium of claim 15 , wherein storing the map entry includes:
retrieving a mapping page P 1 that is stored at an index I 1 in the array, wherein the index I 1 is the largest index in the array that contains a mapping page among all indices in the array that can be represented by D or fewer least significant hits of the first hash digest;
detecting whether the mapping page P 1 is full;
when the mapping page P 1 is not full: storing the map entry in the mapping page P 1 ;
when the mapping page P 1 is full: generating a mapping page P 2 , adding the mapping page P 2 at an index I 2 in the array, transferring one or more mapping entries from the mapping page P 1 to the mapping page P 2 , and storing the map entry in one of the mapping page P 1 or the mapping page P 2 .
18. The non-transitory computer-readable medium of claim 17 , Wherein the index I 2 is greater than the index I 1 , and the map entry is stored in the mapping page P 2 only when the index I 2 can be represented by D or fewer least significant bits of the first hash digest.
19. The non-transitory computer-readable medium of claim 17 , wherein the index I 2 is generated by setting a least significant unset bit of the index I 1 .
20. The non-transitory computer-readable readable medium of claim 15 , wherein the first type-1 address is a logical block address (LBA) in a first address space of a data volume and the first type-2 address is an address in a second address space of the storage device.