-
Notifications
You must be signed in to change notification settings - Fork 1
/
2024-08-13-db-notes:-memory-management.html
338 lines (338 loc) · 15.3 KB
/
2024-08-13-db-notes:-memory-management.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="description" content="This is a personal note for the [[https://15445.courses.cs.cmu.edu/fall2023/notes/06-bufferpool.pdf][CMU 15-445 L6 notes]]">
<link rel="alternate"
type="application/rss+xml"
href="https://chenyo.me/rss.xml"
title="RSS feed for https://chenyo.me">
<title>CMU 15-445 notes: Memory Management</title>
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'],['\\(','\\)']]}});
</script>
<meta name="author" content="chenyo">
<meta name="referrer" content="no-referrer">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="assets/style.css" type="text/css"/>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css"/>
<link rel="favicon" type="image/x-icon" href="favicon.ico">
<script src="assets/search.js"></script></head>
<body>
<div id="preamble" class="status">
<header>
<h1><a href="https://chenyo.me">Chenyo's org-static-blog</a></h1>
<nav>
<a href="https://chenyo.me">Home</a>
<a href="archive.html">Archive</a>
<a href="tags.html">Tags</a>
<div id="search-container">
<input type="text" id="search-input" placeholder="Search anywhere...">
<i class="fas fa-search search-icon"></i>
</div>
</nav>
</header></div>
<div id="content">
<div class="post-date">13 Aug 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-08-13-db-notes:-memory-management.html">CMU 15-445 notes: Memory Management</a></h1>
<nav id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#orgd3b9de6">1. Goals</a></li>
<li><a href="#orgad508e8">2. Locks & Latches</a>
<ul>
<li><a href="#org464dfd5">2.1. Locks</a></li>
<li><a href="#orgbeaaeba">2.2. Latches</a></li>
</ul>
</li>
<li><a href="#orgbfc13b1">3. Buffer pool</a>
<ul>
<li><a href="#org07b8c91">3.1. Metadata</a></li>
<li><a href="#orga86ef04">3.2. Memory allocation policies</a></li>
</ul>
</li>
<li><a href="#org3b2e4fb">4. Buffer pool optimizations</a>
<ul>
<li><a href="#org940fc2d">4.1. Multiple buffer pools</a></li>
<li><a href="#org4ba7c06">4.2. Pre-fetching</a></li>
<li><a href="#org6614885">4.3. Scan sharing</a></li>
<li><a href="#org11ab22d">4.4. Buffer pool bypass</a></li>
</ul>
</li>
<li><a href="#orgd1fe8bc">5. Buffer replacement policies</a>
<ul>
<li><a href="#org30f3413">5.1. Least recently used (LRU)</a></li>
<li><a href="#org935ef33">5.2. Clock</a></li>
<li><a href="#orge84f1b2">5.3. LRU-K</a>
<ul>
<li><a href="#org6629d4b">5.3.1. MySQL approximate LRU-K</a></li>
</ul>
</li>
<li><a href="#org9eaa09f">5.4. Localization</a></li>
<li><a href="#orge03c3de">5.5. Priority hint</a></li>
<li><a href="#orgdeef10a">5.6. Dirty pages</a></li>
</ul>
</li>
<li><a href="#org66d1c8d">6. Other memory pools</a></li>
<li><a href="#org2a1d436">7. OS cache bypass</a></li>
<li><a href="#org2812e58">8. I/O scheduling</a></li>
</ul>
</div>
</nav>
<p>
This is a personal note for the <a href="https://15445.courses.cs.cmu.edu/fall2023/notes/06-bufferpool.pdf">CMU 15-445 L6 notes</a> as well as some explanation from Claude.ai.
</p>
<div id="outline-container-orgd3b9de6" class="outline-2">
<h2 id="orgd3b9de6"><span class="section-number-2">1.</span> Goals</h2>
<div class="outline-text-2" id="text-1">
<ul class="org-ul">
<li>Manage DBMS memory and move data between the memory and the disk, such that the execution engine does no worry about the data fetching.</li>
<li>Spatial control: keep relevant pages physically together on disk.</li>
<li>Temporal control: minimize the number of stalls to read data from the disk.</li>
</ul>
</div>
</div>
<div id="outline-container-orgad508e8" class="outline-2">
<h2 id="orgad508e8"><span class="section-number-2">2.</span> Locks & Latches</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Both used to protect internal elements.</li>
</ul>
</div>
<div id="outline-container-org464dfd5" class="outline-3">
<h3 id="org464dfd5"><span class="section-number-3">2.1.</span> Locks</h3>
<div class="outline-text-3" id="text-2-1">
<ul class="org-ul">
<li>A high-level logical primitive to allow for transaction atomicity.</li>
<li>Exposed to users when queries are run.</li>
<li>Need to be able to rollback changes.</li>
</ul>
</div>
</div>
<div id="outline-container-orgbeaaeba" class="outline-3">
<h3 id="orgbeaaeba"><span class="section-number-3">2.2.</span> Latches</h3>
<div class="outline-text-3" id="text-2-2">
<ul class="org-ul">
<li>A low-level protection primitive a DBMS uses in its internal data structures, e.g., hash tables.</li>
<li>Only held when the operation is being made, like a mutex.</li>
<li>Do not need to expose to users or used to rollback changes.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-orgbfc13b1" class="outline-2">
<h2 id="orgbfc13b1"><span class="section-number-2">3.</span> Buffer pool</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li>An in-memory cache of pages read from the disk.</li>
<li>The buffer pool’s region of memory is organized as an array of fixed size pages; each array entry is called a frame.</li>
<li>When the DBMS requests a page, the buffer pool first searches its cache, if not found, it copies he page from the disk into one of its frame.</li>
<li>Dirty pages (i.e., modified pages) are buffered rather than writing back immediately.</li>
</ul>
</div>
<div id="outline-container-org07b8c91" class="outline-3">
<h3 id="org07b8c91"><span class="section-number-3">3.1.</span> Metadata</h3>
<div class="outline-text-3" id="text-3-1">
<ul class="org-ul">
<li>Page table: An in-memory hash mapping page ids to frame locations in the buffer pool.</li>
<li>Dirty flag: set by a thread whenever it modifies a page to indicate the pages must be written back to disk.</li>
<li>Pin/Reference counter: tracks the number of threads that are currently accessing the page; the storage manager is not allowed to evict a page if its pin count is greater than 0.</li>
</ul>
</div>
</div>
<div id="outline-container-orga86ef04" class="outline-3">
<h3 id="orga86ef04"><span class="section-number-3">3.2.</span> Memory allocation policies</h3>
<div class="outline-text-3" id="text-3-2">
<ul class="org-ul">
<li>The buffer pool decides when to allocate a frame for a page.</li>
<li>Global policies: decisions based on the overall workload, e.g., least recently used (LRU) or clock algorithm.</li>
<li>Local policies: decisions applying to specific query, e.g., priority-based page replacement.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org3b2e4fb" class="outline-2">
<h2 id="org3b2e4fb"><span class="section-number-2">4.</span> Buffer pool optimizations</h2>
<div class="outline-text-2" id="text-4">
</div>
<div id="outline-container-org940fc2d" class="outline-3">
<h3 id="org940fc2d"><span class="section-number-3">4.1.</span> Multiple buffer pools</h3>
<div class="outline-text-3" id="text-4-1">
<ul class="org-ul">
<li>Each database or page can have its own buffer pool and adopts local policies to reduce latch contention.</li>
<li>To map a page to a buffer pool, the DBMS can use object IDs or page IDs as the key.
<ul class="org-ul">
<li>Record ID: a unique identifier for a row in a table (cf. <a href="https://chenyo-17.github.io/org-static-blog/tag-database.html#org2317270">Tuple layout post</a>).</li>
<li>Object ID: a unique identifier for an object, used to reference a user-defined type.</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-org4ba7c06" class="outline-3">
<h3 id="org4ba7c06"><span class="section-number-3">4.2.</span> Pre-fetching</h3>
<div class="outline-text-3" id="text-4-2">
<ul class="org-ul">
<li>While the first set of pages is being processed, the DBMS can pre-fetch the second set into the buffer pool based on the dependency between pages.
<ul class="org-ul">
<li>E.g., If pages are index-organized, the sibling pages can be pre-fetched.</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-org6614885" class="outline-3">
<h3 id="org6614885"><span class="section-number-3">4.3.</span> Scan sharing</h3>
<div class="outline-text-3" id="text-4-3">
<ul class="org-ul">
<li>Query cursors can reuse retrieved data.</li>
<li>When a query comes while a previous query is being processed by scanning the table, the new query can attach its scanning cursor to the first query’s cursor.</li>
<li>The DBMS keeps track of where the second query joined to make sure it also completes the scan.</li>
</ul>
</div>
</div>
<div id="outline-container-org11ab22d" class="outline-3">
<h3 id="org11ab22d"><span class="section-number-3">4.4.</span> Buffer pool bypass</h3>
<div class="outline-text-3" id="text-4-4">
<ul class="org-ul">
<li>Scanned pages do not have to be stored in the buffer pool to avoid the overhead.</li>
<li>Use cases: a query needs to read a large sequence of contiguous pages; temporary pages like sorting or joins.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-orgd1fe8bc" class="outline-2">
<h2 id="orgd1fe8bc"><span class="section-number-2">5.</span> Buffer replacement policies</h2>
<div class="outline-text-2" id="text-5">
<ul class="org-ul">
<li>The DBMS decides which page to evict from the buffer pool to free up a frame.</li>
</ul>
</div>
<div id="outline-container-org30f3413" class="outline-3">
<h3 id="org30f3413"><span class="section-number-3">5.1.</span> Least recently used (LRU)</h3>
<div class="outline-text-3" id="text-5-1">
<ul class="org-ul">
<li>LRU maintains a timestamp of when each page was last accessed, and evicts the page with the oldest timestamp.
<ul class="org-ul">
<li>The timestamp can be stored in a queue for efficient sorting.</li>
</ul></li>
<li>Susceptible to sequential flooding, where the buffer pool is corrupted due to a sequential scan.
<ul class="org-ul">
<li>With the LRU policy the oldest pages are evicted, but they are more likely to be scanned soon.</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-org935ef33" class="outline-3">
<h3 id="org935ef33"><span class="section-number-3">5.2.</span> Clock</h3>
<div class="outline-text-3" id="text-5-2">
<ul class="org-ul">
<li>An approximation of LRU but replace the timestamp with a reference bit which is set to 1 when a page is accessed.</li>
<li>Regularly sweeping all pages, if a bit is set to 1, reset to 0; if a bit is 0, evict the page.</li>
</ul>
</div>
</div>
<div id="outline-container-orge84f1b2" class="outline-3">
<h3 id="orge84f1b2"><span class="section-number-3">5.3.</span> LRU-K</h3>
<div class="outline-text-3" id="text-5-3">
<ul class="org-ul">
<li>Tracks the last K accessed timestamps to predict the next accessed time, hence avoid the sequential flooding issue.</li>
</ul>
</div>
<div id="outline-container-org6629d4b" class="outline-4">
<h4 id="org6629d4b"><span class="section-number-4">5.3.1.</span> MySQL approximate LRU-K</h4>
<div class="outline-text-4" id="text-5-3-1">
<ul class="org-ul">
<li>Use a linked list with two entry points: “old” and “young”.</li>
<li>The new pages are always inserted to the head of “old”.</li>
<li>If a page in the “old” is accessed again, it is then inserted to the head of “young”.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org9eaa09f" class="outline-3">
<h3 id="org9eaa09f"><span class="section-number-3">5.4.</span> Localization</h3>
<div class="outline-text-3" id="text-5-4">
<ul class="org-ul">
<li>Instead of using a global replacement policy, the DBMS make eviction decisions based on each query.</li>
<li>Pages brought in by one query are less likely to evict pages that are important for other ongoing queries.</li>
<li>The DBMS can <b><b>predicts</b></b> more accurately which pages should stay or be evicted once the query is complete, so that the buffer pool is less polluted with less useful pages.</li>
</ul>
</div>
</div>
<div id="outline-container-orge03c3de" class="outline-3">
<h3 id="orge03c3de"><span class="section-number-3">5.5.</span> Priority hint</h3>
<div class="outline-text-3" id="text-5-5">
<ul class="org-ul">
<li>Transactions tell the buffer pool where pages are important based on the <b><b>context</b></b> of each page.</li>
</ul>
</div>
</div>
<div id="outline-container-orgdeef10a" class="outline-3">
<h3 id="orgdeef10a"><span class="section-number-3">5.6.</span> Dirty pages</h3>
<div class="outline-text-3" id="text-5-6">
<ul class="org-ul">
<li>Two ways to handle dirty pages in the buffer pool:
<ul class="org-ul">
<li>Fast: only drop clean pages.</li>
<li>Slow: write back dirty pages to ensure persistent change, and then evict them (if they will not be read again.).</li>
</ul></li>
<li>Can periodically walk through the page table and write back dirty pages in the background.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org66d1c8d" class="outline-2">
<h2 id="org66d1c8d"><span class="section-number-2">6.</span> Other memory pools</h2>
<div class="outline-text-2" id="text-6">
<ul class="org-ul">
<li>A DBMS also maintains other pools to store:
<ul class="org-ul">
<li>query caches,</li>
<li>logs,</li>
<li>temporary tables, e.g., sorting, join,</li>
<li>dictionary caches.</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-org2a1d436" class="outline-2">
<h2 id="org2a1d436"><span class="section-number-2">7.</span> OS cache bypass</h2>
<div class="outline-text-2" id="text-7">
<ul class="org-ul">
<li>Most DBMS use direct I/O (e.g., with <code>fsync</code> instead of <code>fwrite</code>) to bypass the OS cache to avoid redundant page copy and to manage eviction policies more intelligently (cf. <a href="https://chenyo-17.github.io/org-static-blog/tag-database.html#org611ff38">Why not OS post</a>).</li>
</ul>
</div>
</div>
<div id="outline-container-org2812e58" class="outline-2">
<h2 id="org2812e58"><span class="section-number-2">8.</span> I/O scheduling</h2>
<div class="outline-text-2" id="text-8">
<ul class="org-ul">
<li>The DBMS maintains internal <b><b>queue</b></b> to track page read/write.</li>
<li>The priority are determined by multi-facets, e.g., critical path task, SLAs.</li>
</ul>
</div>
</div>
<div class="taglist"><a href="https://chenyo.me/tags.html">Tags</a>: <a href="https://chenyo.me/tag-study.html">study</a> <a href="https://chenyo.me/tag-database.html">database</a> <a href="https://chenyo.me/tag-cmu.html">cmu</a> </div></div>
<div id="postamble" class="status"><div id="search-results"></div>
<footer>
<div class="footer-content">
<div class="footer-left">
<p>© 2024 chenyo. Some rights reserved.</p>
<a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width: 0"
src="https://i.creativecommons.org/l/by-nc/4.0/88x31.png"/>
</a>
</div>
<div class="social-links">
<a href="https://t.me/feihuadawangjiushiwo" target="_blank" rel="noopener noreferrer">
<i class="fab fa-telegram"></i>
</a>
<a href="https://github.com/chenyo-17" target="_blank" rel="noopener noreferrer">
<i class="fab fa-github"></i>
</a>
</div>
</footer></div>
</body>
</html>