Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-31
2003-04-01
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06542907
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention generally relates to a method and system for data replication and replica distribution, and more particularly to a method and system for generation of bounded-length globally unique replica identifiers.
Description of the Related Art
Conventional systems for replicating data on multiple computing devices and synchronizing the replicas require a way to identify each replica uniquely. For example, Parker et al., “Detection of Mutual Inconsistency in Distributed Systems”,
IEEE Transactions on Software Engineering
SE-9, No. 3 (May 1983), pp. 240-247, describes the use of version vectors, which map replica identifiers to readings of logical clocks maintained at each replica, for tracking the relationships among different versions of data in a distributed system.
Petersen et al., “Flexible Update Propagation for Weakly Consistent Replication”, SIGOPS '97
: Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles
, Oct. 5-8, 1997, Saint-Malo, France, pp. 288-301, describes replica creation in the Bayou system. In this system, each replica of a database, other than the original one, is created as a copy of some existing replica. Thus, each replica, other than the original one, can be thought of as a child of a particular parent replica. (This approach precludes scenarios in which two independently created collections of data are merged by synchronizing them with each other, so that they become replicas of each other, each holding the union of their previous contents.) Since the device holding the child replica must contact the device holding the parent replica to obtain its initial contents, the child replica can also obtain its identifier from the device holding the parent replica. The identifier for the child replica, a two part identifier, includes the identifier of the parent replica and an integer uniquely distinguishing the new child replica from all other children of that parent.
U.S. Pat. No. 5,884,322 to Sidhu et al. describes a system in which a parent allocates a set of unique replica identifiers to a child. This set consists of the replica identifier for the child itself and the replica identifiers that can potentially be generated for the descendants of the child. The child, in turn allocates subsets of this set to its own children. However, Sidhu et al. does not stipulate the use of fixed-length identifiers, a specific mechanism for the distributed generation of unique identifiers, or a strategy for partitioning the available identifiers based on an entity's generation number. Similarly, U.S. Pat. No. 5,522,077 to Cuthbert et al. describes a system in which a client obtains a range of contiguous unique-identifier values from a central server, and may later return unused values to the server for reallocation.
U.S. Pat. No. 5,414,841 to Bingham et al. describes another centralized system in which unique identifiers can vary in length. Similarly, the replica identifiers described by Petersen et al. (supra) are not fixed length. Since each replica's identifier includes, as a component, the identifier of its parent replica, the length of a replica identifier grows with each generation of replicas. (If a tree is constructed to describe parent-child relationships, a generation corresponds to a level of the tree.) This is acceptable in an environment where a few replicas serve as parents of many children, so that there are few generations. However, in an environment in which many child replicas are themselves parents (so that a tree describing parent-child relationships has many levels), replica identifiers and the data structures that incorporate them, such as version vectors,.can quickly grow unacceptably large.
Bingham et al. (supra), Cuthbert et al. (supra), and the Cedar software version management system (U.S. Pat. No. 4,558,413 to Schmidt and Lampson) rely on central generation to ensure uniqueness of identifiers. Similarly, U.S. Pat. No. 5,640,608 to Dockter et al. describes the operation of a central tag server that generates tag values in ascending order, hands off blocks of unique tag values to clients in shared volatile storage, and keeps a nonvolatile record of the highest tag value generated so far, ensuring that duplicate tag values will not be generated upon recovery from a failure that destroys the contents of volatile storage. U.S. Pat. No. 5,304,992 to Harashima describes the distribution of centrally generated unique identifiers over a common communication line.
However, there are several advantages to assigning unique replica identifiers without coordinating through a central server:
The elements of the distributed system may have a peer relationship, in which no one device is designated as a server, and there may be no direct connection between an arbitrary pair of devices.
Reliance on coordination with a particular device (e.g., a central server or the like) means that a new replica cannot be created when that device is unavailable (e.g., because either the particular device or the network has failed).
Reliance on coordination through a central server precludes creating new replicas within mobile work groups (groups of colleagues traveling together whose devices are accessible to each other but not to a fixed network).
Channeling all requests for new replica identifiers through a central server can create a system bottleneck.
However, distributing (i.e., decentralizing) the assignment of replica identifiers to various devices raises the problem of ensuring that the generated identifiers are unique (i.e., that two devices unable to contact each other do not generate the sane identifier). Pouzin and Zimmerman, “A Tutorial on Protocols”,
Proceedings of the IEEE
66, No. 11 (November 1978), pp. 1346-1370, discusses the distributed generation of unique identifiers by hierarchical concatenation of a unique domain identifier (identifying, for example, a host computer) with an identifier that is unique within that domain. Richard W. Watson, “Identifiers (Naming) in Distributed Systems”, in Lampson and Siegert, eds.,
Distributed Systems—Architecture and Implementation, an Advanced Course
, Springer-Verlag, New York, 1981, classifies hierarchical concatenation as a special case of an identification scheme built around a sequence of contexts, in which an identifier for one context is mapped by that context into an identifier meaningful in the next context. Watson describes a distributed architecture in which globally unique identifiers consist of a server process address and a local name unique among the names generated by a server process. There may be many server processes generating unique identifiers, each having a unique server address assumed to be already known to the interprocess communication service that delivers a request for a new unique identifier to the server process.
Many inventions are concerned with the distributed generation of unique identifiers by hierarchical concatenation. U.S. Pat. No. 5,117,351 to Miller discloses a system for distributed generation of unique identifiers. Each unique identifier consists of a node identifier uniquely identifying a node of the distributed system, a monotonically increasing per-node time stamp (based on the node's system clock, but incremented when necessary to avoid duplicate use of the same time stamp), a random number used to reduce the probability of generating a duplicate identifier in case the system clock is reset, and a version number identifying the version of the system that generated the identifier, to prevent collisions with identifiers that may be generated by different mechanisms in the future. U.S. Pat. No. 4,792,921 to Corwin is similar, supporting distributed generation of identifiers containing a node identifier (in this case, a telephone number associated with the node) and a time stamp based on a real-time clock that is posited to tick at least once between the generation of any two identifiers. U.S. Pat. No. 5,815,710 to Martin et al. describes the generation of unique identifi
McGinn & Gibb PLLC
Metjahic Safet
Nguyen Merilyn
Zarick, Esq. Gail H.
LandOfFree
Method and apparatus for decentralized, invertible... 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 decentralized, invertible..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for decentralized, invertible... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3074518