Skip to content


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP


dgomezferro edited this page · 33 revisions
Clone this wiki locally

Welcome to the omid wiki! Omid stands for Optimistically transaction Management In Data stores. Here, we walk you through the architecture of CrSO in omid project and explain how you could use it.

What is CrSO?

CrSO adds lock-free transactional support on top of HBase. CrSO benefits from a centralized scheme in which a single server, called status oracle, monitors the modified rows by transactions and use that to detect write-write conflicts. HBase clients in CrSO maintain a read-only copy of transaction commit times to reduce the load on the status oracle, making it scalable up to 50,000 transactions per second (TPS).

Why transactions?

A transaction comprises a unit of work against a database, which must either entirely complete (i.e., commit) or have no effect (i.e., abort). In other words, partial executions of the transaction are not defined. Without the support for transactions, the developers are burdened with ensuring atomic execution of a multi-row transaction despite failures as well as concurrent accesses to the database by other transactions. Data stores such as HBase, BigTable, PNUT, and Cassandra, usually lack this precious feature.

Why CrSO?

  1. CrSO is lock-free. In lock-based approaches, the locks that are held by the incomplete transactions of a failed client prevent others from making progress. In CrSO, if a client is slow or faulty, it does not slow down the other clients.
  2. CrSO does not require any modification into HBase code. All the transactional logic is implemented in the status oracle and the clients.
  3. CrSO does not require any change into HBase table schema. The only change into the data is that the version of an inserted value is assigned to the transaction start timestamp, to enable the transactions to read from a snapshot.
  4. Contrary to previous approaches the commit timestamps are not persisted into data servers. CrSO, therefore, brings transaction support to distributed data stores with a negligible overhead on the HBase servers. CrSO, therefore, enables transactions for many applications running on top of HBase with no perceptible impact on performance.

What is snapshot isolation?

Snapshot isolation guarantees that all reads of a transaction are performed on a snapshot of the database that corresponds to a valid database state with no concurrent transaction. To implement snapshot isolation, the database maintains multiple versions of the data in some data servers, and transactions, run- ning by clients, observe different versions of the data depending on their start time. Implementations of snapshot isolation have the advantage that writes of a transaction do not block the reads of others. Two concurrent transactions still conflict if they write into the same data item, say a database row.

What the status oracle does?

In the centralized implementation of snapshot isolation, a single server, i.e., the status oracle, receives the commit requests accompanied by the set of the identifiers (id) of modified rows, R. Since the status oracle has observed the modified rows by the previous commit requests, it has enough information to check if there is temporal overlap for each modified row. The timestamps are obtained from a timestamp oracle integrated into a status oracle and the uncommitted data of transactions are stored on the same data tables.

For each transaction, the status oracle server sends/receives the following main messages:

  • Timestamp Request/Timestamp Response,
  • isCommitted Query/isCommitted Response,
  • Commit Request/Commit Response,
  • Abort Cleaned-up.

Status Oracle in action

Since the timestamp oracle is integrated into the status oracle, the client obtains the start timestamp from the status oracle. The following list details the steps of transactions:

  • Single-row write. A write operation by transaction txn_w_ is performed by simply writing the new data with a version equal to the transaction start timestamp, Ts(txn_w_).
  • Transaction commit. After a client has written its values on the rows, it tries to commit them by submitting to the status oracle a commit request, which consists of the start timestamp Ts(txn_w_) as well as the list of all the modified rows, R. If the status oracle aborts the transaction, the client must clean up the modified rows.
  • Single-row cleanup. After a transaction aborts, it should clean up all the modified rows. To clean up each row after an abort, the transaction deletes its written versions. This is an extra overhead on data servers, which occurs rarely, only after aborts.
  • Single-row Read. Each read in transaction txnr must observe the last committed data before Ts(txn_r_). To do so, starting with the latest version (assuming that the versions are sorted by timestamp in ascending order), it looksvfor the first value with commit timestamp δ, where δ < Ts(txn_r_). To verify, the transaction inquires the txn_w_ commit time of status oracle.
Something went wrong with that request. Please try again.