<bgdev />^free

HC-tree

SQLite is sometimes used as the core of a client/server database system. While it works reliably well in such cases, the database backend module that it uses to store b-tree structures in its database file was not designed with this case in mind and can be improved upon in several ways. The HC-tree (hctree) project is an attempt to develop a new database backend that improves upon regular SQLite as follows:

Improved concurrency: Stock SQLite is limited to a single concurrent writer.

Using the begin-concurrent extension changes this so that multiple writers may run concurrently using optimistic page-level locking. This improves concurrency somewhat, but page-level locking can detect conflicts between logically independant transactions, and COMMIT operations must still be serialized.

Hctree uses optimistic row-level locking and is designed to support dozens of concurrent writers running at full-speed. Test results obtained from the prototype show that this is possible.

Support for replication: Stock SQLite supports the sessions extension, which allows the contents of a committed transaction to be serialized for tranmission and application to a second database.

Hctree builds this into the database backend, and adds support for application of such transactions to follower databases in leader-follower configurations. In this case, transactions received from a leader database can be applied more quickly and with greater concurrency than with which they were originally applied to the leader database, because no transaction validation is required.

Removal of database size limitations: Stock SQLite uses 32-bit page numbers. Using the default 4KiB page-size, this leads to a maximum database size of 2^44 bytes, or 16TiB.

Hctree uses 48-bit page numbers, allowing 2^60 byte databases, or 1EiB. Roughly one million TiB.

An implicit goal is that hctree must be as fast or faster than stock SQLite for all single-threaded cases. There is no point in running dozens of concurrent writers if each of them is an order of magnitude slower than a single writer writing to a legacy database.

Hctree clients (those that use a version of SQLite compiled from this repository) may read hctree databases and stock SQLite databases.

https://sqlite.org/hctree/doc/hctree/doc/hctree/index.html

КУР - Keep Yourself Positive!