On Thursday, Jul 17, 2003, at 12:48 America/Guayaquil, Berin Loritsch
wrote:
> Berin Loritsch wrote:
>
>> The concept translates over to the adaptive cache approach at almost
>> 1:1.
>> The actual individual cost sample is not important. It is the
>> windowed average
>> that is important. For our cache a simple mean would best suit our
>> problem
>> space. The size of the window for our samples will control how
>> responsive
>> our cache control algorithm is. This would affect your cache
>> prediction
>> algorithm as the value k is no longer needed to control
>> responsiveness. The
>> value k can be set at 0, 1, or 0.5 depending on how you want to
>> affect the
>> slope. IMO, the window size should be the determining factor at how
>> the average
>> cost for a resource will converge toward the optimal point. Large
>> window sizes
>> provide slower response, while a smaller window provides faster
>> response.
>
>
> BTW. If we use "0" for the value of "k", then the cache prediction
> algorithm
> as is defined by your "discriminate caching" sequence would be a purely
> random result. The c(eff) function would solve down to the constant
> 0.5,
> and since we discriminate based on a randomly generated number being
> less
> than the result of the function, we have a 50/50 chance
> (theoretically) that
> the random number would be greater than 0.5. I say theoretcially
> because
> not all random number generators are truly random, or even mostly
> random.
>
> If we use "1" for the value of "k", then the prediction algorithm
> follows
> the efficiency value much better. There is a higher chance of having a
> higher number for the cache prediction, which means we will be
> evaluating
> more entries. In fact, as the value for "eff" reaches +/38, we will
> always
> be caching because the result of the equation will always be 1.
>
> If we use "0.5" for the value of "k", then the prediction algorithm
> still
> follows the efficiency value, but our range is now to +/76.
You analysis is fully correct.
> The question then is, where statistically will this efficiency
> algorithm be all the time?
The idea behind such a design is that if a resource has been efficient
(remember that efficiency in this context means "how much costs we
saved so far on that resource") the chance of avoiding caching should
be very small because it's very likely that the noncached version will
be much less efficient. Of course, the same is true for negative
efficiencies (means that the cache is inefficient on those resources).
The important concept is that even if the cache is very efficient on
that resource (thus efficiency is positive and high), we will be
sampling the other side of the fence to understand if its behavior has
changed.
Imagine the peakhour case: the efficiency for a particular resource
is, for example 50 (means that by "not caching" we saved 50 cost units
[the dimension of which depends on the cost function]), this gives us,
roughly a 99% probability of avoid caching that resource. But on that
one request, we find out that caching effiency for that single resource
was +5.
This changes the overall efficiency to 45, thus increasing the chance
of caching to 1.5% (I'm making up the numbers but you get my point).
The next cached request, another +5 cost units are saved, turning into
40 and the caching change to 2%.
If the caching trend continues, the efficiency will eventually swing
positive, changing the caching behavior adaptively.
If the caching trend was just occasional, this will be simply a
perturbation that will be absorbed by the adaptivity of the system.
The hard thing to sell in this algorithm is that even if you *know*
that you are going to be inefficient on a particular resource, you are
going to be, in order to obtain information on *whether* of not your
prediction was right.
This tradeoff seems like a sin to the eyes of many and I believe that
it is exactly this vision that prevented truly adaptive caches to be
tested.
But, of course, I might be completely wrong.

Stefano.
