About Omid
Omid (Optimistically transaction Management In Data-stores) is an open-source project started at Yahoo back in 2011 that provides transactions to big data stores in the NoSQL ecosystem (e.g. HBase)
Here, we walk you through the motivation behind Omid and its basic concepts and high-level architecture. If you want to skip to a more hands-on approach to Omid, please jump to Getting Started section. If you want more information about the internals, please refer to the Technical Documentation section.
A transaction comprises a set of data manipulation operations on the state of a database system managed as a single unit of work, so all the operations must either entirely be completed (committed) or have no effect (aborted). In other words, partial executions of the transaction are not defined (nor desired in general) because the final state of the database can be corrupted.
Without the support for transactions, developers are burdened with ensuring atomic execution of scattered changes in data upon failures as well as when there are concurrent accesses to the same data by multiple clients.
In order to process transactions, database systems provide a specific component called the Transaction Manager. The goal of transaction managers in general is to guarantee the so-called ACID properties of transactions: Atomicity, Consistency, Isolation and Durability. However, ACID properties are hard to scale when databases have to deal with very large amounts of data and thousands of concurrent users, because the data must be partitioned, distributed and replicated. That was the main reason why, with the advent of NoSQL big data stores, transactions were initially left out of the equation. HBase, Dynamo, BigTable, PNUTS, Cassandra, etc. lacked this precious feature initially. However, with the popularization of NoSQL big datastores in many areas of the industry, the need for transactions has become a must for certain applications.
Omid fills this gap and provides lock-free transactional support on top of HBase with snapshot isolation guarantees.
When solving the conflict detection problem in transactional systems, there are two main approaches that transaction managers may implement: locking and lock-free.
With a locking mechanism, the client managing the transaction attempts to acquire a lock on each cell in the writeset (the set of changes in data performed by the transaction) before committing. If it succeeds in acquiring the lock, and no other transaction has written to the cells since the start of the client's transaction, it can commit, as it knows that no other transaction can write to the cell after the lock has been acquired. Once the commit has completed, the client can release the locks on the cells. If the client fails to acquire the lock on any cell or some other transaction has written to it since the start of the transaction, then the transaction is aborted.
Percolator uses a locking mechanism in its transactional system, and so do other subsequent academic and open source transaction managers for NoSQL datastores.
Locking systems can be problematic in a distributed setting and in the presence of process failures. If a client fails while holding a lock another process must clean up the locks held by that client. However, it is impossible to detect reliably if a client has failed or is just being slow. Normally this is dealt with using timeouts, after which the client is invalidated and its locks released. However, the timeout must be high enough to ensure that valid clients are not invalidated.
In lock-based systems, it is also possible for two transactions to repeatedly conflict with each other over multiple retries as there is no defined order in which locks must be acquired.
In a lock-free mechanism, this type of livelock is not possible. Transactions can always make progress. A lock-free mechanism has a centralized conflict detection mechanism. To commit a transaction, each transaction writeset is sent to this mechanism to check for conflicts with the writesets of other concurrent transactions. If none of those transaction has written to any of the cells of the writeset since the start of the transaction, the transaction can commit. Otherwise the transaction is aborted. Omid uses a lock-free mechanism for conflict detection.
Isolation in ACID refers to the ability for multiple clients to act on a database without interfering with each other. There are various isolation levels, each making a different tradeoff between isolation and concurrent access to the database. Omid is only concerned with Snapshot Isolation.
Snapshot Isolation (SI) provides the users of a database with a consistent view of the database and the ability to detect write-write conficts between transactions. When a client starts a transaction, it is given a "snapshot view" of the database. A value read from a cell within this snapshot will always be the same, unless the transaction itself updates the cell.
To successfully commit a transaction within snapshot isolation, the system must ensure that no other transaction has written to any of the transaction's written cells (that is, its writeset) since the start of the transaction.
That is, transactions with SI guarantees should read from their own data snapshot, being a data snapshot:
- Immutable
- Identified by creation time
- Containing values committed before creation time
In Omid, transactions conflict iff:
- Overlap in time, and...
- ... write to the same cell of a particular row
The following figure describes SI with an example:
As depicted in the figure, transaction T2 overlaps in time with T1 and T3, but spatially:
- T1 ∩ T2 = ∅
- T2 ∩ T3 = { R4 }
So, transactions T1 and T2, despite overlaping in time, they do not overlap in the elements they modify, so they do not conflict. However, transactions T2 and T3 have a conflict because they overlap both in space (both modify R4) and time. Finally, Transaction T4 does not has conflicts with other transactions.
Compared to other isolation levels, SI offers good-enough consistency guarantees -although some anomalies may appear on data, e.g. write-skew- and performance, mainly due to the fact transactions are not aborted due to read-write conflicts. We took this into consideration and we decided to implement SI as the default isolation level for Omid.
The main architectural components are represented in the figure below and described briefly below in the following paragraphs.
The main functionality provided by each component depicted in the figure above is:
- Timestamp Oracle (TO) assigns new timestamps to transactions upon starting/committing
- The Status Oracle (TSO) resolves conflicts between transactions
- Commit Table (CT) stores a temporary mapping from the start timestamp to the commit timestamp of every committed transaction
- Transactional Client Allows the applications to demarcate transactional boundaries and read/write transactionally from/to the data source (e.g. HBase)
- Shadow Cells (SC) allow clients to resolve reads without consulting the commit table
Omid benefits from a centralized scheme in which a single server, called The Status Oracle (TSO), monitors the modified rows/cells by transactions and use that to detect write-write conflicts.
User applications are allowed to begin, commit or abort transactions by means of Transactional Clients (TC), which enable remote communication to the TSO and allow to perform transactional operations on the data stored in the datasource.
When a transaction is created, a unique start timestamp is assigned by the Timestamp Oracle (TO). This start timestamp serves as a transaction identifier and is used by the TSO to guarantee SI by detecting conflicts in the writesset of a committing transaction with other concurrent transactions. Upon, finishing conflict detection successfully, the TSO assigns the transaction a commit timestamp and writes the mapping start/commit timestamp in the Commit Table (CT) before returning the response to the client. When receiving the response. the transactional client, adds a Shadow Cell (SC) per cell in the transaction writeset in order to allow to resolve the right snapshot for further read operations without disturbing the TSO.
For a more in-deep description of how Omid works and the internal of components please refer to the Technical Documentation section.
- Omid is lock-free. In lock-based approaches, the locks on data that are held by the incomplete transactions of a failed client prevent others from progressing. In Omid, if a client is slow or faulty, it does not slow down the other clients.
- Omid does not require any modification into HBase code. All the transactional logic is implemented in the TSO and the Transactional Clients (TCs.)
- Omid does not require any change into HBase table schema. Omid uses the HBase metadata -the cell timestamp in particular- to store the transaction timestamp of each value inserted, updated or deleted in a cell. This enables concurrent transactions to read data from the right snapshot.
- It is being used internally at Yahoo in a production system exhibiting good performance and reliability.
Do you want to try Omid? Please go to the Getting Started section.