Enabling Lightweight Transactions Alongside Precision Fourth Dimension (Asplos 2017)

This newspaper is past times Pulkit A. Misra, Jeffrey S. Chase, Johannes Gehrke, Alvin R. Lebeck, together with it appeared at ASPLOS'17.

The newspaper describes *Semel*, a durable multi-version read-optimized key-value store, together with *Milana*, a distributed OCC transaction organisation built on top of Semel.

The master copy ideas inwards the newspaper are to exploit precision fourth dimension (PTP) together with efficient persistent retentiveness based on flash NVM/SSD, together with to exhibit how they helped for edifice OCC based distributed transactional system. In a way, this newspaper revisited together with revised Thor together with showed the benefits achievable from using modern clocks together with storage technologies within a datacenter. Thor (Sigmod 1995), was from Barbara Liskov's group, together with introduced loosely synchronized clocks for OCC, together with performed validation on the storage servers.

Before nosotros summarize Semel together with Milana, let's recap the master copy contributions of this paper:

1. Move ordering off the critical path: Each version of a key's value is timestamped using PTP. These timestamps enable using a lightweight primary-backup replication protocol that moves update ordering off the critical path. (In this way the newspaper is like to TAPIR from OSDI-15, which leverages NTP based ordering for edifice geo-replicated transactional storage over unordered replication.)
2. Use of *optimistic concurrency control* (OCC) inwards Milana to back upward serializable ACID transactions over Semel. Each transaction executes on a unmarried customer (i.e., an application server). The customer issues read/write requests to Semel storage servers, assigns PTP timestamps for start, destination of transactions, together with acts every bit the coordinator to commit or abort the transaction.
3. Modifying the erase-before-write (remap-on-write) direct of SSDs Flash Translation Layer (FTL) to enable inexpensive multi-version storage together with to integrate version management amongst FTL garbage collection
4. Leveraging the primary/backup replication inwards Semel to trim OCC validation costs, such that write validation occurs solely on the primary for each affected shard, together with read-only transactions (served every bit consistent snapshots) validate locally at the client

Here is the presentation on this from our Zoom Distributed Systems Reading Group.

Semel

Semel uses primary/backup replication amongst a designated primary for each shard. It exploits PTP to relax the ordering requirement together with commit each update every bit presently every bit a bulk of replicas ACK it.

• Since the replicated Semel operations are timestamped writes to independent versions of independent information items, in that place is no ask to hold ordering
• The ordering is explicit inwards the version timestamps, which are recovered along amongst the data
• A server executes reads on the named version together with rejects writes amongst timestamps older than the electrical current version, guaranteeing at-most-once semantics

A key-value shop implemented using traditional SSDs requires 2 mapping steps: mapping Key to Logical Block Address (LBA) together with hence mapping LBA to <PBN, Page>, the physical block number. However, it is possible to alteration the FTL to collapse this two-step translation into a unmarried translation, hence that it maps a fundamental straight to a physical address amongst a unmarried map tabular array access.


Keeping versions approximately longer than necessary on flash-based systems may campaign wasteful remapping (moving) during garbage collection. Semel tries to remainder flash remapping toll amongst the wish to render historical versions within a sure enough window size, e.g., continue all versions that are less than v seconds old. Semel utilizes watermarking to constitute a lower leap on the customer clocks. Each customer periodically broadcasts the timestamp of its concluding acknowledged functioning to all storage servers. The minimum of all these timestamps is the watermark inwards Semel. This way that the clients are non whatever random client, but a laid of application servers that Semel together with Milana continue rail of to update the watermark.

SEMEL's approach to linearizable RPC is like inwards spirit to RIFL, which every bit good timestamps requests at the customer together with persists a completion tape containing each request's timestamp amongst the object. The fundamental departure is that SEMEL's asking timestamps are global together with synchronized across the clients. Precise clocks enable Semel to simplify the ordering protocol.

Milana

Milana leverages Semel's precision timestamps together with builds OCC based transactional organisation adapted to a client/server setting. In Milana, for an update transaction T, the customer start performs the reads from the primaries responsible, stages the write locally, together with hence validates T earlier committing via a 2 stage commit which involves the primaries involved.


Each primary uses Algorithm 1 to validate T's keys. As Algorithm 1 shows, this is done past times comparison T's timestamped read-write accesses to those of other transactions to position whatever access conflicts that violate a serializable ordering. T fails validation if it has conflicts that violate serializability. If T passes validation at the primary, the primary hence propagates the validation conclusion (SUCCESS/ABORT) along amongst the write laid (on successful validation) together with shard listing to the backup replicas, waits for f (out of 2f) backups to respond, together with hence reports the conclusion every bit its vote to the client/coordinator. If a primary votes to commit T hence T is prepared at that primary.


The customer accumulates the votes from all primaries together with determines the outcome: T commits iff all primaries vote to commit, else T aborts. The customer reports the effect to the application together with hence asynchronously notifies all primaries of the outcome. Conflicting transactions are aborted together with hence restarted at the client.

Apart from update transactions, Milan provides efficient snapshot reads. Milana satisfies T's reads for a fundamental K past times returning a version that is electrical current every bit of T's $ts_{begin}$, fifty-fifty if a author has written a novel version of K amongst a subsequently timestamp. The newspaper shows that this reduces fake conflicts together with improves concurrency together with throughput.

Moreover, the Milana clients perform local validation for read-only transactions, because they tin skip the 2 stage commit required for update transactions. Local validation allows a read-only transaction T to commit iff the values inwards T's read laid are from a consistent snapshot:

• each value for a fundamental K inwards T's read laid is the youngest committed version of K amongst timestamp $\leq ts_{begin}$, and 
• no fundamental K inwards the read laid has a prepared version amongst timestamp $\leq ts_{begin}$

Local validation ensures a serializable transaction ordering for read-only transactions, but it does non necessarily render external consistency. Milana provides both serializability together with external consistency for read-write transactions, which validate on the servers.

If a primary of a participant shard fails hence it would block all transactions involving that shard. A novel primary must last elected (failover) inwards lodge to unblock whatever running transactions together with resume service. The newspaper mentions that every bit long every bit a bulk of replicas (f + 1) of all shards are available, it is possible to resume service together with consummate whatever outstanding transaction.

Evaluation

The evaluation shows that

• Semel achieves 20%-50% higher IOPs than a traditional dissever version together with flash management approach.
• Compared to NTP, PTP enables purpose of OCC amongst upward to 43% lower transaction abort rates.
• Under the Retwis benchmark, client-local validation of read-only transactions yields a 35% reduction inwards latency together with 55% growth inwards transaction throughput for read-heavy workloads.

The evaluation is done within a datacenter, non including cross-datacenter experiments. They cite that NTP shows an average skew of 1.51 milliseconds amid clients, spell software timestamped PTP has average skew of 53.2 microseconds. The evaluation did non regard fault-tolerance. Also the FTL remapping was done inwards emulation using the Open-Channel SSD framework, together with non on existent hardware.

Share this post