Data Replication

Taken from the reference (a): Chapter 6, Principles of

Distributed Database Systems, M. Tamer Özsu and Patrick
Valduriez, Springer.
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/1
Replication
• Why replicate?
➡ System availability
✦ Avoid single points of failure
➡ Performance
✦ Localization
➡ Scalability
✦ Scalability in numbers and geographic
area
➡ Application requirements

• Why not replicate?

➡ Replication transparency
➡ Consistency issues
✦ Updates are costly
✦ Availability may suffer if not careful

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/2

Execution Model
• There are physical copies of logical objects in
the system.
• Operations are specified on logical objects,
but translated to operate on physical objects.
• One-copy equivalence
➡ The effect of transactions performed by clients
on replicated objects should be the same as if
they had been performed on a single set of
objects.
Write(x)

x Logical data item

Write(x1) Write(x2 Write(xn)

)
x1 x2 xn
…
Physical data item (replicas, copies)
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/3
Replication Issues
• Consistency models - how do
we reason about the
consistency of the “global
execution state”?
➡ Mutual consistency
➡ Transactional consistency

• Where are updates allowed?

➡ Centralized
➡ Distributed

• Update propagation
techniques: how do we
propagate updates to one
copy to the other copies?
➡ Eager
➡ Lazy
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/4
Consistency
• Mutual Consistency
➡ How do we keep the values of
physical copies of a logical data
item synchronized?
➡ Strong consistency
✦ All copies are updated within the
context of the update transaction.
When the update transaction
completes, all copies have the
same value. Typically achieved
through 2PC
➡ Weak consistency
✦ Eventual consistency: the copies
are not identical when update
transaction completes, but they
eventually converge to the same
value. There are other weak
consistencies.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/5

Transactional Consistency
• We need to guarantee that the
global execution history over
replicated data is serializable.
• One-copy serializability (1SR)
➡ The effect of transactions
performed by clients on replicated
objects should be the same as if
they had been performed one at-
a-time on a single set of objects.
• It is possible for a replicated
DBMS to ensure that data items
are mutually consistent when a
transaction commits, but the
execution history may not be
globally serializable.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/6

 Mutual Consistency vs Transaction
Consistency
Site A Site B Site C
x x, y x, y, z

x ← 20 T2: Read(x) T3: Read(x)

Write(x) y ← x+y Read(y)
Commit Write(y) z ← (x∗y)/100
Commit Write(z)
Commit
Consider the three local histories regarding transaction
consistency:
HA = {W1(xA), C1}
HB = {W1(xB), C1, R2(xB), W2(yB), C2}
HC = {W2(yC), C2, R3(xC), R3(yC), W3(zC), C3,
Its W 1(xC), C
global 1}
history is non-serializable: HB: T1→T2, HC: T2→T3→T1
Mutually consistent: Assume xA = xB = xC = 10, yB = yC = 15, zC =
7 to begin;
in the end xA = xB = xC = 20, yB = yC = 35, zC = 3.5.
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/7
Mutual Consistency vs Transaction
Consistency
Site A Site B
x x
Read(x) T2: Read(x)
x ← x+5 x ← x∗10
Write(x) Write(x)
Commit Commit

Consider the two local

histories:
HA = {R1(xA), W1(xA), C1, W2(xA),
C 2}
HB = {Rhistory
Global 2(xB), W 2(xB), C2, W1(xB),
non-
C 1} serializable: HA: T1→ T2, HB:
T2→ T1
Mutually inconsistent:
Assume xA = xB = 1 to
Distributedbegin;
DBMS in the end xA = 10, ©M. T. Özsu & P. Valduriez Ch.13/8
Update Management
Strategies
• Depending on when the updates are
propagated
➡ Eager update propagation
➡ Lazy update propagation

• Depending on where the updates can take

place
➡ Centralized
Centralized Distributed
➡ Distributed

Eager

Lazy

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/9

Eager Update Propagation
• Changes are propagated within the scope of the transaction
making the changes. The ACID properties apply to all copy
updates.
➡ Synchronous propagation: apply update to all the replicates at the same
time
➡ Deferred propagation: update one replica and differ updates for the
• Masterby(Site 1),
other replicas to the end of transaction. It can be implemented
including the updates in the “prepare-to-commit” messageSlave
at the(Site
start
of 2PC. 2/3/4).
• Enforce mutual consistency using 1SR.
Transaction
• Write on
master,  Writes
• ROWA protocol: Read-one/Write-all
updatescommit on other slaves;
 Reads can be
 from any of
 sites.


Site 1 Site 2 Site 3 Site 4

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/10
Lazy Update Propagation
●Lazy replication first executes the • Master (Site 1),
updating transaction on one copy. After Slave (Site
2/3/4).
the transaction commits, the changes are
propagated to all other copies (refresh • Write on
master,  Writes
transactions)
on other slaves;
●While the propagation takes place, the  Reads can be
copies are mutually inconsistent. from any of
●The time the copies are mutually sites.
inconsistent is an adjustable parameter
which is application dependent.
Transaction
updatescommit

 


Site 1 Site 2 Site 3 Site 4
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/11
Centralized
●There is only one copy which can be updated (the master), all
others (slave copies) are updated reflecting the changes to the
master.
● Single master: There is one master for all data items.
● Primary copy: The master copy for each data item may be
different.

Site 1 Site 2 Site 3 Site 4

Site 1 Site 2 Site 3 Site 4

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/12

Distributed
●Changes can be initiated at any of the copies. That is, any of the
sites which owns a copy can update the value of the data item.
● There are eager/lazy update propagation. It is even difficult to do it
in a distributed manner under lazy update propagation.

Transaction
updates commit

Site 1 Site 2 Site 3 Site 4

Transaction
updates commit

Site 1 Site 2 Site 3 Site 4

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/13

Forms of Replication
Eager Centralized
+ No inconsistencies (identical + No inter-site synchronization is
copies) necessary (it takes place at the
+ Reading the local copy yields the master)
most up to date value
+ There is always one site which
+ Changes are atomic
has all the updates
− A transaction has to update all
sites − The load at the master can be
− Longer execution time high
− Lower availability − Reading the local copy may not
yield the most up-to-date value
Lazy
+ A transaction is always local (good Distributed
response time) + Any site can run a transaction
− Data inconsistencies + Load is evenly distributed
− A local read does not always return
the most up-to-date value − Copies need to be synchronized
− Changes to all copies are not
guaranteed
− Replication is not transparent
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/14
Replication Protocols
The previous discussions can be combined into 4
different replication protocols:

Eager Eager centralized Eager distributed

Lazy Lazy centralized Lazy distributed

Centralized Distributed

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/15

Eager Centralized Protocols
• Design parameters:
➡ Distribution of master
✦ Single master: one master for all data
items
✦ Primary copy: different masters for
different (sets of) data items
➡ Level of transparency (Transparency
Level)
✦ Limited: applications and users need to
know who the master is
✓ Update transactions are submitted directly to
the master
✓ Reads can occur on slaves
✦ Full: applications and users can submit
anywhere and the operations will be
forwarded to the master
✓ Operation-based forwarding
• Four alternative implementation
architectures, only three are
meaningful:
➡ Single master with limited transparency
➡ Single master with full transparency
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/16
Eager Single Master/Limited Transparency
(1)
• Applications submit update transactions directly to the
master
• Master:
➡ Upon read: read locally and return to user
➡ Upon write: write locally, write to other replicas
➡ Upon commit request: run 2PC coordinator to ensure
that all have really installed the changes
➡ Upon abort: abort and inform other sites about abort
• Slaves install writes that arrive from the master

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/17

Eager Single Master/Limited Transparency
(2)
• Applications submit read transactions directly to an
appropriate slave.
• Slave
➡ Upon read: read locally
➡ Upon write from master copy: execute conflicting writes in the
proper order
➡ Upon write from client: refuse (abort transaction; there is error)
➡ Upon commit request from read-only: commit locally
➡ Participant of 2PC for update transaction running on primary

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/18

Eager Single Master/Limited Transparency
(3)
• Applications submit read transactions
directly to an appropriate slave.
• Consider Reads on a local copy directly.
It implies that it does not request a read
lock (lock-S) from the master. It does it
locally using the 2PL for example.
• At the slave side, the local concurrency
control algorithm can ensure that the
local read/write conflicts are serialized.
• Writes can only come from the master.
• Local write-write conflicts do not occur,
as they should be managed by the
master.
• How about reads? Are there any
problems about transaction
consistency?

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/19

Eager Single Master/Limited Transparency
(4)
• Applications submit read transactions directly to an
appropriate slave.
• Are there any problems about transaction consistency?
• Consider
Site Aan(master)
example. Site B (slave) Site C
(slave)
x = 10 x = 10 x
T1: x ← 20 T2: Read(x) T3: Read(x)
= 10
Write(x) Commit Commit
Commit

• What Hhappens if T reads before T

2
= {R (x), C , W (x), C } 1 updates, and T3 reads
after T1B updates?
2 2 1 1

HC = {W1(x), C1, R3(xB), C3}

• The serial orders at Site B: T2 → T1, and at Site C: T1 → T3. The

global serialization order is T2 → T1 → T3.
• In this
Distributed DBMS way, read transactions may
©M. T. Özsu read data that are
& P. Valduriez Ch.13/20
Eager Single Master/Full Transparency
Applications submit all transactions to the Transaction Manager
at their own sites (Coordinating TM)
Coordinating TM Master Site
1. Send op(x) to the master site 1. If op(x) = Read(x): set read
lock on x and send “lock
granted” msg to the
coordinating TM
2. Send Read(x) to any site that 2. If op(x) = Write(x)
has x
a) Set write lock on x
b) Update local copy of x
c) Inform coordinating TM
3. Send Write(x) to all the slaves
3. Act as participant in 2PC
where a copy of x exists The key is the master
4. When Commit arrives, act as site does not deal with
coordinator for 2PC reads or with the
coordination of the
Distributed DBMS ©M. T. Özsu & P. Valduriez
updates across replicas!
Ch.13/21
Eager Primary Copy/Full Transparency
• Applications submit • Primary copy site
transactions directly to their ➡ Read(x): lock x and reply
local TMs to TM
• Local TM: ➡ Write(x): lock x,
➡ Forward each operation to the perform update, inform
primary copy of the data item. TM
➡ Upon granting of locks, submit ➡ Participate in 2PC
Read to any slave, Write to all
slaves • Slaves: as before
➡ Coordinate 2PC.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/22

Eager Distributed Protocol
• Updates originate at any copy • The figure shows an
➡ Each site uses 2 phase locking (2PL). example. There are two
➡ Read operations are performed transactions, T1 and T2. Both
locally. update x, one at Site A and
➡ Write operations are performed at all one at Site D.
sites using a distributed locking • Critical issue: to ensure
protocol. that concurrent conflicting
➡ Coordinate 2PC
Writes initiated at different
• Slaves: master sites are executed in
➡ As before the same order at every
slave site.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/23

Lazy Centralized Protocols
• Design parameters: • The issues to consider are
➡ Distribution of master similar to Eager centralized
✦ Single master: one master for all data protocols.
items • The key difference is that
✦ Primary copy: different masters for propagation does not take
different (sets of) data items place within the update
➡ Level of transparency (Transparency transaction, but after the
Level) transaction commits as a
✦ Limited: applications and users need to separate refresh transaction.
know who the master is
✓ Update transactions are submitted directly to
the master
✓ Reads can occur on slaves
✦ Full: applications and users can submit
anywhere and the operations will be
forwarded to the master
✓ Operation-based forwarding
• Four alternative implementation
architectures, only three are
meaningful:
➡ Single master with limited transparency
➡ Single master with full transparency
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/24
Lazy Single Master/Limited Transparency
(1)

• Update transactions submitted to

master
• Master:
➡ Upon read: read locally and return to
user
➡ Upon write: write locally and return to
user
➡ Upon commit/abort: terminate locally
➡ Sometime after commit: updates to
slaves (in order)

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/25

Lazy Single Master/Limited Transparency
(2)
• Slaves:
➡ Upon read: read locally
➡ Write should be done at the master site first. Writes initiated at
a slave site are rejected.
➡ Refresh transactions: When it receives a refresh transaction, it
applies the updates to its local copies. When it receives
Commit/Abort, it locally performs these actions.
➡ It needs to ensure all refresh transactions are done at all of the
slaves in the same order. As it is single master, it can use
timestamp to do so.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/26

Lazy Primary Copy/Limited Transparency
• There are multiple masters.
• Each master execution is similar to lazy single master in the
way it handles transactions.

• Slave execution are complicated for refresh transactions that

are from multiple masters and need to be ordered properly.

• Assign system-wide unique timestamps to refresh

transactions and execute them in timestamp order.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/27

Lazy Single Master/Full Transparency
• By full transparency, it allows (both
reads/writes) transactions to be
submitted at any site and
forwarding their operations to
either the single master or to the
appropriate primary master site.
• This is very tricky
➡ Forwarding operations to a master
and then getting refresh
transactions cause difficulties.
• Two problems:
➡ Violation of 1SR behavior
➡ A transaction may not see its own
reads
• Problem arises in primary copy/full
transparency as well
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/28
Violation of 1SR
behavior: An Example

Site M (Master) holds x, y; Site B

holds
slave copies of x, y.
T1 (Site B): Read(x), Write(x), Commit
T2 (Site M): Write(x), Write(y), Commit

Writes at a slave will be forwarded to

the master to perform.

Here, the superscript R on

operations indicate that they are
part of a refresh transaction.

The resulting global history over

the logical data items, x and y is
non-1SR.

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/29

Not see its own reads: An Example
• Master Site M holds x, Site D holds slave copy
of x
• T3: Write(x), Read(x), Commit
• Sequence of execution
1. W3(x) submitted at D, forwarded to M for
execution
2. W3(x) is executed at M, confirmation sent back
to D
3. R3(x) submitted at D and executed on the local
copy
4. T3 submits Commit at D, forwarded to M for
execution
5. M executes Commit, sends notification to D,
which also commits T3
6. M sends refresh transaction for T3 to D (for
W (x) operation)
Distributed DBMS 3 ©M. T. Özsu & P. Valduriez Ch.13/30
Lazy Single Master/Full Transparency:
Solution
• Assume T does Write(x)
• At commit time of transaction T, the
master generates a timestamp for it [ts(T)]
• Master sets last_modified(x ) ← ts(T)
M

• When a refresh transaction arrives at a slave site ,

it also sets last_modified(xi) ← last_modified(xM)
• Timestamp generation rule at the master:
➡ ts(T) should be greater than all previously issued timestamps and
should be less than the last_modified timestamps of the data
items it has accessed. If such a timestamp cannot be generated,
then T is aborted.
• The above solves the first problem of Violation of 1SR behavior.
• To solve the second problem that a transaction may not see its own
reads, it needs to keep a list of all the updates that a transaction
performs and use it for reads. Since only the master knows the
updates, the list has to be maintained at the master and all the
Reads/Writes
Distributed DBMS have to be executed
©M. T. Özsu &at the master.
P. Valduriez Ch.13/31
For the Same Example

Site M (Master) holds x, y; Site B

holds slave copies of x, y.
T1 (Site B): Read(x), Write(x),
Commit
T2 (Site M): Write(x), Write(y),
Commit

Writes at a slave will be forwarded to

the master to perform.
Here, the superscript R on
operations indicate that they are
part of a refresh transaction.

The master site M cannot assign

an appropriate timestamp to
transaction T1 when it commits,
because the last_modified(xM)
would reflect the update
performed by T2. T1 would be
aborted.
Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/32
Lazy Distributed Replication (1)
• It is the most complex one because it can be done at any
site.
• Any site:
➡ Upon read: read locally and return to user
➡ Upon write: write locally and return to user
➡ Upon commit/abort: terminate locally
➡ Sometime after commit: send refresh transaction
➡ Upon message from other site
✦ Detect conflicts
✦ Install changes
✦ Reconciliation may be necessary

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/33

Lazy Distributed Replication (2)
• Such problems can be solved using pre-arranged patterns:
➡ Latest update win (newer updates preferred over old ones)
➡ Site priority (preference to updates from headquarters)
➡ Largest value (the larger transaction is preferred)

• Or using ad-hoc decision making procedures:

➡ Identify the changes and try to combine them
➡ Analyze the transactions and eliminate the non-important ones
➡ Implement your own priority schemas

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/34

Replication Strategies
+ Updates do not need to be + No inconsistencies
coordinated + Elegant (symmetrical
+ No inconsistencies solution)
Eager

- Longest response time - Long response times

- Only useful with few - Updates need to be
updates coordinated
- Local copies are can only
be read
+ No coordination necessary + No centralized coordination
+ Short response times + Shortest response times
Lazy

- Local copies are not up to - Inconsistencies

date - Updates can be lost
- Inconsistencies (reconciliation)

Centralized Distributed

Distributed DBMS ©M. T. Özsu & P. Valduriez Ch.13/35