[發(fā)明專利]一種文件系統(tǒng)中實(shí)時(shí)刪除重復(fù)數(shù)據(jù)的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201010252734.0
• 申請(qǐng)日: 2010-08-13
• 公開(kāi)（公告）號(hào): CN101908073A
• 公開(kāi)（公告）日: 2010-12-08
• 發(fā)明（設(shè)計(jì)）人: 唐力;汪東升
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京清亦華知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11201
• 代理人: 羅文群

1.一種文件系統(tǒng)中實(shí)時(shí)刪除重復(fù)數(shù)據(jù)的方法，其特征在于該方法包括以下步驟：

(1)采用嵌入式數(shù)據(jù)庫(kù)存儲(chǔ)文件系統(tǒng)中的元數(shù)據(jù)信息，在該嵌入式數(shù)據(jù)庫(kù)中設(shè)置文件元數(shù)據(jù)表、數(shù)據(jù)塊索引表和文件組成表；所述的文件元數(shù)據(jù)表記錄文件系統(tǒng)中每個(gè)文件的元數(shù)據(jù)，該元數(shù)據(jù)包括文件標(biāo)識(shí)、文件名、文件所在文件夾的標(biāo)識(shí)、文件大小、文件類型、訪問(wèn)權(quán)限以及文件的創(chuàng)建、修改和訪問(wèn)時(shí)間；所述的數(shù)據(jù)塊索引表記錄文件系統(tǒng)中文件的數(shù)據(jù)塊的標(biāo)識(shí)以及與標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的引用次數(shù)，其中數(shù)據(jù)塊的標(biāo)識(shí)為該數(shù)據(jù)塊內(nèi)容的哈希值；所述的文件組成表記錄組成文件系統(tǒng)中的文件的數(shù)據(jù)塊的信息，包括上述文件標(biāo)識(shí)、數(shù)據(jù)塊起始位置、數(shù)據(jù)塊大小和數(shù)據(jù)塊標(biāo)識(shí)，由其中的數(shù)據(jù)塊起始位置和數(shù)據(jù)塊大小決定數(shù)據(jù)區(qū)域；

(2)通過(guò)文件系統(tǒng)的驅(qū)動(dòng)模塊，接收和響應(yīng)應(yīng)用程序?qū)ξ募到y(tǒng)發(fā)起的操作命令，該操作命令包括創(chuàng)建新文件、向已有文件寫入數(shù)據(jù)、從已有文件讀取數(shù)據(jù)和刪除已有文件，具體過(guò)程如下：

(2-1)當(dāng)文件系統(tǒng)的驅(qū)動(dòng)模塊接收到來(lái)自應(yīng)用程序的創(chuàng)建新文件的操作命令時(shí)，在文件元數(shù)據(jù)表中記錄被創(chuàng)建文件的元數(shù)據(jù)；

(2-2)當(dāng)文件系統(tǒng)的驅(qū)動(dòng)模塊接收到來(lái)自應(yīng)用程序的向已有文件寫入數(shù)據(jù)的操作命令時(shí)，進(jìn)行以下操作：

(2-2-1)根據(jù)操作命令中被寫文件的文件標(biāo)識(shí)、寫入位置和寫入數(shù)據(jù)大小，從上述文件組成表中檢索屬于該被寫文件的兩個(gè)數(shù)據(jù)塊標(biāo)識(shí)，且滿足與該兩個(gè)數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的兩個(gè)數(shù)據(jù)塊為與被寫入數(shù)據(jù)區(qū)域相互重疊的首、尾兩個(gè)數(shù)據(jù)塊；

(2-2-2)根據(jù)檢索到的數(shù)據(jù)塊標(biāo)識(shí)，從存儲(chǔ)設(shè)備中讀取與該數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊內(nèi)容；

(2-2-3)將讀出的數(shù)據(jù)塊內(nèi)容中與被寫入數(shù)據(jù)區(qū)域不重疊的數(shù)據(jù)拼接到被寫入數(shù)據(jù)的兩側(cè)，得到拼接后的數(shù)據(jù)及數(shù)據(jù)區(qū)域；

(2-2-4)從上述文件組成表中檢索與屬于該被寫文件、且數(shù)據(jù)塊起始位置位于上述步驟(2-2-3)數(shù)據(jù)區(qū)域之內(nèi)的數(shù)據(jù)塊相對(duì)應(yīng)的數(shù)據(jù)塊標(biāo)識(shí)；

(2-2-5)將與從上述數(shù)據(jù)塊索引表中檢索到的數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的引用次數(shù)減1，當(dāng)引用次數(shù)不為0時(shí)，進(jìn)行步驟(2-2-6)，當(dāng)引用次數(shù)成為0時(shí)，從數(shù)據(jù)塊索引表中刪除該數(shù)據(jù)塊標(biāo)識(shí)及與該數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊引用次數(shù)，并從存儲(chǔ)設(shè)備上刪除該數(shù)據(jù)塊內(nèi)容，進(jìn)行步驟(2-2-6)；

(2-2-6)將上述步驟(2-2-3)拼接后的數(shù)據(jù)切分成一組新數(shù)據(jù)塊；

(2-2-7)從上述數(shù)據(jù)塊索引表中分別搜索與上述一組新數(shù)據(jù)塊相對(duì)應(yīng)的每個(gè)數(shù)據(jù)塊標(biāo)識(shí)：若該數(shù)據(jù)塊標(biāo)識(shí)已存在，則在數(shù)據(jù)塊索引表中將與該數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的引用次數(shù)加1，若該數(shù)據(jù)塊標(biāo)識(shí)為新標(biāo)識(shí)，則在數(shù)據(jù)塊索引表中添加該新數(shù)據(jù)塊標(biāo)識(shí)，并將與該新數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的引用次數(shù)設(shè)置為1，并將與該新數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的新數(shù)據(jù)塊內(nèi)容存儲(chǔ)到存儲(chǔ)設(shè)備上；在上述文件組成表中記錄被寫文件的文件標(biāo)識(shí)、該新數(shù)據(jù)塊的起始位置、該新數(shù)據(jù)塊的大小以及該新數(shù)據(jù)塊的標(biāo)識(shí)；

(2-2-8)根據(jù)向已有文件寫入數(shù)據(jù)的操作命令更新上述文件元數(shù)據(jù)表中被寫文件的元數(shù)據(jù)；

(2-3)當(dāng)文件系統(tǒng)的驅(qū)動(dòng)模塊接收到來(lái)自應(yīng)用程序的從文件系統(tǒng)中的已有文件中讀取數(shù)據(jù)的操作命令時(shí)，進(jìn)行以下操作：

(2-3-1)根據(jù)操作命令，在計(jì)算機(jī)內(nèi)存中分配與待讀取數(shù)據(jù)的大小相等的內(nèi)存空間，并將該內(nèi)存空間初始化為空白；

(2-3-2)根據(jù)操作命令中的被讀文件的文件標(biāo)識(shí)和讀取位置，從上述文件組成表中檢索屬于該被讀文件的數(shù)據(jù)塊標(biāo)識(shí)，且滿足與該數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊是起始位置處于讀取位置之前的最后一個(gè)數(shù)據(jù)塊，若檢索到該數(shù)據(jù)塊標(biāo)識(shí)，且該數(shù)據(jù)塊區(qū)域與待讀取數(shù)據(jù)區(qū)域存在重疊，則讀取該數(shù)據(jù)塊內(nèi)容，并將該讀取的內(nèi)容與待讀取數(shù)據(jù)區(qū)域的重疊部分寫入上述步驟(2-3-1)的內(nèi)存空間的頭部，進(jìn)行步驟(2-3-3)，若檢索不到該數(shù)據(jù)塊標(biāo)識(shí)，或者與檢索到的數(shù)據(jù)標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊區(qū)域與待讀取數(shù)據(jù)區(qū)域不存在重疊，則進(jìn)行步驟(2-3-3)；

(2-3-3)根據(jù)操作命令，從上述文件組成表中檢索屬于該被讀文件的數(shù)據(jù)塊標(biāo)識(shí)，且滿足與該數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的起始位置處于待讀取數(shù)據(jù)區(qū)域內(nèi)；讀取與檢索到的所有數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的內(nèi)容，并將讀出的數(shù)據(jù)塊內(nèi)容中與待讀取數(shù)據(jù)區(qū)域的重疊部分寫入上述步驟(2-3-1)的內(nèi)存空間中；

(2-3-4)根據(jù)操作命令，更新上述文件元數(shù)據(jù)表中被讀文件的元數(shù)據(jù)；

(2-3-5)將上述步驟(2-3-1)的內(nèi)存空間中的數(shù)據(jù)通過(guò)文件系統(tǒng)的驅(qū)動(dòng)模塊返回給應(yīng)用程序；

(2-4)當(dāng)文件系統(tǒng)的驅(qū)動(dòng)模塊接收到來(lái)自應(yīng)用程序的刪除文件系統(tǒng)中的已有文件的操作命令時(shí)，進(jìn)行以下操作：

(2-4-1)從上述文件組成表中檢索屬于被刪除文件的數(shù)據(jù)塊標(biāo)識(shí)；

(2-4-2)在上述數(shù)據(jù)塊索引表中將與檢索到的每個(gè)數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊的引用次數(shù)減1，當(dāng)引用次數(shù)變?yōu)?時(shí)，從數(shù)據(jù)塊索引表中刪除該數(shù)據(jù)塊標(biāo)識(shí)及與該數(shù)據(jù)塊標(biāo)識(shí)相對(duì)應(yīng)的數(shù)據(jù)塊引用次數(shù)，從存儲(chǔ)設(shè)備上刪除該數(shù)據(jù)塊內(nèi)容，并進(jìn)行步驟(2-4-3)，當(dāng)引用次數(shù)未變?yōu)?時(shí)，進(jìn)行步驟(2-4-3)；

(2-4-3)從上述文件組成表中刪除被刪除文件的所有記錄；

(2-4-4)從上述文件元數(shù)據(jù)表中刪除被刪除文件的元數(shù)據(jù)。