Transactional Client-Server Cache Consistency: Alternatives and Performance

One-line summary: 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.

Overview/Main Points

• Architectures: Query-shipping vs. data-shipping. The latter accelerates navigation on client, but must exploit client caching:
  • intra-transaction
  • 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 performance implications.
  • 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. Tradeoffs:
  • When does client declare intention to write: synchronous (on write-permission fault), asynchronous, deferred (maybe preferable since consistency actions expensive).
  • Write perm duration: this transaction, multiple transactions.
  • 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 dynamically.
• 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 grant.
    • Variant: Basic 2PL: like Server 2PL, but only intra-xact caching.
  • 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 requester.
    • 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 server.
  • 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.)

Relevance

Flaws

• 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 previous work.