×

Method and apparatus for efficiently merging, storing and retrieving incremental data

  • US 9,690,790 B2
  • Filed: 02/20/2008
  • Issued: 06/27/2017
  • Est. Priority Date: 03/05/2007
  • Status: Active Grant
First Claim
Patent Images

1. A method comprising:

  • receiving a request for a plurality of pages in a set of incrementally stored data as of a desired time;

    wherein the set of incrementally stored data comprises a base archive and a plurality of snapshots;

    wherein each snapshot corresponds to a distinct epoch of a plurality of epochs, each epoch comprising a time period after creation of the base archive;

    wherein each snapshot comprises;

    a single revised version of each page of data that was changed in the distinct epoch; and

    an index that indicates, for each page that was changed in the distinct epoch, an identity of the page and a location of the single revised version of the page; and

    going from most-recent epoch to least-recent epoch, searching the index of each snapshot corresponding to an epoch later than creation of the base archive and no later than the desired time to identify a location of a most recent version of each page of data that was changed during the epoch;

    storing, in a hash table, each location of each most recent version identified in the searching step, wherein the hash table utilizes a hash function to assign each page number to a unique value, wherein the unique value determines data associated with each said page number;

    searching the hash table for an entry corresponding to a desired page;

    if an entry corresponding to the desired page is found, retrieving the data from the snapshot corresponding to the epoch identified by the entry;

    if an entry is not found in the hash table, retrieving the data from the base archive; and

    wherein the desired time is later than the creation of the base archive and wherein data in each revised version of each page in a snapshot is later than the data in each corresponding page of the base archive.

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