Tux3 Allocation Glossary
daniel.raymond.phillips at gmail.com
Wed Jun 26 20:11:27 PDT 2013
For the next few weeks we will be talking about the last remaining big
Tux3 design issue: allocation heuristics. This is largely uncharted
territory with little formal research available as a guide. Further, we
have a new requirement specific to our atomic commit strategy: data
obsoleted by a delta may not be freed and reallocated until the delta
commit completes. Therefore, the ideal goal for a given allocation will
often not be available and some less desirable location will need to
be used in its place. The immediate effect of this is that we cannot
simply copy the effective algorithms used by the Ext2/3/4 family.
To help us get started studying specific issues and solutions for
Tux3, I have prepared a short glossary of terminology we have been
developing in discussions recently. There are specific, in some
respects novel, algorithms implied by the definitions below, which
will be described later with the help of this basic terminology.
Tux3 Allocation Glossary
All the blocks mapped by one bitmap block. We might change the
granularity of this eventually, but for now an allocation group has
2**(12 + 3) = 2**15 blocks.
Free tag map
Quick means of knowing how much free space is available in each
allocation group (exactly or approximately depending on
implementation). For now, this is implemented as an array of 16 bit
counts of allocated blocks per allocation group.
We tried to satisfy an allocation request within a target region of the
volume and failed, so bounce to some new region and try again.
Search regions successively further away from the orignal goal using a
generating function to generate the search sequence so the search
pattern is repeatable, given the same file
The generating function used to compute successive bounce goals. Must
be repeatable per file. Must have good coverage properties so that
volume space tends to consumed evenly. Must fall back to exhaustive
search (with the help of free tags) after some number of bounces in
order to ensure that all the space in a volume can eventually be used.
Extra space left near files and around directories to handle growth
or rewrites or both.
Fullness of nearby allocation groups. Controls amount of directory
spread and slack space.
If nearby allocation groups have low allocation counts, new directories
will spread out further.
Search for a new extent to allocate just above the previously allocated
extent. For CPU efficiency and good layout, we want to do this most of
the time using a simple test to determine whether this is appropriate.
The logical position of data in a file and position of the file in its
sirectory is extrapolated to determine an initial allocation goal
Extrapolation is to find a good allocation goal for data of a particular
file, using a simple formula based on the position of the dirent in a
directory and the logical position of the data in a file.
More information about the Tux3