隨著科技不斷的發展，出現了很多新的技術和產品，而這些新的技術和產品大多都有龐大的資料量以及對資料快速讀寫的需求，因此在儲存媒介上的要求也相對的提高很多，所以非揮發性記憶體(Non-Volatile Memory；NVM)這一種電腦記憶體也就顯得重要了。非揮發性記憶體是一種能夠兼顧讀寫速度以及一定容量的電腦記憶體，但相較於傳統儲存媒介，儲存空間仍顯不足，也因此如何節省資料儲存空間則成為一大挑戰。
  而節省資料儲存空間的技術主要分成兩類，壓縮檔案以及重複資料刪除。重複資料刪除這項技術會將電腦裡面多筆相同的資料進行刪除只保留一份，這樣可以減少儲存的資料量和提高資料寫入速度並且保持所有資料的完整性，在現有的重複數據刪除技術中有兩種級別的處理方式，分為文件級別重複數據刪除以及塊級別的重複數據刪除這兩種，文件級別的重複數據刪除也就是以一個文件或是檔案當作單位去做判斷，判斷這個文件有沒有相同的資料，從而進行刪除，而塊級別重複數據刪除則是把每筆資料去做切割(約4kb~12kb)，這種做法比起文件級別的重複數據刪除更可以大大的提升數據的重複率從而提高節省的空間達到想要的效果，但也因此會增加一些讀寫速度的成本。
  故本論文的主要研究方法是要透過修改第四代擴充套件檔案系統(Fourth extended filesystem，縮寫為EXT4)使EXT4做到塊級別的重複數據刪除技術並且將其系統放在非揮發性記憶體，而為了讓檔案系統在NVM上有更好的效能並節省更多的空間，所以本論文在檔案系統的整體結構上進行一些新增與修改，並透過EXT4的Extent架構來幫每一個切割好的塊去做整理以及尋找相同資料的塊來進行重複數據刪除。本篇論文的資料切割使用可變長度的資料塊去將資料切割以提高資料的重複率。
  而透過本論文中的模擬結果與分析我們不難發現，本篇論文的方法DeEXT4 檔案系統可以有效的減少重複資料寫入硬碟裡面，而且在檔案重複性較高的文件不只可以減少一般數據的寫入量還可以減少metadata 的使用量，這樣的結果對於EXT4系統有很大的幫助。

With the continuous development of technologies, many new techniques and products have emerged. Most of these new technologies and products yield huge amount of data and require high speed of reading and writing data. Therefore, the needs of storage are comparatively increased and the Non-Volatile Memory (NVM), which considers both the read/write speed and the data capacity becomes an important storage medium. However, NVM has a relatively small data capacity compared to traditional storage such as disk, it is important to reduce the needed storage space of data.

  The technology for saving data storage space is mainly divided into two categories, data compression and data deduplication. Data deduplication will delete multiple copies of the same data on the computer and leaving only one copy. The needed space of data can therefore be reduced and the speed of data writing can be improved. There are two mainly techniques in deduplication, i.e., file level deduplication and block level deduplication. File level deduplication considers a file as a unit for dedupe, whereas block level deduplication cuts a file into data blocks and considers a block as a unit for dedupe. Block level deduplication can greatly reduce the storage space compared to file level deduplication.

Therefore, in this thesis, we strengthen the ability of the EXT4 file system with data deduplication functionality. To make the file system have better performance on NVM and save more space, we made some changes to the structure of filesystem and utilize the Extent structure of EXT4 to track every data block for searching the same data block and for deduplication. The proposed filesystem called DeEXT enable EXT4 to support block-level deduplication efficiently while writing data into NVM storage. 
As the simulation and analysis results show in this paper, DeEXT4 filesystem can effectively reduce the duplicate data written into the storage, and reduce larger amount of metadata if the file duplicated rate is higher.

目錄
致謝 I
中文摘要 II
英文摘要 III
第一章	緒論	1
1.1	前言	1
1.2	動機與目的	1
1.3	論文章節架構	2
第二章	背景知識與相關文獻	3
2.1	第四代擴充套件檔案系統(Fourth extended file system)	3
2.1.1	起源與發展	4
2.1.2	EXT4檔案系統	6
2.1.3	Extent架構	7
2.2	重複資料刪除(data deduplication)	9
2.2.1	重複資料刪除種類	10
第三章	具有重複資料刪除之EXT4檔案系統於NVM上之研究	15
3.1	整體結構	16
3.2	Compressible Check and Deduplicator	18
3.3	DeEXT4子系統-DeEXT	19
3.3.1	Allocated Region Info 和 Space Defrag	20
3.3.2	Dedupe Extent Struct	22
3.3.3	流程圖	24
第四章	模擬與結果	26
4.1	實驗內容	26
4.1.1	模擬數據討論	26
4.2	數據與分析	27
4.3	數據討論	41
第五章	貢獻與未來展望	42
5.1	主要貢獻	42
5.2	未來展望	42
參考文獻	43
圖目錄
圖 2.1 Ext3檔案儲存方式	5
圖2.2 EXT4 檔案系統結構	6
圖2.3 EXT4 Extent	8
圖2.4重複資料刪除技術	10
圖 2.5 Inline Deduplication以及Post Deduplication 11
圖2.6 Block Level 和File Level	13
圖2.7 固定長度切割和不固定長度切割	14
圖3.1架構圖	16
圖 3.2整體結構	18
圖3.3Compressible Check and Deduplicator流程圖	19
圖3.4DeEXT整體架構	20
圖 3.5Allocated Region Info	21
圖3.6Allocated Region Info 和 Space Defrag	22
圖3.7Dedupe Extent Struct	24
圖 3.8流程圖	25
圖 4.1 Cello99使用資料量模擬結果	29
圖4.2 Cello99節省資料效能百分比模擬結果	29
圖4.3 Cello99 metadata模擬結果	30
圖4.4 Financial 1使用資料量模擬結果	32
圖4.5 Financial 1節省資料效能百分比模擬結果	32
圖4.6 Financial 1 metadata模擬結果	33
圖4.7 Financial 2使用資料量模擬結果	35
圖4.8 Financial 2節省資料百分比模擬結果	35
圖4.9 Financial 2 metadata模擬結果	36
圖4.10 Web Search使用資料量模擬結果	38
圖4.11 Web Search節省資料效能百分比模擬結果	38
圖4.12 Web Search metadata模擬結果	39
圖4.13 整體節省資料效能百分比模擬結果	40
圖4.14 整體metadata 節省比率	40

 
表目錄

表 4.1數據分析	27
表4.2 Cello99模擬結果	28
表4.3 Financial 1模擬結果	31
表4.4 Financial 2模擬結果	34
表4.5 Web Search模擬結果	37

參考文獻
[1]	儲存技術大未來 希捷以SMR、氦氣填充、HAMR擴展儲存技術極限,(2016,June,05),Retrieved from https://www.computerdiy.com.tw/seagate-smr-hamr/
[2]	Leo Zhenjun Li ,(2017,August,16), 當我們說重刪，我們 https://community.emc.com/thread/240827?start=0&tstart=0
[3]	重複數據刪除,(2017,November,1) .Retrieved from https://zh.wikipedia.org/wiki/%E9%87%8D%E5%A4%8D%E6%95%B0%E6%8D%AE%E5%88%A0%E9%99%A4
[4]	ext文件系統機制原理剖析.(2017,June,15) Retrieved from http://www.cnblogs.com/f-ck-need-u/p/7016077.html
[5]	ext3(2018,January,27) Retrieved from  https://zh.wikipedia.org/wiki/Ext3
[6]	深入理解ext4(2013,February,25) Retrieved from https://blog.csdn.net/sara4321/article/details/8609610
[7]	M.Jones,(2009,April,16),剖析ext4 Retrieved from https://www.ibm.com/developerworks/cn/linux/l-anatomy-ext4/index.html
[8]	Ext4 ,(2017,November,11) Retrieved from https://zh.wikipedia.org/wiki/Ext4
[9]	David Both ,(2017,July,11), Linux 的 EXT4 檔案系統的歷史、特性以及最佳實踐 Retrieved from https://itw01.com/FLMDEKL.html
[10]	趙蔚,(2002,June,01), Ext2 文件系統的硬盤佈局Retrieved from https://www.ibm.com/developerworks/cn/linux/filesystem/ext2/index.html
[11]	João Paulo , José Pereira “A Survey and Classification of Storage Deduplication Systems”, ACM Computing Surveys,2014
[12]	Dutch T. Meyer, William J. Bolosky“A study of practical deduplication”, ACM Transactions on Storage,2012
[13]	Chun-Ta Lin ;  Yuan-Hao Chang ;  Tei-Wei Kuo ;  Hung-Sheng Chang ;  Hsiang-Pang Li“ How to improve the space utilization of dedup-based PCM storage devices?”, International Conference on Hardware/Software Codesign and System Synthesis,2015
[14]	Guanlin Lu,Yu Jin,David H.C. Du“Frequency Based Chunking for Data De-Duplication”, IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems,2010
[15]	Wen Xia, Yukun Zhou, Hong Jiang, Dan Feng,Yu Hua, Yuchong Hu, Yucheng Zhang, Qing Liu. Du“FastCDC: a Fast and Efficient Content-DefinedChunking Approach for Data Deduplication”,  USENIX Annual Technical Conference,2016.
[16]	Cello 1999 (2011) Retrieved from http://iotta.snia.org/traces/21
[17]	OLTP Application I/O(2007,June,01) Retrieved from http://traces.cs.umass.edu/index.php/Storage/Storage