File version reconciliation using hash codes

Abstract

A file reconciliation process in a distributed file system uses a set of rnal or log files to track the history of file modification at each of different sites, or sets of directories, in a computer system. During reconciliation, sequences of version entries associated with each file in each journal are updated and compared to determine whether (1) a conflict exists for any of the files involved in the reconciliation, and (2) if not, which version of the file is the current version. The version entries contain a hash code or digest that to a high probability uniquely identifies the contents of a file. Sequences of hash codes are used to identify the sequence of file versions. Masks and site indicator fields are included in the journal files and used to track which journal files have copies of version entries for the purpose of deleting version entries when they become obsolete.

Claims

What is claimed is:

1. A method of reconciling different data file storage sites, comprising the steps of:

generating hash codes, each hash code uniquely identifying a corresponding version of a data file by the contents thereof;

storing the generated hash codes in journal files associated with the sites, the hash codes in each journal file being stored in a sequence indicating the order in which different versions of the data file have been stored at the corresponding site;

analyzing the sequences of hash codes from the journal files to determine (1) which version of the data file is the current version, (2) the site or sites at which the current version is stored, and (3) the site or sites at which the current version is not stored; and

copying the current version of the data file from a site at which it is stored to the site or sites at which it is not stored.

2. A method according to claim 1, wherein:

the analyzing step includes determining whether a conflict exists among the sites, a conflict existing when two or more journal files have different hash codes subsequent to a last common hash code, the last common hash code being the most recently generated one of those hash codes appearing in every one of the journal files;

the copying step includes copying the data file from a site whose journal file has a hash code subsequent to the last common hash code to the site or sites whose journal files have no hash code subsequent to the last common hash code; and

the copying step is performed only if a conflict is determined not to exist.

3. A method according to claim 2, further comprising the steps of:

if a conflict is determined to exist, renaming one of the conflicting versions of the file in a manner that distinguishes the one conflicting version from the other conflicting version and also indicates the presence of the conflict; and

copying the conflicting versions of the file to others of the sites so that both conflicting versions of the file are present at all sites.

4. A method according to claim 1, wherein the hash-code storing step includes copying the hash code identifying the current version of the data file, the hash code being copied from the journal file for the site from which the data file is copied, and the hash code being copied to the journal file for each site to which the data file is copied.

5. A method according to claim 1, wherein:

the journal files include sequentially-arranged version entries, each version entry being associated with a corresponding version of the data file having been stored at the corresponding site;

each hash code is included in a corresponding one of the version entries;

each version entry includes a timestamp indicating the time at which the version of the data file identified by the hash code included with the version entry was created; and

the hash-code generating step includes: (1) determining from the timestamp in the last sequential version entry for the data file in a journal file whether the data file at the site associated with the journal file has been modified since the creation of the last version entry; (2) generating the hash code for the data file if the data file has been modified since the creation of the last version entry; and (3) refraining from generating the hash code for the data file if the data file has not been modified since the creation of the last version entry; and

the hash-code storing step includes appending a new version entry to the sequence of version entries in the journal file if the data file has been modified, the appended version entry including the hash code generated for the modified data file.

6. A method according to claim 1, wherein (1) each hash code is included in a corresponding one of a sequence of version entries in the journal files, and (2) each version entry in the journal files includes a site indicator field, the site indicator field having sub-fields, each sub-field corresponding to a different one of the sites and indicating whether the version entry containing the sub-field appears in the journal file for the site corresponding to the sub-field, and further comprising the steps of:

determining from the site indicators in the journal files whether there are version entries in the journal files that have become obsolete such that their deletion from the journal files would not deleteriously affect future reconciliations; and

deleting the version entries determined to be obsolete.

7. A method according to claim 6, wherein the determining step comprises determining whether there are any version entries in the journal files preceding an earliest version entry common to all the journal files; and wherein the deleting step comprises deleting the version entries determined to precede the earliest common version entry.

8. A method according to claim 1, wherein the journal files include sequentially-arranged version entries, each version entry being associated with a corresponding version of the data file having been stored at the corresponding site, and version entry including a file type indicator indicating whether the file is in binary or text format, and further comprising the steps of:

determining whether the file is a text file and whether the file is being copied between systems using different characters to indicate the end of a line in text files; and

if the file is a text file and the file is being copied between such systems, then changing the end-of-line characters appearing in the file to be compatible with the system to which the file is being copied.

9. In a system including data storage sites and a set of journal files associated therewith, each journal file being associated with a corresponding one of the sites and including entries indicating which versions of a data file have appeared at the site, the journal entries being updated during a process of reconciling the contents of the sites, a method of tracking which journal files contain copies of version entries appearing in one of the journal files, comprising the steps of:

storing masks in the one journal file, each mask being a predetermined data value associated with and uniquely identifying a corresponding one of the sites;

storing site indicator fields in the one journal file, each site indicator field being associated with a corresponding one of the journal entries in the one journal file and containing sub-fields, each sub-field indicating, when set to a predetermined value, whether a corresponding one of the journal files has a copy of the journal entry with which the site indicator containing the sub-field is associated; and

upon updating a journal entry in the one journal file during the process of reconciling the one site with another site, setting each of the sub-fields of the site indicator according to a value based on the initial value of the sub-field and the mask associated with each site, such that the site indicator is a persistent record of the journal files in which a copy of the journal entry has appeared.

10. A method for reconciling different versions of a file, comprising the steps of:

generating, for each different version of the file, a hash code from the data content stored in each different version of the file;

storing the hash codes in a journal file in an order in which the different versions of files were stored; and

analyzing the ordered hash codes in the journal file to identify a current version of the file.

Description

CROSS REFERENCE TO RELATED APPLICATIONS

Not Applicable

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

Not Applicable

BACKGROUND OF THE INVENTION

The present invention is related generally to the field of distributed file systems for computers, and more specifically to the reconciliation of different versions of files that may exist at different storage locations within a distributed computer system.

It is increasingly common for computer systems to use distributed file systems for the storage and retrieval of data files. This trend is displacing traditional centralized file systems, in which data files are stored on magnetic disks accessible only to application programs executing on a single computer closely coupled to the disks. As the functionality of computers has increased and their costs decreased, overall computer system performance has benefitted from allowing copies of data files to exist in multiple locations. First-generation examples of these distributed file systems involve desktop workstations or personal computers connected to a local file server. Storage of files on the desktop computer enables fast execution of programs running on the desktop computers, while the existence of these files on the file server provides for data file sharing, a function required in many distributed application programs used in organizations. More recent systems enable similar coordination of data among mobile users having portable computers, users at workstations, and a central data repository that may exist in an organization.

In distributed file systems, it is generally possible that at some time there are two or more different versions of a file at different locations, and that only one version is the current or correct version to be used by all users of the system. Because of this possibility, a mechanism is employed in distributed file systems to ensure file system coherence. A file system is coherent if the correct version of a file is provided to an application program despite the possible existence of outdated or otherwise incorrect versions in the system.

One approach to maintaining file system coherence is direct user-controlled file transfer. One example of this approach is electronic mail. Other examples include a public-domain file-transfer protocol known as Kermit, and a product known as Laplink.RTM. of Traveling Software, Inc. of Washington. The Laplink.RTM. program is used primarily to transfer files between a portable computer and either a desktop computer or another portable computer. All of these file-transfer procedures allow the user of a computer great control over the file-transfer process. However, they are generally not tailored specifically to the problem of file system coherence. The user bears substantial responsibility for anticipating conflicts among versions of files, detecting such conflicts when they occur, purging obsolete versions of files, and ensuring that file updates are timely distributed to the points in the system where they are needed.

Another class of coherence techniques uses shadowing or immediate updating of data files. Such techniques are used in systems such as Network File System (NFS). In systems using these techniques, file updates are broadcast to all storage locations immediately, and in some cases the use of a file being updated is prevented until all copies have been updated. This conservative approach to maintaining coherence eliminates the possibility of conflicts and is largely transparent to the user. However, it also tends to reduce system performance and to cause other problems related to its relative lack of user control. Additionally, the technique is not well suited for mobile users who are only intermittently connected to the broader computer system.

A third general class of coherence techniques relies on the existence of a "special location" for data files within the computer system. For example, a single file server may be the only point in the system from which the correct version of a file can be obtained. Thus the file server must be involved in all file reconciliations. A common example is embodied in a program known as "Briefcase" that is included in the Windows.RTM.95 operating system distributed by Microsoft Corp. of Washington. Briefcase can be used to maintain data file coherence between a desktop personal computer and a portable computer. The desktop machine is treated as the primary data file storage site, and the portable computer as a "briefcase" which temporarily holds copies of files obtained from the desktop computer, the copies or updated versions being returned to the desktop computer upon a user's return to the office environment.

Systems which require a special location to coordinate updates fail when the special location is broken or inaccessible. Version vector systems such as CODA and Bayou avoid using a special location by generating at each site an ascending sequence of version numbers, associating a new version number with each object it creates or updates. Journal entries contain the ID of the site which performed the update and that site's version number for the update. Each current object is associated with a vector, indexed by site, of the individual sites' version numbers. Vector comparisons can result in one of three answers: all components of one vector less than or equal the corresponding components of the other vector, the reverse, or some less and some greater. The latter case is used to detect inconsistent updates.

Yet another approach to the data file coherence problem is described in U.S. Pat. No. 5,600,834 to Howard, which issued Feb. 4, 1997 and is assigned to Mitsubishi Electric Information Technology Center America, Inc. of Cambridge, Mass. A file reconciliation technique is described that uses a combination of automatic mechanisms and user control. The reconciliation technique uses a set of journal files in which the history of file creation, modification, and deletion throughout the system is recorded, each journal file maintaining the portion of the history involving a particular site, or storage location. As used therein, the term "site" refers to a working directory and its sub-directories on a particular storage medium, such as a hard disk or floppy disk. The reconciliation process described in U.S. Pat. No. 5,600,834 is explicitly invoked and controlled by a user, and it operates to reconcile the versions of files and directories existing at the sites specified by the user. The process uses site directories and version entries in the journal files to determine whether there is a single current version of each file or directory, and if so copies that version to the other sites involved in the reconciliation. The process also checks for conflicts, these being indicated when different versions of a file exist in the system that appear to be derived from a common prior version. The process generally works by "merging" the sequences of version entries in each journal to reconstruct the creation/modification/deletion history for each file at the involved sites. Date and time values, referred to as "timestamps", in the journal entries are used in this merging process to place the events from the different journals in order. The process also includes timestamps in "known site" entries used to identify the most recent time that a given site was involved in a reconciliation. This information is used to occasionally purge version entries from the journal file when it is safe to do so, in order to prevent the journal files from growing indefinitely.

The use of timestamps as described in the '834 reconciliation process can occasionally cause undesired results, because of the imperfect tracking of date and time among different computers. Under some circumstances, for example, an older version of a file existing at one site may be written over the correct version existing at another site, because the timestamps incorrectly cause the older version to appear to be more recent. This can happen, for example, when one computer has made an adjustment for Daylight Savings Time and the other computer has not yet made such an adjustment. For similar reasons, dependence on timestamps also can cause problems in the process of tracking per-site reconciliation times.

BRIEF SUMMARY OF THE INVENTION

An improved method of reconciling different file storage sites in a distributed file system is disclosed. A set of journal or log files is used to track the history of file modification at each of the different sites. The journal files contain sequences of version entries associated with each file at the corresponding site. Each version entry contains a hash code or digest that to a very high probability uniquely identifies the contents of a corresponding version of the file. During the reconciliation process, sequences of hash codes obtained from the version entries in each journal are compared with each other to determine (1) whether a conflict exists for any of the files involved in the reconciliation, and (2) if not, which version of the file is the current version. Then the current version is copied to the other sites as necessary, and the journals updated to reflect the file copying.

The hash code or digest is computed from the contents of the file according to a known message digest program such that to a very high probability the code uniquely identifies the contents of the file from which it is generated. Because different versions of a file have different contents, they likewise result in different codes. Thus the hash codes identify different versions of files independently of the files' timestamps, so that the presently-disclosed reconciliation process does not yield undesired results arising from the use of timestamps, as discussed above. The presently-disclosed process also differs from the version vector approach, because it does not depend on the sites to generate unique ascending version numbers, and it does not require that a version vector be maintained for each object.

An improved method of tracking the involvement of sites in file reconciliations is also disclosed. Each version entry in each journal file contains a site indicator field indicating which of the journal files for the other sites has a copy of the entry. When a version entry is created during a reconciliation, the site indicator field is set to a value indicating which sites are involved in the reconciliation and therefore have a copy of the version entry. When all sites have a copy of the version entry as indicated by the site indicator field, it is safe to delete any preceding version entries. Because this tracking process uses the version entries, it further exploits the uniqueness of the hash codes and avoids problems associated with the use of timestamps.

Other aspects, features, and advantages of the present invention are disclosed in the detailed description which follows.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING

FIGS. 1 and 2 are directory listings of two data file storage sites in a computer system;

FIG. 3 is a diagram of the structure of a journal file used in the presently disclosed reconciliation process;

FIGS. 4 through 6 illustrate the structures of components of the journal file of FIG. 3;

FIG. 7 is a flow diagram of the presently disclosed reconciliation process;

FIG. 8 is flow diagram of part of the process by which version entries in the journal file of FIG. 3 are created during the reconciliation process of FIG. 7; and

FIGS. 9-11 are time line diagrams depicting examples of activity affecting files involved in reconciliation.

DETAILED DESCRIPTION OF THE INVENTION

FIGS. 1 and 2 show listings of files existing at two separate sites referred to as SITE1 and SITE2 respectively. The files are listed by filename. SITE1 contains three user files file1.xxx, file2.xxx, and file3.xxx, a subdirectory sub1.dir containing two additional files file5.xxx and file6.xxx, and a journal file site1.jnl. The `xxx` values represent file type extensions that identify the files as user data files. SITE2 contains generally the same files as SITE1, except that it contains a file file4.xxx not contained in SITE1, and it does not have file3.xxx. The journal file for SITE2 is named site2.jnl.

The user files and directory files shown in FIGS. 1 and 2 are created, read, modified, and deleted by a user of the computer system or systems on which the sites SITE1 and SITE2 reside. Further, the files and directories in the sites SITE1 and SITE2 are generally intended to mirror each other. For example, the site SITE1 may be an area on the hard disk of a user's workstation, and the site SITE2 an area on a large disk in a file server used to hold shared or backup copies of the workstation's files. Thus periodically the user files and directories at the two sites are reconciled with each other so that both sites have the latest copies of the files and directories.

FIGS. 3 through 6 show the structure of a journal file. As shown in FIG. 3, a journal file consists of a Header, one or more Site entries, and one or more Version entries. There may be more than one Header, as is the case if a site has subdirectories, but Site entries are only found after the first Header line. A Site entry exists for each site that has been involved in a reconciliation. A Version entry is added to the journal file for each version of each file that has existed at a site. Version entries are purged when they become obsolete, so the Version entries in the journal file at any given time represent only the pertinent version history for each file.

The Header structure is shown in FIG. 4. The site whose history appears in the journal file is identified in a field labelled <sitename>. The Header also includes a field labelled <systype> used to identify the type of computer system on which the site resides, and a field labelled <programname> to identify the version of the reconciliation program that created the journal file.

As shown in FIG. 5, a Version entry includes several fields, these being described as follows:

    ______________________________________
    <verb>       An action performed:
                 + Created or Modified
                 - Deleted
    <date>       Date action performed
    <time>       Time action performed
    <name>       Name of file acted on
    <t>          Type of file acted on:
                 (blank) Ordinary file
                 /  Subdirectory
                 @ Symbolic Link
    ?sites       Bit field indicating which sites do NOT
                 know about this Version; omitted if
                 Version known at all sites. Bit-to-site
                 mapping defined in the mask field of Site
                 entries.
    <digest>     Unique hash code or digest of the contents
                 of the file that resulted from the action.
                 "dt" prefix indicates file is a text file;
                 "db" indicates binary file.
    <remarks>    Remark whose use depends on context. Two
                 special remarks are:
                 !was <name>   (saved file)
                 !deleted <name>  (deleted directory)
    ______________________________________

    ______________________________________
    <date>       Date site last involved in reconciliation
    <time>       Time site last involved in reconciliation
    <sitename>   Name of site
    ?mask        Bit mask to be used for this site in site
                 field of Version entries
    ______________________________________

    ______________________________________
           Journal of SITE1
           $ <date> <time> SITE2 ?1
           $ <date> <time> SITE1 ?2
           + f1date f1time file1.xxx dt = aaaaa
           + f2date f2time file2.xxx dt = bbbbb
           + f3date f3time file3.xxx dt = aaaaa
           + s1date s1time sub1.dir/
           Journal of SITE1/sub1.dir
           + f5date f5time file5.xxx dt = eeeee
           + f6date f6time file6.xxx dt = fffff
           Journal of SITE2
           $ <date> <time> SITE2 ?1
           $ <date> <time> SITE1 ?2
           + f1date f1time file1.xxx dt = aaaaa
           + f2date f2time file2.xxx dt = bbbbb
           + f4date f4time file4.xxx dt = ddddd
           + s1date s1time sub1.dir/
           Journal of SITE2/sub1.dir
           + f5date f5time file5.xxx dt = eeeee
           + f6date f6time file6.xxx dt = fffff
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    + file1 jj39z       + file1 jj39z
    + file2 r9t4w       + file2 r9t4w
    + file3 pq9zr       + file3 pq9zr
    ______________________________________

    ______________________________________
    SITE1                SITE2
    ______________________________________
    file1 jj39z          file1 jj39z
    file2 kpn33          file2 r9t4w
    file3 pq9zr
    ______________________________________

    ______________________________________
    SITE1                SITE2
    ______________________________________
    + file1 jj39z        + file1 jj39z
    + file2 r9t4w        + file2 r9t4w
    + file2 kpn33
    + file3 pq9zr        + file3 pq9zr
                         - file 3
    ______________________________________

    ______________________________________
    SITE1:               SITE2:
    ______________________________________
    + file1 jj39z
                       + file1 jj39z
                       + file2 r9t4w
                        + file2 r9t4w
                       + file2 kpn33
                       + file3 pq9zr
                        + file3 pq9zr
                         - file3
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    + file1 jj39z       + file1 jj39z
    + file2 r9t4w       + file2 r9t4w
    + file2 kpn33       + file2 kpn33
    + file3 pq9zr       + file3 pq9zr
    - file3             - file3
    ______________________________________

    ______________________________________
    SITE1                SITE2
    ______________________________________
    file1 jj39z          file1 jj39z
    file2 kpn33          file2 kpn33
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    + file1 jj39z       + file1 jj39z
    + file2 kpn33       + file2 kpn33
    - file3             - file3
    ______________________________________

    ______________________________________
    SITE1                SITE2
    ______________________________________
    file1 d9qlj          file1 92w3a
    file2 kpn33          file2 kpn33
    ______________________________________

    ______________________________________
    SITE1                SITE2
    ______________________________________
    + file1 jj39z
                       + file1 jj39z
                       + file1 d9qlj  + file1 92w3a
                       + file2 kpn33
                        + file2 kpn33
                       - file3
                        - file3
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    file1 d9qlj         file1#1 92w3a
    file2 kpn33         file2 kpn33
    ______________________________________

    ______________________________________
    SITE1                SITE2
    ______________________________________
    + file1 jj39z
                       + file1 jj39z
                       + file1 d9qlj  + file1#1 92w3a
                       + file2 kpn33
                        + file2 kpn33
                       - file3
                        - file3
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    file1 d9qlj         file1 d9qlj
    file1#1 92w3a       file1#1 92w3a
    file2 kpn33         file2 kpn33
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    + file1 jj39z       + file1 jj39z
    + file1 d9qlj       + file1 d9qlj
    + file1#1 92w3a     + file1#1 92w3a
    + file2 kpn33       + file2 kpn33
    - file3             - file3
    ______________________________________

    ______________________________________
    SITE1               SITE2
    ______________________________________
    + file1 d9qlj       + file1 d9qlj
    + file1#1 92w3a     + file1#1 92w3a
    + file2 kpn33       + file2 kpn33
    - file3             - file3
    ______________________________________

    ______________________________________
    site1.jnl:
            $ date1 time1 SITE1 ?01
            $ date1 time1 SITE2 ?02
    site2.jnl:
            $ date1 time1 SITE1 ?01
            $ date1 time1 SITE2 ?02
    ______________________________________

    ______________________________________
    site1.jnl:
            $ date2 time2 SITE1 ?01
            $ date1 time1 SITE2 ?02
            $ date2 time2 SITE3 ?04
    site2.jnl (unchanged):
            $ date1 time1 SITE1 ?01
            $ date1 time1 SITE2 ?01
    site3.jnl:
            $ date2 time2 SITE1 ?01
            $ date1 time1 SITE2 ?02
            $ date2 time2 SITE3 ?04
    ______________________________________

    ______________________________________
    SITE1 (?1)    SITE2 (?2)     SITE3 (?4)
    ______________________________________
    + file1 jj39z + file1 jj39z  + file1 jj93z
    + file1 d9qlj ?4
                  + file1 d9qlj ?4
    + file1#1 92w3a ?4
                  + file1#1 92w3a ?4
    + file2 r9t4w + file2 r9t4w  + file2 r9t4w
    + file2 kpn33 ?4
                  + file2 kpn33 ?4
    + file3 pq9zr + file3 pq9zr  + file3 pq9zr
    - file3 ?4    - file3 ?4
    ______________________________________

    ______________________________________
    SITE1         SITE2         SITE 3 (?4)
    ______________________________________
    + file1 jj39z + file1 jj39z + file1 jj39z
    + file1 d9qlj ?4
                  + file1 d9qlj + file1 d9qlj
    + file1#1 92w3a ?4
                  + file1#1 92w3a
                                + file1#1 92w3a
    + file2 r9t4w + file2 r9t4w + file2 r9t4w
    + file2 kpn33 ?4
                  + file2 kpn33 + file2 kpn33
    + file3 pq9zr + file3 pq9zr + file3 pq9zr
    - file3 ?4    - file3       - file3
    ______________________________________

    ______________________________________
    SITE1 (?1)    SITE2 (?2)    SITE3 (?4)
    ______________________________________
    + file1 jj39z
    + file1 d9qlj ?4
                  + file1 d9qlj + file1 d9qlj
    + file1#1 92w3a ?4
                  + file1#1 92w3a
                                + file1#1 92w3a
    + file2 r9t4w
    + file2 kpn33 ?4
                  + file2 kpn33 + file2 kpn33
    + file3 pq9zr
    - file3 ?4    - file3       - file3
    ______________________________________

• Inventors
  Howard, John H.;
• Assignee
  Mitsubishi Electric Information Technology Center America, Inc. (ITA) (Cambridge, MA)
• Published
  Aug-1-2000
• Current US Classes:
  707/205
  707/6
• Application #
  054330
• International Classes
  G06F 017/30
• Field of Search
  707/6 707/205 707/2 707/10 707/7 707/102 707/103 707/8 707/201 364/222 364/228 364/282 364/281 340/172 380/25 709/215
• Examiner
  Amsbury; Wayne
• Agent
  Brinkman; Dirk
• US Patent References:
  5333315
  5754844
  5778068
  5778393