Storing metadata in a cuckoo tree

1. A method of storing block-based metadata in a data storage system (DSS), the method comprising:

receiving a request to write a block of data to a logical address of the DSS;

assigning a physical address within the DSS where the block of data is to be stored;

creating a metadata entry for the block of data, the metadata entry including the physical address;

storing a key-value pair within a sorted key-value structure (SKVS) of an ordered plurality of SKVSes, each SKVS having a unique identifier, the key-value pair including the logical address as the key and the metadata entry as the value;

placing an entry within a Cuckoo filter based on the key value, the entry including the identifier of the SKVS in which the key-value pair was stored; and

subsequently accessing the data by:

locating the metadata entry with reference to the Cuckoo filter and

locating the data with reference to the physical address in the metadata entry.

2. The method of claim 1 wherein the method further comprises:

in response to storing the key-value pair within the SKVS, determining that the SKVS has reached a predetermined maximum size;

in response to determining that the SKVS has reached the predetermined maximum size, closing the SKVS to new key-value pairs;

in response to a predetermined number of SKVSes of the of the plurality of SKVSes becoming closed to new key-value pairs:

merging the predetermined number of SKVSes that have become closed to new key-value pairs into a combined SKVS, wherein merging includes, for each key found within any of the predetermined number of SKVSes, inserting a newest key-value pair using that key from the predetermined number of SKVSes into the combined SKVS and

removing entries from the Cuckoo filter that included identifiers of any of the predetermined number of SKVSes.

3. The method of claim 2 wherein merging the predetermined number of SKVSes that have become closed to new key-value pairs into the combined SKVS includes:

creating the combined SKVS; and

further merging a previous version of the combined SKVS into the combined SKVS.

4. The method of claim 2 ,

wherein the combined SKVS already contained preexisting key-value pairs prior to merging the predetermined number of SKVSes that have become closed to new key-value pairs into the combined SKVS; and

wherein merging the predetermined number of SKVSes that have become closed to new key-value pairs into the combined SKVS includes replacing a preexisting key-value pair within the combined SKVS with a newer key-value pair from one of the predetermined number of SKVSes that have become closed to new key-value pairs.

5. The method of claim 2 wherein the predetermined number is half of a predetermined maximum number of SKVSes permitted within the ordered plurality of SKVSes.

6. The method of claim 2 wherein the method further comprises:

receiving a first request to read a first block of data from the DSS;

in response to receiving the first request:

searching for an entry within the Cuckoo filter keyed by the logical address of that request,

finding a set of entries within the Cuckoo filter keyed by the logical address of that request, each entry of the set of entries including a respective SKVS identifier,

indexing into an SKVS identified by a most recent SKVS identifier found within the set of entries using the logical address of that request, and

obtaining a physical address within the DSS from which to read the first block of data with reference to a metadata entry of the identified SKVS indexed by the logical address of that request;

receiving a second request to read a second block of data from the DSS; and

in response to receiving the second request:

searching for an entry within the Cuckoo filter keyed by the logical address of that request, each entry including a respective SKVS identifier,

failing to find a key-value pair keyed by the logical address of that request within any SKVS identified by any entry within the Cuckoo filter keyed by the logical address of that request,

in response to failing to find the key-value pair, indexing into the combined SKVS using the logical address of that request, and

obtaining a physical address within the DSS from which to read the second block of data with reference to a metadata entry of the combined SKVS indexed by the logical address of that request.

7. The method of claim 6 wherein the method further comprises

receiving a third request to read a third block of data from the DSS; and

in response to receiving the third request, without searching for an entry within the Cuckoo filter keyed by the logical address of that request:

searching for an entry within the a table keyed by the logical address of that request,

finding an entry within the table keyed by the logical address of that request, the entry including an SKVS identifier,

indexing into the SKVS identified by the SKVS identifier using the logical address of that request, and

obtaining a physical address within the DSS from which to read the third block of data with reference to a metadata entry of the identified SKVS indexed by the logical address of that request.

8. A computer program product comprising a non-transitory computer-readable storage medium storing a set of instructions, which, when performed by a computing device, cause the computing device to store block-based metadata in a data storage system (DSS) by:

receiving a request to write a block of data to a logical address of the DSS;

assigning a physical address within the DSS where the block of data is to be stored;

creating a metadata entry for the block of data, the metadata entry including the physical address;

storing a key-value pair within a sorted key-value structure (SKVS) of an ordered plurality of SKVSes, each SKVS having a unique identifier, the key-value pair including the logical address as the key and the metadata entry as the value;

placing an entry within a Cuckoo filter based on the key value, the entry including the identifier of the SKVS in which the key-value pair was stored; and

subsequently accessing the data by:

locating the metadata entry with reference to the Cuckoo filter and

locating the data with reference to the physical address in the metadata entry.

9. The computer program product of claim 8 wherein the set of instructions, when performed by the computing device, further causes the computing device to:

in response to storing the key-value pair within the SKVS, determine that the SKVS has reached a predetermined maximum size;

in response to determining that the SKVS has reached the predetermined maximum size, close the SKVS to new key-value pairs;

in response to a predetermined number of SKVSes of the of the plurality of SKVSes becoming closed to new key-value pairs:

merge the predetermined number of SKVSes that have become closed to new key-value pairs into a combined SKVS, wherein merging includes, for each key found within any of the predetermined number of SKVSes, inserting a newest key-value pair using that key from the predetermined number of SKVSes into the combined SKVS and

remove entries from the Cuckoo filter that included identifiers of any of the predetermined number of SKVSes.

10. The computer program product of claim 9 wherein the predetermined number is half of a predetermined maximum number of SKVSes permitted within the ordered plurality of SKVSes.

11. The computer program product of claim 9 wherein the set of instructions, when performed by the computing device, further causes the computing device to:

receive a first request to read a first block of data from the DSS;

in response to receiving the first request:

search for an entry within the Cuckoo filter keyed by the logical address of that request,

find a set of entries within the Cuckoo filter keyed by the logical address of that request, each entry of the set of entries including a respective SKVS identifier,

index into an SKVS identified by a most recent SKVS identifier found within the set of entries using the logical address of that request, and

obtain a physical address within the DSS from which to read the first block of data with reference to a metadata entry of the identified SKVS indexed by the logical address of that request;

receive a second request to read a second block of data from the DSS; and

in response to receiving the second request:

search for an entry within the Cuckoo filter keyed by the logical address of that request, each entry including a respective SKVS identifier,

fail to find a key-value pair keyed by the logical address of that request within any SKVS identified by any entry within the Cuckoo filter keyed by the logical address of that request,

in response to failing to find the key-value pair, index into the combined SKVS using the logical address of that request, and

obtain a physical address within the DSS from which to read the second block of data with reference to a metadata entry of the combined SKVS indexed by the logical address of that request.

12. A data storage system (DSS) for storing block-based metadata comprising:

a set of persistent storage device that provide a pool of persistent storage; and

a computing device communicatively-connected to the set of persistent storage devices, the computing device being configured to perform the following operations:

receiving a request to write a block of data to a logical address of the DSS;

assigning a physical address within the pool of persistent storage where the block of data is to be stored;

creating a metadata entry for the block of data, the metadata entry including the physical address;

storing a key-value pair within a sorted key-value structure (SKVS) of an ordered plurality of SKVSes, each SKVS having a unique identifier, the key-value pair including the logical address as the key and the metadata entry as the value;

placing an entry within a Cuckoo filter based on the key value, the entry including the identifier of the SKVS in which the key-value pair was stored; and

subsequently accessing the data by:

locating the metadata entry with reference to the Cuckoo filter and

locating the data within the pool of persistent storage with reference to the physical address in the metadata entry.

13. The DSS of claim 12 wherein the computing device is further configured to perform the following operations:

in response to storing the key-value pair within the SKVS, determining that the SKVS has reached a predetermined maximum size;

in response to determining that the SKVS has reached the predetermined maximum size, closing the SKVS to new key-value pairs;

in response to a predetermined number of SKVSes of the of the plurality of SKVSes becoming closed to new key-value pairs:

merging the predetermined number of SKVSes that have become closed to new key-value pairs into a combined SKVS, wherein merging includes, for each key found within any of the predetermined number of SKVSes, inserting a newest key-value pair using that key from the predetermined number of SKVSes into the combined SKVS and

removing entries from the Cuckoo filter that included identifiers of any of the predetermined number of SKVSes.

14. The DSS of claim 13 wherein the predetermined number is half of a predetermined maximum number of SKVSes permitted within the ordered plurality of SKVSes.

15. The DSS of claim 13 wherein the computing device is further configured to perform the following operations:

receiving a first request to read a first block of data from the DSS;

in response to receiving the first request:

searching for an entry within the Cuckoo filter keyed by the logical address of that request,

finding a set of entries within the Cuckoo filter keyed by the logical address of that request, each entry of the set of entries including a respective SKVS identifier,

indexing into an SKVS identified by a most recent SKVS identifier found within the set of entries using the logical address of that request, and

obtaining a physical address within the DSS from which to read the first block of data with reference to a metadata entry of the identified SKVS indexed by the logical address of that request;

receiving a second request to read a second block of data from the DSS; and

in response to receiving the second request:

searching for an entry within the Cuckoo filter keyed by the logical address of that request, each entry including a respective SKVS identifier,

failing to find a key-value pair keyed by the logical address of that request within any SKVS identified by any entry within the Cuckoo filter keyed by the logical address of that request,

in response to failing to find the key-value pair, indexing into the combined SKVS using the logical address of that request, and

obtaining a physical address within the DSS from which to read the second block of data with reference to a metadata entry of the combined SKVS indexed by the logical address of that request.