文件隨機或順序讀寫原理深入淺出

一、文件讀寫的用戶程式、作業系統、磁碟交互原理

  最近為了徹底搞懂文件讀寫原理,我特意查詢了很多資料,包括Java讀寫文件的API程式碼、作業系統處理文件以及磁碟硬體知識等。由於網上現存技術文章,幾乎沒有找到一篇能夠徹底綜合講明白這個原理的文章。心中還是有很多疑問。且有不少文章包括書籍所闡述的隨機/順序讀寫原理講述的都是錯誤或誤導性的。所以我綜合了一下我能查閱到的所有資料,深入細節知識,給大家徹底講明白這事。原創文章,轉發請保留第一作者著作權。謝謝!
  如下圖所示。我們編寫的用戶程式讀寫文件時必須經過的OS和硬體交互的記憶體模型。

1、讀文件

  用戶程式通過程式語言提供的讀取文件api發起對某個文件讀取。此時程式切換到內核態,用戶程式處於阻塞狀態。由於讀取的內容還不在內核緩衝區中,導致觸發OS缺頁中斷異常。然後由OS負責發起對磁碟文件的數據讀取。讀取到數據後,先存放在OS內核的主存空間,叫PageCache。然後OS再將數據拷貝一份至用戶進程空間的主存ByteBuffer中。此時程式由內核態切換至用戶態繼續運行程式。程式將ByteBuffer中的內容讀取到本地變數中,即完成文件數據讀取工作。

2、寫文件

  用戶程式通過程式語言提供的寫入文件api發起對某個文件寫入磁碟。此時程式切換到內核態用戶程式處於阻塞狀態,由OS負責發起對磁碟文件的數據寫入。用戶寫入數據後,並不是直接寫到磁碟的,而是先寫到ByteBuffer中,然後再提交到PageCache中。最後由作業系統決定何時寫入磁碟。數據寫入PageCache中後,此時程式由內核態切換至用戶態繼續運行。
用戶程式將數據寫入內核的PageCache緩衝區後,即認為寫入成功了。程式由內核態切換回用於態,可以繼續後續的工作了。PageCache中的數據最終寫入磁碟是由作業系統非同步提交至磁碟的。一般是定時或PageCache滿了的時候寫入。如果用戶程式通過調用flush方法強制寫入,則作業系統也會服從這個命令。立即將數據寫入磁碟然後由內核態切換回用戶態繼續運行程式。但是這樣做會損失性能,但可以確切的知道數據是否已經寫入磁碟了。

一、文件讀寫詳細過程

1、讀文件

  如下所示為一典型Java讀取某文件內容的用戶編程程式碼。接下來我們詳細解說讀取文件過程。

            // 一次讀多個位元組
            byte[] tempbytes = new byte[100];
            int byteread = 0;
            in = new FileInputStream(fileName);//
            ReadFromFile.showAvailableBytes(in);
            // 讀入多個位元組到位元組數組中,byteread為一次讀入的位元組數
            while ((byteread = in.read(tempbytes)) != -1) { //
                System.out.write(tempbytes, 0, byteread);
            }

View Code

  首先通過位置①的程式碼發起一個open的系統調用,程式由用戶態切換到內核態。作業系統通過文件全路徑名在文件目錄中找到目標文件名對應的文件iNode標識ID,然後用這個iNode標識ID在iNode索引文件找到目標文件iNode節點數據並載入到內核空間中。這個iNode節點包含了文件的各種屬性(創建時間,大小以及磁碟塊空間佔用資訊等等)。然後再由內核態切換回用戶態,這樣程式就獲得了操作這個文件的文件描述。接下來就可以正式開始讀取文件內容了。
  然後再通位置②,循環數次獲取固定大小的數據。通過發起read系統調用,作業系統通過文件iNode文件屬性中的磁碟塊空間佔用資訊得到文件起始位的磁碟物理地址。再從磁碟中將要取得數據拷貝到PageCache內核緩衝區。然後將數據拷貝至用戶進程空間。程式由內核態切換回用戶態,從而可以讀取到數據,並放入上面程式碼中的臨時變數tempbytes中。
  整個過程如下圖所示。
  至於上面說到的作業系統通過iNode節點中的磁碟塊佔用資訊去定位磁碟文件數據。其細節過程如下圖所示。

①根據文件路徑從文件目錄中找到iNode ID。

  用戶讀取一個文件,首先需要調用OS中文件系統的open方法。該方法會返回一個文件描述符給用戶程式。OS首先根據用戶傳過來的文件全路徑名在目錄索引數據結構中找到文件對應的iNode標識ID。目錄數據是存在於磁碟上的,在OS初始化時就會載入到記憶體中,由於目錄數據結構並不會很龐大,一次性載入駐留到記憶體也不是不可以或者部分載入,等需要的時候在從磁碟上調度進記憶體也可以。根據文件路徑在目錄中查找效率應該是很高的,因為目錄本身就是一棵樹,應該也是類似資料庫的樹形索引結構。所以它的查找演算法時間複雜度就是O(logN)。具體細節我暫時還沒弄清楚,這不是重點。
  iNode就是文件屬性索引數據了。磁碟格式化時OS就會把磁碟分區成iNode區和數據區。iNode節點就包含了文件的一些屬性資訊,比如文件大小、創建修改時間、作者等等。其中最重要的是還存有整個文件數據在磁碟上的分布情況(文件佔用了哪些磁碟塊)。

②根據iNode ID從Inode索引中找到文件屬性。

  得到iNode標識的ID後,就可以去iNode數據中查找到對應的文件屬性了,並載入到記憶體,方便後續讀寫文件時快速獲得磁碟定位。iNode數據結構應該類似哈希結構了,key就是iNode標識ID,value就是具體某個文件的屬性數據對象了。所以它的演算法時間複雜度就是O(1)。具體細節我暫時還沒弄清楚,這不是重點。
  我們系統中的文件它的文件屬性(iNode)和它的數據正文是分開存儲的。文件屬性中有文件數據所在磁碟塊的位置資訊。

③根據文件屬性中的磁碟空間塊資訊找到需要讀取的數據所在的磁碟塊的物理位置

  文件屬性也就是iNode節點這個數據結構,裡面包含了文件正文數據在磁碟物理位置上的分布情況。磁碟讀寫都是以塊為單位的。所以這個位置資訊其實也就是一個指向磁碟塊的物理地址指針。
  其結構圖如下。
  文件屬性里就包含了文件正文數據佔有磁碟所有資訊。但是由於文件屬性大小有限制,而文件大小沒有限制。這樣會導致磁碟塊佔用資訊超出限制。所以最後一個磁碟數據項設計為特殊的作用。它是一個指向更多磁碟佔用資訊數據的指針。這些更多資訊存放在普通的數據區。這樣當文件iNode載入到記憶體後,可以把其他更多磁碟塊資訊一起載入進來。這樣就避免了iNode索引文件太大的問題。
後續的文件讀寫系統調用,由用戶態切換至內核態。作業系統就可以根據文件數據的相對位置(偏移量)快速從iNode中的磁碟塊佔用數據結構中找到其對應的磁碟物理位置在哪裡了。很明顯這個數據結構類似哈希結構,其演算法複雜度就是O(1)。
  比如我們現在討論的讀取數據。每次用戶程式碼的api調用read方法時。由於時從頭開始讀取,所以OS就從上圖中「磁碟塊0」數據項開始迭代,獲取對應的物理磁碟塊起始地址開始讀取數據並拷貝至PageCache緩衝區,再拷貝至用戶進程緩衝區。這樣用戶程式碼就可以獲取這些數據了。
考慮到另外一種隨機讀的場景。我們並不是把整個文件從頭開始讀一遍。而是需要直接定位到文件的中間某個位置開始 讀取部分內容。如下所示。

  RandomAccessFile raf=new RandomAccessFile(new File("D:\\3\\test.txt"), "r");   
            //獲取RandomAccessFile對象文件指針的位置,初始位置是0  
            System.out.println("RandomAccessFile文件指針的初始位置:"+raf.getFilePointer());  
            raf.seek(pointe);//移動文件指針位置  
            byte[]  buff=new byte[1024];  
            //用於保存實際讀取的位元組數  
            int hasRead=0;  
            //循環讀取  
            while((hasRead=raf.read(buff))>0){  
                //列印讀取的內容,並將位元組轉為字元串輸入  
                System.out.println(new String(buff,0,hasRead));       
            }  

View Code

  程式程式碼調用seek方法直接定位到某個文件相對位置開始讀取內容。實際上就是調用了OS管理文件的系統調用seek函數。這個系統調用需要傳遞一個文件相對位置也就是偏移量,不是指磁碟的物理位置。文件的相對位置偏移量是從0開始的,結束位置和文件的大小位元組數相等。作業系統拿到這個偏移量後,就可以計算出文件所屬的邏輯塊編號。因為每個塊是固定大小的,所以能計算出來。通過文件屬性的邏輯磁碟塊資訊就能得到磁碟塊的物理位置。從而可以快速直接定位到磁碟物理塊讀取到需要的數據。這裡說的邏輯塊和物理塊的概念是有區別的。邏輯塊屬於當前的文件從0開始編號,物理塊才是磁碟真正的存放數據的區域,屬於全局的。編號自然不是從0開始的。

2、寫文件

  寫文件的過程和前面闡述的差不多,相關的知識點也在讀文件中已經順帶描述了。就不在贅述了。這裡就說些特別需要注意的點就行。

  ③根據空閑塊索引找到可以寫入的物理位置並寫入

  如上圖所示,OS寫文件內容時首先要訪問磁碟空閑塊索引表。這是個什麼東西呢?由於磁碟很大,不可能每次寫數據時,都讓磁頭從頭到尾遍歷一次才能找到空閑位置。這樣效率可想而知的差勁。所以OS會把磁碟上的空閑塊索引起來存放在磁碟某個位置上。後續磁碟存儲和刪除文件內容時都通過這個空閑塊索引錶快速定位,同時刪除數據也會更新索引表增加空閑塊。
空閑塊記錄索引的實現常用有兩種,一種是我們熟悉的鏈表結構,還有一種是點陣圖結構。這裡就不詳細討論了。

  ④寫入數據後更新iNode里的磁碟佔用塊索引

  數據寫入後,那麼這個空閑塊就被佔用了,自然也就需要更新下iNode文件屬性里的磁碟佔用塊索引數據了。
我們前面說的寫文件都是只講了尾部追加這種方式。但是實際上我們可以通過RandomAccessFile類實現文件隨機位置寫功能。但是我們同時也有一些困惑。為啥不能直接在中間某個位置插入我們要寫的內容,而是要先把插入位置後面的內容截取放入臨時文件中。插入新內容後,再把臨時文件內容尾部追加到原來的文件中來實現文件修改?程式碼如下所示。

public static void insert(String fileName, long pos, String insertContent) throws IOException{
        File file = File.createTempFile("tmp", null);
        file.deleteOnExit();
        RandomAccessFile raf = new RandomAccessFile(fileName, "rw");
        FileInputStream fileInputStream = new FileInputStream(file);
        FileOutputStream fileOutputStream = new FileOutputStream(file);
        raf.seek(pos);
        byte[] buff = new byte[64];
        int hasRead = 0;
        while((hasRead = raf.read(buff)) > 0){
            fileOutputStream.write(buff);
        }
        raf.seek(pos);
        raf.write(insertContent.getBytes());
        //追加文件插入點之後的內容
        while((hasRead = fileInputStream.read(buff)) > 0){
            raf.write(buff, 0, hasRead);
        }
        raf.close();
        fileInputStream.close();
        fileOutputStream.close();
    }

View Code

  按照我們上面的闡述,寫入的文件內容完全可以存入磁碟上的一個新塊,然後更新下iNode屬性里的佔用磁碟塊索引數據即可。也不需要真的去移動磁碟上的所有數據塊。看上去成本也很小,可為啥我們的編程api卻都不支援呢?
  我想答案可能是這樣的。假如允許我們上面那種操作,如果一個很大的文本文件。你現在只是編輯了文本中間某個位置的一個字,即插入了一個文本字元。那麼此時這個新增的文本內容就得在磁碟上找到一個新的塊存儲下來。這樣是不是有點浪費空間呢?因為磁碟上的一個塊只能分配給一個文件使用,塊大小如果是64kb的話,一個字元也就佔用了2個位元組的空間。更要命的是這樣一搞,使得原本滿存狀態的塊,出現很多不連續的空洞。這樣就會使得讀取文件時數據是不連續的,系統需要額外資訊記錄這些中間的存儲空洞。加大了讀取難度。這就是我猜測的原因。實際上作業系統層面也沒有這種操作插入的系統調用函數。故程式語言層面也就沒法支援了。
  作業系統層面給上層應用程式提供了寫文件的兩個系統調用。write和append,其中append是write的限制形式,即只能在文件尾部追加。而write雖然提供了隨機位置寫,但是並不是將新內容插入其中,而是覆蓋原有的數據。我們平時使用Word文本編輯軟體時,如果對一個很大的文件進行編輯,然後點擊保存,你會發現很慢。同時你還能看到文件所在的目錄下生成了一個新的處於隱藏狀態的臨時文件。這些現象也能說明我們上面的觀點。即編輯文件時,需要一個成本很高的過程。如下圖所示。
 

三、常見認知誤區澄清

1、磁碟上文件存儲數據結構是鏈表,每一塊文件數據節點裡有一個指針指向下一塊數據節點。理解錯誤!

  很多人都知道磁碟存儲一個文件不可能是連續分配空間的。而是東一塊西一塊的存儲在磁碟上的。就誤以為這些分散的數據節點就像鏈表一樣通過其中一個指針指向下一塊數據節點。如下圖所示。
  怎麼說呢?這種方案以前也是有一些文件系統實現過的方案,但是現在常見的磁碟文件系統都不再使用這種落後的方案。而是我前面提到的iNode節點方案。也就是說磁碟上存儲的文件數據塊就是純數據,沒有其他指針之類的額外資訊。之所以我們能順利定位這些數據塊,都全靠iNode節點屬性中磁碟塊資訊的指針。

2、append文件尾部追加方法是順序寫,也就是磁碟會分配連續的空間給文件存儲。理解錯誤!

  這種觀點,包括網上和某些技術書籍里的作者都有這種觀點。實際上是錯誤的。或許是他們根本沒有細究文件存儲底層OS和磁碟硬體的工作原理導致。我這裡就重新總結糾正一下這種誤導性觀點。
前面說過,append系統調用是write的限制形式,即總是在文件末尾追加內容。看上去好像是說順序寫入文件數據,因為是在尾部追加啊!所以這樣很容易誤導大家以為這就是順序寫,即磁碟存儲時分配連續的空間給到文件,減少了磁碟尋道時間。
  事實上,磁碟從來都不會連續分配空間給哪個文件。這是我們現代文件系統的設計方案。前面介紹iNode知識時也給大家詳細說明了。所以就不再贅述。我們用戶程式寫文件內容時,提交給OS的緩衝區PageCache後就返回了。實際這個內容存儲在磁碟哪個位置是由OS決定的。OS會根據磁碟未分配空間索引表隨機找一個空塊把內容存儲進去,然後更新文件iNode里的磁碟佔用塊索引數據。這樣就完成了文件寫入操作。所以append操作不是在磁碟上接著文件末尾內容所在塊位置連續分配空間的。最多只能說邏輯上是順序的。
  那麼邏輯上的隨機寫write是不是會慢呢?根據前面介紹的原理,應該是相同的效率。我們可以做如下測試驗證。使用RandomAccessFile 實現,因為只有這個類支援隨機位置寫入,其他寫文件類都只提供尾部追加方式。打開一個20M的文本文件「test.txt」。分別採用如下兩個方法,隨機位置寫入和尾部追加寫入做100000次操作,多次測得大概的平均耗時數據。

// 文件隨機位置寫入 耗時:1000ms
public static void randomWrite1(String path,String content) throws Exception {
RandomAccessFile raf=new RandomAccessFile(path,"rw");
Random random=new Random();
for(int i=0;i<100000;i++){
raf.seek(random.nextInt((int)raf.length())); // 在文件隨機位置寫入覆蓋
raf.write((i+content+System.lineSeparator()).getBytes());
}
raf.close();
}
// 文件尾部位置寫入 耗時:800ms
public static void randomWrite2(String path,String content) throws Exception {
RandomAccessFile raf=new RandomAccessFile(path,"rw");
for(int i=0;i<100000;i++){
raf.seek(raf.length()); // 總是在文件尾部追加
raf.write((i+content+System.lineSeparator()).getBytes());
}
raf.close();
}

View Code

  看上去採用尾部追加性能略高。實際上也相差不大。多出的200ms只是生成隨機數消耗的。因為如果說隨機位置寫需要某些人認為的磁碟磁頭來回反覆移動,則性能不可能只差這麼一丟丟。實際上我去掉隨機數生成的程式碼,改用固定中間位置寫入,這兩個方法耗時幾乎沒有區別了。這說明無論是尾部追加還是隨機位置寫入方式,性能都是一樣的。因為根據前面介紹的原理,OS通過iNode中的磁碟佔用塊哈希表,可以快速定位到目標磁碟物理位置,其演算法時間複雜度是O(1)。所以尾部追加也是一樣的定位效率。
可能也有些人想說怎麼不試試BufferWriter、FileWriter等寫入類,效率高几個數量級比RandomAccessFile 。我也的確測試過,但是這些類都是採用尾部追加模式,無法和其隨機位置寫入做比較。所以沒法拿出來測試說明。但是這些類寫入性能之所以遠高於直接用RandomAccessFile 尾部追加。我想是因為api方法做了用戶程式層面的優化,比如批量寫入,批量轉化成Byte之類的。而RandomAccessFile 可能就是最原始的直接對接OS系統調用層的API了。

3、mmap記憶體映射技術之所以快,是因為直接把磁碟文件映射到用戶空間記憶體,不走內核態。理解錯誤!

  這也是一種常見的認知誤區,實際上這個技術是作業系統給用戶程式提供的一個系統調用函數。它把文件映射到OS內核緩衝區空間,同時共享給用戶進程,也可以共享給多個用戶進程。映射過程中不會產生實際的數據從磁碟真正調取動作,只有用戶程式需要的時候才會調入部分數據。總之也是和普通文件讀取一樣按需調取。那麼mmap技術為什麼在讀取數據時會比普通read操作快幾個數量級呢?
上面我們講述了普通讀寫操作的記憶體模型。用戶程式要讀取到磁碟上的數據。要經歷4次內核態切換以及2次數據拷貝操作。那麼mmap技術由於是和用戶進程共享內核緩衝區,所以少了一次拷貝操作(數據從內核緩衝區到用戶進程緩衝區)。從而大大提高了性能。如下圖所示。

4、mmap記憶體映射技術寫文件快是因為順序寫磁碟。理解錯誤!

  上面的問題基本已經讓我們理解了mmap技術的記憶體模型。同樣的,我們寫文件時,由於也少了一次數據從用戶緩衝區到內核緩衝區的拷貝操作。使得我們的寫效率非常的高。並不是很多人認為的數據直達磁碟,中間不經過內核態切換,並且連續在磁碟上分配空間寫入。這些理解都是錯誤的。

5、隨機讀寫文件比順序讀寫文件慢,是因為磁碟移動磁頭來回隨機移動導致。理解錯誤!

  這也是一種常見的誤區。我看過很多文章都是這樣認為的。其實所有的寫操作在硬體磁碟層面上都是隨機寫。這是由現代作業系統的文件系統設計方案決定的。我們用戶程式寫入數據提交給OS緩衝區之後,就與我們沒關係了。作業系統決定何時寫入磁碟中的某個空閑塊。所有的文件都不是連續分配的,都是以塊為單位分散存儲在磁碟上。原因也很簡單,系統運行一段時間後,我們對文件的增刪改會導致磁碟上數據無法連續,非常的分散。
  當然OS提交PageCache中的寫入數據時,也有一定的優化機制。它會讓本次需要提交給磁碟的數據規劃好磁頭調度的策略,讓寫入成本最小化。這就是磁碟調度演算法中的電梯演算法了。這裡就不深入講解了。
  至於讀文件,順序讀也只是邏輯上的順序,也就是按照當前文件的相對偏移量順序讀取,並非磁碟上連續空間讀取。即便是seek系統調用方法隨機定位讀,理論上效率也是差不多的。都是使用iNode的磁碟佔用塊索引文件快速定位物理塊。