Generating snapshots of a key-value index

1. A computer implemented method, comprising:

storing key-value pairs in an index in persistent storage, wherein:

indirect nodes of the index include pointers, wherein each pointer identifies an index portion and is associated with a generation identifier for the identified index portion, wherein the index comprises a plurality of snapshots associated with a plurality of generations;

a first indirect node includes a first pointer to a child node, and the first pointer is associated with a first generation identifier for the child node; and

the first indirect node includes a second pointer to a buffer chunk stored in the first indirect node, and the second pointer includes a second generation identifier for the buffer chunk;

receiving a request to read data of a particular snapshot of the index, wherein the particular snapshot is associated with a particular generation of the plurality of generations;

in response to the request, performing a traversal starting from a particular root node associated with the particular generation; and

providing the requested data based on the traversal.

2. The computer implemented method of claim 1 , wherein the traversal is performed using the generation identifiers associated with the pointers of the indirect nodes.

3. The computer implemented method of claim 1 , wherein the particular snapshot includes:

a first set of key-value pairs associated with the particular generation; and

a second set of key-value pairs associated with a different generation, wherein the different generation is older than the particular generation, wherein the second set of key-value pairs is shared by the particular snapshot and a different snapshot.

4. The computer implemented method of claim 1 , wherein the first generation identifier and the second generation identifier are associated with different generations.

5. The computer implemented method of claim 1 , wherein:

the first indirect node is associated with the second generation identifier;

the first indirect node is included in a first tree structure, the first tree structure having a first root node associated with the second generation identifier; and

the first indirect node is also included in a second tree structure, the second tree structure having a second root node associated with a third generation identifier, wherein the second generation identifier and the third generation identifier are associated with different generations.

6. The computer implemented method of claim 1 , wherein each key-value pair in the index is associated with a respective generation identifier.

7. The computer implemented method of claim 1 , wherein each of the pointers includes the associated generation identifier.

8. The computer implemented method of claim 7 , wherein, for each of the pointers, the associated generation identifier is included in a field of the pointer.

9. A non-transitory machine-readable medium storing instructions that upon execution cause a processor to:

store key-value pairs in an index in persistent storage, wherein:

indirect nodes of the index include pointers, wherein each pointer identifies an index portion and is associated with a generation identifier for the identified index portion, wherein the index comprises a plurality of snapshots associated with a plurality of generations;

a first indirect node includes a first pointer to a child node, and the first pointer is associated with a first generation identifier for the child node; and

the first indirect node includes a second pointer to a buffer chunk stored in the first indirect node, wherein the second pointer is associated with a second generation identifier for the buffer chunk;

receive a request to read data of a particular snapshot of the index, wherein the particular snapshot is associated with a particular generation of the plurality of generations;

in response to the request, perform a traversal starting from a particular root node associated with the particular generation; and

provide the requested data based on the traversal.

10. The non-transitory machine-readable medium of claim 9 , wherein the traversal is performed using the generation identifiers associated with the pointers of the indirect nodes.

11. The non-transitory machine-readable medium of claim 9 , wherein the particular snapshot includes:

a first set of key-value pairs associated with the particular generation; and

a second set of key-value pairs associated with a different generation, wherein the different generation is older than the particular generation, wherein the second set of key-value pairs is shared by the particular snapshot and a different snapshot.

12. The non-transitory machine-readable medium of claim 9 , wherein:

the first indirect node is associated with the second generation identifier;

the first indirect node is included in a first tree structure, the first tree structure having a first root node associated with the second generation identifier; and

the first indirect node is included in a second tree structure, the second tree structure having a second root node associated with a third generation identifier, wherein the second generation identifier and the third generation identifier are associated with different generations.

13. The non-transitory machine-readable medium of claim 9 , wherein each of the pointers includes the associated generation identifier.

14. The non-transitory machine-readable medium of claim 13 , wherein, for each of the pointers, the associated generation identifier is one portion of an address specified by the pointer.

15. A storage system comprising:

a processor comprising a plurality of processing engines; and

a machine-readable storage storing instructions, the instructions executable by the processor to:

store key-value pairs in an index in persistent storage, wherein:

indirect nodes of the index include pointers, wherein each pointer identifies an index portion and is associated with a generation identifier for the identified index portion, wherein the index comprises a plurality of snapshots associated with a plurality of generations;

a first indirect node includes a first pointer to a child node, and the first pointer is associated with a first generation identifier for the child node; and

the first indirect node includes a second pointer to a buffer chunk stored in the first indirect node, and wherein the second pointer is associated with a second generation identifier for the buffer chunk;

receive a request to read data of a particular snapshot of the index, wherein the particular snapshot is associated with a particular generation of the plurality of generations;

in response to the request, perform a traversal starting from a particular root node associated with the particular generation; and

provide the requested data based on the traversal.

16. The storage system of claim 15 , wherein the traversal is performed using the generation identifiers associated with the pointers of the indirect nodes.

17. The storage system of claim 15 , wherein the particular snapshot includes:

a first set of key-value pairs associated with the particular generation; and

a second set of key-value pairs associated with a different generation, wherein the different generation is older than the particular generation, wherein the second set of key-value pairs is shared by the particular snapshot and a different snapshot.

18. The storage system of claim 15 , wherein:

the first indirect node is associated with the second generation identifier;

the first indirect node is included in a first tree structure, the first tree structure having a first root node associated with the second generation identifier; and

the first indirect node is included in a second tree structure, the second tree structure having a second root node associated with a third generation identifier, wherein the second generation identifier and the third generation identifier are associated with different generations.

19. The storage system of claim 15 , wherein each of the pointers includes the associated generation identifier.

20. The computer implemented method of claim 19 , wherein, for each of the pointers, the associated generation identifier is included in a field of the pointer.