History preservation in a computer storage system

• US 7,318,072 B2
• Filed: 01/07/2004
• Issued: 01/08/2008
• Est. Priority Date: 02/26/2003
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Burnside Acquisition, LLC
• Inventors: Margolus, Norman H., Homsy, George E. II, Keller, Jeffrey M., Floyd, Jered J.
• Primary Examiner(s): Pham; Khanh B.
• Application Number:
  US10/752,872
• Publication Number:
  US 20040168057A1
• Time in Patent Office: 1,462 Days
• Field of Search: 707 1- 10, 707/200, 707/100, 707/203, 713/187, 711/114
• US Class Current: 1/1
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/125 characterised by the use of retention policies retention policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method by which a disk-based distributed data storage system is organized for protecting historical records of stored data entities. The method comprises recording distinct states of an entity, corresponding to different moments of time, as separate entity versions coexisting within the distributed data storage system, and assigning expiration times to the entity versions independently within each of a plurality of storage sites according to a shared set of rules, before which times deletion is prohibited.

Claims

1. A method for ensuring that rules that prevent premature deletion of data objects stored in a storage system are enforced by servers that store blocks of content that constitute the data objects, the method comprising:

associating distinct reference source identifiers with each of a plurality of storage system entities that make reference to blocks of content;

associating a set of rules with a data object, the set of rules governing when deletion is allowed and when it is disallowed;

computing a hash value based at least in part on both a reference source identifier and information descriptive of or used by the set of rules; and

communicating information which allows the hash value to be computed, to a server that stores a block of content that is a constituent of the data object;

wherein the communicated information is part of a request to delete the block of content; and

wherein when deletion of the data object is disallowed, modification of the content of the data object is also disallowed.

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

3. The method of claim 1 in which the block of content is identified by a digital fingerprint that involves a hash of its content.

4. The method of claim 1 in which the block of content is assigned an expiration time, before which time deletion is prohibited.

5. The method of claim 4 in which an expiration time assigned to the data object is also assigned to each of its constituent blocks of content.

6. The method of claim 4 in which, during a certain time period, the connection between the data object and the block of content is not visible to the server storing the block of content.

7. The method of claim 6 in which, during the certain time period, the expiration time of the block of content passes and the server storing it discards it and reuses its storage space.

8. The method of claim 4 in which no action taken by a client of the storage system can cause the expiration time to be changed to an earlier time.

9. The method of claim 8 in which the client deposits the data object into the storage system.

10. The method of claim 8 in which the client causes the expiration time assigned to the data object to be changed to a later time.

11. The method of claim 8 in which an action taken by the client causes a value to be assigned to the expiration time.

12. The method of claim 4 in which no action taken by any client program that only communicates with the storage system over a wide area network can cause the expiration time to be changed to an earlier time.

13. The method of claim 1 in which the block of content are stored at a plurality of storage sites.

14. The method of claim 1 in which a server storing the block of content denies a request that violates one or more of the set of rules.

15. The method of claim 1 in which distinct states of the data object are recorded, corresponding to different moments of time, as separate version data objects coexisting within the storage system.

16. The method of claim 15 in which the set of rules depends upon when a version data object was created.

17. The method of claim 1 in which the hash value is combined with other hash values associated with other references to the block of content, to form a reference record that is used as part of a reference counting scheme.

18. The method of claim 17 in which the reference record is associated with an interval of expiration times, with the interval comprising a specified starting time and a specified ending time.

19. The method of claim 18 in which the reference record is a sum of hash values associated with references to the block of content.

20. The method of claim 19 in which a reference is removed from the reference record by subtracting a hash value associated with the reference.

21. The method of claim 18 in which, at times during the interval of expiration times, the reference record indicates a non-zero number of references to the block of content and the block is retained.

22. The method of claim 18 in which, at some time during the interval of expiration times, the reference record indicates zero references to the block of content and the block is discarded.

23. The method of claim 18 in which the reference record indicates a non-zero number of references to the block of content but the specified end time of the interval of expiration times has passed and the block is discarded.

24. The method of claim 1 in which the hash value is stored so that it can later be retrieved by the server that stores the block of content.

25. The method of claim 1 in which a content hash is computed as part of the process of depositing the block of content into the storage system.

26. The method of claim 25 in which the block of content is stored at a location or locations determined at least in part by the content hash.

27. The method of claim 25 in which a second content hash is computed as part of the process of depositing a second block of content.

28. The method of claim 27 in which the values of the first and second content hashes are the same and the second deposit relies on the block of content already stored rather than storing a separate copy of the second block of content.

29. The method of claim 1 in which the plurality of storage system entities comprises a plurality of programs or a plurality of computers or a plurality of storage system users.

30. The method of claim 1 in which the plurality of storage system entities comprises a plurality of data structures that contain pointers to the block of content.

31. The method of claim 1 in which the data object is a version data object that records the state of a versioned object at a moment of time, and the set of rules that govern when deletion is allowed for the data object depends upon information about other version data objects that record the state of the versioned object at other moments of time.

32. The method of claim 1 in which the block of content is also a constituent of a second data object that is distinct from the data object, and reference source identifiers are associated with the data object and the second data object.