File Systems and Volume Managers: History and Usage Page 4 - EnterpriseStorageForum.com

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.

Bitmaps Representation

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:

http://www.cs.wpi.edu/~cs502/s01-breecher/lectures/Section11-File_Struct.ppt

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:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/trees.html
http://cs-people.bu.edu/elenam/cs112-labs/lab9/lab9.html
http://www.cs.usask.ca/research/research_groups/aries/projects/applets/tutorials/trees/bintree/

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.

First 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:

http://www.cs.rit.edu/~ark/lectures/gc/03_03_02.html.

Best 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:

http://www.cs.rit.edu/~ark/lectures/gc/03_03_03.html.

Conclusions

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.

Summary

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.


» See All Articles by Columnist Henry Newman



Page 4 of 4

Previous Page
1 2 3 4
 

Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 

Storage Daily
Don't miss an article. Subscribe to our newsletter below.

Thanks for your registration, follow us on our social networks to keep up-to-date