Please enable JavaScript.
Coggle requires JavaScript to display documents.
Principles of Database Buffer Management (Interface and Operations of a DB…
Principles of Database Buffer Management
Interface and Operations of a DB Buffer Manager
The buffer manager is considered a component within the DBMS with well-defined interfaces to other components
Logical References
For each
logical reference
the buffer manager performs the following...
The requested page is fixed in the buffer by marking its buffer control block
The fact that the page has been referenced is recorded
(since reference history important for replacement algorithms)
If page not in buffer, use a buffer allocation strategy to determine the set of candidate pages. A page replacement algorithm decides which of the buffer pages to replace. If page marked for replacement has been modified, it needs ot be written to disk.
The address of the buffer frame containing the requested page is passed to the calling DBMS componenet as a return parameter
Search the buffer and locate the page
Logical Page Reference String
Description:
The sequence of logical references to database pages recorded as a sequence of page numbers. It describes the reference behavior of the DBMS, independent of the buffer size and replacement algorithm of the buffer manager.
Logical reference behavior determined by...
The types of transactions constituting the DBMS load
(retrieval/update, direct/sequential access)
The transaction mix
(number and type of parallel transactions)
The access path structures provided by the DBMS and its undeerlying data model, in the form selected in the internal database schema.
Note every logical reference leads to a physical reference, but every physical reference is preceded by a logical reference.
Description:
Each request for a page. A logical reference can be issued by a single transaction. In that case it is independent of buffer size. Global logical references, characterizing the concurrent execution of multiple transactions are indirectly influenced by the size of the buffer.
Physical References
Description:
Accesses to DB pages on disk. Those accesses are some of the most expensive operations within a DBMS
In contrast to
logical references, physical references
are strongly influenced by the size of the database buffer and the page replacement algorithm of the buffer manager.
Since physical references are expensive, the optimization of the page replacement algorithm is very important for the overall performance of the DBMS.
Searching the Buffer
A search is done whenever a logical reference to a DB page occurs
Search Methods
Direct Search
Not good when running under a virtual memory operating system. In that case a table search technique will reduce page fault rate.
Checks the page headers of all pages in the buffer sequentially. In a buffer of size
N
, on average
N/2
pages will be searched in case of success and
N
in case of a fault.
Translation Table
Uses the page number as a displacement within the table. Hence the table must provide
D
entries for a database containing
D
pages. Restricted only to very small databases.
Unsorted Table
Requires
N/2
accesses on the average for a page found in the buffer.
Sorted Table
Sorted Table
Number of accesses for an unsuccessful sequential search is reduced from
N
to
N/2
.
Involves a much higher overhead when a table entry is inserted or deleted
Possibility to reduce search to
log2N
accesses via balanced binary tree or by maintaining an inde to the sorted table
Requires
N/2
accesses on the average for a page found in the buffer.
Chained Table
Update is less costly than on a compact table, since no entries have to be moved
The chaining sequence can be used to represent additional information, like replacement information for an LRU algorithm
Hash Table
The hash algorithm transforms a page number into a displacement within the page table, where the entry describing the page and its current position in the buffer can be found.
With an appropriately sized hash table, the number
n
of entries searched per
logical reference
can be
1 < n < 1.2
Buffer Allocation for Concurrent Transactions
The buffer allocation algorithm of the buffer management component distributes the available buffer frames among the concurrent database transactions. It is closely related to the page replacement algorithm.
Basic Properties of Database Reference Strings
Those properties clearly distinguish them from page reference strings of programs
Sometimes the reference behavior of DB transactions is predictable. Specific pages have a higher reference probability and can be treated in a special way when referenced.
Since database pages are a centralized resource shared among users, the concurrent use of a page in the buffer by several transactions is frequent
The parallel execution of many transactions can increase the referencing probability across transaction boundaries
Locality of the Reference Behavior
Locality of the Reference Behavior
Locality
means higher than average reference probability for recently referenced pages
If
locality
is observed in a reference string, most virtual memory allocation and replacement algorithms can be applied to buffer management
Detailed information on
locality
is contained in an
LRU stack depth distribution
of the reference string with higher bias towards low stack depths meaning higher locality.
System pages have a much higher probability of reference than user pages
The most important properpty of a reference string in terms of storage allocation and page replacement algorithms.
Classification of Buffer Allocation Algorithms
Buffer allocation algorithms can be subdivided into...
Local Algorithms
An algorithm that allocates buffer frames to a specific transaction without regarding the reference behavior of concurrent transactions.
Need mechanism for handling the allocation of buffer frames for shared pages, due to frequent concurrent access to the same DB page
...
Can be subdivided into...
Dynamic Allocation
Assigns variable-size partitions to the transactions. A partition can grow and shrink according to current transaction reference behavior.
When a buffer fault occurs, the allocation algorithm calculates the optimal partition size for the transaction.
Static Allocation
Constant number of transaction buffer frames for the lifespan of the transaction.
Not good when
the DBMS load changes frequently e.g. in an interactive environment. Not considered applicable in database buffer management
Global Algorithms
Consider not only the reference pattern of the currently executing transaction, but also the reference bahavior of all other transactions.
Page-Type Oriented
A division of the buffer is made into parts containing a single type of page only. Partition sizes can be static or dynamic.
Dynamic Buffer Allocation Using Local Algorithms
Dynamic Buffer Allocation Using Local Algorithms
Denning's Working-Set Algorithm
Description
Description
τ
:= window size. Has to be determined carefully so that only a minimum number of pages needed for an efficient execution are contained. Optionally different
τ
for different types of transactions.
w(t,τ)=|W(t,τ)|
is the working set size at time
t
. Shrinks in phases of high locality. Freed buffer frames willl be available for reallocation to other transactions.
w_dash(τ)
- average working set size of a transaction. Can be used as a measure of locality. Higher locality => lower working set size.
W(t,τ)
:= working set of a transaction - the set of pages referenced by the transaction during the last
τ
references at time
t
.
Best known dynamic storage allocation algorithm. Can be used to describe locality in the reference behavior of programs or database transactions.
Notes
The algorithm only decides whether a certain page in the buffer is eligible for replacement. A page replacement algorithm is therefore needed to select a page for replacement by buffer faults.
Implementing the algorithm means that whenever a page fault occurs, the working set of all active transactions must be determined
Determining Working Set of Active Transactions
Determining Working Set of Active Transactions
Every page
i
in the buffer has, for every transaction using it, a field
l
ast
r
eference
c
ount
LRC(T,i)
When transaction
T
references page
i
,
TRC(T)
is incremented and copied into
LRC(T,i)
.
A buffer page
i
is available for replacement iff
TRC(T) - LRC(T,i) >= τ
for all transactions
T
using it.
Can be done with a
t
ransaction
r
eference
c
ounter
TRC(T)
, which counts all logical references of a transaction.
Page-Fault Frequency Algorithm
Description
Uses the current interval between the last two page faults for the allocation decision. The algorithm is designed to guarantee a maximum fault rate of
F
for all transactions.
If the actual page fault rate
FA
of a transaction is...
...lower than
F
, the transaction keeps its working set in the buffer.
...higher than
F
, a new buffer frame is allocated to the transaction, independent of its current working set.
Replacement Algorithms for the Database Buffer
If a logical reference to the buffer fails, a page in the buffer must be selected for replacement to make room for the requested page.
The algorithms described here can be combined with buffer allocation algorithms
Replacement needed in connection with...
global allocation
- within the entire buffer
static allocation
- within the respective partition
dynamic allocation
- in the set of eligible pages i.e. pages currently not contained in the working set of any transaction/page type
Fetching Pages
Replacement algorithms can be classified into...
Prepaging Algorithms
Fetch not only the requested page, but also
m
additional pages that are physically close to the requested page, thus saving access time.
Can substantially reduce I/O costs when sequential page references are expected. However rarely applicable.
Demand Paging Algorithms
Fetch only the requested page when there is a page fault. High importance for practical applications.
Systematic Description of Replacement Algorithms
Description
Description
Applicable algorithms replace the buffer page having the lowest probability of reference. They rely on the characteristics of the past reference string to predict future reference bahavior.
The age and the references of a buffer page can be applied as suitable criteria to predict future reference behavior. Age is measured by using logical references as units of time.
Classification Methods
Exclusive use of only one of those criteria can not guarantee an optimal replacement decision when there is locality of reference
all references or only the most recent reference to the page
age since the first reference to the page or since the last reference to the page
Algorithms Overview
Algorithms Overview
FIFO
The age of a page since the first reference is the only decision criterion for page replacement. Hence the algorithm is only appropriate for sequential access behavior.
LFU
(least frequently used)
LFU
(least frequently used)
2 more items...
LRU
The replacement decision is made based on which page is referenced and by the age of each buffer page since its most recent reference.
FIX Mechanism
2 more items...
CLOCK
(also called Second Change)
Attempts to simulate LRU behavior by means of a simpler implementation. It is a modification of the FIFO mechanism.
Use Bit
1 more item...
Workflow
2 more items...
GCLOCK
GCLOCK
5 more items...
LRD
(least reference density)
LRD(V1)
1 more item...
LRD(V2)
1 more item...