This section provides an overview of our system and AOCC. More information can be found in [19][13][10][1].
Servers store the database objects in pages on disk; objects are typically smaller than pages. Clients maintain a page cache; they fetch missing pages from servers and use approximate LRU for cache management. Clients and servers rely on ordered communication, e.g., TCP.
Transactions run entirely at clients; clients communicate with servers only when there is a miss in the cache, and to commit transactions. The system serializes transactions using AOCC [13][1] and two-phase commit [11]. (Two-phase commit is avoided for transactions that use objects at only one server.)
AOCC works as follows: While a transaction T is running, client C keeps track of the objects it used and objects it modified. When T is ready to commit, C sends this information together with the new states of modified objects to a server at which some objects used by this transaction reside. This server acts as the coordinator for the commit; other servers where objects used by the transaction reside act as participants.
The participants validate T to ensure that it used only up-to-date versions of all objects and that it has not modified any objects used by other prepared or committed transactions, i.e., we use backward validation [14]. Validation uses a validation queue or VQ to track read/write sets of prepared and committed transactions; details can be found in [1].
Each participant sends its validation results to the coordinator who commits the transaction iff all participants voted positively. The coordinator sends its decision to client C and the participants. The delay observed by the client is due to phase 1 only; phase 2 happens in the background. In phase two, a participant installs T's updates (makes them available to other transactions).
When updates of a transaction run by client C1 modify objects in the cache of client C2, this causes C2's cache to contain out-of-date information. Furthermore, if C2 then runs a transaction that observes this out-of-date information, that transaction will be forced to abort. To avoid such aborts and keep client caches relatively up to date, servers send invalidation messages. The server maintains a per-client _directory_ that lists pages cached at the client (the directory may list pages no longer at the client since the server has not yet been informed that they were dropped). The server uses the directories to determine what invalidations to generate; each invalidation identifies an object that may be out of date at a particular client.
An invalidation message to a client contains all invalidations for that client. When a client receives an invalidation message it discards invalid objects (but not the containing page) and aborts the current transaction if it used them. In addition to keeping caches almost up-to-date, which reduces the number of aborts, invalidation messages also cause transactions that must abort to abort sooner.
Invalidation messages are piggy-backed on other messages that the server sends to the client; the client acks these messages (acks are also piggybacked), which allows the server to discard pending invalidations for the client. However, invalidations are not allowed to remain pending indefinitely. Instead there is a _timeout period_ (half a second in our current implementation). If a server has pending invalidations for the client, and if some of these invalidations are ``old'', i.e., they were generated nearly a timeout period ago, the server sends invalidations to the client on its own account (piggybacked on ``I'm alive'' messages). Thus invalidations are highly likely to arrive within half a second of their generation.
Although our scheme keeps caches almost up to date, it does not
guarantee that they are up to date.
When transactions run they can observe old information, and in
fact if a transaction T modified objects at two different servers,
a transaction running at some other client might observe the new
state of one object and the old state of the other.
Thus, it is possible for a transaction in our system to observe
an inconsistent state. Our new algorithm prevents this situation from
happening.