Patent ID: 8396841

Claim:
A method for performing multi-level deduplication, the method comprising: maintaining a first fingerprint index configured to store fingerprints for data stored in a first client, a second fingerprint index configured to store fingerprints for data stored in a second client, and a common fingerprint index configured to store fingerprints for data stored in both the first client and the second client; generating a first fingerprint for a first data segment, wherein the first data segment corresponds to the first client; querying the first fingerprint index to determine if there is a matching fingerprint to the first fingerprint; in response to determining the first fingerprint index does not contain a matching fingerprint to the first fingerprint: creating a new entry for the first fingerprint in the first fingerprint index; storing the first data segment in a container in a storage device; querying the common fingerprint index to determine if there is a matching fingerprint to the first fingerprint; in response to determining the common fingerprint index does not contain a matching fingerprint to the first fingerprint, creating a new entry for the first fingerprint in the common fingerprint index; in response to determining the common fingerprint index contains a matching fingerprint to the first fingerprint: storing a reference to the matching fingerprint from the first fingerprint; and deleting the first data segment.