RAMP transaction

存储架构 2016-04-13

TL;DR step-by-step visualization of RAMP transactions

Paper Scalable Atomic Visibility with RAMP Transactions (2014)
Isolation level Atomicity + Read Committed
Roundtrips per commit 2 (3 with latency improvements)

Usage in the wild

The algorithm is new and hasn't been noticed in the wild but there there are rumors that Cassandra may support it. Also Facebook reported that they are working on the Apollo database which uses Paxos for replication and CRDT & RAMP for cross shard transactions.


RAMP algorithm solves the problem of simultaneous (atomic) update of set of items distributed between multiple servers (shards).


How to change a set of items

  • For each change of the item send it to shard owning the current version of the item along with the names of all items participating in the transaction (metadata).
  • For each change connect to the its shard and mark the change as committed (if id of the current transaction is greater than id of the previous change).
  • Connect to the shards and mark the commit as confirmed.

How to read a set of items

  • Read the current committed version of the items.
  • If there is a non-confirmed item:
    • (re)-commit the whole transaction which is responsible for the current item (we can do it since we store metadata within each item)
    • confirm the commit
  • Use the metadata to calculate the expected version of the value
  • Fetch the expected version if it's greater than the committed version

The selected steps are not described in the paper but they are necessary if we want to avoid a couple of anomalies. One of them happens when a client reads two items in a transaction, receives new version but then she starts new transaction, reads only one element and receives old version (stale read).

I believe those steps were omitted in the original paper because it was supposed that read transactions should always read the same set of items that were participating in the write transactions. In practice, the latter way has latency penalty because if the items are distributed between different shards and read transaction should always contact all of them.


One of the hardest part of understanding RAMP transactions to me was to come up with an example of the domain where anomalies of the RAMP transactions (lost updates) are explainable and fine from the customer perspective.

The good example is an application like Splitwise which allows customers to split bills between friends and to track how much they own to each other. We can model the domain as a directed weighted graph where nodes represent customers, edges represent debts and distribute it by distributing the nodes with its outgoing edges. With such approach a customer can get a list of its debts by querying only one shard.

Of cause money is classical example where we need serializability, but our application is rather a reminder than bank, so we can relax the guaranties. For example, customers may understand that one of the simultaneous updates to the same data may be canceled, but they can't tolerate inconsistency between views of two customer on how much they own to each other. This is exactly the same guaranties which RAMP transactions provide.

In the step-by-step RAMP visualization I modeled a situation between customers who named just like some of the mathematicians I deeply admire: Evariste Galois, Euclid and Kurt Godel. They take a cab and go to a restaurant, Euclid pays for a ride, Godel handles the restaurant's check and at some point of time they decided to reflect this into the app.

责编内容by:Rystsov's site (源链)。感谢您的支持!


Jepsen: Tendermint 0.10.2 Tendermint is a server and a protocol for building linearizable (or sequentiall...
如何用Python动手写一个NoSQL数据库? 本文完整的示例代码已经放到了GitHub上,这仅是一个极简的Demo,旨在动手了解概念。 (链接 https://github.com/liuch...
Visualizing (scraped) Uber and Lyft Trips in San F... Visualizing Uber and Lyft trips in San Francisco: more than 200,000 ...
HubbleDotNet 开源全文搜索数据库项目–内存索引... 经过2周多的努力,HubbleDotNet 的内存索引功能终于搞好了。有了内存索引,搜索不再去读硬盘,实时性大大提高了。hubble的内存索引不同于lucene...
Large Scale NoSQL Database Migration Under Fire Large Scale NoSQL Database Migration Under Fire ...