>One problem with our LFS is that the cleaner moves data around (as it has 
>to), thereby destroying temporal locality of reference.  After data's been 
>moved enough by cleaning, it's no longer anywhere near data which was
>written at the same time.  The original Sprite solution to this was a
>cleaner which implemented an FFS-like allocation policy, coalescing data
>which is in the same file.  The paper I posted a reference to recently
>describes a better method, in which the cleaner actually tries to group
>data together by *observed* access patterns.  This is the best of both
>worlds.

Unless,of course, your reference patterns form a bistable process,
with period in either state just long enough to fool the cleaner into
optimizing for them, and then switches to the other state. :)

A diversion into offline adversarial analysis and designing algorithms
that minimize the worst-case is probably way, way off-topic.