什么是允许两个根路径之间有效同步的合理数据结构？

Question

我正在开发一个涉及维护两个本地目录之间一致性的应用程序。具体来说，目录应该是相同的，除了其中一个目录中的所有文件都以某种特定方式修改（这部分对我的问题并不重要）。

在运行时，我的应用程序运行两个进程，侦听每个路径下发生的更改，并执行相关操作以在必要时使它们恢复同步。

就我的具体问题而言：我正在寻求有关启动应用程序时的欺骗情况的建议。此时，每个进程都需要检查它正在查找的路径下的所有文件/文件夹，以查看在应用程序未运行时是否有任何更改。 （让我们假设操作系统无法通知应用程序在关闭时发生的任何事情，因此需要直接检查每个文件/文件夹。）

每个进程都可以访问（并维护）一个持久数据结构其指定路径下的所有文件/文件夹。我认为每个文件和文件夹的数据结构中应包含以下内容：

• 文件/文件夹名称；
• 文件哈希（CRC32）；
• 文件/文件夹最后的 mod 数据；和
• 文件/文件夹大小。

这些信息显然有助于检查文件/文件夹的任何更改，但是存储它们的最佳方式是什么？

在我看来，处理应用程序启动情况的一种明智方法是让每个进程递归扫描其指定路径下的所有文件/文件夹，并将扫描的每个文件的元数据与其数据结构中存储的元数据进行比较。然后，进程还应该迭代数据结构以查找已从路径中删除的内容。在此过程中可能遇到的一些情况是：

• 文件已修改（在数据结构中找到文件名，但哈希值不同）；
• 添加文件（在数据结构中未找到相同的文件名或哈希值）；
• 文件重命名（数据结构中存在具有相同哈希值的文件，但不具有相同文件名）；
• 添加了文件夹（数据结构中没有文件夹名称）；
• 文件夹已删除（数据结构中的文件夹名称，但不在路径下）；
• 文件夹已重命名（棘手）。

那么，用于此任务的最佳数据结构是什么？在我的脑海中，我正在考虑某种形式的排序关联数组，例如红黑树，它存储文件和文件夹对象。每个文件对象包含name、hash和mod-date属性，而每个文件夹 > 对象包含 name 和 children 属性，其中 children 存储另一个关联数组及其下面的所有内容。给定任意文件的路径，例如 /foo/bar/file.txt，您从根 (foo) 开始，检查 bar code> 依此类推，直到到达 file.txt 的父对象。

我能想到的另一种选择是仅仅扁平存储所有内容，这样就有一个红黑树，其中每个键都是每个文件/文件夹的完整路径，值是文件 / 文件夹对象。这可能会更快地检索，但无论如何都不可能在不迭代所有值的情况下检测重命名的文件/文件夹，这听起来很昂贵。在第一种方法中，识别重命名可能只涉及检查数据结构的一部分而不是全部。

抱歉，上述想法没有经过深思熟虑。该领域的最新技术是什么？是否有解决此类问题的常用方法？

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 和 Compare 的 Directory 实现将递归其子级。

通过比较 CRC，文件重命名相对容易。您会错过在这两个地方都发生更改并被重命名的文件。如果运行比较的时间证明存在性能问题，您可以将 CRC 字典添加到 Directory 类。

对于目录移动，如果子文件也发生了更改，那么您就会遇到逻辑模糊的情况。最好有一个用户可以针对这种情况操作的合并工具。

如果文件在两个位置都发生更改，并且发生冲突的更改，您还需要面向用户的合并策略。我认为这始终是一个好主意，只是为了让用户注意到文档没有失去连贯性。