Method and system for shrinking a set of data using a differential snapshot, a watch-list structure along with identifying and retaining updated blocks

A method for performing a snapshot-based online backup with shrinking a set of data included into a snapshot, the method comprising:

• providing a writable storage for storing blocks of data;
• providing a backup storage for storing data backup;
• providing snapshot management means used for controlling a differential snapshot of blocks of said writable storage, said differential snapshot comprising:
• a retention container used for storing a copy of any of said blocks of data;
• a watch-list structure identifying blocks of said writable storage remaining unchanged since a moment of creation of said snapshot;
• a retention-list structure storing associations of references to updated blocks of said writable storage with references to original copies of updated blocks stored in said retention container;
• a space allocation list structure identifying unused space in said retention container;
• a snapshot shrinking subroutine used for removing block identification data from said watch-list and removing associations data from said retention-list, said subroutine taking a structure specifying blocks of storage as input data, said subroutine comprising instructions for executing the following steps on a computer:
• removing references to blocks specified by input data from said watch-list;
• adding locations referenced by associations from said retention-list, which include references to blocks specified by input data, into said space allocation list;
• releasing retained data from said retention container;
• removing associations, which include references to blocks specified by input data, from said retention-list;
• creating a differential snapshot of said writable storage;
• compiling a backup-list of blocks required to back up by analyzing file allocation on said snapshot;
• and
• performing a backup of portions of blocks included into said backup-list until said backup-list becomes empty, the step of performing a backup comprising by iteratively executing at least the following steps:
• reading a portion of blocks from said snapshot into a memory buffer for further processing and storing on said backup storage;
• invoking said snapshot shrinking routine with specifying a structure identifying locations of blocks included into said portion as input data;
• removing references to blocks included into said portion from said backup list.

A backup system for performing a snapshot-based online backup, the system comprising:

• a writable storage for storing blocks of data;
• a backup storage for storing data backup;
• a computer system controlling said writable storage device and said backup storage, said computer system comprising:
• snapshot management means for controlling a differential snapshot of data blocks of said writable storage system, said differential snapshot comprising:
• a retention container used for storing a copy of any of said blocks of data;
• a watch-list structure identifying blocks of said writable storage remaining unchanged since a moment of creation of said snap shot;
• a retention-list structure storing associations of references to updated blocks of said writable storage with references to original copies of updated blocks stored in said retention container,
• a space allocation list structure identifying unused space in said retention container;
• means for enabling access to data stored on a snapshot;
• means for shrinking a set of data included to said snapshot, said means for shrinking operable to perform the steps of:
• removing references to specified blocks from said watch-list;
• adding locations referenced by associations stored in said retention-list which include references to said specified blocks into said space allocation list;
• releasing retained data from said retention container;
• and
• removing associations stored in said retention-list which include references to said specified blocks;
• means for performing a snapshot-based online backup with shrinking a set of data included to a snapshot during backup operation, said means for performing a snapshot-based online backup operable, in an interactive manner, to:
• read a portion of blocks from said snapshot into a memory buffer for further processing and storing on a backup store;
• invoke said means for shrinking a set of data included to a snapshot with specifying locations of blocks from portion of blocks as input data.