``BP-Wrapper: a system framework making any replacement algorithms
(almost) lock contention free"

Xiaoning Ding, Song Jiang, and Xiaodong Zhang

Proceedings of 25th International Conference on Data Engineering,
(ICDE'09), Shanghai, China, March 29- April 4, 2009.


Abstract

In a high-end database system, the execution concurrency level rises
continuously in a multiprocessor environment due to the increase in
number of concurrent transactions and the introduction of multi-core
processors. A new challenge for buffer management to address is to
retain its scalability in responding to the highly concurrent data
processing demands and environment. The page replacement algorithm, a
major component in the buffer management, can seriously degrade the
system's performance if the algorithm is not implemented in a scalable
way. A lock-protected data structure is used in most replacement
algorithms, where high contention is caused by concurrent accesses. A
common practice is to modify a replacement algorithm to reduce the
contention, such as to approximate the LRU replacement with the clock
algorithm.  Unfortunately, this type of modification usually hurts hit
ratios of original algorithms. This problem may not exist or can be
tolerated in an environment of low concurrency, thus has not been given
enough attention for a long time.

In this paper, instead of making a trade-off between the high hit ratio
of a replacement algorithm and the low lock contention of its
approximation, we propose a system framework, called BP-Wrapper, that
(almost) eliminates lock contention for any replacement algorithm
without requiring any changes to the algorithm. In BP-Wrapper, we use
batching and prefetching techniques to reduce lock contention and to
retain high hit ratio. The implementation of BP-Wrapper in PostgreSQL
version 8.2 adds only about 300 lines of C code. It can increase the
throughput up to two folds compared with the replacement algorithms
with lock contention when running TPC-C-like and TPC-W-like workloads.