Last changes:
Do Feb  5 09:40:01 CET 2004

The objective is to find and provide a method that artificially ages a filesystem so that one gets an idea of how the performance of a given filesystem behaves under different workloads.

• The standard filesystem benchmarking tools such as Bonnie++, Postmark , Mongo and others all test the optimum case for the block layouting algorithm. In that case the filesystem is empty such that the block allocation algorithm has no problems in layouting the blocks on disk in the way it is designed for.
  
  
• But in practice one also is interested to know how a filesystem performs when it is or was heavily used over a longer period (e.g. months and years). From the user's and administrator's point of view one might also be interested in choosing the right file system for the right task and corresponding workload.
  
  Filesystems using clusters (like the MSDOS/Windows FAT filesystems) are known to be a worst case example, that get severely fragmented. But also the (Berkeley) FFS filesystem and derivates were investigated in the past and found to pay a performance loss of up to 20 percent dependent of the workload. When looking for further information and literature you might find Smith's site a very good starting point.
  
  
• Nevertheless benchmarks on empty systems are very important. Look at my ''gauge measurements'' or at my older (mongo) benchmarks or at the ReiserFS benchmarking site for newer results. You may also find Denis' and Kresimir's filesystem test interesting, though there page seem to be down. Other results and test suites you will easily find if you search in Google Groups.

• Internal Fragmentation: This is the (average) loss of space when blocking data into blocks of fixed size due to the ends of files not filling a whole block. Of course you want to keep this number small not wasting much of memory space eg. by using fragments (FFS) or putting tails of files together (ReiserFS).
  In my simulations I calculate the average internal fragmentation by dividing the number of bytes that are on disk per file or per partition disk by the number of theoretically usable bytes which is the number of blocks used times the block size. One can argue, that a log file on disk (or metadata in general) will automatically enlarge internal fragmentation as its space cannot be used for user data. I am not accounting that for internal fragmentation.
• External Fragmentation: This is the (average) loss of performance when the physical block layout on disk is not optimized for the disc mechanics such as that for many files the blocks belonging to one file are scattered around the whole disc. The actual measured loss of performance depends on various aspects like the disk model, the file system block layout algorithm, the file system usage pattern, all kind of different caches of the disc and of the OS. The reason one wants to avoid external fragmentation is due to the fact that the disc is a random access device which is very slow when seeking the next position to read/write on disc (around milli seconds) compared to computer main memory (around nano seconds).
  Nowadays having the intelligent drives which hide their internal way of storing data on disk the only way to archive an optimal layout is to commit to what the EIDE standard says and the disc manufacturer claim to fulfill: the disk throughput is optimal if successive blocks of a file have adjacent logical block numbers.
  This brings us to a definition of external fragmentation in terms of a number. You can define external fragmentation for a file, as the ratio of the blocks used by a file in a row (in LBA-numbers) divided through the number of blocks minus one it uses in total. A value of one would be optimal then. A value of zero would be extremly bad. This definition of fragmentation is widely used in literature. External fragmentation for a partition is then given by the average over all files in that partition.
  Now, imagine a file that uses every second block in a row. According to the standard definition stated above it would be a worst case having a fragmentation number of zero, but intact having fast disks and caches it is not bad at all. Therefore I also use other definitions. The one, I call fragmentationX, is defined as above with the difference that a maximum of X logical blocks between two adjacent blocks of a file just are counted as optimal as well. This means for X equal to one we are back at the standard definition. In fact I use values of X equal to one, ten, one hundred and one thousand. Back to our example, every value of X greater than one would give a fragmentationX of one, the optimal value. This definition is also not perfect as the layout is in fact not optimal. Therefore I define the fragmented length of a file as the number of logical blocks an imaginary ant would have to walk if it walks from block to block of file, e.g. if the file occupies block number a, b and c, the fragmented length is abs(b-a)+abs(c-b). You then can normalize by the block number minus one, which gives you how much longer the way of the ant is in case of fragmentation. As above a number of one is optimal for that definition, but the higher the number the worse the layout. For our example we get a value of two which is a very good but not optimal value. There is a problem with this definition. There is no practical upper bound, so it is difficult to get a feeling of how fragmented a file really is.
  In all definitions the blocks that are to be read for meta data are left out. The practical reason is that there is no system call to get the corresponding block number of an inode. Besides that, meta data is heavily cached, too.

I hold the copyrights on the entire content of this page. I am not responsible for the content of external links, though. The results and graphs I present are part of my master thesis in computer science at the university of Frankfurt. You are allowed to use them for your research, if you correctly cite me (bibtex entry). Look into the source code of the tools for the license information about it (GNU GPL). For questions, criticism, ideas or what ever do not hesitate to mail.

Constantin Loizides, loizides AT no spam please and robs beware informatik DOT uni-frankfurt DOT de, University of Frankfurt