This PR introduces changes to make the features of [#47] more efficient. We were too aggressive on two fronts:
Trying to find a clean entry to evict: Previously, we tried to go through the entire cache to find a clean entry to evict. This can be very inefficient in a mostly-dirty cache, since we need to perform atomic clock increments and atomic priority decrements for each cache entry we examine. We now only search ahead by a fixed window, kDefaultEvictionLookahead, currently set to 32 (This could be one parameter to play around with).
Guessing how many entries will be batched: We use the range scan code to batch records for write out. Within it, the ART range scan implementation accepts a fixed-size array, so we have to make an initial guess about the scan length. This parameter was set to 100, with the length of the YCSB E scans in mind. However, when batching records for write-out, this is a huge over-estimate. For 1K records, there will be max 3 per page, so we were going through ART and locking 100 records only to the unlock at least 97 of them. We now use different parameters when the user requests a scan (kDefaultUserSubScan = 64) vs when this function is used during writeout (kDefaultWriteOutSubScan =4).
With these changes, cond run //scripts/e2e_custom/ycsb_v2:preload-synth-pg_llsm-1024B takes a bit over 3m to finish on berners-lee.
This PR also introduces some additional updates:
Update llsm_interface.h to create correct copies of the keys before calling BulkLoad() (follow up to [#39])
Adds a test for updates beyond the cache capacity, used to disambiguate correctness vs. performance bugs in the context addressed by this PR.
This PR introduces changes to make the features of [#47] more efficient. We were too aggressive on two fronts:
Trying to find a clean entry to evict: Previously, we tried to go through the entire cache to find a clean entry to evict. This can be very inefficient in a mostly-dirty cache, since we need to perform atomic clock increments and atomic priority decrements for each cache entry we examine. We now only search ahead by a fixed window,
kDefaultEvictionLookahead, currently set to 32 (This could be one parameter to play around with).Guessing how many entries will be batched: We use the range scan code to batch records for write out. Within it, the ART range scan implementation accepts a fixed-size array, so we have to make an initial guess about the scan length. This parameter was set to 100, with the length of the YCSB E scans in mind. However, when batching records for write-out, this is a huge over-estimate. For 1K records, there will be max 3 per page, so we were going through ART and locking 100 records only to the unlock at least 97 of them. We now use different parameters when the user requests a scan (
kDefaultUserSubScan = 64) vs when this function is used during writeout (kDefaultWriteOutSubScan =4).With these changes,
cond run //scripts/e2e_custom/ycsb_v2:preload-synth-pg_llsm-1024Btakes a bit over 3m to finish onberners-lee.This PR also introduces some additional updates:
llsm_interface.hto create correct copies of the keys before callingBulkLoad()(follow up to [#39])cc: @andreaskipf @geoffxy