Transactions in Page-Server Systems - Transaction Processing - page 333

Obviously, a locally created LSN can no longer be the physical address (byte
offset) of the log record in the server's log file. Thus, the LSN s created at the clients
are purely logical sequence numbers that need explicitly be included in the log
records. What is actually needed to enforce write-ahead logging correctly is that,
for each page, the LSN s of updates on that page form an increasing sequence that
obeys the actual order of the updates performed by different clients.
With our caching protocol, a page can be cached for updating at a single client
at a time. To obtain a globally increasing sequence of LSN s, it thus suffices that the
LSN value stamped in the P AGE -LSN field of a page cached for updating is always
greater than the previous value in the field and, of course, greater than the previous
LSN generated locally at that client. For that purpose, the log manager at each client
c maintains a counter
L OCAL -M AX -LSN .c/
that gives the LSN of the last log record written at c. An update action or a structure
modification that modifies pages p 1 ;:::;p k is logged with an LSN n 0 determined as
follows:
n 0 D 1 C max f P AGE -LSN .p 1 /;:::; P AGE -LSN .p k /; L OCAL -M AX -LSN .c/ g .
The new LSN value n 0 is stamped into the P AGE -LSN field of each page p i , i D
1;:::;k, and is assigned as the new value of the counter L OCAL -M AX -LSN .c/.
In this way we ensure that (1) for each page, the LSN s of log records for updates
on that page form a globally increasing sequence and (2) for each client the, LSN s
created by that client form a locally increasing sequence. As each transaction
executes entirely at a single client, observation (2) means that also the sequence
of LSN s for updates by each transaction forms a sequence that is increasing by time
across all transactions at that client.
With purely logical LSN s the traversal of the U NDO -N EXT -LSN chain in transaction
rollback is less efficient than with physical LSN s. For accelerating the traversal, and
also for other purposes (explained below), the server maintains, for each client c,a
small LSN -to-address mapping consisting of pairs .n; a/,wheren is an LSN created
at client c and a is the log-file address (byte offset) of the log record with LSN n
in the log file at the server. New tuples .n; a/ are inserted into the mapping when
a client ships log records to the server, where they are appended to the server's log
file. Not all LSN s are mapped; the location of a given log record can be approximated
with the addresses associated with nearest LSN s that are explicitly mapped.
Instead of the R EC -LSN values in the modified-page table of a transaction-server
system, the server modified-page table maintained at the server of a page-server
system stores values R EC -A DDR , which are physical addresses to the log file.
Accordingly, for a page p buffered at the server, the value R EC -A DDR .p/ in the server
modified-page table indicates that all the updates on page p logged at addresses less
than R EC -A DDR .p/ are in the disk version of page p.In ARIES recovery, the R EC -
A DDR values are used instead of the R EC -LSN values.
Each client c maintains a local client modified-page table that records each
modified page p cached at c and a value R EC -LSN .p/. Recall that a page cached