Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-21
2003-03-25
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06539381
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to distributed databases and, more particularly, to synchronizing database information over a distributed communications network.
2. Related Art
As the use of computer networks grows, the use of distributed databases for storing data has become commonplace. Distributed databases are databases wherein one or more portions of the database are divided and/or replicated (copied) to different computer systems. These portions of the database are commonly referred to in the art as “partitions.” The act of segmenting a database into partitions is commonly referred to as “partitioning.” Partitions are generally distributed throughout a communication network among separate distributed systems to allow access to the database in a more efficient manner than can be achieved with a centralized database. Partitions may be made more easily accessible to users that access information within the particular partition to increase overall database performance. For example, partitions may be located geographically and/or logically closer to database users that use a particular partition.
Also, a distributed database system may include replicas, or copies of a database or database partition, which are located on different systems. The term “database replica” or “replica” will be used herein to refer generally to such replicas regardless of whether the replica contains an entire database or a partition thereof. The set of all database replicas for a partition are referred to as a replica set. By having multiple copies of the database, a database can be recovered if one system (and one copy) experiences problems. Also, distributed databases allow the data to be managed by multiple servers, thus increasing database throughput. However, there are drawbacks to conventional techniques to maintain distributed databases. One problem includes synchronizing database information among the distributed database or database partitions. If a database replica is unreachable, there will be no convergence in the database data among the partitions.
Convergence is generally experienced when each of the database replicas contains the same information. As users add information to the individual replicas, database convergence is critical; a user must know that the data upon which they are relying is current and agrees with the data of the other database replicas. In some distributed database systems, there is an N×N connectivity problem that impedes database convergence. In an N×N system, each system must be able to contact all other systems directly. For instance, each system having a database replica that can achieve a local database change must be able to contact all other replicas to provide those replicas with that change.
In a large database system, there are several reasons why connectivity between database servers cannot be guaranteed. There may be economic limitations to complete connectivity. Transmission of database information over expensive communications links may be cost-prohibitive. Further, there may be transport limitations. In particular, it may not be possible for all database servers to communicate in a same communication protocol across the network. In some situations, two or more computer systems may not be able to communicate at all. There may also be security limitations. With the advent of firewalls and secure networks, allowing such systems to communicate may not be desired. Lastly, some systems may not be available because of a network failure, disconnection from the communication network, or may not be operable or powered on during a time when synchronization is needed.
In addition to distributing database information, synchronization operations may need to be performed to complete certain operations, such as a partitioning operation. In one such partitioning operation, one system, referred to as the “master” or primary system, is designated as the master for a database partition (termed the “master replica”) is responsible for controlling the partitioning operation. The master system generally stores the master replica in a memory system located on the master.
Typically, a database administrator will control the master to create or modify a partition. To propagate changes to the partition, the master typically requires contact with all systems that will participate in a partitioning operation before the partitioning operation can be completed. If one or more systems are not reachable by the master, convergence cannot be achieved. Also, in some database systems it may not be acceptable to relay changes at one point in time to one subset of systems and to relay the changes at a second point in time to a second subset of systems.
Recently, computer systems that provide directory services have become a common way for providing resource information to users. Typically, directory services are databases of resource information that can be accessed by users through a communications network. Novell Directory Services (NDS), for example, is a global directory service solution that provides globally distributed information regarding various network resources to various network systems (Novell Directory Services is a registered trademark of Novell, Incorporated). Such resources can include objects such as systems, users, applications, servers, etc., that users may access through the NDS directory service.
Because the NDS database is used to access all resources on the network, the entire network would be disabled if the database itself were stored on only one server (with all other servers accessing the database on that server) and that server were to become unavailable. To avoid single point failures, distributed NDS databases are typically implemented. In this distributed database, replicas of the database are created and those replicas are stored on different servers. Then, if one server malfunctions, all other servers can continue to access the NDS database from another database replica.
If the NDS database is too large, a network administrator may not want to store the entire database on multiple servers. In this case, the network administrator may create directory partitions. The partitions may also include subpartitions (“child partitions”) beneath them. Using partitions can improve network performance, especially if the network expands across low bandwidth links, such as in a wide area network (WAN). Partitions also make it easier for a network administrator to separately manage portions of the database.
The NDS directory service is based on a standard referred to as the X.500 directory services standard, which defines a directory services protocol. Lightweight Directory Access Protocol (LDAP) is another type of directory services database standard which is commonly used to communicate and store resource information over the Internet. Because directory services databases may benefit from replicas and partitioning, they may also suffer from the aforementioned synchronization problems. These problems may cause other problems for systems that rely upon directory services information.
SUMMARY OF THE INVENTION
The present invention overcomes these and other drawbacks of conventional systems by providing a system and method for synchronizing distributed databases that does not require connectivity between all database replicas. The present invention enables each server to track the state of each replica of a replica set. Changes to the replicas are then communicated between the servers along with their states. The states may be stored as an array of timestamps, each such timestamp indicating a time at which the replica on each server was last updated. In one embodiment, the timestamp may be a unique identifier for identifying a replica change performed on a particular replica.
In a network wherein two servers (a first and a third server) cannot communicate directly, the first network server transmits a replica change to an intermediate (second) server including state information of the first netwo
Izatt Layne C.
Olds Dale R.
Prasad Ranjan
Corrielus Jean M.
Dinsmore & Shohl LLP
Fleurantin Jean Bolte
Novell Inc.
LandOfFree
System and method for synchronizing database information does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for synchronizing database information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for synchronizing database information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000601