ACID to SQLite

This post describes the system of locking and maintaining atomicity, consistency, isolation and reliability (ACID) in SQLite, as well as algorithms for writing and reading from the database file.

Pager Module

Locking and parallel access in SQLite version 3 and higher is handled by a pager (pager module). This module is responsible for ACID. The pager is not interested in the details of the encodings of the database, B - trees, indexes, etc. From his point of view, the database is one file divided into equal blocks (pages) numbered starting from 1. The pager communicates with the operating system using the OS layer Interface. In this post, “flow”, “process” and “thread” are equivalent concepts.

Locks

From the point of view of a single process, a database file can be in one of the 5 blocking states listed below:

• UNLOCKED - The default state. The database is unlocked, any threads can read and write data.
• SHARED - The database is readable, but not writable.
• RESERVED - The process plans to write to a file, but is currently reading. Only one RESERVED lock can be at a time. Together with this mode can be used SHARED lock.
• PENDING - The process waits for all SHARED locks to end to start recording and switch to EXCLUSIVE mode.
• EXCLUSIVE - The process writes to the database file. No other base locks in parallel with this are not allowed.

Below are the algorithms for reading and writing data when using a rollback log as a guarantee of the integrity of the database.

')

Algorithm for reading data from the database

To read from the database, the process should perform the following steps:

1. Open the database file and get the SHARED lock if this action cannot be returned SQLITE_BUSY .
2. Check if the base has a hot rollback log. If not, you can read the data from the database. If yes, then step 3.
3. Get a pending and then EXCLUSIVE lock. If it is not possible to get these locks, it means that another process is already rolling back. In this case, remove all locks and return SQLITE_BUSY .
4. Read the rollback log and the master log (when several databases are attached, a special file (master journal) is created, which stores data on the rollback logs for each of the attached databases).
5. Roll back
6. Delete the redo log file (depending on the journal_mode option of the PRAGMA command , deleting occurs differently).
7. Delete the master log file, if possible.
8. Remove PENDING and EXCLUSIVE locks, but leave the SHARED lock, and read the database.

Algorithm for writing data to the database

To write data to the database, the process must first perform the following steps:

1. Get SHARED lock (read algorithm from the database).
2. Get a RESERVED lock. If this is not possible, return SQLITE_BUSY .
3. Create a redo log. The size of the database, as well as the name of the master of the journal, if such exists, is written in the title of the journal.
4. Before making changes to any database page, the process first writes this page to the redo log. The modified pages are first written to RAM, which means that the base file does not change, and other processes can read data from the base. If the data change is over and the process produces a COMMIT , or if the memory is full, go to step 5.
5. Ensure that all rollback log data was actually written to disk.
6. Get a pending and then EXCLUSIVE lock. If it is not possible to obtain data locks, you must wait until the database file is released.
7. Write all the data from RAM to disk in the database file (if the reason for writing was an overflow of RAM, then return to step 4).
8. Delete the redo log file (depending on the journal_mode option of the PRAGMA command , deleting occurs differently).
9. Remove PENDING and EXCLUSIVE locks.

The atomic commit algorithm is discussed in more detail in another post: habrahabr.ru/post/181584