HackMD
Playing with ext4
tags: linux
目錄
簡介
本文件記錄建立一個 ext4 檔案系統的過程和觀察其空間分配機制而進行的實驗。
使用 ubuntu 18.04 為作業系統，在 Transcend 64GB 隨身碟上建立一個 ext4 檔案系統。
建立 ext4
找到儲存裝置
第一步是找出用於建立 ext4 的儲存裝置，這邊使用的是隨身碟。
建立分區
然後可以使用 gdisk 分割出所需要的大小。gdisk 提供 GPT 分割，若需要使用 MBR 分割，可以使用 fdisk，兩者使用方法基本相同。
使用 n 新增磁區，為減少 ext 的 group block 數量，只提供 200MB 的空間。
設定完成後可以使用 p 預覽分割結果，確認無誤後使用 w 實際開始分割。
完成後再次使用lsblk即可發現新分割的磁區。
格式化
此時分割區尚未進行格式化，使用mkfs格式化並設定 block size 為 4096 bytes，以最少化 block group 的數量。
觀察和實驗
使用 dumpe2fs 吧！
此時 ext4 已建立完畢，使用 dumpe2fs 可觀察 ext4 的詳細資訊。如 Free blocks 的數量，建立時設定的 block size等。
其中 superblock, Group descriptors 等資料佔用了第 0-25 blocks，但 free blocks 並不是從 26 開始，而是 5732。
清空檔案及資料夾
這時候先觀察一下 ext4 內的檔案，發現格式化時預留了一塊lost+found的空間，總共佔用 16384 bytes。
移除掉lost+found。
再次使用 dumpe2fs，因為 bytes，即lost+found應該佔用 4 個 blocks。移除lost+found後Group 0也空出 4 個 blocks，符合預期。
然而無法得知被佔用的 1635-5731 blocks 的具體用途，應為維持 ext4 運作的保留區域。
空間分配方式
為了得知 ext4 分配空間的方式，以下對 ext4 進行多種不同的寫入、刪除操作並進行觀察。
排除 last freed first
為 ext4 建立檔案。
再次觀察 ext4。
新的檔案佔用了最前面的 data block 及 inode。
在使用 group 0 的 inode 的同時。
使用了 group 1 的 data block 而不是 group 0 的 data block。
繼續建立檔案並觀察。系統持續使用 group 0 最前面的 inode 和 group 1 最前面的 data block。
此時可以確認並不是使用 last freed first 的空間分配機制。
排除 least recently used first, next unused first, Last in first out
按2.txt, 3.txt, 4.txt的順序移除檔案，再建立6.txt並觀察。
此時發現，6.txt會佔用最前面的 inode 和 data block。而不是最後被刪除的4.txt所佔用的 data block (last in first out 機制)。或5.txt後面的空間(next unused first, least recently used first 機制)。
至此可以確認並不是使用 last freed first, least recently used first 或 next unused first 的空間分配機制。
判別 first fit, best fit
經過以上的觀察後，基本可以確定 ext4 是使用 first unused 機制。但尚未得知是根據 first fit 還是 best fit。
為此進行建立及刪除檔案的操作，產生一個 2 個連續 free data blocks 在前,1 個連續 free data block 在後的結構。
再次建立一個佔用 1 block size 的檔案，並觀察 data block 的使用狀況。
結果是在後方的單一 data block 被優先使用了，可見 ext4 是使用 best fit 機制。
結論
ext4 是使用 first best fit 的 data block 分配機制。
值得思考的是，ext4 是屬於索引式檔案系統，資料碎片化對效能影響較小，卻依然選擇速度較慢但資料碎片化較少的 best fit 機制，而不是速度更快但碎片化嚴重的 first fit 機制。這可能是考量 ext4 的 inode 有提供 extend 機制，可以使用單一的指標結構表示多個連續的 data block,。有較多連續的空間時，用於表示 data block 的指標數量就會減少，使用到 inode 的雙重，甚至三重指標的機率就會下降，此時理論效能則會獲得提升。
順帶一提，inode 的分配是采用單純的 first unused 機制，因為每個檔案只會使用一個 inode，因此不存在 best fit 和 first fit 的差別。
