跳轉到

1.1 記憶體層級與儲存設備#

概念說明#

電腦的儲存設備可以依「速度、容量、成本」三個軸構成一個金字塔般的記憶體層級（memory hierarchy）：

暫存器（registers）          ~0.3 ns    KB 級
CPU 快取 L1/L2/L3            ~1-40 ns   KB~數十 MB
主記憶體 DRAM                 ~100 ns    GB 級
SSD 固態硬碟                  ~100 μs    TB 級
HDD 傳統硬碟                  ~10 ms     TB 級
網路/雲端儲存                 ~100 ms    幾乎無限

從上到下，大約每一層慢 10 到 1000 倍，但容量與單位成本卻便宜許多。這個「速度落差」正是本章的重點：一個在 DRAM 上只有 100 奈秒的操作，在磁碟上可能要 10 毫秒，相差 10 萬倍。換句話說，如果在演算法設計時不考慮磁碟 I/O，一個理論上 O(n log n) 的演算法，實際可能比 DRAM 上的 O(n²) 還慢。

層級之所以能運作，靠的是兩種區域性（locality）：

  1. 時間區域性（temporal locality）：剛被存取的資料，很可能很快會再度被存取。
  2. 空間區域性（spatial locality）：被存取的資料位址附近，很可能也會被存取。

緩衝池（buffer pool）、作業系統分頁快取（page cache）、CPU 快取，全部都是利用這兩種區域性，把「下一筆可能用到的資料」預先放在較快、較貴的層級。

演算法設計的核心轉變：以「塊」為單位思考#

在主記憶體演算法中，我們假設任意存取都是常數時間。但在磁碟演算法中，存取單位是區塊（block）或頁（page），例如 4KB。這帶來兩個重要推論：

  • 演算法的 I/O 次數（I/O count）比 CPU 運算次數更重要。一個演算法如果能少讀一次磁碟，往往比多算十幾 quote 次比較更划算。
  • 區域性可以被設計。良好的資料結構把相關資料放在同一頁（例如 B-tree 的節點恰好一頁），就能一次 I/O 拿到多筆資訊。

演算法步驟：模擬兩層記憶體的存取#

我們將用 Python 模擬「DRAM 緩衝池 + 磁碟」兩層結構，並展示線性掃描與隨機存取在區域性差異下的效能差距。

# 01.1 範例：兩層記憶體模擬器
import time, random

class SimDisk:
    """模擬磁碟：每次 read_page 花磁碟延遲（以較快的虛擬時間計）"""
    def __init__(self, pages: int, page_size: int, io_latency_ms: float):
        self.data = [bytearray(page_size) for _ in range(pages)]
        self.io_latency_ms = io_latency_ms
        self.io_count = 0

    def read_page(self, pid: int) -> bytes:
        self.io_count += 1
        time.sleep(self.io_latency_ms / 1000)   # 真實等待，僅示範用
        return bytes(self.data[pid])


class BufferPool:
    """簡單的緩衝池：記憶體快取最近讀過的頁"""
    def __init__(self, disk: SimDisk, nframes: int):
        self.disk = disk
        self.frames = {}          # pid -> bytes
        self.order = []           # FIFO 替換用的佇列
        self.nframes = nframes
        self.hit = 0
        self.miss = 0

    def get_page(self, pid: int) -> bytes:
        if pid in self.frames:
            self.hit += 1
            return self.frames[pid]
        self.miss += 1
        if len(self.frames) >= self.nframes:
            victim = self.order.pop(0)
            del self.frames[victim]
        page = self.disk.read_page(pid)
        self.frames[pid] = page
        self.order.append(pid)
        return page


# 展示：線性掃描（好區域性）vs 隨機存取（壞區域性）
def demo():
    disk = SimDisk(pages=1000, page_size=4096, io_latency_ms=10)  # 10ms 延遲
    bp = BufferPool(disk, nframes=100)

    # 線性掃描：每頁讀一次，共 1000 次 I/O
    for pid in range(1000):
        bp.get_page(pid)
    print(f"線性掃描: I/O 次數={disk.io_count}")

    # 重新建立緩衝池做隨機存取示範
    disk2 = SimDisk(pages=1000, page_size=4096, io_latency_ms=10)
    bp2 = BufferPool(disk2, nframes=100)
    random.seed(42)
    for _ in range(1000):
        bp2.get_page(random.randint(0, 999))
    print(f"隨機存取: I/O 次數={disk2.io_count}, 緩衝命中率={bp2.hit/1000:.2%}")

if __name__ == "__main__":
    demo()

執行時可觀察到：同樣 1000 次 get_page，線性掃描觸發 1000 次真實磁碟 I/O，而隨機存取在緩衝池的幫助下 I/O 次數相近，但命中率高；若把延遲調大，時間差距會立刻顯現。這正是層級效應的具體化。

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

設問題有 n 筆資料，每頁 B 筆，共 n/B 頁：

  • DRAM 內線性掃描：O(n) 次處理器存取，全部微秒內完成。
  • 磁碟線性掃描：n/B 次 I/O，若 B=4096、n=10⁹（約 4GB 資料），約需 25 萬次頁讀取；在 HDD 上以 10ms/次計算，持續 40 分鐘；但若這 4GB 是連續存放，每頁只需邏輯定址且循序讀取可達 200MB/s，實際只需約 20 秒。客群：循序 vs 循序的差距是幾百倍。
  • 隨機 4KB 讀取（HDD）：10ms/次 → 100 IOPS → 讀 1GB 隨機頁需要 1000MB/4KB × 10ms ≈ 2.8 小時。這個數字解釋了為何「隨機小 I/O」是磁碟演算法的第一公敵。

練習#

  1. 使用上面的模擬器，將 nframes 從 100 改成 10，比較線性掃描的 I/O 次數是否不變，並解釋為什麼（提示：線性掃描本身也是壞區域性的一種）。
  2. 假設 HDD 延遲 10ms、SSD 延遲 100μs，計算隨機讀取 100 萬個 4KB 頁分別需要多久。這說明了 SSD 對哪一類演算法最友善？
  3. 寫一個簡單實驗：對同一份頁序列，先用 FIFO 替換、再用 LRU 替換，觀察命中率差異。什麼存取模式會讓 FIFO 表現明顯較差？