Method for storing data in one or more files so that both previous and new versions of the data are separately accessible

• US 6,684,226 B1
• Filed: 03/24/2000
• Issued: 01/27/2004
• Est. Priority Date: 03/24/2000
• Status: Expired due to Fees

• Current Assignee: Frontline Software ApS (FrontBase, Inc.)
• Original Assignee: Frontline Software ApS (FrontBase, Inc.)
• Inventors: Bodilsen, Svend
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US09/533,990
• Time in Patent Office: 1,404 Days
• Field of Search: 707/103, 707/203, 707/8, 707/100, 707/201, 707/204, 707/205, 709/217, 717/11, 717/162, 713/185
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

System and method for transaction-based versioned file system. A file system assists the users of computer systems to store data on external persistent storage media such as hard disks, the main task for the file system is to move data to and from the external media, traditional file system leaves the user with little or no control over the contents of files across system crashes. As a consequence the contents of the files are undefined after a system crash, and the file system itself may require lengthy recovery routines before the file system can be used again. The transaction based file system provides the user with control of the contents of the files in the file system across system failures, and the transaction based file system does not require lengthy recovery routines after system failure. A number of versions may be maintained at the same time and retrieved independently of each other. The version generation is based on the so-called shadow page principle.

Claims

1. A method for storing information stored in one or more files on a permanent storage medium, comprising the steps of:

storing data transaction-wise according to a shadow paging principle,

retaining, in a commit operation, the previous data and their physical storage on the storage medium together with a separate storage on the storage medium representing new data as changes to the previous data,

the previous data and the changes together constituting, upon commit, a new version of the data,

both the previous and the new versions of the data being separately accessible,

wherein the data are stored as a number of individually addressable data blocks, addresses representing the physical storage of the individual data blocks being stored in a tree structure of one or more first data elements, and wherein the storing step comprises;

identifying data blocks to be modified,

copying the identified data blocks,

performing the modification(s) on the copied data blocks,

storing the modified data blocks at addresses not coinciding with any of the addressable data blocks or any of the first data elements,

for each identified data block, identifying one or more of the first data elements of the tree structure from a root of the tree structure to the data block,

copying each identified data element at an address not coinciding with any of the addressable data blocks or any of the first data elements,

replacing, in each copied first data element, the address of the identified data block or first data element with the address of the corresponding modified data block or first data element, and

providing a new root of the modified tree structure and having the new root represent the modified first data element corresponding to the first data element represented by the root of the tree structure.

2. The method according to claim 1, wherein the data of a file is stored as a number of data blocks and wherein a change of the contents of the file, the previous data, results in a change of the contents of one or more of the data blocks.

3. The method according to claim 1, wherein a single commit operation causes all changes due to the transaction to all of the one or more files.

4. The method according to claim 1, wherein, during operation of a program accessing the database, at least a number of previous versions representing the maximum simultaneously outstanding transactions plus two are retained.

5. The method according to claim 1, wherein the commit operation comprises the step of providing a new root.

6. The method according to claim 1, wherein:

prior to the step of storing the modified data blocks, information is provided relating to the free addresses of the data storage medium which are not occupied by the data blocks and the first data elements,

the step of storing the modified data blocks comprises storing the modified data blocks at free addresses and removing the addresses from the free addresses, and

the step of copying each identified first data element comprises storing the modified first data elements at free addresses and removing the addresses from the free addresses.

7. The method according to claim 6, wherein the step of information being provided relating to the free addresses comprises:

I) identifying at least substantially all addresses of the storage medium or a relevant part thereof and denoting these addresses free addresses, and

II) for each root, identifying all first data elements and data blocks of the corresponding tree element and removing the corresponding addresses from the free addresses.

8. The method according to claim 7, wherein the step II) is performed only for a predetermined number of roots.

9. The method according to claim 6, wherein the step of information being provided relating to the free addresses comprises, upon a commit operation,storing the addresses of the identified data blocks and first data elements together with a reference to an identity of the new version of the data, providing information relating to free addresses of the storage medium prior to the commit operation, and adding stored addresses referring to an identity of a predetermined prior version of the data to the information relating to the free addresses.

10. The method according to claim 9, wherein a predetermined number of versions of the data are maintained available and where step 3) comprises adding the stored addresses referring to a version generated prior to the predetermined number of versions.

11. The method according to claim 9, further comprising the steps of:

identifying and reserving an existing version of the data, and

performing step

     3) only after release of the reserved version.

12. A method according to claim 1, further comprising the step of:

storing the addresses of the identified data blocks and first data elements in one or more second data elements stored in the storage medium.

13. The method according to claim 12, wherein the second data elements are linked together in a linear list.

14. The method according to claim 1, wherein each data block is encrypted prior to storing.

15. The method according to claim 1, wherein each first data element is encrypted prior to storing.

16. The method according to claim 1, wherein the method comprising collecting a number of desired changes to the data of the one or more files, preparing the new data by performing changes to the previous data and finally separately storing the new data by performing the commit operation.