Design note: Allocation Heuristics

[Daniel Phillips]

Until now, Tux3 has relied on a simple, linear allocation strategy
where we always search for free blocks just after the last one
allocated. This works wonderfully well with an empty volume but is prone
to fragmentation over time as deletes open up holes that tend to be
filled in by unrelated blocks.

A new patch set is now entering testing that attempts to provide good
long term fragmentation resistance by implementing techniques analogous
to those that have worked well for the Ext filesystems over the years.
Similarly, we hope to control fragmentation to the point where the
services of a defragmentation utility are seldom if ever required.

Static versus adaptive allocation policy

I expect that this work will proceed in two major stages, the first of
which is the current patch set. This implements a basic "static"
allocation policy where we establish an allocation goal for each inode
at the time the inode is created, and that goal persists over the life
of the object. Later, we will introduce "adaptive" behavior where inode
allocation goals may change over time in response to observed allocation
patterns.

Hopefully, a simple static allocation policy will already work well
enough for Tux3 to be usable as a general purpose filesystem. After all,
the Ext filesystems get by very well with something not much different.
But clearly, even with good initial guesses, we may want to change our
mind at some point about the allocation goal for a given inode in
response to changing volume congestion patterns.

To support adaptive allocation, we will introduce a "goal" inode
attribute to override the default "inode number equals allocation goal"
rule, to be used in the case that congestion or other undesirable
allocation conditions are detected. For forward compatibility, we will
introduce the goal attribute before freezing the Tux3 layout definition,
whether or not we are ready to use it.

The rest of this note concerns the new, static allocation heuristics,
which I hope will perform fairly well.

Inode number to block address correspondence

The big simplifying idea for the current "static" allocation policy is,
block allocation goal corresponds roughly to inode number. This
accomplishes two things: 1) it gives a stable goal for each inode so
that if rewritten, the new blocks will tend to be allocated fairly close
to the original and 2) it makes the ordering of allocated blocks similar
to the ordering of inodes that own them, so a linear walk through the
inode table will be a roughly linear walk through allocated blocks. This
should reduce seeking on spinning media. For flash, it should help with
erase block behavior.

Imposing the inode number to block address correspondence reduces the
volume layout problem to making good choices for inode numbers. However,
it is impossible in general to make a perfect inode number choice
because at creation time we do not know very much about how big a file
will be, how many files there will be in a directory, or which parts of
the volume will be congested or sparsely used in the future. And
furthermore, all these factors can vary through large ranges over time.
So we content ourselves with some assumptions: most files will be small
and most directories will have a modest number of files.

Some immediate weaknesses are apparent. Two large files with nearby
inode numbers will have similar block allocation goals. If these files
grow slowly by appending, like log files, it is likely that the two
files will end up intertwined, potentially causing extra seeking. If
there are many large files in the same directory, or a very large number
of files in a directory, then there will be congestion in the
neighborhood of that directory and lengthy linear searches might be
needed for new allocations. For the time being, we will just accept
these weaknesses and consider what to do about them if we observe issues
in practice. Eventually, adaptive allocation and other techniques will
help.

Block goal extrapolation

For each file write, we extrapolate an allocation goal which is simply
the logical offset of the write plus the inode number, with "folding" as
described below. Thus, a write to the same logical address always gives
the same physical goal, whether the write is sequential or random.

Tux3 never overwrites data, but always writes new data into free space.
How does this "copy-on-write" interact with the goal extrapolation rule?
If no free space is available nearby (common for rewrite of a large
file) then the new blocks would end up far away from the original.
However, if the file is rewritten again, then chances are, the out of
place blocks will return to their "natural" position. If a very large
file is rewritten so that the write is broken across multiple deltas,
the behavior becomes more interesting. The first delta will be allocated
far out of line, however it will leave a gap into which the next delta
can be written. After that process covers the entire file, we would see
that the entire file has moved lower, with just one region allocated far
out of line.

It seems as though copy-on-write effects should cause only a modest
increase in fragmentation, as long as some "slack space" is distributed
throughout the volume. The actual effect remain to be determined
experimentally. This is one case where the ability to overwrite in place
like Ext4 could be an efficiency advantage.

Low level segment allocator

The purpose of allocation policy is only to provide a starting point
(goal) for a free space search. The low level segment allocator then
provides its own, important semantics. It guarantees to search the
entire volume if necessary, to be sure that all free space on the volume
can actually be used.

The low level allocator searches in two passes, first considering only
allocation groups with enough space to satisfy all or a large part of
the request, then searching all remaining allocation groups with any
free space at all. Thus, there is some fragmentation avoidance built
into the low level allocator.

The low level allocator uses the count map table to skip over full or
nearly full allocation groups efficiently. So if allocation policy does
fail to provide a good allocation goal due to congestion, the result may
be a long but fairly efficient search. A secondary result is potentially
increased fragmentation. Our objective for this new allocation work can
therefore be understood entirely in terms of reducing CPU cost of
searching, and reducing fragmentation.

Directory entry position to inode number correspondence

Mass file operations will often be performed in directory entry order,
therefore it is helpful to establish a correspondence between directory
entry order and inode number. With linear allocation, this happens
naturally when creating files in an empty volume, but breaks down when
creating new files in an existing directory, especially if holes exist
in the directory where files have been deleted. To improve behavior for
such randomly created files, we let the position of a new directory
entry guide the choice of inode number. We use a simple extrapolation of
the directory entry logical address, and use the inode number of the
parent directory as the base.

This should produce good results whether the directory is extended by a
new entry or a previously deleted entry in the interior of the directory
is reused. There are some limitations. If an inode is hard linked or
moved to a new directory, its inode number will be out of line with
others in the destination directory. We also have an unnatural
dependence of inode number choice on the average length of names in a
directory: longer names decrease the density of the inode table. This is
only a minor annoyance because Tux3 inodes are variable sized and
leaving gaps between them does not cost much. In theory, we could
improve this behavior by computing a statistic for average entry name
length to use in the extrapolation calculation.

Directory positioning

As for all inodes, the allocation goal for a directory is simply its
(possibly folded) inode number, which is also the base position for
extrapolating all the inodes contained within the directory. Directories
are extrapolated more widely than files with the intention of leaving
space between directories for contained files. In a nearly empty volume,
we spread directories out more widely, on the assumption that they will
contain relatively more files and subdirectories. We also try to create
directories in relatively empty allocation groups. The threshold for
emptiness is determined by the fullness of the volume and how deeply the
directory is in the filesystem tree. A directory created at root level
in a nearly empty volume will be created only in a completely empty
group, if one is available.

The threshold for emptiness is relaxed as the volume becomes more full,
and for directories deeper in the tree. The search for a relatively
empty group is fairly short. If no relatively empty group is found then
a linear search for a free inode number is performed, starting at the
extrapolated directory inode number.

For the time being, the directory group search is strictly linear,
however it is probable that a pseudo random search using the
extrapolated goal as a key will produce better results, a possible
future improvement.

Directory extrapolation is clearly a flawed mechanism. It produces
congestion when the extrapolated positions of directories with different
parents overlap. It also assumes a limited number of files per directory
- files beyond that will overflow into the regions of other directories.
For the moment, our narrow goal is to improve on the situation where
directories are not spread out at all, and therefore maximally
vulnerable to age related fragmentation.

Use linear allocation as much as possible

Simple linear allocation turns out to be the best allocation policy in
a surprisingly wide variety of cases. The new patch set does not abandon
it entirely. If files are being written in sequence within a delta then
we use linear allocation instead of extrapolating from the inode number
and file size. However, if the linear goal diverges too much from the
extrapolated goal then we use the extrapolated goal and continue
linearly from there. We define "too far" as something on the order of
hard disk cylinder size in an effort to avoid introducing gaps of more
than a track. (Within a track, gaps and out of order allocation are
relatively less important because of the track cache.)

The "too far" linear rule should also help with multitasking loads. If
two tasks are writing in different directories simultaneously, this rule
should prevent these writes from mixing their allocated blocks together.

With linear allocation, if we untar a big directory, then subdirectories
and their contents will always be allocated entirely inside of parent
directories. This is optimal if we read in the same order and reasonably
good even for breadth first access. However this arrangement will not
age well because there is no slack space for creating new files close to
other files in the same directory. The new patch set departs from this
"embedded child" behavior to always create directories outside their
parent directories. This adds two additional seeks per directory to a
depth first traversal. What we hope to gain in return is much better
aging behavior, a result that remains to be confirmed experimentally.

Folding inode numbers to block addresses

Both inode numbers and block addresses are 48 bits, so at a theoretical
maximum size of one exabyte, we have one inode per volume block, which
should be adequate. For smaller volumes, we may generate a volume
address for any inode number by "folding" inode numbers to lie within
the volume address range. The details of the folding algorithm are
somewhat interesting. We take the inode number modulo a volume "wrap",
which is the smallest power of two greater than the volume size, and
fold again to half the wrap size if necessary, yielding a block address
strictly inside the volume. This algorithm gives an inode number to
volume address mapping that behaves well even if the volume is resized.
If volume size is reduced, nearby block allocation goals will still be
nearby. If volume size is increased, then an inode may "unfold" to a new
allocation goal and its blocks will eventually migrate to the new goal
when rewritten. Under many volume size changes, blocks of a given file
will only take on a few different allocation goals, so fragmentation is
controlled.

Summary

In summary, recent patches introduce the following major changes:

  * Inode number implies allocation goal
  * Extrapolate inode numbers from directory entry position
  * Create new directories in empty groups when volume is young
  * Low level extent search now driven by group counts

With these changes, we expect a modest regression in terms of increased
fragmentation on some loads for which linear allocation is optimal, in
return for a large improvement in terms of reduced fragmentation as a
volume ages. How much regression, and how much improvement remain to be
determined experimentally.

The current set of heuristics might need to be adjusted and can
certainly be improved over time. At some point we expect to move on from
static allocation goal determination to adaptive. That said, it is
possible that with the current set of heuristics will already perform
competitively to the point where allocation issues are no longer a
barrier to using Tux3.

Regards,

Daniel