Abstract
Dual-quorum replication is a novel data replication algorithm designed to support Internet
edge services. The internet edge service architecture attempts to improve service availability and
latency by allowing clients to access the closely available edge server rather than a centralized
server. Edge services allow clients to access Internet services via distributed edge servers that
operate on a shared collection of underlying data. Dual-quorum replication focus on the key
problem of sharing read/write data objects across a collection of edge servers when the references
to each object 1) tend not to exhibit high concurrency across multiple nodes and 2) tend
to exhibit bursts of read-dominated or write dominated behavior. Dual-quorum replication
combines volume leases and quorum-based techniques to achieve excellent availability, response
time, and consistency for such workloads.
[attachment=8527]


1 Introduction
Dual-quorum(DQ) replication is a novel data replication algorithm for supporting high avail-
ability and consistency for data replication in edge services.It is developed by exploiting object-
specic workload characteristics and it oers good availability, consistency, and response time.
The Internet edge service architecture attempts to improve service availability and latency by
allowing clients to access the closest available edge server rather than a centralized server or
a centralized server cluster.The benets promised by the edge service architecture are limited
by the coordination among replicas of shared data. Thus, support for data replication is a key
problem in realizing the promise of Internet edge services.
DQ replication is a new protocol designed to meet the demands edge services better. DQ is
optimized for workloads that exhibit locality in two dimensions: 1) at any given time, access
to a given element tends to come from a single server and 2) reads tend to be followed by other
reads and writes tend to be followed by other writes.
DQ replication achieves these goals by two ideas: First devote two separate quorum systems,
an input quorum system Qinput and an output quorum system Qoutput, for write and read
requests, respectively, to optimize both write and reads availability and performance. Because
traditional quorum systems require each read quorum to intersect each write quorum to provide
regular semantics, a small read (write) quorum implies a large write (read) quorum; there is
thus a trade-o between read availability and write availability. In DQ, instead of constructing
read quorums and write quorums from the same quorum system, clients send their writes to a
write quorum formed in Qinput and they read from a read quorum in Qoutput.
Second, DQ generalizes volume lease protocol to reduce the communication overhead between
Qinput and Qoutput to enforce consistency and improve write availability. A volume lease is a
lease for a group of objects.
5
2 Edge Services
The edge services architecture distributes Web services to a collection of edge servers across
WAN and near end users to process requests. This approach minimizes communication across
the wide area network during request processing in order to improve service availability and
latency.A typical web application system can be divided into three layers: the interface layer,
the business logic layer, and the database access layer. Existing edge server approaches for
web service replication can be classied into two categories. One tries to move the interface
and the business logic layers to edge servers and leave the database access layer at the original
application servers. The representative examples are IBMs Websphere Edge Server and Akamai
EdgeComputing. In this approach, the edge server needs to remotely access the database. If
such database accesses are very frequent, then the benet of edge servers can be diminished. To
reduce the burden on the web application servers (web servers, web services, etc.), we assume
that the database replication decisions are made at the edge servers.
Figure 1: The edge service architecture
2.1 Data Replication in Edge servers
The edge services architecture promises to improve the availability and performance of Web
services by replicating servers at geographically distributed sites. A key challenge in such
systems is data replication and consistency, so that edge server code can manipulate shared
data without suering the availability and performance penalties that would be incurred by
accessing a traditional centralized database. It is dicult to maintain consistency and staleness
bound in this case. Mutual exclusion also needed here. Improving availability and latency is
crucial for business-critical e-commerce servers.
6
3 Quorum Systems
Quorum is a set of nodes or servers required to perform an operation and a quorum system is
a collection of subsets of nodes or set of quorums, with the property that each pair of quorums
have a non-empty intersection. Quorum systems are the key mathematical abstraction for
ensuring consistency in fault-tolerant and highly available distributed computing.
A replicated object is one whose state is stored redundantly at multiple sites. Replicated
objects are implemented by two kinds of modules: repositories and front ends. Repositories
provide long-term storage for the objects state, while front ends carry out operations for clients.
In the terminology of Bernstein and Goodman, front ends correspond roughly to transaction
managers and repositories correspond roughly to data managers. Because front ends can be
replicated to an arbitrary extent, perhaps placing one at each clients site, the availability of a
replicated object is dominated by the availability of its repositories.
Each operation requires the co-operation of a certain number of repositories for its successful
completion. A quorum for an operation is any such set of repositories. It is convenient to divide
a quorum into two parts: a front end executing an invocation reads from an initial quorum
of repositories, performs a local computation to choose a response, and records the new event
at a nal quorum of repositories. The initial quorum may depend on the invocation, and the
nal quorum may depend on the response. Either the initial or nal quorum may be empty. A
quorum assignment associates each event with a set of initial and nal quorums.
A quorum system Q is a set of subsets of servers with the property that, for any Q1;Q2 2
Q;Q1 \ Q2 6= 
Giord introduced a weighted voted scheme and was also the rst to rene the concept
of majority-based quorums by separating the notions of read and write quorums. In this
fundamental renement, the Intersection property is relaxed so as not to require all quorums
to intersect. Giord separates quorums into two classes: read and write quorums, and requires
only quorums belonging to dierent classes to intersect. In principle, this renement with its
distinctions between read and write quorums can be applied to any quorum system.
7
4 System Model
In DQ system physical server plays one or more of the following three roles: 1) front-end
servers that handle service client requests from across the Internet.execute application-specic
processing, and act as edge server clients or just clients to the DQ storage system; 2) output
quorum system Qoutput servers that process client read requests; and 3) input quorum system
Qinput servers that process client write requests.
Figure 2: Edge service system model
DQ enforces regular semantics:
 Property 1: A read of o that is not concurrent with any writes of o can return only the
value and logical clock from the completed write of o with the highest logical clock.
 Property 2: A read of o that is concurrent with one or more writes of o can 1) return the
value and logical clock from the completed write of o with the highest logical clock or 2)
return the value and logical clock from some concurrent write of o.
Regular semantics guarantee that a read always returns the last completed write or any con-
current partially completed write.
8
In the remaining sections, the interactions with a quorum system is described in terms of
a QRPC operation. A QRPC operation QRPC(system;RjW; request) sends request to a
collection of servers in the specied quorum system (e.g., Qinput or Qoutput). The QRPC call
then blocks until a set of replies constituting the specied quorum (read quorum if the second
parameter is R, or write quorum otherwise) on the specied system have been gathered. The
call then returns the set of replies that it received. The QRPC operator abstracts away details
of selecting a quorum, retransmissions, and time-outs. In particular, dierent implementations
may choose dierent ways to select which servers from system to send requests to, and they
may select dierent retransmission strategies: The prototype implementation discussed in this
paper always transmits requests to the local server if it is a member of system; it then randomly
selects a sucient number of additional servers to form a read or write quorum and transmits
the request to them; retransmissions are each sent to a new randomly selected quorum using
an exponentially increasing retransmission interval.
9
5 Dual-Quorum Protocol Design
The protocol is discussed in two steps: First, is a simplied asynchronous DQ (ADQ) protocol.
This protocol allows independent optimizations of read and write quorums, but because it
assumes an asynchronous system model, a write can block for an arbitrarily long period of
time. Next is volume leases to the protocol to improve write availability while retaining good
read performance.
5.1 Asynchronous Dual-Quorum Protocol
In a traditional quorum protocol if the read quorum is made large enough to provide good write
availability, read performance will be unacceptable because reads will be WAN-distributed
rather than local operations. To address this dilemma, ADQ processes reads and writes in
two dierent quorum systems (Qinput and Qoutput) and uses a cache invalidation strategy to
synchronize the state of objects replicated in Qinput servers and cached in Qoutput servers to
achieve regular semantics. The key challenge is how to eciently maintain callbacks in Qinput
and Qoutput to reduce the synchronization trac between them.
Basic read and write operations. From the front-end servers perspective, an ADQ read
is the same as a standard quorum read. As Fig 2 illustrates, upon receiving a read request from
a client, the server contacts a read quorum Routput of the output quorum system Qoutput. An
Routput server can return a read immediately if it holds a valid copy of the object. We call this
case a read hit. Otherwise, it must renew the object by communicating with a read quorum
Rinput of the input quorum system. We call this case a read miss.
Upon receiving a write request from a client, the server contacts every server in a write
quorum Winput of the input quorum system Qinput. Just like in the standard quorum write
protocol, the ADQ write has two phases. First, a server i that receives the clients write request
retrieves the highest logical clock from every server in an Rinput via QRPC. Then, the server
advances the logical clock and assigns it along with its unique id as the write version number.
Second, the server sends the write request with the version number to a Winput quorum via
QRPC. The write completes after i receives acknowledgments from every server in a Winput
quorum. If a Qinput server knows that there is no Routput quorum that has a valid copy in each
server, it can perform the write and send an acknowledgment to i immediately, a case that we
call a write suppress. Otherwise, the Qinput server must rst invalidate a Woutput quorum. We
call this case write through.
Read hit and read miss In order to ensure that reads always return versions of objects
consistent with recent writes, each server maintains a set of per-object and per-server variables.
Each Qinput server maintains a Lamport logical clock lc for generating version numbers for
writes. Both Qoutput and Qinput servers store the newest local copy of an object o in valueo for
local reads and writes. valueo includes a value and a version number. To lter redundant or old
invalidations or updates, each Qoutput server j maintains lastKnowno;i,8i; i 2 Qinput as the high-
est version number of o for which an invalidation or an update has been received from a Qinput
server i. To track the validity of a local cache, each Qoutput server j uses valido;i; 8i; i 2 Qinput
to indicate if j still has a valid local copy from i. valido;i is true if and only if the newest value
received from i is at least as new as lastKnowno;i. To track the callback states of Qoutput, each
10
Figure 3:
Qinput server maintains a pair of variables: lastReado and lastAcko;j ; 8j; j 2 Qoutput:lastReado
stores the newest version of o that i has sent to any Qoutput server; lastAcko;j stores the highest
version number contained in the invalidation acknowledgments from a Qoutput server j for o.
The protocol maintains an invariant: if valido;i = true at j, then lastReado  lastAcko;j at i.
Figure 4: Data structures on each Qoutput and Qinput server for object o.
A Qoutput server j considers an object o valid if its local state satises the following condition:
Validity condition 1 (VC1). 8i; i 2 Qinput; valueo:lc  max(lastKnowno;i) and 9Rinput
s:t:8r; r 2 Rinput; valido;r = true:
If VC1 is true, the cache has the latest version of all learned versions, and j has valid copies
from an Rinput quorum. If j satises VC1, j can directly return the current value to a read
request, i.e., read hit.
11
Otherwise, a read on j is a read miss and j needs to communicate with Qinput servers to get
a consistent version. In particular, j sends object renewal messages to an Rinput quorum via
QRPC to renew the object. Each server i in that Rinput quorum responds to an object renewal
request with its local valueo and then updates its local state lastReado with valueo:lc. Upon
receiving an object renewal reply (o0; lc) from a Qinput server i, if lc  lastKnowno;i, then j
updates lastKnowno;i with lc and sets valido;i to be true; if lc > valueo;lc, then j replaces its
valueo with the value in the reply. When VC1 becomes true, j returns its valueo to the client.
Figure 5:
Invalidation suppress and write through. A Qinput server i processes a write request as
a write suppress when the following condition is true:
Suppress condition 1 (SC1). 8j; j 2 Qoutput; lastReado < lastAcko;j :
If SC1 is true at each server of a write quorum in Qinput, then VC1 must be false at all read
quorums in Qoutput. Therefore, it is safe to suppress the invalidations.
If SC1 is false, it is a write through. To ensure that all read quorums in Qoutput are unable
to read an older value, i needs to do some additional tasks before completing the write. i sends
invalidations with the version number of the write to Qoutput using QRPC. Upon receiving an
invalidation Inval(o; lc) from i, a Qoutput server j updates its lastKnowno;i to lc and sets valido;i
to false if lc > lastKnowno;i. Then, j sends an acknowledgment back to i so that i can update
its lastAcko;j to lc and completes the write after collecting acknowledgments from a Woutput
quorum.
12
Figure 6: Request processing scenarios. (a) Write through example. (b) Write suppress exam-
ple. © Read miss example. (d) Read hit example
5.2 Dual-Quorum with Volume Leases
The ADQ protocol just described allows one to vary read and write quorum sizes independently;
therefore, our target application would benet from using a read quorum size of 1 so that reads
can be serviced locally in the normal case; any larger read quorum size introduces a network
delay to every read and provides qualitatively worse read response time. However, a read
quorum size of 1 could lead to unacceptable write availability because it requires a write to
successfully contact all servers in Qoutput to invalidate cached data in the write through case.
The full DQ protocol therefore adapts Yin et al.s volume lease protocol to support very
small read quorums in Qoutput while retaining acceptable availability on writes. An object lease
represents permission to access an object until specied time. A volume lease is a lease on
a group of objects (volume). Under the volume leases protocol, a client may access a cached
object if it holds valid leases on both the object and the objects volume, and a server can modify
data as soon as either lease expires. The combination of short volume leases and long object
leases yields good read response time and high availability for systems with small Qoutput read
quorums; servers in Qoutput can cache objects locally for a long time to reduce individual object
renewal load, and although they must frequently renew volume leases, the cost is amortized
across a large number of objects in a volume. At the same time, the combination does not suer
13
from poor write availability despite large Qoutput write quorums: a write that cannot contact
all servers in a Qoutput write quorum just needs to wait for the (short) volume lease to expire.
To simplify the description of the protocol, assume innite-length object leases or callbacks.
The protocol can be generalized to nite-length object leases simply by treating lease expiration
like object invalidation in the basic protocol.
Figure 7: Per Qoutput and Qinput server data structure for object o.
Data structures.Each server maintains a set of variables in addition to the basic data
structures First, to track the duration of leases, each server maintains a real-time clock cTime
with a drift rate bounded by maxDrif t. Each server also maintains an expiresv;n indicating
when a volume lease for v on server n expires.
The protocol uses delayed invalidations and epoch numbers to minimize the cost of renewing
volume leases. A volume lease can only be renewed by a Qoutput server if the server can guarantee
that it will not allow access to any stale object in that volume. Naive implementation must
synchronize the state of each object in a volume, which can yield unacceptable overheads and
synchronization delays, especially if volumes span many objects.
Delayed invalidations reduce the cost of short disconnections to O(#(missedinvalidations))
from O(#(objectsinavolume)). When a new write arrives, rather than sending the invalidations
immediately to those Qoutput servers that have valid object leases but expired volume leases,
the Qinput server can defer the invalidation messages because the Qoutput cannot read the object
until it renews the volume lease. It can then send a batch of delayed invalidations when the
Qoutput server renews the volume lease. Therefore, each Qinput server also maintains a per-
volume invalidation buer delayedv;j ; 8j; j 2 Qoutput to store delayed invalidations of objects in
v for server j.
Epoch numbers bound the size of delayedv;j ; 8j; j 2 Qoutput and enable fast resynchronization
after long disconnections. Each Qinput server i maintains an epoch number epochv;j ; j 2 Qoutput
and each Qoutput server j stores the max epochv;j value associated with each object o received
from 8i; i 2 Qinput as epocho;i. Whenever a server garbage collects delayedv;j , it increments
epochv;j . Volume lease renewals and object renewals are marked with epochv;j . When epochv;j
on i changes, j conservatively assumes that all object callbacks from i with old epochs have been
revoked by i so that any subsequent read will revalidate the cache copy. The main dierence
between this protocol and the asynchronous protocol is that the object validity check condition
14
and the write suppress condition are changed because of volume leases. In the rest of this
section, we will describe how those conditions have changed.
Object validity and renewal. A Qoutput server j considers an object o under volume vvalid
if its local state satises the following condition:
Validity condition 2 (VC2).8i; i 2 Qinput; valueo:lc  max(lastKnowno;i) and 9Rinputs:t:8r;
r 2 Rinput; valido;r = true ^ expiresv;r > cT ime:
Similar to the basic protocol, j uses VC2 to decide whether to process a read as a readhit or a
readmiss. In a readmiss, j needs to send dierent requests to dierent Qinput servers and reply
when VC2 becomes true. In particular, for each target server i selected, j sends one of three
things: 1) if the volume from i has expired and the object from i is invalid, it sends a combined
volume renewal and object renewal request; 2) if just the volume has expired, it sends a volume
renewal request; or 3) if just the object is invalid, it sends an object renewal request. The object
renewal process is exactly the same as in the basic DQ protocol described in previous Section
except that each Qinput server i also sends its epochv;j with the object values and j updates its
epocho;i and valido;i. The volume lease renewal needs to do a few more things. Upon a volume
lease renewal request from a Qoutput server j, a Qinput server i sends the delayed invalidations
delayedv;j and a volume renewal message containing a lease length L and the volume epoch
number epochv;j . i then records the volume expiration time (expiresv;j = L + cTime).
When j receives a volume lease renewal reply from j, it rst applies the delayed invalidations
to aected objects as described in previous Section and updates expiresv;i and epocho;i for
all objects under volume v. To account for worst case clock drift and any network delays, j
conservatively sets expiresv;i = to + L  (1

Presented By
Mangesh Chanrakant Swami

---

[attachment=12718]
Seminar onDUAL QUORUM REPLICATION SYSTEM FOR EDGE SERVICES
DEFINITIONS
What is Quorum?
What is Replication System?
What is Edge Service?
Introduction
Object stored on a single server.
But what if the server fails ?
Quorum System
Client needs a quorum of servers to access the object
What is a quorum system?
All quorums must have at least one server in common with all other quorums.
SYSTEM MODEL
front end nodes that handle service client requests from across the Internet, execute application-specific processing, and act as edge server clients or just clients to the dual-quorum storage system
Output Quorum System (OQS) nodes that process client read requests.
Input Quorum System (IQS) nodes that process client write requests.
OPERTION
WRITE:-
Client queries a quorum Q for a timestamp from each server in Q
Client chooses a timestamp t greater than any of those returned, and greater than its own timestamp
Client writes v by sending <v, t> to servers:
Each server updates v if t > v’s timestamp on the server
The server returns an ack regardless of whether it updated v
Once the client has received an ack from every server in some quorum Q’, the write is complete
Q does not have to be the same as Q’
Reads:-
Client queries every server in some quorum Q for value/timestamp pairs <v , t>
Client applies some deterministic function Result(A) to the returned pairs
Result(A) should return the correct value v to indicate a read failure
However, the details of Result(A) are intentionally left unspecified to allow different implementations of quorum systems
Dual-Quorum Protocol Design
The basic idea is to separate the read and write quorum into two quorum systems so that they can be optimized individually to improve response time and availability for read-dominated or write-dominated workloads.
The two quorum systems conditionally synchronize with each other to maintain the consistency of data replicated on them when processing both reads and writes.
The protocol is discussed in two steps:-
Simplified asynchronous DQ (ADQ) protocol:-
This protocol allows independent optimizations of read and writes quorums.
Volume leases to the protocol :-
This protocol used to improve writing availability while retaining good read performance.
Dual Quorum Protocol
Asynchronous Dual-Quorum Protocol:-
Basic read and writes operations
Read hit and read miss
Dual-Quorum with Volume Leases
Data structures
APPLICATION
This protocol used in WAN to access Internet with speed and consistency.
Quorum is also used for sensing in Genomics i.e. Quorum sensing.
Quorums can also be used in Grid Technology.
ADVANTAGES
It is a Fault Tolerance
It can handle concurrent operations.
Improves service availability and latency.
It offers nearly ideal trade-offs among high availability, good performance, and strong consistency.
DISADVANTAGE
Support for data replication is a key problem in realizing the promise of Internet edge services.
CONCLUSION
The Internet edge service architecture attempts to improve service availability and latency by allowing clients to access the closest available edge server rather than a centralized server or a centralized server cluster. To provide a single service from multiple locations, service logic (code) replicated on all edge servers must access a collection of shared data.