Data Replication in Objectivity/DB

Introduction: Note: The options referred to as Objectivity/DRO and Objectivity/FTO in this White Paper were combined into a single option, Objectivity High Availability, at Release 8. The functionality is exactly as described here.

Objectivity/DB Data Replication Option (DRO) extends Objectivity/DB? to include database replication capabilities that provide improved read performance and continuous availability, while ensuring data integrity in a manner that is transparent to applications.

Objectivity/DRO provides a method of data replication by which data integrity is maintained not by application specific code, but by the database engine itself. By comparison, traditional database solutions that offer asynchronous replication require data integrity to be maintained by the application, rather than the database.

The fundamental problem in maintaining data integrity in a set of replicated database images is propagating the changes from one database image to each of the others. With Objectivity/DRO, this is accomplished using a highly efficient voting mechanism to determine whether a particular access can successfully be granted to the database. If a majority, or "quorum", of database images agree, then access will be granted. If one or more of the database images are unavailable due to network or server failure, a quorum of database images is still sufficient to successfully modify the database. When the failed servers are repaired, or reconnected to the network, the database images that they contain will be automatically resynchronized to match the contents of the quorum database image.

Data replication with Objectivity/DRO provides continuous system availability in the event of either server or network failures. Since database images can be distributed geographically, Objectivity/DRO protects against physical and catastrophic site failures, as well as hardware and software failures at a given location.

The rest of this document describes Objectivity/DRO in more depth. Discussion will center around the various methods of data replication and present a detailed description of Objectivity/DRO. A number of data replication examples will be presented to demonstrate how to configure Objectivity/DRO in a variety of situations.

Data Replication: The fundamental issue in data replication is maintaining data integrity across multiple database images. Two primary solutions exist, synchronous and asynchronous replication.

Synchronous Replication

Synchronous replication requires that every image of the database be written at once. Data integrity is maintained in traditional database solutions with a two-phase commit within a transaction that accesses every image of the database element to be written, and proceeds only when every image is available for update. In traditional database solutions, synchronous replication eliminates the distinction between master/slave and peer-to-peer configurations.

However, traditional synchronous solutions are vulnerable to system failure. If one image of the database is unavailable due to server failure, the transaction is prevented from completing.

While synchronous replication assures data integrity, it does so at the expense of availability. System availability is greatly reduced with synchronous replication if the links between the database images are fragile. This vulnerability to network failures also prevents synchronously replicated database servers from being geographically distributed, leaving them vulnerable to location specific disasters, like fire or earthquake.

Asynchronous Replication

Asynchronous data replication provides two benefits, improved read performance and continuous availability. The failure of a particular server does not generally affect the operation of the other servers, but does force more work to be done in the application to maintain data integrity.

When changes are made, a single image of the database is updated, and then the changes are propagated to the remaining images. The two popular mechanisms for propagating changes to the other database images are imbedded triggers and passing change logs. Triggers are implemented inside the database and add to the overhead associated with performing transactions in the database. Passing change logs also increases network overhead during the replication of the update, but is less intrusive on the local database .

Asynchronous replication also allows database images to be isolated geographically, since each site has its own version of the data.

Conflict Avoidance, Detection, and Resolution

Conflict resolution is required when two images of the same database are updated at the same time, without knowledge of the other image.

The simplest solution for this type of conflict is to have the application avoid such conflicts by ensuring that each data element belongs to one database image or the other. This forces a master/slave relationship between database images.

Once the conflict exists, traditional databases provide mechanisms to detect and resolve them. Conflict resolution algorithms assign priorities to the conflicting updates based on update requester status (master/slave), timestamps, or some type of application dependent algorithm.

However, all applications do not fit these models. Certainly, a last-writer-wins model can cause problems for the second-to-last-writer. A master/slave relationship does not allow for a true peer-to-peer situation, where multiple servers have equal ability to update the same data.

Traditional Hot Fail-Over Solutions

Take the example shown below with two images of the same database on different database servers, separated by a failed network.

In this scenario, each database server thinks that it is the only one that exists, and that it has the ability to modify the database. Each server continues to process changes, creating the appropriate change log entries, not realizing that the failed server will come back on-line. When the connection is re-established, each will try to update the other.

The problem occurs when both have made changes to the same data element. In this case, both have updated element X, creating Y and Z, creating a conflict that may or may not be able to be resolved. Conflict resolution in this case is entirely application dependent.

Summary of Traditional Replication Solutions

Synchronous and asynchronous replication are summarized in the table below. With synchronous replication, data integrity is assured, but availability is not maintained. With asynchronous replication, availability is higher, but data integrity is not maintained.

Traditional database solutions have struggled to provide data replication, because their fundamental architecture assumes a centralized server that is designed to operate in isolation. Replication and distribution are then provided by connecting multiples of these stand-alone servers.

The reason that traditional database solutions offer both synchronous and asynchronous solutions for the data replication problem is that they are unable to provide data integrity and continuous availability at the same time. They are able to provide one or the other, but not both.

In order to provide both availability and data integrity, a third alternative is required that provides a fundamental improvement to synchronous replication. Objectivity/DRO is an implementation of this third category: synchronous data replication with a dynamic quorum calculation mechanism that provides both availability and data integrity.

Objectivity/DB Data Replication Option

Objectivity/DB has been designed from the beginning to be a distributed database, efficiently maintaining data integrity across multiple database servers. Objectivity/DRO extends this distributed functionality to provide data replication.

Before we can describe the technical aspects of Objectivity/DRO, it is necessary to review the key concepts of Objectivity/DB and Objectivity/FTO.

REVIEW OF OBJECTIVITY/DB KEY CONCEPTS : Objectivity/DB is built around the concept of the 'federated' database, which is defined to be a set of individual databases that reside on a number of servers.

The architecture features Local Servers, Remote Servers, and Lock Servers. The Local Server is linked to the applications, and provides access to the local disk, while Remote Servers provide access to disks on other machines. The Lock Server manages concurrency among users. Caching is maintained on the Local Server to provide improved performance through efficient use of disk I/O. Cross-transaction caching is managed by the database.

Objectivity/DB has the ability to distribute the databases across numerous servers, as shown above.

Distributing databases across multiple servers provides tremendous scalability, since there is no single bottleneck for data access. The lock server process is not a bottleneck, since it uses IDs to determine locking, and does not require accessing the object itself

Autonomous Partitions

Autonomous partitions operate as independent groups of databases within the context of a single federated database. Each autonomous partition has its own lock server process controlling access to its data. Autonomous partitions are provided by Objectivity/DB Fault Tolerant Option (FTO), which is a required option to implement data replication with Objectivity/DRO.

Objectivity/FTO allows Lock Servers to be replicated for each autonomous partition. Catalog information is replicated across autonomous partitions to provide schema definitions when partitions are isolated by network failures.

Placing a lock server in each autonomous partition protects one from the failure of another. Even if an autonomous partition fails, the others can continue to operate among themselves on their own data.

It is important to note, however, there is only one copy of any particular database. With Objectivity/FTO, if one autonomous partition fails, access to that data is interrupted until the autonomous partition is repaired or brought back on line.

Data Replication in Objectivity/DB

Objectivity/DRO provides multiple images of a database, placing each one in a separate autonomous partition. The application requirements determine which databases are to be replicated, and how the database images will be configured.

Objectivity/DRO allows flexible replication of selected data. Since the definition of any individual database is determined by the application developer, and can be dynamically altered, the granularity of the data replication can be selected to meet the requirements of the application.

Updates to data elements are synchronous, so there is no concern of data integrity violations. When an image of a database is brought back on line, it will be automatically resynchronized with any updates that occurred to the other images while it was off-line.

Note that only one image of each database can reside in any autonomous partition. Adding Objectivity/DRO makes it possible to have continuous access to the data.

Creating a sufficient number of database images protects against having a single point of failure. Even multiple failures will not prevent access to the data, as long as enough database images exist to form a quorum.

Quorum Calculation

The number of database images required to complete a transaction is calculated implicitly at runtime. This is called the "quorum calculation".

Simply put, the database images vote and the majority wins.

When a database image is accessed, and a lock is implicitly requested as part of that access, the application process running on the local computer contacts each lock server to determine which database images are available to vote. If a majority of the images of a database is available, called a "quorum", the access is permitted.

In this example, any two of the three database images form a quorum.

The images that are not available, for whatever reason, will be automatically resynchronized when they come back on line.

The quorum calculation uses a minimum of network traffic overhead, since only identification information is being passed. The data itself is not required to be passed, saving the network bandwidth for transmission of the data directly from database server to database server during normal operation of the application.

Non-Quorum Access

The quorum calculation occurs on every inquiry and update transaction.

A quorum is not required for inquiry transactions. The requirements of the particular application determine whether data is accessible for read access when a quorum is not available. While the system default does not allow non-quorum reads, it may be changed programmatically.

A quorum of images is required to successfully access the database for update. The quorum calculation ensures that enough database images are available to represent the true state of the database. Objectivity/DRO prevents non-quorum writes from ever occurring to ensure the integrity of the data, and prevents the need for merging multiple versions of a database together.

The bottom line is that if the application can write the data, there must be a quorum of database images available to ensure the availability of the modified data in the future.

Non-Unitary Weighting

There are many replication scenarios in which some database images require special access or ownership of particular data, regardless of server or network failures elsewhere in the system. Objectivity/DRO addresses this by assigning voting 'weights' to each database image.

Previous examples have been simplified to imply a single vote per database image. The actual case is that, rather than merely counting the number of database images available, the quorum calculation compares the weight of the available database images to the total weight assigned to all the images of that same database.

An example of this is a master/slave configuration in which one particular database image must be available for update transactions to succeed. The other database images are used to provide improved read access performance.

Setting the weight of the first database image to be greater than half the number of total weights assigned has the effect of making the first database image the owner of the database.

This is a master/slave configuration, since it only allows the slave database images to be updated if the master database image is also available to provide a quorum.

Administration and Maintenance

Data replication with Objectivity/DRO is easy to maintain and administrate. There are no complicated database resynchronization procedures for out-of-date database images since Objectivity/DRO automatically resynchronizes them when they come back on-line.

This capability allows easy platform maintenance. For example, in order to update the operating system on a computer, simply take it off-line, install the new version of the operating system, and put the computer back on line. Objectivity/DRO will automatically re-sync the database image, and the end-users will not be aware that maintenance was being performed.

The maintenance of multiple images of a database, including the assignments of weights, is primarily an administrative activity. Applications developed with Objectivity/DRO are not required to be aware that they will have their database replicated. This allows control of the application configuration to be maintained outside of the application development team.

Non-Quorum Recovery (not currently supported)

No software can protect against every kind of failure. There may still be a situation in which a catastrophic event wipes out a quorum of the database images.

Take the example of a master/slave configuration in which all the master database images are located within a geographic region that is destroyed in an earthquake. All that remains after the earthquake is a non-quorum group of database images in some remote location.

If the remaining, non-quorum database images were part of the quorum at the time of the earthquake, then the data in them is current. The data is inaccessible, however, since the remaining database images do not form a quorum.

It would be desirable for the database administrator to be able to use Objectivity/DRO's administrative utilities to redefine the quorum to be within the remaining database images, effectively making the federated database think that the database images destroyed in the earthquake never existed. This capability will be supported in a future release.

BUSINESS SCENARIOS: Objectivity/DB does not distinguish between database images on "client" workstations and database "servers". There is an inherent peer-to-peer relationship that can be modified to fulfill the requirements of the application. The database administrator creates a master/slave or peer-to-peer relationship with Objectivity/DRO by assigning the appropriate weights to the database images.

A. Telephone Call Routing

Protection Against Server Failures

Consider the conflict resolution example described earlier and apply it to telephone call routing; a situation that requires 100% availability of network configuration information. This application requires a hot backup of its data so that no interruption of service occurs.

In order to protect against the database server crashing, an image of the database is placed on a second server. If the first server fails, the second server continues processing normally.

The situation is pictured as follows:

In this configuration, two different servers contain images of the same information. If one of the servers fails, database reads are still possible through the other server. (Note that autonomous partitions may span servers, LANs, and WANs. For the sake of simplicity, this example assumes that each server contains its own autonomous partition.)

Simple Hot Fail-Over With Objectivity/DRO

Objectivity/DRO does not assign primary or secondary status to either of the database images. All images are equivalent representations of the same database. The only differentiator between images is the weight assigned to each which is used in calculating the quorum. If access is available to most of the weight of the replicated database images, authority is granted to make a change to the database.

In this example we have chosen to assign equal weight to each database image, which raises the issue of breaking ties. If one of the servers has failed and someone wants to write to the database, there is no quorum available since there is not a majority of weights available. It's a tie. There are as many weights available as there are unavailable.

The way Objectivity/DRO provides a quorum in the basic two image scenario is to create a third autonomous partition. A "tie-breaker" is placed into this third autonomous partition which casts the deciding vote in the quorum calculation. The tie-breaker is considered the equivalent to a database image for purposes of the quorum calculation, but it contains no data.

Any two of the three database "images" constitute a quorum, even though one of the images is really a tie-breaker.

Protection Against Network Failure

Locating each autonomous partition on a different network shows that this capability is not limited to use in single network configurations. Objectivity/DB, combined with Objectivity/DRO, provides a solution that is able to span networks to protect against network failure.

In the previous example, if all of the servers were on a single network, they would be vulnerable to network failures. In most environments, each geographic location has a number of LAN segments to isolate network failures. Objectivity/DRO handles this complexity transparently.

The configurations shown above both protect against network failure as well as server failure. Any two of the three database images will form a quorum allowing the database to be updated, as if they were on a single LAN.

Should one LAN fail, or the internetwork connection to one of the LANs fail, the quorum is still available to client workstations on the remaining LANs.

When the network between servers is disconnected with Objectivity/DRO, data is not corrupted, since only those servers that form a quorum of databases are able to process updates. While the network connection stays broken, only the contiguous servers forming the quorum can write to the database, thus ensuring data integrity.

Afterwards, when the network is reconnected, Objectivity/DRO automatically re-syncs the out-dated database images, eliminating the worries of accessing stale data, or corrupting the database through simultaneous updates.

B. Airline Customer Profile

Another example is that of an airline providing customer profile information to each counter at airports that are geographically dispersed.

Consider a customer of good standing. A frequent flyer comes to expect a higher level of service from the airline. When dealing with a ticket agent the customer's status will be indicated on the ticket agent's screen.

Clearly, performance is important, since the customer could potentially miss a flight if they had to wait too long, or if their status was not known at a remote location.

For argument's sake, let's assume that there are so many customers that ownership of the customer profile database is divided regionally. (Only New York can update New York customers, etc.) Quorum weighting would be applied as shown above.

With this weighting, each region would effectively own it's data, but replicas would be maintained by the remote locations to address the needs of international travelers. If the internetwork fails, isolating New York from Tokyo and London, New York would still be able read the profile of a European customer flying from London. Updates would not be permitted unless the customer's "home" region was available.

This ability to read "stale" data - called a "non-quorum read" - is an option that may be enabled or disabled, according to the requirements of the application.

This example exposes an application design trade-off true for any database replication implementation in which access to stale ("non-quorum") data is not available for inquiry. When reading stale data is not allowed, data replication is only useful as a means to improve read performance at remote sites.

Flexibility

The primary reason for setting the weights in this manner is to point out the flexibility provided by weighting database images.

If regional ownership is required such that only the "local" region is able to update the customer profile, weights would be assigned as shown. The owner would be given ownership by assigning a weight of 3 to the local image, and a weight of 1 to the remote images.

If regional ownership of customer profiles is not a requirement, a simple change to unitary weights on each database image can alter the behavior of the system to allow any two of the three regions to update a customer profile.

C. Web Server

Many situations require a large volume of data to be updated in a single location that needs to be accessed in geographically separated locations, such as with a Web server.

This scenario generalizes to most situations with the following characteristics:

many reads / few writes
geographic dispersal of information
100% availability required

As an exercise, consider the case of multi-media production facilities at three affiliated news organizations maintaining Web sites for the distribution of current event information. These Web servers would by definition contain a high concentration of audio, full-motion video and bit-mapped graphics.

Some of the information is accessed hundreds of times per day, other information is only accessed occasionally. Though the number of reads is very large in comparison to the number of writes, the data is written on a weekly, or sometimes daily basis.

The problem in trying to access all the information from a single server location Hong Kong is that the data volumes are too high to be transmitted on demand through the WAN connecting sites in San Francisco, Paris and Hong Kong. The information still needs to be accessed in Paris and San Francisco, but it is extremely inconvenient if, at runtime, the staff at those facilities has to wait for transmission when reading the database.

The solution is to use Objectivity/DRO to maintain multiple images of the data. The information is locally held to improve read performance. When updates are made to the database, all the locations will be kept up to date with the latest information. If one of the sites is off-line, Objectivity/DRO will perform the automatic re-synchronization as soon as the problem is resolved.

A geographic distribution of database images will improve read performance by moving the data closer to the end-users. Simple reads can be performed against the local image of the database, eliminating transmission delays due to accessing remote Web servers.

Load Balancing

Note that this application has an uneven distribution of data access. Some of the data is accessed frequently, while other parts of it are read in-frequently.

In this scenario, A represents the hot news item of the day. It is only a small portion of the total volume of the database, yet it is accessed by 90% of the database reads. B represents the background information on A. It is larger than A in terms of size, but is only accessed by 9% of the read traffic. C is only responsible for 1% of the read traffic, but it comprises the vast majority of the database.

Clearly it is desirable to distribute A as widely as possible to provide better response to the majority of the database accesses. B requires some replication, but not as much as A. C, however, can be left on a single server, since it is so infrequently accessed.

You could build a Web server using Objectivity/DRO that is able to dynamically distribute the load across multiple database servers. As Web page access profiles changes over time, the Web server would be able to dynamically redistribute the data across the database servers according to an application specific load distribution algorithm.

CONCLUSIONS: Objectivity/DB Data Replication Option improves read performance and ensures continuous availability with a dynamic quorum calculation mechanism that maintains data integrity despite server or network failures.

Objectivity/DRO protects against failures in both servers or networks. There is no need for applications to perform conflict resolution because Objectivity/DRO's synchronous data replication ensures data integrity. When database images on servers or networks that have failed become available to the quorum, they will be automatically resynchronized to the quorum database image.

Where traditional data replication solutions force the designer into a particular server configuration, Objectivity/DRO offers the flexibility to select the configuration that best fits the application. Configurations can range from simple hot fail-over systems, to widely distributed systems that offer protection against multiple points of failure. By adjusting the weight of database images, Objectivity/DRO supports master/slave, peer-to-peer and mixed configurations.