Почему важно удалять файлы для ускорения их удаления?

Ответ 1

Это не важно, ни b-tree проблема. Это просто совпадение.

Прежде всего, это очень зависит от реализации и очень специфично для ext3. Вот почему я сказал, что это не важно (для общего использования). В противном случае поместите тег ext3 или отредактируйте итоговую строку.

Во-вторых, ext3 делает not использование b-tree для индекса записи каталога. Он использует Htree. Htree похож на b-дерево, но отличается и не требует балансировки. Поиск "htree" в fs/ext3/dir.c.

Из-за индекса на основе htree: a) ext3 имеет более быстрый поиск по сравнению с ext2, но b) readdir() возвращает записи в порядке значения хэша. Порядок хэш-значений является случайным относительно времени создания файла или физического расположения данных. Как мы все знаем, произвольный доступ намного медленнее, чем последовательный доступ на вращающемся носителе.

Статья о ext3, опубликованная для OLS 2005 от Mingming Cao и др., предлагает (акцент мой):

для сортировки записей каталога, возвращаемых readdir() по номеру inode.

Теперь, на rsync. Rsync сортирует файлы по имени файла. См. flist.c:: fsort(), flist.c:: file_compare() и flist.c:: f_name_cmp().

Я не тестировал следующую гипотезу, потому что у меня нет наборов данных, из которых @MIfe получил 43 секунды. но я предполагаю, что сортировка по имени намного ближе к оптимальному порядку, сравниваемому с случайным порядком, возвращаемым readdir(). Вот почему вы видели гораздо более быстрый результат с помощью rsync на ext3. Что делать, если вы генерируете 1000000 файлов со случайными именами файлов, а затем делите их с помощью rsync? Вы видите тот же результат?

Ответ 2

Предположим, что ответ, который вы опубликовали, является правильным и что данная файловая система действительно хранит вещи в сбалансированном дереве. Балансировка дерева - очень дорогостоящая операция. Сохранение "частично" сбалансированного дерева довольно просто, потому что, когда вы допускаете слабое дисбаланс дерева, вы беспокоитесь только о перемещении вещей вокруг точки вставки/удаления. Однако, говоря о полностью сбалансированных деревьях, когда вы удаляете данный node, вы можете обнаружить, что внезапно дети этого node могут принадлежать на полной противоположной стороне дерева или дочерний элемент node на противоположной стороной стал корень node, и все его дети должны быть повернуты вверх по дереву. Это требует от вас либо длинной серии поворотов, либо размещения всех элементов в массиве и повторного создания дерева.

            5
    3               7
2       4       6       8

теперь удалите 7, легко ли?

            5
    3               8
2       4       6       

Теперь удалите 6, все еще легко, да...?

            5
    3               8
2       4       

Теперь удалите 8, uh oh

            5
    3               
2       4

Получение этого дерева для правильной сбалансированной формы, например:

        4
    3       5
2

Это довольно дорого, по сравнению, по крайней мере, с другими изъятиями, которые мы сделали, и экспоненциально хуже по мере увеличения глубины нашего дерева. Мы могли бы сделать это намного (экспоненциально) быстрее, удалив 2 и 4, прежде чем удалить 8. В частности, если наше дерево было более трех уровней в глубину.

Без сортировки удаление в среднем равно O (K * log_I (N) ^ 2). N, представляющее общее количество элементов, а K - номер, который должен быть удален, я число детей, данное node разрешено, log_I (N), а затем глубина, и для каждого уровня глубины мы увеличиваем количество операций квадратично.

Удаление с помощью некоторой справки по порядку в среднем равно O (K * log_I (N)), хотя иногда упорядочение не может вам помочь, и вы застреваете, удаляя что-то, что потребует перебалансировки. Тем не менее, минимизация этого оптимальна.

ИЗМЕНИТЬ:

Другая возможная схема упорядочения деревьев:

            8
    6               7   
1       2       3       4

Достижение оптимального удаления в этом случае было бы проще, потому что мы могли бы воспользоваться нашими знаниями о том, как вещи сортируются. В любой ситуации это возможно, и на самом деле оба идентичны, и в этом случае логика немного проще понять, потому что упорядочение более человечно дружественно для данного сценария. В любом случае in-order определяется как "сначала удалять самый дальний лист", в этом случае бывает так, что самые дальние листья также являются наименьшими числами, что мы могли бы использовать, чтобы сделать его еще немного более оптимальным, но этот факт не всегда справедлив для представленного примера файловой системы (хотя это может быть).

Ответ 3

Я не уверен, что количество перебалансировки B-дерева значительно меняется, если вы удаляете файлы в порядке. Однако я верю, что количество различных попыток внешнего хранилища будет значительно меньше, если вы это сделаете. В любое время единственными узлами в B-дереве, которые нужно посетить, тогда будет крайняя правая граница дерева, тогда как при случайном порядке каждый листовой блок в дереве B посещается с равной вероятностью для каждого файла.

Ответ 4

Ребалансировка для B-деревьев дешевле, чем реализации B-Tree +, поэтому большинство используемых ими файловых систем и баз данных используют их.

Существует множество подходов при удалении, в зависимости от подхода, это может быть более эффективным с точки зрения времени и необходимостью балансировки дерева. Вы также должны будете рассмотреть размер node, так как количество ключей, которые может хранить node, повлияет на необходимость перебалансировки дерева. Большой размер node будет просто переупорядочивать ключи внутри node, но маленький, вероятно, будет многократно перебалансировать дерево.

Огромным ресурсом для понимания этого является знаменитая книга CLR (Thomas Cormen) "Введение в алгоритмы".

Ответ 5

В системах хранения, где размещаются огромные каталоги, буферный кеш будет находиться под напряжением, а буферы могут быть переработаны. Таким образом, если вы удаляете разнесенные по времени, тогда число дисков, которые читаются для того, чтобы вернуть btree в ядро ​​в буферный кеш, между удалениями, может быть высоким.

Если вы сортируете файлы, которые нужно удалить, эффективно вы откладываете удаление и группировку. Это может иметь побочный эффект от большего количества удалений на каждый блок btree. Если есть статистика, чтобы сказать, что попадает в буферный кеш между двумя экспериментами, он может определить, является ли эта гипотеза неправильной или нет.

Но, если в процессе удаления нет стресса в буферном кеше, тогда блоки btree могут оставаться в ядре, а затем моя гипотеза не является допустимой.