<tcl>
hd_keywords {file I/O}
proc hd_assumption {id text} {
# hd_requirement $id $text
}
unset -nocomplain fioreq
hd_read_requirement_file $::DOC/req/hlr35000.txt fioreq
proc fileio_noop {args} {}
proc process {text} {
set zOut ""
set zSpecial ""
foreach zLine [split $text "\n"] {
switch -regexp $zLine {
{^ *REQ *[^ ][^ ]* *$} {
regexp { *REQ *([^ ]+) *} $zLine -> zRecid
append zOut "<p class=req id=$zRecid>\n"
append zOut "[lindex $::fioreq($zRecid) 1]\n"
set zRecText ""
}
{^ *ASSUMPTION *[^ ][^ ]* *$} {
regexp { *ASSUMPTION *([^ ]+) *} $zLine -> zRecid
append zOut "<p class=req id=$zRecid>\n"
set zSpecial hd_assumption
set zRecText ""
}
{^ *$} {
if {$zSpecial ne ""} {
$zSpecial $zRecid $zRecText
set zSpecial ""
append zOut </p>
}
}
default {
if {$zSpecial ne ""} {
if {[regexp {^ *\. *$} $zLine]} {set zLine ""}
append zRecText "$zLine\n"
}
append zOut "$zLine\n"
}
}
}
set zOut
}
hd_resolve [process {
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css">
<script type="text/javascript" src=images/fileformat/rtdocs.js></script>
</head>
<div id=document_title>SQLite File IO Specification</div>
<div id=toc_header>Table Of Contents</div>
<div id=toc>
<b>Javascript is required for some features of this document, including
table of contents, figure numbering and internal references (section
numbers and hyper-links.
</b>
</div>
<!-- End of standard rt docs header -->
<h1 id=overview>Overview</h1>
<p>
SQLite stores an entire database within a single file, the format of
which is described in the <i>SQLite File Database File Format</i>
document <cite>ff_sqlitert_requirements</cite>. Each database file is
stored within a file system, presumably provided by the host operating
system. Instead of interfacing with the operating system directly,
the host application is required to supply an adaptor component that
implements the <i>SQLite Virtual File System</i> interface
(described in <cite>capi_sqlitert_requirements</cite>). The adaptor
component is responsible for translating the calls made by SQLite to
the <i>VFS</i> interface into calls to the file-system interface
provided by the operating system. This arrangement is depicted in figure
<cite>figure_vfs_role</cite>.
<center><img src="images/fileformat/vfs_role.gif">
<p><i>Figure <span class=fig id=figure_vfs_role></span> - Virtual File System (VFS) Adaptor</i>
</center>
<p>
Although it would be easy to design a system that uses the <i>VFS</i>
interface to read and update the content of a database file stored
within a file-system, there are several complicated issues that need
to be addressed by such a system:
<ol>
<li><p>SQLite is required to <b>implement atomic and durable
transactions</b> (the 'A' and 'D' from the ACID acronym), even if an
application, operating system or power failure occurs midway through or
shortly after updating a database file.
<p>To implement atomic transactions in the face of potential
application, operating system or power failures, database writers write
a copy of those portions of the database file that they are going to
modify into a second file, the <i>journal file</i>, before writing
to the database file. If a failure does occur while modifying the
database file, SQLite can reconstruct the original database
(before the modifications were attempted) based on the contents of
the <i>journal file</i>.
<li><p>SQLite is required to <b>implement isolated transactions</b> (the 'I'
from the ACID acronym).
<p>This is done by using the file locking facilities provided by the
VFS adaptor to serialize writers (write transactions) and preventing
readers (read transactions) from accessing database files while writers
are midway through updating them.
<li><p>For performance reasons, it is advantageous to <b>minimize the
quantity of data read and written</b> to and from the file-system.
<p>As one might expect, the amount of data read from the database
file is minimized by caching portions of the database file in main
memory. Additionally, multiple updates to the database file that
are part of the same <i>write transaction</i> may be cached in
main memory and written to the file together, allowing for
more efficient IO patterns and eliminating the redundant write
operations that could take place if part of the database file is
modified more than once within a single <i>write transaction</i>.
</ol>
<p class=todo>
System requirement references for the above points.
<p>
This document describes in detail the way that SQLite uses the API
provided by the VFS adaptor component to solve the problems and implement
the strategies enumerated above. It also specifies the assumptions made
about the properties of the system that the VFS adaptor provides
access to. For example, specific assumptions about the extent of
data corruption that may occur if a power failure occurs while a
database file is being updated are presented in section
<cite>fs_characteristics</cite>.
<p>
This document does not specify the details of the interface that must
be implemented by the VFS adaptor component, that is left to
<cite>capi_sqlitert_requirements</cite>.
<h2>Relationship to Other Documents</h2>
<p>
Related to C-API requirements:
<ol>
<li>Opening a connection.
<li>Closing a connection.
</ol>
<p>
Related to SQL requirements:
<ol>
<li value=3>Opening a read-only transaction.
<li>Terminating a read-only transaction.
<li>Opening a read-write transaction.
<li>Committing a read-write transaction.
<li>Rolling back a read-write transaction.
<li>Opening a statement transaction.
<li>Committing a statement transaction.
<li>Rolling back a statement transaction.
<li>Committing a multi-file transaction.
</ol>
<p>
Related to file-format requirements:
<ol>
<li value=12>Pinning (reading) a database page.
<li>Unpinning a database page.
<li>Modifying the contents of a database page.
<li>Appending a new page to the database file.
<li>Truncating a page from the end of the database file.
</ol>
<h2>Document Structure</h2>
<p>
Section <cite>vfs_assumptions</cite> of this document describes the
various assumptions made about the system to which the VFS adaptor
component provides access. The basic capabilities and functions
required from the VFS implementation are presented along with the
description of the VFS interface in
<cite>capi_sqlitert_requirements</cite>. Section
<cite>vfs_assumptions</cite> complements this by describing in more
detail the assumptions made about VFS implementations on which the
algorithms presented in this document depend. Some of these assumptions
relate to performance issues, but most concern the expected state of
the file-system following a failure that occurs midway through
modifying a database file.
<p>
Section <cite>database_connections</cite> introduces the concept of
a <i>database connection</i>, a combination of a file-handle and
in-memory cache used to access a database file. It also describes the
VFS operations required when a new <i>database connection</i> is
created (opened), and when one is destroyed (closed).
<p>
Section <cite>reading_data</cite> describes the steps required to
open a <i>read transaction</i> and read data from a database file.
<p>
Section <cite>writing_data</cite> describes the steps required to
open a <i>write transaction </i> and write data to a database file.
<p>
Section <cite>rollback</cite> describes the way in which aborted
<i>write transactions</i> may be rolled back (reverted), either as
a result of an explicit user directive or because an application,
operating system or power failure occurred while SQLite was midway
through updating a database file.
<p>
Section <cite>page_cache_algorithms</cite> describes some of the
algorithms used to determine exactly which portions of the database
file are cached by a <i>page cache</i>, and the effect that they
have on the quantity and nature of the required VFS operations.
It may at first seem odd to include the <i>page cache</i>, which is
primarily an implementation detail, in this document. However, it is
necessary to acknowledge and describe the <i>page cache</i> in order to
provide a more complete explanation of the nature and quantity of IO
performed by SQLite.
<h2>Glossary</h2>
<p class=todo>
After this document is ready, make the vocabulary consistent and
then add a glossary here.
<h1 id=vfs_assumptions>VFS Adaptor Related Assumptions</h1>
<p>
This section documents those assumptions made about the system that
the VFS adaptor provides access to. The assumptions noted in section
<cite>fs_characteristics</cite> are particularly important. If these
assumptions are not true, then a power or operating system failure
may cause SQLite databases to become corrupted.
<h2 id=fs_performance>Performance Related Assumptions</h2>
<p>
SQLite uses the assumptions in this section to try to speed up
reading from and writing to the database file.
ASSUMPTION A21010
It is assumed that writing a series of sequential blocks of data to
a file in order is faster than writing the same blocks in an arbitrary
order.
<h2 id=fs_characteristics>System Failure Related Assumptions</h2>
<p>
In the event of an operating system or power failure, the various
combinations of file-system software and storage hardware available
provide varying levels of guarantee as to the integrity of the data
written to the file system just before or during the failure. The exact
combination of IO operations that SQLite is required to perform in
order to safely modify a database file depend on the exact
characteristics of the target platform.
<p>
This section describes the assumptions that SQLite makes about the
content of a file-system following a power or system failure. In
other words, it describes the extent of file and file-system corruption
that such an event may cause.
<p>
SQLite queries an implementation for file-system characteristics
using the xDeviceCharacteristics() and xSectorSize() methods of the
database file file-handle. These two methods are only ever called
on file-handles open on database files. They are not called for
<i>journal files</i>, <i>master-journal files</i> or
<i>temporary database files</i>.
<p>
The file-system <i>sector size</i> value determined by calling the
xSectorSize() method is a power of 2 value between 512 and 32768,
inclusive <span class=todo>reference to exactly how this is
determined</span>. SQLite assumes that the underlying storage
device stores data in blocks of <i>sector-size</i> bytes each,
sectors. It is also assumed that each aligned block of
<i>sector-size</i> bytes of each file is stored in a single device
sector. If the file is not an exact multiple of <i>sector-size</i>
bytes in size, then the final device sector is partially empty.
<p>
Normally, SQLite assumes that if a power failure occurs while
updating any portion of a sector then the contents of the entire
device sector is suspect following recovery. After writing to
any part of a sector within a file, it is assumed that the modified
sector contents are held in a volatile buffer somewhere within
the system (main memory, disk cache etc.). SQLite does not assume
that the updated data has reached the persistent storage media, until
after it has successfully <i>synced</i> the corresponding file by
invoking the VFS xSync() method. <i>Syncing</i> a file causes all
modifications to the file up until that point to be committed to
persistent storage.
<p>
Based on the above, SQLite is designed around a model of the
file-system whereby any sector of a file written to is considered to be
in a transient state until after the file has been successfully
<i>synced</i>. Should a power or system failure occur while a sector
is in a transient state, it is impossible to predict its contents
following recovery. It may be written correctly, not written at all,
overwritten with random data, or any combination thereof.
<p>
For example, if the <i>sector-size</i> of a given file-system is
2048 bytes, and SQLite opens a file and writes a 1024 byte block
of data to offset 3072 of the file, then according to the model
the second sector of the file is in the transient state. If a
power failure or operating system crash occurs before or during
the next call to xSync() on the file handle, then following system
recovery SQLite assumes that all file data between byte offsets 2048
and 4095, inclusive, is invalid. It also assumes that since the first
sector of the file, containing the data from byte offset 0 to 2047
inclusive, is valid, since it was not in a transient state when the
crash occurred.
<p>
Assuming that any and all sectors in the transient state may be
corrupted following a power or system failure is a very pessimistic
approach. Some modern systems provide more sophisticated guarantees
than this. SQLite allows the VFS implementation to specify at runtime
that the current platform supports zero or more of the following
properties:
<ul>
<li><p>The <b>safe-append</b> property. If a system supports the
<i>safe-append</i> property, it means that when a file is extended
the new data is written to the persistent media before the size
of the file itself is updated. This guarantees that if a failure
occurs after a file has been extended, following recovery
the write operations that extended the file will appear to have
succeeded or not occurred at all. It is not possible for invalid
or garbage data to appear in the extended region of the file.
<li><p>The <b>atomic-write</b> property. A system that supports this
property also specifies the size or sizes of the blocks that it
is capable of writing. Valid sizes are powers of two greater than
512. If a write operation modifies a block of <i>n</i> bytes,
where <i>n</i> is one of the block sizes for which <i>atomic-write</i>
is supported, then it is impossible for an aligned write of <i>n</i>
bytes to cause data corruption. If a failure occurs after such
a write operation and before the applicable file handle is
<i>synced</i>, then following recovery it will appear as if the
write operation succeeded or did not take place at all. It is not
possible that only part of the data specified by the write operation
was written to persistent media, nor is it possible for any content
of the sectors spanned by the write operation to be replaced with
garbage data, as it is normally assumed to be.
<li><p>The <b>sequential-write</b> property. A system that supports the
<i>sequential-write</i> property guarantees that the various write
operations on files within the same file-system are written to the
persistent media in the same order that they are performed by the
application and that each operation is concluded before the next
is begun. If a system supports the <i>sequential-write</i>
property, then the model used to determine the possible states of
the file-system following a failure is different.
<p>If a system supports <i>sequential-write</i> it is assumed that
<i>syncing</i> any file within the file system flushes all write
operations on all files (not just the <i>synced</i> file) to
the persistent media. If a failure does occur, it is not known
whether or not any of the write operations performed by SQLite
since the last time a file was <i>synced</i>. SQLite is able to
assume that if the write operations of unknown status are arranged
in the order that they occurred:
<ol>
<li> the first <i>n</i> operations will have been executed
successfully,
<li> the next operation puts all device sectors that it modifies
into the transient state, so that following recovery each
sector may be partially written, completely written, not
written at all or populated with garbage data,
<li> the remaining operations will not have had any effect on
the contents of the file-system.
</ol>
</ul>
<h3 id=fs_assumption_details>Failure Related Assumption Details</h3>
<p>
This section describes how the assumptions presented in the parent
section apply to the individual API functions and operations provided
by the VFS to SQLite for the purposes of modifying the contents of the
file-system.
<p>
SQLite manipulates the contents of the file-system using a combination
of the following four types of operation:
<ul>
<li> <b>Create file</b> operations. SQLite may create new files
within the file-system by invoking the xOpen() method of
the sqlite3_io_methods object.
<li> <b>Delete file</b> operations. SQLite may remove files from the
file system by calling the xDelete() method of the
sqlite3_io_methods object.
<li> <b>Truncate file</b> operations. SQLite may truncate existing
files by invoking the xTruncate() method of the sqlite3_file
object.
<li> <b>Write file</b> operations. SQLite may modify the contents
and increase the size of a file by files by invoking the xWrite()
method of the sqlite3_file object.
</ul>
<p>
Additionally, all VFS implementations are required to provide the
<i>sync file</i> operation, accessed via the xSync() method of the
sqlite3_file object, used to flush create, write and truncate operations
on a file to the persistent storage medium.
<p>
The formalized assumptions in this section refer to <i>system failure</i>
events. In this context, this should be interpreted as any failure that
causes the system to stop operating. For example a power failure or
operating system crash.
<p>
SQLite does not assume that a <b>create file</b> operation has actually
modified the file-system records within persistent storage until
after the file has been successfully <i>synced</i>.
ASSUMPTION A21001
If a system failure occurs during or after a "create file"
operation, but before the created file has been <i>synced</i>, then
SQLite assumes that it is possible that the created file may not
exist following system recovery.
<p>
Of course, it is also possible that it does exist following system
recovery.
ASSUMPTION A21002
If a "create file" operation is executed by SQLite, and then the
created file <i>synced</i>, then SQLite assumes that the file-system
modifications corresponding to the "create file" operation have been
committed to persistent media. It is assumed that if a system
failure occurs any time after the file has been successfully
<i>synced</i>, then the file is guaranteed to appear in the file-system
following system recovery.
<p>
A <b>delete file</b> operation (invoked by a call to the VFS xDelete()
method) is assumed to be an atomic and durable operation.
</p>
ASSUMPTION A21003
If a system failure occurs at any time after a "delete file"
operation (call to the VFS xDelete() method) returns successfully, it is
assumed that the file-system will not contain the deleted file following
system recovery.
ASSUMPTION A21004
If a system failure occurs during a "delete file" operation,
it is assumed that following system recovery the file-system will
either contain the file being deleted in the state it was in before
the operation was attempted, or not contain the file at all. It is
assumed that it is not possible for the file to have become corrupted
purely as a result of a failure occurring during a "delete file"
operation.
<p>
The effects of a <b>truncate file</b> operation are not assumed to
be made persistent until after the corresponding file has been
<i>synced</i>.
ASSUMPTION A21005
If a system failure occurs during or after a "truncate file"
operation, but before the truncated file has been <i>synced</i>, then
SQLite assumes that the size of the truncated file is either as large
or larger than the size that it was to be truncated to.
ASSUMPTION A21006
If a system failure occurs during or after a "truncate file"
operation, but before the truncated file has been <i>synced</i>, then
it is assumed that the contents of the file up to the size that the
file was to be truncated to are not corrupted.
<p>
The above two assumptions may be interpreted to mean that if a
system failure occurs after file truncation but before the truncated
file is <i>synced</i>, the contents of the file following the point
at which it was to be truncated may not be trusted. They may contain
the original file data, or may contain garbage.
ASSUMPTION A21007
If a "truncate file" operation is executed by SQLite, and then the
truncated file <i>synced</i>, then SQLite assumes that the file-system
modifications corresponding to the "truncate file" operation have been
committed to persistent media. It is assumed that if a system
failure occurs any time after the file has been successfully
<i>synced</i>, then the effects of the file truncation are guaranteed
to appear in the file system following recovery.
<p>
A <b>write file</b> operation modifies the contents of an existing file
within the file-system. It may also increase the size of the file.
The effects of a <i>write file</i> operation are not assumed to
be made persistent until after the corresponding file has been
<i>synced</i>.
ASSUMPTION A21008
If a system failure occurs during or after a "write file"
operation, but before the corresponding file has been <i>synced</i>,
then it is assumed that the content of all sectors spanned by the
<i>write file</i> operation are untrustworthy following system
recovery. This includes regions of the sectors that were not
actually modified by the write file operation.
ASSUMPTION A21011
If a system failure occurs on a system that supports the
<i>atomic-write</i> property for blocks of size <i>N</i> bytes
following an aligned write of <i>N</i>
bytes to a file but before the file has been successfully <i>synced</i>,
then is assumed following recovery that all sectors spanned by the
write operation were correctly updated, or that none of the sectors were
modified at all.
ASSUMPTION A21012
If a system failure occurs on a system that supports the
<i>safe-append</i> following a write operation that appends data
to the end of the file without modifying any of the existing file
content but before the file has been successfully <i>synced</i>,
then is assumed following recovery that either the data was
correctly appended to the file, or that the file size remains
unchanged. It is assumed that it is impossible that the file be
extended but populated with incorrect data.
ASSUMPTION A21013
Following a system recovery, if a device sector is deemed to be
untrustworthy as defined by A21008 and neither A21011 or A21012
apply to the range of bytes written, then no assumption can be
made about the content of the sector following recovery. It is
assumed that it is possible for such a sector to be written
correctly, not written at all, populated with garbage data or any
combination thereof.
ASSUMPTION A21009
If a system failure occurs during or after a "write file"
operation that causes the file to grow, but before the corresponding
file has been <i>synced</i>, then it is assumed that the size of
the file following recovery is as large or larger than it was when
it was most recently <i>synced</i>.
<p>
If a system supports the <i>sequential-write</i> property, then further
assumptions may be made with respect to the state of the file-system
following recovery from a <i>system failure</i>. Specifically, it is
assumed that create, truncate, delete and write file operations are
applied to the persistent representation in the same order as they
are performed by SQLite. Furthermore, it is assumed that the
file-system waits until one operation is safely written to the
persistent media before the next is attempted, just as if the relevant
file were <i>synced</i> following each operation.
ASSUMPTION A21014
If a system failure occurs on a system that supports the
<i>sequential-write</i> property, then it is assumed that all
operations completed before the last time any file was <i>synced</i>
have been successfully committed to persistent media.
ASSUMPTION A21015
If a system failure occurs on a system that supports the
<i>sequential-write</i> property, then it is assumed that the set
of possible states that the file-system may be in following recovery
is the same as if each of the write operations performed since the most
recent time a file was <i>synced</i> was itself followed by a <i>sync
file</i> operation, and that the system failure may have occurred during
any of the write or <i>sync file</i> operations.
<!--
<p>
The return value of the xSectorSize() method, the <i>sector-size</i>, is
expected by SQLite to be a power of 2 value greater than or equal to 512.
<p class=todo>
What does it do if this is not the case? If the sector size is less
than 512 then 512 is used instead. How about a non power-of-two value?
UPDATE: How this situation is handled should be described in the API
requirements. Here we can just refer to the other document.
<p>
SQLite assumes that files are stored and written to within the
file-system as a collection of blocks (hereafter sectors) of data, each
<i>sector-size</i> bytes in size. This model is used to derive
the following assumptions related to the expected state of the
file-system following a power failure or operating system crash.
<ul>
<li>
After part or all of a file sector has been modified
using the xWrite() method of an open file-handle, the sector
is said to be in a transient state, where the operating system
makes no guarantees about the actual content of the sector on the
persistent media. The sector remains in the transient state until
the next successful call to xSync() on the same file-handle
returns. If a power failure or operating system crash occurs, then
part or all of all sectors in the transient state when the crash
occurred may contain invalid data following system recovery.
<li>
Following a power failure or operating system crash, the content
of all sectors that were not in a transient state when the crash
occurred may be trusted.
</ul>
<p class=todo>
What do we assume about the other three file-system write
operations - xTruncate(), xDelete() and "create file"?
<p>
The xDeviceCharacteristics() method returns a set of flags,
indicating which of the following properties (if any) the
file-system provides:
<ul>
<li>The <b><i>sequential IO</i></b> property. If a file-system has this
property, then in the event of a crash at most a single sector
may contain invalid data. The file-system guarantees
<li>The <b><i>safe-append</i></b> property.
<li>The <b><i>atomic write</i></b> property.
</ul>
<p class=todo>
Write an explanation as to how the file-system properties influence
the model used to predict file damage after a catastrophe.
-->
<h1 id=database_connections>Database Connections</h1>
<p>
Within this document, the term <i>database connection</i> has a slightly
different meaning from that which one might assume. The handles returned
by the <code>sqlite3_open()</code> and <code>sqlite3_open16()</code>
APIs (<span class=todo>reference</span>) are referred to as <i>database
handles</i>. A <i>database connection</i> is a connection to a single
database file using a single file-handle, which is held open for the
lifetime of the connection. Using the SQL ATTACH syntax, multiple
<i>database connections</i> may be accessed via a single <i>database
handle</i>. Or, using SQLite's <i>shared-cache mode</i> feature, multiple
<i>database handles</i> may access a single <i>database connection</i>.
<p>
Usually, a new <i>database connection</i> is opened whenever the user opens
new <i>database handle</i> on a real database file (not an in-memory
database) or when a database file is attached to an existing <i>database
connection</i> using the SQL ATTACH syntax. However if the <i>shared-cache
mode</i> feature is enabled, then the database file may be accessed through
an existing <i>database connection</i>. For more information on
<i>shared-cache mode</i>, refer to <span class=todo>Reference</span>. The
various IO operations required to open a new connection are detailed in
section <cite>open_new_connection</cite> of this document.
<p>
Similarly, a <i>database connection</i> is usually closed when the user
closes a <i>database handle</i> that is open on a real database file or
has had one or more real database files attached to it using the ATTACH
mechanism, or when a real database file is detached from a <i>database
connection</i> using the DETACH syntax. Again, the exception is if
<i>shared-cache mode</i> is enabled. In this case, a <i>database
connection</i> is not closed until its number of users reaches zero.
The IO related steps required to close a <i>database connection</i> are
described in section <cite>closing_database_connection</cite>.
<p class=todo>
After sections 4 and 5 are finished, come back here and see if we can add a
list of state items associated with each database connection to make things
easier to understand. i.e each database connection has a file handle, a set
of entries in the page cache, an expected page size etc.
<h2 id=open_new_connection>Opening a New Connection</h2>
<p>
This section describes the VFS operations that take place when a
new database connection is created.
<p>
Opening a new database connection is a two-step process:
<ol>
<li> A file-handle is opened on the database file.
<li> If step 1 was successful, an attempt is made to read the
<i>database file header</i> from the database file using the
new file-handle.
</ol>
<p>
In step 2 of the procedure above, the database file is not locked
before it is read from. This is the only exception to the locking
rules described in section <cite>reading_data</cite>.
<p>
The reason for attempting to read the <i>database file header</i>
is to determine the <i>page-size</i> used by the database file.
Because it is not possible to be certain as to the <i>page-size</i>
without holding at least a <i>shared lock</i> on the database file
(because some other <i>database connection</i> might have changed it
since the <i>database file header</i> was read), the value read from the
<i>database file header</i> is known as the <i>expected page size</i>.
REQ H35060
REQ H35070
REQ H35080
REQ H35090
<h2 id=closing_database_connection>Closing a Connection</h2>
<p>
This section describes the VFS operations that take place when an
existing database connection is closed (destroyed).
<p>
Closing a database connection is a simple matter. The open VFS
file-handle is closed and in-memory <i>page cache</i> related resources
are released.
REQ H35400
REQ H35430
<h1 id=page_cache>The Page Cache</h1>
<p>
The contents of an SQLite database file are formatted as a set of
fixed size pages. See <cite>ff_sqlitert_requirements</cite> for a
complete description of the format used. The <i>page size</i> used
for a particular database is stored as part of the database file
header at a well-known offset within the first 100 bytes of the
file. Almost all read and write operations performed by SQLite on
database files are done on blocks of data <i>page-size</i> bytes
in size.
<p>
All SQLite database connections running within a single process share
a single <i>page cache</i>. The <i>page cache</i> caches data read from
database files in main-memory on a per-page basis. When SQLite requires
data from a database file to satisfy a database query, it checks the <i>
page cache</i> for usable cached versions of the required database
pages before loading it from the database file. If no usable cache
entry can be found and the database page data is loaded from the database
file, it is cached in the <i>page cache</i> in case the same data is
needed again later. Because reading from the database file is assumed to
be an order of magnitude faster than reading from main-memory, caching
database page content in the <i>page cache</i> to minimize the number
of read operations performed on the database file is a significant
performance enhancement.
<p>
The <i>page cache</i> is also used to buffer database write operations.
When SQLite is required to modify one of more of the <i>database pages</i>
that make up a database file, it first modifies the cached version of
the page in the <i>page cache</i>. At that point the page is considered
a "dirty" page. At some point later on, the new content of the "dirty"
page is copied from the <i>page cache</i> into the database file via
the VFS interface. Buffering writes in the <i>page cache</i> can reduce
the number of write operations required on the database file (in cases
where the same page is updated twice) and allows optimizations based
on the assumptions outlined in section <cite>fs_performance</cite>.
<p>
Database read and write operations, and the way in which they interact
with and use the <i>page cache</i>, are described in detail in sections
<cite>reading_data</cite> and <cite>writing_data</cite> of this document,
respectively.
<p>
At any one time, the <i>page cache</i> contains zero or more <i>page cache
entries</i>, each of which has the following data associated with it:
<ul>
<li><p>
A reference to <b>the associated <i>database connection</i></b>. Each
entry in the <i>page cache</i> is associated with a single <i>database
connection</i>; the <i>database connection</i> that created the entry.
A <i>page cache entry</i> is only ever used by the <i>database
connection</i> that created it. Page cache entries are not shared between
<i>database connections</i>.
<li><p>
The <b><i>page number</i></b> of the cached page. Pages are sequentially
numbered within a database file starting from page 1 (page 1 begins at
byte offset 0). Refer to <cite>ff_sqlitert_requirements</cite> for
details.
<li><p>
The <b>cached data</b>; a blob of data <i>page-size</i> bytes in size.
</ul>
<p>
The first two elements in the list above, the associated <i>database
connection</i> and the <i>page number</i>, uniquely identify the
<i>page cache entry</i>. At no time may the <i>page cache</i> contain two
entries for which both the <i>database connection</i> and <i>page
number</i> are identical. Or, put another way, a single <i>database
connection</i> never caches more than one copy of a database page
within the <i>page cache</i>.
<p>
At any one time, each <i>page cache entry</i> may be said to be a <i>clean
page</i>, a <i>non-writable dirty page</i> or a <i>writable dirty page</i>,
according to the following definitions:
<ul>
<li> <p>A <b><i>clean page</i></b> is one for which the cached data
currently matches the contents of the corresponding page of
the database file. The page has not been modified since it was
loaded from the file.
<li> <p>A <b><i>dirty page</i></b> is a <i>page cache entry</i> for which
the cached data has been modified since it was loaded from the database
file, and so no longer matches the current contents of the
corresponding database file page. A <i>dirty page</i> is one that is
currently buffering a modification made to the database file as part
of a <i>write transaction</i>.
<li> <p>Within this document, the term <b><i>non-writable dirty
page</i></b> is used specifically to refer to a <i>page cache
entry</i> with modified content for which it is not yet safe to update
the database file with. It is not safe to update a database file with
a buffered write if a power or system failure that occurs during or
soon after the update may cause the database to become corrupt
following system recovery, according to the assumptions made in
section <cite>fs_assumption_details</cite>.
<li> <p>A <i>dirty page</i> for which it would be safe to update the
corresponding database file page with the modified contents of
without risking database corruption is known as a
<b><i>writable dirty page</i></b>.
</ul>
<p>
The exact logic used to determine if a <i>page cache entry</i> with
modified content is a <i>dirty page</i> or <i>writable page</i> is
presented in section <cite>page_cache_algorithms</cite>.
<p>
Because main-memory is a limited resource, the <i>page cache</i> cannot
be allowed to grow indefinitely. As a result, unless all database files
opened by database connections within the process are quite small,
sometimes data must be discarded from the <i>page cache</i>. In practice
this means <i>page cache entries</i> must be purged to make room
for new ones. If a <i>page cache entry</i> being removed from the <i>page
cache</i> to free main-memory is a <i>dirty page</i>, then its contents
must be saved into the database file before it can be discarded without
data loss. The following two sub-sections describe the algorithms used by
the <i>page cache</i> to determine exactly when existing <i>page cache
entries</i> are purged (discarded).
<h2>Page Cache Configuration</h2>
<p class=todo>
Describe the parameters set to configure the page cache limits.
<h2 id=page_cache_algorithms>Page Cache Algorithms</h2>
<p class=todo>
Requirements describing the way in which the configuration parameters
are used. About LRU etc.
<h1 id=reading_data>Reading Data</h1>
<p>
In order to return data from the database to the user, for example as
the results of a SELECT query, SQLite must at some point read data
from the database file. Usually, data is read from the database file in
aligned blocks of <i>page-size</i> bytes. The exception is when the
database file header fields are being inspected, before the
<i>page-size</i> used by the database can be known.
<p>
With two exceptions, a <i>database connection</i> must have an open
transaction (either a <i>read-only transaction</i> or a
<i>read/write transaction</i>) on the database before data may be
read from the database file.
<p>
The two exceptions are:
<ul>
<li> When an attempt is made to read the 100 byte <i>database file
header</i> immediately after opening the <i>database connection</i>
(see section <cite>open_new_connection</cite>). When this occurs
no lock is held on the database file.
<li> Data read while in the process of opening a read-only transaction
(see section <cite>open_read_only_trans</cite>). These read
operations occur after a <i>shared lock</i> is held on the database
file.
</ul>
<p>
Once a transaction has been opened, reading data from a database
connection is a simple operation. Using the xRead() method of the
file-handle open on the database file, the required database file
pages are read one at a time. SQLite never reads partial pages and
always uses a single call to xRead() for each required page.
<p>
After reading the data for a database page, SQLite stores the raw
page of data in the <i>page cache</i>. Each time a page of data is
required by the upper layers, the <i>page cache</i> is queried
to see if it contains a copy of the required page stored by
the current <i>database connection</i>. If such an entry can be
found, then the required data is read from the <i>page cache</i> instead
of the database file. Only a connection with an open transaction
transaction (either a <i>read-only transaction</i> or a
<i>read/write transaction</i>) on the database may read data from the
<i>page cache</i>. In this sense reading from the <i>page cache</i> is no
different to reading from the <i>database file</i>.
<p>
Refer to section <cite>page_cache_algorithms</cite> for a description
of exactly how and for how long page data is stored in the
<i>page cache</i>.
REQ H35010
REQ H35020
REQ H35420
<h2 id=open_read_only_trans>Opening a Read-Only Transaction</h2>
<p>
Before data may be read from a <i>database file</i> or queried from
the <i>page cache</i>, a <i>read-only transaction</i> must be
successfully opened by the associated database connection (this is true
even if the connection will eventually write to the database, as a
<i>read/write transaction</i> may only be opened by upgrading from a
<i>read-only transaction</i>). This section describes the procedure
for opening a <i>read-only transaction</i>.
<p>
The key element of a <i>read-only transaction</i> is that the
file-handle open on the database file obtains and holds a
<i>shared-lock</i> on the database file. Because a connection requires
an <i>exclusive-lock</i> before it may actually modify the contents
of the database file, and by definition while one connection is holding
a <i>shared-lock</i> no other connection may hold an
<i>exclusive-lock</i>, holding a <i>shared-lock</i> guarantees that
no other process may modify the database file while the <i>read-only
transaction</i> remains open. This ensures that <i>read-only
transactions</i> are sufficiently isolated from the transactions of
other database users (see section <cite>overview</cite>).
<p>Obtaining the <i>shared lock</i> itself on the database file is quite
simple, SQLite just calls the xLock() method of the database file
handle. Some of the other processes that take place as part of
opening the <i>read-only transaction</i> are quite complex. The
steps that SQLite is required to take to open a <i>read-only
transaction</i>, in the order in which they must occur, is as follows:
<ol>
<li>A <i>shared-lock</i> is obtained on the database file.
<li>The connection checks if a <i>hot journal file</i> exists in the
file-system. If one does, then it is rolled back before continuing.
<li>The connection checks if the data in the <i>page cache</i> may
still be trusted. If not, all page cache data is discarded.
<li>If the file-size is not zero bytes and the page cache does not
contain valid data for the first page of the database, then the
data for the first page must be read from the database.
</ol>
<p>
Of course, an error may occur while attempting any of the 4 steps
enumerated above. If this happens, then the <i>shared-lock</i> is
released (if it was obtained) and an error returned to the user.
Step 2 of the procedure above is described in more detail in section
<cite>hot_journal_detection</cite>. Section <cite>cache_validation</cite>
describes the process identified by step 3 above. Further detail
on step 4 may be found in section <cite>read_page_one</cite>.
REQ H35100
REQ H35110
<p>
The most common reason an attempt to obtain a <i>shared-lock</i> may
fail is that some other connection is holding an <i>exclusive</i> or
<i>pending lock</i>. However it may also fail because some other
error (e.g. an IO or comms related error) occurs within the call to the
xLock() method.
REQ H35030
REQ H35120
<p>
Section <cite>hot_journal_detection</cite> contains a description of
and requirements governing the detection of a hot-journal file referred
to in the above requirements.
REQ H35040
<p>
The <i>cache validation</i> process is described in detail in section
<cite>cache_validation</cite>
REQ H35050
<p>
The numbered list above notes that the data for the first page of the
database file, if it exists and is not already loaded into the <i>page
cache</i>, must be read from the database file before the <i>read-only
transaction</i> may be considered opened. This is handled by
requirement H35240.
<h3 id=hot_journal_detection>Hot Journal Detection</h3>
<p>
This section describes the procedure that SQLite uses to detect a
<i>hot journal file</i>. If a <i>hot journal file</i> is detected,
this indicates that at some point the process of writing a
transaction to the database was interrupted and a recovery operation
(<i>hot journal rollback</i>) needs to take place. This section does
not describe the process of <i>hot journal rollback</i> (see section
<cite>hot_journal_rollback</cite>) or the processes by which a
<i>hot journal file</i> may be created (see section
<cite>writing_data</cite>).
<p>
The procedure used to detect a <i>hot-journal file</i> is quite
complex. The following steps take place:
<ol class=spacedlist>
<li>Using the VFS xAccess() method, SQLite queries the file-system
to see if the journal file associated with the database exists.
If it does not, then there is no hot-journal file.
<li>By invoking the xCheckReservedLock() method of the file-handle
opened on the database file, SQLite checks if some other connection
holds a <i>reserved lock</i> or greater. If some other connection
does hold a <i>reserved lock</i>, this indicates that the other
connection is midway through a <i>read/write transaction</i> (see
section <cite>writing_data</cite>). In this case the
<i>journal file</i> is not a <i>hot-journal</i> and must not be
rolled back.
<li>Using the xFileSize() method of the file-handle opened
on the database file, SQLite checks if the database file is
0 bytes in size. If it is, the journal file is not considered
to be a <i>hot journal</i> file. Instead of rolling back the
journal file, in this case it is deleted from the file-system
by calling the VFS xDelete() method. <span class=todo>Technically,
there is a race condition here. This step should be moved to
after the exclusive lock is held.</span>
<li>An attempt is made to upgrade to an <i>exclusive lock</i> on the
database file. If the attempt fails, then all locks, including
the recently obtained <i>shared lock</i> are dropped. The attempt
to open a <i>read-only transaction</i> has failed. This occurs
when some other connection is also attempting to open a
<i>read-only transaction</i> and the attempt to gain the
<i>exclusive lock</i> fails because the other connection is also
holding a <i>shared lock</i>. It is left to the other connection
to roll back the <i>hot journal</i>.
<div style="margin-top:0.5em"></div>
It is important that the file-handle lock is upgraded
directly from <i>shared</i> to <i>exclusive</i> in this case,
instead of first upgrading to <i>reserved</i> or </i>pending</i>
locks as is required when obtaining an <i>exclusive lock</i> to
write to the database file (section <cite>writing_data</cite>).
If SQLite were to first upgrade to a <i>reserved</i> or
<i>pending</i> lock in this scenario, then a second process also
trying to open a <i>read-transaction</i> on the database file might
detect the <i>reserved</i> lock in step 2 of this process,
conclude that there was no <i>hot journal</i>, and commence
reading data from the <i>database file</i>.
<li>The xAccess() method is invoked again to detect if the journal
file is still in the file system. If it is, then it is a
hot-journal file and SQLite tries to roll it back (see section
<cite>rollback</cite>).
</ol>
<p class=todo> Master journal file pointers?
<p>
The following requirements describe step 1 of the above procedure in
more detail.
REQ H35140
REQ H35510
REQ H35150
<p>
The following requirements describe step 2 of the above procedure in
more detail.
REQ H35160
REQ H35520
REQ H35170
<p>
The following requirements describe step 3 of the above procedure in
more detail.
REQ H35440
REQ H35530
REQ H35450
REQ H35540
REQ H35460
REQ H35550
<p>
The following requirements describe step 4 of the above procedure in
more detail.
REQ H35470
REQ H35480
<p>
Finally, the following requirements describe step 5 of the above
procedure in more detail.
REQ H35490
REQ H35560
REQ H35570
REQ H35500
<h3 id=cache_validation>Cache Validation</h3>
<p>
When a <i>database connection</i> opens a <i>read transaction</i>, the
<i>page cache</i> may already contain data associated with the
<i>database connection</i>. However, if another process has modified
the database file since the cached pages were loaded it is possible that
the cached data is invalid.
<p>
SQLite determines whether or not the <i>page cache</i> entries belonging
to the <i>database connection</i> are valid or not using the <i>file
change counter</i>, a field in the <i>database file header</i>. The
<i>file change counter</i> is a 4-byte big-endian integer field stored
starting at byte offset 24 of the <i>database file header</i>. Before the
conclusion of a <i>read/write transaction</i> that modifies the contents
of the database file in any way (see section <cite>writing_data</cite>),
the value stored in the <i>file change counter</i> is incremented. When
a <i>database connection</i> unlocks the database file, it stores the
current value of the <i>file change counter</i>. Later, while opening a
new <i>read-only transaction</i>, SQLite checks the value of the <i>file
change counter</i> stored in the database file. If the value has not
changed since the database file was unlocked, then the <i>page cache</i>
entries can be trusted. If the value has changed, then the <i>page
cache</i> entries cannot be trusted and all entries associated with
the current <i>database connection</i> are discarded.
REQ H35180
REQ H35190
<p class=todo>
Why a 16 byte block? Why not 4? (something to do with encrypted
databases).
REQ H35200
<p>
Requirement H35050 (section <cite>open_read_only_trans</cite>)
specifies the action SQLite is required to take upon determining that
the cache contents are invalid.
<h3 id=read_page_one>Page 1 and the Expected Page Size</h3>
<p>
As the last step in opening a <i>read transaction</i> on a database
file that is more than 0 bytes in size, SQLite is required to load
data for page 1 of the database into the <i>page cache</i>, if it is
not already there. This is slightly more complicated than it seems,
as the database <i>page-size</i> is no known at this point.
<p>
Even though the database <i>page-size</i> cannot be known for sure,
SQLite is usually able to guess correctly by assuming it to be equal to
the connections <i>expected page size</i>. The <i>expected page size</i>
is the value of the <i>page-size</i> field read from the
<i>database file header</i> while opening the database connection
(see section <cite>open_new_connection</cite>), or the <i>page-size</i>
of the database file when the most <i>read transaction</i> was concluded.
REQ H35210
REQ H35220
REQ H35230
REQ H35240
<h2>Reading Database Data</h2>
<p class=todo>
Add something about checking the page-cache first etc.
<h2>Ending a Read-only Transaction</h2>
<p>
To end a <i>read-only transaction</i>, SQLite simply relinquishes the
<i>shared lock</i> on the file-handle open on the database file. No
other action is required.
REQ H35130
<p>
See also requirements H35180 and H35210 above.
<h1 id=writing_data>Writing Data</h1>
<p>
Using DDL or DML SQL statements, SQLite users may modify the contents and
size of a database file. Exactly how changes to the logical database are
translated to modifications to the database file is described in
<cite>ff_sqlitert_requirements</cite>. From the point of view of the
sub-systems described in this document, each DDL or DML statement executed
results in the contents of zero or more database file pages being
overwritten with new data. A DDL or DML statement may also append or
truncate one or more pages to or from the end of the database file. One
or more DDL and/or DML statements are grouped together to make up a
single <i>write transaction</i>. A <i>write transaction</i> is required
to have the special properties described in section <cite>overview</cite>;
a <i>write transaction</i> must be isolated, durable and atomic.
<p>
SQLite accomplishes these goals using the following techniques:
<ul>
<li><p>
To ensure that <i>write transactions</i> are <b>isolated</b>, before
beginning to modify the contents of the database file to reflect the
results of a <i>write transaction</i>, SQLite obtains an <i>exclusive
lock</i> on the <i>database file</i>. The lock is not relinquished
until the <i>write transaction</i> is concluded. Because reading from
the <i>database file</i> requires a <i>shared lock</i> (see section
<cite>reading_data</cite>) and holding an <i>exclusive
lock</i> guarantees that no other <i>database connection</i> is holding
or can obtain a <i>shared lock</i>, this ensures that no other
connection may read data from the <i>database file</i> at a point when
a <i>write transaction</i> has been partially applied.
<li><p>Ensuring that <i>write transactions</i> are <b>atomic</b> is the most
complex task required of the system. In this case, <i>atomic</i> means
that even if a system failure occurs, an attempt to commit a <i>write
transaction</i> to the database file either results in all changes
that are a part of the transaction being successfully applied to the
database file, or none of the changes are successfully applied. There
is no chance that a subset of the changes only are applied. Hence from
the point of view of an external observer, the <i>write transaction</i>
appears to be an atomic event.
<p>
Of course, it is usually not possible to atomically apply all the
changes required by a <i>write transaction</i> to a database file
within the file-system. For example, if a <i>write transaction</i>
requires ten pages of a database file to be modified, and a power
outage causes a system failure after sqlite has modified only five
pages, then the database file will almost certainly be in an
inconsistent state following system recovery.
<p>
SQLite solves this problem by using a <i>journal file</i>. In almost
all cases, before the <i>database file</i> is modified in any way,
SQLite stores sufficient information in the <i>journal file</i> to
allow the original the database file to be reconstructed if a system
failure occurs while the database file is being updated to reflect
the modifications made by the <i>write transaction</i>. Each time
SQLite opens a database file, it checks if such a system failure has
occurred and, if so,
reconstructs the database file based on the contents
of the journal file. The procedure used to detect whether or not this
process, coined <i>hot journal rollback</i>, is required is described
in section <cite>hot_journal_detection</cite>. <i>Hot journal rollback
</i> itself is described in section <cite>hot_journal_rollback</cite>.
<p>
The same technique ensures that an SQLite database file cannot be
corrupted by a system failure that occurs at an inopportune moment.
If a system failure does occur before SQLite has had a chance to
execute sufficient <i>sync file</i> operations to ensure that the
changes that make up a <i>write transaction</i> have made it safely
to persistent storage, then the <i>journal file</i> will be used
to restore the database to a known good state following system
recovery.
<li><p>
So that <i>write transactions</i> are <b>durable</b> in the face of
a system failure, SQLite executes a <i>sync file</i> operation on the
database file before concluding the <i>write transaction</i>
</ul>
<p>
The <i>page cache</i> is used to buffer modifications to the database
file image before they are written to the <i>database file</i>. When
the contents of a page is required to be modified as the results of
an operation within a <i>write transaction</i>, the modified copy is
stored in the <i>page cache</i>. Similarly, if new pages are appended
to the end of a database file, they are added to the <i>page cache</i>
instead of being immediately written to the database file within the
file-system.
<p>
Ideally, all changes for an entire write transaction are buffered in
the page cache until the end of the transaction. When the user commits
the transaction, all changes are applied to the database file in the
most efficient way possible, taking into account the assumptions
enumerated in section <cite>fs_performance</cite>. Unfortunately, since
main-memory is a limited resource, this is not always possible for
large transactions. In this case changes are buffered in the <i>page
cache</i> until some internal condition or limit is reached,
then written out to the database file in order to free resources
as they are required. Section <cite>page_cache_algorithms</cite>
describes the circumstances under which changes are flushed through
to the database file mid-transaction to free <i>page cache</i> resources.
<p>
Even if an application or system failure does not occur while a
<i>write transaction</i> is in progress, a rollback operation to restore
the database file and <i>page cache</i> to the state that it was in before
the transaction started may be required. This may occur if the user
explicitly requests transaction rollback (by issuing a "ROLLBACK" command),
or automatically, as a result of encountering an SQL constraint (see
<cite>sql_sqlitert_requirements</cite>). For this reason, the original page
content is stored in the <i>journal file</i> before the page is even
modified within the <i>page cache</i>.
<p class=todo>
Introduce the following sub-sections.
<h2 id=journal_file_format>Journal File Format</h2>
<p>
This section describes the format used by an SQLite <i>journal file</i>.
<p>
A journal file consists of one or more <i>journal headers</i>, zero
or more <i>journal records</i> and optionally a <i>master journal
pointer</i>. Each journal file always begins with a
<i>journal header</i>, followed by zero or more <i>journal records</i>.
Following this may be a second <i>journal header</i> followed by a
second set of zero or more <i>journal records</i> and so on. There
is no limit to the number of <i>journal headers</i> a journal file
may contain. Following the <i>journal headers</i> and their accompanying
sets of <i>journal records</i> may be the optional <i>master journal
pointer</i>. Or, the file may simply end following the final <i>journal
record</i>.
<p>
This section only describes the format of the journal file and the
various objects that make it up. But because a journal file may be
read by an SQLite process following recovery from a system failure
(<i>hot journal rollback</i>, see section
<cite>hot_journal_rollback</cite>) it is also important to describe
the way the file is created and populated within the file-system
using a combination of <i>write file</i>, <i>sync file</i> and
<i>truncate file</i> operations. These are described in section
<cite>write_transactions</cite>.
<h3 id=journal_header_format>Journal Header Format</h3>
<p>
A <i>journal header</i> is <i>sector-size</i> bytes in size, where <i>
sector-size</i> is the value returned by the xSectorSize method of
the file handle opened on the database file. Only the first 28 bytes
of the <i>journal header</i> are used, the remainder may contain garbage
data. The first 28 bytes of each <i>journal header</i> consists of an
eight byte block set to a well-known value, followed by five big-endian
32-bit unsigned integer fields.
<center><img src="images/fileformat/journal_header.gif">
<p><i>Figure <span class=fig id=figure_journal_header></span> - Journal Header Format</i>
</center>
<p>
Figure <cite>figure_journal_header</cite> graphically depicts the layout
of a <i>journal header</i>. The individual fields are described in
the following table. The offsets in the 'byte offset' column of the
table are relative to the start of the <i>journal header</i>.
<table class=striped>
<tr><th>Byte offset<th>Size in bytes<th width=100%>Description
<tr><td>0<td>8<td>The <b>journal magic</b> field always contains a
well-known 8-byte string value used to identify SQLite
journal files. The well-known sequence of byte values
is:
<pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre>
<tr><td>8<td>4<td>This field, the <b>record count</b>, is set to the
number of <i>journal records</i> that follow this
<i>journal header</i> in the <i>journal file</i>.
<tr><td>12<td>4<td>The <b>checksum initializer</b> field is set to a
pseudo-random value. It is used as part of the
algorithm to calculate the checksum for all <i>journal
records</i> that follow this <i>journal header</i>.
<tr><td>16<td>4<td>This field, the <b>database page count</b>, is set
to the number of pages that the <i>database file</i>
contained before any modifications associated with
<i>write transaction</i> are applied.
<tr><td>20<td>4<td>This field, the <b>sector size</b>, is set to the
<i>sector size</i> of the device on which the
<i>journal file</i> was created, in bytes. This value
is required when reading the journal file to determine
the size of each <i>journal header</i>.
<tr><td>24<td>4<td>The <b>page size</b> field contains the database page
size used by the corresponding <i>database file</i>
when the <i>journal file</i> was created, in bytes.
</table>
<p>
All <i>journal headers</i> are positioned in the file so that they
start at a <i>sector size</i> aligned offset. To achieve this, unused
space may be left between the start of the second and subsequent
<i>journal headers</i> and the end of the <i>journal records</i>
associated with the previous header.
<h3 id=journal_record_format>Journal Record Format</h3>
<p>
Each <i>journal record</i> contains the original data for a database page
modified by the <i>write transaction</i>. If a rollback is required, then
this data may be used to restore the contents of the database page to the
state it was in before the <i>write transaction</i> was started.
<center><img src="images/fileformat/journal_record.gif">
<p><i>Figure <span class=fig id=figure_journal_record></span> - Journal Record Format</i>
</center>
<p>
A <i>journal record</i>, depicted graphically by figure
<cite>figure_journal_record</cite>, contains three fields, as described
in the following table. Byte offsets are relative to the start of the
<i>journal record</i>.
<table class=striped>
<tr><th>Byte offset<th>Size in bytes<th width=100%>Description
<tr><td>0<td>4<td>The page number of the database page associated with
this <i>journal record</i>, stored as a 4 byte
big-endian unsigned integer.
<tr><td>4<td><i>page-size<td>
This field contains the original data for the page,
exactly as it appeared in the database file before the
<i>write transaction</i> began.
<tr><td style="white-space: nowrap">4 + <i>page-size</i><td>4<td>
This field contains a checksum value, calculated based
on the contents of the journaled database page data
(the previous field) and the values stored in the
<i>checksum initializer</i> field of the preceding
<i>journal header</i>.
</table>
<p>
The set of <i>journal records</i> that follow a <i>journal header</i>
in a <i>journal file</i> are packed tightly together. There are no
alignment requirements for <i>journal records</i> as there are for
<i>journal headers</i>.
<h3>Master Journal Pointer</h3>
<p>
To support <i>atomic</i> transactions that modify more than one
database file, SQLite sometimes includes a <i>master journal pointer</i>
record in a <i>journal file</i>. Multiple file transactions are
described in section <cite>multifile_transactions</cite>. A <i>
master journal pointer</i> contains the name of a <i>master journal-file
</i> along with a check-sum and some well known values that allow
the <i>master journal pointer</i> to be recognized as such when
the <i>journal file</i> is read during a rollback operation (section
<cite>rollback</cite>).
<p>
As is the case for a <i>journal header</i>, the start of a <i>master
journal pointer</i> is always positioned at a <i>sector size</i>
aligned offset. If the <i>journal record</i> or <i>journal header</i>
that appears immediately before the <i>master journal pointer</i> does
not end at an aligned offset, then unused space is left between the
end of the <i>journal record</i> or <i>journal header</i> and the start
of the <i>master journal pointer</i>.
<center><img src="images/fileformat/master_journal_ptr.gif">
<p><i>Figure <span class=fig id=figure_master_journal_ptr></span> - Master Journal Pointer Format</i>
</center>
<p>
A <i>master journal pointer</i>, depicted graphically by figure
<cite>figure_master_journal_ptr</cite>, contains five fields, as
described in the following table. Byte offsets are relative to the
start of the <i>master journal pointer</i>.
<table class=striped>
<tr><th>Byte offset<th>Size in bytes<th width=100%>Description
<tr><td>0<td>4<td>This field, the <b>locking page number</b>, is always
set to the page number of the database <i>locking page</i>
stored as a 4-byte big-endian integer. The <i>locking page</i>
is the page that begins at byte offset 2<super>30</super> of the
database file. Even if the database file is large enough to
contain the <i>locking page</i>, the <i>locking page</i> is
never used to store any data and so the first four bytes of of a
valid <i>journal record</i> will never contain this value. For
further description of the <i>locking page</i>, refer to
<cite>ff_sqlitert_requirements</cite>.
<tr><td>4<td><i>name-length</i><td>
The <b>master journal name</b> field contains the name of the
master journal file, encoded as a utf-8 string. There is no
nul-terminator appended to the string.
<tr><td>4 + <i>name-length</i><td><i>4<td>
The <b>name-length</b> field contains the length of the
previous field in bytes, formatted as a 4-byte big-endian
unsigned integer.
<tr><td>8 + <i>name-length</i><td><i>4<td>
The <b>checksum</b> field contains a checksum value stored as
a 4-byte big-endian signed integer. The checksum value is
calculated as the sum of the bytes that make up the <i>
master journal name</i> field, interpreting each byte as
an 8-bit signed integer.
<tr><td style="white-space: nowrap">12 + <i>name-length</i><td><i>8<td>
Finally, the <b>journal magic</b> field always contains a
well-known 8-byte string value; the same value stored in the
first 8 bytes of a <i>journal header</i>. The well-known
sequence of bytes is:
<pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre>
</table>
<h2 id=write_transactions>Write Transactions</h2>
<p>
This section describes the progression of an SQLite <i>write
transaction</i>. From the point of view of the systems described in
this document, most <i>write transactions</i> consist of three steps:
<ol>
<li><p>The <i>write transaction</i> is opened. This process is described
in section <cite>opening_a_write_transaction</cite>.
<li><p>The end-user executes DML or DDL SQL statements that require the
structure of the database file of the database file to be modified.
These modifications may be any combination of operations to
<ul><li>modify the content of an existing database page,
<li>append a new database page to the database file image, or
<li>truncate (discard) a database page from the end of the
database file.
</ul>
These operations are described in detail in section
<cite>modifying_appending_truncating</cite>. How user DDL or DML
SQL statements are mapped to combinations of these three operations
is described in <cite>ff_sqlitert_requirements</cite>.
<li><p>The <i>write transaction</i> is concluded and the changes made
permanently committed to the database. The process required to
commit a transaction is described in section
<cite>committing_a_transaction</cite>.
</ol>
<p>
As an alternative to step 3 above, the transaction may be rolled back.
Transaction rollback is described in section <cite>rollback</cite>.
Finally, it is also important to remember that a <i>write transaction</i>
may be interrupted by a <i>system failure</i> at any point. In this
case, the contents of the file-system (the <i>database file</i> and
<i>journal file</i>) must be left in such a state so as to enable
the <i>database file</i> to be restored to the state it was in before
the interrupted <i>write transaction</i> was started. This is known
as <i>hot journal rollback</i>, and is described in section
<cite>hot_journal_rollback</cite>. Section
<cite>fs_assumption_details</cite> describes the assumptions made
regarding the effects of a <i>system failure</i> on the file-system
contents following recovery.
<h3 id=opening_a_write_transaction>Beginning a Write Transaction</h3>
<p>
Before any database pages may be modified within the <i>page cache</i>,
the <i>database connection</i> must open a <i>write transaction</i>.
Opening a <i>write transaction</i> requires that the <i>database
connection</i> obtains a <i>reserved lock</i> (or greater) on the
<i>database file</i>. Because obtaining a <i>reserved lock</i> on
a <i>database file</i> guarantees that no other <i>database
connection</i> may hold or obtain a <i>reserved lock</i> or greater,
it follows that no other <i>database connection</i> may have an
open <i>write transaction</i>.
<p>
A <i>reserved lock</i> on the <i>database file</i> may be thought of
as an exclusive lock on the <i>journal file</i>. No
<i>database connection</i> may read from or write to a <i>journal
file</i> without a <i>reserved</i> or greater lock on the corresponding
<i>database file</i>.
<p>
Before opening a <i>write transaction</i>, a <i>database connection</i>
must have an open <i>read transaction</i>, opened via the procedure
described in section <cite>open_read_only_trans</cite>. This ensures
that there is no <i>hot-journal file</i> that needs to be rolled back
and that any data stored in the <i>page cache</i> can be trusted.
<p>
Once a <i>read transaction</i> has been opened, upgrading to a
<i>write transaction</i> is a two step process, as follows:
<ol>
<li>A <i>reserved lock</i> is obtained on the <i>database file</i>.
<li>The <i>journal file</i> is opened and created if necessary (using
the VFS xOpen method), and a <i>journal file header</i> written
to the start of it using a single call to the file handles xWrite
method.
</ol>
<p>
Requirements describing step 1 of the above procedure in detail:
REQ H35350
REQ H35360
REQ H35580
<p>
Requirements describing step 2 of the above procedure in detail:
REQ H35370
REQ H35380
<h4 id=writing_journal_header>Writing a Journal Header</h4>
<p>
Requirements describing how a <i>journal header</i> is appended to
a journal file:
REQ H35680
REQ H35690
REQ H35700
REQ H35710
REQ H35720
REQ H35730
REQ H35740
<h3 id=modifying_appending_truncating>
Modifying, Adding or Truncating a Database Page
</h3>
<p>
When the end-user executes a DML or DDL SQL statement to modify the
database schema or content, SQLite is required to update the database
file image to reflect the new database state. This involves modifying
the content of, appending or truncating one of more database file
pages. Instead of modifying the database file directly using the VFS
interface, changes are first buffered within the <i>page cache</i>.
<p>
Before modifying a database page within the <i>page cache</i> that
may need to be restored by a rollback operation, the page must be
<i>journalled</i>. <i>Journalling a page</i> is the process of copying
that pages original data into the journal file so that it can be
recovered if the <i>write transaction</i> is rolled back. The process
of journalling a page is described in section
<cite>journalling_a_page</cite>.
REQ H35590
REQ H35600
<p>
When a new database page is appended to a database file, there is
no requirement to add a record to the <i>journal file</i>. If a
rollback is required the database file will simply be truncated back
to its original size based on the value stored at byte offset 12
of the <i>journal file</i>.
REQ H35610
<p>
If required to truncate a database page from the end of the database
file, the associated <i>page cache entry</i> is discarded. The adjusted
size of the database file is stored internally. The database file
is not actually truncated until the current <i>write transaction</i>
is committed (see section <cite>committing_a_transaction</cite>).
REQ H35620
REQ H35630
<h4 id=journalling_a_page>Journalling a Database Page</h4>
<p>
A page is journalled by adding a <i>journal record</i> to the <i>
journal file</i>. The format of a <i>journal record</i> is described
in section <cite>journal_record_format</cite>.
REQ H35270
REQ H35280
REQ H35290
<p>
The checksum value written to the <i>journal file</i> immediately after
the page data (requirement H35290), is a function of both the page
data and the <i>checksum initializer</i> field stored in the
<i>journal header</i> (see section <cite>journal_header_format</cite>).
Specifically, it is the sum of the <i>checksum initializer</i> and
the value of every 200th byte of page data interpreted as an 8-bit
unsigned integer, starting with the (<i>page-size</i> % 200)'th
byte of page data. For example, if the <i>page-size</i> is 1024 bytes,
then a checksum is calculated by adding the values of the bytes at
offsets 23, 223, 423, 623, 823 and 1023 (the last byte of the page)
together with the value of the <i>checksum initializer</i>.
REQ H35300
<p>
The '%' character is used in requirement H35300 to represent the
modulo operator, just as it is in programming languages such as C, Java
and Javascript.
<h3 id=syncing_journal_file>Syncing the Journal File</h3>
<p>
Even after the original data of a database page has been written into
the journal file using calls to the journal file file-handle xWrite
method (section <cite>journalling_a_page</cite>), it is still not
safe to write to the page within the database file. This is because
in the event of a system failure the data written to the journal file
may still be corrupted (see section <cite>fs_characteristics</cite>).
Before the page can be updated within the database itself, the
following procedure takes place:
<ol>
<li> The xSync method of the file-handle opened on the journal file
is called. This operation ensures that all <i>journal records</i>
in the journal file have been written to persistent storage, and
that they will not become corrupted as a result of a subsequent
system failure.
<li> The <i>journal record count</i> field (see section
<cite>journal_header_format</cite>) of the most recently written
journal header in the journal file is updated to contain the
number of <i>journal records</i> added to the journal file since
the header was written.
<li> The xSync method is called again, to ensure that the update to
the <i>journal record count</i> has been committed to persistent
storage.
</ol>
<p>
If all three of the steps enumerated above are executed successfully,
then it is safe to modify the content of the <i>journalled</i>
database pages within the database file itself. The combination of
the three steps above is referred to as <i>syncing the journal file</i>.
REQ H35750
REQ H35760
REQ H35770
<h3 id=upgrading_to_exclusive_lock>Upgrading to an Exclusive Lock</h3>
<p>
Before the content of a page modified within the <i>page cache</i> may
be written to the database file, an <i>exclusive lock</i> must be held
on the database file. The purpose of this lock is to prevent another
connection from reading from the database file while the first
connection is midway through writing to it. Whether the reason for
writing to the database file is because a transaction is being committed,
or to free up space within the <i>page cache</i>, upgrading to an
<i>exclusive lock</i> always occurs immediately after
<i>syncing the journal file</i>.
REQ H35780
REQ H35790
<p class=todo>
What happens if the exclusive lock cannot be obtained? It is not
possible for the attempt to upgrade from a reserved to a pending
lock to fail.
<h3 id=committing_a_transaction>Committing a Transaction</h3>
<p>
Committing a <i>write transaction</i> is the final step in updating the
database file. Committing a transaction is a seven step process,
summarized as follows:
<ol>
<li><p>
The database file header <i>change counter</i> field is incremented.
The <i>change counter</i>, described in
<cite>ff_sqlitert_requirements</cite>, is used by the <i>cache
validation</i> procedure described in section
<cite>cache_validation</cite>.
<li><p>
The <i>journal file</i> is synced. The steps required to <i>sync the
journal file</i> are described in section
<cite>syncing_journal_file</cite>.
<li><p>
Upgrade to an <i>exclusive lock</i> on the database file, if an
<i>exclusive lock</i> is not already held. Upgrading to an
<i>exclusive lock</i> is described in section
<cite>upgrading_to_exclusive_lock</cite>.
<li><p>
Copy the contents of all <i>dirty pages</i> stored in the <i>page
cache</i> into the database file. The set of dirty pages are written
to the database file in page number order in order to improve
performance (see the assumptions in section <cite>fs_performance</cite>
for details).
<li><p>
The database file is synced to ensure that all updates are stored
safely on the persistent media.
<li><p>
The file-handle open on the <i>journal file</i> is closed and the
journal file itself deleted. At this point the <i>write transaction</i>
transaction has been irrevocably committed.
<li><p>
The database file is unlocked.
</ol>
<p class=todo>
Expand on and explain the above a bit.
<p>
The following requirements describe the steps enumerated above in more
detail.
REQ H35800
<p>
The <i>change counter</i> is a 4-byte big-endian integer field stored
at byte offset 24 of the <i>database file</i>. The modification to page 1
required by H35800 is made using the process described in section
<cite>modifying_appending_truncating</cite>. If page 1 has not already
been journalled as a part of the current write-transaction, then
incrementing the <i>change counter</i> may require that page 1 be
journalled. In all cases the <i>page cache entry</i> corresponding to
page 1 becomes a <i>dirty page</i> as part of incrementing the <i>change
counter</i> value.
REQ H35810
REQ H35820
REQ H35830
REQ H35840
REQ H35850
REQ H35860
<p class=todo>
Is the shared lock held after committing a <i>write transaction</i>?
<h3>Purging a Dirty Page</h3>
<p>
Usually, no data is actually written to the database file until the
user commits the active <i>write transaction</i>. The exception is
if a single <i>write transaction</i> contains too many modifications
to be stored in the <i>page cache</i>. In this case, some of the
database file modifications stored in the <i>page cache</i> must be
applied to the database file before the transaction is committed so
that the associated <i>page cache entries</i> can be purged from the
page cache to free memory. Exactly when this condition is reached and
dirty pages must be purged is described in section
<cite>page_cache_algorithms</cite>.
<p>
Before the contents of the <i>page cache entry</i> can be written into
the database file, the <i>page cache entry</i> must meet the criteria
for a <i>writable dirty page</i>, as defined in section
<cite>page_cache_algorithms</cite>. If the dirty page selected by the
algorithms in section <cite>page_cache_algorithms</cite> for purging,
SQLite is required to <i>sync the journal file</i>. Immediately after
the journal file is synced, all dirty pages associated with the
<i>database connection</i> are classified as <i>writable dirty pages</i>.
REQ H35640
REQ H35660
<p>
Appending a new <i>journal header</i> to the journal file is described
in section <cite>writing_journal_header</cite>.
<p>
Once the dirty page being purged is writable, it is simply written
into the database file.
REQ H35670
<h2 id="multifile_transactions">Multi-File Transactions</h2>
<h2 id="statement_transactions">Statement Transactions</h2>
<h1 id=rollback>Rollback</h1>
<h2 id=hot_journal_rollback>Hot Journal Rollback</h2>
<h2>Transaction Rollback</h2>
<h2>Statement Rollback</h2>
<h1>References</h1>
<table id="refs" style="width:auto; margin: 1em 5ex">
<tr><td style="width:5ex" id="capi_sqlitert_requirements">[1]<td>
C API Requirements Document.
<tr><td style="width:5ex" id="sql_sqlitert_requirements">[2]<td>
SQL Requirements Document.
<tr><td style="width:5ex" id="ff_sqlitert_requirements">[3]<td>
File Format Requirements Document.
</table>
}]</tcl>