Patent ID: 8392384

Claim:
A method for use in a deduplication storage system, the method comprising: generating a new fingerprint corresponding to a received data segment; and searching for a matching fingerprint to the new fingerprint in a first index; in response to determining the first index does not include a match for the new fingerprint: storing the new data segment in a first container of a first storage device; and entering a binary sampling mode for the first index in response to determining the first storage device has less than a given capacity, said binary sampling mode being configured to reduce a number of entries in the first index which are currently categorized as samples by re-categorizing as non-samples one or more existing entries in the first index which are currently categorized as samples; wherein the binary sampling mode comprises: categorizing a first subset of a plurality of entries of the first index as samples; categorizing a second subset of the plurality of entries of the first index as non-samples; wherein entries categorized as samples are not eligible for replacement in the first index, and entries categorized as non-samples are eligible for replacement in the first index.