允許兩個根路徑之間高效同步的敏感數據結構是什麼？

Question

我正在研究涉及維護兩個本地目錄之間一致性的應用程序。具體來說，目錄應該是相同的，除了其中一個目錄中的所有文件都以某種特定的方式修改（這部分對我的問題並不重要）。

運行時，我的應用程序運行兩個進程，用於監聽每個路徑下發生的更改，並執行相關操作以在必要時使其恢復同步。

就我的具體問題而言：我正在尋找關於何時啓動應用程序的tricker情況的建議。此時，每個進程都需要檢查所有正在查看的路徑下的所有文件/文件夾，以查看應用程序未運行時是否有任何更改。 （讓我們假設應用程序不能在OS關閉時發生任何事情通知OS，因此將需要直接檢查每個文件/文件夾。）

每個進程將有權訪問（並維護）一個所有文件/文件夾在其指定路徑下的持久數據結構。我在考慮在每個文件和文件夾的數據結構中應該包含以下內容：

• 文件/文件夾名稱;
• 文件哈希（CRC32）;
• 文件/文件夾最後的mod數據;和
• 文件/文件夾大小。

這些信息顯然有助於檢查文件/文件夾的任何更改，但是存儲它們的最佳方式是什麼？

在我看來，處理應用程序啓動情況的一種明智方式是每個進程遞歸掃描指定路徑下的所有文件/文件夾，並將掃描的每個文件的元數據與存儲在其數據結構。然後，這些進程還應該遍歷數據結構以查找已從路徑中刪除的內容。在這個過程中可能遇到的一些情況是：

• 修改文件（在數據結構中找到的文件名，但散列不同）;
• 添加文件（在數據結構中沒有相同的文件名或哈希）;
• 重命名文件（數據結構中存在具有相同散列的文件，但不具有相同的文件名）;
• 文件夾已添加（數據結構中沒有文件夾名稱）;
• 文件夾已刪除（數據結構中的文件夾名稱，但不在路徑下）;
• 文件夾改名（棘手的一個）。

那麼，什麼是最好的數據結構用於這項任務？在我的腦海中，我正在考慮某種形式的排序關聯數組，例如紅黑樹，它存儲了file和folder對象。每個file對象包含name,hash和mod-date屬性，而每個folder對象包含name和children屬性，其中children存儲另一個關聯數組，其中包含所有內容。給定到任意文件的路徑，例如/foo/bar/file.txt，您從根（foo）開始，檢查bar依此類推，直到您到達file.txt的父對象。

我能想到的另一種方法是隻存儲一切斷然，使得在一個紅黑樹，其中每個關鍵是每個文件/文件夾的完整路徑，並將該值是file/folder對象。這對於檢索來說可能會更快，但是無論如何都無法遍歷所有值來檢測重命名的文件/文件夾，這聽起來很昂貴。在第一種方法中，識別重命名的情況可能只涉及檢查數據結構的一部分而不是全部。

對不起，上述想法並不是非常深思熟慮。這個領域的藝術狀況如何？對於這些類型的問題，是否有任何行之有效的方法？

Answer 1

您正在爲一個文件系統建模，因此使用分層數據結構是很自然的。畢竟，您不需要將dir1 \ dir2 \ foo.txt中的文件與dir3 \ bar.txt進行比較，對不對？您沒有提及目錄之間的文件移動，因爲您正在跟蹤的內容。

因此，數據結構可以是：

interface IFSEntry { 
    string name 
    datetime creationDate 
    pure virtual bool Compare(IFSEntry other) 
    pure virtual void UpdateFrom(IFSEntry other) 
    pure virtual bool WasRenamed(Dictionary<string,IFSEntry> possibleOriginals, out string oldName) 
    ... 
} 

class File : IFSEntry { 
    ... 
} 

class Directory : IFSEntry { 
    private Dictionary<string,IFSEntry> children; 
    ... 
} 

UpdateFrom的目錄實現和比較會遞歸下降自己的孩子。

比較CRC的文件重命名會相對容易。你會錯過在兩個地方發生變化並被重命名的文件。如果運行比較的時間證明性能問題，則可以將CRC字典添加到Directory類。

對於目錄移動，如果子文件也改變了，那麼你就有了模糊邏輯的情況。最好有一個合併工具，用戶可以在這種情況下操作。

如果兩個位置的文件都發生更改，如果發生衝突的更改，還需要一個面向用戶的合併策略。我認爲這總是一個好主意，只是爲了讓用戶注意文檔不失一致性。