## Run this script to generated a lockingv3.html output file#set rcsid {$Id: }source common.tclheader {File Locking And Concurrency In SQLite Version 3}proc HEADING {level title} {  global pnum  incr pnum($level)  foreach i [array names pnum] {    if {$i>$level} {set pnum($i) 0}  }  set h [expr {$level+1}]  if {$h>6} {set h 6}  set n $pnum(1).$pnum(2)  for {set i 3} {$i<=$level} {incr i} {    append n .$pnum($i)  }  puts "<h$h>$n $title</h$h>"}set pnum(1) 0set pnum(2) 0set pnum(3) 0set pnum(4) 0set pnum(5) 0set pnum(6) 0set pnum(7) 0set pnum(8) 0HEADING 1 {File Locking And Concurrency In SQLite Version 3}puts {<p>Version 3 of SQLite introduces a more complex locking and journaling mechanism designed to improve concurrency and reduce the writer starvation problem.  The new mechanism also allows atomic commits of transactionsinvolving multiple database files.This document describes the new locking mechanism.The intended audience is programmers who want to understand and/or modifythe pager code and reviewers working to verify the designof SQLite version 3.</p>}HEADING 1 {Overview}puts {<p>Locking and concurrency control are handled by the the <a href="http://www.sqlite.org/cvstrac/getfile/sqlite/src/pager.c">pager module</a>.The pager module is responsible for making SQLite "ACID" (Atomic,Consistent, Isolated, and Durable).  The pager module makes sure changeshappen all at once, that either all changes occur or none of them do,that two or more processes do not try to access the databasein incompatible ways at the same time, and that once changes have beenwritten they persist until explicitly deleted.  The pager also providesan memory cache of some of the contents of the disk file.</p><p>The pager is unconcernedwith the details of B-Trees, text encodings, indices, and so forth.From the point of view of the pager the database consists ofa single file of uniform-sized blocks.  Each block is called a"page" and is usually 1024 bytes in size.   The pages are numberedbeginning with 1.  So the first 1024 bytes of the database are called"page 1" and the second 1024 bytes are call "page 2" and so forth. All other encoding details are handled by higher layers of the library.  The pager communicates with the operating system using one of severalmodules (Examples:<a href="http://www.sqlite.org/cvstrac/getfile/sqlite/src/os_unix.c">os_unix.c</a>,<a href="http://www.sqlite.org/cvstrac/getfile/sqlite/src/os_win.c">os_win.c</a>)that provides a uniform abstraction for operating system services.</p><p>The pager module effectively controls access for separate threads, orseparate processes, or both.  Throughout this document whenever theword "process" is written you may substitute the word "thread" withoutchanging the truth of the statement.</p>}HEADING 1 {Locking}puts {<p>From the point of view of a single process, a database filecan be in one of five locking states:</p><p><table cellpadding="20"><tr><td valign="top">UNLOCKED</td><td valign="top">No locks are held on the database.  The database may be neither read norwritten.  Any internally cached data is considered suspect and subject toverification against the database file before being used.  Other processes can read or write the database as their own locking statespermit.  This is the default state.</td></tr><tr><td valign="top">SHARED</td><td valign="top">The database may be read but not written.  Any number of processes can hold SHARED locks at the same time, hence there can bemany simultaneous readers.  But no other thread or process is allowedto write to the database file while one or more SHARED locks are active.</td></tr><tr><td valign="top">RESERVED</td><td valign="top">A RESERVED lock means that the process is planning on writing to thedatabase file at some point in the future but that it is currently justreading from the file.  Only a single RESERVED lock may be active at onetime, though multiple SHARED locks can coexist with a single RESERVED lock.RESERVED differs from PENDING in that new SHARED locks can be acquiredwhile there is a RESERVED lock.</td></tr><tr><td valign="top">PENDING</td><td valign="top">A PENDING lock means that the process holding the lock wants to writeto the database as soon as possible and is just waiting on all currentSHARED locks to clear so that it can get an EXCLUSIVE lock.  No new SHARED locks are permitted against the database ifa PENDING lock is active, though existing SHARED locks are allowed tocontinue.</td></tr><tr><td valign="top">EXCLUSIVE</td><td valign="top">An EXCLUSIVE lock is needed in order to write to the database file.Only one EXCLUSIVE lock is allowed on the file and no other locks ofany kind are allowed to coexist with an EXCLUSIVE lock.  In order tomaximize concurrency, SQLite works to minimize the amount of time thatEXCLUSIVE locks are held.</td></tr></table></p><p>The operating system interface layer understands and tracks all fivelocking states described above.  The pager module only tracks four of the five locking states.A PENDING lock is always just a temporarystepping stone on the path to an EXCLUSIVE lock and so the pager moduledoes not track PENDING locks.</p>}HEADING 1 {The Rollback Journal}puts {<p>Any time a process wants to make a changes to a database file, itfirst records enough information in the <em>rollback journal</em> torestore the database file back to its initial condition.  Thus, beforealtering any page of the database, the original contents of that pagemust be written into the journal.  The journal also records the initialsize of the database so that if the database file grows it can be truncatedback to its original size on a rollback.</p><p>The rollback journal is a ordinary disk file that has the same name asthe database file with the suffix "<tt>-journal</tt>" added.</p><p>If SQLite is working with multiple databases at the same time(using the ATTACH command) then each database has its own journal.But there is also a separate aggregate journalcalled the <em>master journal</em>.The master journal does not contain page data used for rolling backchanges.  Instead the master journal contains the names of theindividual file journals for each of the ATTACHed databases.   Each ofthe individual file journals also contain the name of the master journal.If there are no ATTACHed databases (or if none of the ATTACHed databaseis participating in the current transaction) no master journal iscreated and the normal rollback journal contains an empty stringin the place normally reserved for recording the name of the masterjournal.</p><p>A individual file journal is said to be <em>hot</em>if it needs to be rolled backin order to restore the integrity of its database.  A hot journal is created when a process is in the middle of a databaseupdate and a program or operating system crash or power failure prevents the update from completing.Hot journals are an exception condition. Hot journals exist to recover from crashes and power failures.If everything is working correctly (that is, if there are no crashes or power failures)you will never get a hot journal.</p><p>If no master journal is involved, thena journal is hot if it exists and its corresponding database filedoes not have a RESERVED lock.If a master journal is named in the file journal, then the file journalis hot if its master journal exists and there is no RESERVEDlock on the corresponding database file.It is important to understand when a journal is hot so thepreceding rules will be repeated in bullets:</p><ul><li>A journal is hot if...    <ul>    <li>It exists, and</li>    <li>It's master journal exists or the master journal name is an        empty string, and</li>    <li>There is no RESERVED lock on the corresponding database file.</li>    </ul></li></ul>}HEADING 2 {Dealing with hot journals}puts {<p>Before reading from a a database file, SQLite always checks to see if thatdatabase file has a hot journal.  If the file does have a hot journal, thenthe journal is rolled back before the file is read.  In this way, we ensurethat the database file is in a consistent state before it is read.</p><p>When a process wants to read from a database file, it followedthe following sequence of steps:</p><ol><li>Open the database file and obtain a SHARED lock.  If the SHARED lock    cannot be obtained, fail immediately and return SQLITE_BUSY.</li><li>Check to see if the database file has a hot journal.   If the file    does not have a hot journal, we are done.  Return immediately.    If there is a hot journal, that journal must be rolled back by    the subsequent steps of this algorithm.</li><li>Acquire a PENDING lock then an EXCLUSIVE lock on the database file.    (Note: Do not acquire a RESERVED lock because that would make    other processes think the journal was no longer hot.)  If we    fail to acquire these locks it means another process    is already trying to do the rollback.  In that case,    drop all locks, close the database, and return SQLITE_BUSY. </li><li>Read the journal file and roll back the changes.</li><li>Wait for the rolled back changes to be written onto     the surface of the disk.  This protects the integrity of the database    in case another power failure or crash occurs.</li><li>Delete the journal file.</li><li>Delete the master journal file if it is safe to do so.    This step is optional.  It is here only to prevent stale    master journals from cluttering up the disk drive.    See the discussion below for details.</li><li>Drop the EXCLUSIVE and PENDING locks but retain the SHARED lock.</li></ol><p>After the algorithm above completes successfully, it is safe to read from the database file.  Once all reading has completed, theSHARED lock is dropped.</p>}HEADING 2 {Deleting stale master journals}puts {<p>A stale master journal is a master journal that is no longer beingused for anything.  There is no requirement that stale master journalsbe deleted.  The only reason for doing so is to free up disk space.</p><p>A master journal is stale if no individual file journals are pointingto it.  To figure out if a master journal is stale, we first read themaster journal to obtain the names of all of its file journals.  Thenwe check each of those file journals.  If any of the file journals namedin the master journal exists and points back to the master journal, thenthe master journal is not stale.  If all file journals are either missingor refer to other master journals or no master journal at all, then themaster journal we are testing is stale and can be safely deleted.</p>}HEADING 1 {Writing to a database file}puts {<p>To write to a database, a process must first acquire a SHARED lockas described above (possibly rolling back incomplete changes if thereis a hot journal). After a SHARED lock is obtained, a RESERVED lock must be acquired.The RESERVED lock signals that the process intends to write to the