algorithm - 当应用程序未运行时，Dropbox 用于识别本地更改的文件/文件夹列表的算法是什么？

Question

我知道当应用程序运行时，我们可以使用一些操作系统事件来识别文件系统的变化。我只是想知道应用程序何时未运行，如果我对文件系统进行了大量更改，例如添加/修改/删除/重命名几个文件和文件夹，Dropbox 使用什么算法来识别这些更改。我能想到的一件事是，通过将文件系统上文件的最后修改时间与应用程序运行时的 LMT 存储值进行比较。在这种情况下，无论如何我们都必须遍历所有文件。但是，如果我们重命名，LMT 不会改变。只是想看看有没有更好的方法，因为依赖 LMT 有其自身的问题？

有什么意见吗？

Answer 1

我不知道 Dropbox 是不是这样处理的，但这里有一个可能有用的策略:

您有一个由 Dropbox 处理的根目录。如果我是 Dropbox，我会为服务器上的每个文件保留哈希值。从根开始，应用程序将扫描文件树(目录 + 文件)并计算每个文件的哈希值。

扫描将导致双索引哈希表。每个文件和目录都将使用其相对路径(从根 Dropbox 目录)编制索引。将使用每个文件的哈希值创建第二个索引。

现在，应用程序已经扫描并建立了双索引哈希表。然后服务器将发送元组(相对路径、文件的哈希值)。让 (f, h) 成为这样一个文件元组:

1. 应用程序将尝试使用 f 通过路径索引获取文件:
   1. 如果有结果，比较哈希值。如果不匹配，更新远程服务器上的文件
   2. 如果没有结果，文件可能已被删除或移动/重命名。然后，该应用程序尝试使用 h 通过哈希索引获取文件:如果匹配，则意味着该文件仍然存在，只是位于不同的路径下(因此移动或重命名)。应用程序发送信息，文件在服务器上被适本地移动/重命名。
2. 使用散列或路径均未找到该文件。它已从 Dropbox 文件树中删除:我们在服务器上相应地删除它。

请注意，此策略需要一个同步机制来了解，当遇到匹配项时，文件是否必须在客户端或服务器上更新。这可以通过存储 Dropbox(在客户端和服务器上)最后一次运行更新的时间以及谁执行了最后一次更新(在服务器上)来实现。