Reducing hash collisions in large scale data deduplication
US10762051B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 30, 2018 |
| Grant date | Sep 1, 2020 |
| Priority date | — |
| Expiry date | Feb 3, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/137
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system obtains a first data chunk and a second data chunk of a plurality of data chunks associated with a first data snapshot of a computing system. A hash record is assigned to a data chunk, and used to create a hash value that is written to a first lookup table. The hash function is selected from a plurality of hash functions. The system creates a first archive by saving the plurality of data chunks and the first lookup table to a datastore. The system writes a second hash record for the individual data chunks to a second lookup table using the same hash functions that were used for the first lookup table. Dissimilar hash values between the first lookup table and the second lookup table are identified, and a second archive that includes data chunks with different data from the corresponding data chunks from the first data snapshot is created based on the data chunks with the dissimilar hash values.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.