Squid_ The Definitive Guide - Duane Wessels [59]
Squid has two of these cache_dir selection algorithms. The default algorithm is called least-load; the alternative is round-robin.
The least-load algorithm, as the name implies, selects that cache directory that currently has the smallest workload. The notion of load depends on the underlying storage scheme. For the aufs, coss, and diskd schemes, the load is related to the number of pending operations. For ufs, the load is constant. For cases in which all cache_dirs have equal load, the algorithm uses free space and maximum object sizes as tie-breakers.
The selection algorithm also takes into account the max-size and read-only options. Squid skips a cache directory if it knows the object size is larger than the limit. It also always skips any read-only directories.
The round-robin algorithm also uses load measurements. It always selects the next cache directory in the list (subject to max-size and read-only), as long as its load is less than 100%.
Under some circumstances, Squid may fail to select a cache directory. This can happen if all cache_dirs are overloaded or if all have max-size limits less than the size of the object. In this case, Squid simply doesn't write the object to disk. You can use the cache manager to track the number of times Squid fails to select a cache directory. View the store_io page (see Section 14.2.1.41), and find the create.select_fail line.
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