Introducing Limbo: A complete rewrite of SQLite in Rust

2 years ago, we forked SQLite. We were huge fans of the embedded nature of SQLite, but longed for a more open model of development. libSQL was born as an Open Contribution project, and we invited the community to build it with us.

As a result, libSQL is an astounding success. With over 12k Github stars, 85 contributors, and features like native replication and vector search, libSQL is the engine that powers the Turso platform.

Today we are announcing a more ambitious experiment: what could we achieve, if we were to completely rewrite SQLite in a memory-safe language (Rust)? With the Limbo project, now available at github.com/tursodatabase/limbo, we are now trying to answer that question.

#The pros and cons of forking

When we forked SQLite, forking was not the only alternative. We considered rewriting it entirely, but were concerned about the huge lead time needed to have something production-ready, and the toil involved in keeping compatibility. A fork would also allow us to keep back-merging from SQLite, adopting new features as they come.

On the other hand, there are disadvantages as well: SQLite’s test suite is proprietary, meaning that it is hard to achieve the confidence to make very large changes. It is also written in C, an unsafe language, which makes evolving the codebase with confidence even harder.

Weighing the pros and cons, forking was the way to go, and the libSQL project was born.

#A new approach

Adding Vector search to SQLite was an eye opener. We didn’t want to do this as an extension, since we wanted to make the syntax as straightforward and natural as possible. That would require changes to the bytecode generation, which we did. We are able to expose vectors as a data type, query relational and vector data together in the same table, and as long as the query doesn’t need an index, use perfectly boring SQL syntax.

But for searches with an index, without making very invasive changes, it was hard to achieve the syntax that we wanted:

SELECT title, year
   FROM movies
   ORDER BY vector_distance_cos(embedding, vector('[4,5,6]'))
   LIMIT 3;

And we ended up settling for

SELECT title, year
   FROM vector_top_k('movies_idx', vector('[4,5,6]'), 3)
   JOIN movies
   ON movies.rowid = id;

The index is represented as a separate table, and we have to explicitly join it with the main table.

At that point, we decided to try a new approach and answer the question: how much effort was it really involved in rewriting SQLite from scratch ? And can we do it in a way that effortlessly keeps compatibility? Would that make it easier for us to be more aggressive and do some of the things we wanted to do in our fork (like asynchronous I/O) with a high degree of confidence?

To answer those questions, Pekka started an ambitious experiment on his personal github account. It was named Limbo as a codename temporarily, and it did extremely well. Without much press, just me talking about it on 𝕏, the project grew to 1,000 github stars, and attracted more than 30 contributors organically.

#The next step

With the success of this experiment, we have decided to turn Limbo into an official project at Turso. It is still an experiment, but now an official Turso experiment, which will allow us to pour more resources into it, including more time from other engineers in the company.

Our goal is to build a reimplementation of SQLite from scratch, fully compatible at the language and file format level, with the same or higher reliability SQLite is known for, but with full memory safety and on a new, modern architecture.

That is not to say that we’re building a competitor or alternative to libSQL: if it succeeds, this codebase just becomes libSQL. The code is available under the same license as libSQL (MIT), and with the same community-friendly attitude that defined our project.

#Can we match SQLite’s world-famous reliability?

Since this is a reimplementation, doesn’t that mean that testing is now even harder? The reality is that it is the other way around. Since we are reimplementing it from scratch, we are doing it with Deterministic Simulation Testing (DST) built-in from the get-go. We have both added DST facilities to the core of the database, and partnered with Antithesis to achieve a level of reliability in the database that lives up to SQLite’s reputation.

Deterministic Simulation Testing is a paradigm made famous by the folks at TigerBeetle, that we at Turso already dipped our toes into with our server-side code. With DST, we believe we can achieve an even higher degree of robustness than SQLite, since it is easier to simulate unlikely scenarios in a simulator, test years of execution with different event orderings, and upon finding issues, reproduce them 100% reliably.

In the DST world, writing our own simulator is akin to writing unit tests: they allow us to move fast, experiment easily, and stress changes thoroughly. But much as unit testing does not do away with the need for higher level integration testing that tests the behavior of the system at a higher level, we felt like we needed to go the extra mile to achieve the levels of reliability that we wanted.

To complete the puzzle, we wanted to deterministically test the behavior of the database when interacting with the operating system and other components. To do that, we are partnering with Antithesis, a company that provides a system-level Deterministic Simulation Testing framework, and can simulate all sorts of hardware and software failures. Antithesis does that by providing a deterministic hypervisor that runs many fuzzing threads in parallel, allowing us to quickly search the input space.

As an example of why this is important, they have already helped us find issues in our io_uring implementation under partial writes. Our own DST framework would not have caught this, since the actual I/O loop is replaced by the simulated I/O loop in testing. Partial writes are an extremely rare condition, and therefore, hard to test in an automated fashion.

Aside from Deterministic simulation testing, we also routinely fuzz inputs, and then make sure that the generated bytecode is the same, for both Limbo and SQLite.

#The current status

While Limbo is still in early stages, it has already achieved some important milestones that are already a couple of things worth noting:

#Fully asynchronous I/O

Limbo is designed to be fully asynchronous. SQLite itself has a synchronous interface, meaning driver authors who want asynchronous behavior need to have the extra complication of using helper threads. Because SQLite queries tend to be fast, since no network round trips are involved, a lot of those drivers just settle for a synchronous interface. However, this has two fundamental problems: Not all SQLite queries are fast. Aggregations over large data, for example, will always be slow, even if the data is fully local. In modern environments, it is actually desirable that queries go over the network. One example is Turso, which serves SQLite over HTTP. Another example are implementations of SQLite over S3 providing the illusion of infinite storage space, where data can be cached locally, but parts of it may be remote.

Limbo is designed to be asynchronous from the ground up. It extends sqlite3_step, the main entry point API to SQLite, to be asynchronous, allowing it to return to the caller if data is not ready to consume immediately. On Linux, Limbo uses io_uring, a performant API for asynchronous system calls.

#Designed for WASM

While SQLite can compile to WASM, it is mostly an afterthought for SQLite. In practice, projects like wa-sqlite exist to extend SQLite and allow it to function in WASM environments like Stackblitz . Limbo is designed from the ground up to have a WASM build, and already has a VFS implementation that works with popular tools like Drizzle without any changes. For example, it is possible to write:

import { drizzle } from 'drizzle-orm/better-sqlite3';
import * as s from 'drizzle-orm/sqlite-core';
import { Database } from 'limbo-wasm';

const sqlite = new Database('sqlite.db');
const db = drizzle({ client: sqlite });
const users = s.sqliteTable("users", {
  id: s.integer(),
  name: s.text(),
})

const result = db.select().from(users).all();

console.log(result);

Browser support is in the works.

#Performance

SQLite is known for its stellar performance, but in many operations, Limbo is already on par or faster than SQLite. Executing cargo bench on Limbo’s main directory, we can compare SQLite running SELECT * FROM users LIMIT 1 (620ns on my Macbook Air M2), with Limbo executing the same query (506ns), which is 20% faster.

#Simplicity

Despite the fact that SQLite’s file-based nature makes working with it extremely simple, SQLite grew a considerable amount of tunables over the years, which make getting top performance out of it non-obvious (the SQLite numbers on the benchmark above are after tuning). For maximum performance, users have to choose WAL mode over journal mode, disable POSIX advisory locks, etc.

Limbo, while maintaining compatibility with SQLite’s bytecode and file format, drops a lot of the features that we consider less important for modern environments (including SQLite’s “amalgamation”, the build system that generates a single C file), providing a better out-of-the-box experience.

#Interested in learning more?

Limbo is available under the MIT license on our Github. If you are interested in building an embedded database with the bold vision of taking the promise of SQLite to the next level, come build with us.