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

Claim 15:
16. A computer system comprising:
a common storage system; and
a plurality of host computer systems connected to the common storage system, wherein each host computer system is programmed to:
track, via one or more processors, write operations to the common storage system the write operations comprising a first write operation; and
perform a deduplication operation on storage blocks associated with the write operations using a data structure that is stored in the common storage system to find duplicate blocks, wherein the data structure comprises:
a hash index that is divided into a plurality of pages, each of the plurality of pages including one or more entries of the hash index, each entry of the hash index containing (a) a hash value of a block stored in the common storage system and (b) a file pointer associated with the block, wherein the entries of the hash index are maintained in sorted order according to the hash values of the entries of the hash index; and

wherein performing the deduplication operation on storage blocks associated with the write operations by using the data structure comprises:
generating a first hash value of a data block of the first write operation;
associating the first hash value with a first file pointer derived from the first write operation;
determining the first hash value is not in the hash index;
locating an entry in the one or more jump indexes including a second hash value associated with the first hash value;
locating a first page of the hash index using a first pointer included in the entry in the one or more jump indexes; and
adding a new entry to the first page of the hash index, the new entry containing the first hash value and the first file pointer.