Time indexed file system

• US 8,060,481 B1
• Filed: 05/23/2006
• Issued: 11/15/2011
• Est. Priority Date: 06/30/2005
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Bhanjois, Bhimsen, Vajgel, Peter, Harmer, Craig K., Colgrove, John A., Borate, Milind
• Primary Examiner(s): LEWIS, ALICIA M
• Application Number:
  US11/439,302
• Time in Patent Office: 2,002 Days
• Field of Search: None
• US Class Current: 707/695
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files

Abstract

A method and mechanism for managing a time-indexed block map in a file system configured to store multiple versions of file data. A file system includes inodes or other structures corresponding to files in the system. Responsive to creating a file, one or more blocks are allocated for use in storing the file data. A block map is maintained for the file and is updated to include an identification of the blocks storing the file data and a timestamp corresponding to the stored data. In response to creating a file, data corresponding block map is maintained. In addition, a new entry is created in the block map which identifies the newly allocated blocks. Further, an entry of the block map is updated to (i) identify the particular blocks to which the write was directed and (ii) include a timestamp corresponding to the time of the write.

Claims

1. A method for managing data in a file system, the method comprising:

allocating by a computing device one or more blocks for use in storing data corresponding to a file;

storing the file data in the blocks;

updating an inode corresponding to the file responsive to said allocating, the inode including attributes and an extent map corresponding to the file, the inode being configured to simultaneously identify multiple versions of the file corresponding to multiple points in time, wherein the update includes adding data to the inode which identifies the one or more blocks;

in response to detecting a write to the file, subsequent to said updating, is directed to particular blocks of the one or more blocks;

allocating one or more new blocks for use in storing data which corresponds to the file;

creating a new entry in the extent map of the inode which identifies the new blocks, said new entry being simultaneously maintained along with entries of the one or more entries in the extent map;

updating a first entry of the extent map to identify the particular blocks to which the write was directed and a time at which the write occurred;

wherein said extent map simultaneously maintains entries for multiple updates which have been made to the file at multiple points in time, and wherein each entry of the extent map includes a key comprising an offset to corresponding data within the file and a timestamp associated with a time of an update of a corresponding extent map entry;

in response to detecting the write corresponds to one or more blocks of an original extent;

splitting the original extent at a first block corresponding to the beginning of the write; and

splitting the original extent at a last block corresponding to the end of the write.

2. The method as recited in claim 1, wherein the file system does not store multiple copies of a given block for a particular file which are common to multiple versions of the particular file.

3. The method as recited in claim 2, wherein the first entry is the new entry, and wherein the method further comprises storing data corresponding to the write in the new blocks.

4. The method as recited in claim 2, wherein the first entry is an entry corresponding to at least one of the particular blocks, and wherein the method further comprises:

copying the data from the particular blocks to the new blocks;

storing data corresponding to the write in the particular blocks; and

updating the new entry to identify at least one of the new blocks, and include an original timestamp corresponding to the data stored in a corresponding block.

5. The method as recited in claim 1, wherein the first entry is the new entry and the new blocks comprise a new extent, and wherein the method further comprises storing data corresponding to the write in the new extent.

6. The method as recited in claim 1, wherein the new blocks comprise a new extent and the first entry is an entry corresponding to at least one of the particular blocks, and wherein the method further comprises:

copying the data from the particular blocks to the new extent;

storing data corresponding to the write in the particular blocks; and

updating the new entry to identify the new extent, and include an original timestamp corresponding to the data stored in a corresponding block.

7. The method as recited in claim 1, wherein the extent map is stored in a B-tree, wherein each node of the B-tree includes a key comprising an offset and a timestamp associated with a time of an update of a corresponding extent map entry.

8. A computing system comprising:

a computing device; and

a storage device comprising a plurality of allocable blocks for storing data;

wherein the computing device is configured to;

allocate one or more of the blocks for use in storing data corresponding to a file;

store the file data in the blocks;

update an inode corresponding to the file responsive to said allocating, the inode including attributes and an extent map corresponding to the file, the inode being configured to simultaneously identify multiple versions of the file corresponding to multiple points in time, wherein the update includes adding data to the inode which identifies the one or more blocks;

in response to detecting a write to the file, subsequent to said updating, is directed to particular blocks of the one or more blocks;

allocate one or more new blocks for use in storing data which corresponds to the file;

create a new entry in the extent map of the inode which identifies the new blocks, said new entry being simultaneously maintained along with entries of the one or more entries in the extent map;

update a first entry of the extent map to identify the particular blocks to which the write was directed and a time at which the write occurred;

wherein said extent map simultaneously maintains entries for multiple updates which have been made to the file at multiple points in time, and wherein each entry of the extent map includes a key comprising an offset to corresponding data within the file and a timestamp associated with a time of an update of a corresponding extent map entry;

in response to detecting the write corresponds to one or more blocks of an original extent;

split the original extent at a first block corresponding to the beginning of the write; and

split the original extent at a last block corresponding to the end of the write.

9. The computing system as recited in claim 8, wherein the computing system does not store multiple copies of a given block for a particular file which are common to multiple versions of the particular file.

10. The computing system as recited in claim 9, wherein the first entry is the new entry, and wherein the method further comprises storing data corresponding to the write in the new blocks.

11. The computing system as recited in claim 10, wherein the first entry is an entry corresponding to at least one of the particular blocks, and wherein the computing device is further configured to:

copy the data from the particular blocks to the new blocks;

store data corresponding to the write in the particular blocks; and

update the new entry to identify at least one of the new blocks, and include an original timestamp corresponding to the data stored in a corresponding block.

12. The computing system as recited in claim 8, wherein the first entry is the new entry and the new blocks comprise a new extent, and wherein the method further comprises storing data corresponding to the write in the new extent.

13. The computing system as recited in claim 8, wherein the new blocks comprise a new extent and the first entry is an entry corresponding to at least one of the particular blocks, and wherein the computing system is further configured to:

copy the data from the particular blocks to the new extent;

store data corresponding to the write in the particular blocks; and

update the new entry to identify the new extent, and include an original timestamp corresponding to the data stored in a corresponding block.

14. The computing system as recited in claim 8, wherein the extent map is stored in a B-tree, wherein each node of the B-tree includes a key comprising an offset and a timestamp associated with a time of an update of a corresponding extent map entry.

15. A computer readable storage medium comprising program instructions, wherein the program instructions are executable to:

allocate one or more of the blocks for use in storing data corresponding to a file;

store the file data in the blocks;

update an inode corresponding to the file responsive to said allocating, the inode including attributes and an extent map corresponding to the file, the inode being configured to simultaneously identify multiple versions of the file corresponding to multiple points in time, wherein the update includes adding data to the inode which identifies the one or more blocks;

in response to detecting a write to the file, subsequent to said updating, is directed to particular blocks of the one or more blocks;

allocate one or more new blocks for use in storing data which corresponds to the file;

create a new entry in the extent map of the inode which identifies the new blocks, said new entry being simultaneously maintained along with entries of the one or more entries in the extent map;

update a first entry of the extent map to identify the particular blocks to which the write was directed and a time at which the write occurred;

wherein said extent map simultaneously maintains entries for multiple updates which have been made to the file at multiple points in time, and wherein each entry of the extent map includes a key comprising an offset to corresponding data within the file and a timestamp associated with a time of an update of a corresponding extent map entry;

in response to detecting the write corresponds to one or more blocks of an original extent;

split the original extent at a first block corresponding to the beginning of the write; and

split the original extent at a last block corresponding to the end of the write.

16. The computer readable storage medium as recited in claim 15, wherein the storage medium for use in storing data does not store multiple copies of a given block for a particular file which are common to multiple versions of the particular file.

17. The computer readable storage medium as recited in claim 16, wherein the extent map is stored in a B-tree, wherein each node of the B-tree includes a key comprising an offset and a timestamp associated with a time of an update of a corresponding extent map entry.