SQLite4  Check-in [ec9a805164]

<title>LSM Design Overview</title>
<nowiki>




<div id=start_of_toc></div>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#summary style=text-decoration:none>1. Summary </a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#data_structures style=text-decoration:none>2. Data Structures </a><br>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#locks style=text-decoration:none>2.1. Locks</a><br>


&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#database_file style=text-decoration:none>2.2. Database file</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#sorted_runs style=text-decoration:none>2.2.1. Sorted Runs</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#levels style=text-decoration:none>2.2.2. Levels</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#snapshots style=text-decoration:none>2.2.3. Snapshots</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#in-memory_tree style=text-decoration:none>2.3. In-Memory Tree</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#memory_allocation style=text-decoration:none>2.3.1. Memory Allocation</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#header_fields style=text-decoration:none>2.3.2. Header Fields</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#other_shared-memory_fields style=text-decoration:none>2.4. Other Shared-Memory Fields</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#log_file style=text-decoration:none>2.5. Log file</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#database_recovery_and_shutdown style=text-decoration:none>3. Database Recovery and Shutdown</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#read-write_clients style=text-decoration:none>3.1. Read-write clients</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#database_operations style=text-decoration:none>4. Database Operations </a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#reading style=text-decoration:none>4.1. Reading</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#writing style=text-decoration:none>4.2. Writing</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#flushing_the_in-memory_tree_to_disk style=text-decoration:none>4.2.1. Flushing the in-memory tree to disk</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#shared-memory_management style=text-decoration:none>4.2.2. Shared-memory management</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#log_file_management style=text-decoration:none>4.2.3. Log file management</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#working style=text-decoration:none>4.3. Working</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#free-block_list_management style=text-decoration:none>4.3.1. Free-block list management</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#checkpoint_operations style=text-decoration:none>4.4. Checkpoint Operations</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#scheduling_policies style=text-decoration:none>5. Scheduling Policies</a><br>

<div id=end_of_toc></div>

<h1 id=summary>1. Summary </h1>

The LSM embedded database software stores data in three distinct data
structures:

<p>
When an application writes to the database, the new data is written to the
in-memory tree. Once the in-memory tree has grown large enough, its contents
are written into the database file as a new sorted run. To reduce the number
of sorted runs in the database file, chronologically adjacent sorted runs 
may be merged together into a single run, either automatically or on demand.

<h1 id=locking>2. Locks and Locking Protocols</h1> <p>
Read/write (shared/exclusive) file locks are used to control concurrent 
access. LSM uses the following file-locks:



<table>
  <tr><td valign=top>DMS1
      <td><p style=margin-top:0>
          This locking byte is used to serialize all connection and
          disconnection operations performed by read-write database
          connections. An EXCLUSIVE lock is taken for the duration of all such
          operations.

          <p>Additionally, read-only connections take a SHARED lock on this
          locking byte while attempting to connect to a database. This ensures
          that a read-only connection does not attempt to connect to the
          database while a read-write clients connection or disconnection
          operation is ongoing.

  <tr><td valign=top>DMS2
      <td><p style=margin-top:0>
          Read-write connections hold a SHARED lock on this locking byte for
          as long as they are connected to the database.

  <tr><td valign=top>DMS3
      <td><p style=margin-top:0>
          Read-only connections hold a SHARED lock on this locking byte for
          as long as they are connected to the database.

  <tr><td valign=top>RWCLIENT(n)
      <td><p style=margin-top:0>
          There are a total of 16 RWCLIENT locking bytes. After a read-write
          client connects to the database it attempts to find a free RWCLIENT
          locking slot to take an EXCLUSIVE lock on. If it cannot find one,
          this is not an error. If it can, then the lock is held for as long 
          as the read-write client is connected to the database for.

          <p>The sole purpose of these locks is that they allow a read-only
          client to detect whether or not there exists at least one read-write
          client connected to the database. Of course if large numbers of 
          read-write clients connect and disconnect from the system in an
          inconvenient order the system may enter a state where there exists
          one or more connected read-write clients but none of them hold a
          RWCLIENT lock. This is not important - if a read-only client fails
          to detect that the system has read-write clients it may be less
          efficient, but will not malfunction.

  <tr><td valign=top>WRITER
      <td><p style=margin-top:0>
          A database client holds an EXCLUSIVE lock on this locking byte
          while writing data to the database. Outside of recovery, only clients
          holding this lock may modify the contents of the in-memory b-tree.
          Holding this lock is synonymous with having an open write transaction
          on the database.

  <tr><td valign=top>WORKER
      <td><p style=margin-top:0>
          A database client holds an EXCLUSIVE lock on this locking byte
          while performing database work (writing data into the body of the
          database file).

  <tr><td valign=top>CHECKPOINTER&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      <td><p style=margin-top:0>
          A database client holds an EXCLUSIVE lock on this locking byte
          while performing a checkpoint (syncing the database file and 
          writing to the database header).

  <tr><td valign=top>ROTRANS
      <td><p style=margin-top:0>
          A read-only database client holds a SHARED lock on this locking byte
          while reading from a non-live database system.

  <tr><td valign=top>READER(n)
      <td><p style=margin-top:0>
          There are a total of 6 READER locking bytes. Unless it is a read-only
          client reading from a non-live database, a client holds a SHARED lock
          on one of these while it has an open read transaction.  Each READER
          lock is associated with a pair of id values identifying the regions
          of the in-memory tree and database file that may be read by clients
          holding such SHARED locks.
</table>






<h1 id=data_structures>2. Data Structures </h1>












<h2 id=locks>2.1. Locks</h2>
<p>





Read/write (shared/exclusive) file locks are used to control concurrent 
access. LSM uses the following file-locks:





<ul>


  <li> <p>The <b>DMS1</b>, <b>DMS2</b> locking regions. These are used to

       implement the "dead-man-switch" mechanism copied from SQLite's WAL

       mode for safely connecting to and disconnecting from a database. 
       See "Database Recovery and Shutdown" below.


  <li> <p>Several (say 3) <b>READER</b> locking regions. Database clients 
       hold a SHARED lock one of the READER locking regions while reading the





       database. As in SQLite WAL mode, each reader lock is paired with a 
       value indicating the version of the database that the client process 




       is using. The value consists of two fields:








  <ul>
    <li> A 64-bit snapshot id. This identifies the version of the database file

         that the reader is accessing.

    <li> A 32-bit shared-memory chunk id. This identifies the version of the


         in-memory tree the reader is reading.


  </ul>

  <li> <p>The <b>WRITER</b> locking region. A database client holds an 
       EXCLUSIVE lock on this locking region while writing data to the 

       database. Outside of recovery, only clients holding this lock may
       modify the contents of the in-memory b-tree.













  <li> <p>The <b>WORKER</b> lock. A database client holds an EXCLUSIVE lock



       on this locking region while writing data into the body of the 


       database file.



  <li> <p>The <b>CHECKPOINTER</b> lock. A database client holds an EXCLUSIVE

       lock on this locking region while writing to the database file header.




</ul>






<p>
In the following sections, "the WRITER lock", refers to an exclusive lock
on the WRITER locking region. For example "holding the WRITER lock" is
equivalent to "holding an exclusive lock on the WRITER locking region".
Similar interpretations apply to "the WORKER lock" and "the CHECKPOINTER 
lock".

<h2 id=database_file>2.2. Database file</h2>

<p>
This section summarizes the contents of the database file informally. A 
detailed description is found in the header comments for source code files 
<a href="../src/lsm_file.c">lsm_file.c</a> (blocks, pages etc.), 
<a href="../src/lsm_sorted.c">lsm_sorted.c</a> (sorted run format) and 
<a href="../src/lsm_ckpt.c">lsm_ckpt.c</a> (database snapshot format). 

<p>
As with an SQLite database file, each page in the database may be addressed 
by its 32-bit page number. This means the maximum database size is roughly
(pgsz * 2^32) bytes. The first and last pages in each block are 4 bytes
smaller than the others. This is to make room for a single page-number.

<h3 id=sorted_runs>2.2.1. Sorted Runs</h3>

<p>
A single sorted run is spread across one or more database pages (each page
is a part of at most one sorted run). Given the page number of a page in a
sorted run the following statements are true:

<ul>

In other words, given the page numbers of the first and last pages of a 
sorted run and the page number of the root page for the embedded b-tree,
it is possible to traverse the entire run in either direction or query for
arbitrary values.

<p><span style="color:red"> TODO: Embedded pointers.  </span>

<h3 id=levels>2.2.2. Levels</h3>

<p>
Each sorted run is assigned to a "level". Normally, a level consists of a
single sorted run. However, a level may also consist of a set of sorted runs
being incrementally merged into a single run.

<p>

time for all entries.






<h3 id=snapshots>2.2.3. Snapshots</h3>

<p>
Each meta page may contain a database <b>snapshot</b>. A snapshot contains all 
the information required to interpret the remainder of the database file (the
sorted runs and free space). Specifically, it contains:

<ul>

       Recovery and Shutdown" below).
</ul>

<p>
A more detailed description is available in the header comments in
source code file <a href="../src/lsm_ckpt.c">lsm_ckpt.c</a>

<h2 id=in-memory_tree>2.3. In-Memory Tree</h2>

<p>
The in-memory tree is an append-only b-tree of order 4 (each node may have 
up to 4 children), which is more or less equivalent to a red-black tree. 
An append-only tree is convenient, as it naturally supports the 
single-writer/many-readers MVCC concurrency model. 

<p>
The implementation includes some optimizations to reduce the number of 
interior nodes that are updated when a leaf node is written that are not 
described here. See header comments in source code file 
<a href=../src/lsm_tree.c>lsm_tree.c</a> for details.

<h3 id=memory_allocation>2.3.1. Memory Allocation</h3>

<p>
More than one in-memory 
tree may exist in shared-memory at any time. For example in the following 
scenario:

<ol>

but the values that connect the linked list together are not. The writer 
that detects the failure must scan the entire shared-memory region to 
reconstruct the linked list. Any sequence ids assigned by the failed 
writer are reverted (perhaps not to their original values, but to values
that put them at the start of the linked list - before those chunks that
may still be in use by existing readers).

<h3 id=header_fields>2.3.2. Header Fields</h3>
<p>
As well as the in-memory tree data, the following fixed-size fields 
stored in well-known locations in shared-memory are part of the in-memory
tree. Like the in-memory tree data, outside of recovery these fields are only
ever written to by clients holding the WRITER lock.

<ul>
  <li> Two copies of a data structure called a "tree-header". Tree-header-1
       and tree-header 2. A tree-header structure contains all the information
       required to read or write to a particular version of the append only
       b-tree. It also contains a 64-bit checksum.

  <li> A boolean flag set to true at the beginning of every write 
       transaction and cleared after that transaction is successfully 
       concluded - the "writer flag". This is used to detect failures that
       occur mid-transaction. It is only ever read (or written) by clients
       that hold the WRITER lock.
</ul>


<h2 id=other_shared-memory_fields>2.4. Other Shared-Memory Fields</h2>

<ul>
  <li> Snapshot 1.
  <li> Snapshot 2.
  <li> The meta-page pointer. This value is either 1 or 2. It indicates which
       of the two meta-pages contains the most recent database snapshot.
  <li> READER lock values.
</ul>

<h2 id=log_file>2.5. Log file</h2>

<a href=../src/lsm_log.c>lsm_log.c</a>.

<h1 id=database_recovery_and_shutdown>3. Database Recovery and Shutdown</h1>

<h2 id=read-write_clients>3.1. Read-write clients</h2>

<p>
Exclusive locks on locking region DMS1 are used to serialize all connect and
disconnect operations performed by read-write clients. 

<p>When an LSM database connection is opened (i.e. lsm_open() is called):

<pre>
  lock(DMS1, EXCLUSIVE)           # Block until successful
    lock(DMS2, EXCLUSIVE)         # Abandon if not immediately successful
    if( DMS2 successfully locked ){
      zero *-shm file (or equivalent)
      run recovery
    }
    if( error during recovery ){
      unlock(DMS2)
    }else{
      lock(DMS2, SHARED)          # "cannot" fail
    }
  unlock(DMS1)
</pre>

<p>
Running recovery involves reading the database file header and log file
to initialize the contents of shared-memory. Recovery is only run when the
first connection connects to the database file. There are no circumstances
(including the unexpected failure of a writer process) that may cause 
recovery to take place after the first client has successfully connected.

<p>
Assuming recovery is successful (or not required), the database client is
left holding a SHARED lock on DMS2. This lock is held for as long as the
database connection remains open.

<p>
When disconnecting from a database (i.e. an lsm_close() call following a
successful lsm_open()):

<pre>
  lock(DMS1, EXCLUSIVE)           # Block until successful
    lock(DMS2, EXCLUSIVE)         # Abandon if not immediately successful
    if( DMS2 successfully locked ){
      ...TODO...
      delete *-shm file (or equivalent)
    }
    unlock(DMS2)
  unlock(DMS1)
</pre>

<h2 id=read-only_clients>3.1. Read-only clients</h2>

<p>It is assumed that read-only clients may take SHARED locks only. And
that a read-only client may not run database recovery when a db is opened 
in multi-process mode.

<p>

<h1 id=database_operations>4. Database Operations </h1>

<h2 id=reading>4.1. Reading</h2>

<p>
Opening a read transaction:

<ol>
  <li> <p>Load the current tree-header from shared-memory.

Once a read transaction is opened, the reader may continue to read the 
versions of the in-memory tree and database file for as long as the READER
lock is held.
<p>
To close a read transaction all that is required is to drop the SHARED lock
held on the READER slot. 

<h2 id=writing>4.2. Writing</h2>

<p>
To open a write transaction:

<ol>
  <li> <p>Open a read transaction, if one is not already open.
  <li> <p>Obtain the WRITER lock.

  <li> Sweep the shared-memory area to rebuild the linked list of chunks so
       that it is consistent with the current tree-header.

  <li> Clear the writer flag.
</ol>

<h3 id=flushing_the_in-memory_tree_to_disk>4.2.1. Flushing the in-memory tree to disk</h3>

<p>
For the purposes of writing, the database file and the in-memory tree are
largely independent. Processes holding the WRITER lock write to the in-memory
tree, and processes holding the WORKER lock write to the database file.

<ol>

  <li> Update the private copy of the tree-header to reflect a new, empty tree.

  <li> Commit the write transaction, writing the new, empty tree to
       shared-memory.
</ol>

<h3 id=shared-memory_management>4.2.2. Shared-memory management</h3>

<p>
A writer client may have to allocate new shared-memory chunks. This can be
done either by extending the shared-memory region or by recycling the first
chunk in the linked-list. To check if the first chunk in the linked-list may
be reused, the writer must check that:

<ul>
  <li> The chunk is not part of the current in-memory tree (the one being
       appended to by the writer). A writer can check this by examining its
       private copy of the tree-header.

  <li> The chunk is not part of an in-memory tree being used by an existing
       reader. A writer checks this by scanning (and possibly updating) the
       values associated with the READER locks - similar to the way SQLite 
       does in WAL mode.
</ul>

<h3 id=log_file_management>4.2.3. Log file management</h3>

<p>
A writer client also writes to the log file. All information required to write
to the log file  (the offset to write to and the initial checksum values) is
embedded in the tree-header. Except, in order to reuse log file space (wrap
around to the start of the log file), a writer needs to know that the space
being recycled will not be required by any recovery process in the future.
In other words, that the information contained in the transactions being
overwritten has been written into the database file and is part of the
snapshot written into the database file by a checkpointer (see "Checkpoint
Operations" below).

<p>
To determine whether or not the log file can be wrapped, the writer requires
access to information stored in the newest snapshot written into the database
header. Their exists a shared-memory variable indicating which of the two
meta-pages contain this snapshot, but the writer process still has to read the
snapshot data and verify its checksum from disk.

<h2 id=working>4.3. Working</h2>

<p>
Working is similar to writing. The difference is that a "writer" modifies
the in-memory tree. A "worker" modifies the contents of the database file.

<ol>
  <li> <p>Take the WORKER lock.

  <li> <p>Invoke xShmBarrier().

  <li> <p>Update snapshot-1 in shared-memory.

  <li> <p>Release the WORKER lock.
</ol>

<h3 id=free-block_list_management>4.3.1. Free-block list management</h3>

<p>
Worker clients occasionally need to allocate new database blocks or move
existing blocks to the free-block list. Along with the block number of each
free block, the free-block list contains the snapshot-id of the first 
snapshot created after the block was moved to the free list. The free-block
list is always stored in order of snapshot-id, so that the first block in

       header. This is done by reading (and verifying the checksum) of the
       snapshot currently stored in the database meta-page indicated by the
       shared-memory variable.
</ul>



<h2 id=checkpoint_operations>4.4. Checkpoint Operations</h2>

<ol>
  <li> Take CHECKPOINTER lock.

  <li> Load snapshot-1 from shared-memory. If the checksum does not match
       the content here, release the CHECKPOINTER lock and abandon the 
       attempt to checkpoint the database.

  <li> Sync the database file again.

  <li> Update the shared-memory variable to indicate the meta-page written in
       step 5.

  <li> Drop the CHECKPOINTER lock.
</ol>

<h1 id=scheduling_policies>5. Scheduling Policies</h1>

<p>
When a client writes to a database, the in-memory tree and log file are
updated by the client itself before the lsm_write() call returns. Eventually, 
once sufficient writes have accumulated in memory, the client marks the 
current tree as "old", and subsequent writes are accumulated in a new tree.

<p>
In order to prevent the in-memory tree and log file from growing indefinitely,
at some point in the future the following must occur:

<ul>
  <li>The contents of the old tree must be written into the database file
      (a WORKER lock operation). Once this is done the memory used to store the
      old tree is available for reuse.

  <li>A checkpoint operation must take place to sync the data into the 
      database file and update the database header (a CHECKPOINT lock 
      operation). Once this has been done the log file space that was used 
      to store the data may be reclaimed.
</ul>

<p>
In addition to the above, it is necessary to perform a certain amount of 
work on the database to merge existing levels together. This is not just
to speed up queries - there is a hard limit of roughly 40 levels to stop
database snapshots from growing overly large.

<p><b> Explicit Calls to lsm_work() and lsm_checkpoint() </b>

<p><b> Compulsory work </b>

<ul>
  <li><p> If a writer tries to mark a tree as "old", but there is already an
       old tree in-memory, the writer attempts to grab the WORKER lock and
       write both the old and new tree to a new database level.

      <p> If the WORKER lock cannot be obtained immediately, block until it
       can be
</ul>

<p><b> Auto work </b>