~rousskov/squid/3p2-plus

Viewing all changes in revision 10851.

  • Committer: Alex Rousskov
  • Date: 2011-04-05 22:18:20 UTC
  • Revision ID: rousskov@measurement-factory.com-20110405221820-6fazfzh9vz3zjg2u
Balance SMP workers load by raising one worker accept priority per second.

SMP workers are known to consume significantly different CPU time when the
load cannot keep all workers busy. For example, here are the total CPU time
results (plus CPU core IDs) from a 1M-transaction test with seven workers:

 6:32 2 squid            
 5:31 7 squid            
 4:03 5 squid            
 2:42 4 squid            
 1:06 6 squid            
 0:19 1 squid            
 0:11 3 squid            

The overall imbalance stems from the fact that most workers often have nothing
to do but to wait for the next TCP connection. When the next connection
arrives, the worker that can accept(2) the connection first, gets to service
it. Since all workers are about the same, the first worker to wake up from
epoll(2) waiting wins.

The shared listening descriptor inside the OS kernel has a queue of waiting
workers.  When the new connection arrives, all waiting workers are awaken (via
their epoll_wait(2) calls), in the kernel-determined order. Apparently, that
order is LIFO: the last worker to be placed in the wait queue is the one to be
awaken first.

The new "load balancing" code that gets activated every second and changes the
listening queue order. During N-th second, N-th worker becomes the first in
the queue and will most likely get more work. With time, every worker gets
similar number of chances to be the busiest and the idlest one, leveling the
load:

 3:15 2 squid            
 2:58 3 squid            
 2:43 6 squid            
 2:43 4 squid            
 2:34 1 squid            
 2:32 7 squid            
 2:17 5 squid            

This specific algorithm seems to do a somewhat better job than some simpler
schemes we have tried (e.g., change workers order every time Squid accepts a
connection), possibly because it does not reshuffle workers at semi-random
times, which may lead to groups of busier and "idler" workers.

When a worker has multiple listening ports, all ports are moved to the front
of their respective queues. We have tried moving just one port at a time, but
that more complex algorithm did not produce significantly better results in
short tests.


There are other, secondary factors such as CPU affinity and shared CPU core
caches. We are ignoring them for now, but they probably contribute to the
uneven CPU time distribution among workers even when this load balancing
algorithm is in place.


This change works in epoll-based environments only.

expand all expand all

Show diffs side-by-side

added added

removed removed

Lines of Context: