PowerPoint Presentation
Buffer Management
R & G – Chapter 9.4
1
Architecture of a DBMS: What we’ve learned
Database Management
System
Database
Query Parsing
& Optimization
Relational Operators
Files and Index Management
Buffer Management
Disk Space Management
SQL Client
Completed
Completed
Completed
You are here!
2
Lower Architecture of a DBMS
Database Management
System
Database
Files and Index Management
Buffer Management
Disk Space Management
3
Disk
Files and Index Management
Buffer Management
Disk Space Management
RAM
Buffer Management Levels of Abstraction
4
Buffer Management, cont
RAM
Disk
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Buffer Manager
Page 3
Page 1
Page 4
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Buffer Manager
5
Buffer Management Read
The illusion of addressing and modifying disk pages in memory.
RAM
Disk
Disk Space Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Frame
Frame
Frame
Frame
Page 3
Frame
Frame
Page 1
Page 4
Buffer Manager
6
APIs
Write
Page
Read
Page
Write
Page
Read
Page
Disk
Disk Space Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
RAM
Frame
Frame
Frame
Frame
Page 3
Frame
Frame
Page 1
Page 4
Buffer Manager
7
Mapping Pages Into Memory, Pt 1
RAM
Disk
Frame
Frame
Frame
Frame
Frame
Frame
Buffer Manager
Page 3
Page 1
Page 4
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 1
Disk Space Manager
API Request
Message:
Request: Read page 1
API Request
Buffer Manager
8
Mapping Pages Into Memory, Pt 2
RAM
Disk
Frame
Frame
Frame
Frame
Frame
Frame
Buffer Manager
Page 3
Page 1
Page 4
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 1
Disk Space Manager
Page 2
Page 2
API Request
Message:
Request: Read page 2
API Request
Buffer Manager
9
Mapping Pages Into Memory, Pt 3
RAM
Disk
Frame
Frame
Frame
Frame
Frame
Frame
Buffer Manager
Page 3
Page 1
Page 4
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 1
Page 2
Disk Space Manager
Frame
API Request
Message:
Request: Read page 2
Frame
Buffer Manager
10
Mapping Pages Into Memory, Pt 4
RAM
Disk
Frame
Frame
Frame
Frame
Frame
Frame
Buffer Manager
Page 1
Page 2
Page 3
Page 3
Disk Space Manager
Frame
API Request
Message:
Request: Read page 3
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
API Request
Buffer Manager
11
Mapping Pages Into Memory
Frame
Frame
Frame
Frame
Frame
Frame
Buffer Manager
Page 1
Page 2
Page 3
Disk
Disk Space Manager
Frame
API Request
Message:
Request: Read page 3
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
API Request
Buffer Manager
12
Questions We Need to Answer
Handling dirty pages
Page Replacement
Q1: Dirty Pages?
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Buffer Manager
Page 2
Page 3
Page 1
Page 4
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 3
14
Handling Dirty Pages
Handling dirty pages
How will the buffer manager find out?
Dirty bit on page
What to do with a dirty page?
Write back via disk manager
Advanced Questions
Concurrent operations on a page
Solved by Concurrency Control module
System Crash before write-back
Solved by Recovery module
Database Management
System
Database
Query Parsing
& Optimization
Relational Operators
Files and Index Management
Buffer Management
Disk Space Management
SQL Client
Concurrency Control
Recovery
16
BufMgr State
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Buffer Manager
Page 2
Page 6
Page 4
Page 5
17
BufMgr State: Explicit
Buffer pool: Large range of memory, malloc’ed at DBMS server boot time (MBs-GBs)
Frame
Frame
Frame
Frame
Frame
Frame
FrameId PageId Dirty? Pin Count
1
2
3
4
5
6
18
BufMgr State: Explicit Pt 2
Buffer pool: Large range of memory, malloc’ed at DBMS server boot time (MBs-GBs)
Buffer Manager metadata: Smallish array in memory, malloc’ed at DBMS server boot time
Keep an in-memory index (hash table) on PageId
Frame
Frame
Frame
Frame
Frame
Frame
FrameId PageId Dirty? Pin Count
1 1 N 0
2 2 Y 1
3 3 N 0
4 6 N 2
5 4 N 0
6 5 N 0
19
BufMgr State: Illustrated
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 4
Page 6
Page 5
FrameId PageId Dirty? Pin Count
1 1 N 0
2 2 Y 1
3 3 N 0
4 6 N 2
5 4 N 0
6 5 N 0
20
BufMgr State: Illustrated 2
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
Page 4
21
Page Replacement Terminology Review
How will the buffer mgr know if a page is “in use”?
Page pin count
If buffer manager is full, what page should be replaced?
Page replacement policy
When a Page is Requested …
If requested page is not in pool:
Choose an un-pinned (pin_count = 0) frame for replacement.
If frame “dirty”, write current page to disk, mark “clean”
Read requested page into frame
Pin the page and return its address
If requests can be predicted (e.g., sequential scans) pages can be pre-fetched
several pages at a time!
Q2: Page Replacement
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Buffer Manager
Page 1
Page 3
Page 4
Page 5
Page 6
Page 7
Page 4
Page 5
Page 6
Page 2
Page 2
Page 7
*pointer
Page 7
API Request
Message:
Request: Read page 7
API Request
24
After Requestor Finishes
Requestor of page must:
set dirty bit if page was modified
unpin the page (preferably soon!)
Why does requestor unpin?
What happens if they don’t do it soon?
Page in pool may be requested many times
a pin count is used.
To pin a page: pin_count++
A page is a candidate for replacement iff
pin_count == 0 (“unpinned”)
CC & recovery may do additional I/Os upon replacement
Write Ahead Log protocol; more later!
Answers to Our Previous Questions
Handling dirty pages
How will the buffer manager find out?
Dirty bit on page
What to do with a dirty page?
Write back via disk manager
Page Replacement
How will the buffer mgr know if a page is “in use”?
Page pin count
If buffer manager is full, which page should be replaced?
Page replacement policy
Page Replacement Policy Intro
Page is chosen for replacement by a replacement policy:
Least-recently-used (LRU), Clock
Most-recently-used (MRU)
Policy can have big impact on #I/Os
Depends on the access pattern.
LRU Replacement Policy
Least Recently Used (LRU)
Pinned Frame: not available to replace
Track time each frame last unpinned (end of use)
Replace the frame which was least recently used
FrameId PageId Dirty? Pin Count Last Used
1 1 N 0 43
2 2 Y 1 21
3 3 N 0 22
4 6 N 2 11
5 4 N 0 24
6 5 N 0 15
LRU Replacement Policy, Pt 2
Very common policy: intuitive and simple
Good for repeated accesses to popular pages (temporal locality)
Can be costly. Why?
Need to “find min” on the last used attribute (priority heap data structure)
Approximate LRU: CLOCK policy
FrameId PageId Dirty? Pin Count Last Used
1 1 N 0 43
2 2 Y 1 21
3 3 N 0 22
4 6 N 2 11
5 4 N 0 24
6 5 N 0 15
BufMgr State: Illustrated
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
Page 4
30
Clock Policy State: Illustrated
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
Page 4
clock hand
next page
to consider
reference bits
recently referenced
pages
31
Clock Policy State: Explicit
FrameId PageId Dirty? Pin Count Ref Bit
1 1 N 1 1
2 2 N 1 1
3 3 N 0 1
4 4 N 0 0
5 5 N 0 0
6 6 N 0 1
Clock Hand
1
32
Clock Policy State: Illustrated Part 1
Request: Read page 7
Current frame has pin-count > 0:
Skip
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
Page 4
✔
✔
✔
✔
Page 7
Page 7
Page 7
33
Clock Policy State: Illustrated, Part 2
Request: Read page 7
Current frame not pinned,
Ref bit set:
Clear ref bit
Skip
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
Page 4
✔
✔
✔
✔
Page 7
Page 7
34
Clock Policy State: Illustrated, Pt 3
Request: Read page 7
Current frame not pinned
Ref bit unset:
Replace
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
Page 4
✔
✔
✔
Page 7
Page 7
Page 7
35
Clock Policy State: Illustrated, Pt 4
Request: Read page 7
Current frame not pinned
Ref bit unset:
Replace
Set pinned
Set ref bit
Advance clock
Page 4
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
✔
✔
✔
✔
Page 7
Page 7
Page 7
36
Clock Policy State: Illustrated, Pt 5
Request: Read page 7
Current frame not pinned
Ref bit unset:
Replace
Set pinned
Set ref bit
Advance clock
Return pointer
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 3
Page 2
Page 6
Page 5
✔
✔
✔
✔
Page 7
*pointer
Page 7
Page 7
37
Clock Policy Pseudocode
38
Clock Policy Pseudocode, Pt 2
Clock Policy Pseudocode, Pt 3
Is LRU/Clock Always Best?
Very common policy: intuitive and simple
Works well for repeated accesses to popular pages
Temporal locality
LRU can be costly Clock policy is cheap
Quite similar
If you like, try to find cases where they differ.
When might they perform poorly
What about repeated scans of big files?
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Repeated Scan (LRU)
Cache Hits: 0
Attempts: 0
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
42
Repeated Scan (LRU): Read Page 1
Cache Hits: 0
Attempts: 1
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
43
Repeated Scan (LRU): Read Page 2
Cache Hits: 0
Attempts: 2
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
44
Repeated Scan (LRU): Read Page 3
Cache Hits: 0
Attempts 3:
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
45
Repeated Scan (LRU): Read Page 4
Cache Hits 0:
Attempts: 4
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 6
Page 7
Page 5
46
Repeated Scan (LRU): Read Page 5
Cache Hits: 0
Attempts: 5
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 6
Page 7
Page 5
Page 5
47
Repeated Scan (LRU): Read Page 6
Cache Hits: 0
Attempts 6
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
So far, unavoidable cache misses.
Now the fun begins.
48
Repeated Scan (LRU): Read Page 7
Cache Hits: 0
Attempts: 7
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Disk Space Manager
49
Repeated Scan (LRU): Reset to beginning
Cache Hits: 0
Attempts: 7
Buffer Manager
Buffer Manager
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Disk Space Manager
Page 1
Page 1
50
Repeated Scan (LRU): Read Page 1 (again)
Cache Hits: 0
Attempts: 8
Buffer Manager
Buffer Manager
Buffer Manager
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Disk Space Manager
Page 3
Page 4
Page 6
Page 7
Page 5
Page 1
Page 1
Page 2
51
Repeated Scan (LRU): Read Page 2 (again)
Cache Hits: 0
Attempts: 9
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 4
Page 5
Page 6
Page 7
Page 5
Disk Space Manager
Page 3
Page 4
Page 6
Page 7
Page 5
Page 1
Page 2
Page 2
52
Repeated Scan (LRU): Read Page 3 (again)
Cache Hits: 0
Attempts: 10
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 2
Page 5
Page 6
Page 7
Page 5
Disk Space Manager
Page 1
Page 3
Page 4
Page 6
Page 7
Page 5
53
Repeated Scan (LRU): Page 4 (again)
Cache Hits: 0
Attempts: 11
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 2
Page 5
Page 6
Page 7
Disk Space Manager
Page 1
Page 3
Page 4
Page 6
Page 7
Page 5
54
Repeated Scan (LRU): Read Page 5, cont
Cache Hits: 0
Attempts: 12
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Page 2
Page 5
Page 7
Page 4
Disk Space Manager
Page 1
Page 3
Page 6
Page 7
Page 5
Get the picture? A worst-case scenario!
“Sequential Flooding”
55
Sequential Scan + LRU
Sequential flooding
0% hit rate in cache!
Repeated sequential scan very common in database workloads
We will see it in nested-loops join
What could be better?
Repeated Scan (MRU)
Cache Hits: 0
Attempts: 6
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
So far, unavoidable cache misses.
Now the fun begins.
57
Repeated Scan (MRU): Read Page 7
Cache Hits: 0
Attempts: 7
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
58
Repeated Scan (MRU): Reset
Cache Hits: 0
Attempts: 7
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
59
Repeated Scan (MRU): Read Page 1 (again)
Cache Hits: 1
Attempts: 8
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
60
Repeated Scan (MRU): Read Page 2 (again)
Cache Hits: 2
Attempts: 9
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
61
Repeated Scan (MRU): Read Page 3 (again)
Cache Hits: 3
Attempts: 10
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
62
Repeated Scan (MRU): Read Page 4 (again)
Cache Hits: 4
Attempts: 11
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
63
Repeated Scan (MRU): Read Page 5 (again)
Cache Hits: 5
Attempts: 12
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Frame
Frame
Frame
Frame
Frame
Frame
Disk Space Manager
Page 1
Page 2
Page 3
Page 4
Page 5
Page 7
Page 5
Page 6
64
Repeated Scan (MRU): Read Page 6 (again)
Cache Hits: 5
Attempts: 13
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Disk Space Manager
Page 5
Page 6
65
Repeated Scan (MRU): Read Page 7 (again)
Cache Hits: 6
Attempts: 14
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
66
Repeated Scan (MRU): Reset (again)
Cache Hits: 6
Attempts: 14
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
67
Repeated Scan (MRU): Read Page 1 (again x2)
Cache Hits: 7
Attempts: 15
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
68
Repeated Scan (MRU): Read Page 2 (again x2)
Cache Hits: 8
Attempts: 16
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
69
Repeated Scan (MRU): Read Page 3 (again x2)
Cache Hits: 9
Attempts: 17
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
70
Repeated Scan (MRU): Read Page 4 (again x2)
Cache Hits: 10
Attempts: 18
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 4
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
71
Repeated Scan (MRU): Read Page 5 (again x2)
Cache Hits: 10
Attempts: 19
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Buffer Manager
Frame
Frame
Frame
Frame
Frame
Frame
Page 1
Page 2
Page 3
Page 7
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
Page 7
Page 5
Page 6
72
General Case: SeqScan + MRU
B buffers
N > B pages in file
First pass (N attempts): 0 hits
The next (B– 1) passes have B hits each
The next (N – B) passes have (B – 1) hits each
The next (B– 1) passes have B hits each
…
In limit: (B(B-1) +(B-1)(N-B)) / (N(N-1)) = (B-1)/(N – 1) hit rate
Improvement for sequential scan: prefetch
Prefetch: Ask disk space manager for a run of sequential pages
E.g. On request for Page 1, ask for Pages 2-5
Why does this help?
Amortize random I/O overhead
Allow computation while I/O continues in background
Disk and CPU are “parallel devices”
We seem to need a hybrid!
LRU wins for random access (hot vs. cold)
When might we see that behavior?
MRU wins for repeated sequential
E.g. for certain joins
Two General Approaches
Use DBMS information to hint to BufMgr
For big queries: we can predict I/O patterns from the handful of query processing algorithms we’ll learn shortly
For simple lookups: LRU often does well
Find fancier stochastic policies
E.g. 2Q, LRU-2, ARC.
See Page Replacement Algorithm on Wikipedia but beware the OS-centric history
Hybrids are not uncommon in modern DBMSs
E.g. special-case for indexes, use LRU-2 otherwise
FWIW, PostgreSQL currently uses CLOCK
Imagine workloads for a big cloud DBMS like AWS Aurora!
DBMS vs OS Buffer Cache
Doesn’t the filesystem (OS) manage buffers and pages too?
Issues:
Portability: different FS, different behavior
OS limitations: DBMS requires ability to force pages to disk
Required for recovery, as we’ll see
OS limitations: DBMS can predict its own page reference patterns
E.g. consider scanning the leaves of a B+-tree
Affects both page replacement and prefetching
Summing Up
Buffer Manager provides a level of indirection
Maps disk page Ids to RAM addresses
Ensures that each requested page is “pinned” in RAM
To be (briefly) manipulated in-memory
And then unpinned by the caller!
Attempts to minimize “cache misses”
By replacing pages unlikely to be referenced
By prefetching pages likely to be referenced
Make Sure You Know
Pin Counts and Dirty Bits:
When do they get set/unset?
By what layer of the system?
LRU, MRU and Clock
Be able to run each by hand
For Clock:
What pages are eligible for replacement
When is reference bit set/unset
What is the point of the reference bit?
Sequential flooding
And how it behaves for LRU (Clock), MRU
/docProps/thumbnail.jpeg