Transcript Frolund Presentation

e-Transactions: End-to-End Reliability
for Three-Tier Architectures
Svend Frølund and Rachid Guerraoui
Applicable to three-tier architectures
• Front-end clients
• Middle-tier application servers
• Back-end database servers
Three-tier Architecture
Typical three-tier architectures fail
to provide reliability guarantees
• At-most-once processing: request is
executed once or not at all
• Server failure results in error
• No knowledge if transaction was
successful
• Resubmitting request may result in
duplicate transaction
Exactly-once transaction abstraction
• Mask failures in the middle
and back-end tiers
• Eliminate resubmission
• What if client crashes?
e-Transactions
• Guarantees exactly-once
transaction, unless the client crashes
• If the client crashes, at-most-once
processing can be assumed
• Up to user to figure out what has
happened
• Crashed client does not affect other
clients
Need for e-Transactions:
Improvements over existing reliability
concepts for three-tier architectures
• Addresses all three tiers
• Includes liveness properties of
replicated services
• Also includes safety properties of
transaction-processing systems
e-Transactions Algorithm
• Distributed commit scheme
• Primary-backup replication scheme
• Interfaces with COTS technologies,
particularly database servers
• Client does not need access to local
storage
• Assumes perfect knowledge about
failures
e-Transactions Model: System
• Distributed System
• Finite processes communicate by
message passing
• A process is either up or down
• Crash – transition from up to down
• Recovery – transition from down to up
• Crash has no impact on stable storage
• Processes do not behave maliciously
• Communications are reliable
e-Transactions Model: Clients
• Set of processes (ci  Client)
• Domain of request values and
domain of result values
• (nil  Request  Result)
• Operation issue() : Request 
Result
e-Transactions Model:
Application Servers
• Set of processes (ai  AppServer)
• Application servers are stateless
• Function compute() : Request 
Result
• Compute function is non-blocking
e-Transactions Model:
Database Servers
• Set of processes (si  Server)
• Function vote() : Result  Vote
where Vote = {yes, no}
• Function decide() : Result 
Outcome  Out-come where
Outcome = {commit, abort}
e-Transactions Specification
• Termination – liveness guarantee by
preventing blocking situations
• Agreement – safety guarantee by
ensuring consistency of client and
databases
• Validity – restrict the space of
possible results (exclude
meaningless results)
e-Transactions Specification:
Termination
• (T.1) If the client issues a request,
then, unless it crashes, the client
eventually delivers a result
• (T.2) If any database server votes for a
result, then the database server
eventually commits or aborts the
result
e-Transactions Specification:
Agreement
• (A.1) No result is delivered by the
client unless the result is committed
by all database servers
• (A.2) No database server commits
more than one result for the same
request
• (A.3) No two database servers decide
differently on the same result
e-Transactions Specification:
Validity
• (V.1) If the client issues a request and
delivers a result, then the result has
been computed by an application
server with the request as a
parameter
• (V.2) No database server commits a
result unless all database servers
have voted yes for that result
e-Transactions Implementation:
Assumptions
• Closed system, the only entities are
the client, the application servers, and
the database servers
• Communication channels are reliable
• Knowledge of failures is perfect
e-Transactions Implementation:
Client Algorithm
e-Transactions Implementation:
Database Server Algorithm
e-Transactions Implementation:
Primary Application Server Algorithm
e-Transactions Implementation:
Backup Application Server Algorithm
e-Transactions Protocol
Correctness: Lemma1
No primary application server
remains blocked forever in one of the
wait statements of lines 8, 10, 14, and
17, in the primary application server
algorithm
e-Transactions Protocol
Correctness: Lemma2
Let t be any time. 1) At most one
application server is the primary
application server at t and 2) there is
a time t’ ≥ t after which some
application server remains primary
forever
e-Transactions Protocol
Correctness: Lemma3
(Termination T.1)
If the client issues a request, then
unless it crashes, the client
eventually delivers a result
e-Transactions Protocol
Correctness: Lemma4
(Termination T.2)
If any database server votes for a
result, then the database server
eventually commits or aborts the
result
e-Transactions Protocol
Correctness: Lemma5
(Agreement A.1)
No result is delivered by the client,
unless the result is committed by all
database servers
e-Transactions Protocol
Correctness: Lemma6
(Agreement A.2)
No database server commits more
than one result for the same request
e-Transactions Protocol
Correctness: Lemma7
(Agreement A.3)
No two database servers decide
differently for the same result
e-Transactions Protocol
Correctness: Lemma8
(Validity V.1)
If the client issues a request and
delivers a result, then the result has
been computed by an application
server with the request as a
parameter
e-Transactions Protocol
Correctness: Lemma8
(Validity V.2)
No database server commits a result
unless all database servers have
voted yes for that result
e-Transactions Performance
• Latency – 16% increase over baseline
unreliable algorithm, compared to
23% increase over baseline for a 2PC
algorithm that guarantees at-mostonce semantics
• Scalability – linear increase in
response time with respect to the
number of database servers
e-Transactions Related Work:
Transaction Monitors
• Middle-tier server encapsulates
processing as an atomic transaction
• Assumes stable storage at the client
• Nothing prevents transaction
coordinator from crashing and
blocking all participants
e-Transactions Related Work:
Persistent Queues
• Client submits request through a
persistent client-queue
• Server processes request and stores
result into a persistent server-queue
• Client and server queues must be
replicated with additional cost
• Atomic commitment mechanism to
avoid blocking
e-Transactions Related Work:
Message Logging
• Clients log incoming and outgoing
requests
• Server logs incoming requests and
outgoing replies
• Server stores database operations
• Requires intertransaction state at the
client
e-Transactions Related Work:
Object Groups
• Single transaction entity that is made
highly available through a replication
and coordination protocol
• Overhead of coordinating replicated
application servers
• Replication of database servers
makes use of COTS databases
complicated
e-Transactions Current Status:
Total-e-Transactions
• HP distributed transaction
management system
• Java implementation based on Sun’s
Java Transaction Service standard
• Utilizes OMG’s Object Transaction
Service for Interoperability
References
• e-Transactions: end-to-end reliability for three-tier
architectures
Frolund, S.; Guerraoui, R.; Software Engineering, IEEE
Transactions on Volume 28, Issue 4, April 2002
Page(s):378 – 395
• Three Tier Software Architectures
(http://www.sei.cmu.edu/str/descriptions/threetier.html)
• Total-e-Transactions Frequently Asked Questions
www.hpmiddleware.com/downloads/ pdf/Total-eTransactions_2.2_FAQ.pdf