Network Topology

The following figure illustrates the network topology of the distributed data environment in the enterprise.

Figure Data Distribution Architecture

The techniques described in this text require that a Central Database exists as the arbiter and final authority for all updates to all of the databases. If the network were made up of peer systems, each transmitting updates to other systems, controlling the propagation of updates would be difficult and the process would be fraught with errors.

Figure Peer Network Example

One scenario is illustrated in the above figure. In this scenario, each system is responsible for transmitting updates to the other systems. As long as this happens in a timely manner, everything is fine. There is a window during which an error could be introduced. Assume that both System A and System B update the same row in their local databases and prepare update transmission. System A transmits it’s updates to the other systems. Before that update can be applied on System B, it sends out it’s update and then the update from System A in processed. System A and B have different contents in the updated row and Systems C and D have indeterminate contents based on the order they receive the updates. This window can be aggravated if either System A or B is inaccessible while the updating process occurs. Since this is the technique that is used by Data Distributors, it can be seen why they limit row updating to the system that created the row.

This illustrates the need for a central arbiter to determine which update is the correct one and to insure that the correct data is stored in all of the databases in the enterprise. This brings us to some of the precepts that have to be determined before any hope of implementing a distributed database can be achieved.

Distribution Precepts

The basic precepts we will discuss are:

  • Row Versions
  • Primary Key Assignments
  • Collisions and Collision Resolution
  • Closed Loop Update process
  • Collision Detection

Row Versions

A row version is a mechanism to assign a version value to a row in the database. One of the methods is to have an integer value that is set to one when the row is created in the central database and incremented when the row is updated.

A similar method is to maintain a monotonically increasing counter in the database and to assign its value to the row value in the central database when the row is created or updated. The advantage that this method has is that the updates can be ordered when they are prepared for transmission. The disadvantage of this method is that there are a finite number of updates that can be applied before the row version counter overflows. With a unsigned long integer, this value is 4,294,967,296.

Another method would be to store the date/time of the update. The DATE datatype in most databases stores the number of seconds from the database epoch date, a date the developers agreed would be prior to any date that may need to be stored in a database. If the date/time value is used as the row version, care must be taken to insure that the system clock on the central database server is consistent, possibly by synchronizing the system time to a government maintained standard.

Primary Key Assignments

Provision must be made to prevent primary key collisions. There are two basic techniques that can be used to solve this problem, Allocated Primary Key ranges or distribution of Primary Key Pools.

Allocating Primary Key ranges is to basically divide the primary key values based on some database identifier. Clarify used this method before the inception of Traveler by placing a numeric database id in the high order bits of the long integer primary keys. The assigned primary key value would be (Database ID * 2^28) + next primary key value. The method that was used at AMAT was to have two longword values comprise the primary key, putting the database id in the first longword value and the generated value in the second. This can feasibly be done with character primary key values by pre-pending a database identifier to the front the assigned primary key value.

Traveler used a method that distributed Primary Key Pools to the remote databases. Each database was initially allocated two pools for each table in the database and when a pool was exhausted, the remote database would request a new pool.

Collisions and Collision Resolution

A collision is when a single logical row is updated by two or more databases at virtually the same time. One of these updates must be determined to be the correct update and the others discarded by the central database. A simple collision resolution method would be to require that the row version of the row in the central database be the same as the row version in the update row from the remote database. If the values aren’t equal, the update is thrown away. This would establish that the first update received by the central database would be the one applied, known as “First in Wins.”

Closed Loop Update Process

The data in the central database is always correct. For a remote database to complete an update to a row, that update is sent to the central database, it is applied and then when updates are returned from the central database, the update is included, confirming the update in the remote database. This does not mean that the updated data must make the round trip before it can be seen in the remote database. If every update had to be applied and returned by the central database, performance would be abysmal. Updates are applied to the remote databases as they occur but the synchronization process can overwrite them when the loop is closed.

Collision Detection

The user must be notified that a row that they modified was not applied to the database because of a collision.

This can be done by trapping the collision on the central database server and notifying the remote database server that the collision occurred or by detecting that the row received from the central database was not the same row that was sent.

The mechanics of this process will be discussed later.