[Bernstein09] 9.3. Synchronizing Updates to Replicated Data

9.3. Synchronizing Updates to Replicated Data

One-Copy Serializability

Onpossible goal of replication is to have replicas behave functionallylike nonreplicated servers. This goal can be stated precisely by theconcept of one-copy serializability, which extends the concept ofserializability to a system where multiple replicas are present. Anexecution is one-copy serializableif it has the same effect as a serial execution on a one-copy database.We would like a system to ensure that its executions are one-copyserializable. In such a system, the user is unaware that data isreplicated.

In asystem that produces serializable executions, what can go wrong thatwould cause it to violate one-copy serializability? The answer issimple, though perhaps not obvious: a transaction might read a copy ofa data item, say x, that was not written by the last transaction that wrote other copies of x. For example, consider a system that has two copies of x, stored at locations A and B, denoted x_A and x_B. Suppose we express execution histories using the notation of Section 6.1, where r, w, and crepresent read, write, and commit operations, respectively, andsubscripts are transaction identifiers. Consider the followingexecution history:

H = r₁[x_A] w₁[x_A] w₁[x_B] c₁ r₂[x_B] w₂[x_B] c₂ r₃[x_A] w₃[x_A] w₃[x_B]c₁

This is a serial execution. Each transaction reads just one copy of x; since the copies are supposed to be identical, any copy will do. The only difficulty with it is that transaction T₂ did not write into copy x_A. This might have happened because copy x_A was unavailable when T₂ executed. Rather than delaying the execution of T₂ until after x_A recovered, the system allowed T₂ to finish and commit. Since we see r₃[x_A] executed after c₂, apparently x_A recovered before T₃ started. However, r₃[x_A] read a stale value of x_A, the one written by T₁, not T₂.

When x_A recovered, it should have been refreshed with the newly updated value of x that is stored in x_B. However, we do not see a write operation into x_A after T₂ committed and before r₃[x_A] executed. We therefore conclude that when r₃[x_A] executed, x_A still had the value that T₁ wrote.

Clearly, the behavior of H is not what we would expect in a one-copy database. In a one-copy database, T₃ would read the value of x written by T₂, not T₁. There is no other serial execution of T₁, T₂, and T₃that has the same effect as H. Therefore, H does not have the sameeffect as any serial execution on a one-copy database. Thus, it is notone-copy serializable.

One obvious implication of one-copy serializability is that each transaction that writes into a data item x should write into all copies of x.However, when replication is used for improved availability, this isn’talways possible. The whole point is to be able to continue to operateeven when some copies are unavailable. Therefore, the not-so-obviousimplication of one-copy serializability is that each transaction thatreads a data item x must read a copy of x that was written by the most recent transaction before it that wrote into any copy of x. This sometimes requires careful synchronization.

Still,during normal operation, each transaction’s updates should be appliedto all replicas. There are two ways to arrange this: replicate updateoperations or replicate requests. In the first case, each requestcauses one transaction to execute. That transaction generates updateoperations, each of which is applied to all replicas. In the secondcase, the request message is sent to all replicas and causes a separatetransaction to execute at each replica. We discuss each case, in turn.

Replicating Updates

There are two approaches to sending a transaction’s updates to replicas: synchronous and asynchronous. In the synchronous approach, when a transaction updates a data item, say x, the update is sent to all replicas of x.These updates of the replicas execute within the context of thetransaction. This is called synchronous because all replicas are, ineffect, updated at the same time (see Figure 9.4a).Although sometimes this is feasible, often it is not, because itproduces a heavy distributed transaction load. In particular, itimplies that all transactions that update replicated data have to usetwo-phase commit, which entails significant communications cost.

Fortunately, looser synchronization can be used, which allows replicas to be updated independently. This is called asynchronous replication, where a transaction directly updates one replica and the update is propagated to other replicas later (see Figure 9.4b).

Asynchronousupdates from different transactions can conflict. If they are appliedto replicas in arbitrary orders, then the replicas will not beidentical. For example, suppose transactions T₁ and T₂ update x, which has copies x_A and x_B. If T₁ updates x_A before T₂, but T₁ updates x_B after T₂, then x_A and x_Bend up with different values. The usual way to avoid this problem is toensure that the updates are applied in the same order to all replicas.By executing updates in the same order, all replicas go through thesame sequence of states. Thus, each query (i.e., read-only transaction)at any replica sees a state that could have been seen at any otherreplica. And if new updates were shut off and all in-flight updateswere applied to all replicas, the replicas wouldbe identical. Therefore, users working with one replica see the samebehavior that they would see with any other replica. In this sense, allreplicas behave exactly the same way.

Applyingupdates in the same order to all replicas requires somesynchronization. This synchronization can degrade performance, becausesome operations are delayed until other operations have time tocomplete. Much of the complexity in replication comes from cleversynchronization techniques that minimize this performance degradation.

Whethersynchronous or asynchronous replication is used, applying updates toall replicas is sometimes impossible, because some replicas are down.The system could stop accepting updates when this happens, but this israrely acceptable since it decreases availability. If some replicas docontinue processing updates while other replicas are down, then whenthe down replicas recover, some additional work is needed to recoverthe failed replicas to a satisfactory state. Some of the complexity inreplication comes from ways of coping with unavailable servers andhandling their recovery.

Replicas can be down either because a system has failed or because communication has failed (see Figure 9.5).The latter is more dangerous, because it may lead to two or moreindependently functioning partitions of the network, each of whichallows updates to the replicas it knows about. If a resource hasreplicas in both partitions,those replicas can be independently updated. When the partitions arereunited, they may discover they have processed incompatible updates.For example, they might both have sold the last item from inventory.Such executions are not one-copy serializable, since it could not bethe result of a serial execution on a one-copy database. There are twosolutions to this problem. One is to ensure that if a partition occurs,only one partition is allowed to process updates. The other is to allowmultiple partitions to process updates and to reconcile theinconsistencies after the partitions are reunited—something that oftenrequires human intervention.

Circumventingthese performance and availability problems usually involvescompromises. To configure a system with replicated servers, one mustunderstand the behavior of the algorithms used for update propagationand synchronization. These algorithms are the main subject of thischapter.

Replicating Requests

An alternative to sending updates to all replicas is to send the requests to run the original transactions to all replicas (see Figure 9.6).To ensure that all the replicas end up as exact copies of each other,the transactions should execute in the same order at all replicas.Depending on the approach selected, this is either slow or tricky. Aslow approach is to run the requests serially at one replica and thenforce the requests to run in the same order as the other replicas. Thisensures they run in the same order at all replicas, but it allows noconcurrency at each replica and therefore would be an inefficient useof each replica’s resources.

Thetrickier approach is to allow concurrency within each replica and usesome fancy synchronization across replicas to ensure that timingdifferences at the different replicas don’t lead to different executionorders at different replicas. For example, in HP’s Reliable TransactionRouter (RTR), a replicated request can be executed at two or morereplicas concurrently as a single distributed transaction. Since itruns as a transaction, it is serialized with respect to otherreplicated requests (which also run as transactions). It therefore canexecute concurrently with other requests. Transaction synchronization(e.g., locking) ensures that the requests are processed in the sameorder at all replicas. As usual, transaction termination issynchronized using two-phase commit. However, unlike ordinary two-phasecommit, if one of the replicas fails while a transaction is beingcommitted, theother continues running and commits the transaction. This is useful incertain applications, such as securities trading (e.g., stock markets),where the legal definition of fairness dictates that transactions mustexecute in the order they were submitted, so it is undesirable to aborta transaction due to the failure of a replica.

Replicatingupdates is a more popular approach than replicating requests, by far.Therefore, we will focus on that approach for the rest of this chapter.