Oracle7 Server Distributed Systems Volume II: Replicated Data

Contents Index Home Previous Next

Dynamic Ownership Conflict Avoidance

This section describes a more advanced method of designing your applications to avoid conflicts. This method, known as token passing, is similar to the workflow method described in Chapter 1. Although this section describes how to use this method to control the ownership of an entire row, you can use a modified form of this method to control ownership of the individual column groups within a row.

Both workflow and token passing allow dynamic ownership of data. With dynamic ownership, only one site at a time is allowed to update a row, but ownership of the row can be passed from site to site. Both work flow and token passing use the value of one or more "identifier" columns to determine who is currently allowed to update the row.

Workflow

With workflow partitioning, you can think of data ownership as being "pushed" from site to site. Only the current owner of the row is allowed to push the ownership of the row to another site, by changing the value of the "identifier" columns.

Take the simple example of separate sites for ordering, shipping, and billing. Here, the identifier columns are used to indicate the status of an order. The status determines which site can update the row. After a user at the ordering site has entered the order, he or she updates the status of this row to SHIP. Users at the ordering site are no longer allowed to modify this row -- ownership has been pushed to the shipping site.

After shipping the order, the user at the shipping site will update the status of this row to BILL, thus pushing ownership to the billing site, and so on.

To successfully avoid conflicts, applications implementing dynamic data ownership must ensure that the following conditions are met:

With workflow partitioning, only the current owner of the row can push the ownership of the row to the next site by updating the "identifier" columns. No site is given ownership unless another site has given up ownership; thus ensuring there is never more than one owner.

Because the flow of work is ordered, ordering conflicts can be resolved by applying the change from the site that occurs latest in the flow of work. Any ordering conflicts can be resolved using a form of the Priority conflict resolution method, where the priority value increases with each step in the work flow process.

The PRIORITY conflict resolution method successfully converges for more than one master as long as the priority value is always increasing.

Token Passing

Token passing uses a more generalized approach to meeting these criteria. To implement token passing, instead of the "identifier" columns, your replicated tables must have owner and epoch columns. The owner column stores the global database name of the site currently believed to own the row.

This column should be used exclusively for establishing ownership and should not otherwise be updated. The epoch column is used to resolve ordering conflicts. This number is updated each time the ownership of the row changes. Thus the change associated with the highest epoch number is the most recent change.

Once you have designed a token passing mechanism, you can use it to implement a variety of forms of dynamic partitioning of data ownership, including workflow.

You should design your application to implement token passing for you automatically. You should not allow the owner or epoch columns to be updated outside this application.

Whenever you attempt to update a row, your application should

For example, Figure 8 - 2 illustrates how ownership of employee 100 passes from the ACCT_SF database to the ACCT_NY database.

Figure 8 - 2. Grabbing the Token

Locating the Owner of a Row

To grab ownership, the ACCT_NY database uses a simple recursive algorithm to locate the owner of the row. The pseudo code for this algorithm is shown below:

-- Pseudo code for locating the token owner.
-- This is for a table TABLE_NAME with primary key PK.
-- Initial call should initialize loc_epoch to 0 and loc_owner
-- to the local global name.
get_owner(PK IN primary_key_type, loc_epoch IN OUT NUMBER, 
          loc_owner IN OUT VARCHAR2)
{
    -- use dynamic SQL (dbms_sql) to perform a select similar to
    -- the following:
    select owner, epoch into rmt_owner, rmt_epoch
         from TABLE_NAME@loc_owner
         where primary_key = PK for update;
    if rmt_owner = loc_owner and rmt_epoch >= loc_epoch then
      loc_owner := rmt_owner;
      loc_epoch := rmt_epoch;
      return;
    elsif rmt_epoch >= loc_epoch then 
      get_owner(PK, rmt_epoch, rmt_owner);
      loc_owner := rmt_owner;
      loc_epoch := rmt_epoch;
      return;
    else
      raise_application_error(-20000, 'No owner for row');
    end if;
}

Grabbing Ownership

After locating the owner of the row, the ACCT_NY site grabs ownership from the ACCT_SF site by completing the following steps:

Applying the Change

You should design your application to implement this method of token passing for you automatically whenever you perform an update. You should not allow the owner or epoch columns to be updated outside this application. The lock that you grab when you change ownership is released when you apply your actual update. The changed information, along with the updated owner and epoch information, will be asynchronously propagated to the other sites in the usual manner.

Contents Index Home Previous Next