This paper has presented a new scheme for guaranteeing that transactions in a client/server system view consistent state while they are running. The scheme is presented in conjunction with an optimistic concurrency control algorithm, but could also be used to prevent read-only transactions from conflicting with read/write transactions in a multi-version system .
The scheme is lazy about providing consistency. It simply gathers information as transactions commit, and propagates information to clients in fetch replies. Clients use information only when necessary - to ensure that the current transaction observes a consistent view.
The scheme is based on multipart timestamps. Today the utility of multistamps is limited because their size is proportional to system size and therefore they don't scale to very large systems. Our scheme solves this problem by using real times in multistamps. Using time allows us to keep multistamps small by truncating them without loss of information and with minimal impact on performance: we remove older information that is likely to already be known while retaining recent information. We assume clocks are loosely synchronized; loss of synchronization affects only performance and not correctness.
The paper shows that our approach has extremely low costs.
Cost takes the form of stalls - times when a client
transaction must be delayed because
some dependency information is needed to ensure consistency.
Our experiments show that small multistamps are sufficient to make
stalls rare in all workloads
and extremely rare in realistic low-contention workloads.
Furthermore, low stall rates translate into extremely low
impact on the cost to run transactions.