跳轉到

7.2 UNIX inode 與日誌式檔案系統#

概念說明#

UNIX 檔案系統（UFS、ext2/3/4）用 inode（index node） 描述檔案：每個檔案一個 inode，內含元資料（大小、權限、時間戳）與資料區塊指標，配置採「索引式」而非 FAT 的鏈結式：

  • 12 個直接指標：直接指向 12 個資料區塊（以 4KB 區塊計，覆蓋 48KB）。
  • 1 個單間接指標：指向一個滿是區塊指標的區塊（4KB/8bytes = 512 個指標 → +2MB）。
  • 1 個雙間接：→ 512 × 2MB = +1GB。
  • 1 個三間接：→ +512GB。

隨機讀取第 k 個區塊，最多走 3 層間接（通常間接塊已快取），遠優於 FAT 的線性走鏈。目錄則是特殊檔案：內容是「(檔名 → inode 編號)」的對照表。

當機一致性問題：一次檔案建立要寫多個地方（inode、目錄區塊、資料區塊、位圖），順序中斷就會出現孤兒 inode 或指向未初始化區塊的指標。日誌式檔案系統（journaling）的解法：先把「即將進行的區塊寫入」記到日誌區（順序寫），日誌完整落盤後（commit record）才真正改動原地；當機重啟後重播（replay）日誌即可把檔案系統帶回一致狀態。ext4 的資料模式可選 journal / ordered / writeback，差別在是否把「檔案資料」也寫進日誌。

演算法步驟：日誌式寫入（write-ahead）#

  1. 把將寫入的元資料（與視模式包含的資料）區塊複製進日誌。
  2. 寫入 commit record（代表交易完整）。
  3. checkpoint：把日誌中的區塊寫到最終位置。
  4. 釋放日誌空間。當機後：日誌中有 commit → 重播；無 commit → 丟棄。

Python 範例#

BLOCK = 4096
PTR_PER_BLOCK = BLOCK // 8      # 8 bytes/指標 → 512

class Inode:
    def __init__(self):
        self.direct = [None] * 12
        self.single, self.double, self.triple = None, None, None

    def block_ptr(self, k):
        """回傳第 k 區塊的指標所在層級（模擬定址）"""
        if k < 12: return ("direct", k)
        k -= 12
        if k < PTR_PER_BLOCK: return ("single", k)
        k -= PTR_PER_BLOCK
        d1, d2 = divmod(k, PTR_PER_BLOCK)
        if d1 < PTR_PER_BLOCK: return ("double", (d1, d2))
        k -= PTR_PER_BLOCK ** 2
        d1, rem = divmod(k, PTR_PER_BLOCK ** 2)
        d2, d3 = divmod(rem, PTR_PER_BLOCK)
        return ("triple", (d1, d2, d3))

ino = Inode()
cap_direct = 12
cap_single = PTR_PER_BLOCK
cap_double = PTR_PER_BLOCK ** 2
cap_triple = PTR_PER_BLOCK ** 3
total = cap_direct + cap_single + cap_double + cap_triple
def fmt(n_blocks):
    kb = n_blocks * 4
    if kb < 1024: return f"{kb}KB"
    if kb < 1024**2: return f"{kb/1024:.0f}MB"
    if kb < 1024**3: return f"{kb/1024**2:.0f}GB"
    return f"{kb/1024**3:.0f}TB"

print(f"4KB 區塊：直接 {fmt(cap_direct)} + 單間接 {fmt(cap_single)} "
      f"+ 雙間接 {fmt(cap_double)} + 三間接 {fmt(cap_triple)}")
print("第 100 區塊的定址:", ino.block_ptr(100))

class Journal:
    """簡化日誌：write-ahead + commit + replay"""
    def __init__(self):
        self.log, self.committed, self.disk = [], False, {}

    def begin(self): self.log, self.committed = [], False
    def write(self, blk, data): self.log.append((blk, data))
    def commit(self): self.committed = True
    def checkpoint(self):
        if self.committed:
            for blk, data in self.log: self.disk[blk] = data
        self.log = []

j = Journal()
j.begin()
j.write(100, "inode 資料"); j.write(101, "目錄項")
j.commit(); j.checkpoint()
print("正常流程後磁碟:", j.disk)

j2 = Journal()
j2.begin(); j2.write(200, "孤兒寫入")   # 未 commit 就當機
j2.checkpoint()
print("未 commit 不落地:", j2.disk)

複雜度與 I/O 成本分析#

  • 隨機讀第 k 區塊：1 次資料 I/O + 至多 3 次間接塊 I/O（實務上間接塊常快取）。
  • 寫入：日誌模式下每個區塊寫兩次（日誌一次 + 原地一次），寫放大 2×，但換取當機一致性。
  • inode 大小固定（如 256 bytes），支援的檔案大小上限由指標層級與區塊大小決定。
  • ext4 用 extent（範圍描述）取代多層間接，一個 extent 記錄「起點 + 長度」，連續大檔案只需一個 extent，定址更省。

練習#

  1. 區塊 4KB、指標 4 bytes 時，重新計算各層容量與單檔上限。
  2. 用 Journal 類別模擬「commit 後、checkpoint 前當機」，說明重播（replay）該做什麼。
  3. 比較 extent 與三層間接在「讀取 1GB 連續檔案的元資料」所需 I/O 次數。