File Systems and Volume Managers: History and Usage Page 4
Free Space Allocation and Representation Methods
Each file system uses an algorithm to find and allocate free space within the file system. Most file systems use binary trees (btrees) allocation to represent free space, but some file systems use bitmaps to represent free space. Each method of free space representation has its advantages and disadvantages.
The use of bitmap representation is less common. In this method, each bit in the map represents a single allocation unit such as 1,024 bytes, 512 KB or even 100s of megabytes; therefore, a single bit could represent a great deal of space.
Some good information can be found at:
Binary Trees (Btrees) Representation
A btree is basically a sorted list of all the free allocations and used space for the file system. It is important to understand how the space is allocated from the tree. Some good reading on btree allocation, which is used in most file systems to find free space, can be found at:
Free space Allocation
With each allocation type (btree or bitmap), free space must be found and allocated with the representation method. These allocation methods find the free space based on their internal search algorithms. The two most common methods used are first fit and best fit.
The first fit method tries to find the first space within the file system that matches the allocation size requested by the file being allocated. In some file systems, the first fit method is used to find the space closest to the last allocation of the file being extended, thereby allowing the allocation to be sequential block addresses for the file within the file system. Here is a good example of first fit:
The best fit method tries to find the best place in the file system for the allocation of the data. This method is used to try to reduce total file system fragmentation. This method always takes more CPU cycles than first fit, as the whole file system must be searched for the best allocation. (Note: In systems that use round-robin allocation, only the device that the initial allocation was made on needs to be searched.)
This method also works better at reducing fragmentation, especially on large (multiple megabyte) allocations or when files cannot be pre-allocated (for file systems that support this method). Most vendors do not support this method, and most allocations in file systems are not large, as the overhead would be huge. The old Cray NC1FS supports this method by using hardware vector registers to quickly do the search.
Here is a good example of best fit:
In general, btrees do a better job for small allocations, but then the files could become fragmented. Bitmaps are better for larger allocations, but the time for allocation can be much longer to search the map for free space. Both of these methods can be optimized for your operational requirements by tunable parameters in the file system and volume manager as well as by RAID configuration and allocations, which we will review in a few months. While some file systems have a hybrid approach to allocation, these are generally proprietary and require a non-disclosure agreement to completely understand their inner workings.
You should now have a good understanding of how file systems and volume managers work internally. Next month we will apply this information to specific tuning issues and to understanding file system and volume manager tradeoffs and choices. As we follow the data path, we'll then move on the RAID devices and discuss how to put all of this information to good use.