On Optimistic Methods for Concurrency Control

paper here:

http://www.google.com/url?sa=t&source=web&cd=1&ved=0CCMQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.114.3052%26rep%3Drep1%26type%3Dpdf&rct=j&q=On%20optmistic%20method%20for%20concurrency%20control&ei=EPB5Tp6rFYWJsQLW28joAw&usg=AFQjCNGrkzBJkj-S35zwDWNlA5iYM--eWg&sig2=vLC4D24pmZlETmYNr0q4Kw

Summary:

In this paper the authors analyzed the drawbacks of doing concurrency control using traditional lock techniques: you have to pay the locking overhead even when you don't really need it. They then proposed optimistic concurrency control: let transactions proceed as if there's no conflict, and back-up them if a conflict is detected.

The main idea behind this optimistic approach is to divide the transactions into three phases: read, validation and write. In read phase, transactions only read database values and all updates take place in local copy; we also remember what we read and update in this transaction. In validation phase, we use some algorithm to detect whether there is a conflict during the read phase. If there is no conflict, we proceed to write phase and apply the updates to the global database; otherwise we just back-up and do necessary clean-up.

The authors discussed in detail how to validate a transaction. They laid out three conditions for transactions to meet serial equivalence (mainly about the read/write set of each transaction should not intersect with each other), and discussed how to assign each transaction a serial number to facilitate validation. Two families of validations algorithm are then proposed: one require serial write phase of all transactions; and the other allow concurrent write phases.

The author also discussed what kind of workload is suitable for optimistic concurrency control: query-dominate workload and other workload which conflict happen in a low probability. An example is given and analyzed (in paper) to show that optimistic concurrency control is promising in maintaining B-tree index. However, no experimental results are shown.

Comments:

1. This whole optimistic CC thing has a copy-on-write semantics. So note that it could break the original physical layout and extra caution should be taken.

2. The paper didn't quantify at all the overhead of the optimistic approach: maintaining sets, intersection, making local copies (memory copy is expensive!). The authors intentionally did that but you should let them manipulating you....

3. Optimistic Control has not yet been implemented in any commercial system as far as I know, but some techniques developed in this paper, like assigning transaction numbers, are very influential.