84
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
Updates to the size index happen when a file changes size. As an opti-
mization the file system only updates the size index when a file is closed.
This prevents the file system from having to lock and modify the global size
index for every write to any file. The disadvantage is that the size index
may be slightly out-of-date with respect to certain files that are actively be-
ing written. The trade-off between being slightly out-of-date versus updating
the size index on every write is well worth it--the performance hit is quite
significant.
The other situation in which the size index can be a severe bottleneck is
when there are many files of the same size. This may seem like an unusual
situation, but it happens surprisingly often when running file system bench-
marks that create and delete large numbers of files to test the speed of the
file system. Having many files of the same size will stress the index struc-
ture and how it handles duplicate keys. BFS fares moderately well in this
area, but performance degrades nonlinearly as the number of duplicates in-
creases. Currently more than 10,000 or so duplicates causes the performance
of modifications to the size index to lag noticeably.
The last modification time index is the final inherent file attribute that
BFS indexes. Indexing the last modification time makes it easy for users to
find recently created files or old files that are no longer needed. As expected,
the last modification time index receives updates when a file is closed. The
update consists of deleting the old last modification time and inserting a new
time.
Knowing that an inherent index such as the last modification time index
could be critical to system performance, BFS uses a slightly underhanded
technique to improve the efficiency of the index. Since the last modification
time has only 1-second granularity and it is possible to create many hundreds
of files in 1 second, BFS scales the standard 32-bit time variable to 64 bits
and adds in a small random component to reduce the potential number of
duplicates. The random component is masked off when doing comparisons
or passing the information to/from the user. In retrospect it would have been
possible to use a 64-bit microsecond resolution timer and do similar masking
of time values, but since the POSIX APIs only support 32-bit time values
with 1-second resolution, there wasn't much point in defining a new, parallel
set of APIs just to access a larger time value.
In addition to these three inherent file attributes, there are others that
could also have been indexed. Early versions of BFS did in fact index the cre-
ation time of files, but we deemed this index to not be worth the performance
penalty it cost. By eliminating the creation time index, the file system re-
ceived roughly a 20% speed boost in a file create and delete benchmark. The
trade-off is that it is not possible to use an index to search for files on their
creation time, but we did not feel that this presented much of a loss. Simi-
larly it would have been possible to index file access permissions, ownership
information, and so on, but we chose not to because the cost of maintaining
Practical File System Design:The Be File System
, Dominic Giampaolo
page 84