LRU algorithm and performance

Hi Squiders,

I have been running squid (currently 1.1.22 on different Linuxes)
successfully for a long time and have seen many helpful discussions on
performance, memory and the LRU cache algorithm. Today I would like to share
some experiences with you that can really help with tuning the cache and
might be of interest for the developers working on 1.2.

First a bug report : while the "reference age" works as advertised, squid
uses 0 as a default and not 365 days as squid.conf states.

Back in the early 80´s when I was a programmer I implemented LRU using
doubly linked lists. I think it is an efficient way for any number of
entries, but maybe this was thought to be impractical for hundreds of
thousands of objects.

However with the current implementation there are some design deficiencies
that are difficult to see. You may have noticed (from cachemgr.cgi) that the
LRU expiration age varies widely over time. This should not happen. In any
given period of time the amount of objects stored in the cache should equal
the amount of objects purged, and only smaller adjustments to the LRU age
should be needed.

Since squid scans the storage table over the course of a day while traffic
patterns peak during some hours, during these hours the LRU age goes down
significantly, since objects arrive much faster than sufficiently old
objects are found for purging. This gets worse for us poor guys who reload
squid every night because of the growing memory problem, as this means that
peak traffic hits the same store buckets every day. So I hacked store.c to
scan the storage table every 1 second instead of 10 seconds. Interestingly
enough this also significantly brought down the load average on my machine.

result # 1 : Store objects are scanned much faster for expiration than new
objects arrive in the cache, making the algorithm act smoother.

Another problem that makes the LRU ages vary is the handling of larger
objects. Lets first assume that squid runs on default values. This means we
have a distance of 5 MB between the high and low water marks and a maximum
object size of 8 MB. Every larger object brings the cache over the high
water mark, the LRU age drops to about 0 and the algorithm becomes something
like random replacement.

Once such an object becomes purged from the cache, the LRU value rises to
the reference age and no objects are purged for some time. This behaviour
effectively keeps smaller objects longer in the cache, resulting in a larger
number of cache objects, additional memory requirements and a performance
penalty.

These problems can be overcome by making the distance between the low and
high water mark much larger than one day worth of traffic. I suggest setting
the refererence age at a realistic value, just some weeks over the typical
LRU age.

Result #2 : the LRU age does not drop significantly below its average, the
number of store objects is reduced, the cache contents always stays near
above the low water mark.

Suggestion : the LRU algorithm could get still smoother if the calculation
of total storage contents would include the current size of objects
currently being loaded from the web as this would make room in advance for
those objects.

My results of these measures were improved performance, improved hit rates
and 8 % less objects in the cache.

My settings :

store.c :
        store_buckets = 7951, store_maintain_rate = 1; /* 10 */

squid.conf :
cache_swap 2500
cache_swap_low 80
cache_swap_high 100
maximum_object_size 32768
reference_age 50 days

LRU age is at about 28 days
Storage size is at 2024 MB

Let me know what you think.

Developers : if you have read this far, are there some useful ideas (at
least for squid.conf) ?

I would be glad if some of you could make use of this information as I did
from previous postings.

Gero

-----------------------------------------------------------
--- Ammirati Puris Lintas ---
--- Gero Dittmer, Mittelweg 177, 21048 Hamburg, Germany ---
--- phone: +49 40 41441217 fax: +49 40 41441616 ---
--- Email: Gero.Dittmer@hamburg.aplnet.com ---
--- ... waiting for a unicorn under chapter eleven ... ---
Received on Wed Sep 02 1998 - 06:55:24 MDT