Back to index
Transactional Client-Server Cache Consistency: Alternatives and Performance
M.J. Franklin, M.J. Carey, M. Livny
Summary by: Armando Fox and Steve Gribble
Cache consistency for distributed (client-server) DB's is harder to
implement and has more tradeoffs than traditional SMP cache consistency,
because of high message cost, consistency granularity, access
granularity, and ACID semantics.
- Architectures: Query-shipping vs. data-shipping. The latter
accelerates navigation on client, but must exploit client
- Inter-transaction: requires cache consistency protocol.
All proposed algs support ACID isolation or Gray's "degree 3"
(serializable) transaction model.
- Architectural considerations:
- Page vs. object caching
- Aggregate processing/storage likely to be at clients, not
server; putting complexity at server allows support needs
and bulletproofness to be centrally managed
- E.g.: Dynamic replication (based on client demands) and
second-class ownership (server's copy is the truth)
- Taxonomy axes: detection ("lazy") vs. avoidance ("eager")
of accessing stale data.
Same semantics in all algs, so taxonomy based on
- Detection-based can be augmented with optimization hints
(e.g. asynchronous update notifications), but must still function
correctly without them.
- Avoidance-based use Read One/Write All (clients read any copy,
write all copies).
- Detection-based algorithms tradeoffs:
- When to check validity (synchronous on page write, asynch
starting at first write, deferred until commit). Deferred
allows batching and may speed up common case; others may
give fewer stale-data-aborts
- Change notification hints (used for inter-transaction
caching): invalidate vs. update
- Avoidance-based algorithms: client software needs additional
mechanisms to support eager consistency, and server must keep
track of location of every copy (to implement ROWA); use
directory-based cache coherence architecture for scalability.
- When does client declare intention to write: synchronous
(on write-permission fault),
asynchronous, deferred (maybe preferable since consistency
- Write perm duration: this transaction, multiple
- What to do when incoming consistency action can affect
xact locally in progress:
wait for completion, or preempt local xact. Wait can result in
stronger semantic guarantees on reads since forces remote
writer to serialize behind local reader.
- Remote update policy: invalidate, update, or choose
- Performance comparisons on a family of algorithms:
- Server-based 2PL: synchronous validation, verify at write
time that primary copy of page (at server) has same value
before write as your copy.
- Variants: Caching 2PL: cached copies tagged with
version numbers, xacts request lock from server
before modifying page, if version numbers don't
match, server piggybacks latest version on lock
- Variant: Basic 2PL: like Server 2PL, but only
- Callback locking: Synchronous write-intention
declaration. When server sees one, it issues callbacks to
all clients that have the page to invalidate it, then
grants write perm to
- Variant: Callback-All: server callbacks are
"downgrades"--clients may keep page read-only.
If client detects any outstanding write locks, it
rejects downgrade callback and notifies server.
Global deadlock can result, but it's detectable at
- Optimistic 2PL: defer write intention to end of xact's
execution phase. When server grants write locks to
writer, it can either update (O2PL-P) or invalidate
(O2PL-I) other clients that have a copy.
- As with shared-memory cache consistency, performance depends
almost completely on the workload (amount of locality, amount of
read or write sharing, communication-to-computation overhead, etc.)
An encyclopedic and relatively disinterested survey paper; reasonable
taxonomy of what seems like a large and hack-laden design space.
- Still not clear to me that the differences from "traditional" SMP
cache consistency are that large, esp. with respect to
performance evaluation. Seems like designers of these protocols
could have leveraged/learned more than they did from that
Back to index