與大家分享一組文件系統(tǒng)考古文章
開篇將帶大家回到1974年,
從Unix V7 文件系統(tǒng)開始。
有時(shí),進(jìn)步難以察覺(jué),特別是當(dāng)你正身處其中時(shí)。而對(duì)比新舊資料之間的差異,尋找那些推動(dòng)變革的信息源,我們就可以清晰地看到進(jìn)步的發(fā)生。在Linux(以及大部分Unix系統(tǒng))中,都可以印證這一點(diǎn)。
Unix V7 是 Unix 操作系統(tǒng)的一個(gè)重要的早期版本,于 1979 年發(fā)布,是貝爾實(shí)驗(yàn)室最后一個(gè)廣泛分發(fā)的版本。它是第一個(gè)真正可移植的 Unix 版本,被移植到了多種平臺(tái)上,包括 DEC PDP-11, VAX, x86, Motorola 68000 等。Unix V7 的 VAX 移植版本,叫做 UNIX/32V,是流行的 4BSD 系列 Unix 系統(tǒng)的直接祖先。許多老牌的 Unix 用戶認(rèn)為 Unix V7 是 Unix 發(fā)展的頂峰。
Unix V7 Research Release 的源代碼可以在 unix-history-repo^[3]^ 這個(gè)由 Diomidis Spinellis 維護(hù)的項(xiàng)目中找到。如果你想深入了解 Unix 的設(shè)計(jì)原理,可以參考 Maurice J. Bach 的經(jīng)典著作 The Design of the Unix Operating System^[4]^,并查看 Research V7 Snapshot^[5]^ 這個(gè)分支的代碼庫(kù)。
Ken Thompson (坐著的) 和 Dennis Ritchie 在小型計(jì)算機(jī) PDP-11 上工作,他們是貝爾實(shí)驗(yàn)室(Bell Labs)的研究員,在20世紀(jì)70年代早期開發(fā)了Unix操作系統(tǒng)及其文件系統(tǒng)。
Machines
1974 年,計(jì)算機(jī)擁有一個(gè)“核心”,即中央處理單元。然而,在某些計(jì)算機(jī)中,這個(gè)“核心”已經(jīng)發(fā)生了變化。不再是由多個(gè)部件(如算術(shù)邏輯單元、寄存器、順序控制器和微碼存儲(chǔ)器)組成的設(shè)備,而是一顆單一的集成芯片,單個(gè)芯片上集成了數(shù)千個(gè)晶體管。它們被叫做“小型計(jì)算機(jī)”。
Kernels
在 Unix 中,我們通過(guò)配置頭文件(header file)來(lái)處理系統(tǒng)資源。如下圖所示,這里顯示了頭文件中配置的默認(rèn)值^[6]^,數(shù)據(jù)結(jié)構(gòu)是數(shù)組,所示值是相應(yīng)的數(shù)組大小。如果要更改它們,則需要編輯文件,重新編譯和鏈接內(nèi)核,然后重新啟動(dòng)系統(tǒng)。
它有一個(gè)文件系統(tǒng)緩沖區(qū)緩存(file system buffer cache),使用 NBUF(29)個(gè)磁盤塊,每個(gè)磁盤塊的大小是 512 字節(jié),用來(lái)暫時(shí)存儲(chǔ)磁盤上的數(shù)據(jù)塊和 inode,從而加速文件系統(tǒng)訪問(wèn)。另外還有一個(gè)索引節(jié)點(diǎn)數(shù)組(inode array),它有 NINODE (200)個(gè)條目,每個(gè)條目對(duì)應(yīng)一個(gè)文件的元數(shù)據(jù),還可以同時(shí)掛載 NMOUNT (8)個(gè)文件系統(tǒng)。每個(gè)用戶最多可以運(yùn)行MAXUPRC(25)個(gè)進(jìn)程,總共有 NPROC(150)個(gè)系統(tǒng)進(jìn)程。每個(gè)進(jìn)程最多可以打開 NOFILE(20)個(gè)文件。
閱讀 Bach 的著作和 V7 源代碼是很有趣的,盡管它們已經(jīng)完全過(guò)時(shí)。因?yàn)檫@些源代碼中呈現(xiàn)出的許多核心概念更加清晰,結(jié)構(gòu)更簡(jiǎn)潔,有時(shí)甚至帶有古老的風(fēng)格。然而,正是這些概念定義了 Unix 文件系統(tǒng)。V7 Unix 被寫入了 POSIX 標(biāo)準(zhǔn),之后的每個(gè)文件系統(tǒng)都必須遵守它。如果您想了解更多相關(guān)示例,請(qǐng)參考 But Is It Atomic?^[8]^
核心概念
Unix 文件系統(tǒng)的基本概念和結(jié)構(gòu)來(lái)自這個(gè)系統(tǒng)。其中一些概念甚在現(xiàn)代系統(tǒng)中依然存在。
磁盤由一系列數(shù)據(jù)塊(block)組成,從第 0 塊開始,一直到第 n 塊結(jié)束。在文件系統(tǒng)的開始部分,我們可以找到超級(jí)塊(superblock)。它位于文件系統(tǒng)的第 1 塊。超級(jí)塊存儲(chǔ)了文件系統(tǒng)的一些基本信息,比如文件系統(tǒng)的大小、空閑塊的數(shù)量、空閑索引節(jié)點(diǎn)的數(shù)量等。當(dāng)我們執(zhí)行掛載(mount)系統(tǒng)調(diào)用時(shí),系統(tǒng)會(huì)找到一個(gè)空閑的掛載結(jié)構(gòu)(mount structure^[8]^),并且從磁盤上讀取超級(jí)塊,把它作為掛載結(jié)構(gòu)的一部分。
Inode
內(nèi)存中的超級(jí)塊(in-memory superblock)是磁盤上超級(jí)塊的副本,用于加快文件系統(tǒng)的訪問(wèn)速度。它包含一個(gè) short 類型的字段,用于存儲(chǔ)一個(gè)索引節(jié)點(diǎn)數(shù)組(inode array)在磁盤上的位置。
索引節(jié)點(diǎn)(inode^[9]^)是一個(gè)描述文件內(nèi)容和屬性的結(jié)構(gòu),文件內(nèi)容由一系列數(shù)據(jù)塊(block)組成,每個(gè)數(shù)據(jù)塊的大小是固定的(通常是 512 字節(jié)或 1024 字節(jié)),文件屬性包含文件名、大小、權(quán)限、時(shí)間戳等元數(shù)據(jù)(metadata)。
磁盤上的 inode 如上圖所示。每個(gè) 512 字節(jié)的磁盤塊可以容納 8 個(gè) inode,因此它們?cè)?64 字節(jié)邊界上對(duì)齊。
文件系統(tǒng)中的 inode 數(shù)組是一個(gè) short 類型的計(jì)數(shù)器,它的最大值是 65535,也就是說(shuō)文件系統(tǒng)中最多只能有 65535 個(gè) inode。由于每個(gè)文件都需要一個(gè) inode,因此每個(gè)文件系統(tǒng)最多只能容納 65535 個(gè)文件。
每個(gè)文件具有一些固定屬性:
(2字節(jié))mode,它包含了文件的類型和訪問(wèn)權(quán)限;
(2字節(jié))nlink,它表示這個(gè)文件有多少個(gè)名字;
(2字節(jié))uid,文件的所有者;
(2字節(jié))gid,文件所有者的組 ID;
(4字節(jié))size,文件的長(zhǎng)度,以字節(jié)為單位(定義為 off_t,長(zhǎng)整型);
(40字節(jié))addr 數(shù)組,包含了文件的數(shù)據(jù)塊在磁盤上的地址;
(3x 4字節(jié))三個(gè)時(shí)間,atime(訪問(wèn)時(shí)間),mtime(修改時(shí)間)和 ctime(所謂的創(chuàng)建時(shí)間,但實(shí)際上是最后一個(gè) inode 更改的時(shí)間)。
總大小為 64 字節(jié)。
bmap()
Addr 數(shù)組包含 40 個(gè)字節(jié),但它存儲(chǔ)了 13 個(gè)磁盤塊地址,每個(gè)地址使用 3 個(gè)字節(jié)。這對(duì)于 24 位來(lái)說(shuō)非常適用,或者說(shuō)對(duì)應(yīng)于 16 個(gè)大小為 512 字節(jié)的兆塊,總文件系統(tǒng)大小為 8M 千字節(jié),即 8GB。
小型計(jì)算機(jī) PDP-11 RL02磁盤驅(qū)動(dòng)器的前面板 (來(lái)自 pdp-11.nl [10])
PDP-11 RL02K磁盤盒^[11]^可容納 10.4 MB,而更新的 RA92^[12]^ 可存儲(chǔ) 1.5 GB。
Addr 數(shù)組在 bmap()^[13]^ 函數(shù)中被使用。該函數(shù)接收一個(gè) inode(ip)和一個(gè)邏輯塊號(hào) bn,并返回一個(gè)物理塊號(hào)。也就是說(shuō),它將文件中的一個(gè)塊映射到磁盤上的一個(gè)塊,因此得名。
前 10 個(gè)塊指針直接存儲(chǔ)在 inode 中。例如,要訪問(wèn)塊 0,bmap() 將在 inode 中查找^[14]^ di_addr[0] 并返回該塊號(hào)。
額外的塊存儲(chǔ)在一個(gè)間接塊中,而間接塊則存儲(chǔ)在 inode 中。對(duì)于更大的文件,會(huì)分配一個(gè)雙間接塊,并指向更多的間接塊,最終非常大的文件需要甚至三次間接塊。
代碼首先確定需要多少層間接尋址^[15]^,也就是要通過(guò)多少個(gè)間接塊才能找到文件內(nèi)容的磁盤塊。然后,獲取相應(yīng)的間接塊^[16]^。最后,代碼按照適當(dāng)?shù)拇螖?shù)解析間接尋址^[17]^,也就是根據(jù)層數(shù)依次從間接塊中讀取其他間接塊或直接塊的地址,直到找到文件內(nèi)容的磁盤塊。
對(duì)于越來(lái)越大的文件,原始的 Unix 文件結(jié)構(gòu)采用了逐漸增加的間接訪問(wèn)次數(shù)。這樣形成了一個(gè)壓縮的數(shù)組,其中較短的文件可以直接通過(guò) inode 中的數(shù)據(jù)進(jìn)行訪問(wèn),而較大的文件則需要通過(guò)越來(lái)越多的間接訪問(wèn)來(lái)獲取數(shù)據(jù)。為了提高性能,保持間接塊在文件系統(tǒng)緩沖區(qū)高速緩存中是至關(guān)重要的。
這種擴(kuò)展性取決于塊大小(早期為 512 字節(jié),現(xiàn)在為 4096 字節(jié))和塊號(hào)的字節(jié)大小(最初為 3 字節(jié),后來(lái)為 4 字節(jié)甚至 8 字節(jié))。
Atomic writes
文件的寫入是在加鎖的狀態(tài)下進(jìn)行的,因此它們始終具有原子性。即使是跨越多個(gè)數(shù)據(jù)塊的寫入操作,也是如此。這一點(diǎn)在 But Is It Atomic?^[18]^ 中有詳細(xì)討論。
這也意味著即使有多個(gè)寫入進(jìn)程,在單個(gè)文件上,任何時(shí)刻只能有一個(gè)磁盤寫入操作處于活躍狀態(tài)。這對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的開發(fā)者來(lái)說(shuō)非常不便利。
Naming files
目錄是一個(gè)具有特殊類型和固定記錄結(jié)構(gòu)^[19]^的文件。
一個(gè)目錄條目包含一個(gè)inode號(hào)(一個(gè)無(wú)符號(hào)整數(shù))和一個(gè)文件名,文件名的長(zhǎng)度最多可以達(dá)到14個(gè)字節(jié)。這使得一個(gè)磁盤塊可以容納32個(gè)目錄條目,而一個(gè)目錄文件的直接塊可以引用的10個(gè)磁盤塊可以容納320個(gè)目錄條目。
下層(lower)的文件系統(tǒng)中充滿了大量的文件。這些文件沒(méi)有名稱,只有編號(hào)。
上層 (upper)的文件系統(tǒng)使用一種特殊類型的文件,具有簡(jiǎn)單的16字節(jié)記錄結(jié)構(gòu),用于為文件分配最多14個(gè)字符的名稱。一個(gè)特殊的函數(shù)namei()將文件名轉(zhuǎn)換為inode號(hào)。
傳遞給namei()的路徑名具有層次結(jié)構(gòu):它們可以包含/作為路徑分隔符,并以?(NUL)作為終止符。路徑名若以/開頭,則遍歷將從文件系統(tǒng)的根目錄開始,形成絕對(duì)路徑名;若不以/開頭,則遍歷將從u.u_cdir,即當(dāng)前目錄開始。
該函數(shù)逐個(gè)消耗路徑名的各個(gè)組成部分,使用當(dāng)前活動(dòng)目錄,并在該目錄中線性搜索當(dāng)前組件的名稱。當(dāng)找到最后一個(gè)路徑名組件或在任何階段找不到組件時(shí),該函數(shù)結(jié)束。如果在路徑中的任何目錄的任何點(diǎn)上,我們沒(méi)有 x 權(quán)限^[20]^,它也會(huì)結(jié)束。
該函數(shù)按順序逐個(gè)處理路徑名的各個(gè)組成部分。它使用當(dāng)前目錄,并在該目錄中線性搜索當(dāng)前組成部分的名稱。函數(shù)的結(jié)束條件有兩種情況:一是找到了路徑名的最后一個(gè)組成部分,二是在路徑的任何目錄中,出現(xiàn)了無(wú)法訪問(wèn)^[21]^的情況。
掛載點(diǎn)是特殊條目^[22]^,它會(huì)從當(dāng)前節(jié)點(diǎn)和文件系統(tǒng)的目錄條目切換到掛載文件系統(tǒng)的根inode。這使得Unix中的所有文件系統(tǒng)看起來(lái)像是一棵單一的樹,如果要進(jìn)行"硬盤修改"的操作,只需簡(jiǎn)單地切換到不同的目錄。
最終,該函數(shù)將返回給定路徑名的inode指針,根據(jù)需要和需求創(chuàng)建(或刪除)inode(和目錄條目)。它是目錄遍歷和訪問(wèn)權(quán)限檢查的集中點(diǎn)。
一些創(chuàng)新的想法以及限制
這個(gè)早期的Unix文件系統(tǒng)具有許多很好的特性:
它將多個(gè)文件系統(tǒng)呈現(xiàn)為一個(gè)統(tǒng)一的樹形結(jié)構(gòu);
文件是無(wú)結(jié)構(gòu)的字節(jié)數(shù)組;
這些數(shù)組以可動(dòng)態(tài)增加深度的動(dòng)態(tài)數(shù)組的形式存儲(chǔ)。它們內(nèi)部使用一種逐漸嵌套的間接塊系統(tǒng),其中數(shù)組的元素可以是指向其他數(shù)組或數(shù)據(jù)的指針,從而形成層次嵌套的結(jié)構(gòu)。這使得磁盤搜索的復(fù)雜度為O(1);
下層文件系統(tǒng)創(chuàng)建文件和上層的文件系統(tǒng)組織文件互相隔離,分工明確。獲取inode的唯一方式是路徑名遍歷,并且在此過(guò)程中始終檢查權(quán)限;
文件名中只有很少的特殊字符,即/和?(空字符)。
但也有明顯的限制:
文件只能有16M個(gè)塊;
文件系統(tǒng)只能有非常有限的65535個(gè)inode。
還有一些令人討厭的限制:
文件只能有一個(gè)正在寫入的進(jìn)程,這會(huì)導(dǎo)致并發(fā)性受限;
目錄查找是線性掃描,因此對(duì)于大型目錄(超過(guò)320個(gè)條目),速度變得非常慢;
沒(méi)有強(qiáng)制文件鎖定系統(tǒng)。但存在幾種用于咨詢式文件鎖定的系統(tǒng)。
還有一些特殊情況:
在 Unix V7 系統(tǒng)中,沒(méi)有 delete() 系統(tǒng)調(diào)用,而是 unlink() 系統(tǒng)調(diào)用,它可以刪除一個(gè)文件的名字,并且那些沒(méi)有任何文件名和打開文件句柄的文件會(huì)被自動(dòng)清理。這會(huì)導(dǎo)致一些不符合預(yù)期的結(jié)果,例如,只有當(dāng)一個(gè)完全沒(méi)有文件名的文件被完全關(guān)閉時(shí),它占用的磁盤空間才會(huì)被釋放。許多 Unix 系統(tǒng)管理員都曾經(jīng)問(wèn)過(guò)他們的磁盤空間去哪了,當(dāng)他們刪除了 /var/log 目錄下的日志文件,卻忘記了有一些進(jìn)程還在使用它;
最初沒(méi)有 mkdir() 和 rmdir() 系統(tǒng)調(diào)用,這導(dǎo)致了存在可被利用的競(jìng)態(tài)條件。競(jìng)態(tài)條件是指在多線程或多進(jìn)程環(huán)境中,由于操作的順序和時(shí)機(jī)不確定性,可能導(dǎo)致安全漏洞或錯(cuò)誤行為的情況。這在 Unix 的后續(xù)版本中得到了修復(fù);
有一些操作在特定條件下具有原子性(例如write(2)系統(tǒng)調(diào)用),或者經(jīng)過(guò)修改后具有原子性(mknod(2)和mkdir(2))。
在結(jié)構(gòu)上,inode表和塊和inode的空閑映射位于文件系統(tǒng)的開頭,磁盤空間也是從磁盤的前端線性分配的。這導(dǎo)致了頻繁的尋址操作,并且可能導(dǎo)致文件系統(tǒng)的碎片化(即文件存儲(chǔ)在非相鄰的塊中)。
遍歷目錄結(jié)構(gòu)意味著從磁盤開頭讀取目錄的inode,然后向后移動(dòng)到更遠(yuǎn)的數(shù)據(jù)塊,再?gòu)拇疟P開頭讀取下一個(gè)路徑名組成部分的下一個(gè)inode,并向后移動(dòng)到相應(yīng)的數(shù)據(jù)塊。這個(gè)過(guò)程在每個(gè)路徑名組成部分上來(lái)回進(jìn)行,速度并不快。
改進(jìn)
在之后的發(fā)展中,minix文件系統(tǒng)忠實(shí)繼承了PDP-11 V7 Unix文件系統(tǒng),保留了它的特性包括局限。然而,隨著時(shí)間的推移,在現(xiàn)代的Linux系統(tǒng)中,由于其不再具備實(shí)用性,它已經(jīng)從內(nèi)核源代碼中移除。
在稍后的一篇文章中,我們將會(huì)了解到關(guān)于BSD快速文件系統(tǒng),如何更好地布局磁盤上的數(shù)據(jù),如何實(shí)現(xiàn)更長(zhǎng)的文件名、更多的inode,以及如何通過(guò)考慮磁盤的物理特性來(lái)加快速度。
要解決目錄查找時(shí)間線性增長(zhǎng)、單個(gè)寫入者或有限的文件元數(shù)據(jù)這些問(wèn)題需要更新的文件系統(tǒng)。
審核編輯:湯梓紅
評(píng)論