29

前段时间我了解到rsync删除文件比许多其他工具快得多。

几天前，我在 Serverfault 上看到了这个精彩的答案，它解释了为什么rsync这么擅长删除文件。

引用该答案：

我今天重温了这一点，因为大多数文件系统以 btree 格式存储其目录结构，删除文件的顺序也很重要。执行取消链接时，需要避免重新平衡 btree。因此，我在删除发生之前添加了一个排序。

您能否解释按顺序删除文件如何防止或减少 btree 重新平衡的数量？

我希望答案能够显示删除顺序如何提高删除速度，并详细说明btree级别发生的情况。编写rsync和其他程序的人（请参阅问题中的链接）使用这些知识来创建更好的程序。我认为对于其他程序员来说，拥有这种理解以便能够编写更好的软件是很重要的。

4

5 回答 5

12

这不重要，也不是 b-tree 的问题。这只是一个巧合。

首先，这非常依赖于实现并且非常特定于 ext3。这就是为什么我说它不重要（一般用途）。否则，放置 ext3 标记或编辑摘要行。

其次，ext3 不使用b-tree 作为目录条目索引。它使用 Htree。Htree 与 b-tree 类似，但不同，不需要平衡。在fs/ext3/dir.c中搜索“htree” 。

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

曹明明等人为 OLS 2005 发表的一篇关于 ext3 的论文。建议（强调我的）：

按 inode number对 readdir() 返回的目录条目进行排序。

现在，进入 rsync。Rsync 按文件名对文件进行排序。请参阅flist.c::fsort()、flist.c::file_compare()和flist.c::f_name_cmp()。

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

于 2013-08-18T15:30:49.673 回答
9

让我们假设您发布的答案是正确的，并且给定的文件系统确实将内容存储在平衡树中。平衡树是一项非常昂贵的操作。保持树“部分”平衡非常简单，因为当您允许树稍微不平衡时，您只需担心在插入/删除点周围移动事物。然而，当谈到完全平衡的树时，当你移除一个给定的节点时，你可能会突然发现，这个节点的子节点可能属于树的完全相反的一侧，或者对侧的一个子节点已经成为根节点，并且它的所有子节点都需要在树上向上旋转。这需要您进行一连串的旋转，或者将所有项目放入一个数组中并重新创建树。 

            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

在这种情况下实现最优移除会更容易，因为我们可以利用我们对事物如何排序的知识。在任何一种情况下都有可能，实际上两者都是相同的，在这种情况下，逻辑更容易理解，因为对于给定的场景，排序更人性化。在任何一种情况下，按顺序都被定义为“首先删除最远的叶子”，在这种情况下，最远的叶子恰好也是最小的数字，我们可以利用这一事实使它更小更优化，但对于所展示的文件系统示例，这一事实不一定正确（尽管可能如此）。

于 2013-07-30T19:44:46.663 回答
2

如果您按顺序删除文件，我不相信 B-tree 重新平衡的数量会发生显着变化。但是，我确实相信，如果您这样做，对外部存储的不同搜索次数将会大大减少。在任何时候，B 树中唯一需要访问的节点将是树的最右边界，而在随机顺序下，每个文件以相同的概率访问 B 树中的每个叶块。

于 2013-07-31T03:41:58.087 回答
1

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

删除时有很多方法，根据方法的不同，它在时间和重新平衡树的需要方面可能更有效。您还必须考虑节点的大小，因为节点可以存储的键数量会影响重新平衡树的需要。较大的节点大小只会对节点内的键重新排序，但较小的节点可能会使树重新平衡很多次。

理解这一点的一个很好的资源是著名的 CLR (Thomas Cormen) 书“算法简介”。

于 2013-08-08T17:56:16.883 回答
0

在托管大量目录的存储系统上，缓冲区缓存将处于压力之下，并且缓冲区可能会被回收。因此，如果您有按时间间隔的删除，那么在删除之间将 btree 重新返回到缓冲区缓存中的磁盘读取次数可能会很高。

如果您对要删除的文件进行排序，则实际上是在延迟删除并将它们捆绑在一起。这可能会产生每个 btree 分页块的更多删除的副作用。如果有统计数据可以说明两次实验之间的缓冲区缓存命中是多少，它可能会判断这个 hypo 是否错误。

但是，如果在删除过程中缓冲区缓存没有压力，那么 btree 块可能会留在核心中，那么我的假设就不是一个有效的假设。

于 2013-08-13T02:57:25.097 回答