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

Claim 0:
1. A method for reverse range lookup in an ordered data structure of keys associated with one or more snapshots in a snapshot hierarchy, wherein each key comprises a logical block address (LBA) and a snapshot identifier (ID) of one of the one or more snapshots, the method comprising:
receiving a read request defining a range of LBAs selected for querying the ordered data structure, wherein the range of LBAs includes a start LBA and a last LBA, wherein the keys in the ordered data structure are in an order from smallest LBA to largest LBA, wherein in the order, keys having a same LBA are ordered from smallest snapshot ID to largest snapshot ID;
traversing 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;

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