Paper Summary: Granola, Depression Overhead Distributed Transaction Coordination

This newspaper is yesteryear Cowling as well as Liskov, as well as it appeared at Usenix ATC'12.  Most closely related papers to this newspaper are the Sinfonia as well as Calvin papers. So, it may move helpful to besides read the summaries of those papers from the links inwards a higher house to familiarize yourself with them.

This newspaper looks at coordination of 1-round transactions, which are dissimilar from full general transactions that involve multi-round interaction with the client. 1-round transactions execute at the player nodes, with no communication with other nodes except for at most a unmarried commit/abort vote.

Figure 1 shows the organization architecture. The clients are the transaction managers for these 1-round transactions. They initiate transactions as well as evaluate the commit/conflict/abort decisions returned for the transactions. The repositories communicate with i roughly other (for at most a unmarried commit/abort vote) to coordinate transactions.

There are 2 types of transactions inwards Granola: coordinated ones, as well as uncoordinated ones. Actually, better/less-confusing names for these 2 types would move lock-coordinated transactions as well as timestamp-coordinated transactions, since the latter type of transactions even so involve coordination alongside the repositories.

To reverberate this duality inwards coordination mode, each repository runs inwards i of 2 modes. When at that spot are no coordinated transactions running at a repository, it runs inwards timestamp mode. When a repository receives a asking for a coordinated transaction, it switches to the locking mode.

Uncoordinated transactions

There are 2 kinds of uncoordinated transactions: unmarried repository transactions, or independent distributed transactions. Granola uses a timestamped-based coordination to furnish serializability to both kinds of uncoordinated transactions as well as avoids locking for them. Examples of independent distributed transactions include read-only transactions, as well as local-read transactions, such equally laissez passer on every employee a 2% raise.

(In our previous work, the slow-fast newspaper (2010), nosotros had besides made an analysis similar to the independent transactions idea. Our slow-fast analysis inspects the plan actions, which are precondition guarded assignment statements, as well as determined for which actions the atomicity tin move relaxed so that they tin execute inwards an uncoordinated manner. Our finding was that if the precondition of a plan activeness is "locally-stable" (i.e., this precondition predicate cannot move out falsified yesteryear execution of other plan actions), as well as so it is security to execute this plan activeness inwards an uncoordinated/nonatomic manner.)

Repositories are assumed to bring access to loosely synchronized clocks (say NTP synchronized clocks). The job of timestamps inwards Granola are for ordering/serializability of transactions, as well as logical clocks would besides suffice. Granola needs fourth dimension synchronization for performance/throughput non for correctness. This separation is e'er a welcome one. (I can't resist but refer to our hybrid logical clock, HLC, work here. I mean value HLC would improve exposition of Granola, as well as would brand it tolerant to malformed clients which may increase highTS as well as deny service to normal clients' requests.)

Figure five shows the straightforward unmarried repository execution, as well as Figure vi shows the to a greater extent than interesting independent transaction execution. Since these are 1-round transactions, the commit/abort decisions are local as well as one-shot at repositories. Voting is used to notify other repositories almost the local determination (a conflict vote campaign a repository to abort the transaction), as well as besides for nominating a proposed timestamp for the transaction. The transaction is assigned the highest timestamp from alongside the votes.

In the "pure" timestamp mode, all unmarried repository as well as independent distributed transactions commit successfully, as well as serializability is guaranteed equally they are executed inwards timestamp order. This provides a substantial reduction inwards overhead from locking as well as aborts, which improve the throughput.

While inwards the timestamp mode, coordinated transactions may besides move out inwards which may Pb to conflict decisions to move returned for the unmarried or distributed independent transactions executing on those repositories. Those repositories volition switch to coordinated mode to serve the coordinated transactions. Once all coordinated transactions bring completed those repositories tin in i trial to a greater extent than transition to the timestamp mode.

Dually, inwards locking mode, repositories tin even so serve unmarried repository as well as distributed independent transactions provided they gain non conflict, i.e., they gain non involve to update a locked item. (In effect, the timestamp mode is simply a shortcut to announce the lack of whatever coordinated transactions inwards the system.)

Coordinated transactions

Figure seven shows coordinated transaction execution. Coordination is needed for a transaction that requires a remote read for abort/commit decision. For example, the transaction to transfer \$50 from Alice's concern human relationship to Bob's concern human relationship get-go needs to remote-read Alice's concern human relationship to certify that it indeed has to a greater extent than than \$50. (Recall that inwards contrast for an independent distributed transaction the read, or the guard of the transaction, was local: laissez passer on every employe 2% raise.) Different from independent distributed transaction execution, the coordinated transaction execution involves a prepare stage to instruct required locks. Locks ensure serializability for coordinated transaction execution. So timestamp gild may non move satisfied inwards commit of transactions, as well as thus, external consistency may non move provided for coordinated transaction execution.

Discussion

This newspaper is written with a focus on describing the organization inwards reasonable item to potential users of the system. This diverges a fight from the academic style, which would seat the focus on the novelties as well as "intellectual merit" (a la NSF). Maybe this is because of the style/focus of the USENIX ATC conference. The evaluation department is besides actually prissy as well as detailed. (Granola performs similar Sinfonia for coordinated transacations, as well as improve throughput for uncoordinated transactions.)

It seems that Granola does non offering much payoff over Calvin. The newspaper compares inwards the related piece of work with Calvin as well as states the following. "The Calvin transaction coordination protocol was developed inwards parallel with Granola, as well as provides similar functionality. Rather than using a distributed timestamp voting scheme to decide execution order, Calvin delays read/write transactions as well as runs a global understanding protocol to gain a deterministic locking order."

I mean value Granola may bring an border over Calvin for low-latency, peculiarly for transactions that involve a brace repositories. The best agency to meet why is to consider this analogy.
Granola:Calvin :: CSMA:TDMA.

Share this post