10
$\begingroup$

A simplified classical database transaction can be viewed as:

  • reading M items
  • performing some calculation based on those reads
  • writing some N results based on these calculations, which may include the elements originally read.

When performing these transactions (concurrently) the ACID properties need to be maintained.

Exactly the same requirements (N updates based on M reads transactionally) exist in other non-DBMS concurrent systems.

I'm interested in finding out what algorithms exist for performing/resolving these transactions, and what the relative strengths and weaknesses of these algorithms are. Could you recommend some reading? This could be books or online references/tutorials.

Clarification:

So for example, a naive algorithm might be each transaction taking a single global lock, in effect forcing single threading and removing concurrency. A slightly more complicated algorithm would be individual item read/write locks, with an ordering to avoid deadlock). Etc, etc. Is there a good source documenting various algorithms for solving this problem. Even an answer which only pointed to a single algorithm with it's strength and weaknesses would be useful.

$\endgroup$
  • 3
    $\begingroup$ This question certainly falls within the scope of this site. I would recommend writing a little more about the context in which you are working. At present it is rather general and open. $\endgroup$ – Dave Clarke Oct 31 '10 at 9:06
  • $\begingroup$ Do you think it is worth rephrasing so it is precisely the database question? IE something like "I have a database which can be read and written to, and I want to be able to read and write transactionally with ACID properties. What algorithms exist for ensuring these properties" $\endgroup$ – Nick Fortescue Oct 31 '10 at 9:19
  • $\begingroup$ Rephrasing the question may result in answers closer to what you are looking for, such as giving more details of the problem you are trying to solve; at present you only give hints. In any case, it sounds like you are asking for classical database transaction algorithms. $\endgroup$ – Dave Clarke Oct 31 '10 at 9:51
  • $\begingroup$ @Dave - thanks, I've edited. Better? $\endgroup$ – Nick Fortescue Oct 31 '10 at 10:00
  • 1
    $\begingroup$ Are you already familiar with DBMS textbooks such as the one by Ramakrishnan and Gehrke? And if you are not asking about the internals of a DBMS, can you clarify the question to let us know the difference between a DBMS and what you are interested in? $\endgroup$ – Maverick Woo Oct 31 '10 at 10:09
10
$\begingroup$

The book Transactional Information Systems by Weikum and Vossen covers quite a lot of the area, both in theoretical and practical terms, from different perspectives, not just transactions. It's about 1000 pages long, so will keep you busy for a weekend or two. On the other hand, it's nearly 10 years old, so there might be something more up-to-date available. Other books in the line include Concurrency Control and Recovery in Database Systems by Bernstein, P., Hadzilacos, V., and Goodman, N, Addison-Wesley, 1987, Transaction Processing: Concepts and Techniques by Jim Gray and Andreas Reuter, and Principles of Transaction Processing by Philip A. Bernstein and Eric Newcomer, 2009. I haven't seen the latter one, but being the most recent it could be a good place to start, although your solution may well be found in older texts. A trip to the library may be worthwhile.

A monumental text in this area is Atomic Transactions by Nancy Lynch et al. It presents a formal account and proofs of a number of the kinds of algorithms you are interested in. It's rather formal, and tedious, so may not be to your taste.

A lot of recent work is devoted to Software Transactional Memory, which is applying the transaction ideas to multi-threaded applications. There are tens of publications on this topic each year: the wikipedia page provides plenty of references.

$\endgroup$
  • 1
    $\begingroup$ thanks dave, especially for the phrase "Software transactional memory", I hadn't come across this name $\endgroup$ – Nick Fortescue Oct 31 '10 at 10:33
  • 1
    $\begingroup$ STM is a really hot topic in programming languages research these days. There's a race on to see whether STM or Actor-based programming models will be the basis of future concurrent (= all) programming languages. $\endgroup$ – Dave Clarke Oct 31 '10 at 10:47
  • 1
    $\begingroup$ Besides STM, one particular keyword to look for inside these references is MVCC. It's used in most modern DBMSs: en.wikipedia.org/wiki/Multiversion_concurrency_control $\endgroup$ – Maverick Woo Oct 31 '10 at 12:28
  • $\begingroup$ @supercooldave I'm not sure it's a race: I think future languages will have to support a bit of both to some degree or another. $\endgroup$ – Marc Hamann Oct 31 '10 at 15:18
  • $\begingroup$ @Marc Harmann: metaphorically speaking. $\endgroup$ – Dave Clarke Oct 31 '10 at 15:36

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.