Oh wow… My jaw dropped when I read your post, I couldn’t believe things are that bad in storage hardware world, but apparently, it’s reality… And now tables have turned that I’m taking Sorc96 place wanting to ask you his questions 
I take my hat off to you. At first I didn’t understand, but now I’m eagerly looking forward to Hobbes 
Your knowledge on the topic is commendable. But I do wonder how can you solve this in a comprehensive manner, once and for all? Barring writing a driver that uses disk in their raw form (block devices?) then I am not sure you can protect against the kernel and the existing drivers trying to be too smart and too helpful, and crippling proper database performance as a result – which as you alluded to is an old and known problem.
Lol first I think I need to clarify something. When I say I want to solve these problems once I mean for me. I don’t mean that I am, like, the savior of the database universe or something; that would be quite silly.
Actually, it’s the Tigerbeetle devs who have been pushing this boundary forward lately with respect to having a proper storage fault model, and I am very much “copying off of their homework” in my own implementation. But that’s how this stuff works: much of their approach was copied from ZFS (the filesystem), the designers of which also contributed enormously to this idea of systems that don’t incessantly lose data.
What I mean by “solve these problems once” is actually, for me, very specific. I am very interested in sovereignty as I have mentioned, and I want to be able to build systems that store data for some products that I’m working on. Here are a few of the things I want:
This list is not random, it’s a specific list of things that I actually need for specific functionality in apps that I am actually designing. I want to be able to “own” these things so I am not forever at the mercy of megacorporations that hate us. There are many open source projects available that do some of these things, but none of them are exactly what I want.
The thing is, all of these things (and others) have the same base requirements: a way to consistently replicate persistent data across servers and be somewhat resilient to corruption. So I could write that code three or four times, or I could factor it out, write it once, and then build the other stuff as (mostly) stateless layers on top of it.
Hobbes is that code factored out. Hobbes is a toolkit which will contain all of the parts of building “distributed database-shaped things” which are the same so that I don’t have to re-implement them 10 times. This is actually a practical endeavor. I have clear and specific goals.
However, in sharing this work with the community of course I am trying to also present it in terms of how it might be useful to them, as that’s what people really want to hear (see the first few posts in this thread).
Well on Linux you kinda can. You just set O_DIRECT and bypass the page cache. That’s literally what it’s for. This is going to become a lot more common now that it is known to be effectively impossible to avoid corruption without that flag. Postgres prominently supports direct I/O now for example.
(Actually it’s funny, this all began with Postgres’s fsyncgate. After that they modified the database to crash on fsync failure, only for that paper to then be published showing that doesn’t work either!)
I am not knowledgeable or resourced enough to do all of the research needed for this on my own. But thankfully Tigerbeetle has pretty solid internals docs and readable code and they care a lot about evangelizing this approach (because it makes their database look good) so I can just learn from them.
If they say ECC memory and O_DIRECT is good enough then I believe them. Obviously no database is going to survive the Sun swallowing the Earth, but if I’m writing a storage engine from scratch (which I literally am right now, see the xks directory) then I may as well use the latest best practices.
BTW I will probably not do the nif thing for a while. I’m just trying to structure everything so that it will be an easy switch. I am not looking forward to dealing with native code because I am not a systems programmer. But I was not a database programmer either so shrug. I’ll make do.
I won’t know the answer to this for a while as Hobbes is not yet at a place where this can be tested. And even if it were, doing such tests would be pretty (financially) expensive. Scaling to huge numbers is not a priority for me in the short term. What matters to me is that Hobbes is architecturally capable of scaling so that it can grow with me.
With that said, FoundationDB could provide a rough upper bound. FDB is known to tap out around a few hundred terabytes of data (i.e. around a petabyte after replication). This is on the order of maybe a thousand servers. My understanding is that FDB taps out due to keepalives, though, which is a very fixable thing. So I suspect its users (i.e. Apple/Snowflake) simply have not found much use for getting past ~100TB scale in a single cluster.
Apple’s deployment for example is highly multitenant: it stores all CloudKit data, and is probably slowly consuming their (also enormous) Cassandra deployment. You want to have separate clusters for blast radius reasons, and you can move tenants between clusters, so really the cluster size limit is a tenant size limit. And 100TB is a very big tenant, so you can see why there is little need to get larger than that. Also, you want separate clusters so that you can shard geographically for low latency.
If you have a very big dataset you have to shard it across servers. A primitive approach here is to hash shard data into explicit buckets like e.g. DynamoDB which has 10GB shards controlled by a user-defined (developer-defined, that is) shard key. In that case you just send data to the right server(s) for its shard.
Unfortunately this means that you have to know the distribution of your dataset in advance, which is problematic. To solve this you can do range-based autosharding, where the shards are split/merged automatically and moved around as the distribution changes. This is a more advanced approach.
Spanner, CockroachDB, FoundationDB, and of course Hobbes are examples of the latter approach.
Maintaining atomic transactions across disparate shards gets tricky, though. Older systems just don’t, while newer systems like CockroachDB have atomic transactions but with questionable consistency guarantees. Spanner, FDB, and Hobbes offer very strong consistency guarantees.
The answer to your actual question is deeply technical and completely different among all of the systems I mentioned, but I can try to hand-wave a bit. For Hobbes we essentially take in a bunch of small transactions, group them together into a batch with a single version, perform concurrency control, and then split them up and send them to different servers for storage. This is, like, legit pretty complicated though.
Hi @garrison , I was reading some of Hobbes (specifically the binary enc/dec in Keyset) and realized you may be interested in this erlfdb PR.
https://github.com/foundationdb-beam/erlfdb/pull/57
The implementation from the original erlfdb accumulated an offset int and used that to do ever-increasing match clauses. This turns out to be pretty slow. It makes a measurable difference when doing many erlfdb_tuple operations.
Hah, I thought the offset thing was pretty clever in that you can grab the binary slice without accumulating by character (which would be the naive approach). But it looks like :binary.match() is a nif and there’s no beating that. Thanks for the tip, I’ll keep that in mind.
If you’re reading that code I should note that I only implemented enough of Keyset to be useful internally. The first implementations of a lot of the internals were scaffolded out with hacky manual string encodings and that quickly became an actual problem so I needed some sane form of binary encoding.
I was going to make a point about how unfortunate it is that we can’t prefix the strings with their lengths but I see you already mentioned that in the PR! This is a case where I think the value encodings can make a much better tradeoff by including a header with types/offsets/lengths at the start of each value. That way you don’t have to decode the entire value (much larger than a key) in order to pull out a “column”. Obviously the values have no ordering requirement.
I think it’s time for a little update.
Storage engine development has been going very well. There is, mostly, a storage engine now. It’s named XKS (short for ExKeyStore, which I think is a hilarious pun) and you can find the code in the lib/xks directory. It’s unfinished and obviously still messy, but most of the constituent parts are now there and it’s just a matter of gluing them together.
For those unaware, a “storage engine” is just the part of a database that writes data to disk. Generally a storage engine exposes some level of abstraction (like “key/value store”) and atomic commit functionality. Strangely, storage engines are often completely separate pieces of software from the databases that utilize them. MySQL has InnoDB, MongoDB has WiredTiger, and so on. Some databases do have their own for various reasons: Postgres’s is quite bespoke and quite old (and quite bad), Tigerbeetle’s is very deeply integrated with their data model (it literally only stores fixed-length data, which is unique).
For those of you who remember some of my earlier comments on the topic (before Hobbes was formally announced), you may remember that I originally intended to just use SQLite as a storage engine and dodge this particular yak for now. In fact, that’s exactly what FoundationDB did for over a decade. They have since switched over to RocksDB, for some reason.
So why did I change my mind? Well, firstly at the time I just didn’t know how to write a proper storage engine, but as Hobbes’s development dragged on I ended up studying enough to fix that. But also, I came to realize that there are some areas where deep integration with the storage engine can actually simplify the implementation of Hobbes’s distributed features and improve correctness. And if there are any two things I like, they’re being lazy and not writing bugs. So, uh, yolo.
On the correctness side, rolling the entire storage engine from scratch means Hobbes can maintain zero dependencies (and if there’s anything I hate, it’s dependencies) and perform fully integrated simulation testing of the entire database as a whole. Whereas if I used something like SQLite, I would probably be mocking it out during testing, which is Not Great. Also, XKS is designed to be very resilient to corruption via comically aggressive cryptographic checksumming of the entire file a la ZFS or Tigerbeetle; it’s a modern design.
On the functionality side, FDB’s most unfortunate limitation is that read-only transactions can only be a few seconds long. Most of FDB’s limitations are Good Actually, including the limit on read+write transactions. Long transactions in an optimistic system (or really even a pessimistic system) are poison and to be avoided. But read-only transactions are different as they have no contention under an MVCC model. The reason FDB doesn’t support this is really a skill issue on the part of the SQLite btree: it doesn’t know how to store versioned data. Poor thing.
XKS uses an LSM tree design that pushes database versions directly down into the storage engine. LSMs are a natural fit for this because compaction provides an opportunity to garbage-collect old versions. And if you design this wrong you end up with Postgres’s VACUUM disaster, where, fun fact, they originally designed it so that old tuples would never be garbage collected at all and then apparently found out that that is a bad idea (lol).
The XKS design is quite unique and I have been unable to find another real-world example of an LSM that works this way. I’m sure the idea must exist in research somewhere, but in practice it seems like people just add another version to the keys “in userspace” (see CockroachDB/Pebble). Maybe Spanner’s storage engine does this but we’ll never know because they only gave us a one-paragraph description (WHY).
That’s all for now.
Very thankful for my fuzzers when I have to refactor garbage like this. And no, I do not want to talk about wtf I was thinking when I wrote the first pass. I think I was just trying to get through it.
It’s becoming increasingly clear to me how much code quality matters, and also how much of it is a pure expression of skill and experience. I did not understand how to shape that code properly until I had to write a similar version a few more times elsewhere in the engine, and then it slowly dawned on me. That first attempt was so messy I literally had to sit down and reverse engineer it despite having written it only a few weeks ago.
It’s also becoming increasingly clear to me that very little of the difference can be automatically linted or checked. I have suspected this for a while (and I don’t like linters or formatters very much), but this is a pretty clear example. I doubt anyone who clicks that link will even be able to understand why the new version is better; not out of ignorance, but because it’s enormously context-specific. I doubt a top LLM could make much sense of it either, at least not well enough to make useful recommendations in advance.
I wrote a lot of messy code over the past week trying to get persistence of the remaining data structures to work. Now that the engine can save itself to “disk” (or so it thinks), it’s definitely time to go over everything and clean up before I move on to the fun parts. Though I do find refactoring to be quite relaxing as long as I have good tests, which is of course the hard bit.
I’ve started to get very good at scaffolding out large projects. I suspect junior devs think this ability is black magic, but it’s very much a skill that you hone with practice. Eventually you learn how to break the thing up and build it one piece at a time.
I’ve seen people suggest that they find LLMs useful for starting new projects, which I find concerning. If you don’t practice you will never learn how to do it yourself. Maybe fine if models are writing all of the code, but what do you do when you want to build something outside of the training set?
I think I should consider posting more devlog-shaped things. Maybe in a separate thread, or perhaps on the blog. Unclear.
LLMs are a great way to overcome the blank canvas terror. Or just make a draft so you can curate it. I don’t view remembering the exact layout of a typical Elixir project as an important skill.
In commercial programming generating and then massaging the generated code is an oft-enough occurrence for LLMs to become objective net positives.
Took a quick look. It mostly seems aimed at making sure your recursive accumulator-using (and potentially tailcall-optimized) functions more… idiomatic? Easier to work with? Not quite sure but yeah, it’s a touch obscure code indeed. But deconstructing data and making the recursive functions easier to read is already a big win IMO.
How did fuzzers help? Did they expose edge cases?