Patent ID: 11880584
Assignee: VMWARE LLC
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 6:
7. A system comprising:
one or more processors; and
at least one memory, the one or more processors and the at least one memory configured to:
receive a read request defining a range of LBAs selected for querying an ordered data structure of keys associated with one or more snapshots in a snapshot hierarchy, wherein:
each key in the ordered data structure comprises a logical block address (LBA) and a snapshot identifier (ID) of one of the one or more snapshots,
the keys in the ordered data structure are in an order from smallest LBA to largest LBA,
in the order, keys having a same LBA are ordered from smallest snapshot ID to largest snapshot ID, and
the range of LBAs includes a start LBA and a last LBA; traverse the ordered data structure in reverse of the order until a first key is located that:
has a first LBA that is less than or equal to the last LBA; and
has a first snapshot ID that is less than or equal to the largest snapshot ID among snapshot IDs of the one or more snapshots in the snapshot hierarchy;

add an extent corresponding to the located first key to an extent result list; and
return the extent result list having, at least the extent corresponding to the located first key in response to the read request.