Processing of Write-Intensive Transactions - Transaction Processing - page 361

are conventional disk-based B-trees. There is a single log to which all updates
on all the relations are logged, either logically or physiologically, depending on
the organization of the relation. Any transaction can operate on any number of the
relations. Modifications on the disk-based index structures are logged, while those
on the main-memory structures are not. Explain how ARIES -based recovery works
in this setting: what needs to be done in the analysis, redo, and undo passes and what
needs to be checkpointed?
15.8 Assume that a flash-memory-based SSD applies a block-level FTL mapping.
What actions are involved in garbage collection? Give a worst-case scenario in
which garbage collection involves much reading and writing.
Bibliographical Notes
DeWitt et al. [ 1984 ] observe that a transaction can release its commit-duration locks
before the commit log record is forced onto disk, as long as it does not return results
to the application and declare as having committed until the commit log record has
reached the log disk. The issue of early lock release is formalized with the notion of
partial strictness by Soisalon-Soininen and Ylönen [ 1995 ].
Johnson et al. [ 2010 , 2012 ] identify four logging-related impediments to database
system scalability: (a) the high volume of small-sized write requests may saturate
the disk, (b) transactions hold locks while waiting for the log flush, (c) excessive
process-context switching overwhelms the operating-system scheduler with threads
executing log writes, and (d) contention appears as transactions serialize accesses to
main-memory log data structures.
The write-optimized B-tree is from Graefe [ 2004 ], who suggests maintaining the
parent links only between buffer control blocks of buffered pages rather than linking
the pages themselves (as we do in Sect. 15.3 ). Graefe [ 2004 ] also suggests enforcing
a stricter buffering policy for modified pages, so that a modified child page must
always be relocated and flushed before the parent page.
The idea of turning costly random disk writes to append-only ones to be merged
later as larger bulks into the main file dates back to differential files [Severance and
Lohman, 1976 ] and log-structured file systems [Rosenblum and Ousterhout, 1992 ].
The log-structured merge tree or LSM tree is from O'Neil et al. [ 1996 ]. Jermaine
et al. [ 2007 ] introduce a structure called the partitioned exponential file that consists
of a set of merge trees each covering a subrange of the entire key space. Sears et al.
[ 2008 ] describe a database storage engine that uses LSM trees to create full database
replicas. The b LSM tree of Sears and Ramakrishnan [ 2012 ]isan LSM tree with
near-optimal read and scan performance and with an improved merge scheduler.
The b LSM tree is used in Walnut, a cloud object store [Chen et al. 2012 ].
The buffer tree of Arge [ 1995 , 2003 ] is another index structure that incorporates
the idea of collecting updates into larger bulks before posting them to their final
destinations. The buffer tree has a buffer attached to each node of the B-tree; updates