Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which typically involve data partition (also called sharding) and data replication.
What are the major research issues in distributed transactions?
Are there well-known theories and solutions which need (theoretical) improvement?
Any references are appreciated.
There are many research areas both in the theory and practice of distributed databases.
One of the main practical challenges is that of implementing efficient concurrency control mechanisms for distributed and geo-replicated databases. In order to execute transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which requires that transactions appear to be executed sequentially. An alternative to serialisability is that of settling for Snapshot Isolation [1], but this has been proved to scale poorly to geo-replicated and distributed systems. At the current state of the art, two different variants of Snapshot Isolation (SI) have been defined to deal with concurrency control in geo-replicated systems: Parallel Snapshot Isolation (PSI) [2], and Non Monotonic Snapshot Isolation (NMSI) [3,4]. As for what it concerns distributed databases (i.e. where data are sharded among different sites), a variant of snapshot isolation for distributed system has been proposed very recently [5].
Having different notions of isolation levels which provide weaker guarantees than serialisability, another important question is that of writing programs in a way so that executions still appear to be serialisable. A sound criterion for Snapshot Isolation has been devised in [1]. Some people in my group are currently working on devising a reasonable criterion for PSI.
Another relevant question, both from a theoretical and practical point of view, is that of transaction chopping. Basically chopping is a static analysis techniques in which coarse-grained transactions are broken down into smaller, fine grained transactions. For serialisability, this question has been tackled in [6], and the resulting theory has been applied to give a practical implementation in [7].
From the point of view of theoretical foundations of distributed databases, there has been some proposal to use techniques from the weak memory models community [8] to define formally the behaviour of transactions. In [9] the authors give a formal notion of behaviour for transactions; the same approach have been used in [10] to specify the behaviour of replicated data types.
Recently, I and some colleagues of mine (Alexey Gotsman and Hongseok Yang) built, starting from the techniques developed in [8,9,10], a theoretical framework for specifying the observable behaviour of consistency levels for geo-replicated databases. We successfully employed the framework to give an axiomatisation of SI, PSI and NMSI, each of which we have proved to be correct with respect to a simple implementation. We also exploited the resulting theory to devise a chopping criterion for PSI. These results will hopefully we published in the foreseeable future.
Please do not hesitate to write me if you have other questions. Hope this helps,
Andrea Cerone.
References:
[1] Fekete et al, Making Snapshot Isolation Serializable (2005)
[2] Sovran et al, Transactional Storage for Geo-replicated Systems (2011)
[3] Arkedani et al, Non-Monotonic Snapshot Isolation: scalable and strong consistency for geo-replicated transactional systems (2013)
[4] Arkedani et al, On the Scalability of Snapshot Isolation (2013)
[5] Binnig et al, Distributed snapshot isolation: global transactions pay globally, local transactions pay locally
[6] Shasha et al, Transaction chopping: algorithms and performance studies (1995)
[7] Zhang et al, Transaction chains: achieving serializability with low latency in geo-distributed storage systems (2013)
[8] Alglave, A formal hierarchy of weak memory models (2012)
[9] Buckhardt et al, Understanding Eventual Consistency (2013)
[10] Buckhardt et al, Replicated Data Types: Specification, Verification, Optimality (2014)
