Sampling fingerprints in bins

A system comprising:

• persistent storage to store a fingerprint index divided into a plurality of fingerprint index sections, the plurality of fingerprint index sections being part of respective bins of a plurality of bins;
• a memory to store buffers that are part of the respective bins of the plurality of bins;
• a processor;
• and
• a storage medium storing instructions executable on the processor to:
• compute fingerprints for incoming data units, wherein each fingerprint of the fingerprints comprises a bin selector portion to select a respective bin of the plurality of bins;
• select, based on values of the bin selector portions in the fingerprints and an adaptive sampling indication, a first subset of the fingerprints to sample, the adaptive sampling indication indicating a proportion of the fingerprints to be added to the fingerprint index;
• select, based on the values of the bin selector portions in the fingerprints and the adaptive sampling indication, a second subset of the fingerprints to not sample;
• add fingerprint index entries corresponding to the first subset of the fingerprints to a respective subset of the plurality of bins, wherein adding a fingerprint index entry to a bin of the respective subset of the plurality of bins comprises adding the fingerprint index entry to the buffer of the bin;
• merge the fingerprint index entries added to the respective subset of the plurality of bins from one or more buffers of the respective subset of the plurality of bins into respective fingerprint index sections of the fingerprint index;
• merge the fingerprint index entries added to the respective subset of the plurality of bins from one or more buffers of the respective subset of the plurality of bins into the fingerprint index in the persistent storage;
• and
• not add fingerprint index entries corresponding to the second subset of the fingerprints to the plurality of bins, wherein the fingerprint index entries corresponding to the second subset of the fingerprints that are not added to the plurality of bins are not merged from the buffers of the plurality of bins into the fingerprint index.

A method performed by a system comprising a hardware processor, comprising:

• setting a value of an adaptive sampling indication that indicates a proportion of fingerprints computed based on data units to be added to a fingerprint index stored in persistent storage, wherein the fingerprint index comprises a plurality of fingerprint index sections that are part of respective bins of a plurality of bins, and each bin of the plurality of bins further comprising a respective buffer contained in a memory, wherein each fingerprint of the fingerprints comprises a bin selector portion to select a respective bin of the plurality of bins;
• comparing a value of a bin selector portion of a first fingerprint for a first data unit and a value of a bin selector portion of a second fingerprint for a second data unit to the value of the adaptive sampling indication;
• determining based on the comparing whether to add a fingerprint index entry containing the first fingerprint to a first bin to which the value of the bin selector portion of the first fingerprint maps;
• in response to determining based on the comparing to add the fingerprint index entry containing the first fingerprint to the first bin, add the fingerprint index entry to a buffer of the first bin;
• merge the fingerprint index entry from the buffer of the first bin into the fingerprint index stored in the persistent storage;
• and
• determining based on the comparing to not add a fingerprint index entry containing the second fingerprint to the plurality of bins, wherein the fingerprint index entry containing the second fingerprint that is not added to the plurality of bins is not merged from the buffers of the plurality of bins into the fingerprint index stored in the persistent storage.