Tuning file system block addressing for performance

ABSTRACT

In most general purpose file systems, data blocks are scattered throughout the disk so as not to require arbitrary chunks of contiguous disk space. To be able to find the n^th data block in a file, both an index and indexing function must exist. The classical Unix File System (UFS) paradigm calls for a tree of block pointers, where the leaf nodes are data blocks in the file, and all other nodes are file system meta-data. In more highly-optimized file systems, b trees are used to index extents (groups of contiguous blocks). In these systems, the number of disk accesses required depends upon the depth of the associated indexing tree. Fragmentation is also an ongoing issue with file system design, decreasing overall file system performance. For read efficiency, direct pointers to all blocks in every file would be ideal, but also far too costly in terms of space.In this paper, a framework is proposed that optimizes file system performance by: decreasing the number of disk seeks to one for each file seek, forcing extent sizes to grow as file sizes grow, and providing a sound environment for efficiently decreasing file system fragmentation.

REFERENCES

• 1: Delvin C. Defoe , Sharath R. Cholleti , Ron K. Cytron, Upper bound for defragmenting buddy heaps, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 2: Erik D. Demaine , J. Ian Munro, Fast Allocation and Deallocation with an Improved Buddy System, Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, p.84-96, December 13-15, 1999
• 3: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 4: Philip D. L. Koch, Disk file allocation based on the buddy system, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.352-370, Nov. 1987 [doi>10.1145/29868.29871]
• 5: Zhenmin Li , Zhifeng Chen , Yuanyuan Zhou, Mining block correlations to improve storage performance, ACM Transactions on Storage (TOS), v.1 n.2, p.213-245, May 2005 [doi>10.1145/1063786.1063790]
• 6: Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
• 7: A. Sweeny. Scalability in the xfs file system. In Proceedings of the USENIX 1996 Annual Technical Conference. USENIX, January 1996.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Operational analysis

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Design, Management, Performance

Keywords:
file systems, fragmentation, optimization