This adds time-to-keep expiration to the LRUCacheWithDelete.
Besides the other ledgers of the backing cache, on every write operation the update time is saved in a fixed-sized array. No other speed or memory overhead is required for regular operations: most importantly, that means there is no age verification on read. Customer must periodically call the expire method, which evicts items older than the time-to-keep.
Our use case is a 15-minute time-to-keep on caches of 64k capacity, where we can tolerate a modest slop in expiration and small periodic expiry sweeps. The benchmark script demonstrates a 1M-element cache with a 10s ttk being expired every 2 seconds, spending 50-60ms on each expiry sweep. I don't know what use case would need those extremes but there you go.
Limitations:
The time-to-live (maximum age of any record returned in a read operation) has only the weak guarantee of (time-to-keep + maximum-delay-between-expires).
The expire operation must be done as a whole, and this does not offer to do it in a separate thread or make any attempt to be thread safe. However, the benchmarks in benchmark/lru-cache show that a full delete of every item in a 30,000 element cache runs in less than 10ms on a 2019 Macbook Pro.
Having two expire operations scheduled in the same thread should be harmless but would give no speedup, so if you found yourself in a situation where the expire was taking significant time it could be big trouble.
Due to floating-point shenanigans a custom clock returning fractional times may behave unexpectedly
Alternatives considered and discarded:
Rather than walking the full length of the age ledger (or linked list), keep a data structure (heap?) to reveal only the expirable records. This could shorten expiry times in general but I'd worry that if there was a large batch to expire the time spent grooming the heap could swamp the typical-case savings.
Maintain two or more generations of cached items, rotating then at ttl/2. (write to both, read from the new generation falling back to the old generation, and on each expire discard the oldest generation and add a new empty cache). This would make expiry O(1), with low impact on individual operations but a notable tradeoff in cache efficiency.
Checking the age on read would significantly impact the read performance.
Potential Opportunities for improvement:
Reduce the memory footprint of the age ledger by chunking the timestamps to bytes or words. In the case of byte (256 age bins), a 10-minute ttk, and otherwise default parameters, an expire operation would discard everything older than (ttk - ttk/64) (guaranteeing the ttk but reaping an additional 1.5% of records). Expire must be called at least once every 2 * ttk (20 minutes) or the newest records would be indistinguishable from the oldest records. (Everything would work but it would be a damn shame for cache efficiency). A word-sized (64k bins) ledger makes the tradeoffs minimal, but offering both choices shouldn't be a problem.
For every record it expires we independently call delete, which doctors the read-age linked list. It may make more sense to walk the linked list. I stubbed that out but would value guidance on how to do surgery on the list as it is traversed.
The commit history here is a hot mess that includes and crosses with the other PR on profiling. I'll reorganize with squashed commits once I button things up.
This adds time-to-keep expiration to the LRUCacheWithDelete.
Besides the other ledgers of the backing cache, on every write operation the update time is saved in a fixed-sized array. No other speed or memory overhead is required for regular operations: most importantly, that means there is no age verification on read. Customer must periodically call the expire method, which evicts items older than the time-to-keep.
Our use case is a 15-minute time-to-keep on caches of 64k capacity, where we can tolerate a modest slop in expiration and small periodic expiry sweeps. The benchmark script demonstrates a 1M-element cache with a 10s ttk being expired every 2 seconds, spending 50-60ms on each expiry sweep. I don't know what use case would need those extremes but there you go.
Limitations:
The time-to-live (maximum age of any record returned in a read operation) has only the weak guarantee of
(time-to-keep + maximum-delay-between-expires).The expire operation must be done as a whole, and this does not offer to do it in a separate thread or make any attempt to be thread safe. However, the benchmarks in
benchmark/lru-cacheshow that a full delete of every item in a 30,000 element cache runs in less than 10ms on a 2019 Macbook Pro.Having two expire operations scheduled in the same thread should be harmless but would give no speedup, so if you found yourself in a situation where the expire was taking significant time it could be big trouble.
Due to floating-point shenanigans a custom clock returning fractional times may behave unexpectedly
Alternatives considered and discarded:
Potential Opportunities for improvement:
Reduce the memory footprint of the age ledger by chunking the timestamps to bytes or words. In the case of byte (256 age bins), a 10-minute ttk, and otherwise default parameters, an expire operation would discard everything older than (ttk - ttk/64) (guaranteeing the ttk but reaping an additional 1.5% of records). Expire must be called at least once every
2 * ttk(20 minutes) or the newest records would be indistinguishable from the oldest records. (Everything would work but it would be a damn shame for cache efficiency). A word-sized (64k bins) ledger makes the tradeoffs minimal, but offering both choices shouldn't be a problem.For every record it expires we independently call delete, which doctors the read-age linked list. It may make more sense to walk the linked list. I stubbed that out but would value guidance on how to do surgery on the list as it is traversed.
The commit history here is a hot mess that includes and crosses with the other PR on profiling. I'll reorganize with squashed commits once I button things up.