Electrical computers and digital processing systems: virtual mac – Task management or control
Reexamination Certificate
1999-01-29
2004-06-29
An, Meng-Al T. (Department: 2126)
Electrical computers and digital processing systems: virtual mac
Task management or control
C707S793000
Reexamination Certificate
active
06757896
ABSTRACT:
BACKGROUND
1. Technical Field
The present invention relates generally to object stores and, in particular, to a method and apparatus that enables two or more computers to partially replicate object stores by allowing synchronization of only such objects contained in the stores that are intended to be shared among the stores.
2. Background Description
In general, an object is a collection of data and/or functions which, for example, modify the data. An object store is a collection of objects. The objects in the store can either be persistent or transient. The object store provides a set of application programming interfaces for manipulating (e.g., reading, modifying and deleting) objects in the store. An object store controller is an application written ‘on top’ of an object store that manipulates the contents of the store.
FIG. 1
is a diagram illustrating a system to which the present invention may be applied. The system
100
includes two computers (
102
a
,
102
b
). Each computer (
102
a
,
102
b
) respectively includes: an object store (
106
a
,
106
b
); an object store controller (
104
a
,
104
b
); at least one application (
120
a
,
120
b
); and a communication system (
108
a
,
108
b
). The controllers (
104
a
,
104
b
) are used by the applications (
120
a
,
120
b
) to access and modify the object stores (
106
a
,
106
b
). The communication systems (
120
a
,
120
b
) enable the (system) computers (
102
a
,
102
b
) to communicate with other computers. Further, the computers (
102
a
102
b
) may be either intermittently or continuously connected to one another via a communication network
112
.
The Mobile Network Computer Reference Specification (MNCRS) provides a method and apparatus for synchronizing the full content of two object stores (www.mncrs.org). Every object in a store is identified by a unique object identifier. Object stores are replicated among two or more computers. Hence, a single object (identified by its unique identifier) is replicated among those computers. Different replicas of an object are potentially updated on different computers. Two replicas of an object store are synchronized periodically. Synchronization is realized using a version data structure associated with each object.
FIG. 2A
is a diagram illustrating a conventional version vector data structure associated with each object in an object store. The version vector
202
includes a list of tuples
204
. Each tuple
204
contains a node identifier
206
and a clock value
208
. The node identifier
206
may be implemented as, for example, a simple integer that is associated with a particular computer (e.g.,
102
a
,
102
b
) in the system. The clock value may be implemented as an integer reflecting a logical value. Thus, the kth tuple in the version vector
202
represents the node identifier and the local clock value for a particular object at the kth computer.
When an object is updated or inserted in an object store of a computer, the tuple in the version vector corresponding to that computer is updated with the current local clock value at that computer. Then, the local clock value is incremented. The version vectors of an object and its replica are compared as follows: for every index k, the clock value of the kth tuple in the version vector of the object is compared with the clock value of the kth tuple in the version vector of the replica. Thus, when comparing two version vectors (of an object and its replica), the object's version vector is considered to be newer than the replica's version vector when all the clock values of the object's version vector are equal to or greater than all the corresponding clock values of the replica's version vector. Alternatively, the object's version vector is considered to be older than the replica's version vector when all the clock values of the object's version vector are less than or equal to all the corresponding clock values of the replica's version vector. If only some clock values of the object's version vector are greater than or equal to corresponding clock values in the replica's version vector and other clock values in the object's version vector are less than the corresponding clock values in the replica's version vector, then the object and its replica are considered to be ‘in conflict’.
The version vector of an object is incremented as follows: if the kth computer in the system is incrementing the version vector, the clock value in the kth tuple of the version vector is updated with the local clock value and then the local clock value is incremented. The content of the object is not altered.
Similar to each object in an object store, the store itself is associated with a summary version vector. The summary version vector of the store includes a list of tuples, each tuple containing a node identifier and a clock value. The clock value in the kth tuple in the summary version vector for a store is the maximum of the clock values in the kth tuples in the version vectors for all objects in the store. Hence, all objects in the store are, at most, as recent as the summary version vector of the store. As a result, when the version vector of an object in one store is compared with the summary version vector of a replica store, if the version vector of the object is strictly older than the summary version vector of the replica store, then it can be concluded that the replica store has seen this object already. However, if the version vector of the object is newer than or conflicts with the summary version vector of the replica store, then it can be concluded that the replica store may not have seen this object.
FIG. 2B
illustrates how two object stores perform a full synchronization in MNCRS. The controller for store
1
(‘store
1
controller’) requests the summary version vector of store
2
from the controller of store
2
(‘store
2
controller’) (step
210
). In response, the store
2
controller sends the store
2
summary version vector to the store
1
controller (step
212
). The store
1
controller determines which objects in store
1
are newer than, or conflict with, the summary version vector sent by store
2
(step
214
). The store
1
controller then sends those objects (updates) to the store
2
controller (step
216
) using its communication system
108
via the communication network
112
. As used herein, an update consists of an object's contents, its identifier, and its version vector. The object content part of an update can optionally be empty for an update that signifies deletion of an object.
The store
2
controller then applies those objects (updates) locally to the objects in store
2
(step
218
). Applying an update may consist of copying the replica object's contents to the local object, merging the replica object's contents with those of the local object, or simply keeping the original contents of the local object. In either case, the version vector of the local object is changed to a newer version vector reflecting that the object in store
2
has been synchronized with its replica in store
1
.
The store
2
controller first requests the summary version vector from the store
1
controller (step
220
). In response, the store
1
controller sends the store
1
summary version vector to the store
2
controller (step
222
). The store
2
controller determines which objects in store
2
are newer than, or conflict with, the summary version vector sent by store
1
(step
224
). The store
2
controller then sends those objects (updates) to the store
1
controller (step
226
) using its communication system
108
via the communication network
112
.
The store
1
controller then applies those objects (updates) locally to the objects in store
1
(step
228
). Accordingly, the version vector of the local object is changed to a newer version vector reflecting that the object in store
2
has been synchronized with its replica in store
1
. Thus, the two replicas have completed synchronization.
In the above method, each object in one store is synchronized with it
Cohen Norman H.
Mohindra Ajay
Purakayastha Apratim
An Meng-Al T.
F. Chau & Associates LLC
Herzberg Louis P.
International Business Machines - Corporation
Zhen Li B.
LandOfFree
Method and apparatus for enabling partial replication of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for enabling partial replication of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for enabling partial replication of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3365922