为什么删除文件可以加快文件移除速度？

Question

不久前，我了解到 rsync 可以比许多其他工具更快地删除文件。

几天前，我发现Serverfault上的这个精彩答案解释了为什么rsync在删除文件方面表现得如此出色。

引自该答案：

今天我重新审视了这个问题，因为大多数文件系统在btree格式中存储其目录结构，删除文件的顺序也很重要。你需要避免在执行unlink时重新平衡btree。因此，在删除之前我添加了一个排序步骤。

请问如何有序地删除文件可以防止或减少btree重新平衡的次数？

---

_{我希望答案可以展示有序删除如何提高删除速度，并详细说明在btree级别发生的情况。编写rsync和其他程序的人（请参见问题中的链接）使用这些知识来创建更好的程序。我认为其他程序员理解这一点能够编写更好的软件非常重要。}

- ovgolovin

---

你的rsync链接已经失效了。这个存档链接可以使用；我是在这个相关问题中找到的。 - nh2

我现在已经对rm -r和rsync进行了基准测试。它们在包含n个文件的目录删除中，无论是在ext4还是xfs上，都显示O(n²)的性能。来自2008年的coreutils补丁声称已经修复了这个问题，并应该具有O(n)的性能。我在这里提出了一个新的错误报告。 - nh2

Answer 1

这不是重要的问题，也与B树无关。这只是一个巧合。

首先，这非常依赖于实现，并且非常特定于ext3。这就是为什么我说它对于一般使用来说并不重要。否则，请添加ext3标签或编辑摘要行。

其次，ext3使用Htree而不是B树作为目录条目索引。Htree类似于B树但又不同，不需要平衡。请在fs/ext3/dir.c中搜索“htree”。

由于基于htree的索引，a) ext3比ext2具有更快的查找速度，但b)readdir()按哈希值顺序返回条目。哈希值顺序相对于文件创建时间或数据物理布局是随机的。正如我们所知，旋转介质上的随机访问比顺序访问慢得多。

Mingming Cao等人在2005年OLS发表的一篇有关ext3的论文建议（我强调）：

通过inode编号对readdir()返回的目录条目进行排序。

现在，我们来谈谈rsync。rsync通过文件名进行排序。请参见flist.c::fsort(), flist.c::file_compare(), 和 flist.c::f_name_cmp()。

我没有测试以下假设，因为我没有从 @MIfe 获得43秒 的数据集。但我认为按名称排序比readdir()返回的随机顺序更接近最佳顺序。这就是为什么你在ext3上使用rsync时看到了更快的结果。如果你用随机文件名生成1000000个文件，然后用rsync删除它们呢？你会看到相同的结果吗？

- Yasushi Shoji

---

谢谢！有一件事我无法理解。经过排序后，我们仍然一个一个地删除文件，因此这仍然是随机访问（只是猜测）。如果这些文件被单独发送到文件系统进行删除，那么文件系统如何从按顺序获取要删除的文件中获益呢？ - ovgolovin

我认为这是顺序的，因为Linux块层在命中旋转介质之前会合并来自文件系统层的相邻请求。如你所知，unlink（2）不会清除整个文件，而是在文件系统中将它们标记为“已删除”。这些标记，包括块指针，非常接近。关键是，因为我们正在谈论非常大的目录，有大量这些标记占用了大量空间。随机访问空间不会给块层合并请求的任何机会，并且与顺序合并访问相比会导致重大开销。 - Yasushi Shoji

如果我理解正确，操作系统应该首先从目录中删除文件，然后将索引节点标记为空。这应该会导致硬盘驱动器头在这些文件夹和索引节点结构之间移动一个单独的文件。Linux是否能够批量删除多个文件，以便利用顺序索引节点排序（似乎应该先完成文件夹，然后批量更新所有这些文件的索引节点）。 - ovgolovin

据我所知，Unix/Posix/Linux系统调用被设计成简单易用。删除目录并不总是会删除其中的文件；这是因为有一种叫做“硬链接”的东西。因此，即使你拥有这样一个系统调用，它仍然需要逐个检查inode。 - Yasushi Shoji

你说得对，这只是巧合。在测试时，我按字典顺序创建了文件（file1、file2、file3），因此节点自然也按照相同的顺序排列。 - Matthew Ife

Answer 2

假设您发布的答案是正确的，并且给定的文件系统确实在平衡树中存储东西。 平衡树是一种非常昂贵的操作。 将树保持“部分”平衡相当简单，因为当您允许树稍微失衡时，您只需要担心在插入/删除点周围移动物品。 但是，当谈论完全平衡的树时，当您删除一个给定节点时，您可能会发现该节点的子项可能属于树的完全相反的一侧，或者相反侧的子节点已成为根节点，并且所有其孩子都需要向树上传递。 这要求您执行一系列长时间的旋转，或将所有项目放入数组并重新创建树。

            5
    3               7
2       4       6       8

现在移除数字7，很容易对吧？

            5
    3               8
2       4       6       

现在去掉6，还是很容易的，对吧...？

            5
    3               8
2       4       

现在移除8，哎呀

            5
    3               
2       4

将这棵树转化为正确的平衡形态，如下图所示：

        4
    3       5
2

相比我们所做过的其他移除操作，这很昂贵，并随着树深度的增加呈指数级增长。如果在删除8之前先删除2和4，则可以将此速度提高到指数级，特别是对于超过3级深度的树。

如果不进行排序，则平均需要O(K * log_I(N)^2)次删除操作。其中N代表总元素数量，K代表要删除的数量，I代表给定节点允许的子节点数量，log_I(N)表示深度，每个深度的增加会使操作次数呈二次方增长。

通过一些排序帮助，平均删除操作可达到O(K * log_I(N))。但有时无法通过排序解决问题，需要重新平衡。尽量减少此类情况最优。

编辑：

另一个可能的树排序方案：

            8
    6               7   
1       2       3       4

在这种情况下，实现最佳的删除操作会更容易，因为我们可以利用我们对事物排序方式的了解。在任何一种情况下都是可能的，实际上两种情况是相同的，只不过在这种情况下，逻辑稍微简单一些，因为所给出的场景的排序方式更加人性化。无论哪种情况，按顺序定义为“先删除最远的叶子节点”，在这种情况下，恰好最远的叶子节点也是最小的数字，这个事实可以被利用来使其更加优化，但这个事实不一定适用于所提供的文件系统示例（虽然可能适用）。

- ChrisCM

---

从我看来，删除中序会导致不平衡（例如，如果我们删除2 3 4，则需要重新平衡树）。我不明白删除中序如何有所帮助。 - ovgolovin

我选择的排序方式是为了演示平衡二叉树的工作原理，而不是展示最佳删除顺序或文件系统使用的排序方式。无论给定节点允许有多少个子节点，逻辑都是相同的，二叉（2个子节点）树在文本中最容易演示。 - MobA11y

我不在乎作者使用的排序方式，这篇文章的重点是展示重新平衡带来的痛苦，以及为什么要避免它，以及rsync如何通过这样做实现更快的性能！也就是回答问题：你能解释一下按顺序删除文件如何防止或减少B树重新平衡的次数吗？“按顺序”并不总是意味着显而易见的事情。在这种情况下，“按顺序”意味着首先处理最远的叶子节点，而不是1 < 2。 - MobA11y

相反地，我们可以在树本身上更改排序标准，使两者意思相同。 :) - MobA11y

我认为大家都清楚地知道重新平衡会导致额外的操作。问题是关于如何通过删除“按顺序”的实际方面来减少重新平衡次数。如果作者所说的“按顺序”意味着与排序顺序不同的顺序，我想知道它是什么顺序。这个问题就是关于这个的。 - ovgolovin

Answer 3

我不确定如果你按顺序删除文件，B树重新平衡的次数会显著改变。然而，我相信如果这样做，与随机删除相比，需要进行的外部存储器寻道次数将显著减少。在任何时候，只需要访问B树中极右边界的节点，而在随机删除时，每个叶子块都有相等的概率被访问。

- mcdowella

---

是的，你可能是对的。Btree在硬盘文件系统上使用的原因是它具有更快的顺序访问速度。因此，如果我们按顺序遍历这些叶子节点，结果应该会更快。另一方面，当我们从这些叶子节点中删除节点时，我们最终会进行重新平衡，以便访问另一个Btree叶子节点，即随机访问，这是缓慢的。另一方面，重新平衡将无论如何发生，但至少我们按顺序遍历叶子节点，从而减少开销。 - ovgolovin

Answer 4

重新平衡B树比B树+实现更便宜，这就是为什么大多数文件系统和数据库索引实现使用它们的原因。

删除时有许多方法，具体取决于方法，可以更有效地节省时间并减少需要重新平衡树的次数。您还需要考虑节点的大小，因为节点可以存储的键数将影响需要重新平衡树的次数。大的节点大小只会在节点内重新排序键，但较小的节点大小可能会使树重新平衡多次。

了解此内容的绝佳资源是著名的CLR（Thomas Cormen）书籍“算法导论”。

- rudygodoy

---

谢谢！我提出这个问题是因为我对这个主题非常感兴趣。我的朋友们在Twitter上转发了关于rsync快速删除的信息，并猜测它为什么如此快速（他们猜测它使用了多个线程等等）。所以这个主题对许多程序员来说确实很有趣。在StackOverflow上，我收到了许多深入细节的好答案，提供了源代码链接（例如https://dev59.com/CnTYa4cB1Zd3GeqPunGl#17845560），并且解释得比许多书籍更好（https://dev59.com/1mox5IYBdhLWcg3wFAU1#9513423）... - ovgolovin

所以我提出了这个问题，因为它可能对很多人来说都很有趣。一个展示rsync如何在文件系统级别删除东西的例子，并详细说明发生了什么的答案将使所有这些人理解，并甚至可能使他们在某种程度上成为更好的专家。对我来说，从现实生活中的例子中学习东西比使用规范的理论书籍追求它们要有趣和激励得多。 - ovgolovin

Answer 5

在托管巨大目录的存储系统上，缓冲高速缓存将承受压力并且缓冲区可能会被回收。因此，如果您按时间间隔删除，则在删除之间将需要大量磁盘读取以将B树重新加载到缓冲高速缓存中。

如果您对要删除的文件进行排序，实际上您正在延迟删除并将它们分组。这可能会导致每个分页B树块中有更多的删除操作。如果有统计数据表明两个实验之间缓冲高速缓存命中率的情况，则可以判断这一假设是正确的还是错误的。

但是，如果删除操作时缓冲高速缓存没有压力，则B树块可以保持在内存中，那么我的假设就不成立了。

- lsk