如何設(shè)計(jì)文件系統(tǒng)LFS

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)如何設(shè)計(jì)文件系統(tǒng)LFS，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

    LFS 超快的文件系統(tǒng)，可以同時(shí)存儲(chǔ)海量大文件和小文件。并且不單單是一個(gè)文件系統(tǒng)，我還用作了數(shù)據(jù)庫。

    我的測試數(shù)據(jù)是：和 C 直接讀寫文件速度幾乎一樣。

    項(xiàng)目地址：github  git@osc

    注：這是一個(gè)開源項(xiàng)目，你可以自由使用，但對(duì)于開發(fā)者，我們需要審核，確認(rèn)是否能承擔(dān)開發(fā)工作。所以，需要 @ME.

    在設(shè)計(jì)之前，需要明確兩個(gè)目標(biāo)：高并發(fā)，超快讀寫。

    為了實(shí)現(xiàn)高并發(fā)，那么必須將每個(gè)并發(fā)進(jìn)行分離，各自做自己的工作，互不影響。意味著 A 和 B 可以同時(shí)讀相同的或者不同的文件，或者寫不同的文件，但是，不能寫同一個(gè)文件。

    為了實(shí)現(xiàn)超快讀寫，在高并發(fā)的前提下已經(jīng)可以很快的進(jìn)行文件的操作了，并且對(duì)文件的定位也非常重要，事實(shí)上，我是基于對(duì)文件定位的設(shè)計(jì)來實(shí)現(xiàn)的高并發(fā)。

    那么我的工作就變得清晰簡單了，我需要實(shí)現(xiàn)一個(gè)非常棒的文件定位就好了。

    為了更快的速度，我沒有使用文件名的方案（在應(yīng)用場景，這根本就不必用到），而是將文件名設(shè)計(jì)為一個(gè)文件 ID。我使用一個(gè) int 來實(shí)現(xiàn)，意味著最大可以提供 2^32 -1 個(gè)文件，這已經(jīng)很大了，幾乎可以存儲(chǔ)一個(gè)大型服務(wù)的所有文件了。（事實(shí)上，為了實(shí)現(xiàn)海量存儲(chǔ)，實(shí)現(xiàn)分布式，我們可以非常簡單的組織這個(gè)文件 ID，來實(shí)現(xiàn)一個(gè)宇宙唯一的文件 ID，為何這么說？因?yàn)槲募?ID 是自增長的，所以雖然有 int 的限制，但我們可以無視它，就是說文件 ID 也可以是變長的。）

    文件 ID 是自增長的，所以對(duì)于上層應(yīng)用來講，文件名是由文件系統(tǒng)生成的。這樣的好處是，文件名足夠小，并且因?yàn)槭窃O(shè)計(jì)好的，所以文件系統(tǒng)知道該怎么分配一個(gè)文件 ID 給上層應(yīng)用。并且可以根據(jù)這個(gè)文件 ID，實(shí)現(xiàn)理想的文件定位策略。在我的實(shí)現(xiàn)中，這個(gè)文件 ID 沒有任何神秘之處，所以不需要任何算法來計(jì)算出這個(gè)文件 ID，它只是自增長的而已，只不過它自己增長的非常恰到好處。

    暫時(shí)忘記文件 ID，先 Mark 一下，稍后再講，我們先來看一下如何能快速定位到文件內(nèi)容。最好的方式莫過于能直接知道文件內(nèi)容的存儲(chǔ)位置了（起始位置和結(jié)束位置），ok，那么我們就用兩個(gè) int 來存儲(chǔ)這兩個(gè)信息，然后我們就可以直接根據(jù)這個(gè)存儲(chǔ)位置找到實(shí)際的文件內(nèi)容了。嗯，沒錯(cuò)，這種方法不錯(cuò)。那么問題來了，我們有許多許多的文件，每個(gè)都需要記錄有位置信息才行，所以我們得弄一個(gè)文件出來，專門存儲(chǔ)這個(gè)位置信息來對(duì)應(yīng)文件的實(shí)際內(nèi)容。因此我做一個(gè)索引文件出來，用來記錄文件內(nèi)容的存儲(chǔ)位置（人們稱之為元數(shù)據(jù)，但我不這么理解，在 LFS 中，它就是一個(gè)索引文件 Index，稍后你也會(huì)理解為何如此命名）。這樣一來我可以用這個(gè)索引文件記錄許多個(gè)文件的位置信息了，在索引文件里查一下，就能知道存儲(chǔ)位置在什么地方，很簡單。不過，當(dāng)文件變得多起來的時(shí)候，和索引文件對(duì)應(yīng)的存儲(chǔ)實(shí)際內(nèi)容的文件會(huì)增長的比索引文件快得多，當(dāng)其增長到一定上限時(shí)，我們無法對(duì)其寫入新的內(nèi)容（受限于操作系統(tǒng)的文件格式，我們可能無法對(duì)一個(gè)單一文件寫入大量內(nèi)容，并且由于我們前面使用兩個(gè) int 來記錄位置信息，這就決定了，文件內(nèi)容不能大于 4G）。所以我們得對(duì)存儲(chǔ)實(shí)際內(nèi)容的文件進(jìn)行分塊，用許多許多的塊文件來存儲(chǔ)超過容量限制的內(nèi)容，在 LFS 里稱之為 Block。

    這樣一來我們可以存儲(chǔ)許多數(shù)據(jù)了，但是 Index 和 Block 的對(duì)應(yīng)關(guān)系被破壞掉了（事實(shí)上，我很樂意看到如此情況，因?yàn)橛纱?，才可以進(jìn)入高并發(fā)的第一步）。為何這么說，如果依然保留這種對(duì)應(yīng)關(guān)系也是可以的，就是說每個(gè) Index 都有一個(gè) Block 與之對(duì)應(yīng)。但是這樣一來，Index 會(huì)有許多個(gè)，并且如果一個(gè) Block 只存儲(chǔ)一個(gè)文件的話，那么 Index 會(huì)變得非常?。ㄖ挥?8 字節(jié)），這會(huì)造成 Index 的嚴(yán)重碎片化，而一旦 Index 變得碎片化了，那么我們根據(jù)其進(jìn)行定位文件內(nèi)容也相應(yīng)變得更復(fù)雜了。所以，我們打破 Index 和 Block 的對(duì)應(yīng)關(guān)系，使用另外一種方式，令 Block 對(duì)應(yīng)到 Index。使 Index 中記錄每個(gè)文件對(duì)應(yīng)的 Block ID，來實(shí)現(xiàn)新的對(duì)應(yīng)關(guān)系，這就增加了一個(gè) int 來記錄 Block ID。這樣，Index 就可以記錄許多個(gè) Block 了，并且也不會(huì)產(chǎn)生碎片化，可以平穩(wěn)的進(jìn)行增長了。

    這樣一來，我們就可以實(shí)現(xiàn)一種并發(fā)了。因?yàn)槊總€(gè)文件都會(huì)記錄自己的 Block ID，那么當(dāng)對(duì)不同文件進(jìn)行操作時(shí)，意味著，是對(duì)不同 Block 進(jìn)行操作，因?yàn)槊總€(gè) Block 具有獨(dú)立性，所以，只要同一時(shí)刻，處理的不是同一個(gè) Block，那么許多個(gè) Block 可以自由的進(jìn)行處理，互不影響。至此，我們已經(jīng)可以實(shí)現(xiàn)部分并發(fā)了。

    對(duì)于 Index 來講，已經(jīng)記錄的位置信息也是可以進(jìn)行并發(fā)處理的。因?yàn)橐呀?jīng)記錄過的內(nèi)容不會(huì)再次發(fā)生改變，所以讀取索引時(shí)，可以實(shí)現(xiàn)高并發(fā)，從而實(shí)現(xiàn)讀取的高并發(fā)。

    不過，這里有一個(gè)問題，被前文忽略了，就是 Index 是怎么寫的呢？

    當(dāng) LFS 收到寫文件請(qǐng)求時(shí)，需要找到一個(gè)空閑的 Block，并且將 Block ID 和該 Block 內(nèi)的位置信息記錄到 Index 中，即 Index 中的每個(gè)記錄有 12 個(gè)字節(jié)。單線程處理時(shí)沒有任何問題，不停的對(duì)這個(gè) Index 進(jìn)行追加寫。但是當(dāng)并發(fā)產(chǎn)生時(shí)，我們就遇到了麻煩，Index 的內(nèi)容會(huì)被哪個(gè)線程進(jìn)行寫操作呢？可能會(huì)被寫亂。所以，我們的要求高并發(fā)之路，在這里被擋了下來，這里會(huì)變成單線程操作。不過，幸運(yùn)的是，Index 寫的內(nèi)容很少，每次只有 12 個(gè)字節(jié)，所以會(huì)很快，從而降低了對(duì)并發(fā)的影響。

    恰好，和 Block 類似，我們也可以用許多個(gè) Index 來實(shí)現(xiàn)高并發(fā)。就是說，每一個(gè) Index 只有一個(gè)線程在寫，這樣一來，高并發(fā)又提高了一個(gè)量級(jí)。

    至此，我們來描述下 Index 的格式：BlockID:int, start:int, end:int，共 12 個(gè)字節(jié)。每一個(gè)文件都有這 12 個(gè)字節(jié)。但是？額……我們的文件 ID 在哪里呢？

    答案是：沒有文件 ID。

    接下來講一下，我們前面 Mark 的文件 ID。如我所說，沒有文件 ID 會(huì)存儲(chǔ)，那么是如何找到對(duì)應(yīng)的文件內(nèi)容的呢，就是說如何找到 Index 內(nèi)的位置信息呢？

    事實(shí)上，我很討厭文件 ID 這個(gè)東西，所以有意避開它了，因?yàn)榇_實(shí)沒有必要來存儲(chǔ)這個(gè)文件 ID，如果是文件名的話，那就不得不存儲(chǔ)了，但是幸好在 LFS 設(shè)計(jì)之初，就使用的是文件 ID。并且我為什么要浪費(fèi)字節(jié)來存儲(chǔ)文件 ID 呢？所以，由于我們之前的設(shè)計(jì)，我們可以不用存儲(chǔ)文件 ID 了，這就是說，LFS 內(nèi)不會(huì)有任何的查找過程，即使是 Index 內(nèi)也不會(huì)。

    LFS 使用的方案是通過計(jì)算找到具體內(nèi)容，并且只有計(jì)算。由于 Index 內(nèi)每個(gè)文件都是相同的 12 個(gè)字節(jié)的記錄，所以，LFS 通過應(yīng)用層傳來的文件 ID 乘以 12 個(gè)字節(jié)，就得到了，該文件 ID 在 Index 內(nèi)的位置，然后取出這 12 個(gè)字節(jié)就能到對(duì)應(yīng)的 Block 進(jìn)行操作了。索引一定需要哈?；蛘吲判?？看樣子不是。所以這也是我稱之為索引的原因，因?yàn)?Index 發(fā)揮的索引的作用比元數(shù)據(jù)的作用高得多。

    不過，因?yàn)?Index 文件也有多個(gè)，那么首先我們得知道文件 ID，所在的 Index 才行。幸好，每個(gè) Index 的額定大小是相同的，即每個(gè) Index 都可以記錄相同數(shù)量的文件位置信息。并且每個(gè) Index 都是有編號(hào)的，即我們理解為：編號(hào)為 0 的 Index 存儲(chǔ)文件 ID [0 - 99] 的位置信息，編號(hào)為 1 的 Index 存儲(chǔ)文件 ID [100 - 199] 的位置信息；現(xiàn)在需要讀取文件 ID 為 109 的內(nèi)容，那么使用 Math.floor(109 / 100)，得到 1 即為編號(hào)為 1 的 Index；然后我們還需要獲得在該 Index 內(nèi)的文件 ID，即：109 - (1 * 100) = 9；最后，因?yàn)槊總€(gè)文件記錄 12 個(gè)字節(jié)的信息，所以：9 * 12 = 108，即為索引內(nèi)的偏移，然后取出后面的 12 個(gè)字節(jié)，就是對(duì)應(yīng) Block 的信息了。從而根據(jù)讀取到的 Block 信息對(duì) Block 進(jìn)行操作。

    因?yàn)槲募?ID 與 Index 是隱式關(guān)聯(lián)的，所以，在并發(fā)時(shí)分配空閑 Index 時(shí)，即意味著，分配了一個(gè)恰到好處的文件 ID，這樣就實(shí)現(xiàn)了文件 ID 的自增長，并且確實(shí)恰到好處。

    這就是 LFS 的核心原理。 有什么理由會(huì)不快呢？

    核心原理，看似簡單，但是，LFS 實(shí)現(xiàn)的更多，支持更新和刪除，尤其是更新，實(shí)現(xiàn)起來確實(shí)復(fù)雜。

    LFS 會(huì)像其他的文件系統(tǒng)一樣在更新時(shí)使用擴(kuò)展塊嗎？不會(huì)，為什么需要呢？我們已經(jīng)有了 Block，那么直接用 Block 進(jìn)行更新就好了。LFS 為更新提供了多種操作方式，暫且以實(shí)現(xiàn)起來最簡單，并且描述起來也最簡單的方式來做一個(gè)說明：

    操作方式之一是，先刪除舊的內(nèi)容，然后重新寫文件。即重新進(jìn)行一次寫文件的流程，只不過，此時(shí)，文件 ID 不需要增長，直接向指定的文件 ID 覆蓋寫入內(nèi)容即可。這也就意味著，即使是在第一次寫文件的時(shí)候（LFS 還沒有自增到該文件 ID），也可以使用指定的文件 ID 來寫入內(nèi)容，并不是一定要 LFS 先生成該文件 ID，然后才能進(jìn)行寫入（但是我個(gè)人不建議這么做）。

    其他的操作方式是在原數(shù)據(jù)上進(jìn)行修改（處理方式不同），不刪除舊的內(nèi)容。如果新內(nèi)容大于原來的內(nèi)容的話，會(huì)分配一個(gè)新的 Block 用來寫入溢出的內(nèi)容。這個(gè)過程可能會(huì)產(chǎn)生數(shù)據(jù)遷移，幸好，LFS 的多種更新方式中存在避免數(shù)據(jù)遷移的方式，并且也提供分配更少 Block 的方式來使更新效率最大化。（我很喜歡這些處理方式，非常符合我的工作需求，對(duì)于更新頻繁，或者不斷增長的內(nèi)容，非常棒。）

    由于更新方式有多種以應(yīng)對(duì)各種需求，所以更新的功能實(shí)現(xiàn)起來很復(fù)雜，但對(duì)外 API 依然很簡單。事實(shí)上，LFS 沒有更新的 API，寫文件的 API 同時(shí)實(shí)現(xiàn)了更新，這樣對(duì)外層應(yīng)用來講會(huì)更簡單（為什么非要弄一個(gè)更新 API 呢？NO!）。

    LFS 把許多文件都進(jìn)行分塊處理，就是說，幾乎每個(gè)部分都是并發(fā)的。每個(gè)文件的大小默認(rèn)是 64M（為什么？不是因?yàn)榱餍?，而是我認(rèn)為 64M 可以非常快的一次性載入內(nèi)存，即使是配置不怎么樣的機(jī)器。事實(shí)上，如你所見，幾乎沒有多少 CPU 計(jì)算，所以，LFS 更適合部署在成本低但 IO 優(yōu)秀的機(jī)器上，從而減少成本。成本也是 LFS 的要求之一，我希望任何人都能用得起 LFS。），可以用來存儲(chǔ)海量大文件和小文件，由于前面介紹的原理，這意味著，可以同時(shí)存儲(chǔ)海量大文件和小文件。

    并且，我不單把 LFS 只作為一個(gè)文件系統(tǒng)來用，事實(shí)上，我個(gè)人也使用它的數(shù)據(jù)庫特性，相信這一點(diǎn)大家都能理解。

    另外，LFS 在計(jì)劃中，提供碎片整理，用來將碎片進(jìn)行合并處理等，希望有意向的伙伴可以加入進(jìn)來。事實(shí)上，我已經(jīng)通過一種方式，來將這種操作變得更簡單，但還有部分尚未實(shí)現(xiàn)。

上述就是小編為大家分享的如何設(shè)計(jì)文件系統(tǒng)LFS了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。