Hyder is a transactional indexed-record manager for shared flash. That is, it supports operations on indexed records and transaction operations that bracket the record operations. It is designed to run on a cluster of servers that have shared access to a large pool of network-addressable storage, which stores the indexed records as a multiversion log-structured database. Hyder's main feature is that it scales out without partitioning the database or application.
In Hyder, the database is stored as a multiversion (i.e., copy-on-write) binary search tree. Each node is a key-value pair. Each update to a node in the tree creates a new node, which in turn requires that new copies be created of all of its ancestors. When a transaction begins, it is given the latest copy of the database root, which defines a static snapshot. The transaction’s updates are stored in a transaction-local cache. When the transaction is ready to commit, its updates are gathered into a record and appended to the store.
Unlike conventional database systems, appending a transaction T’s update record to the log does not necessarily commit T. Instead, when a server receives T’s log record L, it determines whether T actually committed. T’s log record contains a reference R to the last committed transaction in the log that contributed to the snapshot that T read. The server scans the log to determine if any committed transactions in between R and L included a conflicting operation. This is determined by looking at the writeset and optionally the readset (depending on the desired isolation level), which are summarized in each log record. If there are no conflicts, then T committed. Otherwise, it aborted. In effect, this is optimistic concurrency control. Since all servers are scanning the same log, they all make the same decision regarding T. If the server that executed T determines that T aborted, then it re-executes T.
- Philip A. Bernstein, Sudipto Das, Bailu Ding, and Markus Pilman, Optimizing Optimistic Concurrency Control for Tree-Structured, Log-Structured Databases, in International Conference on Management of Data (SIGMOD), ACM – Association for Computing Machinery, 31 May 2015.
- Philip A. Bernstein and Sudipto Das, Scaling Optimistic Concurrency Control by Approximately Partitioning the Certifier and Log, in IEEE Data Engineering Bulletin, vol. 38, no. 1, IEEE – Institute of Electrical and Electronics Engineers, March 2015.
- Philip A. Bernstein, Colin W. Reid, and Sudipto Das, Hyder - A Transactional Record Manager for Shared Flash, in CIDR , January 2011. Best Paper Award
- Philip A. Bernstein, Colin W. Reid, Ming Wu, and Xinhao Yuan, Optimistic Concurrency Control by Melding Trees, in PVLDB, vol. 4, no. 11, pp. 944-955, 2011.
- Mahesh Balakrishnan, Phil Bernstein, Dahlia Malkhi, Vijayan Prabhakaran, and Colin Reid, Brief Announcement: Flash-Log -- A High Throughput Log, in 24th International Symposium on Distributed Computing (DISC 2010), Springer Verlag, September 2010.
- Colin W. Reid and Philip A. Bernstein, Implementing an Append-Only Interface for Semiconductor Storage, in IEEE Data Eng. Bull., vol. 33, no. 4, pp. 14-20, 2010.