mirror of
https://github.com/clockworklabs/SpacetimeDB.git
synced 2026-06-27 08:18:48 -04:00
Phoebe Goldman
29b21cc1b1
# Description of Changes Reviving a previous patch I wrote during our (internal) TPCC experimentation. This has become important because, in addition to its performance implications, it makes row insertion locations deterministic regardless of datastore restarts, which previously they were not. Previously, restarting the datastore would re-order the `non_full_pages` list (i.e. sort it by increasing `PageIndex`, where normally it was not sorted), meaning that which page a new row would be inserted into depended on when the datastore was last restarted. With this patch, that is not the case: the `non_full_pages` are always kept in a deterministic order, so which page a new row goes into is also deterministic. Original commit message follows: And sort them by number of available var-len granules. This prevents an accidentally quadratic behavior where, for a table where the average row contains many var-len granules, after inserting a large number of rows, there would be a large number of pages in `non_full_pages` each of which had enough space for at least one fixed-len row part, but insufficient space for an actual row in practice due to insufficient var-len granules. Each insertion would then do a linear scan over `non_full_pages` before either inserting into the last page or allocating a new page which went to the end. Now, non-full pages are stored in a `BTreeSet` sorted by the number of free var-len granules, and the search for a useable page is done with a `BTreeSet::range` iterator for only the pages with enough granules. I think there may still be an off-by-one-ish bug here, where a page may have enough bytes in the gap that it could either store the fixed-len part or the var-len granules, but not both, but this fix hopefully will suffice for now. # API and ABI breaking changes N/a # Expected complexity level and risk 2? Table code is a bit fiddly, and this path is performance-sensitive when inserting rows. # Testing - [x] Passes table crate tests. - [x] Was included in our internal TPCC experimentation, where it significantly improved performance (due to that benchmark exercising the accidentally-quadradic behavior this patch is designed to protect). - [x] Joshua ran the keynote-2 benchmarks with this patch and did not observe a decrease in throughput.
⚠️ Internal Crate ⚠️
This crate is intended for internal use only. It is not stable and may change without notice.