Limbo: A complete rewrite of SQLite in Rust
turso.tech
turso.tech
The SQLite3 business model is that SQLite3 is open source but the best test suite for it is proprietary, and they don't accept contributions to any of either. This incentivizes anyone who needs support and/or new features in SQLite3 to join the SQLite Consortium. It's a great business model -- I love it. But there are many users who want more of a say than even being a consortium member would grant them, and they want to contribute. For those users only a fork would make sense. But a fork would never gain much traction given that test suite being proprietary, and the SQLite3 team being so awesome.
However, a memory-safe language re-implementation of SQLite3 is a very different story. The U.S. government wants everyone to abandon C/C++ -- how will they do this if they depend on SQLite3? Apart from that there's also just a general interest and need to use memory-safe languages.
That said, you're right that there are many other projects that call for a rewrite in Rust way before SQLite3. The thing is: if you have the need and the funding, why wouldn't you rewrite the things you need first? And if SQLite3 is the first thing you need rewritten, why not?
By the way, SQLite itself does not meet one of these criteria. Know which one? ))
This is going to sound pedantic, but SQLite is not Open Source. It's Public Domain. The distinction is subtle, but it is important.
In other words you don't use PD software "like Free Software". You can use it in many places where Free Software would not be permissible.
In terms of -developer- freedom, public domain is top of the pile, the Open Source, then Free Software.
In terms of -user- freedoms Free Software is top of the pile, OSS in the middle, public domain is similar to commercial software.
GPL is copyleft. MIT, BSD etc. are permissive. But all of those are both free software and open source, which are essentially synonyms.
The reason so many people get confused by this is that some of the people who prefer copyleft licenses (notably the FSF) also tend to prefer the term “free software”, for philosophical reasons.
In your analogy we're not the ones calling elephants bananas, you are. We want to keep calling one bananas and the other elephants. You are suggesting that since elephants are similar to bananas you can simply use either word.
Legally, Open Source and Public Domain are -very- different animals. Open Source comes eith a copyright, and a license (which has requirements), public domain does not.
Of course public domain and open source are both "shipped as source code". Then again so is a fair bit of proprietary software. That doesn't make it open source either.
Similarly the common use of "open source" is different to the OSI's preferred definition. Note that the OSI's preferred definition is not a legal definition. It's just what they prefer.
Please note that public domain laws vary depending on the country. What you call a banana might mean something different elsewhere.
Conversely, open source doesn't necessarily mean "free to use without encumbrance." There are many open-source licenses that forbid certain uses (e.g. Business Source License). On the other hand, a work in the public domain is free to be used by all without restriction.
A better analysis of open source vs. public domain would be in the form of a square, where one dimension would be the right to use the work, and the other dimension would be the ability to obtain and contribute source code.
Also, many licenses, such as the GPL (one of the very first "open source" licenses), have certain encumbrances; you cannot redistribute GPL-licensed software without either including its source code or making it readily available.
Open Source relies on copyright and contract law (which are somewhat standardized or at least understood due to their importance in commerce). Public domain relies on other laws that can vary significantly.
https://opensource.org/blog/public-domain-is-not-open-source
> “Open Source” describes a subset of free software that is made available under a copyright license approved by the Open Source Initiative as conforming with the Open Source Definition.
No it doesn't. It describes software whose source is "open" which is generally understood to mean that you can read, modify and reuse the code for free.
Public domain definitely fits that. The "public domain doesn't exist in some countries" arguments are spurious as far as I can tell.
I'm a bit puzzled why SQLite doesn't solve this trivial issue by claiming the code is CC0-licensed. CC0 is made just for that: a very wordy way to make it as close to public domain as possible in each jurisdiction.
On the other hand, hobbyists won't care. As long as you trust them in their intention to have it open source they won't sue you for infringement either. And if as a company you need more assurance than "it's public domain" they are so nice to sell you a fancy legally-satisfying piece of paper for an undisclosed price. It's a subtle but clever way to get income from users with too much money
They explicitly state, "Anyone is free to copy, modify, publish, use, compile, sell, or distribute the original SQLite code, either in source code form or as a compiled binary, for any purpose, commercial or non-commercial, and by any means."
One can buy a "license" if one's company is run by idle lawyers: https://www.sqlite.org/purchase/license
It's not clear this is a license grant rather than legal advice (which would be correct legal advice if the code were public domain, but it is not).
It's $6,000 https://sqlite.org/prosupport.html
Well, there are 2 different modes of communication:
(1) official language-lawyer pedantic communication: "open source" != "public domain"
(2) conversational casual chitchat : "open source" includes "public domain"
Yes, the SQLite home page does say "public domain". However, when people interview SQLite create, Richard Hipp, he himself calls it "open source". He also doesn't correct others when they also call it "open source". Excerpt of R Hipp:
So, I thought, well, why can't I have a database that just
reads directly off the disc? And I looked around and
there were none available. I thought, “oh, I'll just write
my own, how hard can that be?” Well, it turns out to be
harder than you might think at first, but I didn't know
that at the time. But we got it out there and I just put it
out as open source. And before long, I started getting
these phone calls from the big tech companies of the
day, like Motorola and AOL, and, “Hey, can you
support this?”, and “Sure!” And it's like, wow, you can
make money by supporting open source software?
it's wrong though. like, can't be more wrong than that. you can't do whatever you want with open source software, the license tells what you can and cannot do.
with public domain software you can do most things.
Edit: FSF should have been OSI, I think. Fixed.
(To be fair to OSI, I've never seen any of their representatives do this. But the internet vigilante squad they've spawned feels quite empowered to let us know we've broken the rules.)
I don't know where you got this idea but it's not true. The OSI is simply defending the definition as it has been generally understood since the start of its usage in the 1980s by Stallman and others.
The only group of people "re-defining" -- quite successfully I suppose, which you are an example of -- what open source software means are those that have a profit motive to use the term to gain traction during the initial phase where a proprietary model would not have benefited them.
I don't think I need to provide concrete examples of companies that begin with an open source licensing model, only to rug-pull their users as soon as they feel it might benefit them financially, these re-licensing discussions show up on HN quite often.
Most of us on 8 and 16 bit home computers didn't even knew "Stallman and others" were.
Additionally, GCC only took off after Sun became the first UNIX vendor to split UNIX into two SKUs, making the whole development tools its own product. Others quickly followed suit.
Also, in regards to Ada adoption hurdles, when they made an Ada compiler, it was its own SKU, not included on the UNIX SDK base package.
Nobody's arguing that public domain code, or the MIT, or whatever is not open source; it's obviously open source because it's _more_ free than the GPL.
Sure, devs can call any "source available" project "open source" because it gets people interested even though you have zero interest in using an open source development model or allowing others to make changes to the code. Devs can also expect well deserved flak from people who understand that "open source" is not marketing speak.
No. What are you talking about? They are not related... other than for people virtually completely new to, well, open source.
You are also completely confused, here, too:
> Yes, the SQLite home page does say "public domain". However, when people interview SQLite create, Richard Hipp, he himself calls it "open source". He also doesn't correct others when they also call it "open source".
They are different things. A project can be both; a person can talk about these two aspects of one project.
> They are different things. A project can be both; a person can talk about these two aspects of one project.
BTW, your pouring on of qualifiers (elsewhere "weasel words") shows your (correct) lack of conviction:
> the details of definitions, but I think by most people's definitions of 'open source', something that is 'public domain' qualifies as such
How's that for being pedantic?
capitalization is not bearing meaning in these contexts.
open source means OSI compliant, broadly speaking, and licensed as such.
in contrast, public domain doesn't exist in some jurisdictions, which is why sqlite as a company had to create an option to provide an official license. which they found so annoying that they charged a sweet fee to send a signed printed letter...
Is it though? The website does say "All of the code and documentation in SQLite has been dedicated to the public domain by the authors" but copyright law has no exception for "dedications" to the public domain. At best the authors are estopped from bringing suit but even that is unclear.
[quote]
Licenses are available to satisfy the following needs:
* You want indemnity against claims of copyright infringement.
* You are using SQLite in a jurisdiction that does not recognize the public domain.
* You are using SQLite in a jurisdiction that does not recognize the right of authors to dedicate their work to the public domain.
* You want to hold a tangible legal document as evidence that you have the legal right to use and distribute SQLite.
* Your legal department tells you that you have to purchase a license.
You keep and maintain your local fork that does what you need it to do. perhaps if you are charitable you share it with others. but you don't need to do this. and it just adds support burden.
As far as I can see, these tests come with the same public domain dedication as the rest of the code.
You may be referring to the TH3 tests (https://sqlite.org/th3.html). The main goal (100% branch coverage, 100% MC/DC) would not be achievable for a Rust implementation (or at least an idiomatic Rust implementation …) because of the remaining dynamic run-time checks Rust requires for safety.
The same would be possible in Rust. Everything that could panic has a non-panicking alternative, and you could conditionally insert `unreachable_unchecked()` to error handling branches to remove them. That wouldn't be most idiomatic, but SQLite's solution is also a custom one.
ABI, the same way you don't need the Linux kernel to be rewritten to remove your app dependency on C/C++
That's the position of two federal agencies, namely, FBI and CISA. They don't describe how this change will reduce CVEs or why the languages they prefer still produce projects with CVEs.
I don't particularly hold the technical or social acumen of FBI or CISA in particularly high regard and I'm not sure why anyone would by default either. Mostly because they say things like "switch to python!" without once accounting for the fact that python is written in C.
It's an absurd point to invoke as a defense of this idea.
no.
the business model is services, and a red phone to companies who use sqlite in production. like nokia back in the days when we had these little flip phones, or desk phones had a "rolodesk" built in, or many other embedded uses of a little lovely dependable data store.
the services include porting to and "certification" on specifically requested hardware and OS combinations, with indeed proprietary test suites. now these are not owned by sqlite, but by third parties. which license them to sqlite (the company).
and it started with being paid by the likes of nokia or IBM to make sqlite production ready, add mc/dc coverage, implement fuzzing, etc etc etc.,
their license asks you to do good not evil. and they take that serious and try their best to do the same. their own stuff is to an extreme extend in the public domain.
It's not just old Nokias or desktop phones, nor just embedded sytsems. sqlite is almost everywhere. Adobe, Apple, Microsoft, Google, Mozilla and many other companies use it in very widely deployed software.
> no.
> the business model is services, and a red phone to companies who use sqlite in production. like nokia back in the days when we had these little flip phones, or desk phones had a "rolodesk" built in, or many other embedded uses of a little lovely dependable data store.
Members of the SQLite Consortium surely have this "red phone" you speak of. So in what way was my characterization of their business model wrong?
> It uses Asynchronous I/O, considers WASM as first class, and has Deterministic Simulation Testing support from the beginning.
These are all very hard to do in straight C if your goal is to program in Rust.
All the other C code could be rewritten, this doesn’t stop or slow down any such effort. But for sure it was never going to be possible for a database provider to start making a memory safe implementation of libpng or something.
> 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.Further down the post I actually call out explicitly that we do intend to get rid of some of the baggage.
libSQL already isn't fully compatible: as soon as you add a RANDOM ROWID table, you get "malformed database schema" when using the (e.g.) sqlite3 shell to open your file (also Litestream doesn't work, etc).
And that's fine, as there probably is no better way of doing what you needed to do. But it's also taking what SQLite offers and breaking the ecosystem, under the covers of "we're compatible" without ever calling out what compromises are being made.
Note how the SQLite documentation that introduces STRICT tables very clearly documents the backwards compatibility issues of the feature and how to get around them: https://sqlite.org/stricttables.html#backwards_compatibility
You also never got round to documenting the internal Virtual WAL APIs you exposed. This is something where SQLite is lacking, where you could've made an impact without any compatibility issues, and pressure upstream to release something by doing it first/better. Alas, you did it for Turso's exclusive benefit.
Once you start using libSQL features, SQLite tools will simply stop working with your databases.
That means the sqlite3 shell stops working, backup solutions like Litestream and sqlite-rsync stop working, SQLite GUIs like SQLiteStudio stop working, forensic and data recovery tools start giving will have a harder time working, etc.
Maybe it's all worth it, but it's not full compatibility, and it should at least be documented.
And in this case the project intends to be fully compatible, so they wouldn't be able to unilaterally adopt or drop features anyway.
Compatibility for libSQL is a one way street. I don't expect Limbo to be any different.
And the FOREIGN KEY support is here: https://www.sqlite.org/foreignkeys.html The two requirements are that your build not have it disabled, and that you execute `PRAGMA foreign_keys = ON;` when you open the database (every time you open the database).
As for STRICT: if you make your tables STRICT, there's no opt-out.
So why is this an issue? Do you want them to break the file format to say "from this version forward, all tables are STRICT"? What does that really buy you?
It's an embed database: anyone who can mess with your database and circumvert integrity can also open the file and corrupt it.
It removes a footgun for new users. That's not an insignificant benefit.
Probably not worth the backwards compatibility cost, but it definitely is an issue.
This is easy to do for any project using the amalgamation.
That was my take for many years but I have come around 180 degree on this. I think at this point it's very likely and most likely mandatory to eventually rewrite SQLite. In parts because of what is called out in the blog post: the tests are not public. More importantly, the entire project is not really open. And to be clear: that is okay. The folks that are building it, want to have it that way, and that's the contract we have as users.
But that does make certain things really tricky that are quite exciting. So yes, I do think that SQLite could need some competition. Even just for finding new ways to influence the original project.
However, if there's a big product behind the fork, and even better, a rewrite to a memory-safe language, then the fork begins to make a lot of sense. So, hats off to y'all for pulling this off!
There isn't a long term roadmap, or anything like that. I got pretty excited when I saw the results, though. It's less about the number of github stars - who the hell cares about those - but the contributors. Limbo already has a very nice list of contributors, which led me to believe there is something here!
The first 90% is easy, it's the second 90% that is very hard.
In my experience the 10% that doesn't get done is the 10% that people don't care too much about it anyway.
They have a process for contributions to follow: you suggest a feature, they implement it. It's far from the only project to take such a stance.
Just in the SQLite “ecosystem” see the contribution policies of Litestream and LiteFS. I don't see people brandishing the ”not open contribution” to Ben's projects.
https://github.com/superfly/litefs?tab=readme-ov-file#contri...
https://github.com/benbjohnson/litestream?tab=readme-ov-file...
This is literally the first time I've ever heard of this, for any project anywhere. I suppose Android is built a bit in this way, but that's a whole other can of worms.
However, unless you can guarantee that every branch tested has been covered for all possibly relevant application states, that does not preclude CVEs.
Everytime a bug is reported in the forums, the open source tests are updated as part of the bug fix for everyone to see.
There's a separate test suite that offers 100% coverage, that is proprietary, and which was created for certification for use in safety critical environments.
HN loves to discuss business models for open source, but apparently has a problem with this one. Why?
Speaking of "wal" mode, is "wal2" mode [1] on your radar for this project to prevent wal files from growing indefinitely in a busy system?
So that’s dead on arrival.
uv run --with pylimbo --python 3.13 python
>>> import limbo
>>> con = limbo.connect("/tmp/content.db")
thread '<unnamed>' panicked at core/schema.rs:186:18:
not yet implemented: Expected CREATE TABLE statement
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
stack backtrace:
0: _rust_begin_unwind
1: core::panicking::panic_fmt
2: limbo_core::util::parse_schema_rows
3: _limbo::__pyfunction_connect
4: pyo3::impl_::trampoline::trampolineIf this is just a standard sqlite database that you are trying to open, though, I'd have expected it to work.
First, there's no need to rewrite anything to add an async interface to sqlite if you want (many clients do, whether local or remote).
The issue with sqlite's synchronous interface is leaving a thread idle while you wait for IO. But I wonder how much of an issue that really is. sqlite is designed to run very locally to the storage, and can make use of native file caching, etc, which makes IO blocking very short if not zero. You wonder if applications have enough idling sqlite threads to justify the switching. (It's not free and would be at quite a fine-grained level.)
The section does mention remote storage, but in that case you're much better off with an async client talking to compute running sqlite, sync interface and all, that is very local to the storage. AKA, a client/server database.
Also, in the WASM section, we're still talking about something that would best be implemented as a sqlite client/wrapper, with no need at all to rewrite it.
That's not the only issue. waiting for the result of every read to be able to queue the next read is also an issue, particularily for a VFS that exists on a network (which is a target of theirs, they explicitly mention S3).
I'm not sure if they also are doing work on improving this, but I'm sure that theoretically many reads and writes that SQLite does do not depend on all previous reads and writes, which means you could queue many of them earlier. If your latency to storage is large, this can be a huge performance difference.
I'm personally interested in the potential for async bindings for Python. Making fast async wrappers for blocking APIs in Python-land is painful (although it might improve in the future with nogil).
With io_uring you're talking about the low-level, where blocks are actually read and written.
As-is, sqlite is agnostic on that point. It doesn't do I/O directly, but uses an OS abstraction layer, called VFS. VFS implementations for common platforms are built-in, but you can create your own that handles storage IO any way you like, including queuing reads and writes concurrently using io_uring.
So that's not a reason to rewrite sqlite.
(In fact, I'd be surprised if they weren't looking at io_uring, and, if it seemed likely to generally improve performance, to provide an option to use it, either in the existing linux-vfs or in some other way.)
> I'm personally interested in the potential for async bindings for Python.
Well, it's perfectly possible to do that with the current sqlite. It may be painful, as you say, but not even remotely at the level of pain a complete rewrite entails.
> Well, it's perfectly possible to do that with the current sqlite.
If you want to wrap a blocking API in python, with actual parallelism, you have to use multiple processes with communication between them. The main advantage of sqlite in the first place is that it's in-process, and you'd lose that.
On a single thread. There can be multiple threads.
Of course leaving a thread idle while waiting for IO isn't great. That's why I noted it at the beginning. But it doesn't seem idling threads has proven to be much of a problem with sqlite, so it wouldn't be much justification for a rewrite.
> If you want to wrap a blocking API in python, with actual parallelism, you have to use multiple processes
You can use multiple threads in the same process.
(Python has some limitations in that respect, but that's not a sqlite issue and can't be fixed by a sqlite rewrite.)
Do they claim a clean room implementation?
It seems wise of SQLite to close down their test suite. That's a great idea I wish I had heard about earlier.
I personally use SQLite and DuckDB daily, but recently adopted turso in lieu of litestream for a something. I appreciate that they all are relatively compatible but I'd love to just have a tool.
Even then thats why I love the relationship between SQLite and DuckDB. I can backend my system with SQLite and run analytics and processing via DuckDB and they service specific purposes.
The hard thing with this for me is being a split consumer and not having the bandwidth to split my attention between who is doing better innovation and just using a tool I can rely on to predictably get the job done for me.
That being said, hats off this is awesome. I really appreciate turso.
https://www.sqlite.org/hirely.html
https://www.sqlite.org/qmplan.html
https://www.sqlite.org/th3.html
The name "Limbo" is also used by a post-C/UNIX language from AT&T for the Inferno operating system.
If there was a solid certification, it would likely be for a specific version.
Are there any open source DST projects, even just getting started? I don't even know how/where to start if I would want to do the same on a small app, but can't afford nor want to depend long term on a commercial license.
They aren’t fully open source but are free to use, including use with open source software. They may be a bit on the complex side though.
They mention testing that bytecode generation generates the exact same results as SQLite... Does this exclude writing new optimization passes that are not in sqlite?
tl;dr We are rewriting SQLite in Rust. It uses Asynchronous I/O, considers WASM as first class, and has Deterministic Simulation Testing support from the beginning.
Can it have more than 1 writer?
(In this case, since it's a rewrite in Rust, it's not actually a fork at all, I think)
Or are they claiming they will support MVCC with full file format and interprocess synchronization compatibility.
We're not fans of public domain, which is one of the things that led us to create libSQL in the first place.
It is MIT.
Also, it is technically possible for someone to claim public domain software as entirely their own work, while MIT requires attribution.
As the article mentioned, a complete rewrite will not be as stable as the original.
Only by the SQLite team. They don't accept contributions of anything other than spelling fixes and such.
https://www.sqlite.org/copyright.html
> In order to keep SQLite completely free and unencumbered by copyright, the project does not accept patches. If you would like to suggest a change and you include a patch as a proof-of-concept, that would be great. However, please do not be offended if we rewrite your patch from scratch.
We already have a fork, called libSQL. However, the goals of Limbo are far more ambitious and we cannot rewrite some parts step by step. We want to have DST ( Deterministic Simulation Testing), a testing methodology pioneered by Foundation DB and TigerBeetle. It is not easy to do that in an existing codebase
Congrats on a great new undertaking!
I could trivially write “an SQLite clone” that could execute `SELECT * FROM users LIMIT 1` even faster than either this or SQLite—if that's the only string I accepted as input!
Like a node editor or spreadsheet? It needs to be suitable for general public
So be sure you proceed in such a way that never contributes any money or code back to the original project.
https://www.w3.org/TR/webdatabase/
"The specification reached an impasse: all interested implementors have used the same SQL backend (Sqlite), but we need multiple independent implementations to proceed along a standardisation path."
I could understand if you said 'the fastest' or 'the safest' but 'the smallest' is what I'm hung up on
C libraries aren't automatically the fastest option, there's a lot of C code which has stagnated on the performance front but is still widely used because it's battle tested and known to be robust by C standards.
That's kind of my point, writing a faster PNG decoder in C may be easier for you but convincing anyone to actually use it instead of the slower but proven safe-ish libpng would be an uphill battle. Trust in C code is extremely hard-won compared to Rust which uses little if any unsafe. The 'png' crate that Chrome is considering to replace libpng has no unsafe whatsoever and is still faster.
But C lacks many modern data structures, which are critical for performance on modern hardware and bigger input data.
While fast code requires thoughtfulness regardless of the language, I think rust lets you focus on the fast aspect more because rustc ensures _some_ safety and correctness.
I can write fast and very unsafe C code fast, but I write code that just as fast , but safer in rust faster than in C.
Here's a more concrete, albeit irrelevant in practice example from writing most things in both languages:
https://news.ycombinator.com/item?id=42342382#42352053
Implemented in Rust over generic T, you need Wrapping<T> or the equivalent num_traits traits. The implementations for these take borrowed references. Rustc is pretty good at ensuring this becomes pass by value under the hood, but it's imperfect. I found instances of it failing in the test disassembly, even though an implementation for this never has to touch anything but registers. That's performance work that wouldn't have existed in C/C++ for these particular types.
Faster on a single query, returning a single result, on a single computer. That's not how database performance should be measured or compared.
In any case, the programming language should have little to no impact on the database performance, since the majority of the time is spent waiting on io anyway
may be! However, Rust makes some things easier. It is also easy to maintain and reiterate
It is to highlight that we already reached a good level of performance this early in the project.
Your claim about the programming language having no impact is just false, though. It's exactly what people said back in 2015 when we released Scylla. It was already false then, it is even more false now.
The main reason is that storage is so incredibly fast today, the CPU architecture (of which the language is a part) does make a lot of difference.
This is the right thing to do. It's a pity so many projects don't keep an eye on performance from the very first day. Getting high performing product is a process, not a single task you apply at the end. Especially in a performance critical system like a database, if you don't pay attention to performance and instead you delay optimizing till the end, at the end of the day you'll need to do a major rewrite.
I don't even care about being faster than sqlite, just not being slower, this early, is already the win I'm looking for.
That was true maybe 30 years ago with spinning disks and 100 mbit ethernet. Currently, with storage easily approaching speeds of 10 GB/s and networks at 25+ Gbit/s it is quite hard to saturate local I/O in a database system. Like, you need not just a fast language (C, C++, Rust) but also be very smart about how you write code.
The reason is obvious, of course: it has less features, and doing nothing is always faster than doing something.
Once it's feature complete, then meaningful comparisons can be made. For now, it's puffery.
The goal with that was just to demonstrate that there's nothing really there that is fundamentally slower, and the perf is already on par in the areas where we spent cycles on.