Methods and systems for insert optimization of tiered data structures

1. A method of improving input/output operation efficiency in a data storage system that includes: a memory controller with one or more processors; a datastore storing one or more tiered data structures; and a volatile memory distinct from the datastore, the volatile memory including a cache and a key-map that is distinct from the one or more tiered data structures stored in the datastore; the method comprising:

at the memory controller operatively coupled with the datastore and the volatile memory:

receiving one or more requests to perform transactions that include a plurality of memory operations to be performed on the datastore;

batching, into a batched set of leaf node operations, memory operations of the plurality of memory operations that are associated with keys in a range of keys assigned to a first leaf node in a tiered data structure of the one or more tiered data structures;

determining whether one or more predefined conditions are satisfied; and

in accordance with a determination that the one or more conditions are satisfied:

locating the first leaf node in the tiered data structure using the key-map to map one of the keys associated with one of the memory operations in the batched set of leaf node operations to a location in the datastore that includes the first leaf node;

storing a copy of the first leaf node in the cache;

modifying the copy of the first leaf node by performing the batched set of leaf node operations so as to obtain one or more modified leaf nodes, wherein modifying the copy of the first leaf node comprises determining whether a set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into two or more leaf nodes; and

writing the one or more modified leaf nodes to one or more locations in the datastore with one or more write operations.

2. The method of claim 1 , wherein:

the datastore comprises a plurality of slabs;

the tiered data structure of the one or more tiered data structures includes a plurality of leaf nodes;

the first leaf node of the tiered data structure includes one or more data objects and is stored in a first slab of the plurality of slabs;

the method further comprises:

in accordance with a determination that the writing comprises writing a plurality of leaf nodes, prior to writing the one or more modified leaf nodes:

allocating two or more contiguous slabs in the datastore for the plurality of leaf nodes; and

assigning keys in the key-map for data objects corresponding to the memory operations in the batched set of leaf node operations to locations of the two or more contiguous slabs; and

writing the one or more modified leaf nodes to one or more locations in the datastore comprises writing the plurality of leaf nodes to the two or more contiguous slabs in the datastore in a single write operation.

3. The method of claim 1 , further comprising:

prior to writing the one or more modified leaf nodes to the one or more locations in the datastore, assigning the keys in the key-map, for data objects corresponding to the memory operations in the batched set of leaf node operations, to the one or more locations in the datastore.

4. The method of claim 1 , further comprising:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations does not require a split of the copy of the first leaf node, processing the set of insert operations in the batched set of leaf node operations by inserting one or more data objects corresponding to the set of insert operations into the copy of the first leaf node, the set of insert operations including one or more insert operations.

5. The method of claim 1 , further comprising:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into two leaf nodes:

splitting the copy of the first leaf node into the two leaf nodes; and

processing the set of insert operations in the batched set of leaf node operations, the set of insert operations including one or more insert operations, the processing including:

inserting data objects associated with the set of insert operations into a particular leaf node of the two leaf nodes; and

in accordance with a determination that the particular leaf node is full, inserting data objects associated with remaining insert operations in the set of insert operations into a second leaf node of the two leaf nodes.

6. The method of claim 1 , further comprising:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into three or more leaf nodes:

splitting the copy of the first leaf node into the three or more leaf nodes; and

processing the set of insert operations in the batched set of leaf node operations, the set of insert operations including two or more insert operations, the processing including:

inserting data objects associated with a first subset of the set of insert operations into a first leaf node of the three or more leaf nodes;

in accordance with a first determination that the first leaf node of the three or more leaf nodes is full, inserting data objects associated with a second subset of insert operations of the set of insert operations, distinct from the first subset of insert operations, into a second leaf node of the three or more leaf nodes; and

in accordance with a second determination that the second leaf node is full, inserting data objects associated with remaining insert operations in the set of insert operations, distinct from the insert operations in the first subset of insert operations and the second subset of insert operations, into remaining leaf nodes of the three or more leaf nodes that are distinct from the first leaf node and the second leaf node.

7. A data storage system, comprising:

a datastore storing one or more tiered data structures;

a volatile memory distinct from the datastore, the volatile memory including a cache and a key-map that is distinct from the one or more tiered data structures stored in the datastore; and

a memory controller with one or more processors and memory storing one or more programs, wherein the one or more programs are configured to be executed by the one or more processors, the one or more programs including instructions for:

receiving one or more requests to perform transactions that include a plurality of memory operations to be performed on the datastore;

batching, into a batched set of leaf node operations, memory operations of the plurality of memory operations that are associated with keys in a range of keys assigned to a first leaf node in a tiered data structure of the one or more tiered data structures;

determining whether one or more predefined conditions are satisfied; and

in accordance with a determination that the one or more conditions are satisfied:

locating the first leaf node in the tiered data structure using the key-map to map one of the keys associated with one of the memory operations in the batched set of leaf node operations to a location in the datastore that includes the first leaf node;

storing a copy of the first leaf node in the cache;

modifying the copy of the first leaf node by performing the batched set of leaf node operations so as to obtain one or more modified leaf nodes, wherein modifying the copy of the first leaf node comprises determining whether a set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into two or more leaf nodes; and

writing the one or more modified leaf nodes to one or more locations in the datastore with one or more write operations.

8. The data storage system of claim 7 , wherein:

the datastore comprises a plurality of slabs;

the tiered data structure of the one or more tiered data structures includes a plurality of leaf nodes;

the first leaf node of the tiered data structure includes one or more data objects and is stored in a first slab of the plurality of slabs;

the one or more programs further include instructions for:

in accordance with a determination that the writing comprises writing a plurality of leaf nodes, prior to writing the one or more modified leaf nodes:

allocating two or more contiguous slabs in the datastore for the plurality of leaf nodes; and

assigning keys in the key-map for data objects corresponding to the memory operations in the batched set of leaf node operations to locations of the two or more contiguous slabs; and

writing the one or more modified leaf nodes to one or more locations in the datastore comprises writing the plurality of leaf nodes to the two or more contiguous slabs in the datastore in a single write operation.

9. The data storage system of claim 7 , the one or more programs further including instructions for:

prior to writing the one or more modified leaf nodes to the one or more locations in the datastore, assigning the keys in the key-map, for data objects corresponding to the memory operations in the batched set of leaf node operations, to the one or more locations in the datastore.

10. The data storage system of claim 7 , the one or more programs further including instructions for:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations does not require a split of the copy of the first leaf node, processing the set of insert operations in the batched set of leaf node operations by inserting one or more data objects corresponding to the set of insert operations into the copy of the first leaf node, the set of insert operations including one or more insert operations.

11. The data storage system of claim 7 , the one or more programs further including instructions for:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into two leaf nodes:

splitting the copy of the first leaf node into the two leaf nodes; and

processing the set of insert operations in the batched set of leaf node operations, the set of insert operations including one or more insert operations, the processing including:

inserting data objects associated with the set of insert operations into a particular leaf node of the two leaf nodes; and

in accordance with a determination that the particular leaf node is full, inserting data objects associated with remaining insert operations in the set of insert operations into a second leaf node of the two leaf nodes.

12. The data storage system of claim 7 , the one or more programs further including instructions for:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into three or more leaf nodes:

splitting the copy of the first leaf node into the three or more leaf nodes; and

processing the set of insert operations in the batched set of leaf node operations, the set of insert operations including two or more insert operations, the processing including:

inserting data objects associated with a first subset of the set of insert operations into a first leaf node of the three or more leaf nodes;

in accordance with a first determination that the first leaf node of the three or more leaf nodes is full, inserting data objects associated with a second subset of insert operations of the set of insert operations, distinct from the first subset of insert operations, into a second leaf node of the three or more leaf nodes; and

in accordance with a second determination that the second leaf node is full, inserting data objects associated with remaining insert operations in the set of insert operations, distinct from the insert operations in the first subset of insert operations and the second subset of insert operations, into remaining leaf nodes of the three or more leaf nodes that are distinct from the first leaf node and the second leaf node.

13. A non-transitory computer-readable storage medium storing one or more programs, the one or more programs comprising instructions which, when executed by a memory controller with one or more processors, cause the memory controller to:

receive one or more requests to perform transactions that include a plurality of memory operations to be performed on a datastore storing one or more tiered data structures;

batch, into a batched set of leaf node operations, memory operations of the plurality of memory operations that are associated with keys in a range of keys assigned to a first leaf node in a tiered data structure of the one or more tiered data structures;

determine whether one or more predefined conditions are satisfied; and

in accordance with a determination that the one or more conditions are satisfied:

locate the first leaf node in the tiered data structure using a key-map to map one of the keys associated with one of the memory operations in the batched set of leaf node operations to a location in the datastore that includes the first leaf node;

store a copy of the first leaf node in the cache;

modify the copy of the first leaf node by performing the batched set of leaf node operations so as to obtain one or more modified leaf nodes, wherein modifying the copy of the first leaf node comprises determining whether a set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into two or more leaf nodes; and

write the one or more modified leaf nodes to one or more locations in the datastore with one or more write operations.

14. The non-transitory computer-readable storage medium of claim 13 , wherein:

the datastore comprises a plurality of slabs;

the tiered data structure of the one or more tiered data structures includes a plurality of leaf nodes;

the first leaf node of the tiered data structure includes one or more data objects and is stored in a first slab of the plurality of slabs;

the instructions further cause the memory controller to:

in accordance with a determination that the writing comprises writing a plurality of leaf nodes, prior to writing the one or more modified leaf nodes:

allocate two or more contiguous slabs in the datastore for the plurality of leaf nodes; and

assign keys in the key-map for data objects corresponding to the memory operations in the batched set of leaf node operations to locations of the two or more contiguous slabs; and

writing the one or more modified leaf nodes to one or more locations in the datastore comprises writing the plurality of leaf nodes to the two or more contiguous slabs in the datastore in a single write operation.

15. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further cause the memory controller to:

prior to writing the one or more modified leaf nodes to the one or more locations in the datastore, assign the keys in the key-map, for data objects corresponding to the memory operations in the batched set of leaf node operations, to the one or more locations in the datastore.

16. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further cause the memory controller to:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations does not require a split of the copy of the first leaf node, process the set of insert operations in the batched set of leaf node operations by inserting one or more data objects corresponding to the set of insert operations into the copy of the first leaf node, the set of insert operations including one or more insert operations.

17. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further cause the memory controller to:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into two leaf nodes:

split the copy of the first leaf node into the two leaf nodes; and

process the set of insert operations in the batched set of leaf node operations, the set of insert operations including one or more insert operations, the processing including:

inserting data objects associated with the set of insert operations into a particular leaf node of the two leaf nodes; and

in accordance with a determination that the particular leaf node is full, inserting data objects associated with remaining insert operations in the set of insert operations into a second leaf node of the two leaf nodes.

18. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions further cause the memory controller to:

in accordance with a determination that the set of insert operations in the batched set of leaf node operations requires a split of the copy of the first leaf node into three or more leaf nodes:

split the copy of the first leaf node into the three or more leaf nodes; and

process the set of insert operations in the batched set of leaf node operations, the set of insert operations including two or more insert operations, the processing including:

inserting data objects associated with a first subset of the set of insert operations into a first leaf node of the three or more leaf nodes;

in accordance with a first determination that the first leaf node of the three or more leaf nodes is full, inserting data objects associated with a second subset of insert operations of the set of insert operations, distinct from the first subset of insert operations, into a second leaf node of the three or more leaf nodes; and

in accordance with a second determination that the second leaf node is full, inserting data objects associated with remaining insert operations in the set of insert operations, distinct from the insert operations in the first subset of insert operations and the second subset of insert operations, into remaining leaf nodes of the three or more leaf nodes that are distinct from the first leaf node and the second leaf node.