Block-level single instancing

Abstract

Described in detail herein are systems and methods for single instancing blocks of data in a data storage system. For example, the data storage system may include multiple computing devices (e.g., client computing devices) that store primary data. The data storage system may also include a secondary storage computing device, a single instance database, and one or more storage devices that store copies of the primary data (e.g., secondary copies, tertiary copies, etc.). The secondary storage computing device receives blocks of data from the computing devices and accesses the single instance database to determine whether the blocks of data are unique (meaning that no instances of the blocks of data are stored on the storage devices). If a block of data is unique, the single instance database stores it on a storage device. If not, the secondary storage computing device can avoid storing the block of data on the storage devices.

We claim: 
     
         1 . A system for restoring a file from a storage device, the system comprising:
 at least one processor;   at least one data storage device;   means for receiving a request for a file, wherein the file is archived as one or more data blocks on the storage device;   means for determining a first file and a first offset within the first file corresponding to the requested file,
 wherein the first file stores data blocks that are not eligible for single instancing, and 
 wherein the first file also stores at least one data structure that includes references to data blocks that are eligible for single instancing; 
   means for accessing the first file at the first offset;   means for determining if a first data block beginning at the first offset includes at least a first portion of the requested file;   means for obtaining the first data block from the first file when the first data block beginning at the first offset includes at least the first portion of the requested file; and   means for providing the requested file to a client device.   
     
     
         2 . The system of  claim 1 , further comprising:
 means for storing in the data structure of the first file a reference to the already stored instance of the first data block if an instance of a second data block is received when the first data block has already been stored on the storage device; and   means for storing the second data block to a third file if the second data block is received when an instance of the second data block has not already been stored on the storage device,
 wherein the third file stores only a single instance of each data block, 
 wherein the third file stores data blocks from more than one file stored at one or more computing client devices, and 
 wherein the third file includes multiple portions available for storing blocks, and 
 wherein the second data block is stored in one or more portions. 
   
     
     
         3 . The system of  claim 1 , further comprising:
 means for determining if data beginning at the first offset includes a reference to a second data block in a second file that includes at least a second portion of the requested file;   means for accessing the second file when the data beginning at the first offset includes the reference to the second data block in the second file; and   means for obtaining the second data block from the second file.   
     
     
         4 . The system of  claim 3 , wherein the first file is located within a first folder, and the second file is located within a second folder. 
     
     
         5 . The system of  claim 1 , further comprising:
 determining a logical container corresponding to the requested file; and   analyzing the logical container to determine the first file.   
     
     
         6 . The system of  claim 1 , further comprising:
 accessing an index file associated with the first file, wherein the index file stores, for at least some of the one or more data blocks, a single flag indicating whether the stored block of data is referred to in one or more metadata files on the one or more storage devices; and   analyzing the index file to determine the first offset within the first file.   
     
     
         7 . A computer-readable storage medium whose contents cause a computing system to perform a method of restoring a file from a storage device, the method comprising:
 receiving a request for a file, wherein the file is archived as one or more data blocks on the storage device;   determining a first file and a first offset within the first file corresponding to the requested file;   accessing the first file at the first offset;   determining if a first data block beginning at the first offset includes at least a first portion of the requested file;   when the first data block beginning at the first offset includes at least the first portion of the requested file, obtaining the first data block from the first file;   when a second data block that includes at least a second portion of the requested file exists, obtaining the second data block; and   providing the requested file to a client device.   
     
     
         8 . The computer-readable storage medium of  claim 7 , wherein the method further comprises:
 determining if data beginning at the first offset includes a reference to a second data block in a second file that includes at least a second portion of the requested file; and   when the data beginning at the first offset includes the reference to the second data block in the second file, accessing the second file; and
 obtaining the second data block from the second file. 
   
     
     
         9 . The computer-readable storage medium of  claim 7 , wherein the method further comprises:
 when a second portion of the requested file is in a second file, determining a second offset within the second file at which the second data block is located; and   obtaining the second data block.   
     
     
         10 . The computer-readable storage medium of  claim 7 , wherein the first file is located within a first folder, and the second file is located within a second folder. 
     
     
         11 . The computer-readable storage medium of  claim 7 , wherein the method further comprises:
 determining a logical container corresponding to the requested file; and   analyzing the logical container to determine the first file.   
     
     
         12 . The computer-readable storage medium of  claim 7 , wherein the method further comprises:
 accessing an index file associated with the first file; and   analyzing the index file to determine the first offset within the first file.   
     
     
         13 . A method of restoring a file from a storage device, the method comprising:
 receiving a request for a file, wherein the file is archived as one or more data blocks on the storage device;   determining a first file and a first offset within the first file corresponding to the requested file;   accessing the first file at the first offset;   determining if a first data block beginning at the first offset includes at least a first portion of the requested file;   when the first data block beginning at the first offset includes at least the first portion of the requested file, obtaining the first data block from the first file;   when a second data block that includes at least a second portion of the requested file exists, obtaining the second data block; and   providing the requested file to a client device.   
     
     
         14 . The method of  claim 13 , wherein the method further comprises:
 determining if data beginning at the first offset includes a reference to a second data block in a second file that includes at least a second portion of the requested file; and   when the data beginning at the first offset includes the reference to the second data block in the second file, accessing the second file; and   obtaining the second data block from the second file.   
     
     
         15 . The method of  claim 13 , wherein the method further comprises:
 when a second portion of the requested file is in a second file, determining a second offset within the second file at which the second data block is located; and   obtaining the second data block.   
     
     
         16 . The method of  claim 13 , wherein the first file is located within a first folder, and the second file is located within a second folder. 
     
     
         17 . The method of  claim 13 , wherein the method further comprises:
 determining a logical container corresponding to the requested file; and   analyzing the logical container to determine the first file.   
     
     
         18 . The method of  claim 13 , wherein the method further comprises:
 accessing an index file associated with the first file; and   analyzing the index file to determine the first offset within the first file.   
     
     
         19 . The method of  claim 13 , wherein determining a first file and a first offset within the first file corresponding to the requested file includes analyzing an index file to determine a volume folder and chunk folder that include the data blocks associated with the requested file. 
     
     
         20 . The method of  claim 13 , wherein determining a first file and a first offset within the first file corresponding to the requested file includes determining a volume folder and chunk folder corresponding to the requested data.