4 ms·
My favourite simple "eviction" algorithm is just to wipe out the entire cache as soon as it gets full. Insertion: %hash = () if keys %hash > 100000; $
by jstanley 3y ago
My favourite simple "eviction" algorithm is just to wipe out the entire cache as soon as it gets full.
Insertion:
%hash = () if keys %hash > 100000;
$hash{$key} = $val;
Retrieval:
return $hash{$key};
Desirable properties include bounded memory usage (assuming bounded size of $val), O(1) (amortised) insertion/retrieval, and (most importantly) it only takes a second to write and there's almost 0 chance of writing it wrong.
The downside is that the mean utilisation is only 50%.
- throwaway143829 3y agoI love the simplicity, but wiping the cache is a no-go for most serious apps.
- jstanley 3y agoIt depends on the application.
- 3np 3y agoIf wiping the cache is a no-go, how do you handle (unexpected) restarts?
- jrockway 3y agoWith a 3 day outage and a status page that says "a small percentage of users are experiencing decreased availability while we investigate a network issue in us-east-1".
- cmrdporcupine 3y agoAnother simple one is to just identify a bunch of completely random candidates for eviction, give them some interval of time for a "second chance" to be used, and if not used in that time, flush them. Has the advantage of lower overhead and simplicity.
- phkahler 3y agoI wonder how that would compare to randomly evicting something.
- rhplus 3y ago"Why does our service slow to a crawl every 5 minutes?"