×

Self-referential deduplication

  • US 9,075,532 B1
  • Filed: 04/23/2010
  • Issued: 07/07/2015
  • Est. Priority Date: 04/23/2010
  • Status: Active Grant
First Claim
Patent Images

1. A method comprising:

  • deduplicating data, wherein the deduplicating comprises;

    calculating a first value as a function of data in an nth data block of a backup copy comprising a number, z, of data blocks, where n is a number from 1 to z;

    comparing the first value with each of a plurality of values in a plurality of entries, respectively, of a first data structure, the plurality of entries comprising a plurality of pointers, respectively, that identify a plurality of locations, respectively, where a plurality of data blocks, respectively, are physically stored in a storage system;

    if the first value compares equally to a value contained in one of the plurality of entries of the first data structure, then a copy of the nth data block was previously stored in the storage system and as a result the method further comprises adding a pointer to the one entry to an nth entry of a second data structure, wherein the pointer identifies where the copy of the nth data block is stored in the storage system;

    if the first value does not compare equally with any value contained in the plurality of entries of the first data structure, (1) storing the nth data block in the storage system, and (2) adding a first pointer to the nth entry of the second data structure, wherein the first pointer identifies where the nth data block is stored in the storage system;

    storing the second data structure in the storage system after adding the pointer or the first pointer to the nth entry;

    wherein the first pointer enables a computer system to retrieve the nth data block from the storage system without referencing the first data structure during data reflation, andwherein the pointer enables the computer system to retrieve the copy of the nth data block from the storage system without referencing the first data structure during reflation.

View all claims
  • 7 Assignments
Timeline View
Assignment View
    ×
    ×