Sled: remove serde

[spacejam]

on my main dev machine, serde takes up 16 of the 29 seconds required to do a release build of sled. human optimizations are the most important for long-term system health, since they encourage all other optimizations. sled doesn't need very complex serialization, so this will be fairly easy to replace.

[pmuens]

Sounds like a good plan :+1:

sled doesn't need very complex serialization, so this will be fairly easy to replace.

Any idea / proposal what serde can be replaced with?

[spacejam]

@pmuens I replaced it with a pretty simple implementation in #902 that just uses some simple rust traits to write very little code, and it still performs on-par with serde even though now it takes half the time to compile the project!

[pmuens]

@spacejam that's awesome! 👌

I was wondering if there might be a need for a more lightweight serde-like crate which only provides the most minimal boilerplate to get basic serialization working. There might be something out there already (I haven't looked) but this is more rooted in educational curiosity.

I really enjoy the implementation in serialization.rs. Do you think there's room to make this more generic? Or do we end up with a reimplementation of serde once we'd go down that path?

[spacejam]

@pmuens yeah! @Geal has a nice crate, cookie factory that is a pretty clean and generic implementation of a simple serializer. It should be noted though that serde is really good due to the human convenience factor, and bincode used with serde is fast enough for many workloads. Once you go down the hand-written (even library-assisted) path, it's important to start spending a lot more effort on testing as well. That's why like half of the new serialization module in sled is just quickcheck tests.

There are a few key reasons why I eventually chose to remove serde after 4 years of it being a great choice:

1. Fresh compile times actually make up a big part of my experienced friction when working with this project. I have the philosophy that human optimizations are the most important ones for building fast reliable software over long time periods. Anything that makes the project less exhilarating will ultimately lead to slower and buggier code, because the humans will be less psyched about pushing it forward. It needs to feel like a game. That's why I keep playing the "build sled" video game after 4 years, I've kept it fun for myself. Shaving off 50% of the compile time really makes trying out changes significantly more exhilarating for me. (I should probably be putting more effort into gamifying "release 1.0" as well though xD)
2. I can separate the concurrent IO buffer space reservation from actually serializing my data, reducing the latency between an atomic read of a tree node and an attempt to compare-and-swap it to a new value. The log reservation has to happen in between the read and the CAS operation, and if the CAS operation is successful the log reservation is later completed, or filled with a no-op if the CAS failed. This is a key part of how the on-disk representation of data stays consistent with the in-memory representation in sled even when many threads may be doing CAS operations on shared memory without any locking. But a key part of this is that the amount of latency between the tree node read and the CAS is a huge contributor to failed operations. The shorter this latency, the less likely a CAS operation will be to fail. So, by being able to separate the calculation of a log reservation size from the actual serialization of the written data, we can skip a bunch of serialization work until we have successfully performed the CAS, and only lazily fill it in. I'm expecting this to significantly improve performance with contentious workloads where several threads tend to be writing to data on the same tree nodes, possibly interfering with each other's lock-free progress. Oh yeah, and this approach is also zero-allocation because we pre-allocate the IO buffers that this gets written into, skipping the initial write-to-vec step that I was doing out of laziness before. Note that this is also possible using bincode's serialized_size and serialize_into functions, but I figured I might as well address all of these issues in a single effort as well.
3. I have a long-term goal of implementing SIMD-friendly de/serialization, and by having this in place, that work involves changing like 5 lines of general layout code in the serialization module, then adding the simd-procesing parts. This means it might not be so hard to convince a SIMD badass to peek at sled, which currently suffers from many of the issues requiring significant architecture work, which makes it expensive to get interested contributors on-board. By having this already in place, it makes storage work much cheaper because the path to changing things is now much shallower.
4. I can use less space than generic serializers by having knowledge that some repeated types will be the last item in an externally-framed buffer, letting me skip length fields here and there due to them being implicit. I'm only comfortable doing this because these types have really stabilized a lot over 4 years and I don't see a high likelihood of modifying them at this point. serde is great when things might not feel completely ready to cut into marble. After SIMD friendliness, these will be at that point I believe.
5. when you're building a database, it feels kind of creepy not being in total control over your byte representation. I want to choose exactly where a new field gets placed, and I want to be able to reason about migration concerns without any black-box uncertainty. bincode is pretty straightforward, but it's slightly bloated for things like enums, where it stores variants as a u32. For types like PageState, I can actually fold the variant into a 1-byte length field, due to having zero repeated fields for one of the variants and something between 1 and 16 repeated items for the other variant. So many little compression tricks start to pop out when I no longer need to be general-purpose.

Sorry for the wall of text, but I have a feeling I'll be referring back to this when people ask about it.

[pmuens]

Thanks for the in-depth writeup @spacejam! 👍

Sorry for the wall of text

Absolutely not! It was a really insightful to read about all the (non obvious) implications an external dependency can have on the (human) performance as well as the overall DB architecture and design.

[djc]

Can you elaborate a bit on how from-scratch compile times add friction to your lived experience? I feel like they mostly don't matter that much to me.

For the other points, it feels like they could be addressed to some extent by using serde but writing a custom Serializer/Deserializer. That potentially makes the API for users a little bit more idiomatic because you can still use Serialize/Deserialize for the types involved.

[spacejam]

@djc I don't need the genericism though, it's an abstraction that doesn't help me write my functionality any faster. It would also block off a number of optimizations that can only be taken because I have information beyond the type signature of the types used in sled. Take the PageState enum for example. 2 variants, one has between 1 and 16 repeated fields, the other has 0. I can use a single byte to represent both the variant and the length for the repeated item. Generic abstractions block optimization opportunities. After 4 years of building this thing, I'm at the point where these are the optimizations that make big differences. One of the biggest problems in sled right now is that it takes too much space on disk, and there are a ton of great non-generic optimizations I can pursue to fix this.

Storage engines are all about finding generic abstractions and breaking them in the name of performance while staying on the right side of the actual correctness requirements.

I spend a lot of time compiling in fresh directories. I spend a lot of time waiting for sanitizers to build, which need to start fresh, as well as CI, which often doesn't use caches as it should. I don't want users who try out sled to feel like they just made their project a lot slower to build.

I would definitely use serde for the first 4 years all over again, but at this point the genericism stands in the way.

[djc]

Makes sense, thanks for elaborating!