Processing at the Server

Servers have two responsibilities: they must compute multistamps, and they must send them to clients in fetch responses. A fetch response sends a page containing modifications of transactions; at that point we also send the merge of the multistamps of those transactions.

The server maintains the following data structures. The PSTAMP table maps pages to multistamps: the multistamp of a page is the merge of the multistamps of all transactions that modified that page. The ILIST maps clients to invalidation information. Each element of ILIST[C] is a timestamp _ts_ and a list of object ids, indicating that these objects were invalidated for C at time _ts_. The VQ records multistamps of committed transactions (along with information about reads and writes of prepared and committed transactions).

Commit Processing. In the prepare phase, if validation of transaction T succeeds, participant S computes multistamp _m_ as follows:

1. S initializes _m_ to be empty.

2. If the commit of T would cause invalidations for any other clients, S sets _ts_ to the current time of its clock. Then for each potentially invalidated client C:
   1. S adds tuple <_C, S, ts_> to _m_.

   2. S adds <_ts, olist_> to the ILIST for C, where _olist_ contains ids of all objects modified by T that are in pages listed in S's directory for C.

3. For each transaction U that T depends on, S merges VQ[U].mstamp with _m_. The dependencies are determined using S's VQ.

Then S sends _m_ in the vote message to the coordinator. If the coordinator decides to commit T, it merges multistamps received from participants to obtain T's multistamp. This multistamp is sent to participants in the commit messages. The participants store it in VQ[T].mstamp. Furthermore, for each page P modified by T, the participant merges this multistamp into PSTAMP[P].

If the coordinator decides to abort, it sends this information to the participants. The participant then removes information about T from the ILIST.

Fetch Processing. When a server receives a fetch message for object _x_ on page P, if there is a prepared transaction that modified _x_, it waits for it to complete. Then it sends the fetch reply, which contains P and also PSTAMP[P]. (Our base system never delays a fetch reply. However, the probability of a delay is very small since the prepare window is very small.)

Invalidations. To produce an invalidation message, the server goes through the ILIST in timestamp order from smallest to largest, stopping when it has processed the entire list, or it reaches an entry for a prepared (but not yet committed) transaction. The ids of all objects in the processed entries are sent in the message along with the largest timestamp contained in the processed entries.

As mentioned, invalidation messages are piggybacked on every message sent to a client and clients acknowledge invalidations. The acknowledgement contains the timestamp _ts_ of the associated invalidation message. The server then removes all entries whose timestamps are less than or equal to _ts_ from the ILIST.

A client may also request invalidation information. Such a request contains a timestamp _ts_. The server responds by sending back an invalidation message as above except that the timestamp in the message must be greater than or equal to _ts_. It is possible that some entry in the table with a timestamp less than or equal to _ts_ exists for a transaction that has not yet committed (it is still prepared); in this case, the server delays the response until the outcome for that transaction is known. Such delays are unlikely because the coordinator sends the phase-two message to participants promptly.