Friday, April 11, 2014

Scalable Atomic Visibility with RAMP Transactions

Peter Bailis - We recently wrote a paper that will appear at SIGMOD called Scalable Atomic Visibility with RAMP Transactions. This post introduces RAMP Transactions, explains why you should care, and briefly describes how they work.

Executive Summary -

What they are: We’ve developed three new algorithms—called Read Atomic Multi-Partition (RAMP) Transactions—for ensuring atomic visibility in partitioned (sharded) databases: either all of a transaction’s updates are observed, or none are.

Why they’re useful: In addition to general-purpose multi-key updates, atomic visibility is required for correctly maintaining foreign key constraints, secondary indexes, and materialized views.

Why they’re needed: Existing protocols like locking couple mutual exclusion and atomic visibility. Mutual exclusion in a distributed environment can lead to serious performance degradation and availability problems.

How they work: RAMP transactions allow readers and writers to proceed concurrently. Operations race, but readers autonomously detect the races and repair any non-atomic reads. The write protocol ensures readers never stall waiting for writes to arrive.

Why they scale: Clients can’t cause other clients to stall (via synchronization independence) and clients only have to contact the servers responsible for items in their transactions (via partition independence). As a consequence, there’s no mutual exclusion or synchronous coordination across servers.

The end result: RAMP transactions outperform existing approaches across a variety of workloads, and, for a workload of 95% reads, RAMP transactions scale to over 7 million ops/second on 100 servers at less than 5% overhead.

Where the overhead goes: Writes take 2 RTTs and attach either a constant (in RAMP-Small and RAMP-Hybrid algorithms) or linear (in RAMP-Fast) amount of metadata to each write, while reads take 1-2 RTTs depending on the algorithm.

Read the paper here

Leave a Reply

All Tech News IN © 2011 & Main Blogger .