| 摘要 |
A three-way merge technique efficiently updates metadata in accordance with a three-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 three-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 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 data entries of a metadata structure; merging the first, second and third data entries to form a fourth data entry, the fourth data entry representing a merge of the first, second and third offset ranges, the second and third data entries stored on an array of storage devices attached to the storage system; and storing the fourth data entry on the storage array. |
