6 ms·
Note: In most cases you don't want to split pages prior to insertion as is being done here. Instead, you want to insert data first, and then restore the page s
by cperciva 3y ago
Note: In most cases you don't want to split pages prior to insertion as is being done here. Instead, you want to insert data first, and then restore the page size invariants at the end (prior to committing the operation / writing to disk / etc). If you're doing multiple operations at once (e.g. adding new keys and deleting others) it may turn out that you can avoid the expensive page-splitting operation by postponing it.
- koverstreet 3y agoNo, you don't. That'll add expensive memory reallocations; it may let you avoid the split operation but then that isn't worth it because you've added a nasty performance cliff to your insert case - you'll either be doing the memory allocation repeatedly, or you'll waste a ton of memory when your buffer is bigger than your on disk node size.
- cperciva 3y agoFor my workload it's optimal to keep working nodes deserialized anyway. YMMV but what I'm doing gets me over a million operations per second -- 1 Gbps of requests -- on a single CPU so I don't think I'm going far wrong. EDIT: I just noticed you're the bcachefs author. I'm guessing you're dealing with much larger key/value pairs than I am (40+40)?
- 7e 3y agoWell, bcachefs is currently the slowest of all Linux filesystems.
- 7e 3y agoSee https://www.phoronix.com/review/bcachefs-linux-67 https://www.phoronix.com/review/bcachefs-linux-67.
- magicalhippo 3y agoProbably more interesting to consider the follow-up article[1] after some debug code was disabled and such. [1]: https://www.phoronix.com/review/bcachefs-benchmarks-linux67 https://www.phoronix.com/review/bcachefs-benchmarks-linux67
- koverstreet 3y agoNo, that's a typical size for bcachefs as well. But I've had to optimize for memory usage, performance when working set does not fit into ram - we also don't have a serialize/deserialize step, that will really hurt you when working set doesn't fit in ram. You want to validate when you're reading in a btree node, but you want to keep that as cheap as possible. For avoiding the serialize/deserialize, the thing to use now would be Cap'n Proto.
- cperciva 3y agoAh, that would explain it. Yeah, I have a total datastore size which is out of core, but the working set is generally in core... partly because I can use all the RAM on the system if I want to, whereas filesystems are (usually!) expected to occupy just a portion of the system memory. FWIW, my "deserialize" doesn't involve copying all the data -- I just construct pointers into the (serialized) page. Serializing has to copy data though.
- valenterry 3y agoJust wanted to say, I really enjoyed reading your guys conversation, since I barely never do low-level optimizations like that. Very interesting, thanks for sharing your thoughts!
- apavlo 3y ago> No, you don't. This is correct. Most disk-oriented DBMSs use fixed-size pages. So you can't go larger than the node size (not entirely true if using auxiliary data structures to buffer changes like an inefficient -epsilon tree).
- ayende 3y agoThat assumes that you are actually doing all the work in a side buffer? The way we do it, all the operations are done on the actual buffers of the tree, so there is no actual way _to_ have more space (even temporarily). This way, you avoid extra allocation, copying, etc.
- cperciva 3y agoThe only time I copy data (or keys for that matter) is when I'm constructing the new serialized page(s). All the rest of the work is done with pointers into the old page or the request structures.