Salt: Combining Acid As Well As Base Of Operations Inwards A Distributed Database

This newspaper appeared inward OSDI'14. The authors are Chao Xie, Chunzhi Su, Manos Kapritsos, Yang Wang, Navid Yaghmazadeh, Lorenzo Alvisi, as well as Prince Mahajan, all from The University of Texas at Austin. Here you lot tin sentinel a video of the OSDI presentation of the paper, as well as too notice the presentation slides as well as the newspaper available every bit opened upwards access.  USENIX knows how to practise conferences right.

Dropping ACID

ACID (Atomicity, Consistency, Isolation, Durability) approach provides ease-of-programming through its unproblematic transaction abstraction, simply loses on the performance. BASE (Basically-Available, Soft state, Eventually consistent) approach, popularized past times the NoSQL systems, provides expert performance (low-latency, high-throughput, as well as scalability), simply loses on the ease-of-programming due to increased complexity of concurrent execution inward distributed systems.

This newspaper introduces Salt, which aims to notice a best-of-both-worlds middle ground: to supply high performance similar BASE alongside small-scale programming endeavor similar ACID.

Less is more

Salt approach is motivated past times the next observation (which is an instance of the Pareto principle). I am quoting from the paper:

"When an application outgrows the performance of an ACID implementation, it is frequently because of the needs of alone a handful of transactions: most transactions never examine the limits of what ACID tin offer. Numerous applications [2, 4, 5, 10, 11] demonstrate this familiar lopsided pattern: few transactions are performance-critical, spell many others are either lightweight or infrequent." 

Of course, a amend quantification than saying "numerous" or "many" applications would brand the declaration for the Salt approach stronger. However, such an extensive written report may own got several months, as well as is unfair to enquire for a conference newspaper submission.

It is tempting to increment the concurrency of those critical ACID transactions past times splitting them into smaller mini ACID transactions. However, doing thus may non move prophylactic every bit you lot would lose Atomicity (which frees you lot from worrying nearly intermediate states during failures) as well as Isolation (which regulates which states tin move accessed when transactions execute concurrently). The newspaper calls this a stark selection as well as cites the YouTube clip from Butch Cassidy to farther drive this betoken habitation (I am non kidding).

The paper's proposal is this. Instead of worrying nearly all possible Atomicity & Isolation complications alongside all other ACID transactions, Salt categorizes transactions into ACID transactions as well as a little number of BASE transactions, as well as lets you lot worry alone nearly checking Atomicity & Isolation complications betwixt the BASE transactions.

Of course of pedagogy at that topographic point is an unmentioned complication here. You too own got to ensure that these BASE transactions leave of absence the database inward consistent state. This is non an slow describe every bit well, as well as opens upwards Salt's ease-of-programming to debate. On the other hand, you lot would own got to worry nearly this for all operations if you lot implement a full-BASE solution.

The Salt approach

Actually Salt's BASE transactions approach gets its inspiration from the ACID nested transactions. The newspaper says:

"Nested transactions is an abstraction originally introduced to offer, for long-running transactions, atomicity at a finer granularity than isolation. Our operate inward introducing BASE transactions is similar inward spirit to that of traditional nested transactions: both abstractions aim at gently loosening the coupling betwixt atomicity as well as isolation. The number that BASE transactions address, however, is the flip side of the 1 tackled past times nested transactions: this time, the challenge is to supply isolation at a finer granularity, without either drastically escalating the complexity of reasoning nearly the application, or shattering atomicity."

By providing isolation at a finer granularity, Salt allows BASE transactions to accomplish high concurrency past times observing each other's internal states, without affecting the isolation guarantees of ACID transactions. A BASE transaction is made upwards of multiple mini-transactions, called element of group I subtransactions. (Yes, the newspaper makes several Chemistry puns.) The committed nation of an element of group I subtransaction is observable past times other BASE or element of group I subtransactions. On the other hand, the committed nation of an element of group I subtransaction is non observable past times other ACID transactions until the bring upwards BASE transaction commits.  As such, Salt guarantees that, when BASE as well as ACID transactions execute concurrently, ACID transactions retain, alongside abide by to all other transactions (whether BASE, alkaline, or ACID), the same isolation guarantees they used to savour inward a purely ACID environment.

The proverbial Bank example

When you lot beak nearly ACID versus BASE the classical instance is the banking corporation coin transfer example. The newspaper gives a pure ACID, a pure BASE, as well as a Salt implementation of this example.

I wonder, which implementation is closer to the agency the coin transfers are genuinely handled inward existent banks. If somebody familiar alongside how banks grip the coin transfer tin weigh inward on this, that may shed a lite on this debate.  My coin is on the pure BASE approach.

Something nearly this banking corporation instance is strange though. The total-balance functioning is an unrealistic big/monolithic operation. Why did that own got to move a transaction? The total-balance functioning could move done alongside a consistent/timed snapshot, no? Then why did it own got to move a transactions spanning/freezing the entire system?

Now let's banking corporation fit the 3 implementations to a greater extent than closely. The implementation inward Figure 1.a (ACID) uses alone 1 type of locks, ACID locks. Figure 1.b (BASE) uses alone 1 type of locks, local locks. BASE programming looks similar classical distributed organization programming, it tries to practise everything alongside local asynchronous actions every bit much every bit possible. Figure 2 (Salt) uses Alkaline, Saline, as well as ACID locks.

Why does Salt involve 3 unlike locks? Because the commencement element of group I transaction is special, every bit it determines whether the entire BASE transaction it is included inward volition succeed or not. If that commencement element of group I subtransaction succeeds, as well as thus comes the saline-lock to brand the intermediate states inward the repose of the BASE transaction available to other BASE as well as element of group I transactions. But then, this is something I am soundless non clear on. Salt attributes significance to the commencement element of group I subtransaction, thus its pattern should too move special. But I am unclear nearly what should acquire inward that subtransaction? Are at that topographic point guidelines to pattern that commencement subtransaction thus it captures the successful completion of the repose of the BASE transaction?

Evaluation

Like whatever OSDI/SOSP newspaper worth its tabular array salt (see, I tin too brand "Salt" puns :-), the newspaper includes a potent evaluation section. The authors implemented a Salt image past times modifying MySQL Cluster. They evaluated the image using the TPC-C benchmark, which consists of five types of transactions: new-order (43.5%), payment (43.5%), stock-level (4.35%), order-status (4.35%), as well as delivery (4.35%). The results exhibit that past times BASE-ifying 2 of these transactions, Salt achieves 80% of maximum throughput of a total BASE implementation.

Notice the left side of Figure 7, which shows that ACID version faster than the Salt version nether depression load. The newspaper doesn't hash out this but, if nosotros had both ACID as well as BASE version of transactions, it may move possible to hot-swap betwixt these ii versions to optimize the throughput of the organization depending on the electrical flow organization load.

Related work

The newspaper fails to cite several papers that proposed orthogonal approaches to bargain alongside the same problem: improving the performance of ACID transactions, spell keeping the ease-of-programmability.

The Red-Blue Actions newspaper (OSDI'12) considered the work of reducing the granularity of ACID transactions past times using a generator functioning as well as shadow functioning as well as categorizing the operations  as scarlet (consistency critical) as well as bluish (fast as well as eventually consistent). That newspaper too uses a Bank example.

Then at that topographic point are piece of work from the Berkeley grouping on this problem. I had summarized the Invariant-based coordination avoidance newspaper earlier. There is too the Highly Available Transactions newspaper  (VLDB'13) where they  look at ACID isolation degree relaxing for improving availability.

Discussion

The newspaper proposes the Salt approach assuming the ACID implementation of the application is already present. The application for this is if you lot already own got an ACID system, you lot tin Salt it to fine-tune the performance. Another approach would move to start alongside a BASE implementation as well as to increment atomicity/isolation for a twain operations. Maybe for to a greater extent than or less applications, it volition move easier for going from BASE to Salt: Starting alongside BASE as well as and thus adding Alkaline subtransactions as well as ACID transactions (if necessary).

The Salt approach practise require a learning bend as well as tin move tricky. But how practise nosotros debate the complexity of the programming endeavor needed for 1 approach (say Salt) versus the other (say pure BASE) inward an objective manner? One tin objectively exhibit performance improvements alongside evaluations, simply it is harder to debate for "ease of programming" inward an objective/quantitative manner.

There tin too move to a greater extent than or less complications alongside the early-committing (after the commencement element of group I subtransaction) inward BASE transactions. This query came upwards inward the OSDI presentation. If deadlock occurs the MySQL Cluster approach is to utilisation timouts as well as scroll the transactions back. In this case, Salt throws exceptions which the developer involve to address to re-achive consistency as well as atomicity.

Share this post