> srand(time ^ $$); # or some reasonably unique seed
> for ($tries = 1; $tries < $retries; $tries++) {
> ...
> # didn't get the lock; wait awhile and try again.
> sleep(1 + rand(9)); # wait 1 to 10 seconds
The core of the problem is refusal to back off more than 10 seconds.
Adding a one second minimum doesn't help at all.
I guess I didn't explain the problem well enough. Let's try again...
There will be one process who has the lock. The whole idea is for
everyone else to get out of the way and let that process run, so it
will release the lock. If everyone else comes back every 10 seconds,
and there are too many of them, they starve the process who has the
lock.
An individual process's decision on how long to wait should not be
based on how *quickly* it can come back and "hope" that the lock is
gone. Instead it should be based on how *slowly* it can come back,
*in order to* leave the resources available to the process that holds
the lock. The more times a process checks the lock and finds it busy,
the more it needs to pipe down and let the lock-holder get some work
done. Clearly the lock-holder (and the other people "ahead of us" in
the queue) didn't get enough work done since the previous check, else
they would have finished and released the lock. That's why the delay
must increase each time around the loop.
The beauty of using actual file-locking system calls is that they
don't wake up and swap in a process until it actually gets the lock.
The failure my patch corrects is that the processes that are waiting
for the lock are constantly waking up; under heavy load they
completely consume the system resources. The easiest way they have to
measure the load is by the number of times they've failed to get the
lock; each failed retry should convince them that the load is even
higher than they thought, and that therefore they should back off even
more than last time.
> I'm not sure
> everyone backing off at the same rate, whether exponential, linear,
> quadratic, or whatever, would help as much as a random sleep.
An element of randomness will help against a second problem, that of
everyone waking up at once and only the first one getting the lock.
But that's a second-order problem; you only get there after you solve
the first-order problem. If everyone sleeps such that they all wake
at once, the first one will get the lock, everyone else will burn CPU
and disk bandwidth while they look at the lock, and THEN (if you
solved the first-order problem, i.e. if they have all backed off
enough to leave time for this) the first one will get to run, will do
its work, and will release the lock. Somebody else will get it on the
next round. Progress *will* get made.
If you didn't solve the first-order problem, everyone comes back to look
again BEFORE the lock-holder gets their work done, and you have collapse.
The cure for the first problem is eliminating the unrealistic
"maximum" time to wait. There should be no maximum on the sleep()
call. If your process is only willing to wait a total of ten minutes,
it should be willing to wake up at these elapsed times from the start:
1, 3 (delay 2), 7 (delay 4), 15 (delay 8), 31 (delay 16), 63 (delay 32),
127 (delay 64), 255 (delay 128), 511 (delay 256). It can get to ten
minutes in nine sleeps rather than six hundred sleeps. By the
fifth sleep, it's giving everyone else half a minute to get their work
done and get out of its way. If that wasn't enough, it will give
them an uninterrupted full minute the next time. Etc.
The exponential backoff strategy has been used time and time again to
deal with congestion collapse (inability to get any work done when the
offered work exceeds a certain threshold). It's used in Ethernet
hardware. It's used in TCP retries, where backing off when packets
are lost due to congestion permits a smaller amount of data to be
transmitted successfully by everyone, rather than none at all when
everyone is pounding the gateway with retransmissions at 1-second
intervals. The theoreticians on the list (if any) might be able to
find papers that say why it works, or why anything less drastic doesn't
work under heavy loads.
John
Follow-Ups:
References:
|
|
