History preservation in a computer storage system

• US 8,055,628 B2
• Filed: 01/07/2004
• Issued: 11/08/2011
• Est. Priority Date: 02/26/2003
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Permabit Technology Corporation (International Business Machines Corporation)
• Inventors: Margolus, Norman H., Homsy, George E. II, Keller, Jeffrey M., Floyd, Jered J.
• Primary Examiner(s): Lovel; Kimberly
• Application Number:
  US10/752,980
• Publication Number:
  US 20040167939A1
• Time in Patent Office: 2,862 Days
• Field of Search: 707/200, 707/663, 7079992-999204
• US Class Current: 707/663
• 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 by which a disk-based data storage system attached to a network is organized for protecting historical records of stored data entities, the method comprising:

storing data entities in the disk-based data storage system;

recording distinct states of the stored data entities, corresponding to different moments of time, as separate entity versions stored within the disk-based data storage system;

assigning an expiration time to a first entity version which records a state of a first stored data entity;

assigning an expiration time to a second entity version which records a state of a second stored data entity that is distinct from the first stored data entity; and

assigning expiration times to blocks of stored content that constitute the first and second entity versions;

wherein the recording step comprises determining, using hashes of blocks of content and without comparing entire blocks of content, that a block of content of the first entity version is identical to a block of content of the second entity version;

wherein storage space for the identical block of content is shared between the first and second entity versions, constituting a shared block of stored content;

wherein an expiration time assigned to the shared block of stored content is constrained by the expiration times assigned to the first and second entity versions, so that the expiration time assigned to the shared block is constrained to be at least as late as the latest of the expiration times assigned to the first and second entity versions;

wherein the expiration time assigned to the shared block is finite;

wherein the expiration time assigned to the first entity version is later than the expiration time assigned to the second entity version;

wherein a client of the disk-based data storage system determines the expiration time assigned to the first entity version;

wherein, if an expiration time has been assigned to the shared block and as long as the expiration time has not yet passed, the client cannot cause the shared block to be modified or deleted, and cannot cause the expiration time assigned to the shared block to be changed to an earlier time;

wherein, after an expiration time has been assigned to the shared block and before it has passed the client can cause the expiration time to be changed to a later time; and

wherein, after the expiration time assigned to the shared block has passed, the shared block is deleted.

2. The method of claim 1 in which the disk-based data storage system is distributed and the expiration times are assigned independently within each of a plurality of storage sites according to a shared set of rules.

3. The method of claim 2 in which two storage sites are at least a mile apart.

4. The method of claim 1 in which a second shared block is assigned a reference count which reflects the number of instances there are of the block as a constituent of entity versions which have not been assigned an expiration time.

5. The method of claim 4 in which the second shared block is assigned a reference count which reflects the number of instances there are of the block as a constituent of entity versions which are scheduled to expire during some specified future time interval.

6. The method of claim 4 in which the second shared block is assigned a default expiration time that depends on a time of origin associated with the block itself.

7. The method of claim 6 in which the default expiration time depends at least in part upon expiration times assigned to entity versions that it is a constituent of.

8. The method of claim 6 in which the second shared block has a reference count of zero and a default expiration time which has passed and it is discarded and its storage space is reused.

9. The method of claim 1 in which the expiration time assigned to the shared block has not yet passed and a specially authorized client of the disk-based storage system is allowed to cause the shared block to be discarded.

10. The method of claim 1 in which the expiration time assigned to the first entity version has not yet passed and a specially authorized client of the disk-based storage system is allowed to cause the first entity version to be deleted.

11. The method of claim 10 in which a block that is a constituent of the deleted first entity version is discarded and its storage space is reused.

12. The method of claim 1 in which the client only communicates with the disk-based data storage system over the network.

13. The method of claim 12 in which the client caused the first entity version to be stored into the disk-based data storage system.

14. The method of claim 1 in which, after the expiration time determined by the client is assigned to the first entity version and before it has passed, the client causes the expiration time assigned to the first entity version to be changed to a later time.

15. The method of claim 1 in which the first entity version initially had no expiration time assigned to it and an action taken by the client caused the expiration time to be assigned.

16. The method of claim 1 in which, after the expiration time is assigned to the first entity version and before it has passed, no action taken by any client program that only communicates with the disk-based data storage system over a wide area network can cause the expiration time assigned to the first entity version to be changed to an earlier time.

17. The method of claim 1 in which the first entity version is one of a plurality of entity versions that record historical states of the first stored data entity, with each of the plurality of entity versions associated with a historical time interval during which the recorded historical state was the state of the first stored data entity.

18. The method of claim 17 in which the expiration time assigned to the first entity version depends at least in part on the length of the historical time interval associated with the first entity version.

19. The method of claim 17 in which the expiration time assigned to the first entity version depends at least in part on whether or not the historical time interval associated with the first entity version includes a specified moment of time.

20. The method of claim 1 in which the first stored data entity is a file in a file system or a record in a database or an object in an object storage system.

21. The method of claim 1 in which expiration times are assigned to a plurality of entity versions by clients of the disk-based data storage system.

22. The method of claim 1 in which a third entity version is deposited into the disk based data storage system in response to a request by a client program communicating with the storage system over the network;

and the client program requests that the third entity version be deleted before it has expired and it is not deleted; and

the client program requests that the third entity version be deleted after it has expired and it is deleted.

23. The method of claim 1 in which the first entity version and second entity version each comprise a plurality of blocks of stored content.

24. The method of claim 23 in which, after the expiration time of the shared block of stored content has passed, another block that was one of the plurality of blocks of stored content of the first entity version has an expiration time that has not yet passed.

25. The method of claim 1 in which, at a time when the shared block is no longer a part of any unexpired entity version, the block is discarded from the storage system and its space is reused.

26. The method of claim 25 in which the determination that the shared block is no longer a part of any unexpired entity version is made using the expiration time assigned to the shared block, and without checking expiration times assigned to entity versions.

27. The method of claim 26 in which entity versions are stored in a form in which, without the provision of information that is not stored persistently in the disk-based data storage system, the expiration times assigned to entity versions cannot be determined.

28. The method of claim 1 in which the contents of the first and second entity versions are not identical.

29. The method of claim 23 in which, after the expiration time is assigned to the first entity version and as long as it has not yet passed, the client cannot cause an unshared block of stored content that is a constituent only of the first entity version to be modified or deleted, and cannot cause the expiration time assigned to the unshared block to be changed to an earlier time.

30. The method of claim 29 in which, after the expiration time is assigned to the unshared block and before it has passed, the client causes the expiration time assigned to the unshared block to be changed to a later time.