文件系統的物理結構分配
當前位置：點晴教程→知識管理交流
→『 技術文檔交流 』
在計算機世界中，文件是數據的抽象集合，它為用戶提供了一種直觀的方式來處理數據。而這些文件的數據最終必須存儲在具體的物理設備上，例如HDD、SSD 或是 USB。這些存儲設備通過設備控制器將他們的物理介質映射為一個巨大的、可隨機尋址的地址空間，我們可以將其看作一個超大的數組。一個設備可以儲存多個文件，那么，如何將多個抽象的文件映射到這一巨大空間上，就是一個非常重要的問題。文件系統的設計在這里起著至關重要的作用，它必須以合理的方式將文件分布到物理存儲介質上，以確保存儲和訪問的高效性。本文將為您介紹幾種經典的文件分配方式及其優缺點。 物理存儲的基本概念：塊與簇當硬盤經過設備控制器抽象為一個超大的數組后，對于設備來說，塊（block）通常是存儲介質的最小單元。每個塊有固定的大小，例如 4KB，由存儲介質本身決定。這些塊是存儲設備的最小分配和管理單位。而為了更好地利用空間并減少管理開銷，在系統中，塊可以進一步組合成更大的存儲單位，稱為簇（cluster），通常簇由幾個連續的塊組成。通常在格式化時可以指定簇大小，之后就不再改變，一簇至少包含一個塊，也可以設定為包含多個塊。 簇的大小直接影響到存儲效率和文件系統的性能。大簇（如32KB或64KB）意味著每個簇可以容納更多數據，從而減少文件系統管理這些簇的開銷，管理更容易且讀寫性能高，但會導致即使是 1 字節的文件也會占用一簇，造成小文件占用過多空間的情況，導致內部碎片（internal fragmentation）。反之，小簇（如512字節或4KB）可以減少內部碎片，但會增加管理簇的復雜性和處理開銷。因此，簇大小的選擇是權衡存儲效率與管理開銷的重要決策。 在格式化完成后，簇就成為文件系統視角下的最小分配單位，后文就不區分這兩個概念了。 連續分配：最簡單卻難以擴展的方案存儲器已經劃分為以簇編址的巨大數組，而文件也被劃分為幾簇，接下來我們要考慮怎樣為他們安排位置。 連續分配（Contiguous Allocation）是文件系統中最簡單的物理分配方式。它將文件存儲在一組連續的簇中。在文件記錄中，只需要存儲文件的起始位置和長度，這樣在訪問文件時，只需要從起始位置開始，讀取指定長度的數據即可。由于連續分配的文件在物理磁盤上是緊密排列的，因此它非常適合隨機訪問（random access），尤其是對大文件的順序訪問時，性能表現十分優秀。當新增文件時，直接找到可容納下文件的連續塊插入即可。 然而，連續分配也有許多致命缺點：
這些缺點使得連續分配在現代操作系統中很少使用，尤其是在面對高頻率的文件操作時。然而，在某些特定情況下，例如對于磁帶這樣的順序訪問存儲介質（sequential access storage medium），連續分配仍然是有效的選擇。 簡單鏈表分配：解決碎片問題的嘗試為了解決外部碎片的問題，一種改進的方法是鏈表分配（Linked Allocation）。在鏈表分配中，文件被分為多個塊，每個塊通過一個指針鏈接到下一個塊，從而形成一個鏈表。文件記錄只需要存儲文件的第一個塊的地址（以及可能的最后一個塊地址），其余的塊通過鏈表指針進行訪問。這樣離散的分配方式也就不再有外部碎片。 然而，鏈表分配也有明顯的缺點：
鏈表分配解決了外部碎片的問題，但由于無法隨機訪問和存儲開銷大的缺點，使得它在現代操作系統中的應用也較為有限。 顯式鏈表分配：文件分配表 (FAT)在鏈表分配的基礎上，另一種改進方式是顯式鏈表分配（Explicit Linked Allocation），即將每個塊的指針信息集（即下一塊）中存儲在一個專門的表中（而非儲存到每個塊中），這就是文件分配表（File Allocation Table, FAT）。FAT 是一種將每一個簇和其后續簇的位置關系集中存儲的結構，通過查找文件的起始簇，可以逐步找到文件的所有簇。 在 FAT 結構下，文件記錄仍只需要存儲文件的起始塊位置，然后通過 FAT 來找到其他塊的位置。這樣的設計使得在文件內進行塊間跳轉變得更加方便，雖然 FAT 仍然不能真正實現隨機訪問，但跳轉速度相較于簡單鏈表分配要快得多。為了提高訪問速度，操作系統通常將 FAT 緩存在內存中，從而在文件訪問時減少對磁盤的頻繁讀取。 FAT 結構具有如下特點：
FAT 系列文件系統最早設計于 1977 年，歷經多次演化，至今仍有應用，特別是在嵌入式設備和閃存設備（如 USB 閃存）中。FAT 系列文件系統（如 FAT16、FAT32）由于其簡單性和廣泛兼容性，成為了很多嵌入式設備的首選。exFAT 是微軟在 2006 年引入的一種新的文件系統，專為閃存設備設計，主要目的是在 FAT32 的基礎上克服其局限性，相比上面介紹的原始版本拓展了很多功能，同時保持兼容性。 索引分配：真正實現隨機訪問在離散存儲的基礎上，顯然不一定要使用鏈表。可以在文件記錄中以變長數組記錄每個塊的位置，這樣就可以實現真正的隨機訪問。這種數組叫做索引（index），這種分配方式稱為索引分配（Indexed Allocation）。在索引分配中，文件系統會為在每個文件的文件記錄里維護其索引塊，索引塊中存儲了文件各個數據塊的物理位置。通過查找這個索引塊，操作系統可以直接定位到文件的任意塊，從而實現快速的隨機訪問。簡單來說，索引用數組實現就可以，也可以選擇二叉樹或哈希表，這就不是本文的重點了。
單級索引（Single-Level Index）是最簡單的一種索引分配方式，其中每個文件都有一個單獨的索引塊，記錄文件的所有數據塊位置。這使得文件的訪問變得非常靈活，特別是對于需要頻繁隨機訪問的場景，索引分配具有顯著的優勢。此外，由于索引塊集中存儲了所有的塊位置，文件的增刪也變得更加容易，只需更新索引塊即可，無需對物理塊進行復雜的移動操作。 例如，假設一個單級索引系統，每個索引塊的大小為 4KB，且每個指針占用 4 字節，那么一個索引塊最多可以容納 4KB / 4B = 1024 個指針。如果每個數據塊的大小也是 4KB，那么這個文件系統支持的最大文件大小為 1024 * 4KB = 4MB。 由此可以看出，單級索引適用于中小型文件。然而，索引塊的大小是有限的，這意味著單級索引的文件大小上限很低，只能用于較小的文件。對于非常大的文件，則需要使用其他的多級索引方案。 多級索引由于文件記錄的大小通常是有限的，因此文件系統引入了多級索引（Multi-Level Indexing）的概念，也叫間接索引。多級索引通過使用多個層次的索引塊來管理文件的數據塊位置。例如，兩級索引（Two-Level Indexing）使用一個一級索引塊指向多個二級索引塊，而二級索引塊則記錄文件的數據塊位置。這種設計使得文件系統可以存儲比單級索引更大的文件。 以二級索引為例子，文件記錄中儲存的索引是一級索引，一級索引中指向的塊并非文件本身，而是其他索引塊，叫做二級索引，由二級索引記錄文件簇的物理位置。 混合索引：現代文件系統的主流多級索引提高了單文件大小的上限，但是，如果文件記錄中全部使用多級索引，即使只有 1 字節的文件，也至少需要占用多級索引中每一級索引塊各一個。文件越小，索引本身帶來的開銷越大。
現代文件系統為了平衡小型文件和大型文件的存儲需求，引入了混合索引（Hybrid Indexing）的方式。混合索引結合了直接索引、間接索引和多級索引的優點。例如，在某些文件系統中，文件記錄中包含了一些直接指向數據塊的指針（適用于小文件），以及間接指向索引塊的指針（適用于較大的文件）。這種設計使得文件系統能夠高效地處理各種不同大小的文件，既能減少小文件的管理開銷，又能支持大型文件的高效存取。 例如，假設一個文件系統使用混合索引的方式，每個 inode 包含 12 個直接指針、1 個一級間接指針、1 個二級間接指針以及 1 個三級間接指針。假設每個數據塊大小為 4KB，每個指針占用 4 字節。則：
因此，該混合索引結構支持的最大文件大小約為 48KB + 4MB + 4GB + 4TB。由此可以看出，混合索引的設計使得文件系統既能夠高效地處理小型文件，又可以支持非常大的文件。 混合索引方式被廣泛應用于現代絕大多數文件系統中，例如：
混合索引結構的優勢在于其對小型文件和大型文件的適應性，使得文件系統能夠在各種應用場景下提供高效的存儲和訪問性能。因此，混合索引成為了現代文件系統設計的主流選擇。通過這種方式，文件系統不僅能夠高效管理存儲空間，還能夠提供靈活的隨機訪問能力，以滿足不同用戶和應用程序的需求。 ?作者Ofnoname 博客園https://www.cnblogs.com/ofnoname/p/18492168 該文章在 2024/10/23 9:04:28 編輯過 |
關鍵字查詢
相關文章
正在查詢... 
|
400 186 1886
