We periodically run a process which examines the space usage on our AFS home directory servers, and moves user volumes from one server to another in an attempt to balance the usage. However, just balancing on usage isn't enough. Recently, we've made some changes in the process to take into account other factors, such as the volume's average activity, in order to have servers with a load profile that is more even.
The AFS fileserver processes keep a record of the # of "accesses" to a volume during a 24 hour period. Nighly, we dump a copy of this data in addition to the volume's current location, size, and other information to a database table that we keep around for statistics and such. During the last run of our "rebalancing" tool, it was noticed that some of our servers have an inordinate amount of activity compared to others.
When the rebalancing process was originally envisioned, it was considered that we'd "balanced" with some effort given to load, but it was never implemented, because it was quite easy to balance over one factor -- but things get a bit more difficult when balancing over two. Our balancing algorithm relies on probability and random chance to try to obtain average-case balancing over our partitions. Other ways of doing it are enormously complicated, have potentially horrible performance characteristics, or are prone to ugly worst case input scenarios. So, it basically works like this:
1) add up all of the current space usage and access counts;
calculate an ideal space usage & access weighting for server partitions.
For access counts, we look at a 30-day average.
(server partition space targets are based on % utilization, and load
targets are based on a % of the total load weighted by the servers's
"power factor", which is just a numeric representation of the server's
I/O+cpu speed as compared to other servers)
2) For each server partition, randomly "remove" volumes and place them in
the free-roaming pool until the partition reaches a certain percentage
utiliization of it's targeted space/load. We shoot for "under" our target
here as to add some entropy to the system.
3) Iterate through the server partitions one by one, picking a volume at random
from the "pool" that won't put it over it's targets. Do this until an
iteration doesn't result in any allocations.
4) If there are volumes left in the pool, do step 3 again with space &
utilization targets that are a few percentage points higher than the
ideal. This is done because, well, as mentioned before, things get more
difficult when trying to balance two factors. Need a little wiggle room.
5) If there are still volumes left in the pool, complete the balancing operation
using space only. Ok, we can't get it perfect this time.
6) Randomly distribute any remaining volumes over the available partitions.
There usually aren't anything left at this stage, but it's here just in case.
And that's it. The idea of this is to run it often (every couple days or so), and over time, you'd have pretty well balanced IO & space utilization. It's kind of like blackjack -- you basically come out even over the long run, but any one hour at the table might be a downer. The idea of doing the "removes" in stage 2 based on 80% utilization is to guarantee that things get shaken up a bit; things should get more evenly distributed every time you shake it.