10
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thanks for your comprehensive answer. For SI, are there distributed, lock-free protocols in replicated settings in the literature? Or is this attempt meaningless because SI does not scale well? For PSI, I have read a paper (Tim Kraska@Eurosys'13) which mentioned its implementation in future work. Is Generalized Paxos suitable for this? What are the possible pros/cons/challenges compared to the original one in Sovran et al [2]? Thanks again. $\endgroup$ – hengxin Dec 19 '14 at 5:21
  • 2
    $\begingroup$ Indeed SI does not scale well to geo-replicated systems. In [4] above, the authors prove that there are properties, such as Genuine Partial Replication, which cannot be attained by geo-replicated DBMSs running at the SI consistency level. In [5], the authors show examples of executions that behave according to SI locally (at single shards), but not globally , and propose a variant of SI, called DSI. For what it concerns MDCC, I am not aware of this paper, and I have to admit that I do not know the implementation details of generalised Paxos. But I will gladly have a look, and reply asap. $\endgroup$ – Andrea Cerone Dec 22 '14 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.