Locking Schemes for Replicated Data Updating

Data distribution is commonly used in high-performance computing (HPC). Basically there are two fundamental data distribution topologies. One is replication; the other is partition.

With data partition, you can achieve parallel processing of a large amount of data.
With data replication, you can achieve load balancing and high availability(HA).

Even though a data item has several replicas in a data replication environment, it should have some degree of transparency and appear to only one virtual global item to end users.
The biggest challenge using data replication is the proper trade-off between data coherence and performance based on your business requirements.

Some kind of locking scheme is usually employed in order to achieve data coherence.
I will list some replication and locking schemes I have experienced using Oracle10g advanced replication, Oracle10g RAC, Oracle10g TimesTen and Gigaspaces XAP 7.1.

Before we go to details, let's suppose you have a distributed airline ticketing system (DATS hereafter) which has two databases: one is in NY and the other is in LA. Depending your replication scheme, data can be updated either at one site only and replicated to the other or at both sites and replicated to the each other.
Further suppose the following actions take place in time sequence:

1. There is only one ticket left in the database. Because both local database replicas are synchronized at this time, the only ticket can be taken by either NY or LA;
2. A NY customer bought this ticket. This action was updated in the local NY database and will be replicated to LA somehow depending on the replication scheme;
3. Depending on your replication scheme, the LA database can show the same ticket either still available or already taken by a NY customer. If the same ticket still appears available to the LA database, it will be sold to a LA customer. This will create an oversold situation.

1. Synchronous Replication Using Distributed Locks and Local Transactions

Oracle RAC (formerly OPS in version 8i and prior) allows the same physical database to be accessed at multiple instance sites. In order to allow users to read and write any data at any time at any instance site, Oracle RAC uses "Cache Fusion" to ensure data coherence.

"Cache Fusion" basically uses synchronous replication with a distributed locking manager (DLM). DLM acts as a distributed lock (DL) coordinator among other functions so that the same resource - e.g. a table row - can only be granted to one instance site for changing at a time while other sites have to wait.

DLM also act as a global resource directory. For example, when instance site 1 updated a row, it doesn't need to actively push the new version of data to all other instance sites.  When instance site 2 later requests the same row, DLM can tell it to get the latest version from instance site 1.
Also instance site 1 doesn't need to use any distributed transaction thanks to DLM and the fact that there is still only one physical database (so far I haven't seen any synchronous replication that use both distributed locks and distributed transactions).

Benefits include very high degree of data coherence and load balance for both reads and writes.
Drawback include poor write performance and requirements of high-speed interconnect due to distributed locks.
Distributed locks usually consist of quite a few daemon processes and data structures at each site whose coordination performs poorly in a low-speed interconnect such as LAN and WAN. For Oracle "Cache Fusion", distributed locks are implemented with Global Cache Service (GCS), Global Enqueue Service (GES) and Global Resource Directory (GRD).

If we apply this scheme to DATS assuming the poor interconnect performance is tolerable, step 3 has to wait for the DL to be release by step 2. When step 3 gets the DL, the same ticket will show already taken by step 2.
(In order to have good performance, most multi-tiered applications use optimistic locking that can create lost update problem. For example if we use optimistic locking in both databases in DATS, the application tier in step3 can first read the LA database before step 2 and then sell the same ticket to a LA customer after step 2.
The application must use "optimistic locking with version checking" to fix this issue. One version checking is just a version number that increases whenever there is any corresponding data change.
Suppose the version is 0 at step 1. Step 2 updates it to 1. The version found by the application tier read at step 3 is also 0. But when the application tier tries to sell the same ticket, it will fail because it will find the version has changed to 1 from its cached value 0.
All our arguments assume "optimistic locking with version checking" .)

2. Synchronous Replication Using Local Locks and Distributed Transactions
Oracle's multimaster replication (also called peer-to-peer or n-way) has two data coherence protocols.
One of them is synchronous replication that applies any changes or executes any replicated procedures at all sites participating in the replication environment as part of a single distributed transaction. If the DML statement or procedure fails at any site, then the entire transaction rolls back.

The distributed transaction ensures data consistency at all sites in real-time. However it doesn't use any distributed locking. Instead it only uses local locks in the participant local transaction.
This is the case when an application performs a synchronous update to a replicated table. Oracle first locks the local row and then uses an after row trigger to lock the corresponding remote row. Oracle releases the locks when the transaction commits at each site.

Benefits include high degree of data coherence, simple implementation, easy administration and fit to both high-speed interconnect and low-speed LAN and WAN (implementing distributed locks in low-speed LAN and WAN is much harder than using lock locks in such environments).
Drawbacks include possible deadlock due to temporal behavior of local and remote locking, high availability requirements on network and poor write performance.

If we apply this scheme to DATS assuming the poor interconnect performance is tolerable, step 3 has to wait for step 2 to release the local and remote locks. When step 3 gets the locks, the same ticket will show already taken by step 2.

3. Synchronous Replication Using Local Locks and Local Transactions
TimesTen's unidirectional active-standby pair configuration only uses so called "return twosafe
replication". It provides fully synchronous replication between the master (the active site) and subscriber (the standby site).
No distributed transaction or distributed lock is involved. Instead only local transaction and local lock are used. Specifically the local transaction on the subscriber is first committed before on the master. If the subscriber can't commit, the master will not commit either.
At any time, only the active site can be updated that greatly simplifies data updating complexity (otherwise using local locks and local transactions will be insufficient) and ensures fast fail-over to the standby site in case of the active site failure.

This scheme has similar benefits and drawbacks to the previous scheme in section 2.
However its performance is even better thanks to the avoiding of two-phase commit (2PC) required in a distributed transaction. It also eliminates the deadlock because only the active site allows updates.
Although the standby site seems to be a waste of capacity, you can collocate it with another active site as shown in figure 1 (by another I mean it has different data from the collocated standby site).
This scheme has lower degree of data coherence due to the inconsistency resulted from master commit failure even the subscriber has successfully committed (the root cause is it doesn't use distributed transactions as you can guess. But you should also know that data inconsistency can still result from the second "commit" phase failure in a 2PC process).

TimesTen's practice in this scenario is consistent with its configurations for high performance in other areas such as asynchronous logging and data caching with write-behind policy, 

Gigaspaces IMDG has a very similar topology called primary-backup replication. The only difference is it uses distributed transactions instead of local transactions only. So it has higher degree of data coherence than TimesTen.
Another advantage is the fail-over happens in Gigaspaces IMDG transparently to end users while TimesTen customers need to resort to some third-part cluster manager or some custom software.



If we apply this scheme to DATS, either NY or LA site will be the active site and the other standby site has to connect to the active for data updating (in reality, active-standby often is used with a high-speed interconnect). The local lock in the active site prevents the oversold situation.

This scheme along with data partitioning as shown in figure 1 is strongly recommend compared to the two previous synchronous schemes if it can your business requirements.
Although the two previous synchronous schemes allow updating anywhere, updating the same resource entails costly lock coordination over network. Scalable updating is usually achieved by data partitioning.
Although the two previous synchronous schemes allow distributed and scalable reads, you can fine-tune your partitions to allow more current reads.

Figure 1: The Primary-Backup Partition in Gigaspaces

4. Asynchronous Replication with Update Anywhere
Another data coherence protocol in Oracle's multimaster replication is asynchronous replication that allows users to update data at any participant site.
This scheme is also used in Oracle's updatable materialized view replication and TimesTen's bidirectional master-subscriber replication for general distributed workloads.

With this scheme the data changes at one site will be queued for propagation to other sites and committed locally. The queued changes will be propagated in batches in a separate transaction. So it doesn't use any distributed lock or distributed transaction. Instead it only use local locks required in the corresponding local transaction.

Benefits include great read and write performance, easy implementation, simple administration and fit to low-speed interconnection such as LAN and WAN and disconnected updating.
Drawbacks include limited degree of data coherence depending on data refresh frequency, and possible data change conflicts.
Because there is no distributed lock or distributed transaction involved, a replication conflict occurs if two transactions originating from different sites update the same row at nearly the same time (when the queued changes are propagated to the other site, the other site will have two versions of data changes. So which one should take place?).

A conflict resolution method must be provided to resolve the data inconsistency. Both Oracle and TimesTen have a prebuilt "latest timestamp" resolution method that makes the change with the latest timestamp the winner. Oracle also allows you to customize a resolution method based on your business requirements.

This scheme can't be applied to DATS if oversold situations are not allowed because the changes at NY and LA sites can be committed independently in two different transactions that result in the same ticket being sold to two customers.
If occasional oversold situations are allowed, the NY and LA sites can sell tickets at different times thanks to the three hours time zone difference. If a replication conflict does occur, relevant information should be recorded in the database based on which your front-end application takes proper actions (in reality a reservation system like DATS doesn't use this scheme).

5. Asynchronous Replication with Update on Master Site only

This scheme is used in Oracle's read-only materialized view replication, TimesTen's unidirectional master-subscriber replication and Gigaspaces IMDG's master-local replication.

This scheme basically has similar benefits and drawbacks to the previous scheme in section 4. However because it only allows updates at the master, it eliminates the notorious replication conflicts, which most of the time proves to be a very sound design in an asynchronous replication environment.

If we apply this scheme to DATS and suppose NY is the master site (or a third site is the master), NY has to wait if LA first gets the local lock at the master site. The local lock in the master site prevents the oversold situation.

Life is much easier using Gigaspaces IMDG's master-local topology as shown in figure 2 because it automatically delegates your local cache updating to the master which propagates the same updating to other local caches. Gigaspaces IMDG also supports optimistic locking with versioning.
You must do both by yourself if you use Oracle's read-only materialized view replication and TimesTen's unidirectional master-subscriber replication.

Figure 2: Gigaspaces Master-Local Topology where Master can be Figure 1

Daylight Saving Time (DST) and Timezone Handling in Java, JDBC and Oracle

The following problem has been puzzling me for 2 days.
Because MISO (Midwest ISO. A power market for several Mid West regions) doesn't support DST, it sent us data at hour 2 on Mar 14,2010 which is the DST beginning date (the hour 2 is supposed to be skipped if the ISO supports DST).

The date values in question are stored in an Oracle column called endDate which is of Oracle's date type without time zone information. In other words, you interpret such a date type's components (year,month,day,hour,minute,second and millisecond) in your local timezone.
If your data are across timezone, you should use Oracle's "timestamp with timezone" or "timestamp with local timezone". Such a date type has an additional timezone component based on which you interpret other components.

This additional timezone component is the key to understand the difference between Oracle's date type and Java's date type.
Because Java's date type represents the specified number of milliseconds since the standard base time known as "the epoch", namely January 1, 1970, 00:00:00 GMT. (Don't miss this GMT timezone!)
When you try to load an Oracle date value without a timezone into a Java date object, you will face difficulty without using any timezone in Java.

We used Hibernate's TimestampType to map this DB column to a Java Date type.
I used the following code to extract the hour in the endDate:
    Calendar cal = Calendar.getInstance();    //(1)

  int he;                                   //(2)
       
  cal.setTime(getEndDate());                //(3)
  he = cal.get(Calendar.HOUR_OF_DAY);       //(4)

The code is running in east coast which is currently in DST (it is August 2010). The hour in line (4) returns 1 for the hour 2 in question and the getEndDate()'s toString() also shows hour 1 instead of hour 2 or hour 3.

Getting to know why this happened is quite involving and confusing mainly due to the DST switch. We explain it in three steps.

First we need to know how Hibernate and JDBC driver retrieves you endDate value to a Java date object.
Hibernate's TimestampType just calls the following ResultSet's method to get the endDate.

   java.sql.Timestamp getTimestamp(String columnLabel);  

Because our DB column doesn't have timezone, what timezone will be used in the returned Timestamp (it extends date type) in the above method (still remember my previous statement "Java's date type represents the specified number of milliseconds since the standard base time known as "the epoch", namely January 1, 1970, 00:00:00 GMT. ")?
Astute readers may recall there is any similar method in ResultSet that allows you to provide a timezone through a Calendar:

   java.sql.Timestamp getTimestamp(int columnIndex, Calendar cal) ;

This method is exactly to handle a DB column without a timezone so that you can interpret the DB date times in a specified timezone based on your business logic.

The Java document for the first method doesn't say what time zone is associated with the returned timestamp value. This is unfortunate and different JDBC drivers may do different things. Later I will present what I found based on my testings.
Actually Java's date doesn't care about any time zone per se; it only remembers the the number of milliseconds since the "epoch". It is Java's calendar that incorporates a timezone (and also a locale).
Remember the preferred way to create a date object is to create a calendar first then call its getTime() to return the date. Calendar's getTime() creates a date by calculating the number of milliseconds since the "epoch".
On the other hand, you can assign a date value to a calendar whose time zone may be different from the original time zone that created the date.
For example, you created hour 1 in EST(GMT-5), then you assign this time to a calendar whose time zone is CST(GMT-6). The assigned calendar will returns a date whose hour is 0.
We can also infer that in order to return the same hour, the 2 time zones assigned to the 2 calendars must be the same.

Secondly, Java has different Calendar creation call syntax.
They behave differently for different timezones on Mar 14,2010(or any other DST beginning dates) even they all refer to the same region.
Take the New York region for example. Suppose our code runs in New York, the following 3 calls all return time zones in the New York region:
  Calendar cal = Calendar.getInstance(TimeZone.getTimeZone("GMT-5:00")); //EST. No DST support      (1)
  Calendar cal = Calendar.getInstance(TimeZone.getTimeZone("GMT-4:00")); //EDT. No DST support      (2)
  Calendar cal = Calendar.getInstance(); //default to "America/New_York". Supports DST  (3)

With (1), you can set the calendar's hour to 1,2 and 3 etc, even hour 2 doesn't exist and it actually corresponds to hour 3 in EDT.
With (2), you can also set the calendar's hour to 1,2 and 3 etc, even neither hour 1 or 2 exists and they actually correspond to hour 0 and 1 in EST, respectively.
With (3), you can set the calender to all 24 hours except 2. Specifically hour 1 corresponds to hour 1 in EST and hour 3 and later correspond to hours in EDT. When you try to set hour 2, Java actually changes to hour 3 in EDT because call syntax (3) supports DST and hour 2 doesn't exist.
(It is easy to understand if you just think the time zones in call syntax (1) and (2) are some first-class time zones and the time zone in (3) can be either GMT-5 or GMT-4 depending on the hour).

Finally we connect the dots together and shows you why line (4) got hour 1. 
When Hibernate uses the getTimestamp() without a calendar, the Oracle JDBC driver uses GMT-5 for hour 1 and GMT-4 for other hours to create a calendar and eventually returns a timestamp (I am not sure whether this is standard practice). So the hour 2 in the endDate is kept as hour 2 which actually corresponds to hour 1 in EST.
Because Line (1) is the Calendar call syntax (3) which supports DST, line (4) returns the actually hour 1 in EST.

Actually our application needs to return whatever hour MISO sent us without any DST offsetting. Based on the above analysis of Date and Calendar, line (1) must specify the same timezone as the one used to create the endDate by the JDBC driver. Unfortunately this is a guess game if you DB column doesn't have timezone information.

There are 2 solutions.
One is to design a DB column with time zone information.
The other is to extend Hibernate's TimestampType by explicitly specifying a GMT timezone such as your local timezone based on the raw GMT offset (Such Timezones ignore DST schedules).

Lastly the toString() from a Date object is based on your local timezone which may confuse you when your intended timezone is different.

hibernate.jdbc.batch_versioned_data can't be set to TRUE for Oracle JDBC driver

Duo to Oracle's popularity, we originally assumed it should be safe to turn on this flag for Oracle JDBC drivers until we saw a Unit testing exception.
Basically the Unit test tried to update a POJO in an optimistic way. It should have failed because the same POJO was just updated by another user before it. However Hibernate (3.3) just silently returned without resulting in any database update.
I traced the code to Hibernate's method checkBatched() in class Expectations$BasicExpections. The rowCounts Oracle returned turns out to be always -2 (Statement.SUCCESS_NO_INFO) for all its version 9i,10g and 11g JDBC drivers.

This returned value "-2" was finally verified by Oracle's JDBC Developer's Guide titled "Update Counts in the Oracle Implementation of Standard Batching" in Chapter 23 "Performance Extensions".
Basically it says:

• For a prepared statement batch, it is not possible to know the number of rows affected in the database by each individual statement in the batch. Therefore, all array elements have a value of -2. According to the JDBC 2.0 specification, a value of -2 indicates that the operation was successful but the number of rows affected is unknown.
  
• For a generic statement batch, the array contains the actual update counts indicating the number of rows affected by each operation. The actual update counts can be provided only in the case of generic statements in the Oracle implementation of standard batching.
  
• For a callable statement batch, the server always returns the value 1 as the update count, irrespective of the number rows affected by each operation.

The different returned values for different statements can be explained by the following Oracle implementation details:

In Oracle JDBC applications, update batching is intended for use with prepared statements that are being processed repeatedly with different sets of bind values.

The Oracle implementation of standard update batching does not implement true batching for generic statements and callable statements. Even though Oracle JDBC supports the use of standard batching for Statement and CallableStatement objects, you are unlikely to see performance improvement.

But I still have a hard time to believe that the back-end powerful Oracle database even couldn't know  the number of rows affected by each preparedStatement in a batch.

I am equally disappointed with the way Hibernate is handling Statement.SUCCESS_NO_INFO(-2).
This is how it happens: Hibernate uses preparedStatement for batch updates. Because the where clause in the update sql used a staled version number, Oracle just didn't update anything and returned successfully. Finally Hibernate still interprets Statement.SUCCESS_NO_INFO(-2) just as an successful update instead of throwing any optimistic exception. As you know this is not acceptable.

I know Hibernate is in a dilemma in this case because when Oracle returns Statement.SUCCESS_NO_INFO(-2) it either means some rows were updated or no row was udpated.
But I still like Hibernate to throw some exception to remind users of the updating ambiguity.

The good news is batch inserting is still safe as because returning Statement.SUCCESS_NO_INFO(-2) must mean a row was successfully inserted into the database.
So you may have to create a separate datasource for batch inserting only.