分布式文件快速搜索V7.0(多計算機并行)
2010-07-13 20:19 靈感之源 閱讀(6435) 評論(11) 收藏 舉報
系列文章
1.分布式文件快速搜索V7.0(多計算機并行/多種算法)
2.分布式文件快速搜索的設計與實現(開源/分布式計算/并行)
前言
這個話題很古老了，用C#實現的也很多，很明顯我是在造輪子了。不過我今晚閑得頭疼，在codeplex碰見看見一個項目，就是找重復文件的，項目代碼我沒看，我只是想找事情做。對開發人員來說，舒展一下手指的最佳辦法是敲代碼了。我最喜歡通過寫代碼來學東西了，看著枯燥的書本就沒勁。
需求
找重復文件，首先是要獲取文件的特征，很久以前用CRC，雖然最近MD5已經給中國某大學研究員驗證不可靠，不過我還是喜歡MD5:)。你可以選擇SHA1，換個類名就可以了。
實現
實現的辦法很簡單，就是把所有文件的特征都算出來，然后比較。
問題是，如果盲目地對每個文件都先獲取哈希特征，再進行比較，那會很浪費時間，譬如你的磁盤沒有重復文件，或者有些很巨大的不重復文件，那你就要把絕大部分時間浪費在無謂的哈希獲取上了。
所以，我們先使用文件大小進行碰撞，再對相同大小的進行碰撞，可以極大地提高效率。為什么選擇文件大小呢？因為如果文件大小不一樣，那就不可能內容重復了吧？為什么不同時選擇文件的修改時間？文件修改時間不一樣，文件內容也是可以一樣的，對不？既然我們的目的只是找內容相同的文件（不是文件名相同），那我們就可以無視文件名和文件修改時間了。允許選擇不同的特征組合，譬如先是單純的文件大小，或者文件大小+文件名+創建時間。
實現過程是用Dictionary來根據特征分組，碰撞（相同文件內容）就放到該特征下的重復文件列表，最后找出所有重復的文件。
程序很簡單，主要是原始文件和重復文件的選擇。函數可以指定重復目錄，如果匹配到是在重復目錄下的，就認為是可刪除的（相對保留原始文件而言，本程序沒有刪除代碼。。。）重復的文件，如果沒有指定重復目錄，則自動選擇第一個文件為原始文件。
并行的實現
一直想用多線程來實現提速，今晚閑得頭疼，就簡陋地實現。大概實現步驟：因為不是.NET3.5/4，所以沒有PPL，只能模擬并行了：C# Parallelism: Executing Methods in Parallel in .NET 3.5 。原理是封裝了ThreadPool，結合ManualResetEvent和WaitHandle.WaitAll等待所有線程完成。在.NET 2.0中，Dictionary不是線程安全的，又不想花時間自己寫封裝，就只有在網上找了個封裝好的線程安全的Dictionary。多線程的思想是：分配任務，分而治之。業務邏輯是自行切割要檢索的文件夾到不同的線程，得到結果后，最終實現并行計算。
網上發現的最quick & dirty的代碼
http://www.hosca.com/blog/post/2010/04/13/using-LINQ-to-detect-and-remove-duplicate-files.aspx
這個代碼極大地讓感到我今晚寫的代碼很冗余。。。它用了幾個Linq的語句：Select所有文件，GroupBy哈希值，然后ForEach刪除。。。Linq是很精妙。。。不過這個辦法跟我的老慢速算法是大同小異的，所以速度也是可以無視的。
我實現的代碼(讓你容易找點......)
老規矩，vs2005+c#2.0，quick & dirty，沒linq，沒var，沒有自動屬性。不要跟代碼規范較真，也不要糾纏為什么代碼都放一個文件，純粹是為了方便粘貼到博客而已，在產品開發中，6000多個手工寫的類我都是很有組織地歸類的:)
代碼中有7個算法：
WorkV1：最原始的，對每個文件都進行哈希值比對；
WorkV2：較新的算法，先用文件大小（或加上文件名、創建日期、修改日期等）進行過濾，匹配的文件組合才進行哈希值比對；
WorkV3：新的多線程算法，把多線程應用到文件檢索和文件哈希值獲取；
WorkV4：測試發現如果把多線程應用到文件讀取，則性能急劇下降，但僅獲取文件信息，則有很大提升，雖然瓶頸在文件讀取，但起碼在檢索信息上，比起V2有了提升；
WorkV5：新的算法，文件檢索使用多線程，文件哈希值獲取則動態判斷文件所在地物理磁盤，如果不是同一個物理磁盤，則是使用多線程，否則采用跟V2一樣的算法；因為判斷物理磁盤引入了System.Management.dll，使用了DriveIdentification條件編譯；
WorkV6：新的算法，支持對互聯網上的計算機進行搜索，哈希值的快速存取，文件內容搜索，全文索引；
WorkV7：最新的算法，添加了對協議提供者模式的支持，可以自由添加各種訪問協議；
在這里比較性能其實意義不大，以為不同機器比較不同的文件，差異太大了，譬如你的機器有2個文件，一個巨大，一個渺小，用新的快速算法，微秒間完成，用老的慢算法，則你可能要去睡一覺。
程序有3個條件編譯：DRIVEID啟用物理磁盤識別（需要引用System.Management.dll）,VERBOSE啟用詳細的調試信息,LoG啟用保存日志
使用
看代碼，判斷支持多個文件夾。先Find出重復文件組合(指紋/相同文件列表)，再用FindAll找出可以刪除的所有重復文件。
如果要實現分布式搜索，必須在被搜索的計算機運行WorkV7Manager的實例，具體參看代碼。
本地搜索
搜索本地完全一樣的文件
Dictionary<string, MatchFileItem> result;
BaseWork worker = new WorkV6();
result = worker.Find(new FileURI[] { new FileURI(@"c:\download\"), new FileURI(duplicateFolder)}
, new string[] { }, "", SearchTypes.Size | SearchTypes.Name, MatchTypes.ContentSame);
List<string> duplicatedFiles = worker.FindAll(result, duplicateFolder);
分布式搜索
初始化
WorkUtils.Initialiaze(new KeyValuePair<string, string>(), CompressionMethods.GZip, new System.Net.WebProxy());
服務器端
服務器端
Dictionary<string, UserAccess> users = new Dictionary<string, UserAccess>();
users.Add("user", new UserAccess("user", "pass", UserRights.Discover | UserRights.Search));
string[] allowedPaths = new string[] { @"e:\temp\New Folder" };
manager.Start(users, allowedPaths, 8880);
客戶端
客戶端
Dictionary<string, MatchFileItem> result;
result = Worker.Find(new FileURI[] { new FileURI(@"c:\download\"), remoteFolder }
, new string[] { }, "YOUR KEYWORD HERE", SearchTypes.Size, MatchTypes.ContentExtract);
List<string> matchFiles = Worker.FindAll(result, string.Empty);
已知問題
本程序并沒有考慮因為文件量巨大而會造成內存不足等問題，這個就留到以后我閑得更頭痛的時候再考慮吧。
如果你要同時測試多種算法，那是不可能的，因為所有算法的瓶頸是對文件的哈希值獲取，而這個方法允許Windows對已經訪問的文件進行緩存和預取（pre-fetch），這樣當你測試完第一個算法，再用第二個算法的時候，就會發現秒級完成。所以你每測試出一個結果，就應該重啟電腦。。。
未知問題
如果你發現有什么bug，麻煩告訴我，我喜歡學習:)
改進
1.2010-7-16 v1；
2.2010-7-14 v2 添加了對選擇文件名/修改時間/創建時間為重復標準的支持；重構代碼，引入了基類，方便測試；
3.2010-7-14 v2.1 再次重構，并添加了對指定文件類型的支持，允許正則表達式；
4.2010-7-15 v3 增加了對多線程的支持，速度提升；
5.2010-7-16 v3.1 修正了從v2開始出現的重復測試問題；
6.2010-7-16 v4 僅應用多線程于文件查找；
7.2010-7-16 v5 動態支持多磁盤多線程提速；
8.2010-7-16 v5.1 增加了對使用文件屬性過濾的支持，并重構了部分代碼，并修正了動態多磁盤的判斷；
9.2010-7-19 v5.2 允許單純地查找匹配大小/文件名而不計算哈希值，增加了對文件名過濾的支持，并重構了部分代碼，加入了對動態多磁盤的容錯；
10.2010-7-20 v6 實現了網格搜索
10.2010-7-20 v6.1 添加了對文件發現的支持，如果遠程計算機沒有發布可訪問的目錄，則不進行搜索
10.2010-7-20 v6.2 添加了對刪除重復文件的支持，并改造了用戶訪問機制
11.2010-7-21 v6.3 添加了對快速存取哈希值的支持；
12.2010-7-21 v6.4 修正了快速存取哈希值的異常問題；
13.2010-7-23 v6.6 添加了對HTTP協議、內容匹配、全文索引的支持；
14.2010-7-26 v6.7 添加了對HTTP、TCP壓縮傳輸的支持；
15.2010-7-28 v6.8 添加了NTFS USN Journal技術，檢索文件信息速度提升10倍，源代碼：http://filio.codeplex.com/SourceControl/changeset/changes/74232
16.2010-7-31 v6.9 添加了對基于角色的訪問控制（RBAC）的權限管理；
17.2010-8-11 v7.0 添加了對協議提供者模式的支持；
TODO
1.目前來看，改進速度的辦法是多線程了，多個線程獲取目錄文件，然后多個線程對文件列表進行哈希獲取。 在V3中添加了對多線程的支持；
2.添加對分布式（互聯網上的機器）的支持；在v6中添加了對網格搜索的支持；
3.添加對刪除文件的支持； 在v6.1中添加了對刪除文件的支持；
4.文件內容哈希值存儲，以便以后快速獲取（同時記錄文件名、大小、修改時間和哈希值，任一不匹配則認為文件改變了）在v6.3中實現了哈希值快速存取
5.添加對HTTP協議的支持；在v6.6中實現了對HTTP協議的支持
6.添加對搜索文件內容的支持：完全匹配、全文索引；在v6.6中添加了對文件內容匹配、全文索引的支持；
7.添加對lucene.net和hubbledotnet的支持；
8.添加對緩存的壓縮支持；在V6.6添加了對緩存壓縮的支持；
9.添加對網絡傳輸(HTTP/TCP)的壓縮支持；在v6.7添加了對網絡壓縮傳輸的支持；
10.添加對文件同步的支持：chunck/index/count，斷點續傳
11.添加對基于角色的訪問控制（RBAC）；在v6.9中添加了對其的支持；
12.如果檢索互聯網上的計算機，如果指定搜索目錄存在大量的文件，則返回結果可能會因為太大而造成網絡超時等問題；
13.添加對HTTP/TCP的SSL連接的支持；
14.添加對NTFS的USNJournal支持，可以比普通的檢索文件信息(Directory.GetFiles)快10倍。。。 在v6.8中添加了對其的支持
代碼下載
點擊這里下載：Filio.zip
項目地址
本項目已經在http://filio.codeplex.com/ 開源
浙公網安備 33010602011771號