Sled: typed Trees, letting users avoid deserialization

[spacejam]

We have a nice opportunity to make our values Serializable and stored in their high-level form in cache to help application developers avoid needing to deserialize them every time they pull them out of memory.

https://ai.google/research/pubs/pub48030 talks about a trend happening in large-scale systems to move towards domain-specific caches to avoid network hops and serialization costs.

We can type Trees, defaulting to [u8], but allowing them to be opened using other type parameters. sled users can already avoid network hops. But this would also save them serialization costs and the need to have high-level caches in addition to the built-in pagecache.

[spacejam]

This is a step toward #562

[ehiggs]

This could probably use flat buffers.

[ckaran]

@ehiggs flat buffers don't support i128/u128 directly, which means that there will be types in rust that the typed Trees won't be able to directly support.

[spacejam]

This has been "addressed" via documentation:
https://github.com/spacejam/sled/blob/df81d300c6f3cc8c1ba29ca81d0cf9620641e460/examples/structured.rs

The documentation shows how to achieve this functionality without requiring any changes to the sled core.

[ckaran]

@spacejam I see where you're coming from (too much to do, not enough resources to to it all), but I think that this should be left open and marked to work on at a lower priority. The issue might seem like just a toe-stub level of headache, but IMHO one of the reasons sled is awesome (#950) is because there are so very, very few toe-stubs in it. It's well-polished code that 'just works'. Leaving little things like this lying around detract from that level of polish. Please don't do that.

[spacejam]

@ckaran I think one issue with this is that it is pretty much impossible to design something like this without causing toe-stubs for people. For this in particular, one of the most glaring things is that a Tree may contain any data you want, and for high performance, you often want to group items with different structures together in the same Tree to benefit from cache locality, if they tend to be accessed together. Rather than pulling 3 Tree nodes from disk to view a key from 3 different Trees, you may be able to just do 1 page-in if they all live next to each other on the same Tree node.

So, a Tree can contain data with different schemas. That raises the question of "typed IVec" which can be viewed in any form that people may want. I may consider bridging serde::Serialize with sled::Serialize and providing IVec::view_as<'de, T: serde::Deserialize<'de>> (not DeserializeOwned though, since we want to avoid making copies).

I'll open another issue for IVec::view_as, since I see that as more likely.

[ckaran]

For this in particular, one of the most glaring things is that a Tree may contain any data you want, and for high performance, you often want to group items with different structures together in the same Tree to benefit from cache locality.

Good point! I hadn't thought about that.