Debian Codegraph @

www/walformat.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>WAL-mode File Format</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 WAL-mode File Format
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#files_on_disk">1. Files On Disk</a></div>
126 <div class="fancy-toc2"><a href="#the_main_database_file">1.1. The Main Database File</a></div>
127 <div class="fancy-toc2"><a href="#the_write_ahead_log_or_wal_file">1.2. The Write-Ahead-Log or "-wal" File</a></div>
128 <div class="fancy-toc2"><a href="#the_wal_index_or_shm_file">1.3. The Wal-Index or "-shm" file</a></div>
129 <div class="fancy-toc2"><a href="#file_lifecycles">1.4. File Lifecycles</a></div>
130 <div class="fancy-toc2"><a href="#variations">1.5. Variations</a></div>
131 <div class="fancy-toc1"><a href="#the_wal_index_file_format">2. The WAL-Index File Format</a></div>
132 <div class="fancy-toc2"><a href="#the_wal_index_header">2.1. The WAL-Index Header</a></div>
133 <div class="fancy-toc3"><a href="#the_mxframe_field">2.1.1. The mxFrame field</a></div>
134 <div class="fancy-toc3"><a href="#the_nbackfill_field">2.1.2. The nBackfill field</a></div>
135 <div class="fancy-toc3"><a href="#wal_locks">2.1.3. WAL Locks</a></div>
136 <div class="fancy-toc2"><a href="#wal_index_hash_tables">2.2. WAL-Index Hash Tables</a></div>
137 <div class="fancy-toc2"><a href="#locking_matrix">2.3. Locking Matrix</a></div>
138 <div class="fancy-toc3"><a href="#how_the_various_locks_are_used">2.3.1. How the various locks are used</a></div>
139 <div class="fancy-toc3"><a href="#operations_that_require_locks_and_which_locks_those_operations_use">2.3.2. Operations that require locks and which locks those operations use</a></div>
140 <div class="fancy-toc1"><a href="#recovery">3. Recovery</a></div>
141 </div>
142 </details>
143 </div>
144
145
146
147
148
149 <p>This document describes low-level details on how <a href="wal.html">WAL mode</a> is
150 implemented on unix and windows.
151
152 </p><p>The separate <a href="fileformat2.html">file format</a> description provides details on the
153 structure of a database file and of the write-head log file used in
154 <a href="wal.html">WAL mode</a>. But details of the locking protocol and of the format
155 of the WAL-index are deliberately omitted since those details
156 are left to discretion of individual <a href="vfs.html">VFS</a> implementations. This
157 document fills in those missing details for the unix and windows <a href="vfs.html">VFSes</a>.
158
159 </p><p>For completeness, some of the higher level formatting information
160 contains in the <a href="fileformat2.html">file format</a> document and elsewhere is replicated here,
161 when it pertains to WAL mode processing.
162
163 </p><h1 id="files_on_disk"><span>1. </span>Files On Disk</h1>
164
165 <p>When in active use, the state of a WAL mode database is described
166 by three separate files:
167
168 </p><ol>
169 <li> The main database file with an arbitrary name "X".
170 </li><li> The write-ahead log file, usually named "X-wal".
171 </li><li> The wal-index file, usually named "X-shm".
172 </li></ol>
173
174 <h2 id="the_main_database_file"><span>1.1. </span>The Main Database File</h2>
175
176 <p>The format of the main database file is as described in the
177 <a href="fileformat2.html">file format</a> document. The <a href="fileformat2.html#vnums">file format version numbers</a> at offsets
178 18 and 19 into the main database must both be 2 to indicate that the
179 database is in WAL mode. The main database may have an arbitrary
180 name allowed by the underlying filesystem. No special file suffixes
181 are required, though ".db", ".sqlite", and ".sqlite3" seem to be
182 popular choices.
183
184 </p><h2 id="the_write_ahead_log_or_wal_file"><span>1.2. </span>The Write-Ahead-Log or "-wal" File</h2>
185 <p>The write-ahead log or "wal" file is a roll-forward journal
186 that records transactions that have been committed but not yet applied
187 to the main database. Details on the format of the wal file are
188 described in the <a href="fileformat2.html#walformat">WAL format</a> subsection of the main <a href="fileformat2.html">file format</a>
189 document. The wal file is named by appending the four characters
190 "-wal" to the end of the name of the main database file. Except
191 on 8+3 filesystems, such names are not allowed, and in that case
192 the file suffix is changed to ".WAL". But as 8+3 filesystems are
193 increasingly rare, that exceptional case can usually be ignored.
194
195 <a name="shm"></a>
196
197 </p><h2 id="the_wal_index_or_shm_file"><span>1.3. </span>The Wal-Index or "-shm" file</h2>
198 <p>The wal-index file or "shm" file is not actually used as a file.
199 Rather, individual database clients mmap the shm file and use it
200 as shared memory for coordinating access to the database and as a cache
201 for quickly locating frames within the wal file. The name
202 of the shm file is the main database file name with the four characters
203 "-shm" appended. Or, for 8+3 filesystems, the shm file is the main
204 database file with the suffix changed to ".SHM".
205
206 </p><p>The shm file does not contain any database content and is not required
207 to recover the database following a crash. For that reason, the first
208 client to connect to a quiescent database will normally truncate the
209 shm file if it exists. Since the content of the shm file does not need
210 to be preserved across a crash, the shm file is never fsync()-ed to disk.
211 In fact, if there were a mechanism by which SQLite could tell the
212 operating system to never persist the shm file to disk but always hold
213 it in cache memory, SQLite would use that mechanism to avoid any
214 unnecessary disk I/O associated with the shm file. However, no such
215 mechanism exists in standard posix.
216
217 </p><p>Because the shm is only used to coordinate access between concurrent
218 clients, the shm file is omitted if <a href="pragma.html#pragma_locking_mode">exclusive locking mode</a>
219 is set, as an optimization. When <a href="pragma.html#pragma_locking_mode">exclusive locking mode</a> is set,
220 SQLite uses heap memory in place of the memory-mapped shm file.
221
222 </p><h2 id="file_lifecycles"><span>1.4. </span>File Lifecycles</h2>
223
224 <p>When a WAL mode database is in active use, all three of the above
225 files usually exist. Except, the Wal-Index file is omitted if
226 <a href="pragma.html#pragma_locking_mode">exclusive locking mode</a> is set.
227
228 </p><p>If the last client using the database shuts down cleanly by
229 calling <a href="c3ref/close.html">sqlite3_close()</a>, then a <a href="wal.html#ckpt">checkpoint</a> is run automatically
230 in order to transfer all information from the wal file
231 over into the main database, and both the shm file
232 and the wal file are unlinked. Thus, when the database is not in
233 use by any client, it is usually the case that only the main
234 database file exists on disk.
235 However, if the last client did not call <a href="c3ref/close.html">sqlite3_close()</a> before it
236 shut down, or if the last client to disconnect was a read-only client,
237 then the final cleanup operation does not occur and the
238 shm and wal files may still exist on disk even when the database is
239 not in use.
240
241 </p><h2 id="variations"><span>1.5. </span>Variations</h2>
242
243 <p>When <a href="pragma.html#pragma_locking_mode">PRAGMA locking_mode=EXCLUSIVE</a> (exclusive locking mode) is set,
244 only a single client is allowed to have the database open at one time. Since
245 only a single client can use the database, the shm file is omitted.
246 The single client uses a buffer in heap memory as a substitute for the
247 memory-mapped shm file.
248
249 </p><p>If a read/write client invokes
250 <a href="c3ref/file_control.html">sqlite3_file_control</a>(<a href="c3ref/c_fcntl_begin_atomic_write.html#sqlitefcntlpersistwal">SQLITE_FCNTL_PERSIST_WAL</a>) prior to shutdown,
251 then at shutdown a checkpoint is still run, but the shm file and wal
252 file are not deleted.
253 This allows subsequent read-only clients to connect to and read the
254 database.
255
256 <a name="walidxfmt"></a>
257
258 </p><h1 id="the_wal_index_file_format"><span>2. </span>The WAL-Index File Format</h1>
259
260 <p>
261 The WAL-index or "shm" file is used to coordinate access to the database
262 by multiple clients, and as a cache to help clients quickly locate frames
263 within the wal file.
264
265 </p><p>
266 Because the shm file is not involved in recovery, the shm file does not
267 need to be machine byte-order independent. Hence, numeric values in
268 the shm file are written in the native byte order of the host computer,
269 rather than being converted into a specific cross-platform byte order as
270 is done with the main database file and the wal file.
271
272 </p><p>
273 The shm file consists of one or more hash tables, where each hash table
274 is 32768 bytes in size. Except, a 136-byte header is carved out of the
275 front of the very first hash table, so the first hash table is only
276 32632 bytes in size. The total size of the shm file is always a multiple
277 of 32768. In most cases, the total size of the shm file is exactly 32768
278 bytes. The shm file only needs to grow beyond a single hash table if
279 when the wal file grows very large (more than 4079 frames). Since the
280 default <a href="c3ref/wal_autocheckpoint.html">automatic checkpoint threshold</a> is
281 1000, WAL files rarely reach the 4079 threshold needed to make the shm file
282 grow.
283
284 </p><h2 id="the_wal_index_header"><span>2.1. </span>The WAL-Index Header</h2>
285
286 <p>The first 136 bytes of the shm file are a header. The shm header has
287 three main divisions as follows:
288
289 </p><center>
290 <i>WAL-Index Header Divisions</i><br>
291 <table width="80%" border="1">
292 <tr><th>Bytes</th><th>Description
293 </th></tr><tr><td valign="top">0..47</td><td>First copy of the WAL Index Information</td>
294 </tr><tr><td valign="top">48..95</td><td>Second copy of the WAL Index Information</td>
295 </tr><tr><td valign="top">96..135</td><td>Checkpoint Information and Locks</td>
296 </tr></table>
297 </center>
298
299 <p>Individual fields of the shm header, except for the
300 salt values copied from the WAL header, are unsigned integers
301 in the native byte-order of the host machine. The salt values
302 are exact copies from the WAL header and are in whatever byte
303 order is used by the WAL file.
304 The size of integers may be 8, 16, 32, or 64 bits.
305 A detailed breakout of the individual fields of the shm header
306 follows:
307
308 </p><center>
309 <i>WAL-Index Header Details</i><br>
310 <table width="80%" border="1">
311 <tr><th>Bytes</th><th>Name</th><th>Meaning</th></tr>
312 <tr>
313 <td>0..3</td><td>iVersion</td>
314 <td>The WAL-index format version number. Always 3007000.</td>
315 </tr>
316 <tr>
317 <td>4..7</td><td>&nbsp;</td>
318 <td>Unused padding space. Must be zero.
319 </td></tr>
320 <tr>
321 <td>8..11</td><td>iChange</td>
322 <td>Unsigned integer counter, incremented with each transaction.
323 </td></tr>
324 <tr>
325 <td>12</td><td>isInit</td>
326 <td>The "isInit" flag. 1 when the shm file has been initialized.
327 </td></tr>
328 <tr>
329 <td>13</td><td>bigEndCksum</td>
330 <td>True if the WAL file uses big-endian checksums. 0 if the WAL
331 uses little-endian checksums.
332 </td></tr>
333 <tr>
334 <td>14..15</td><td>szPage</td>
335 <td>The database page size in bytes, or 1 if the page size is 65536.
336 </td></tr>
337 <tr>
338 <td>16..19</td><td>mxFrame</td>
339 <td>Number of valid and committed frames in the WAL file.
340 </td></tr>
341 <tr>
342 <td>20..23</td><td>nPage</td>
343 <td>Size of the database file in pages.
344 </td></tr>
345 <tr>
346 <td>24..31</td><td>aFrameCksum</td>
347 <td>Checksum of the last frame in the WAL file.
348 </td></tr>
349 <tr>
350 <td>32..39</td><td>aSalt</td>
351 <td>The two salt values copied from the WAL file header.
352 These values are in the byte-order of the WAL file, which
353 might be different from the native byte-order of the
354 machine.
355 </td></tr>
356 <tr>
357 <td>40..47</td><td>aCksum</td>
358 <td>A checksum over bytes 0 through 39 of this header.
359 </td></tr>
360 <tr>
361 <td>48..95</td><td>&nbsp;</td>
362 <td>A copy of bytes 0 through 47 of this header.
363 </td></tr>
364 <tr>
365 <td>96..99</td><td>nBackfill</td>
366 <td>Number of WAL frames that have already been backfilled into the database
367 by prior checkpoints.
368 </td></tr>
369 <tr>
370 <td>100..119</td><td>read-mark&#91;0..4&#93;
371 </td><td>Five "read marks". Each read mark is a 32-bit unsigned integer (4 bytes).
372 </td></tr>
373 <tr>
374 <td>120..127</td><td>&nbsp;</td>
375 <td>Unused space set aside for 8 file locks.
376 </td></tr>
377 <tr>
378 <td>128..132</td><td>nBackfillAttempted</td>
379 <td>Number of WAL frames that have attempted to be backfilled but which might
380 not have been backfilled successfully.
381 </td></tr>
382 <tr>
383 <td>132..136</td><td>&nbsp;</td>
384 <td>Unused space reserved for further expansion.
385 </td></tr>
386 </table>
387 </center>
388
389 <a name="mxframe"></a>
390
391 <h3 id="the_mxframe_field"><span>2.1.1. </span>The mxFrame field</h3>
392
393 <p>The 32-bit unsigned integer at offset 16 (and repeated at offset 64)
394 is the number of valid frames in the WAL. Because WAL frames are numbered
395 starting with 1, mxFrame is also the index of the last valid commit frame
396 in the WAL. A commit frame is a frame that has a non-zero "size of database"
397 value in bytes 4 through 7 of the frame header, and that indicates the end
398 of a transaction.
399 </p><p>
400 When mxFrame field is zero, it indicates that the WAL is empty and that
401 all content should be obtained directly from the database file.
402 </p><p>
403 When mxFrame is equal to <a href="walformat.html#nbackfill">nBackfill</a>, that indicates that all content
404 in the WAL has been written back into the database.
405 In that case, all content can be read directly from the database.
406 Furthermore, the next writer is free to <a href="fileformat2.html#walreset">reset the WAL</a> if no other
407 connections hold locks on WAL_READ_LOCK(N) for N>0.
408 </p><p>
409 The mxFrame value is always greater than or equal to both
410 <a href="walformat.html#nbackfill">nBackfill</a> and nBackfillAttempted.
411
412
413 <a name="nbackfill"></a>
414
415 </p><h3 id="the_nbackfill_field"><span>2.1.2. </span>The nBackfill field</h3>
416
417 <p>The 32-bit unsigned integer at offset 128 in the WAL-index header
418 is called the "nBackfill".
419 this field holds the number of frames in the WAL file which
420 have been copied back into the main database.
421
422 </p><p>The nBackfill number is never greater than <a href="walformat.html#mxframe">mxFrame</a>.
423 When nBackfill equals <a href="walformat.html#mxframe">mxFrame</a>, that means that the WAL content
424 has been completely written back into the database and it is
425 ok to <a href="fileformat2.html#walreset">reset the WAL</a> if there are no locks held on any of WAL_READ_LOCK(N)
426 for N>0.
427
428 </p><p>The nBackfill can only be increased while holding the
429 WAL_CKPT_LOCK. However, nBackfill is changed to zero
430 during a <a href="fileformat2.html#walreset">WAL reset</a>, and this happens while holding
431 the WAL_WRITE_LOCK.
432
433 <a name="locks"></a>
434
435 </p><h3 id="wal_locks"><span>2.1.3. </span>WAL Locks</h3>
436
437 <p>Eight bytes of space are set aside in the header to support
438 file locking using the xShmLock() method in the <a href="c3ref/io_methods.html">sqlite3_io_methods</a>
439 object. These eight bytes are never read nor written by SQLite since
440 some VFSes (ex: Windows) might implement locks using mandatory file locks.
441
442 </p><p>These are the eight locks supported:
443
444 </p><center>
445 <i>WAL-Index Locks Controlled By xShmLock()</i><br>
446 <table border="1">
447 <tr><th rowspan="2">Name</th><th colspan="2">Offset
448 </th></tr><tr><th>xShmLock</th><th>File
449 </th></tr><tr>
450 <td>WAL_WRITE_LOCK
451 </td><td>0
452 </td><td>120
453 </td></tr>
454
455 <tr>
456 <td>WAL_CKPT_LOCK
457 </td><td>1
458 </td><td>121
459 </td></tr>
460
461 <tr>
462 <td>WAL_RECOVER_LOCK
463 </td><td>2
464 </td><td>122
465 </td></tr>
466
467 <tr>
468 <td>WAL_READ_LOCK(0)
469 </td><td>3
470 </td><td>123
471 </td></tr>
472
473 <tr>
474 <td>WAL_READ_LOCK(1)
475 </td><td>4
476 </td><td>124
477 </td></tr>
478
479 <tr>
480 <td>WAL_READ_LOCK(2)
481 </td><td>5
482 </td><td>125
483 </td></tr>
484
485 <tr>
486 <td>WAL_READ_LOCK(3)
487 </td><td>6
488 </td><td>126
489 </td></tr>
490
491 <tr>
492 <td>WAL_READ_LOCK(4)
493 </td><td>7
494 </td><td>127
495 </td></tr>
496 </table>
497 </center>
498
499
500
501 <p><i>TBD: More information about the header</i>
502
503 </p><h2 id="wal_index_hash_tables"><span>2.2. </span>WAL-Index Hash Tables</h2>
504
505 <p>The hash tables in the shm file are designed to answer the
506 following question quickly:
507
508 </p><blockquote><i>
509 FindFrame(P,M):
510 Given a page number P and a maximum WAL frame index M,
511 return the largest WAL frame index for page P that does not exceed M,
512 or return NULL if there are no frames for page P that do not exceed M.
513 </i></blockquote>
514
515 <p>
516 Let the datatypes "u8", "u16", and "u32" mean unsigned integers of
517 length 8, 16, and 32 bits, respectively. Then, the first 32768-byte unit
518 of the shm file is organized as follows:
519
520 </p><blockquote><pre>
521 u8 aWalIndexHeader[136];
522 u32 aPgno[4062];
523 u16 aHash[8192];
524 </pre></blockquote>
525
526 <p>The second and all subsequent 32768-byte units of the shm file are
527 like this:
528
529 </p><blockquote><pre>
530 u32 aPgno[4096];
531 u16 aHash[8192];
532 </pre></blockquote>
533
534 <p>Collectively, the aPgno entries record the database page number stored
535 in all frames of the WAL file. The aPgno[0] entry on the first hash table
536 records the database page number stored in the very first frame in the WAL
537 file. The aPgno[i] entry from the first hash table is the database page number
538 for the i-th frame in the WAL file. The aPgno[k] entry for the second
539 hash table is the database page number for the (k+4062)-th frame in the
540 WAL file. The aPgno[k] entry for the n-th 32768-byte hash table in the
541 shm file (for n>1) holds the database page number stored in the
542 (k+4062+4096*(n-2))-th frame of the WAL file.
543
544 </p><p>Here is a slightly different way to describe the aPgno values:
545 If you think of all aPgno values as a contiguous array, then
546 the database page number stored in the i-th frame of the WAL file
547 is stored in aPgno[i]. Of course, aPgno is not a contiguous array.
548 The first 4062 entries are on the first 32768-byte unit of the shm
549 file and subsequent values are in 4096 entry chunks in later units
550 of the shm file.
551
552 </p><p>One way to compute FindFrame(P,M) would be to scan the aPgno
553 array starting with the M-th entry and working backwards towards
554 the beginning and return J where aPgno[J]==P. Such an algorithm would
555 work, and it would be faster than searching the whole WAL file for
556 the latest frame with page number P. But the search can be made
557 much faster still by using the aHash structure.
558
559 </p><p>A database page number P is mapped into a hash value
560 using the following hash function:
561
562 </p><blockquote>
563 h = (P * 383)%8192
564 </blockquote>
565
566 <p>This function maps every page number into an integer between 0
567 and 8191 inclusive. The aHash field of each 32768-byte shm file unit
568 maps P values into indexes of the aPgno field of the same unit as
569 follows:
570
571 </p><ol>
572 <li> Compute the hash value: h = P * 383
573 </li><li> Let X be the largest set of consecutive integers {h, h+1, h+2, ..., h+N}
574 such that for every j in X, aPgno&#91;j%8192]!=0. The X set will be empty
575 if aPgno&#91;h%8192]==0. The X set is easily computed by starting with
576 the value h%8192, and adding h%8192 to X and incrementing h until
577 encountering the first aPgno&#91;h%8192] entry that is zero.
578 </li><li> The set X contains the index in aPgno of every entry in the current
579 32768-byte unit of the shm file that might possibly be a solution
580 to the FindFrame(P,M) function. Each of these entries must be
581 checked separately to ensure that the aPgno value is P and that the
582 frame number does not exceed M. The largest frame number that passes
583 those two tests is the answer.
584 </li></ol>
585
586 <p>Each entry in the aPgno array has a single corresponding entry
587 in the aHash array. There are more available slots in aHash than
588 there are in aPgno. The unused slots in aHash are filled with zero.
589 And since there are guaranteed to be unused slots in aHash, that means
590 the loop that computes X is guaranteed to terminate. The expected size
591 of X is less than 2. The worst case is that X will be the same as the
592 number of entries in aPgno, in which case the algorithm runs at about
593 the same speed as a linear scan of aPgno. But that worst case performance
594 is exceedingly rare. Usually, the size of X will be small and the use
595 of the aHash array allows one to compute FindFrame(P,M) much faster.
596
597 </p><p>Here is an alternative way of describing the hash look-up algorithm:
598 Start with h = (P * 383)%8192 and look at aHash[h] and subsequent entries,
599 wrapping around to zero when h reaches 8192, until finding an entry with
600 aHash[h]==0. All aPgno entries having a page number of P will have an
601 index that is one of the aHash[h] values thusly computed.
602 But not all the computed aHash[h] values will
603 meet the matching criteria, so you must check them independently. The
604 speed advantage comes about because normally this set of h values is
605 very small.
606
607 </p><p>Note that each 32768-byte unit of the shm file has its own aHash and
608 aPgno arrays. The aHash array for a single unit is only helpful in finding
609 aPgno entries in that same unit. The overall FindFrame(P,M) function
610 needs to do hash lookups beginning with the latest unit and working
611 backwards to the oldest unit until it finds an answer.
612
613 </p><h2 id="locking_matrix"><span>2.3. </span>Locking Matrix</h2>
614
615 <p>Access is coordinated in WAL mode using both the legacy DELETE-mode
616 locks controlled by the xLock and xUnlock methods of the <a href="c3ref/io_methods.html">sqlite3_io_methods</a>
617 object and the WAL locks controlled by the xShmLock method of the
618 <a href="c3ref/io_methods.html">sqlite3_io_methods</a> object.
619
620 </p><p>Conceptually, there is just a single DELETE-mode lock. The DELETE-mode
621 lock for a single database connection can be in exactly one of the
622 following states:
623 </p><ol>
624 <li value="0"> SQLITE_LOCK_NONE (unlocked)
625 </li><li value="1"> SQLITE_LOCK_SHARED (reading)
626 </li><li value="2"> SQLITE_LOCK_RESERVED (reading, waiting to write)
627 </li><li value="3"> SQLITE_LOCK_PENDING (new readers blocked, waiting to write)
628 </li><li value="4"> SQLITE_LOCK_EXCLUSIVE (writing)
629 </li></ol>
630 <p>The DELETE-mode locks are stored on the <a href="fileformat2.html#lockbyte">lock-byte page</a> of the
631 main database file.
632 Only SQLITE_LOCK_SHARED and SQLITE_LOCK_EXCLUSIVE are factors for WAL-mode
633 databases.
634 The other locking states are used in rollback-mode, but not in WAL-mode.
635
636 </p><p>The <a href="walformat.html#locks">WAL-mode locks</a> are described above.
637
638 </p><h3 id="how_the_various_locks_are_used"><span>2.3.1. </span>How the various locks are used</h3>
639
640 <p>The following rules show how each of the locks is used.
641
642 </p><ul>
643 <li><p><b>SQLITE_LOCK_SHARED</b>
644 </p><p>
645 All connections hold SQLITE_LOCK_SHARED continuously while attached
646 to a WAL-mode database. This is true for both read/write connections
647 and read-only connections.
648 The SQLITE_LOCK_SHARED lock is held even by connections that are
649 not within transaction.
650 This is different from rollback mode, where the SQLITE_LOCK_SHARED is
651 released at the end of each transaction.
652
653 </p></li><li><p><b>SQLITE_LOCK_EXCLUSIVE</b>
654 </p><p>
655 Connections hold an exclusive lock when changing between WAL mode
656 and any of the various rollback-modes. Connections might also attempt to
657 obtain an EXCLUSIVE lock when they disconnect from WAL mode. If
658 a connection is able to obtain an EXCLUSIVE lock, that means it is the
659 only connection to the database and so it may attempt to checkpoint
660 and then delete the WAL-index and WAL files.
661 </p><p>
662 When a connection is holding a SHARED lock on the main database,
663 that will prevent any other connection from acquiring the EXCLUSIVE
664 lock, which in turn prevents the WAL-index and WAL files from being
665 deleted out from under other users, and prevents a transition out of
666 WAL-mode while other users are accessing the database in WAL-mode.
667
668
669 </p></li><li><p><b>WAL_WRITE_LOCK</b>
670 </p><p>
671 The WAL_WRITE_LOCK is only locked exclusively. There is never a shared
672 lock taken on WAL_WRITE_LOCK.
673 </p><p>
674 An EXCLUSIVE WAL_WRITE_LOCK is held by any connection that is appending
675 content to the end of the WAL. Hence, only a single process at a time
676 can append content to the WAL. If a <a href="fileformat2.html#walreset">WAL reset</a> occurs as a consequence of
677 a write, then the <a href="walformat.html#nbackfill">nBackfill</a> field of the WAL-index header is reset to
678 zero while holding this lock.
679 </p><p>An EXCLUSIVE is also held WAL_WRITE_LOCK, and on several other locking
680 bytes, when a connection is running <a href="walformat.html#recovery">recovery</a> on the shared WAL-index.
681
682 </p></li><li><p><b>WAL_CKPT_LOCK</b>
683 </p><p>
684 The WAL_CKPT_LOCK is only locked exclusively. There is never a shared
685 lock taken on WAL_CKPT_LOCK.
686 </p><p>
687 An EXCLUSIVE WAL_CKPT_LOCK is held by any connection that is running
688 a <a href="wal.html#ckpt">checkpoint</a>. The <a href="walformat.html#nbackfill">nBackfill</a> field of the WAL-index header may be
689 increased while holding this exclusive lock, but it may not be decreased.
690 </p><p>An EXCLUSIVE is also held WAL_CKPT_LOCK, and on several other locking
691 bytes, when a connection is running <a href="walformat.html#recovery">recovery</a> on the shared WAL-index.
692
693 </p></li><li><p><b>WAL_RECOVER_LOCK</b>
694 </p><p>
695 The WAL_RECOVER_LOCK is only locked exclusively. There is never a shared
696 lock taken on WAL_RECOVER_LOCK.
697 </p><p>
698 An EXCLUSIVE WAL_RECOVER_LOCK is held by any connection that is running
699 <a href="walformat.html#recovery">recovery</a> to reconstruct the shared WAL-index.
700 </p><p>
701 A read-only connection that is rebuilding its private heap-memory WAL-index
702 does not hold this lock. (It cannot, since read-only connections are not
703 allowed to hold any exclusive locks.) This lock is only held when rebuilding
704 the global shared WAL-index contained in the memory-mapped SHM file.
705 </p><p>
706 In addition to locking this byte, a connection running <a href="walformat.html#recovery">recovery</a> also
707 gets an exclusive lock on all other WAL locks except for WAL_READ_LOCK(0).
708
709 </p></li><li><p><b>WAL_READ_LOCK(N)</b>
710 </p><p>
711 There are five separate read locks, numbers 0 through 4.
712 Read locks may be either SHARED or EXCLUSIVE.
713 Connections obtain a shared lock on one of the read locks bytes while
714 they are within a transaction.
715 Connections also obtain an exclusive lock on read locks, one at a time,
716 for the brief moment while they are updating the values of the corresponding
717 read-marks.
718 Read locks 1 through 4 are held exclusively when running <a href="walformat.html#recovery">recovery</a>.
719 </p><p>
720 Each read lock byte corresponds to one of the five 32-bit read-mark
721 integers located in bytes 100 through 119 of the WAL-index header, as
722 follows:
723 </p><center>
724 <table border="1">
725 <tr><th>Lock Name</th><th>Lock offset</th><th>Read-mark name</th><th>Read-mark offset
726 </th></tr><tr><td>WAL_READ_LOCK(0)</td><td>123</td><td>read-mark[0]</td><td>100..103
727 </td></tr><tr><td>WAL_READ_LOCK(1)</td><td>124</td><td>read-mark[1]</td><td>104..107
728 </td></tr><tr><td>WAL_READ_LOCK(2)</td><td>125</td><td>read-mark[2]</td><td>108..111
729 </td></tr><tr><td>WAL_READ_LOCK(3)</td><td>126</td><td>read-mark[3]</td><td>112..115
730 </td></tr><tr><td>WAL_READ_LOCK(4)</td><td>127</td><td>read-mark[4]</td><td>116..119
731 </td></tr></table>
732 </center>
733 <p>
734 When a connection holds a shared lock on WAL_READ_LOCK(N), that is a
735 promise by the connection that it will use the WAL and not the database
736 file for any database pages that are modified by the first
737 read-mark[N] entries in the WAL.
738 The read-mark[0] is always zero. If a connection holds a shared lock
739 on WAL_READ_LOCK(0), that means the connection expects to be able to ignore
740 the WAL and read any content it wants from the main database.
741 If N>0 then the connection is free to use more of the WAL file beyond
742 read-mark[N] if it wants to, up to the first mxFrame frames.
743 But when a connection holds a shared lock on WAL_READ_LOCK(0), that is a
744 promise that it will never read content from the WAL
745 and will acquire all content directly from the main database.
746 </p><p>
747 When a checkpoint runs, if it sees a lock on WAL_READ_LOCK(N), then it
748 must not move WAL content into the main database for more than the first
749 read-mark[N] frames. Were it to do so, it would overwrite content that
750 the process holding the lock was expecting to be able to read out of the
751 main database file. A consequence of this is that if the WAL file
752 contains more than read-mark[N] frames (if mxFrame>read-mark[N]
753 for any read-mark for which WAL_READ_LOCK(N) is held by another process),
754 then the checkpoint cannot run to completion.
755 </p><p>
756 When a writer wants to <a href="fileformat2.html#walreset">reset the WAL</a>, it must ensure that there are
757 no locks on WAL_READ_LOCK(N) for N>0 because such locks indicate
758 that some other connection is still using the current WAL file and
759 a <a href="fileformat2.html#walreset">WAL reset</a> would delete content out from those other connections. It is
760 ok for a <a href="fileformat2.html#walreset">WAL reset</a> to occur if other connections are holding WAL_READ_LOCK(0)
761 because by holding WAL_READ_LOCK(0), those other connections are promising
762 not to use any content from the WAL.
763 </p></li></ul>
764
765 <h3 id="operations_that_require_locks_and_which_locks_those_operations_use"><span>2.3.2. </span>Operations that require locks and which locks those operations use</h3>
766
767 <ul>
768 <li><p><b>Transition into and out of WAL-mode</b>
769
770 </p><p>The SQLITE_LOCK_EXCLUSIVE lock must be held by a connection that wants
771 to transition into or out of WAL mode.
772 Transitioning into WAL mode is, therefore, just like any other write
773 transaction, since every write transaction in rollback mode requires
774 the SQLITE_LOCK_EXCLUSIVE lock.
775 If the database file is already in WAL mode (hence if the desire is to change
776 it back into rollback mode) and if there are two
777 or more connections to the database, then each of these connections will
778 be holding an SQLITE_LOCK_SHARED lock. That means that the
779 SQLITE_LOCK_EXCLUSIVE cannot be obtained, and the transition out of
780 WAL mode will not be allowed. This prevents one connection from deleting
781 WAL mode out from under another. It also means that the only way to move
782 a database from WAL mode into rollback mode is to close all but one
783 connection to the database.
784
785
786 </p></li><li><p><b>Close a connection to a WAL mode database</b>
787
788 </p><p>When a database connection closes (via <a href="c3ref/close.html">sqlite3_close()</a> or
789 <a href="c3ref/close.html">sqlite3_close_v2()</a>), an attempt is made to acquire
790 SQLITE_LOCK_EXCLUSIVE. If this attempt is successful, that means
791 the connection that is closing is the last connection to the database.
792 In that case, it is desirable to clean up the WAL and WAL-index files,
793 so the closing connection runs a <a href="wal.html#ckpt">checkpoint</a> (while holding
794 SQLITE_LOCK_EXCLUSIVE) and this deletes both the WAL and WAL-index files.
795 The SQLITE_LOCK_EXCLUSIVE is not released until after both the
796 WAL and WAL-index files have been deleted.
797
798 </p><p>If the application invokes
799 <a href="c3ref/file_control.html">sqlite3_file_control</a>(<a href="c3ref/c_fcntl_begin_atomic_write.html#sqlitefcntlpersistwal">SQLITE_FCNTL_PERSIST_WAL</a>) on the database
800 connection prior to closing, then the final checkpoint is still
801 run but the WAL and WAL-index files are
802 not deleted as they normally would be.
803 This leaves the database in a state that allows other processes
804 without write permission on the database, WAL, or WAL-index files
805 to open the database read-only.
806 If the WAL and WAL-index files are missing, then a process that
807 lacks permission to create and initialize those files will not be
808 able to open the database, unless the database is designated
809 as immutable using the <a href="uri.html#uriimmutable">immutable query parameter</a>.
810
811 </p></li><li><p><b>Reconstruct the global shared WAL-index during <a href="walformat.html#recovery">recovery</a></b>
812
813 </p><p>All of the WAL-index locks, except for WAL_READ_LOCK(0),
814 are held exclusively while reconstructing the global shared WAL-index
815 during <a href="walformat.html#recovery">recovery</a>.
816
817 </p></li><li><p><b>Append a new transaction to the end of the WAL</b>
818
819 </p><p>An exclusive lock is held on WAL_WRITE_LOCK while adding new
820 frames onto the end of a WAL file.
821
822 </p></li><li><p><b>Read content from the database and WAL as part of a transaction</b>
823
824 </p></li><li><p><b>Run a checkpoint</b>
825
826 </p></li><li><p><b>Reset the WAL file</b>
827
828 </p><p>A <a href="fileformat2.html#walreset">WAL reset</a> means to rewind the WAL and start adding new frames
829 at the beginning. This occurs while appending new frames to a WAL
830 that has <a href="walformat.html#mxframe">mxFrame</a> equal to <a href="walformat.html#nbackfill">nBackfill</a> and which has no locks on
831 WAL_READ_LOCK(1) through WAL_READ_LOCK(4). The WAL_WRITE_LOCK is
832 held.
833
834 </p></li></ul>
835
836 <a name="recovery"></a>
837
838 <h1 id="recovery"><span>3. </span>Recovery</h1>
839
840 <p>
841 Recovery is the process of rebuilding the WAL-index so that it is
842 synchronized with the WAL.
843
844 </p><p>
845 Recovery is run by the first thread to connect to a WAL-mode database.
846 Recovery restores the WAL-index so that it accurately describes the
847 WAL file. If there is no WAL file present when the first thread connects
848 to the database, there is nothing to recover, but the recovery process
849 still runs to initialize the WAL-index.
850
851 </p><p>
852 If the WAL-index is implemented as a memory-mapped file and that file is
853 read-only to the first thread to connect, then that thread creates a
854 private heap-memory ersazt WAL-index and runs the recovery routine to
855 populate that private WAL-index. The same data results, but it is held
856 privately rather that being written into the public shared memory area.
857
858 </p><p>
859 Recovery works by doing a single pass over the WAL, from beginning to end.
860 The checksums are verified on each frame of the WAL as it is read. The
861 scan stops at the end of the file or at the first invalid checksum.
862 The <a href="walformat.html#mxframe">mxFrame</a> field is set to the index of the last valid commit frame
863 in WAL. Since WAL frame numbers are indexed starting with 1, mxFrame is
864 also the number of valid frames in the WAL. A "commit frame" is a frame
865 that has a non-zero value in bytes 4 through 7 of the frame header.
866 Since the recovery procedure has no way of knowing how many frames of the
867 WAL might have previously been copied back into the database, it initializes
868 the <a href="walformat.html#nbackfill">nBackfill</a> value to zero.
869
870 </p><p>
871 During recovery of the global shared-memory WAL-index, exclusive locks are
872 held on WAL_WRITE_LOCK, WAL_CKPT_LOCK, WAL_RECOVER_LOCK, and WAL_READ_LOCK(1)
873 through WAL_READ_LOCK(4). In other words, all locks associated with the
874 WAL-index except for WAL_READ_LOCK(0) are held exclusively. This prevents
875 any other thread from writing the database and from reading any transactions
876 that are held in the WAL, until the recovery is complete.
877 </p><p align="center"><small><i>This page was last updated on 2025-05-10 11:18:57Z </small></i></p>
878