EP0774715A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
System for backing up files from disk volumes on multiple nodes of a computer network
Assignee: STAC Electronics
•
Filing: 1996-10-21
•
Granted: —
•
Expires: 2016-10-21
Abstract
Abstract A system for backing up files from disk volumes on multiple nodes of a computer network to a common random-access backup storage means. As part of the backup process, duplicate files (or portions of files) may be identified across nodes, so that only a single copy of the contents of the duplicate files (or portions thereof) is stored in the backup storage means. For each backup operation after the initial backup on a particular volume, only those files which have changed since the previous backup are actually read from the volume and stored on the backup storage means. In addition, differences between a file and its version in the previous backup may be computed so that only the changes to the file need to be written on the backup storage means. All of these enhancements significantly reduce both the amount of storage and the amount of network bandwidth required for performing the backup. Even when the backup data is stored on a shared-file server, data privacy can be maintained by encrypting each file using a key generated from a fingerprint of the file contents, so that only users who have a copy of the file are able to produce the encryption key and access the file contents. To view or restore files from a backup, a user may mount the backup set as a disk volume with a directory structure identical to that of the entire original disk volume at the time of the backup.
Inventors
- 👤 Douglas L. Whiting
- 👤 Tom Dilatush
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-05 21:18
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1446; G06F11/1448; G06F11/1453; G06F11/1458; G06F11/1464
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
306 words
A method for backing up data files stored on a disk volume of a node of a computer network to a backup storage means, said backup storage means containing data files already backed up from other nodes on said computer network, said method comprising the steps of: searching through a list of said files already contained in said backup storage means for a match to files to be backed up from said disk volume; operative when no match is found between a file to be backed up from said disk volume and any of said files already contained in said list, storing on said backup storage means a complete representation of the contents of said file to be backed up, computing an index that indicates the location on said backup storage means of said complete representation, and adding to said list an entry describing said file to be backed up from said disk volume; operative when a match is found between a file to be backed up from said disk volume and a file already contained in said list, computing an index that indicates the location on said backup storage means of a complete representation of the contents of said file already contained in said list; storing a data structure specifying the directory structure of said disk volume at the time of the backup operation, said data structure also including, for each said file backed up from said disk volume, said index indicating the location of said complete representation, either of said file to be backed up or of said file already contained in said list, depending on the outcome of said search through said list; and whereby a file that is duplicated across nodes may be identified so that only one copy of the contents of said file is stored on said backup storage means.
Claim 2
Dependent Claim
86 words
The method of claim 1 in which the step of storing said complete representation of the contents of said file to be backed up further includes the step of: operative when a previous version of said file has already been backed up from said node to said backup storage means, computing the differences from the previous version of said file, representing portions of the contents of said file to be backed up using indices into the representation of said previous version on said backup storage means.
Claim 3
Dependent Claim
67 words
The method of claim 2 in which the existence of said previous version of said file is detected using a previously saved data structure specifying the directory structure of a previous backup operation, and in which said differences between said versions are computed using an index, contained in said previously saved data structure, to a complete representation of the contents of said previous version of said file.
Claim 4
Dependent Claim
49 words
The method of claim 3 in which the steps of storing said complete representation of the contents of said file to be backed up further includes the step of compressing portions of said representation using a lossless data compression algorithm before storing said representation on said backup storage means.
Claim 5
Dependent Claim
58 words
The method of claim 4 in which the step of storing said complete representation of the contents of said file to be backed up further includes the step of encrypting portions of said complete representation using a hash encryption key that is derived by computing a hash function on the contents of said file to be backed up.
Claim 6
Dependent Claim
27 words
The method of claim 5 in which said hash encryption key is stored as part of said data structure specifying the directory structure of said disk volume.
Claim 7
Dependent Claim
59 words
The method of claim 1 in which the step of storing said complete representation of the contents of said file to be backed up further includes the step of encrypting portions of said complete representation using a hash encryption key that is derived from a computing a hash function on the contents of said file to be backed up.
Claim 8
Dependent Claim
27 words
The method of claim 7 in which said hash encryption key is stored as part of said data structure specifying the directory structure of said disk volume.
Claim 9
Independent Claim
60 words
The method of any of claims 1-8 in which the step of storing said data structure specifying said structure of said disk volume further includes the steps of compressing portions of said data structure with a lossless data compression algorithm; and encrypting said hash encryption key using an encryption key that is private to said node on said computer network.
Claim 10
Independent Claim
33 words
The method of any of claims 1-8 in which the said list of said files already contained in said backup storage means is organized as a database in order to minimize search time.
Claim 11
Dependent Claim
51 words
The method of claim 10 in which each entry in said database includes a bash function computed on the directory entry information for the file associated with said entry, including the file name, length, and time of creation, and a hash function computed over portions of the contents of said file.
Claim 12
Dependent Claim
144 words
The method of claim 11 in which said search of said database includes the following steps: loading a first section of said database, said first section containing partial entries, each partial entry containing only a portion of an entry of said database; generating a new database entry of said file to be backed up; and searching through said first section for a match between said new database entry and said partial entries and, operative when a match is found between said new database entry and a partial entry of said first section, loading the remaining portions of said matching partial entry from the associated entry in a second section of said database, and comparing said new database entry with said remaining portion of said associated entry to determine whether there is a complete match between said new database entry and the complete database entry.
Claim 13
Dependent Claim
35 words
The method of claim 12 in which said first section of said database is stored in a sorted order based on bit fields of said partial entries and is compressed with lossless data compression algorithm.
Claim 14
Dependent Claim
57 words
The method of claim 13 in which said lossless data compression algorithm includes storing an array indicating how many consecutive entries in said sorted first section have bit fields of each possible value of said bit fields, and in which the rest of said first section omits said bit fields from the remainder of said partial entries.
Claim 15
Independent Claim
64 words
The method of any of claims 1-8 in which the contents of a particular backup operation are mounted as a restored disk volume having a directory structure identical to that of the original disk volume at the time of said backup operation, whereby said files on said restored disk volume may be accessed from any application software that uses normal file system input/output calls.
Claim 16
Dependent Claim
17 words
The method of claim 15 in which said restored disk volume is accessible on a read-only basis.
Claim 17
Dependent Claim
44 words
The method of claim 15 in which said restored disk volume is accessible for reads and write, all writes to said restored disk volume being cached in a transient storage means, the contents of which are discarded when said restored disk volume is unmounted.
Claim 18
Independent Claim
150 words
The method of any of claims 2-8 in which the differences between said file to be backed up and said previous version of said file are computed using a probabilistic algorithm, including the following steps: at the time when said previous version was backed up, storing on said backup storage means a set of hash function values computed on fixed size chunks of said previous versions; at the time of said backup, loading said previously stored hash function results; comparing said hash function results from said previous file version to hash function results computed on fixed size chunks of said file to be backed up; and operative when a chunk of said file to be backed up has the same hash value as a chunk of said previous file, representing sad chunk of said file to be backed up by an index indicating said matching chunk of said previous version.
Claim 19
Dependent Claim
61 words
The method of claim 18 in which said comparison of said hash function results includes sliding the hash function computation from byte to byte within said file to be backed up, whereby matching chunks in said file to be backed up may be found on any byte boundary in said file to be backed up, and not solely on chunk boundaries.
Claim 20
Dependent Claim
18 words
The method of claim 19 in which said hash function includes computation of a cyclic redundancy check (CRC).
Claim 21
Dependent Claim
62 words
The method of claim 18 in which the contents of a particular backup operation are mounted as a restored disk volume having a directory structure identical to that of the original disk volume at the time of said backup operation, whereby said files on said restored disk volume may be accessed from any application software that uses normal file system input/output calls.
Claim 22
Dependent Claim
17 words
The method of claim 21 in which said restored disk volume is accessible on a read-only basis.
Claim 23
Dependent Claim
44 words
The method of claim 22 in which said restored disk volume is accessible for reads and write, all writes to said restored disk volume being cached in a transient storage means, the contents of which are discarded when said restored disk volume is unmounted.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.