Advanced Storage SystemsNTHU — Spring 2026
← Back to Data Compression

Data Compression

Android 從 512 MB 漲到 3 GB

從 Android 2.3.6 到 8.0，應用程式、framework、字型、各種 system resource 不斷增加，系統分割區一路從 512 MB 漲到 3 GB。然而，這些檔案都是 read-only 的，只有更新時才會寫入新的，為了省空間，工程師把它們以壓縮形式存在手機當中。

壓縮除了讓有限的儲存裝置裝更多東西，還能省 I/O bandwidth，但代價是讀資料前要先解壓縮。

請問：如何讓我花的 CPU 時間，比省下的 I/O 時間還低呢？

CPU vs I/O：壓縮真的划算嗎

假設要從 NVMe SSD（3 GB/s）讀 1 GB 資料。沒壓縮，純 I/O 約 333 ms。

用 zstd 壓縮率 2 倍，disk 只剩 500 MB，讀取 167 ms；但 zstd 單執行緒解壓速度約 1.5 GB/s，解 1 GB 要 667 ms。總時間 834 ms，反而比沒壓縮慢 2.5 倍。

改用 LZ4（壓縮率 1.5 倍、解壓快），讀 667 MB 要 222 ms，解壓速度約 4 GB/s，解 1 GB 只需 250 ms。總時間 472 ms，差距縮小，但仍比沒壓縮慢。

換成 HDD（100 MB/s），讀 1 GB 要 10 秒；zstd 壓縮後變 5 秒讀加 0.67 秒解壓，共 5.67 秒。HDD 上壓縮幾乎一定划算，disk 太慢，CPU 怎麼花都值得。

CPU vs I/O time comparison across compression scenarios on NVMe SSD and HDD
CPU vs I/O 時間取捨：快 SSD 上 zstd 反而比不壓縮慢，HDD 上壓縮幾乎一定划算

很多人以為「壓縮率越高越好」。其實不是。壓縮率高的演算法解壓縮也慢，在快速 SSD 上經常比不壓縮還慢。實務上要把「I/O 時間 + CPU 時間」一起算才能知道哪個演算法對你的 workload 划算。

常見的壓縮演算法

演算法壓縮率壓縮速度解壓速度典型場景
LZ4低 (~2x)極快 (~500 MB/s)極快 (~4 GB/s)即時壓縮、低延遲、kernel 與檔案系統
Snappy低-中 (~2x)快 (~400 MB/s)快 (~2 GB/s)RocksDB、Cassandra、LevelDB
gzip (deflate)中-高 (~3x)慢 (~30 MB/s)中等 (~400 MB/s)一般用途、HTTP、tar.gz
zstd高 (~3-5x，可調)中等 (~150 MB/s @ L3)快 (~1.5 GB/s)現代取代 gzip 的首選
Brotli高 (~4x，對文字特別好)慢中等HTTP/2、字型壓縮
xz (LZMA)極高 (~5x+)極慢慢一次壓多次解的 archive、kernel image

（數字是粗略的數量級，實際效能會因 input 特性和硬體大幅變動，不用背喔！）

選擇壓縮演算法的原則：

  • I/O 慢、CPU 閒（傳統 HDD、network storage、distro package）：選壓縮率高的（zstd、brotli、xz）

  • I/O 快、CPU 緊（NVMe SSD、in-memory cache、手機）：選解壓快的（LZ4、Snappy）

  • 已被壓縮過的資料（JPEG、video、加密過的資料）：不要再壓縮，幾乎壓不動，純粹浪費 CPU

  • 沒有「最好」的演算法，只有「最適合你 workload 的演算法」。Web 字型用 Brotli（壓一次傳給上億個使用者，可以接受極慢壓縮換最高壓縮率）。LSM-tree 的 SSTable 多半用 LZ4 或 Snappy（讀路徑要快）。Linux kernel image 用 xz（開機時解壓一次就好）。

  • zstd 是 Meta 這家公司對人類文明最大的貢獻之一，他可以讓我們調 level。level 1 跟 level 19 是同一份 code 但壓縮率差很多，level 越高壓縮率越好但壓縮越慢，解壓速度反而通常差不多。所以「慢壓一次、快解很多次」的 workload（例如 Linux distro 的 package、CDN 內容）會把 level 開到最高。

壓縮的單位：Block Compression

假設你要壓縮一份 1 GB 的檔案，有兩個極端做法。第一種：整份檔案丟給 gzip，得到 100 MB 的壓縮檔。但接下來如果你只想讀檔案中間某個 100 bytes 的資料，你必須從頭把整個 100 MB 解壓縮完才能找到那個位置。第二種：每個 byte 都單獨壓縮。但單一個 byte 沒重複可言，壓縮率為 0。

折衷做法是 block compression：把資料切成固定大小的 block，每個 block 獨立壓縮、獨立解壓縮。讀的時候你只需要解壓縮包含目標的那個 block，不需要碰其他 block。這是現代 storage system 普遍採用的做法。

但 block 切多大就是一個經典的 trade-off：

  • Block 越大：壓縮演算法看到的資料越多，能找到更多重複，壓縮率越好。但讀一筆小資料也要解壓整個 block，read amplification 變大。
  • Block 越小：解壓成本低、random access 便宜。但壓縮率變差。

Fixed-Input vs Fixed-Output：兩種設計哲學

還有一個 design choice：要讓「壓縮前的輸入量」固定，還是「壓縮後的輸出量」固定？

  • Fixed-input：每次拿固定 N bytes 的原始資料丟給壓縮器，得到 variable-sized 的 compressed block。例如「我每 128 KB 的原始資料壓成一個 block」，輸出可能是 30 KB、可能是 80 KB，因為不同區段壓縮率不同。

  • Fixed-output：不斷往壓縮器塞資料，直到壓縮輸出剛好填滿 N bytes 就停。例如「我要每個 disk block 都恰好是 4 KB」，於是塞資料塞到輸出 = 4 KB 就停，下一段繼續。

兩者的差別在於 random access 的成本：

  • Fixed-input 沒辦法直接從 logical offset 算出在 disk 上的位置（每個 block 壓完大小不一樣），需要額外維護一個 offset index，而且讀 1 byte 要解壓整個 fixed-input chunk。
  • Fixed-output 因為每個 block 大小一樣，可以直接用 block 編號 × N 算出 disk 位置，O(1) 定位，而且每次解壓量上限是固定的。

代價是壓縮率：fixed-output 的壓縮器經常壓到一半被「卡住」（輸出快滿了），無法充分利用接下來的重複，壓縮率比 fixed-input 差。

EROFS vs Squashfs 之爭

回到 Android 的唯讀檔案系統。 Squashfs 是一個常用的 Linux 壓縮 read-only 檔案系統，常用於你的 Linux 開機碟。

Android 手機廠商曾經試著直接採用 Squashfs 當作唯讀檔案系統，結果造成手機卡卡的、畫面凍結。Why？

Squashfs 採用 fixed-input 設計：把檔案切成固定大小的 chunk，每個 chunk 個別壓縮。 因為 chunk 越大壓縮率越好，所以工程師很自然的把 chunk 開到 128 KB 以換取最省的儲存空間。

問題是：當應用程式想讀檔案中的 1 byte（隨機存取在手機上很常見，例如 dynamic library 載入時跳到某個 function offset），檔案系統必須把那 1 byte 所在的整個 128 KB chunk 從 disk 讀出來、解壓縮，再把要的 1 byte 給應用程式。這叫 read amplification。1 byte 變成 128 KB 的 disk I/O 加上 128 KB 的 CPU 解壓工作。

對記憶體的影響尤為嚴重。解壓 128 KB 需要：

  1. 先在 kernel 配置一塊中間 buffer
  2. 把壓縮資料讀進來
  3. 再配置 32 個 4 KB physical page 裝解壓結果
  4. 再 copy 到 VFS 的 page cache

整個流程下來，原本 1 byte 的讀取，在記憶體裡留下幾十個 page 的足跡。

Squashfs read amplification and memory consumption: 1-byte request triggers full chunk decompression with intermediate buffers and many page allocations
Squashfs 的 fixed-input 設計讓 1 byte 讀取觸發整個 chunk 的 I/O、解壓、與大量 page 分配 （圖片來源：EROFS, USENIX ATC '19）

EROFS 的解法：fixed-output 4 KB blocks

EROFS（Enhanced Read-Only File System）2018 年由華為提出，在 2019 年進入 Linux mainline 4.19，部署在 HUAWEI EMUI 9.1 的超過一千萬支手機上。

EROFS 採用了 fixed-output，每個 compressed block 固定 4 KB，對齊 OS page size。

這樣讀 1 byte 最多只需要解壓一個 4 KB block，而且因為解壓後的資料剛好是一個 page 的倍數，可以做 in-place decompression：直接把解壓結果寫進 VFS 已經分配好的 page cache page 裡，省掉中間 buffer 和記憶體 copy。

代價是什麼？壓縮率。因為每個 4 KB block 的壓縮器看到的原始資料量比 Squashfs-128K 少。但 EROFS 用了一些工程巧思（例如允許一個壓縮輸出對應多個原始 page、不要求每個 block 邊界對齊 file 邊界），實際壓縮率比同樣 fixed-input 4 KB 的 Squashfs 還好。另外，EROFS 選擇使用 LZ4 而不是壓縮率更高的 zstd。因為手機 CPU 不強、電池有限，解壓縮速度比壓縮率更重要。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

  1. 假設一顆 NVMe SSD 的 random read bandwidth 是 5 GB/s，你的 workload 是讀 2 GB 資料。某個壓縮演算法壓縮率 3 倍、解壓速度 2 GB/s。請計算壓縮版的總時間（disk read + decompression）跟不壓縮的純 I/O 時間（2 GB / 5 GB/s）哪個快、差多少。這告訴你什麼？

  2. Squashfs 把 chunk size 從 4 KB 開到 128 KB，儲存空間從 592 MB 降到 380 MB，請分析他的 read amplification 和記憶體使用。

  3. EROFS 用 fixed-output 取代 fixed-input，得到 random access 友善的特性，但理論上壓縮率應該比 fixed-input 差。為什麼 EROFS 的儲存效率（533 MB）反而比 Squashfs-4K（592 MB）好？