Update mechanism for computer storage container manager

• US 5,873,097 A
• Filed: 12/17/1996
• Issued: 02/16/1999
• Est. Priority Date: 05/12/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Ruben, Ira L., Harris, Jared M.
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/768,339
• Time in Patent Office: 791 Days
• Field of Search: 707/100, 707/103, 707/200-204
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Methods and data structures which permit information to be stored as objects in target containers and update containers. A target container defines a first state of the information, and the update container, which can point to the target container, identifies changes to the information in the first state which would be sufficient to update the first information state to a second information state. Update containers may be nested to any depth. When an application program opens an update container, the procedure searches down the chain until it finds the ultimate target container. It then creates in-memory structures for providing access to the objects and value data represented in such container. The procedure then works its way back up the chain, performing the changes on the in-memory structure, which are called for in each of the update containers. New modifications made after this process is complete, are recorded in memory, and when committed, are written out into a new update container which references the container that the application program originally opened. The changes which are identified in an update container, if they represent modifications to an object in an underlying container, refer to that object logically rather than physically. Multiple concurrent (parallel) updaters are supported, since more than one update container can refer to the same target container. Thus each updater has an independent view of the information being updated. The mechanism facilitates reconciliation of concurrent updates since it maintains a record of the changes made.

Claims

1. A method for updating information from a first persistently stored information state to a second persistently stored information state, said information being represented in said first information state by a target container containing a plurality of objects, comprising the steps of:

determining container changes sufficient to modify said first information state to said second information state;

committing said second information state by, at least in part, persistently storing, in a structure logically separate from said target container, an update container including objects identifying all of said container changes, such that said first information state remains readable without requiring application of change records relative to said second information state; and

including a table of contents (TOC) in said update container that includes information about every object in the update container.

2. A method according to claim 1, wherein said step of persistently storing comprises the step of persistently storing change instructions in said update container.

3. A method according to claim 1, wherein said container changes include insertion of a new object, and wherein said step of persistently storing comprises the step of persistently storing said new object in said update container.

4. A method according to claim 1, wherein said container changes include deletion of a particular object from said target container, and wherein said step of persistently storing comprises the step of persistently storing in said update container an object identifier persistently associated with said particular object.

5. A method according to claim 1, wherein said container changes include a plurality of deletions of particular objects from said target container, and wherein said step of persistently storing comprises the step of persistently storing in said update container a list of object identifiers persistently associated with said particular objects.

6. A method according to claim 1, wherein said container changes include modification of a particular object in said target container from a first object state being its state in said first information state, to a second object state being its state in said second information state, and wherein said step of persistently storing comprises the step of:

persistently storing in said update container an object identifier persistently associated with said particular object; and

persistently storing in said update container in correspondence with said object identifier, an identification of object changes which would be sufficient to update said particular object from said first object state to said second object state.

7. A method according to claim 6, wherein said particular object in said first object state includes at least one value identifying value data, wherein said object changes include modification of said value data from a first value data state being its state in said first object state, to a second value data state being its state in said second object state, and wherein said step of persistently storing an identification of object changes comprises the step of:

persistently storing in said update container in correspondence with said object identifier, an identification of said value data in said particular object, and an identification of value data changes which would be sufficient to update said value data from said first value data state to said second value data state.

8. A method according to claim 6, wherein each of said objects in said target container includes at least one value header designating value data, and wherein said step of persistently storing an identification of object changes comprises the steps of:

writing to said update container as new value data, change instructions sufficient to modify the value data of said particular object from a first value data state to a second value data state; and

writing to said update container a change instruction calling for said new value data to be inserted into said particular object.

9. A method according to claim 1, wherein said container changes stored in said step of persistently storing include no changes which are in excess of those sufficient to update said information state to said second information state.

10. A method according to claim 1, wherein said target container is stored in a first file, and wherein said step of persistently storing an update container comprises the step of storing said update container in a second file distinct from said first file.

11. A method according to claim 1, wherein said target container is stored in a first file, and wherein said step of persistently storing an update container comprises the step of appending said update container to said first file.

12. A method according to claim 1, wherein said step of determining container changes comprises the steps of:

representing said first information state in non-persistent storage;

manipulating said information in non-persistent storage using at least orne change steps said second information state being defined by the state of said information after said step of manipulating; and

subsequently to said step of representing,

recording at least all non-superfluous ones of said change steps,

said container changes beina the change steps recorded in said step of recording.

13. A method according to claim 12, wherein said target container comprises a prior target container and a prior update container, said prior target container representing said information in a prior information state, and wherein said step of representing said first information state in non-persistent storage comprises the steps of:

using said prior target container to represent in non-persistent storage said prior information state; and

manipulating said information in non-persistent storage in response to change steps identified in said prior update container.

14. A method according to claim 1, wherein said step of persistently storing comprises the steps of:

writing change instructions to said update container; and

subsequently writing to said update container an indication that said update container is valid.

15. A method according to claim 14, wherein said change instructions include a first change instruction to be executed, and wherein said step of subsequently writing comprises the step of writing to said update container a label identifying said first change instruction.

16. A method according to claim 1, wherein said step of determining container changes sufficient to modify said first information state to said second information state comprises the steps of:

producing a temporary representation of said information in said first information state in unstable storage in dependence upon said target container;

modifying said temporary representation of said information in said first information state to produce a temporary representation of said information in said second information state in unstable storage;

determining said container changes from said temporary representation of said information in said second information state in unstable storage.

17. A method according to claim 1, further comprising the steps of:

determining second container changes sufficient to modify said first information state to a third information state; and

committing said third information state by, at least in part, persistently storing, in a structure logically separate from said target container and from said update container, a second update container identifying all of said second container changes, such that said first information state remains readable without requiring application of change records relative to said second or third information state, and such that said second information state remains readable without requiring application of change records from said second update container.

18. A method according to claim 1, wherein:

said target container is persistently stored on a first medium; and

said step of persistently storing an update container comprises the step of persistently storing said update container on a second medium different from said first medium.

19. A method according to claim 18, wherein said first medium is a read-only medium, and wherein said second medium is a read/write medium.

20. The method according to claim 1, wherein:

said TOC is maintained logically separate from said container changes; and

all format information about every object stored in said update container is maintained in said TOC.

21. The method according to claim 20, wherein the format of each object stored in said update container is different.

22. A method according to claim 20, wherein said container changes include modification of a particular object in said target container from a first object state being its state in said first information state, to a second object state being its state in said second information state, and wherein said step of persistently storing comprises the step of:

persistently storing in said update container an object identifier persistently associated with said particular object; and

persistently storing in said update container in correspondence with said object identifier, an identification of object changes which would be sufficient to update said particular object from said first object state to said second object state.

23. A method according to claim 20, wherein said step of determining container changes sufficient to modify said first information state to said second information state comprises the steps of:

producing a temporary representation of said information in said first information state in unstable storage in dependence upon said target container;

modifying said temporary representation of said information in said first information state to produce a temporary representation of said information in said second information state in unstable storage;

determining said container changes from said temporary representation of said information in said second information state in unstable storage.

24. A method for preparing information from persistent storage for further processing in temporary storage, said information being represented in said persistent storage in both a first information state and a second information state, comprising the steps of:

accessing a persistently stored target container representing a plurality of objects which identify said information in said first information state;

producing a first temporary representation of said information in said first information state in dependence upon said target container;

accessing a persistently stored update container identifying container changes which are sufficient to modify said information from said first information state to said second information state, including the substeps of,

accessing a table of contents (TOC) containing format information of the container changes, and

utilizing the format information to determine said container changes;

applying said container changes to said first temporary representation of said information to form a temporary representation of said information in said second information state; and

producing a second temporary representation of said information in said first information state in dependence upon said target container, said second temporary representation of said first information state existing simultaneously with said temporary representation of said second information state.

25. A method according to claim 24, wherein said step of accessing a persistently stored target container comprises the steps of:

accessing said persistently stored update container to obtain a reference to said target container; and

accessing said target container in response to said reference.

26. A method according to claim 24, wherein said step of producing a first temporary representation in dependence upon said target container comprises the steps of:

accessing a persistently stored prior target container representing a plurality of objects which identify said information in a prior information state;

producing a prior temporary representation of said information in said prior information state in dependence upon said prior target container;

accessing a persistently stored prior update container identifying prior container changes which are sufficient to update said information from said prior information state to said first information state; and

applying said prior container changes to said prior temporary representation of said information.

27. A method according to claim 24, further comprising the steps of:

modifying said information in temporary storage to produce a third information state for said information; and

persistently storing a second update container identifying container changes which would be sufficient to update said information from said second information state to said third information state.

28. A method according to claim 24, wherein said information is represented in persistent storage also in a third information state, further comprising the steps of:

accessing a persistently stored second update container identifying second container changes which are sufficient to modify said information from said first information state to said third information state; and

applying said second container changes to said second temporary representation of said information to form a temporary representation of said information in said third information state.

29. A method according to claim 28, wherein said temporary representation of said third information state exists simultaneously with said temporary representation of said second information state.

30. A method according to claim 24, wherein:

said step of accessing a persistently stored target container comprises the step of accessing said target container from a first medium; and

said step of accessing a persistently stored update container comprises the step of accessing said update container from a second medium different from said first medium.

31. A method according to claim 30, wherein said first medium is a read-only medium and wherein said second medium is a read/write medium.

46. A storage medium according to claim 24, wherein said target container comprises a prior target container and a prior update container, said prior target container representing said information in a prior information state, and wherein said third computer instructions comprise:

computer instructions which use said prior target container to represent in non-persistent storage said prior information state; and

computer instructions which manipulate said information in non-persistent storage in response to change steps identified in said prior update container.

32. A method for manipulating information, said information being represented in a first information state by a persistently stored target container containing a plurality of objects, comprising the steps of:

determining container changes sufficient to modify said first information state to a second information state;

committing said second information state by, at least in part, persistently storing, in a structure logically separate from said target container, an update container including objects identifying said container changes such that said first information state remains readable without requiring application of change records relative to said second information state;

including a table of contents (TOC) in the update container that includes information about every object in the update container;

subsequently accessing said target container;

producing a temporary representation of said information in said first information state in dependence upon said subsequently accessed target container;

accessing said update container; and

applying said container changes persistently stored in said update container to said temporary representation of said information.

33. A method according to claim 32, further comprising the steps of:

manipulating said temporary representation of said information using at least one subsequent change step; and

persistently storing a second update container identifying said at least one subsequent change step.

34. A storage medium carrying a collection of software procedures for updating information from a first persistently stored information state to a second persistently stored information state, said information being represented in said first information state by a target container containing a plurality of objects, said procedures including:

first computer instructions which determine container changes sufficient to modify said first information state to said second information state;

second computer instructions which commit said second information state by, at least in part, persistently store, in a structure logically separate from said target container, an update container including objects identifying said container changes, such that said first information state remains readable without requiring application of change records relative to said second information state; and

including a table of contents (TOC) in said update container that includes information about every object in the update container.

35. A storage medium according to claim 34, wherein said second computer instructions comprise computer instructions which persistently store change instructions in said update container.

36. A storage medium according to claim 34, wherein said container changes include insertion of a new object, and wherein said second computer instructions comprise computer instructions which persistently store said new object in said update container.

37. A storage medium according to claim 34, wherein said container changes include deletion of a particular object from said target container, and wherein said second computer instructions comprise computer instructions which persistently store in said update container an object identifier persistently associated with said particular object.

38. A storage medium according to claim 34, wherein said container changes include a plurality of deletions of particular objects from said target container, and wherein said second computer instructions comprise computer instructions which persistently store in said update container a list of object identifiers persistently associated with said particular objects.

39. A storage medium according to claim 34, wherein said container changes include modification of a particular object in said target container from a first object state being its state in said first information state, to a second object state being its state in said second information state, and wherein said second computer instructions comprise:

third computer instructions which persistently store in said update container an object identifier persistently associated with said particular object; and

fourth computer instructions which persistently store in said update container in correspondence with said object identifier, an identification of object changes which would be sufficient to update said particular object from said first object state to said second object state.

40. A storage medium according to claim 39, wherein said particular object in said first object state includes at least one value identifying value data, wherein said object changes include modification of said value data from a first value data state being its state in said first object state, to a second value data state being its state in said second object state, and wherein said fourth computer instructions comprise computer instructions which persistently store in said update container in correspondence with said object identifier, an identification of said value data in said particular object, and an identification of value data changes which would be sufficient to update said value data from said first value data state to said second value data state.

41. A storage medium according to claim 39, wherein each of said objects in said target container includes at least one value header designating value data, and wherein said fourth computer instructions comprise:

computer instructions which write to said update container as new value data, change instructions sufficient to modify the value data of said particular object from a first value data state to a second value data state; and

computer instructions which write to said update container a change instruction calling for said new value data to be inserted into said particular object.

42. A storage medium according to claim 34, wherein said container changes stored by said second computer instructions include no changes which are in excess of those sufficient to update said information state to said second information state.

43. A storage medium according to claim 34, wherein said target container is stored in a first file, and wherein said second computer instructions comprise computer instructions which store said update container in a second file distinct from said first file.

44. A storage medium according to claim 34, wherein said target container is stored in a first file, and wherein said second computer instructions comprise computer instructions which append said update container to said first file.

45. A storage medium according to claim 34, wherein said first computer instructions comprise:

third computer instructions which represent said first information state in non-persistent storage;

fourth computer instructions which manipulate said information in non-persistent storage using at least one change step, said second information state being defined by the state of said information after execution of said sixth computer instructions; and

fifth computer instructions which record at least all non-superfluous ones of said change steps, execution of said third computer instructions preceding execution of said fifth computer instructions,

said container changes being the change steps recorded by said fifth computer instructions.

47. A storage mediunm according to claim 34, wherein said second computer instructions comprise:

third computer instructions which write change instructions to said update container; and

fourth computer instructions which, after execution of said third computer instructions, write to said update container an indication that said update container is valid.

48. A storage medium according to claim 47, wherein said change instructions include a first change instruction to be executed, and wherein said fourth computer instructions comprise computer instructions which write to said update container a label identifying said first change instruction.

49. A new storage medium according to claim 34, wherein said first computer instructions include:

computer instructions which produce a temporary representation of said information in said first information state in unstable storage in dependence upon said target container;

computer instructions which modify said temporary representation of said information in said first information state to produce a temporary representation of said information in said second information state in unstable storage; and

computer instruction which determine said container changes from said temporay representation of said information in said second information state in unstable storage.

50. A storage medium according to claim 34, further comprising:

computer instructions which determine second container changes sufficient to modify said first information state to a third information state; and

computer instructions which commit said third information state by, at least in part, persistently storing, in a structure logically separate from said target container and from said update container, a second update container identifying all of said second container changes, such that said first information state remains readable without requiring application of change records relative to said second or third information state, and such that said second information state remains readable without requiring application of change records from said second update container.

51. A storage medium according to claim 34, wherein:

said target container is persistently stored on a first medium; and

said second computer instructions include computer instructions which persistently store said update container on a second medium different from said first medium.

52. A storage medium according to claim 51, wherein said first medium is a read-only medium, and wherein said second medium is a read/write medium.

53. A storage medium carrying a collection of software procedures for retrieving information from persistent storage for further processing in temporary storage, comprising:

first computer instructions which access a persistently stored target container representing a plurality of objects which identify said information in a first information state;

second computer instructions which produce a first temporary representation of said information in said first information state in dependence upon said target container;

third computer instructions which access a persistently stored update container identifying container changes which are sufficient to modify said information from said first information state to a second information state, which include instructions for,

accessing a table of contents (TOC) containing format information of the container changes, and

utilizing the format information to determine said container changes;

fourth computer instructions which apply said container changes to said first temporary representation of said information; and

computer instructions which produce a second temporary representation of said information in said first information state in dependence upon said target container, said second temporary representation of said first information state existing simultaneously with said temporary representation of said second information state.

54. A storage medium according to claim 53, wherein said first computer instructions comprise:

computer instructions which access said persistently stored update container to obtain a reference to said target container; and

computer instructions which access said target container in response to said reference.

55. A storage medium according to claim 53, wherein said second computer instructions comprise:

computer instructions which access a persistently stored prior target container representing a plurality of objects which identify said information in a prior information state;

computer instructions which produce a prior temporary representation of said information in said prior information state in dependence upon said prior target container;

computer instructions which access a persistently stored prior update container identifying prior container changes which are sufficient to update said information from said prior information state to said first information state; and

computer instructions which apply said prior container changes to said prior temporary representation of said information.

56. A storage medium according to claim 53, further comprising:

computer instructions which modify said information in temporary storage to produce a third information state for said information; and

computer instructions which persistently store a second update container identifying container changes which would be sufficient to update said information from said second information state to said third information state.

57. A storage medium according to claim 53, wherein said information is represented in persistent storage also in a third information state, further comprising:

computer instructions which access a persistently stored second update container identifying second container changes which are sufficient to modify said information from said first information state to said third information state; and

computer instructions which apply said second container changes to said second temporary representation of said information to form a temporary representation of said information in said third information state.

58. A storage medium according to claim 57, wherein said temporary representation of said third information state exists simultaneously with said temporary representation of said second information state.

59. A storage medium according to claim 53, wherein said persistently stored target container is stored on a first medium, and wherein said persistently stored update container is stored on a second medium different from said first medium.

60. A storage medium according to claim 59, wherein said first medium is a read-only medium and wherein said second medium is a read/write medium.

61. A storage medium carrying a collection of software procedures for manipulating information, said information being represented in a first information state by a persistently stored target container containing a plurality of objects, comprising:

first computer instructions which determine container changes sufficient to modify said first information state to a second information state;

second computer instructions which commit said second information state by, at least in part, persistently storing, in a structure logically separate from said target container, an update container identifying said container changes such that said first information state remains readable without requiring application of change records relative to said second information state, and a table of contents (TOC) in said update container that includes information about every object in the update container;

third computer instructions which, after execution of said second computer instructions, access said target container;

fourth computer instructions which produce a temporary representation of said information in said first information state in dependence upon said subsequently accessed target container;

fifth computer instructions which access said update container; and

sixth computer instructions which apply said container changes persistently stored in said update container to said temporary representation of said information.

62. A storage medium according to claim 61, further comprising:

computer instructions which manipulate said temporary representation of said information using at least one subsequent change step; and

computer instructions which persistenly store a second update container identifying said at least one subsequent change step.

63. A computer implemented persistent storage having:

a first chain of at least two sequentially associated containers including a top container and a bottom container, wherein,

each of said containers in said chain except said top container being a prior container to a respective next container in said chain,

each of said containers in said chain except said bottom container containing a reference to the respective prior container in said chain and each of said containers representing information in a respective state, and

said bottom container having a first information state stored therein, and

at least one of said containers representing said information as a plurality of objects, including a table of contents (TOC) that includes information about every object in the container, each given one of said containers except said bottom container identifying, container changes sufficient to update said information from the state represented by the prior container to the state represented by the given container.

64. Storage according to claim 63, further comprising a branch chain of at least two sequentially associated branch containers, said branch chain including a top branch container not being in said first chain and a bottom branch container being one of said containers in said first chain, each of said containers in said branch chain except said bottom branch container containing a reference to a respective prior container in said branch chain.

65. Storage according to claim 63, wherein at least two of said containers are stored in different files.

66. Storage according to claim 65, wherein said different files are stored on different media.

67. Storage according to claim 63, wherein at least two sequentially associated ones of said containers are stored in a single file.

68. Storage according to claim 63, wherein said bottom container represents said information as objects, and wherein said container changes in said given container are identified at least in part by a change instruction identifying a change selected from the group consisting of deletion of a specified object and modification of a specified object.

69. Storage according to claim 68, wherein each of said objects has associated therewith at least one property, and each property has associated therewith at least one value, and wherein said change instruction identifies a change which comprises modification of a specified object,

wherein said modification is selected from the group consisting of:

(a) deletion of a specified property of said specified object, and all values associated therewith;

(b) insertion of a specified new value in association with a specified property of said specified object; and

(c) a combined insertion of a specified new property in association with said specified object and insertion of a specified new value in association with said new property.

70. Storage according to claim 69, wherein said modification includes said combined insertion modification, and wherein said specified new value includes at least one value change instruction identifying a modification to be made to said at least one value of said specified object.