Stan Cao

A backend developer.

Fast File System

less than 1 minute read

Original File System

original_fs

Problems

  • long distance between inodes/data
  • inodes in single dir not close to one another
  • small blocks (512 bytes)
  • blocks laid out poorly
  • free list becomes scrambled, causes random allocation

Conclusion

Old file system treat disk like RAM, we need to find a disk-aware file system

Implementation

  • use bitmap instead of free list, provides more flexibility, with more global view.
  • use groups

groups

  • Super rotation, use multiple super blocks for each group using different offset
  • Larger blocks, from 512 bytes to 4 KB
  • Others: long file names, atomic rename, symbolic links

Redundancy in FFS

  • Dir and inode tables
  • Dir and inode link counts
  • Data bitmap and inode pointers
  • Inode file size and inode/indirect pointers

You may also enjoy

K-D-tree

1 minute read

A k-dimensional or k-d tree is a binary tree used to subdivide a collection of records into ranges for k diļ¬€erent attributes in each record.

B-tree

2 minute read

In the 1980s B-trees were applied to database management systems, with an emphasis on how to ensure consistent B-tree access patterns to support concurrency ...

Sorting

1 minute read

Sorting is always an important topic in computer science. Theoretically, comparison sorts cannot perform better than O(n lgn) in the best case, better perfor...