Proposal for Improving Concurrency in SQLite

This article proposes a method for increasing the concurrent access performance of the SQLite embedded database engine. The Microsoft Jet database engine is used for comparison. The method is presented at a high-level with justification, but implementation details are not worked out. The intended audience is all those interested in SQLite concurrency performance.

SQLite versus Jet

SQLite and Microsoft Jet are both file-server database engines. A file-server database differs from a client-server database in that there are no constantly running server processes to intercept and handle requests. Instead, each client process directly issues requests to the database. The client processes can run database functions because they either load a shared database DLL (Msjet40.dll - 1.4 MB, sqlite.dll - 0.3 MB), or have the functionality compiled-in. Both client-server and file-server based database engines typically store all their data on the operating system's ordinary file system. Both rely on the integrity of the operating system file system. Some advanced client-server databases, notably Oracle, store their data in specially formatted partitions.

The Jet database engine is no longer supported by Microsoft, is limited to two gigabytes per database file, and it does not support durability of its transactions. [3] Jet provides the functionality to manage data in Microsoft Access .MDB files. (Microsoft Access by itself only provides a graphical front-end.) Jet is closed source and only runs on the Windows platform, but it is freely distributable subject to certain license terms. Jet enforces referential integrity (via foreign key constraints), allows nested transactions, and supports stored procedures. It has no support for triggers.

By comparison, SQLite is maintained by SQLite.org. It can support two terabyte database files and ACID-compliant transactions. Its source code is in the public domain, meaning anyone is free to use it for any purpose whatsoever. It it very small and can operate in a vast set of platforms and languages. SQLite does not come with a graphical front-end as feature-rich as Microsoft Access, although third-party solutions exist. SQLite does not enforce referential integrity, and it does not support nested transactions or stored procedures. It has limited support for triggers.

Neither database is particularly suited for high concurrency environments, where multiple users simultaneously read and write the database. Jet fails because it is not fully ACID-compliant, and has a hard-limit of 255 simultaneous connections and recommended limit much lower. SQLite fails because it uses file-level locking that requires locking the entire database during write transactions. Although Jet is not ACID-compliant, it supports row-level locking (since version 4.0), theoretically offering better performance under concurrent access than SQLite. [6] Jet can be configured in page-level locking mode, and supports write flushing to improve durability.

SQLite implements ACID-compliance by way of a transaction journal. The journal entries are stored in an automatically created file with the same name as the database file, but with a "-journal" prefix. Somewhat analogously, Jet implements row-level locking by way of a special lock file. The lock file is also named after the database file, but it takes a .LDB extension.

Prior SQLite Concurrency Proposals

Dr. Richard Hipp, the creator of SQLite, suggests some table-level locking methods to improve concurrency in SQLite. One is by storing each table in a separate file, while the other is by storing additional locking information in the journal. Both methods have significant disadvantages. Storing tables in separate files goes against SQLite's goal of simplicity, while storing locking information in the journal still disallows concurrent writes. [2]

Another method is to shorten the effective duration of transactions. The proposed method involves special keywords that indicate the desired access requirements when the transaction is begun. The problem is that these keywords would be proprietary to SQLite, and make the queries less portable. Remembering the transaction isolation levels (serializable, repeatable read, read committed, and read uncommitted) and how they are supported is already difficult, and adding proprietary extensions would increase the burden on the developer.

Dr. Hipp states, "if the fact that it is serverless is what is limiting the concurrency of SQLite, then it seems that the best way to remedy the problem is to convert SQLite to be client-server." [2] Because such a conversion would require an unlikely redesign of SQLite, he suggests using some other client-server database in high-concurrency environments. Certainly, a client-server database is more practical when database clients are accessing the database via the network. Clients connections via direct TCP/IP socket connections are quite robust, whereas connections to network file systems have many issues, especially when it comes to file locking. Nevertheless, there are several common situations where concurrency is desirable and all clients are local.

For example, the back-end database of a website is typically only accessed by the web server on the same machine. Stand-alone applications embedding SQLite also stand to gain, especially large, complex ones like the Mozilla suite. Mozilla plans to embed SQLite in its new Unified Storage subsystem. [4] As SQLite is embedded in more and more of the general computing infrastructure, considering improvements to its limitations is worthy of attention.

Client-server versus File-server Database Engines

Do client-server databases inherently have better concurrent performance than file-server databases? A simple thought experiment will suggest that they do not. Consider a simple client-server database with a single process running on the server. Suppose this process is unloaded from memory when there are no pending requests, and is reloaded when needed by the operating system. Consider further, that the clients have a copy of the database server in their own memory, which is sent to the server for execution when a request needs to be processed and there is no pre-existing process running. Since both types of database engines typically store their data on the file system, what was once a client-server database is now behaving as a file-server database. The same logic can be reversed to show that a file-server database can be converted to a client-server database.

This observation is confirmed by studying other database engines. One example is the Firebird database engine, which comes in three, interchangeable operating modes. The Classic Server and SuperServer modes correspond to a client-server model, while the Embedded mode corresponds to the file-server model. Another example is the Java HSQLDB engine. This engine supports a servlet mode where database requests are routed through HTTP to an application server like Tomcat. The application server starts up the database servlet only when a database request needs to be processed. Both of these examples show that the distinction between client-server and file-server database engines is apparent rather than fundamental. The differences in the execution model do not necessarily constrain the architecture.

Therefore, SQLite is not relegated to having poor concurrent performance simply because it is a file-server engine. Furthermore, due to SQLite's popularity, improved concurrency in SQLite would have widespread benefits. It remains to be shown a method for improving concurrency that preserves the advantages of compactness, zero-maintenance, and simplicity.

Method for Table-level Locking

The row-level and page-level locking schemes of the Jet engine suggest a similar mechanism for SQLite. SQLite could use a separate file to hold locking information. For the sake of simplicity, assume that SQLite implements only table-level locking initially. Rather than inventing a new file format for the lock coordination file, the file could be implemented as a SQLite database itself.

In SQLite, the pager module is responsible for locking and concurrency control. [1] In the proposed improvement, the pager module would be modified to store table lock information in a separate SQLite database. The module would determine which tables a query accesses or modifies, and then acquire locks on those tables. This lock database would be created automatically, and would be named after the original database with a suffix of "-locks". Its main contents would be a table containing the tables of the original database and their current locking status. All access to the original database would be coordinated through this lock database.

Since this would increase overhead, there would be a flag in the database to either enable or disable this concurrency mode. This way, the performance of single-user applications would not be adversely affected. Such an option would be similar to Jet's choice of row or page-level locking mode.

Because the lock database is a SQLite database, it is fully ACID-compliant and incorruptible. In order to maintain ACID-compliance between multiple, simultaneous writer processes, each process must be given its own journal file. The journal files could be named with the suffix "-journalPID", where PID is the process or other unique connection identifier. This way, if any or all processes crash in the middle of a transaction, the journal files become hot, and the next client can use them to restore the database to a consistent state.

Maintaining a lock database shortens the effective duration of non-competing transactions to the time required to check the lock status flag of the requested tables. The benefit is most pronounced in the multiple writer scenario, where processes attempt to write simultaneously. In this scenario, both writers are working with different sets of tables throughout the course of their transactions. Currently, one process would receive the file lock, and the other process would poll until the lock were released. In the proposed model, both processes would be free to run simultaneously, as the lock database and algorithms have guaranteed that they will not conflict with each other.

SQLite's file structure is suited to support table-level locking. The file is subdivided into pages, with each table stored as a B-tree in a subset of those pages. [5] Therefore, there should be no page that contains data for more than one table. In other words, each table is stored mutually exclusive of other tables. Journal files are related to database files in that they store only database pages that have been modified, deleted, or added.

After both processes complete their transactions, their journals must be written to the original database. Since both journals deal with different sets of pages, both can be written to the original database simultaneously. There is no need even for byte-range file locking, since the table locks imply byte range locks. During lock acquisition, each process can be assigned a method for acquiring free store pages that doesn't conflict with any other active processes.

As was done in Jet, such a technique could be extended to the page-level or row-level. Each of these modes could be an additional database option, with their corresponding tradeoffs in lock database size, overhead penalty, and concurrency benefit. Since pages and rows can already be uniquely identified by a page index and rowid, respectively, no significant changes to the database file structure would be required. Only the lock table structure would need to be extended. The query parser must be able to translate the query into range of objects that must be locked. Finally, the algorithms to merge the journals with the database would need to maintain consistency.

This proposal is made only to argue that significant concurrency improvements are possible in SQLite and to suggest a direction for further research, not to present a working or usable implementation. It is also not to say that concurrency algorithms are easy to implement. Although complex, the algorithms would most likely not increase the code size of SQLite significantly, thereby preserving SQLite's compactness.

Conclusion

In conclusion, Jet and SQLite are database engines with similar characteristics. These database engines are not limited in concurrency performance simply because they are file-server rather than client-server engines. Instead, locking mechanisms can be implemented through the use of temporary files. More specifically, SQLite could implement table-locking by the use of a temporary lock database, and temporary journals for each client process. Due to SQLite's increasing popularity and importance, such concurrency improvements would be most welcome.

References

1. Hipp, Dr. Richard, File Locking And Concurrency In SQLite Version 3, Retrieved Jan. 6, 2006.
2. Hipp, Dr. Richard, http://www.sqlite.org/concurrency.html, Improving Concurrency In SQLite, Nov. 22, 2003 Draft, Retrieved Jan. 6, 2006.
3. Microsoft, Microsoft Office 2000/Visual Basic Programmer's Guide - Using Transactions, 2002, Retrieved Jan. 6, 2006.
4. Mozilla.org, Mozilla2 Unified Storage, Nov. 15, 2005, Retrieved Jan. 6, 2006.
5. SQlite, Comments in btree.c Source Code, Retrieved Jan. 6, 2006.
6. Wikipedia, Microsoft Jet Database Engine, Retrieved Jan. 6, 2006.