System and method for removing overlapping ranges from a flat sorted data structure
US8868520B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 1, 2012 |
| Grant date | Oct 21, 2014 |
| Priority date | — |
| Expiry date | Mar 20, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/1752
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system and method efficiently removes ranges of entries from a flat sorted data structure, such as a fingerprint database, of a storage system. The ranges of entries represent fingerprints that have become stale, i.e., are not representative of current states of corresponding blocks in the file system, due to various file system operations such as, e.g., deletion of a data block without overwriting its contents. A deduplication module performs an attributes intersect range calculation (AIRC) procedure on the stale fingerprint data structure to compute a set of non-overlapping and latest consistency point (CP) ranges. The output from the AIRC procedure, i.e., the set of non-overlapping and latest CP ranges, is then used to remove stale fingerprints associated with that deleted block (as well as each other deleted data block) from the fingerprint database.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.