7.5 Replacement Policies

The cache_replacement_policy directive controls the replacement policy for Squid's disk cache. Version 2.5 offers three different replacement policies: least recently used (LRU), greedy dual-size frequency (GDSF), and least frequently used with dynamic aging (LFUDA).

LRU is the default policy, not only for Squid, but for most other caching products as well. LRU is a popular choice because it is almost trivial to implement and provides very good performance. On 32-bit systems, LRU uses slightly less memory than the others (12 versus 16 bytes per object). On 64-bit systems, all policies use 24 bytes per object.

Over the years, many researchers have proposed alternatives to LRU. These other policies are typically designed to optimize a specific characteristic of the cache, such as response time, hit ratio, or byte hit ratio. While the research almost always shows an improvement, the results can be misleading. Some of the studies use unrealistically small cache sizes. Other studies show that as cache size increases, the choice of replacement policy becomes less important.

If you want to use the GDSF or LFUDA policies, you must pass the enable-removal-policies option to the ./configure script (see Section 3.4.1). Martin Arlitt and John Dilley of HP Labs wrote the GDSF and LFUDA implementation for Squid. You can read their paper online at http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html. My O'Reilly book, Web Caching, also talks about these algorithms.

The cache_replacement_policy directive is unique in an important way. Unlike most of the other squid.conf directives, the location of this one is significant. The cache_replacment_policy value is actually used when Squid parses a cache_dir directive. You can change the replacement policy for a cache_dir by setting the replacement policy beforehand. For example:

cache_replacement_policy lru

cache_dir ufs /cache0 2000 16 32

cache_dir ufs /cache1 2000 16 32

cache_replacement_policy heap GDSF

cache_dir ufs /cache2 2000 16 32

cache_dir ufs /cache3 2000 16 32

In this case, the first two cache directories use LRU replacement, and the second two use GDSF. This characteristic of the replacement_policy directive is important to keep in mind if you ever decide to use the config option of the cache manager (see Section 14.2.1.7). The cache manager outputs only one (the last) replacement policy value, and places it before all of the cache directories. For example, you may have these lines in squid.conf:

cache_replacement_policy heap GDSF

cache_dir ufs /tmp/cache1 10 4 4

cache_replacement_policy lru

cache_dir ufs /tmp/cache2 10 4 4

but when you select config from the cache manager, you get:

cache_replacement_policy lru

cache_dir ufs /tmp/cache1 10 4 4

cache_dir ufs /tmp/cache2 10 4 4

As you can see, the heap GDSF setting for the first cache directory has been lost.