What does a database optimized for SSDs look like?

Very interesting, thank you. TIL.

At the 4K random reads impacted by the fact that you still cannot switch Samsung SSDs to 4K native clusters?

Datacenter storage will generally not be using M.2 client drives. They employ optimizations that win many benchmarks but sacrifice on consistency multiple dimensions (power loss protection, write performance degrades as they fill, perhaps others).

With SSDs, the write pattern is very important to read performance.

Datacenter and enterprise class drives tend to have a maximum transfer size of 128k, which is seemingly the NAND block size. A block is the thing that needs to be erased before rewriting.

Most drives seem to have an indirection unit size of 4k. If a write is not a multiple of the IU size or not aligned, the drive will have to do a read-modify-write. It is the IU size that is most relevant to filesystem block size.

If a small write happens atop a block that was fully written with one write, a read of that LBA range will lead to at least two NAND reads until garbage collection fixes it.

If all writes are done such that they are 128k aligned, sequential reads will be optimal and with sufficient queue depth random 128k reads may match sequential read speed. Depending on the drive, sequential reads may retain an edge due to the drive’s read ahead. My own benchmarks of gen4 U.2 drives generally backs up these statements.

At these speeds, the OS or app performing buffered reads may lead to reduced speed because cache management becomes relatively expensive. Testing should be done with direct IO using libaio or similar.

That’s literally faster to do a full table scan below a particular table size.

And the filesystem will also likely be 4k block size.

Also due to error correction issues. Flash is notoriously unreliable, so you get bit errors _all the time_ (correcting errors is absolutely routine). And you can make more efficient error-correcting codes if you are using larger blocks. This is why HDDs went from 512 to 4096 byte blocks as well.

Because it is in addition to your writes, not instead of them. That's what “ahead” points to.

We're talking about database performance here, not deployment numbers.

For on disk data structures, yes.

LSM-trees do really badly at multithreaded update workloads, and compaction overhead is really problematic when there isn't much update locality.

On the other hand, having most of your index be constant lets you use better data structures. Binary search is really bad.

For pure in memory indexes, according to the numbers I've seen it's actually really hard to beat a pure (heavily optimized) b-tree; for in-memory you use a much smaller node size than on disk (I've seen 64 bytes, I'd try 256 if I was writing one).

For on disk, you need to use a bigger node size, and then binary search is a problem. And 4k-8k as is still commonly used is much too small; you can do a lockless or mostly lockless in-memory b-tree, but not if it's persistent, so locking overhead, cache lookups, all become painful for persistent b-trees at smaller node sizes, not to mention access time on cache miss.

So the reason bcachefs's (and bcache's) btree is so fast is that we use much bigger nodes, and we're actually a hybrid compacting data structure. So we get the benefits of LSM-trees (better data structures to avoid binary search for most of a lookup) without the downsides, and having the individual nodes be (small, simple) compacting data structures is what makes big btree nodes (avoiding locking overhead, access time on node traversal) practical.

The Aurora paper [0] goes into detail of correlated failures.

> In Aurora, we have chosen a design point of tolerating (a) losing an entire AZ and one additional node (AZ+1) without losing data, and (b) losing an entire AZ without impacting the ability to write data. [..] With such a model, we can (a) lose a single AZ and one additional node (a failure of 3 nodes) without losing read availability, and (b) lose any two nodes, including a single AZ failure and maintain write availability.

As for why this can be considered durable enough, section 2.2 gives an argument based on their MTTR (mean time to repair) of storage segments

> We would need to see two such failures in the same 10 second window plus a failure of an AZ not containing either of these two independent failures to lose quorum. At our observed failure rates, that’s sufficiently unlikely, even for the number of databases we manage for our customers.

[0] https://pages.cs.wisc.edu/~yxy/cs764-f20/papers/aurora-sigmo...

All financial systems don't care about time.

Prety much all financial transactions are settled with a given date, not instantly. Go sell some stocks, it takes 2 days to actually settle. (May be hidden by your provider, but that how it works).

For that matter, the ultimate in BASE for financial transactions is the humble check.

That is a great example of "money out" that will only be settled at some time in the future.

There is a reason there is this notion of a "business day" and re-processing transactions that arrived out of order.

I don't think we're disagreeing. But the issue is at the boundary between software and hardware, which the hardware device manufacturers have dictated, not further up.

Sure, I never claimed that relational databases were the first ones. I was confused because they were trying to explain a specific timeline different from the article, but only mentioned a single time period that didn't seem likely to be what they intended, and I thought it might make sense to clarify what that time period was. I'm sure this isn't the case for everyone, but at least to me, it's surprising not to be explicit in the information they were trying to claim the article glossed over.

The parent comment was pretty explicit in what types of databases it was talking about:

> I should add that the bond between relational databases and spinning rust goes back further.

It's certainly possible I failed to infer the point they were trying to make, but personally I would find it confusing for them to only mention one type of database (relational) and one time period (the 60s) if they actually meant a different type of database or a different time period in their central point of there being a relationship with, in their words, relational databases and spinning rust, in a specific time period other than what the article describes.

Isn't that why a WAL exists, so you didn't actually need to do that with eg postgres and other rdbms?

I just tested the mediocre enterprise nvme I have sitting on my desk (micron 7400 pro), it does over 30000 fsyncs per second (over a thunderbolt adapter to my laptop, even)

It is actually very cheap if done right. Enterprise SSDs have write-through caches, so an O_DIRECT|O_DSYNC write is sufficient, if you set things up so the filesystem doesn't have to also commit its own logs.

Durability always has an asterisk i.e. guaranteed up to N number of devices failing. Once that N is set, your durability is out the moment those N devices all fail together. Whether that N counts local disks or remote servers.

I think this entire design approach is on its way out. It turns out that the DIMM protocol was very much designed for volatile RAM, and shoehorning anything else in involves changes through a bunch of the stack (CPU, memory controller, DIMMs), which are largely proprietary and were never intended to support complex devices from other vendors according to published standards. Sure, every CPU and motherboard attempts to work with every appropriately specced DIMM, but that doesn’t mean that the same “physical” bits land in the same DRAM cells if you change your motherboard. Beyond interoperability issues, the entire cache system on most CPUs was always built on the assumption that, if the power fails, the contents of memory do not need to retain any well-defined values. Intel had several false starts trying to build a reliable mechanism to flush writes all the way to the DIMM.

Instead the industry seems to be moving toward CXL for fancy memory-like-but-not-quite-memory. CXL is based on PCIe, and it doesn’t have these weird interoperability and caching issues. Flushing writes all the way to PCIe has never been much of a problem, since basically every PCI or PCIe device ever requires a mechanism by which host software can communicate all the way to the device without the IO getting stalled in some buffer on the way.