Data repository and method for promoting network storage of data

• US 7,685,096 B2
• Filed: 10/14/2004
• Issued: 03/23/2010
• Est. Priority Date: 02/18/2000
• Status: Expired due to Fees

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Permabit Technology Corporation (International Business Machines Corporation)
• Inventors: Homsy, George E. II, Floyd, Jered J., Knight, Thomas F. Jr., Margolus, Norman H.
• Primary Examiner(s): Pham; Hung Q
• Application Number:
  US10/967,071
• Publication Number:
  US 20050131961A1
• Time in Patent Office: 1,986 Days
• Field of Search: 707/2, 707/10, 713/180
• US Class Current: 713/165
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/645 using a third party
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for turning variable-length file path names into fixed-length object identifiers in a data repository, the method comprising, assigning a fixed-value identifier to a file system in the data repository, computing a first deterministic pseudo-random function that combines a first component of a plurality of file system pathname components associated with a file with the fixed-value identifier, computing a second deterministic pseudo-random function that combines a second component of the plurality of file system pathname components with the result of the first function, and using at least one of the computed deterministic pseudo-random functions to produce a fixed-length object identifier for the file.

Claims

1. A method for storing and retrieving files, the method comprising:

storing a plurality of objects, identified by fixed-length object-identifiers, in a data repository;

assigning, by clients of the data repository, a fixed-value identifier to each file system of a plurality of client file systems;

sending, from one of the clients of the data repository, a plurality of files belonging to at least one of the plurality of file systems to be stored in the data repository, with each of the plurality of files identified by a fixed-length object-identifier computed from a file system pathname that comprises a plurality of ordered pathname components;

for each of the plurality of files to be stored;

computing sequentially, by the one of the clients, a component identifier for each component of the file system pathname of the file to be stored, using a hash function, wherein the component identifier of the first component of the file system pathname is computed by hashing the first component and the fixed-value identifier assigned to the file system that the file to be stored belongs to, and for each component of the file system pathname after the first component, the component identifier of that component is computed by hashing that component and the computed component identifier of the component before that component; and

storing the file as an object in the data repository, using the computed component identifier of the last component of the file system pathname as a fixed-length object-identifier for the object stored in the data repository;

sending, from a client of the data repository, an access request to the data repository, wherein the access request includes a computed component identifier of the last component of a file system pathname as a fixed-length object-identifier;

locating, by a data server of the data repository, stored data corresponding to the fixed-length object-identifier included in the sent access request; and

retrieving a file corresponding to the located stored data from the data repository and communicating the retrieved filed to the client;

wherein, for each of the sent plurality of files to be stored, the first component of the file system pathname comprises the name of a top-level directory that is one of a plurality of top-level directories of the file system that the file to be stored belongs to, and the last component of the file system pathname comprises the name of the file.

2. The method of claim 1 in which the hash function is a cryptographic hash function.

3. The method of claim 1 in which the fixed-value identifier assigned to each file system of the plurality of client file systems is chosen randomly.

4. The method of claim 1 in which pathname components are stored in the data repository.

5. The method of claim 1 in which information sufficient to compute a last component identifier for one of the plurality of files is communicated from the one of the clients of the data repository to an other of the clients of the data repository in order to transmit access to the one of the plurality of files from the one of the clients to the other of the clients.

6. The method of claim 1 in which the one of the clients of the data repository copies files from a source file system into the data repository using source path names to derive repository object identifiers.

7. The method of claim 1 in which the data repository uses a fingerprint of a portion of object content in order to identify and locate a stored block containing the portion of content.

8. The method of claim 7 in which the fingerprint is a cryptographic hash of the portion of object content.

9. The method of claim 7 in which a plurality of clients of the data repository that store objects that all contain a portion of object content with a same fingerprint share access to a stored block containing the portion of object content.

10. The method of claim 1 wherein a fixed-value identifier is a name-randomizer value.

11. The method of claim 1 wherein the data repository comprises a set of repository servers and the allocation of objects to repository servers is based, at least in part, on object identifiers.

12. The method of claim 1 in which, for each of the sent plurality of files to be stored, the file system pathname that identifies the file to be stored has more than two components and all but the last component are the names of directories of the file system that the file to be stored belongs to.

13. The method of claim 1 in which the file system pathname that identifies a file to be stored has more than ten components.

14. The method of claim 1 in which the information sufficient to compute the last component identifier for the one of the plurality of files comprises:

the component identifier for a component that is earlier in the pathname of the one file, and components of the pathname that follow the earlier component.