N-way merge technique for updating volume metadata in a storage I/O stack
First Claim
1. A method comprising:
- receiving first, second and third write requests directed towards a logical unit (LUN), the first, second and third write requests having respective first, second and third data, the first, second and third write requests representing respective first, second and third offset ranges of the LUN, the second and third offset ranges overlapping the first offset range, the write requests processed at a storage system having a memory;
associating first, second and third keys with the respective first, second and third data;
storing the first, second and third keys in respective first, second and third entries of a metadata structure;
merging the first, second and third entries to form a fourth entry, the fourth entry representing a merge of the first, second and third offset ranges, the second and third entries stored on an array of storage devices attached to the storage system; and
storing the fourth entry on the storage array.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
-
Citations
20 Claims
-
1. A method comprising:
-
receiving first, second and third write requests directed towards a logical unit (LUN), the first, second and third write requests having respective first, second and third data, the first, second and third write requests representing respective first, second and third offset ranges of the LUN, the second and third offset ranges overlapping the first offset range, the write requests processed at a storage system having a memory; associating first, second and third keys with the respective first, second and third data; storing the first, second and third keys in respective first, second and third entries of a metadata structure; merging the first, second and third entries to form a fourth entry, the fourth entry representing a merge of the first, second and third offset ranges, the second and third entries stored on an array of storage devices attached to the storage system; and storing the fourth entry on the storage array. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method comprising:
-
receiving a number of write requests directed towards a logical unit (LUN),each write request having respective data and representing respective offset ranges of the LUN, wherein the number of write requests is greater than three, the write requests processed at a storage system having a memory; associating the respective data of each write request with a respective key; storing the respective key of the respective data in a respective entry of a metadata structure, wherein the metadata structure includes a plurality of levels, wherein each entry is associated with a different level of the plurality of levels; merging the respective entries to form a merged entry, the merged entry representing a merge of all the respective offset ranges, the plurality of entries stored on an array of storage devices attached to the storage system; and storing the merged entry on a lowest level of the plurality of levels of the metadata structure.
-
-
11. A system comprising:
-
a storage system having a memory connected to a processor via a bus; a storage array coupled to the storage system; and a storage I/O stack executing on the processor of the storage system, the storage I/O configured to; receive first, second and third write requests directed towards a logical unit (LUN), the first, second and third write requests having respective first, second and third data, the first, second and third write requests representing respective first, second and third offset ranges of the LUN, the second and third offset ranges overlapping the first offset range, the write requests processed at a storage system having a memory; associate first, second and third keys with the respective first, second and third data; store the first, second and third keys in respective first, second and third entries of a metadata structure; merge the first, second and third entries to form a fourth entry, the fourth entry representing a merge of the first, second and third offset ranges, the second and third entries stored on an array of storage devices attached to the storage system; and store the fourth entry on the storage array. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification