Почему важно удалять файлы, чтобы быстрее их удалять?
Некоторое время назад я узнал, что rsync удаляет файлы гораздо быстрее, чем многие другие инструменты.
Несколько дней назад я наткнулся на этот замечательный ответ на Serverfault, который объясняет, почему rsync так хорош в удалении файлов.
Цитата из этого ответа:
Я вернулся к этому сегодня, потому что большинство файловых систем хранят свои структуры каталогов в формате btree, порядок удаления файлов также важен. Нужно избегать перебалансировки btree при выполнении разрыва связи. Поэтому я добавил сортировку перед удалением.
Не могли бы вы объяснить, как удаление файлов по порядку предотвращает или уменьшает количество перебалансировок btree?
Я ожидаю, что ответ покажет, как удаление в порядке увеличения скорости удаления, с подробностями того, что происходит на btree уровень. Люди, которые написали rsync и другие программы (см. ссылки в вопросе) использовали эти знания для создания лучших программ. Я думаю, что для других программистов важно иметь это понимание, чтобы иметь возможность писать лучше.
5 ответов
Это не важно, ни B-Tree вопрос. Это просто совпадение.
Прежде всего, это очень сильно зависит от реализации и очень сильно зависит от ext3. Вот почему я сказал, что это не важно (для общего пользования). В противном случае поместите тег ext3 или отредактируйте итоговую строку.
Во-вторых, ext3 не использует b-дерево для индекса записи каталога. Он использует Htree. Htree похож на b-tree, но отличается и не требует балансировки. Поиск "htree" в fs / ext3 / dir.c.
Из-за индекса на основе htree, а) ext3 имеет более быстрый поиск по сравнению с ext2, но б) readdir() возвращает записи в порядке хеш-значений. Порядок значений хеш-функции является случайным относительно времени создания файла или физического расположения данных. Как мы все знаем, произвольный доступ намного медленнее, чем последовательный доступ на вращающемся носителе.
Статья на ext3, опубликованная для OLS 2005 Mingming Cao, et al. предлагает (выделение мое):
сортировать записи каталога, возвращаемые readdir() по номеру inode.
Теперь на rsync. Rsync сортирует файлы по имени файла. Смотрите flist.c:: fsort (), flist.c:: file_compare () и flist.c:: f_name_cmp ().
Я не проверял следующую гипотезу, потому что у меня нет наборов данных, из которых @MIfe получил 43 секунды. но я предполагаю, что сортировка по имени была намного ближе к оптимальному порядку по сравнению со случайным порядком, возвращаемым readdir(). Вот почему вы видели намного более быстрый результат с rsync на ext3. Что если вы сгенерируете 1000000 файлов со случайными именами, а затем удалите их с помощью rsync? Вы видите тот же результат?
Давайте предположим, что ответ, который вы разместили, является правильным, и что данная файловая система действительно хранит вещи в сбалансированном дереве. Балансировка дерева - очень дорогая операция. Поддержание "частично" сбалансированного дерева довольно просто, в том случае, когда вы допускаете, чтобы дерево было слегка неуравновешенным, вам нужно беспокоиться только о перемещении объектов вокруг точки вставки / удаления. Однако, когда речь идет о полностью сбалансированных деревьях, когда вы удаляете данный узел, вы можете обнаружить, что внезапно дочерние узлы этого узла могут принадлежать полностью противоположной стороне дерева, или дочерний узел на противоположной стороне стал корневым. узел, и все его дочерние элементы должны быть повернуты вверх по дереву. Это требует от вас выполнения длинных серий поворотов или размещения всех элементов в массиве и повторного создания дерева.
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
Это довольно дорого, по сравнению, по крайней мере, с другими удалениями, которые мы сделали, и экспоненциально ухудшается с увеличением глубины нашего дерева. Мы могли бы сделать это намного (экспоненциально) быстрее, удалив 2 и 4, прежде чем удалить 8. Особенно, если наше дерево было более 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
В этом случае было бы проще добиться оптимального удаления, потому что мы можем воспользоваться нашими знаниями о том, как вещи сортируются. В любой ситуации это возможно, и на самом деле обе идентичны, в этой логике немного проще понять, потому что порядок более дружественен для данного сценария. В любом случае порядок определяется как "сначала удалите самый дальний лист", в этом случае так уж получилось, что самые дальние листья также являются наименьшими числами, факт, который мы могли бы использовать, чтобы сделать его даже немного более оптимальным, но этот факт не обязательно верен для представленного примера файловой системы (хотя это может быть).
Я не уверен, что количество ребалансировки B-дерева существенно изменится, если вы удалите файлы по порядку. Однако я верю, что если вы сделаете это, количество различных обращений к внешнему хранилищу будет значительно меньше. В любое время единственными узлами в B-дереве, которые необходимо посетить, будет тогда крайняя правая граница дерева, тогда как при случайном порядке каждый листовой блок в B-дереве посещается с равной вероятностью для каждого файла.
Перебалансировка для B-Trees дешевле, чем реализация B-Tree+, поэтому большинство реализаций файловых систем и индексов баз данных используют их.
Существует много подходов при удалении, в зависимости от подхода, который может быть более эффективным с точки зрения времени и необходимости перебалансировать дерево. Вам также необходимо учитывать размер узла, так как количество ключей, которые может хранить узел, повлияет на необходимость перебалансировки дерева. Большой размер узла просто переупорядочивает ключи внутри узла, но маленький, вероятно, заставит дерево перебалансироваться много раз.
Большим ресурсом для понимания этого является знаменитая книга CLR (Томас Кормен) "Введение в алгоритмы".
В системах хранения, где размещаются огромные каталоги, буферный кеш будет находиться под нагрузкой, и буферы могут быть переработаны. Таким образом, если вы удалили разнесенные по времени удаления, то число операций чтения с диска, чтобы вернуть btree в ядро в буферный кеш, между удалениями, может быть высоким.
Если вы сортируете файлы, которые нужно удалить, вы фактически задерживаете удаление и группируете их. Это может иметь побочный эффект большего числа удалений на блок btree. Если есть статистика, указывающая, какие попадания в буферный кеш происходит между двумя экспериментами, он может сказать, является ли эта гипо неправильной или нет.
Но если при удалении нет нагрузки на буферный кеш, тогда блоки btree могут остаться в ядре, и тогда моя гипотеза не верна.