All right, I'm sure this is a duplicate of a question somewhere, but I can't find it.
My problem seems so easy on paper, and yet here am I writing this.
So, I have written my own caching system. It's 99% done. I'm lacking the last piece of the puzzle : let the system decide wether it's "profitable" (time wise) to load from the cache or not.
I have 4 variables :
hit : counter of successful loads from cache
miss : counter of unsuccessful loads from cache
time_check : the average time it takes to load from the cache (hit and time_check are updated at the same time)
time_generate : the average time it takes to generate the page from scratch (miss and time_generate are updated at the same time)
From there, my problem sounds easy. I need to figure out a formula or a set of if-elses conditions to decide wether to attempt a load from the cache or not.
It is safe to assume the variables are already there because the algorithm will run only after at least 100 page loads.
One important thing to take into account, is that if the algorithm decides to load from the cache and it MISSES, the overall loading time will be time_check + time_generate!
Aaaand... From there I don't know how I should do it.
I need the system to take the right decision for loading content from the cache according the the probability of getting an actual time gain.
I can already say right from the start that if time_generate < time_check, we should not use the cache no matter what hit and miss are. But then, for the rest, I am getting confused.
By any chance, does anyone reading this has a flash brain and is able to immediately understand what I am looking for? :)
I spent some serious amount of time thinking about this, and after numerous attempts I have finally found an answer that satisfies my needs. In case anyone needs it:
Skipping all the calculations and simplifications, the end formula is:
minimum hit rate % = time_check / time_generate
I guess you could somehow find it from the other replies here.
Next, from that base formula we need to distort time to penalize higher times. That is because, in statistics and probabilities, loosing 2.5s over 3.5s is identical to losing 250s over 350s. However, that is not how we "feel" time. We're way more willing to bet to loose 2.5s rather than 250s. If we're betting to loose 250s over 350s, we would expect a very high hit rate. And if we're betting to loose 2.5s over 3.5s: "I mean, it's only 2.5s so it's not that much of an issue, let's try it anyway".
I have tried a lot of options based on random attempts but the one that I kept in the end is:
minimum hit rate % = arctan(time_check/100) / arctan(time_generate/100)
I don't have any justification for it, it just works best for my needs. It is also adaptable by changing the denominator. /50 will make it stricter (higher hit rate required) and /150 will make it more flexible (less hit rate required). It suits all range of values and gives quite expectable results.
I guess it all depends on your particular configuration, here are the other time distorting options I have tried and their issues:
- time_check² / time_generate² [too loose on high distanced values]
- time_check ^ 0.1 / time_generate ^ 0.1 [too strict overall]
- 1.05 ^ time_check / 1.05 ^ time_generate [way too strict overall]
- 1.1 ^ time_check / 1.1 ^ time_generate [way too loose on high distanced values]
- log2(time_check) / log2(time_generate) [not suited for values of 1 and below]