Research and Research-Linked projects for sem1 2015, supervised by Alan Fekete

Improved Models for Staleness in NoSQL Cloud Data Stores

In order to remain available despite partitions, many data storage layers for cloud platforms offer forms of eventual consistency between replicas. Examples include Apache Cassandra, AWS SimpleDB, and the storage of Google App Engine. Recent work by Bailis et al from UC Berkeley introduced a framework called PBS for predicting the probability of observing stale data in these platforms, based on measuring the distribution of inter-replica message latencies; the PBS framework is now available in Cassandra. PBS assumes that replicas are managed using a natural Dynamo-style algorithm of reading and writing from sets of replicas; however measurements reported by Wada et al from NICTA, of actual staleness probabilities in SimpleDB seem to show a different pattern from what PBS predicts.

This project will seek a better model for the probability of seeing stale data, that fits closely with what is actually observed. To begin, the project will collect measurements of staleness probabilities in SimpleDB, and see whether the behavior has changed since what was reported by Wada et al in 2011. We will also measure inter-node communication times, so that we can compare quantitatively between the predictions of PBS and the actual values of staleness probability. Further work could look at other platforms, including Cassandra. The main contribution of the project will be a new predictive model for staleness probability to match what is observed.

References: PBS site; Data Consistency Properties and the Trade-offs in Commercial Cloud Storage: the Consumers' Perspective.

This project is suitable for Research Track (18crpts), or Honours. A cut-down version would be available for research-linked projects (12 crpt, or for a TSP student). This project would be part of the activity of the Database research group of the School, and involve collaboration with NICTA's Software Systems Research Group at the ATP. This project requires good awareness of performance issues, some programming (Java and perhaps also C# and C), doing lots of careful data collection and plenty of data analysis.

Tradeoffs in snapshot-based concurrency control

In multiversion storage management, changes to a record produce a new version, rather than modifying the original storage location, and reads can use old versions rather than waiting for writes to commit. These techniques are used in several important database engines, including InnoDB, PostgreSQL, Microsoft SQLServer, and Oracle. In particular, PostgreSQL uses a multiversion concurrency control algorithm called SerializableSI which was invented by Michael Cahill for his PhD research at USyd. Another new algorithm was proposed by David Lomet of Microsoft Research, and implemented as a prototype in InnoDB by a USyd student (Peter Ward). Lomet's algorithm has a tunable parameter in the decision between blocking and aborting, and Ward only implemented the aborting case.

This project will study the tradeoff between blocking and aborting in Lomet's algorithm. To begin, the project will implement Lomet's algorithm in PostgreSQL, using the mechanisms already present for multiversions and lock management. Then microbenchmark experiments will be run, to compare how performance changes when blocking or aborting are used, based on features such as the amount of data read and written in each transaction, the amount of conflict between transactions, etc, as well as features of the hardware such as the bandwidth to the disk, and the speed of the CPU, and key features of the algorithms such as the amount of overhead in each operation due to checking concurrency control.

References: Serializable isolation for snapshot databases; Serializable Snapshot isolation in PostgreSQL; Multi-version Concurrency via Timestamp Range Conflict Management

This project is suitable for Research Track (18crpts), or Honours. A cut-down version would be suitable as research-linked (12crpts or TSP). This project would be part of the activity of the Database research group of the School. This project requires good awareness of performance issues, skill working with database tuning, some programming (C), lots of experiments and plenty of data analysis.

Measuring the anomalies in multi-item multi-operation access for NoSQL stores

Many NoSQL stores (and other research prototype storage platforms) do not provide traditional database transactions, but rather offer only individual operations or else they offer transactions only on items that belong to an item group (which will be collocated). For some workloads, this seems adequate, but in principle, application threads that perform a sequence of accesses to several items could interfere and cause data integrity to be violated. This project aims to empirically measure how much data corruption would occur in such platforms, as a function of the features of the workload. A framework for this sort of measurement is YCSB+T from Dey et al http://dx.doi.org/10.1109/ICDEW.2014.6818330 Previous related work has measured the anomalies in single-site databases running with low isolation http://www.vldb.org/pvldb/2/vldb09-185.pdf

This project is suitable for Research Track (18crpts), or Honours. A cut-down version would be suitable as research-linked (12crpts or TSP). This project would be part of the activity of the Database research group of the School. This project requires good awareness of performance issues, skill working with database tuning, some programming (Java), lots of experiments and plenty of data analysis.

A new serialization certification approach

Recent (not yet published) work by a group including Alan Fekete, has proposed a new way to certify or validate the serializability of execution, when a transaction wishes to commit. The essential idea of the new approach is to track the dependencies (read-write, write-read, and write-write conflicts) between transactions, and use these to propagate a few values associated with each transaction; a simple test at commit time checks a particular novel relationship between the values associated to the requesting transaction and those it depends on, or that depend on it; if that relationship does not hold, the requesting transaction is aborted. The project will implement this certification mechanism (and also the Read Committed isolation level) into the Shore-MT system which is a research prototype database written in C++ with lock-based concurrency control and it is targeted at scalability on multicore platforms see https://sites.google.com/site/shoremt/ Evaluation will compare the combination of Read Committed isolation and the certification, against the existing Serializable isolation currently offered by Shore-MT.

This project is suitable for Research Track (18crpts), or Honours. A cut-down version would be suitable as research-linked (12crpts or TSP). This project would be part of the activity of the Database research group of the School. This project requires good awareness of performance issues, skill working with database tuning, quite a bit of programming (C++), lots of experiments and plenty of data analysis.