King Rat (gkr) wrote,
King Rat

June 2002 IEEE Computer

Really interesting article titled Efficient Replacement of Nonuniform Objects in Web Caches by Hyokyung Bahn, Kern Koh, Sam H Noh and Sang Lyul Min. Mostly it's interesting to me not because of web caching, but because it has a 2 page sidebar describing replacement algorithms for caching. I haven't seen a good compilation ever. I don't know what algorithm we use in our software, but it might be a good idea to review it to see how useful it is. We have pretty much one class used as a base for all our caching. Because it exists, most of our developers simply use it so they don't have to re-write anything. Of course, I don't think we ever check to see if the algorithm is efficient for the new uses.

LRU (least recently used)
Removes the least recently referenced object first.
LFU (least frequently used)
Removes the least frequently referenced object first.
Removes the largest object first
Removes the least recently referenced object whose size is larger than desired free space of size s. If enough space is not freed, LRU-min sets s to s/2 and repeats the procedure until enugh space has been freed.
Value(i) = (ts + p/bs) (ni)q/si,, where ts is the estimated latency required to open a connection to server s, bs is the estimated bandwidth of the connection, ni is the number of references made to object i since it has been brought into the cache, and si is the size of the object i; p and q are constants.
LNC-R-W3 (least normalized cost replacement)
Value(i) = [k/tc - tk)] x (ci/si) x si-1.3 where ci is the cost to fetch an object i to the cache si is the size of object i, tc is the current time, and tk is the time of the k-th reference. LNC-R-W3 first considers all objects having just one reference sample in their Value order, then all objects with two reference samples, and so on.
LRV (lowest relative value)
Not noting the algorithms anymore. They are getting more complicated to type. Reference Rizzo and Vicisano. Replacement policies for a proxy cache.
GD-size (greedy-dual size)
reference Cao and Irani. Cost-aware WWW proxy caching algorithms
sw-LFU (server weighted LFU)
reference T.P. Kelly et. al. Biased replacement policies for web caches: differential quality of service and aggregate user value
reference Niclausse, Liu and Nain. A new and efficient caching policy for the world wide web
SLRU (size-adjusted LRU)
Aggarwal, Wolf and Yu. Caching on the world wide web

As we aren't caching web pages exactly, should look into other algorithms as well.

Article The Agile Methods Fray has nice quote on the anti-agile methods side: Agile methods are just hacking by another name.

You might like this one wingedelf: XP training is a necessary but not sufficient condition for succcess in XP. Did you get training?

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened