Stan Cao

A backend developer.

LFS - Log File System

less than 1 minute read

general ideas

Goal: to do operations sequentially to improve performance

  • Just write all data sequentially to new segments.

  • Never overwrite, even if that means we leave behind old copies.

  • Buffer writes until we have enough data.

write both data and inodes

write

  • formula for calculating buffer size

buffer

overwrite

overwrite

layout for LFS

layout

mechanism for garbage collection

  1. Is an inode the latest version?

    Check imap to see if it is pointed to (fast).

  2. Is a data block the latest version?

    Scan ALL inodes to see if it is pointed to (very slow).

  3. Solution: segment summary that lists inode

    corresponding to each data block.

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...