有趣

有用

有態(tài)

設計文件系統(tǒng)思路

這一篇文章是帶大家思考，fatfs文件系統(tǒng)是怎樣逐步發(fā)展而來的，如果你是文件系統(tǒng)的設計者，你會怎么設計?希望從這個思考的過程，幫助大家掌握fatfs里面的一些基本概念。

要設計一種文件系統(tǒng)，說白了就是要實現(xiàn)一種文件名與文件數(shù)據(jù)的映射，也就是給定一個文件名后，就能找到它所對應的映射。這看似簡單，事實上卻不簡單。要考慮的問題很多，比如數(shù)據(jù)的不連續(xù)存儲、存儲空間的有效利用等等。

這里我們從簡單的實現(xiàn)算法開始思考，一步步逼近fatfs的設計思想。

原始文件系統(tǒng)

存儲設備(flsh、軟盤、硬盤)上面是由很多順序分布的扇區(qū)所構成的，文件里面的內(nèi)容就存儲在這些扇區(qū)上面，最簡單的算法，就是在先在扇區(qū)里面存儲文件名，然后在文件名的后面存儲對應數(shù)據(jù)。其他文件用同樣的方法依次存儲，最終文件系統(tǒng)里面的的布局如下圖所示:

這種儲存文件的方法，有一定的優(yōu)點，比如說算法簡單，沒有任何的空間浪費，數(shù)據(jù)的儲存十分緊湊等等。但是致命的缺點就是文件的搜索效率太低，每次查找文件的時候，遍歷全部的扇區(qū)顯然是非常愚蠢的辦法。

改進方案一

把文件名全部保存在扇區(qū)的起始位置，這樣就能避免對整個扇區(qū)的搜索了，如下圖

可以看到，這里已經(jīng)出現(xiàn)了一些內(nèi)存空間的浪費，但這個是必然會存在的，空間換時間。另外的一個缺點是，現(xiàn)在文件的保存只能在連續(xù)的扇區(qū)保存，一旦小文件被刪除之后，它騰出來的內(nèi)存空間將不足以用來儲存其他一些大文件。我們可以把它理解為"磁盤碎片"

改進方案二

要讓數(shù)據(jù)可以跨扇區(qū)儲存，又要知道各部分數(shù)據(jù)的具體存儲位置，該如何實現(xiàn)呢?這時候我們應該想起鏈表這種數(shù)據(jù)結構，因為鏈表就是專門針對非連續(xù)空間存儲的。我們可以在每個扇區(qū)的頭部都設置一個專門的字段來記錄扇區(qū)所屬文件以及下一個扇區(qū)的地址，這樣讀取某一個扇區(qū)之后，就能知道下一個扇區(qū)在什么位置了。

這樣，就能把"磁盤碎片"空間也拼湊起來使用了。只是現(xiàn)在我們定位一個文件的時候，還是得逐個扇區(qū)地讀一下文件名，效率依然很低。

改進方案三

我們要解決遍歷扇區(qū)的"惡夢"，就必須把文件名剝離出來，不能讓隨意地保存在扇區(qū)里面。否則永遠擺脫不了遍歷扇區(qū)的結局。我們現(xiàn)在回想一下，之所要把文件名保存在扇區(qū)上，無非是因為需要靠文件名幫助我們定位到文件的位置。

這其實跟我們看書非常相類似，我們拿到一本書，如果想找到某一個章節(jié)的內(nèi)容，一個笨方法就是逐頁地翻書，直到我們找到這個章節(jié)的名字。只不過這個笨方法我們都不喜歡用，我們直接通過書本前幾頁的目錄就能得到目標章節(jié)的位置了。

我們模仿書的目錄一樣，拿出一些扇區(qū)專門用來記錄文件名和它對應的數(shù)據(jù)其實位置。這樣一來，當我們想到查找某些文件內(nèi)容時，就查一下這個"目錄"就可以了。這個"目錄"我們把它叫做文件索引表。如下圖:

改進方案四

現(xiàn)在每個扇區(qū)的頭部還有一個專門的字段來記錄扇區(qū)所屬文件以及下一個扇區(qū)的地址，這個字段我們也把它剝離出來集中管理，像文件索引表一樣，也用一些扇區(qū)來保存，這樣子會顯得整個文件系統(tǒng)，架構更加的清晰，管理更加方便。這些用來保扇區(qū)關系的扇區(qū)，在fatfs里面就叫做FAT(File Allocation Table)表，如下圖:

改進方案五

當磁盤里面的扇區(qū)數(shù)量非常多的時候，它們之間的鏈式關系會非常復雜，F(xiàn)AT表需要白白消耗很多內(nèi)存來儲存它們，為了減小扇區(qū)間鏈式關系的復雜度，我們可以把多個扇區(qū)合并成一個新的儲存單位。這樣一來，新的儲存單位間的鏈式關系就會簡化很多。在fat32文件系統(tǒng)里面，這種新的儲存單位稱為簇。

總結

到這里，通過一個對文件系統(tǒng)不斷迭代優(yōu)化的過程，就把fatfs的基本概念，通俗易懂地介紹給大家了。希望大家能夠深刻理解下面這幾個概念的含義:

• 文件索引表
• FAT表
• 簇