Object replication using information quality of service

• US 7,596,585 B2
• Filed: 11/03/2004
• Issued: 09/29/2009
• Est. Priority Date: 11/03/2004
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Richardson, James P.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): RADTKE, MARK A
• Application Number:
  US10/980,778
• Publication Number:
  US 20060106894A1
• Time in Patent Office: 1,791 Days
• Field of Search: 707/203, 711161-162, 711/151
• US Class Current: 707/634
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A database replication function for a local object and one or more destination objects, where one or more local applications make requests to the source objects is disclosed. A request logging function records requests sent by the one or more local applications into a memory log. An update propagation function determines which source object states must be propagated to one or more destination objects based on information quality of service accuracy requirements.

Claims

1. A database system, the system comprising:

a computer executing a database replication function for a local object and one or more destination objects, where one or more local applications make requests to the local object, the database replication function comprising;

a request logging function for recording a sequence of requests sent by the one or more local applications to the local object; and

an update propagation function, wherein the update propagation function determines which local object states to propagate to the one or more destination objects, based on information quality of service accuracy requirements;

wherein the update propagation function determines which local object states to propagate by determining whether present local object state meets a propagation condition; and

wherein the information quality of service accuracy requirements include parameters (Δ

s, Δ

t) and wherein the propagation condition is met if a magnitude of the local object state change from s_i to s_j is greater than or equal to the parameter Δ

s , and the state s_j that causes the local object state change from s_i to s_j to be greater than or equal to the parameter Δ

s has existed on the local object for a time greater than or equal to Δ

t without being propagated to the destination object.

2. The database system of claim 1, wherein the request logging function further filters out requests that do not cause a state change in the local object and to record a sequence of requests sent by the one or more local applications to the local object that do cause a state change in the local object.

3. The database system of claim 1, where Δ

t is a function of Δ

s such that larger local object state changes are propagated sooner than relatively smaller changes.

4. The database system of claim 1, wherein the magnitude of the local object state change from s_i to s_j is measured using a distance function.

5. The database system of claim 1, wherein the update propagation function propagates a first local object state to the destination object by outputting a sequence of updates based on a sequence of requests from the request logging function.

6. The database system of claim 5, wherein the update propagation function applies a compression algorithm that transforms the sequence of requests from the request logging function into a compressed sequence of requests to produce the sequence of updates.

7. The database system of claim 6, wherein the compression algorithm applies a set of compression transformations to the sequence of requests from the request logging function interactively.

8. The database system of claim 7, wherein the compression algorithm reorders one or more commutative requests.

9. The database system of claim 7, wherein the update propagation function further propagates a local object state to the destination object based on information quality of service timing requirements.

10. The database system of claim 9, wherein the update propagation function is executed cyclically, with a cycle period chosen so that the information quality of service timing requirements are not exceeded.

11. The database system of claim 1, wherein the local object and the destination object are both container objects.

12. A database system comprising:

a first computer having a source object, the source object having a container object structure, the source object further having one or more contained objects;

at least one second computer having one or more destination objects, the one or more destination object having the same container object structure as the source object;

the first compute executing one or more local applications, the one or more local applications making requests to the source object;

a request logging function recording a sequence of requests sent by the one or more local applications to the source object;

an update propagation function, wherein the update propagation function determines which source object states to propagate to the one or more destination objects, based on information quality of service accuracy requirements;

wherein the update propagation function determines which source object states must be propagated by determining whether one or more of the contained objects of the source object state meet a propagation condition,

wherein the information quality of service accuracy requirements include parameters (Δ

s, Δ

t) for one or more of the contained objects,

wherein the propagation condition for a contained object is met if the magnitude of the contained object state change from s_i to s_j is greater than or equal to the parameter Δ

s, and the state s_j that causes the contained object state change from s_i to s_j to be greater than or equal to the parameter Δ

s has existed on the contained object for a time greater than or equal to Δ

t without being propagated to the destination object, and

wherein the magnitude of the contained object state change from s_i to s_j is measured using a distance function.

13. The database system of claim 12, wherein the request logging function further filters out requests that do not cause a state change in the source object and records a sequence of requests sent by the one or more applications to the source object that do cause a state change in the source object.

14. The database system of claim 12 wherein the update propagation function propagates a source object state to the destination object by outputting a sequence of updates based on a sequence of requests from the request logging function,

wherein the update propagation function transforms the sequence of requests from the request logging function into a partially-ordered set of requests based on a container specification,

wherein the update propagation function applies a compression algorithm that transforms the partially-ordered set of requests into a compressed sequence of requests to produce the sequence of updates, and

wherein the update propagation function is executed cyclically, with a cycle period chosen so that the information quality of service timing requirements are not exceeded.

15. The database system of claim 12, further comprising:

an update reception function, wherein the update reception function is adapted to update the source object based on object states received from the one or more destination objects.

16. A method for propagating database updates, the method comprising:

logging requests made to a source object by one or more applications, the source object stored on a computer readable medium;

determining a magnitude of a source object state change since time of a most recent previous update propagation;

determining when the magnitude of the source object state change is greater than or equal to an information quality of service accuracy parameter Δ

s;

determining when the present source object state causes the magnitude of the source object state change to be greater than or equal to the information quality of service accuracy parameter Δ

s for a time greater than or equal to an information quality of service accuracy parameter Δ

t without being propagated to the destination object; and

propagating a sequence of updates based on the logged requests to one or more destination objects, when the magnitude of the source object state change is greater than or equal to Δ

s and the present source object state has existed on the source object for a time greater than or equal to Δ

t without being propagated to the one or more destination objects.

17. The method of claim 16, further comprising:

applying a compression algorithm that transforms the logged requests into a compressed sequence of requests to produce the sequence of updates.

18. The method of claim 16, wherein the magnitude of the source object state change is determined by a distance function.

19. The method of claim 16, further comprising:

determining how long of a duration of time is tolerable to propagate the source object state to the one or more destination objects once the magnitude of the source object state change is greater than or equal to Δ

s, and wherein the propagating a sequence of updates is completed with that duration of time.

20. A method for propagating database updates, the method comprising:

logging requests made to a source object by one or more applications, the source object stored on a computer readable medium;

periodically determining when a magnitude of a source object state change, since a time of a most recent previous update propagation, is greater than or equal to an information quality of service accuracy parameter Δ

s and when a present source object state has existed on the source object for a time greater than or equal to an information quality of service accuracy parameter Δ

t without being propagated to the destination object;

when the magnitude of the source object state change is greater than or equal to Δ

s and the present source object state causes the magnitude of the source object state change to be greater than or equal to the information quality of service accuracy parameter Δ

s has existed on the source object for a time greater than or equal to Δ

t without being propagated to the one or more destination objects, applying a compression algorithm that transforms the logged requests into a compressed sequence of requests; and

propagating the compressed sequence of request to one or more destination objects, wherein the cycle period for periodically determining the magnitude of the source object state change is chosen so that information quality of service timing requirements are not exceeded.

21. A method for propagating database updates, the method comprising:

logging requests made to a source object by one or more applications, the source object stored on a computer readable medium;

determining a magnitude of a source object state change since a time of a most recent previous update propagation;

determining when the magnitude of the source object state change is greater than or equal to an information quality of service accuracy parameter Δ

s; and

when the magnitude of the source object state change is greater than or equal to Δ

s and after a present source object state causes the magnitude of the source object state change to be greater than or equal to the information quality of service accuracy parameter Δ

s has existed on the source object for a time greater than or equal to Δ

t, propagating a sequence of updates based on the logged requests to one or more destination databases.

22. A method for propagating database updates, the method comprising:

logging requests made to a source object by one or more applications, the source object stored on a computer readable medium;

determining a magnitude of a source object state change since a time of a most recent previous update propagation;

determining when a magnitude of the source object state change is greater than or equal to an information quality of service accuracy parameter Δ

s;

when the magnitude of the source object state change is greater than or equal to Δ

s and after a present source object state causes the magnitude of the source object state change to be greater than or equal to the information quality of service accuracy parameter Δ

s for a time greater than or equal to Δ

t, applying a compression algorithm that transforms the logged requests into a compressed sequence of requests to produce the sequence of updates; and

propagating the compressed sequence of updates based on the logged requests to one or more destination databases.

23. A computer-readable medium having computer-executable instructions for performing a method for propagating database updates, the method comprising:

logging requests made to a source object by one or more applications;

determining a magnitude of a source object state change since the time of a most recent previous update propagation;

determining when the magnitude of the source object state change is greater than or equal to an information quality of service accuracy parameter Δ

s ;

determining when a present source object state causes the magnitude of the source object state change to be greater than or equal to the information quality of service accuracy parameter Δ

s for a time greater than or equal to an information quality of service accuracy parameter Δ

t without being propagated to the destination object; and

propagating a sequence of updates based on the logged requests to one or more destination databases, if the magnitude of the source object state change is greater than or equal to Δ

s and the present source object state has existed on the source object for a time greater than or equal to Δ

t without being propagated to the one or more destination objects.

24. The method of claim 23, further comprising:

applying a compression algorithm that transforms the logged requests into a compressed sequence of requests to produce the sequence of updates.

25. The method of claim 23, wherein the magnitude of the source object state change is determined by a distance function.

26. The method of claim 23, further comprising:

determining how long of a duration of time is tolerable to propagate the source object state to the one or more destination objects once the magnitude of the source object state change is greater than or equal to Δ

s , and wherein the propagating a sequence of updates is completed with that duration of time.