操作系統(tǒng)導(dǎo)論-持久化
36.1系統(tǒng)架構(gòu)
從下到上性能越來越高，成本越來越高，支持連接的設(shè)備數(shù)量越來越少。
36.2標(biāo)準(zhǔn)設(shè)備
一個(gè)標(biāo)準(zhǔn)設(shè)備包含兩部分：
硬件接口：供系統(tǒng)軟件控制它的操作，所有設(shè)備都有自己的特定接口以及典型交互協(xié)議。
內(nèi)部結(jié)構(gòu)：設(shè)備相關(guān)功能的特定實(shí)現(xiàn)，負(fù)責(zé)具體實(shí)現(xiàn)設(shè)備展示給系統(tǒng)的抽象接口。
狀態(tài)寄存器：讀取設(shè)備當(dāng)前狀態(tài)；命令寄存器：通知設(shè)備執(zhí)行具體任務(wù)；數(shù)據(jù)寄存器：將數(shù)據(jù)傳給設(shè)備/從設(shè)備接收數(shù)據(jù)。
協(xié)議：操作系統(tǒng)如何與設(shè)備進(jìn)行交互
36.4利用中斷減少CPU開銷
如果設(shè)備非?？?>輪詢;如果設(shè)備比較慢->中斷。
設(shè)備的速度未知使用混合（hybrid）策略，先嘗試輪詢一小段時(shí)間，如果設(shè)備沒有完成操作，此時(shí)再使用中斷。這種兩階段（two-phased）的辦法可以實(shí)現(xiàn)兩種方法的好處。
36.5利用DMA進(jìn)行更高效的數(shù)據(jù)傳送
使用 PIO的方式，CPU的時(shí)間會(huì)浪費(fèi)在向設(shè)備傳輸數(shù)據(jù)或從設(shè)備傳出數(shù)據(jù)的過程中。
DMA工作過程如下。OS通過編程告訴DMA引擎數(shù)據(jù)在內(nèi)存的位置，要拷貝的大小以及要拷貝到那個(gè)設(shè)備。此后操作系統(tǒng)可以處理其它請(qǐng)求。當(dāng)DMA的任務(wù)完成后，DMA控制器拋出一個(gè)中斷來告訴OS已經(jīng)完成數(shù)據(jù)傳輸。
36.6設(shè)備交互的方法
硬件如何與設(shè)備通信?
特權(quán)指令：采用明確的I/O指令，這些指令規(guī)定了操作系統(tǒng)將數(shù)據(jù)送到特定設(shè)備寄存器的方法。
內(nèi)存映射I/O：硬件將設(shè)備寄存器作為內(nèi)存地址提供。當(dāng)需要訪問設(shè)備寄存器時(shí)，操作系統(tǒng)裝載(讀取)或者存入(寫入)到該內(nèi)存地址；如何硬件會(huì)將裝載/存入轉(zhuǎn)移到設(shè)備上，而不是物理內(nèi)存。
特權(quán)指令中的特權(quán)指OS是唯一可以直接與設(shè)備交互的實(shí)體。
內(nèi)存映射I/O的好處是不需要引入新指令來實(shí)現(xiàn)設(shè)備交互。
36.7納入OS：設(shè)備驅(qū)動(dòng)程序
每個(gè)設(shè)備都有非常具體的接口，如何將它們納入操作系統(tǒng)，我們希望操作系統(tǒng)盡可能通用。
關(guān)鍵問題：如何實(shí)現(xiàn)一個(gè)設(shè)備無關(guān)的操作系統(tǒng) ？
如何保持操作系統(tǒng)的大部分與設(shè)備無關(guān)，從而對(duì)操作系統(tǒng)的主要子系統(tǒng)隱藏設(shè)備交互的細(xì)節(jié)？ 通過抽象進(jìn)行解決。
在最底層，操作系統(tǒng)的一部分軟件清楚地知道設(shè)備如何工作，我們將這部分軟件稱為設(shè)備驅(qū)動(dòng)程序（device driver），所有設(shè)備交互的細(xì)節(jié)都封裝在其中。
文件系統(tǒng)（當(dāng)然也包括在其之上的應(yīng)用程序）完全不清楚它使用的是什么類型的磁盤。它只需要簡(jiǎn)單地向通用塊設(shè)備層發(fā)送讀寫請(qǐng)求即可，塊設(shè)備層會(huì)將這些請(qǐng)求路由給對(duì)應(yīng)的設(shè)備驅(qū)動(dòng)，然后設(shè)備驅(qū)動(dòng)來完成真正的底層操作。
這種封裝也有不足的地方。例如，如果有一個(gè)設(shè)備可以提供很多特殊的功能，但為了兼容大多數(shù)操作系統(tǒng)它不得不提供一個(gè)通用的接口，這樣就使得自身的特殊功能無法使用。
第37章I/O設(shè)備
關(guān)鍵問題：現(xiàn)代磁盤驅(qū)動(dòng)器如何存儲(chǔ)數(shù)據(jù)？接口是什么？數(shù)據(jù)是如何安排和訪問的？磁盤調(diào)度如何提高性能？
37.1接口
驅(qū)動(dòng)器由大量山區(qū)(512字節(jié)塊)組測(cè)，磁盤可以視為一組扇區(qū)。
許多文件系統(tǒng)一次讀取或?qū)懭?KB(或更多)，驅(qū)動(dòng)器制造商唯一保證的是單個(gè)512字節(jié)的寫入是原子的。
37.2基本幾何形狀
37.3簡(jiǎn)單的磁盤驅(qū)動(dòng)器
磁盤完整的I/O時(shí)間圖：尋道；盤片旋轉(zhuǎn)；數(shù)據(jù)傳輸；
許多驅(qū)動(dòng)器采用某種形式的磁道偏斜（track skew)，以確保即使在跨越磁道邊界時(shí)，順序讀取也可以方便地服務(wù)。
扇區(qū)往往會(huì)偏移因?yàn)閺囊粋€(gè)磁道切換到另一個(gè)磁道時(shí)，磁盤需要時(shí)間來重新定位磁頭（即便移到相鄰磁道）。如果沒有這種偏斜，磁頭將移動(dòng)到下一個(gè)磁道，但所需的下一個(gè)塊已經(jīng)旋轉(zhuǎn)到磁頭下，因此驅(qū)動(dòng)器將不得不等待整個(gè)旋轉(zhuǎn)延遲，才能訪問下一個(gè)塊。
后寫：寫入磁盤緩存后，回報(bào)寫入完成。
直寫：實(shí)際寫入磁盤后，回報(bào)寫入完成。
后寫緩存有時(shí)會(huì)使驅(qū)動(dòng)器看起來"更快"，但可能有危險(xiǎn)。
37.4I/O時(shí)間
第38章廉價(jià)冗余磁盤陣列RAID
關(guān)鍵問題：我們?nèi)绾螛?gòu)建一個(gè)大型、快速和可靠的存儲(chǔ)系統(tǒng)？關(guān)鍵技術(shù)是什么？不同方法之間的折中是什么？
RAID使用多個(gè)磁盤一起構(gòu)建更快、更大、更可靠的磁盤系統(tǒng)。
從外部看，RAID看起來像一個(gè)磁盤：一組可以讀取或?qū)懭氲膲K。
在內(nèi)部，RAID由多個(gè)磁盤、內(nèi)存（包括易失性和非易失性）以及一個(gè)或多個(gè)處理器來管理系統(tǒng)。
RAID的優(yōu)點(diǎn)：
性能：并行使用多個(gè)磁盤可以大大加快 I/O時(shí)間。
容量：大型數(shù)據(jù)集需要大型磁盤。
可靠性：通過某種形式的冗余（redundancy），RAID可以容許損失一個(gè)磁盤并保持運(yùn)行，就像沒有錯(cuò)誤一樣。
透明性：RAID對(duì)于主機(jī)系統(tǒng)看起來就像一個(gè)大磁盤。
38.1接口和RAID內(nèi)部
當(dāng)文件系統(tǒng)向 RAID發(fā)出邏輯 I/O請(qǐng)求時(shí)，RAID內(nèi)部必須計(jì)算要訪問的磁盤（或多個(gè)磁盤）以完成請(qǐng)求，然后發(fā)出一個(gè)或多個(gè)物理 I/O來執(zhí)行此操作。
在很高的層面上來看，RAID是一個(gè)非常專業(yè)的計(jì)算機(jī)系統(tǒng)：它有一個(gè)處理器，內(nèi)存和磁盤。然而，它不是運(yùn)行應(yīng)用程序，而是運(yùn)行專門用于操作 RAID的軟件。
38.2故障模型
RAID旨在檢測(cè)并從某些類型的磁盤故障中恢復(fù)。
38.3如何評(píng)估RAID
性能；可靠性；容量；
我們現(xiàn)在考慮 3個(gè)重要的 RAID設(shè)計(jì)：RAID 0級(jí)（條帶化），RAID 1級(jí)（鏡像）和 RAID 4/5級(jí)（基于奇偶校驗(yàn)的冗余）
38.4RAID0級(jí)：條帶化
沒有冗余，但可作為性能和容量的上限。
RAID陣列的大塊大小(chunk size)為4KB
RAID陣列的大塊大小(chunk size)為8KB
RAID映射問題
給定一個(gè)邏輯塊來讀或?qū)?，RAID如何確切地知道要訪問哪個(gè)物理磁盤和偏移量？
對(duì)于塊大小為8KB的情況：磁盤= A % 磁盤數(shù) ；偏移量 = A / 磁盤數(shù) ；
大塊大小的tradeoff
chunk size較小的情況：文件將跨多個(gè)磁盤進(jìn)行條帶化，從而增加了對(duì)單個(gè)文件的讀取和寫入的并行性。但是，跨多個(gè)磁盤訪問塊的定位時(shí)間會(huì)增加，因?yàn)檎麄€(gè)請(qǐng)求的定位時(shí)間由所有驅(qū)動(dòng)器上請(qǐng)求的最大定位時(shí)間決定。
chunk size較大的情況：較大的大塊大小減少了這種文件內(nèi)的并行性，因此依靠多個(gè)并發(fā)請(qǐng)求來實(shí)現(xiàn)高吞吐量。但是，較大的大塊大小減少了定位時(shí)間。
大多數(shù)RAID采用64KB大小的chunk
評(píng)估RAID的性能：考慮兩種性能指標(biāo)
單請(qǐng)求延遲：它可以揭示單個(gè)邏輯 I/O操作期間可以存在多少并行性。
RAID穩(wěn)態(tài)吞吐量：即許多并發(fā)請(qǐng)求的總帶寬。
單塊請(qǐng)求的延遲與單個(gè)磁盤的延遲幾乎相同；
穩(wěn)態(tài)吞吐量對(duì)于順序IO=N(磁盤數(shù)量)×S(單個(gè)磁盤的順序帶寬)；隨機(jī)IO=N×R(單個(gè)磁盤的隨機(jī)帶寬)
38.5RAID1級(jí)：鏡像
RAID1(鏡像):需生成系統(tǒng)中每個(gè)塊的多個(gè)副本。每個(gè)副本應(yīng)該放在一個(gè)單獨(dú)的磁盤上。這樣，我們可以容許磁盤故障。
假設(shè)對(duì)于每個(gè)邏輯塊，RAID保留兩個(gè)物理副本。
讀取可以選擇一個(gè)進(jìn)行讀取，寫入可以并行進(jìn)行。
RAID-1分析
容量在鏡像級(jí)別=2時(shí)，容量=N/2；從可靠性角度，表現(xiàn)良好。
性能：
單請(qǐng)求延遲：讀取與單個(gè)磁盤上的延遲相同。寫入時(shí)間大致等于單次寫入時(shí)間，平均而言比寫入單個(gè)磁盤略高。
穩(wěn)態(tài)吞吐量：順序?qū)懭隢/2×S；順序讀N/2×S；隨機(jī)讀N×R；隨機(jī)寫N/2×R；
38.6RAID4級(jí)：通過奇偶校驗(yàn)節(jié)省空間
向磁盤陣列添加冗余(奇偶校驗(yàn))，基于奇偶校驗(yàn)的方法試圖使用較少的容量，從而克服由鏡像系統(tǒng)付出的巨大空間損失。不過，這樣做的代價(jià)是——性能。
奇偶校驗(yàn)=異或函數(shù)，如果有奇數(shù)個(gè)1，則返回1，否則返回0；
利用奇偶校驗(yàn)從故障中恢復(fù)：將數(shù)據(jù)位和奇偶校驗(yàn)位異或。
對(duì)于block，將block上的每一位按位執(zhí)行XOR操作，將結(jié)果放入奇偶校驗(yàn)塊的相應(yīng)位置中。
RAID-4分析
容量：RAID-4使用 1個(gè)磁盤作為它所保護(hù)的每組磁盤的奇偶校驗(yàn)信息。因此，RAID組的有用容量是（N?1）。
可靠性：RAID-4容許 1個(gè)磁盤故障，不容許更多。如果丟失多個(gè)磁盤， 則無法重建丟失的數(shù)據(jù)。
性能：連續(xù)讀取性能可以利用除奇偶校驗(yàn)磁盤以外的所有磁盤，因此可提供（N?1）×S（簡(jiǎn)單情況）的峰值有效帶寬。
將大塊數(shù)據(jù)寫入磁盤時(shí)，RAID-4可以執(zhí)行一種簡(jiǎn)單優(yōu)化，稱為全條帶寫入（full-stripe write）。在這種情況下，RAID可以簡(jiǎn)單地計(jì)算 P0的新值（通過在塊 0、12和 3上執(zhí)行 XOR），然后將所有塊（包括奇偶?jí)K）并行寫入上面的 5個(gè)磁盤。因此，全條帶寫入是 RAID-4寫入磁盤的最有效方式。
順序?qū)懭氲男阅埽河行?N-1)×S；隨機(jī)讀性能：(N-1)×R；
隨機(jī)寫入：隨機(jī)寫的復(fù)寫，會(huì)導(dǎo)致奇偶校驗(yàn)塊 P0將不再準(zhǔn)確地反映條帶的正確奇偶校驗(yàn)值。P0也必須更新。
加法奇偶校驗(yàn)：并行讀取條帶中所有其他數(shù)據(jù)塊并與新塊進(jìn)行異或。生成新的校驗(yàn)塊。接下來將新數(shù)據(jù)和新奇偶校驗(yàn)并行寫入其各自的磁盤。(需要讀取其它磁盤來計(jì)算奇偶校驗(yàn))。
減法奇偶校驗(yàn)：
使用減法奇偶校驗(yàn)，每次隨機(jī)寫入RAID必須執(zhí)行4次物理I/O(兩次讀和兩次寫入)。
現(xiàn)幾乎同時(shí)向 RAID-4提交 2個(gè)小的請(qǐng)求，這些數(shù)據(jù)位于磁盤 0和 1上，因此對(duì)數(shù)據(jù)的讀寫操作可以并行進(jìn)行，出現(xiàn)的問題是奇偶校驗(yàn)磁盤。這兩個(gè)請(qǐng)求都必須讀取 4和 13的奇偶校驗(yàn)塊，即奇偶校驗(yàn)塊1和 3。
在這種類型的工作負(fù)載下，奇偶校驗(yàn)磁盤是瓶頸。我們有時(shí)將它稱為基于奇偶校驗(yàn)的 RAID的小寫入問題（small-write problem）。 因此，即使可以并行訪問數(shù)據(jù)磁盤，奇偶校驗(yàn)磁盤也不會(huì)實(shí)現(xiàn)任何并行。
奇偶校驗(yàn)磁盤必須為每個(gè)邏輯 I/O執(zhí)行兩次 I/O（一次讀取，一次寫入），其性能固定為R/2，添加磁盤也無法改善。
單請(qǐng)求延遲：?jiǎn)未螌懭氲难舆t需要兩次讀取，然后兩次寫入。讀操作可以并行進(jìn)行，寫操作也是如此，因此總延遲大約是單個(gè)磁盤的兩倍。
38.7 RAID5級(jí)：旋轉(zhuǎn)奇偶校驗(yàn)
為解決小寫入問題(部分解決)，
順序讀寫性能(N-1)×S;隨機(jī)讀N×R；小寫入總帶寬N×R/4；
38.8RAID比較：總結(jié)
第39章文件和目錄
39.3創(chuàng)建文件
通過open系統(tǒng)調(diào)用完成，調(diào)用open()并傳入O_CREAT標(biāo)志，程序可以創(chuàng)建一個(gè)新文件。O_TRUNC,將其截?cái)酁榱阕止?jié)大小，刪除所有現(xiàn)有內(nèi)容。
open()的一個(gè)重要方面是它的返回值：文件描述符（file descriptor）。
一個(gè)文件描述符就是一種權(quán)限/指向文件類型對(duì)象的指針
39.4讀寫文件
open();read(文件描述符,緩沖區(qū),緩沖區(qū)大小);write(文件描述符,緩沖區(qū),寫入大小);
39.5讀取和寫入，但不按順序
off_t lseek(int fildes, off_t offset, int whence); ?第一個(gè)參數(shù)是熟悉的（一個(gè)文件描述符）。第二個(gè)參數(shù)是偏移量，它將文件偏移量定位到文件中的特定位置。
偏移量決定在文件中讀取或?qū)懭霑r(shí)，下一次讀取或?qū)懭腴_始的位置
第一種是當(dāng)發(fā)生 N個(gè)字節(jié)的讀或?qū)憰r(shí)，N被添加到當(dāng)前偏移。因此，每次讀取或?qū)懭攵紩?huì)隱式更新偏移量。第二種是明確的lseek，它改變了上面指定的偏移量。
39.6用fsync()立即寫入
當(dāng)程序調(diào)用 write()時(shí)，它只是告訴文件系統(tǒng)：請(qǐng)?jiān)趯淼哪硞€(gè)時(shí)刻，將此數(shù)據(jù)寫入持久存儲(chǔ)。出于性能的原因，文件系統(tǒng)會(huì)將這些寫入在內(nèi)存中緩沖（buffer）一 段時(shí)間（例如 5s或 30s）。在稍后的時(shí)間點(diǎn)，寫入將實(shí)際發(fā)送到存儲(chǔ)設(shè)備。從調(diào)用應(yīng)用程序的角度來看，寫入似乎很快完成，并且只有在極少數(shù)情況下（例如，在 write()調(diào)用之后但寫入磁盤之前，機(jī)器崩潰）數(shù)據(jù)會(huì)丟失。
提供給應(yīng)用程序的接口被稱為 fsync(int fd)。當(dāng)進(jìn)程針對(duì)特定文件描述符調(diào)fsync()時(shí)，文件系統(tǒng)通過強(qiáng)制將所有臟（dirty）數(shù)據(jù)（即尚未寫入的）寫入磁盤來響應(yīng)，針對(duì)指定文件描述符引用的文件。一旦所有這些寫入完成，fsync()例程就會(huì)返回。
39.7文件重命名
mv使用了系統(tǒng)調(diào)用 rename(char * old, char * new)，它只需要兩個(gè)參數(shù)：文件的原來名稱（old）和新名稱（new）。
rename()調(diào)用是一個(gè)原子調(diào)用
39.8獲取文件信息
文件系統(tǒng)會(huì)保存關(guān)于它存儲(chǔ)的每個(gè)文件的metadata，可以使用stat();fstat()系統(tǒng)調(diào)用。通常保存在inode結(jié)構(gòu)中。
39.9刪除文件
使用unlink()系統(tǒng)調(diào)用，而不是remove/delete。
39.10創(chuàng)建目錄
永遠(yuǎn)不能直接寫入目錄。因?yàn)槟夸浀母袷奖灰暈槲募到y(tǒng)元數(shù)據(jù)，所以只能間接更新目錄，例如，通過在其中創(chuàng)建文件、目錄或其他對(duì)象類型。
39.11讀取目錄
opendir(),readdir(),closedir()；
目錄只有少量的信息（基本上，只是將名稱映射到 inode號(hào)
39.12刪除目錄
刪除目錄可能會(huì)導(dǎo)致刪除大量的數(shù)據(jù)，因此rmdir()要求該目錄在刪除之前是空的。
39.13硬鏈接
39.14符號(hào)鏈接
第41章局部性和快速文件系統(tǒng)
41.1問題：性能不佳
UNIX文件系統(tǒng)性能很糟糕，主要問題是老 UNIX文件系統(tǒng)將磁盤當(dāng)成隨機(jī)存取內(nèi)存。數(shù)據(jù)遍布各處，而不考慮保存數(shù)據(jù)的介質(zhì)是磁盤的事實(shí)，因此具有實(shí)實(shí)在在的、昂貴的定位成本。例如，文件的數(shù)據(jù)塊通常離其 inode非常遠(yuǎn)，因此每當(dāng)?shù)谝淮巫x取 inode然后讀取文件的數(shù)據(jù)塊。
文件系統(tǒng)會(huì)變得非常碎片化，因?yàn)榭臻e空間沒有得到精心管理?？臻e列表最終會(huì)指向遍布磁盤的一堆塊。
需要磁盤碎片化整理工具，將重新組織磁盤數(shù)據(jù)以連續(xù)放置文件，并為讓空閑空間成為一個(gè)或幾個(gè)連續(xù)的區(qū)域，移動(dòng)數(shù)據(jù)，然后重寫 inode等以反映變化。
41.2FFS：磁盤意識(shí)文件系統(tǒng)
思路是讓文件系統(tǒng)的結(jié)構(gòu)和分配策略具有“磁盤意識(shí)”，從而提高性能。
所有現(xiàn)代文件系統(tǒng)都遵循現(xiàn)有的接口（從而保持與應(yīng)用程序的兼容性），同時(shí)為了性能、可靠性或其他原因，改變其內(nèi)部實(shí)現(xiàn)。
41.3組織結(jié)構(gòu)：柱面組
FFS將磁盤劃分為一些分組，稱為柱面組。
這些分組是 FFS用于改善性能的核心機(jī)制。通過在同一組中放置兩個(gè)文件，F(xiàn)FS可以確保先后訪問兩個(gè)文件不會(huì)導(dǎo)致穿越磁盤的長(zhǎng)時(shí)間尋道。
FFS需要能夠在每個(gè)組中分配文件和目錄。每個(gè)組看起來像這樣
41.4策略：如何分配文件和目錄
相關(guān)的東西放一起（無關(guān)的東西分開放）
目錄的放置：找到分配數(shù)量少的柱面組（因?yàn)槲覀兿Ｍ缃M平衡目錄）和大量的自由 inode（因?yàn)槲覀兿ＭS后能夠分配一堆文件），并將目錄數(shù)據(jù)和 inode放在該分組中。當(dāng)然，這里可以使用其他推斷方法（例如，考慮空閑數(shù)據(jù)塊的數(shù)量）。
文件的放置：首先將文件的數(shù)據(jù)塊分配到與其inode相同的組中，從而防止 inode和數(shù)據(jù)之間的長(zhǎng)時(shí)間尋道。其次，它將位于同一目錄中的所有文件，放在它們所在目錄的柱面組中。
41.5測(cè)量文件的局部性
路徑差異值：為了找到兩個(gè)文件的共同祖先，必須在目錄樹上走多遠(yuǎn)。它們?cè)跇渖显娇拷?，度量值越低?/p>
可以看到大約 7%的文件訪問是先前打開的文件，并且近 40%的文件訪問是相同的文件或同一目錄中的文件（即 0或 1的差異值）。因此，F(xiàn)FS的局部性假設(shè)似乎有意義（至少對(duì)于這些跟蹤）。
41.6大文件例外
如果沒有不同的規(guī)則，大文件將填滿它首先放入的塊組（也可能填滿其他組）。以這種方式填充塊組是不符合需要的，因?yàn)樗恋K了隨后的“相關(guān)”文件放置在該塊組內(nèi)，因此可能破壞文件訪問的局部性。
對(duì)于大文件，F(xiàn)FS執(zhí)行以下操作。在將一定數(shù)量的塊分配到第一個(gè)塊組之后，F(xiàn)FS將文件的下一個(gè)“大”塊（即第一個(gè)間接塊指向的那些部分）放在另一個(gè)塊組中（可能因?yàn)樗睦寐实投x擇）。
FFS采用了一種簡(jiǎn)單的方法，基于 inode本身的結(jié)構(gòu)。前 12個(gè)直接塊與 inode放在同一組中。每個(gè)后續(xù)的間接塊，以及它指向的所有塊都放在不同的組中。如果塊大小為 4KB，磁盤地址是 32位，則此策略意味著文件的每 1024個(gè)塊（4MB）放在單獨(dú)的組中，唯一的例外是直接指針?biāo)赶虻奈募那?48KB。
為了攤銷成本，必須在尋道之間傳輸更多數(shù)據(jù)。
41.7關(guān)于FFS的其它幾件事
容納小文件可能會(huì)導(dǎo)致磁盤浪費(fèi)，當(dāng)時(shí)許多文件大小為2KB左右，塊大小4KB。
為此引入了子塊，子塊大小為512Byte，文件系統(tǒng)可以將子塊分配給文件。直到其達(dá)到完整的4KB數(shù)據(jù)。此時(shí)FFS找到應(yīng)該4KB塊，將其復(fù)制到其中，并釋放子塊以備將來使用。
這個(gè)過程效率低下，F(xiàn)FS通過修改libc庫來避免這種異常行為，將緩沖寫入，然后以4KB塊的形式將它們發(fā)送到文件系統(tǒng)。
第二個(gè)巧妙方法是針對(duì)性能進(jìn)行優(yōu)化的磁盤布局。
FFS首先發(fā)出一個(gè)請(qǐng)求，讀取塊 0。當(dāng)讀取完成時(shí)，F(xiàn)FS向塊 1發(fā)出讀取，為時(shí)已晚：塊 1已在磁頭下方旋轉(zhuǎn)，現(xiàn)在對(duì)塊 1的讀取將導(dǎo)致完全旋轉(zhuǎn)。
在下一塊經(jīng)過磁頭之前，F(xiàn)FS有足夠的時(shí)間發(fā)出請(qǐng)求。實(shí)際上，F(xiàn)FS足夠聰明，能夠確定特定磁盤在布局時(shí)應(yīng)跳過多少塊，以避免額外的旋轉(zhuǎn)。這種技術(shù)稱為參數(shù)化。
現(xiàn)代磁盤在內(nèi)部讀取整個(gè)磁道并將其緩沖在內(nèi)部磁盤緩存中。
FFS是允許長(zhǎng)文件名的第一個(gè)文件系統(tǒng)之一，符號(hào)鏈接，原子rename()操作。
第42章崩潰一致性：FSCK和日志
系統(tǒng)可能在任何兩次寫入之間崩潰或斷電，因此磁盤上狀態(tài)可能僅部分地更新。崩潰后，系統(tǒng)啟動(dòng)并希望再次掛載文件系統(tǒng)（以便訪問文件等）。鑒于崩潰可能發(fā)生在任意時(shí)間點(diǎn)，如何確保文件系統(tǒng)將磁盤上的映像保持在合理的狀態(tài)？
FSCK，文件系統(tǒng)檢查程序；預(yù)寫日志journaling;
42.2FSCK文件系統(tǒng)檢查程序
讓不一致的事情發(fā)生，然后重啟時(shí)查找這些不一致并修復(fù)它們。
這種方法無法解決所有問題，文件系統(tǒng)看起來是一致的，但是inode指向垃圾數(shù)據(jù)。
FSCK的基本總結(jié)。
超級(jí)塊：fsck首先檢查超級(jí)塊是否合理，主要是進(jìn)行健全性檢查，例如確保文件系統(tǒng)大小大于分配的塊數(shù)。通常，這些健全性檢查的目的是找到一個(gè)可疑的（沖突的）超級(jí)塊。在這種情況下，系統(tǒng)（或管理員）可以決定使用超級(jí)塊的備用副本。
空閑塊：fsck掃描 inode、間接塊、雙重間接塊等，以了解當(dāng)前在文件系統(tǒng)中分配的塊。它利用這些知識(shí)生成正確版本的分配位圖。因此，如果位圖和inode之間存在任何不一致，則通過信任 inode內(nèi)的信息來解決它。對(duì)所有 inode執(zhí)行相同類型的檢查，確保所有看起來像在用的 inode，都在 inode位圖中有標(biāo)記。
inode狀態(tài)：檢查每個(gè) inode是否存在損壞或其他問題。例如，fsck確保每個(gè)分配的 inode具有有效的類型字段（即常規(guī)文件、目錄、符號(hào)鏈接等）。如果 inode字段存在問題，不易修復(fù)，則 inode被認(rèn)為是可疑的，并被 fsck清除，inode位圖相應(yīng)地更新。
inode鏈接：fsck還會(huì)驗(yàn)證每個(gè)已分配的 inode的鏈接數(shù)。你可能還記得，鏈接計(jì)數(shù)表示包含此特定文件的引用（即鏈接）的不同目錄的數(shù)量。為了驗(yàn)證鏈接計(jì)數(shù)，fsck從根目錄開始掃描整個(gè)目錄樹，并為文件系統(tǒng)中的每個(gè)文件和目錄構(gòu)建自己的鏈接計(jì)數(shù)。如果新計(jì)算的計(jì)數(shù)與 inode中找到的計(jì)數(shù)不匹配，則必須采取糾正措施，通常是修復(fù) inode中的計(jì)數(shù)。如果發(fā)現(xiàn)已分配的 inode但沒有目錄引用它，則會(huì)將其移動(dòng)到 lost + found目錄。
重復(fù)：fsck還檢查重復(fù)指針，即兩個(gè)不同的 inode引用同一個(gè)塊的情況。如果一個(gè) inode明顯不好，可能會(huì)被清除?；蛘?，可以復(fù)制指向的塊，從而根據(jù)需要為每個(gè) inode提供其自己的副本。
壞塊：在掃描所有指針列表時(shí)，還會(huì)檢查壞塊指針。如果指針顯然指向超出其有 效范圍的某個(gè)指針，則該指針被認(rèn)為是“壞的”，例如，它的地址指向大于分區(qū)大小的塊。在這種情況下，fsck不能做任何太聰明的事情。它只是從 inode或間接塊中刪除（清除）該指針。
目錄檢查：fsck不了解用戶文件的內(nèi)容。但是，目錄包含由文件系統(tǒng)本身創(chuàng)建的特定格式的信息。因此，fsck對(duì)每個(gè)目錄的內(nèi)容執(zhí)行額外的完整性檢查，確保“.”和“..”是前面的條目，目錄條目中引用的每個(gè) inode都已分配，并確保整個(gè)層次結(jié)構(gòu)中沒有目錄的引用超過一次。
根本問題：太慢了。
42.3日志(預(yù)寫日志)
將更新的內(nèi)容，先寫入磁盤的一個(gè)指定區(qū)域(日志).
帶有日志的ext3文件系統(tǒng)如下
數(shù)據(jù)日志
中間的 3個(gè)塊只包含塊本身的確切內(nèi)容，這被稱為物理日志（physical logging）。
在日志中放置更緊湊的更新邏輯，邏輯日志，
一旦這個(gè)事務(wù)安全地存在于磁盤上，我們就可以覆寫文件系統(tǒng)中的舊結(jié)構(gòu)了。這個(gè)過程稱為加檢查點(diǎn)（checkpointing）。如果寫入成功完成，說明成功的加上了檢查點(diǎn)。
在寫入日志期間發(fā)生崩潰，當(dāng)一次發(fā)出5個(gè)塊的寫入。
簡(jiǎn)單的方法是一次發(fā)出一個(gè)，等待每個(gè)完成再發(fā)出下一個(gè)。
通過寫入屏障(wirte barrier)，當(dāng)它完成時(shí)，能確保在屏障之前發(fā)出的寫入，先于在屏障之后發(fā)出的寫入到達(dá)磁盤。
可能會(huì)將垃圾快？？的內(nèi)容復(fù)制導(dǎo)DB應(yīng)該存在的位置上。
寫入日志，必須先寫出事務(wù)開始?jí)K和內(nèi)容，這些寫入完成后，文件系統(tǒng)才能將事務(wù)結(jié)束塊發(fā)送到磁盤。磁盤會(huì)產(chǎn)生額外的旋轉(zhuǎn)，對(duì)性能影響很明顯。
為了避免一次發(fā)出5個(gè)塊寫入的問題，文件系統(tǒng)分兩步發(fā)出事務(wù)寫入。
日志寫入；日志提交；加檢查點(diǎn)；
恢復(fù)：如果崩潰發(fā)送在事務(wù)被安全地寫入日志前，只需簡(jiǎn)單地跳過待執(zhí)行的更新。
如果事務(wù)已提交到日志之后但在加檢查點(diǎn)完成之前發(fā)生崩潰，文件系統(tǒng)恢復(fù)過程將掃描日志，并查找已提交到磁盤的事務(wù)。然后，這些事務(wù)被重放（replayed，按順序），文件系統(tǒng)再次嘗試將事務(wù)中的塊寫入它們最終的磁盤位置。
批處理日志
基本協(xié)議可能會(huì)增加大量額外的磁盤流量。
在同一目錄中連續(xù)創(chuàng)建兩個(gè)文件，稱為 file1和 file2。要?jiǎng)?chuàng)建一個(gè)文件，必須更新許多磁盤上的結(jié)構(gòu)，它們需要一遍又一遍的寫入相同的塊。
一些文件系統(tǒng)不會(huì)一次一個(gè)地向磁盤提交每個(gè)更新（例如，Linux ext3）。通過將所有更新緩沖到全局事務(wù)中。
文件系統(tǒng)只將內(nèi)存中的 inode位圖、文件的 inode、目錄數(shù)據(jù)和目錄 inode標(biāo)記為臟，并將它們添加到塊列表中，形成當(dāng)前的事務(wù)。當(dāng)最后應(yīng)該將這些塊寫入磁盤時(shí)（例如，在超時(shí) 5s之后），會(huì)提交包含上述所有更新的單個(gè)全局事務(wù)。因此，通過緩沖更新，文件系統(tǒng)在許多情況下可以避免對(duì)磁盤的過多的寫入流量。
使日志有限
日志滿會(huì)導(dǎo)致兩個(gè)問題：日志越大恢復(fù)時(shí)間越長(zhǎng)，日志已滿時(shí)不能向磁盤提交進(jìn)一步的事務(wù)。采用循環(huán)數(shù)據(jù)結(jié)構(gòu)。
元數(shù)據(jù)日志
對(duì)于每次寫入磁盤，我們現(xiàn)在也要先寫入日志，從而使寫入流量加倍。
有序日志/元數(shù)據(jù)日志，用戶數(shù)據(jù)不需寫入日志，直接寫入文件系統(tǒng)。
在將相關(guān)元數(shù)據(jù)寫入磁盤日志前，先將數(shù)據(jù)塊寫入磁盤。
通過強(qiáng)制先寫入數(shù)據(jù)，文件系統(tǒng)可以保證指針永遠(yuǎn)不會(huì)指向垃圾。這個(gè)“先寫入被指對(duì)象，再寫入指針對(duì)象”的規(guī)則是崩潰一致性的核心，
發(fā)出寫入日志之前強(qiáng)制數(shù)據(jù)寫入完成不是正確性所必需的。真正的要求是發(fā)出日志提交快之前完成數(shù)據(jù)寫入和日志元數(shù)據(jù)寫入。
42.4其它方法
軟更新：軟更新[GP94]的方法。這種方法仔細(xì)地對(duì)文件系統(tǒng)的所有寫入排序，以確保磁盤上的結(jié)構(gòu)永遠(yuǎn)不會(huì)處于不一致的狀態(tài)。例如，通過先寫入指向的數(shù)據(jù)塊，再寫入指向它的inode，可以確保 inode永遠(yuǎn)不會(huì)指向垃圾。
寫時(shí)復(fù)制：這種技術(shù)永遠(yuǎn)不會(huì)覆寫文件或目錄。相反，它會(huì)對(duì)磁盤上以前未使用 的位置進(jìn)行新的更新。在完成許多更新后，COW文件系統(tǒng)會(huì)翻轉(zhuǎn)文件系統(tǒng)的根結(jié)構(gòu)，以包含指向剛更新結(jié)構(gòu)的指針。這樣做可以使文件系統(tǒng)保持一致。
減少日志協(xié)議等待磁盤寫入完成的次數(shù)的技術(shù)。這種新方法名為樂觀崩潰一致性（optimistic crash consistency）
盡可能多地向磁盤發(fā)出寫入，并利用事務(wù)校驗(yàn)和（transaction checksum）的一般形式，以及其他一些技術(shù)來檢測(cè)不一致，如果出現(xiàn)不一致的話。
第43章日志結(jié)構(gòu)文件系統(tǒng)
——To Be Continue
