N-way merge technique for updating volume metadata in a storage I/O stack
A N-way merge technique efficiently updates metadata in accordance with a N-way merge operation managed by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. The metadata is embodied as mappings from logical block addresses (LBAs) of a logical unit (LUN) accessible by a host to durable extent keys, and is organized as a multi-level dense tree. The mappings are organized such that a higher level of the dense tree contains more recent mappings than a next lower level, i.e., the level immediately below. The N-way merge operation is an efficient (i.e., optimized) way of updating the volume metadata mappings of the dense tree by merging the mapping content of all three levels in a single iteration, as opposed to merging the content of the first level with the content of the second level in a first iteration of a two-way merge operation and then merging the results of the first iteration with the content of the third level in a second iteration of the operation.
1. A system comprising:
a central processing unit (CPU) adapted to execute a storage input/output (I/O) stack;
one or more solid state devices (SSDs) coupled to the CPU; and
a memory coupled to the CPU and configured to store the storage I/O stack, the memory further configured to store one or more dense tree metadata structures wherein each dense tree metadata structure has at least three adjacent levels, each level of each dense tree metadata structure including metadata entries for storing metadata embodied as mappings from offset ranges of a logical unit (LUN) to keys, the storage I/O stack configured to merge the mappings of the adjacent levels in a single merge iteration when at least one of the adjacent levels exceeds an amount of fullness.
2. The system of claim 1 wherein the storage I/O stack is further configured to:
apportion the LUN into one or more volumes; and
partition each volume into one or more regions, wherein each region is represented by a dense tree metadata structure.
3. The system of claim 2 wherein the storage I/O stack is further configured to receive a write request directed towards the LUN, the write request representing an offset range within an offset range space of a region of the LUN.
4. The system of claim 3 wherein the storage I/O stack is further configured to:
employ a sliding window to merge the mappings of the adjacent levels;
advance the sliding window across the offset range space; and
fill the sliding window with the mappings.
5. The system of claim 4 wherein the storage I/O stack is further configured to organize the offset range space as a matrix.
6. The system of claim 5 wherein the matrix has a top-down focus that extends from a highest adjacent level of the dense tree metadata structure to a lowest adjacent level of the dense tree metadata structure.
7. The system of claim 5 wherein the storage I/O stack is configured to advance the sliding window from a starting offset of the matrix to an ending offset of the matrix.
8. The system of claim 5 wherein the storage I/O stack is configured to:
advance the sliding window at defined offset and length intervals; and
examine the mappings of the levels that fill the sliding window at each interval.
9. The system of claim 1 wherein the storage I/O stack is configured to merge the mappings of the adjacent levels for a dense tree metadata structure having complete overlap of each mapping between the adjacent levels.
10. The system of claim 1 wherein the storage I/O stack is configured to merge the mappings of the adjacent levels for a dense tree metadata structure having partial overlap of the mappings between the adjacent levels.
11. The system of claim 10 wherein the partial overlap of the mappings comprises a three-way split overlap of the mappings between the adjacent levels.
12. A method comprising:
storing one or more dense tree metadata structures in a memory coupled to a processor of a storage system, wherein each dense tree metadata structure has at least three adjacent levels, each level of each dense tree metadata structure including metadata entries for storing metadata embodied as mappings from offset ranges of a logical unit (LUN) to keys; and
merging the mappings of the adjacent levels in a single merge iteration when at least one of the adjacent levels exceeds an amount of fullness.
13. The method of claim 12 further comprising:
apportioning the LUN into one or more volumes; and
partitioning each volume into one or more regions, wherein each region is represented by a dense tree metadata structure.
14. The method of claim 13 further comprising:
receiving a write request directed towards the LUN, the write request representing an offset range within an offset range space of a region of the LUN.
15. The method of claim 14 further comprising:
employing a sliding window to merge the mappings of the adjacent levels;
advancing the sliding window across the offset range space; and
filling the sliding window with the mappings.
16. The method of claim 15 further comprising:
organizing the offset range space as a matrix.
17. The method of claim 16 wherein the matrix has a top-down focus that extends from a highest adjacent level of the dense tree metadata structure to a lowest adjacent level of the dense tree metadata structure.
18. The method of claim 16 further comprising:
advancing the sliding window from a starting offset of the matrix to an ending offset of the matrix.
19. The method of claim 16 further comprising:
advancing the sliding window at defined offset and length intervals; and
examining the mappings of the levels that fill the sliding window at each interval.
20. A non-transitory computer readable medium including program instructions for execution on a processor of a storage system, the program instructions configured to:
store one or more dense tree metadata structures in a memory of the storage system, wherein each dense tree metadata structure has at least three adjacent levels, each level of each dense tree metadata structure including metadata entries for storing metadata embodied as mappings from offset ranges of a logical unit (LUN) to keys; and
merge the mappings of the adjacent levels in a single merge iteration when at least one of the adjacent levels exceeds an amount of fullness.