10.10 Putting It All Together

As you probably realize by now, Squid has many different ways to decide how and where requests are forwarded. In many cases, you can employ more than one protocol or technique at a time. Just by looking at the configuration file, however, you'd probably have a hard time figuring out how Squid uses the different techniques in combination. In this section I'll explain how Squid actually makes the forwarding decision.

Obviously, it all starts with a cache miss. Any request that is satisfied as an unvalidated cache hit doesn't go through the following sequence of events.

The goal of the selection procedure is to create a list of appropriate next-hop locations. A next-hop location may be a neighbor cache or the origin server. Depending on your configuration, Squid may select up to three possible next-hops. If the request can't be satisfied by the first, Squid tries the second, and so on.

10.10.1 Step 1: Determine Direct Options

The first step is to determine if the request may, must, or must not be sent directly to the origin server. Squid evaluates the never_direct and always_direct access rule lists for the request. The goal is to set a flag to one of three values: DIRECT_YES, DIRECT_MAYBE, or DIRECT_NO. This flag later determines whether Squid should, or should not, try to select a neighbor cache for the request. Squid checks the following conditions in order. If any condition is true, it sets the direct flag and proceeds to the next step. If you're following along in the source code, this step corresponds to the beginning of the peerSelectFoo( ) function:

  1. Squid looks at the always_direct list first. If the request matches this list, the direct flag is set to DIRECT_YES.

  2. Squid looks at the never_direct list next. If the request matches this list, the direct flag is set to DIRECT_NO.

  3. Squid has a special check for requests that appear to be looping. When Squid detects a forwarding loop, it sets the direct flag to DIRECT_YES to break the loop.

  4. Squid checks the minimum_direct_hops and minimum_direct_rtt settings, but only if you've enabled netdb. If the measured hop count or round-trip time is lower than the configured values, Squid sets the direct flag to DIRECT_YES.

  5. If none of the previous conditions are true, Squid sets the direct flag to DIRECT_MAYBE.

If the direct flag is set to DIRECT_YES, the selection process is complete. Squid forwards the request directly to the origin server and skips the remaining steps in this section.

10.10.2 Step 2: Neighbor Selection Protocols

Here Squid uses one of the hierarchical protocols to select a neighbor cache. As before, once Squid selects a neighbor in this step, it exits the routine and proceeds to Step 3. This step roughly corresponds to the peerGetSomeNeighbor( ) function:

  1. Squid examines the neighbor's Cache Digests. If it indicates a hit, that neighbor is placed on the next-hop list.

  2. Squid tries CARP if enabled. CARP always succeeds (i.e., selects a parent), unless the cache_peer_access or cache_peer_domain rules forbid communication with any of the parent caches for a particular request.

  3. Squid checks netdb measurements (if enabled) for a "closest parent." If Squid knows that the round-trip time from one or more parents to the origin server is less than its own RTT to the origin server, Squid selects the parent with the least RTT. For this to happen, the following conditions must be met:

    • Both your Squid and the parent cache(s) must have enabled netdb measurements.

    • query_icmp must be enabled in your configuration file.

    • The origin server must respond to ICMP pings.

    • The parent(s) must have previously measured the RTT to the origin server and returned those measurements in ICP/HTCP replies, or through a netdb exchange.

  4. Squid sends ICP/HTCP queries as the last resort. Squid loops through all neighbors and checks a number of conditions. Squid doesn't query a neighbor if:

    • The direct flag is DIRECT_MAYBE and the request is nonhierarchical (see Section 10.4.5). Because Squid is allowed to go directly to the origin server, it doesn't bother the neighbor with this request, which is likely to be uncachable.

    • The direct flag is DIRECT_NO, the neighbor is a sibling, and the request is nonhierarchical. Because Squid is forced to use a neighbor, it only queries parents, which can always handle a cache miss.

    • The cache_peer_access or cache_peer_domain rules forbid sending this request to the neighbor.

    • The neighbor's no-query flag is set, or its ICP/HTCP port number is zero.

    • The neighbor is a multicast responder.

  5. Squid counts how many queries it sends and calculates how many replies to expect. If it expects at least one reply, the rest of the next-hop selection procedure is postponed until the replies arrive, or a timeout occurs. Squid expects to receive replies from neighbors that are alive, but not neighbors that are dead (see Section 10.3.2).

10.10.3 Step 2a: ICP/HTCP Reply Processing

If Squid sends out any ICP or HTCP queries, it waits for some number of replies. Just after transmitting the queries, Squid knows how many replies to expect and the maximum amount of time to wait for them. Squid expects a reply from every alive neighbor queried. If you're using multicast, Squid adds the current group size estimate to the expected reply count. While waiting for replies, Squid schedules a timeout, in case one or more of the replies don't arrive.

When Squid receives an ICP/HTCP reply from a neighbor, it takes the following actions:

  1. If the reply is a hit, Squid forwards the request to that neighbor immediately. Any replies arriving after this point are ignored.

  2. If the reply is a miss, and it is from a sibling, it is ignored.

  3. Squid doesn't immediately act on ICP/HTCP misses from parents. Instead, it remembers which parents meet the following criteria:

    The closest-parent miss

    If the reply includes a netdb RTT measurement, Squid remembers the parent that has the least RTT to the origin server.

    The first-parent miss

    Squid remembers the parent that had the first reply. In other words, the parent with least RTT to your cache. Two cache_peer options affect this part of the algorithm: weight=N and closest-only.

    The weight=N option makes a parent closer than it really is. When calculating RTTs, Squid divides the actual RTT by this artificial weight. Thus you can give higher preference to certain parents by increasing their weight value.

    The closest-only option disables the first-parent miss feature for a neighbor cache. In other words, Squid selects a parent (based on ICP/HTCP miss replies) only if that parent is the closest to the origin server.

  4. If Squid receives the expected number of replies (all misses), or if the timeout occurs, it selects the closest-parent miss neighbor if set. Otherwise, it selects the first-parent miss neighbor if set.

Squid may not receive any ICP/HTCP replies from parent caches, either because they weren't queried or because the network dropped some packets. In this case, Squid relies on the secondary parent (or direct) selection algorithm described in the next section.

If the ICP/HTCP query timeout occurs before receiving the expected number of replies, Squid prepends the string TIMEOUT_ to the result code in access.log.

10.10.4 Step 3: Secondary Parent Selection

This step is a little tricky. Remember that if the direct flag is DIRECT_YES, Squid never executes this step. If the flag is DIRECT_NO, Squid calls the getSomeParent( ) function (described subsequently) to select a backup parent, in case Step 2 failed to select one. Following that, Squid adds to the list all parents it believes are alive. Thus, it tries all possible parent caches before returning an error message to the user.

In the case of DIRECT_MAYBE, Squid adds both a parent cache, and the origin server. The order, however, depends on the prefer_direct setting. If prefer_direct is enabled, Squid inserts the origin server into the list first. Next, Squid calls getSomeParent( ) if the request is hierarchical or if the nonhierarchical_direct directive is disabled. Finally, Squid adds the origin server last if prefer_direct is disabled.

The getSomeParent( ) function selects one of the parents based on the following criteria. In each case, the parent must be alive and allowed to handle the request according to the cache_peer_access and cache_peer_domain rules:

  • The first parent with the default cache_peer option

  • The parent with the round-robin cache_peer option that has the lowest request count

  • The first parent that is known to be alive

10.10.5 Retrying

Occasionally, Squid's attempt to forward a request to an origin server or neighbor may fail for one reason or another. This is why Squid creates a list of appropriate next-hop locations during the neighbor selection procedure. When one of the following types of errors occurs, Squid can retry the request at the next server in the list:

  • Network congestion or other errors can cause a "connection timeout."

  • The origin server or neighbor cache may be temporarily unavailable, causing a "connection refused" error.

  • A sibling may return a 504 (Gateway Timeout) error if the request would cause a cache miss.

  • A neighbor may return an "access denied" error message if the two caches have a mismatch in access control policies.

  • A read error may occur on an established connection before Squid reads the HTTP message body.

  • There may be race conditions with persistent connections.

Squid's algorithm for retrying failed requests is relatively aggressive. It is better for Squid to keep trying (causing some extra delay), rather than return an error to the user.

    Appendix A. Config File Reference