70
5
AT T R I B U T E S , I N D E X I N G , A N D Q U E R I E S
This performance bottleneck is an issue because in the BeOS the window
system stores icon positions for files as attributes of the file. Thus, with this
design, when displaying all the files in a directory, each file would need at
least one disk access to get the file i-node, one access to load the attribute
directory i-node, another directory access to look up the attribute name, an-
other access to load the attribute i-node, and finally yet another disk access
to load the data of the attribute. Given that current disk drives have access
times on the order of milliseconds (and sometimes tens of milliseconds) while
CPU speeds reach into the sub-5-nanosecond range, it is clear that forcing
the CPU to wait for five disk accesses to display a single file would devastate
performance.
We knew that a number of the attributes of a file would be small and that
providing quick access to them would benefit many programs. In essence
the problem was that at least some of the attributes of a file needed more
efficient access. The solution came together as another design issue reared
its head at roughly the same time. BFS needed to be able to store an arbitrary
number of files on a volume, and it was not considered acceptable to reserve
space on a volume for i-nodes up front. Reserving space for i-nodes at file
system initialization time is the traditional approach to managing i-nodes,
but this can lead to considerable wasted space on large drives with few files
and invariably can become a limitation for file systems with lots of files and
not enough i-nodes. BFS needed to only consume space for as many or as
few files as were stored on the disk--no more, no less. This implied that
i-nodes would likely be stored as individual disk blocks. Initially it seemed
that storing each i-node in its own disk block would waste too much space
because the size of the i-node structure is only 232 bytes. However, when
this method of storing i-nodes is combined with the need to store several
small attributes for quick access, the solution is clear. The spare space of an
i-node block is suitable for storage of small attributes of the file. BFS terms
this space at the end of an i-node block as the
small data
area. Conceptually
a BFS i-node looks like Figure 5-2.
Because not all attributes can fit in the
small data
area of an i-node, BFS
continues to use the attribute directory and i-nodes to store additional at-
tributes. The cost of accessing nonresident attributes is indeed greater than
attributes in the
small data
area, but the trade-off is well worth it. The most
common case is extremely efficient because one disk read will retrieve the
i-node and a number of small attributes that are often the most needed.
The
small data
area is purely an implementation detail of BFS and is com-
pletely transparent to programmers. In fact, it is not possible to request
that an attribute be put in the
small data
area. Exposing the details of this
performance tweak would mar the otherwise clean attribute API.
small data Area Detail
The data structure BFS uses to manage space in the
small data
area is
Practical File System Design:The Be File System
, Dominic Giampaolo
page 70