LINUX.ORG.RU

Пишу оффлайн дефрагментатор reiserfs

 ,


8

9

Собственно, уже написал.

На данный момент он дорос до версии v0.2.2 и в нём реализовано всё, что я собирался реализовывать. Код здесь: https://github.com/i-rinat/reiserfs-defrag/archive/v0.2.2.tar.gz

В плане сохранности данных реализовано журналирование как метаданных, так и самих данных (нужно включить, указав параметр командной строки). Сама схема журналирования похожа на data=ordered в ext3/4, когда сначала пишутся данные, а только потом происходит обновление метаданных. Актуальные данные никогда не переписываются на месте, всегда происходит копирование на пустое место. Это снижает производительность, но значительно снижает вероятность повреждения. Собственно, сейчас повреждения возможны только если диск сойдёт с ума и начнёт писать куда не просили. По крайней мере, мне нравится так думать.

В составе есть краткая документация.

В далёком будущем появится версия v0.3, в которой ожидаются убавление тормозов в режиме tree-through и улучшение производительности для больших директорий.

★★★★★

Последнее исправление: i-rinat (всего исправлений: 3)

Да, вопрос Ищу алгоритм дефрагментации снова актуален.

у столпов K&R в старых изданиях был алгоритм оценки уровня фрагментации ФС и (если память не изменяет) даже простая дефрагментация. Точнее неподскажу :( Ну очень давно это было..алгоритм приводился так как использовал мало оперативки в работе (винты были мааленькие, но памяти было ещё меньше).

зы: а вообще классика дефрагментации *nix - dump+restore.

ззы: именно поэтому всяческие home spool и прочие tmp run log, высаживались в отдельные ФС - ограничивались области где происходит фрагментация. То есть основная система было де-факто нефрагментирована (практически read-only), а все прочее можно либо очистить/пересоздать или прогнать через бекап.

MKuznetsov ★★★★★
()

GiB

МиБ

дефрагментатор reiserfs

Дамы и господа! Перед вами экспериментальное подтверждение того, что использование бибикающих приставок вместо человеческих - симптом тяжелых проблем с головой.

anonymous
()
Ответ на: комментарий от anonymous

А я тебя ждал. Спасибо, что выразил своё мнение. Ой, я ещё и ё использую. Прокомментируй и это, пожалуйста.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от MKuznetsov

был алгоритм оценки уровня фрагментации ФС

А разве там не про аллокатор памяти? Редакций две, и навскидку я там не нашёл похожего.

использовал мало оперативки в работе

тогда, скорее всего, он не был слишком хитрым. Просто собирать все файлы подряд — так я уже реализовал.

а вообще классика дефрагментации *nix - dump+restore.

Это потому что других вариантов нет. Если бы дефрагментаторы были, и было с чем сравнивать, но всё равно все бы делали dump-restore, я бы поверил. Вот для ext2 был оффлайновый, но он был простой как пробка, и это приводило к быстрому росту фрагментации после использования. Если бы авторы сделали более продвинутый способ размещения файлов (по примеру аллокатора из драйвера ext2), да ещё и с учётом уже последовательно размещённых файлов, время на запуск дефрагментатора было бы значительно меньше dump-restore, и использовали бы его.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

А разве там не про аллокатор памяти? Редакций две, и навскидку я там не нашёл похожего.

у КР в библиографии более чем одна книга :)

сделали более продвинутый способ размещения файлов (по примеру аллокатора из драйвера ext2)

Эээ..imho Простейшая дефрагментация подразумевает проход по дереву и испльзование алгоритма аллокатора ФС. Как-бы эмуляция dump+restore: по дереву ищется очередной блок для переноса, аллокатором выбирается ему место, если место занято то блоки меняются местами, если не занято то блок копируется.

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Простейшая дефрагментация подразумевает проход по дереву и испльзование алгоритма аллокатора ФС

Так дефрагментация может никогда и не закончиться. Сейчас у дефрагментатора ext4 такая проблема — он двигает только те файлы, которые фрагментированы. А в случае

a#b#c#d#e#f#g#h#i#j#k#l#m#n####........
где #, a, b, c, ... — отдельные разные файлы, а . — свободное место, файл # никогда не будет дефрагментирован.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Так дефрагментация может никогда и не закончиться

с чего бы ? если в ФС не разрушена логика и не образовались циклы - проход по дереву закончится, все блоки будут перенесены на свои новые места. Да, вид ФС примет такой, как будто бы её восстановили из бекапа. (то есть небудет gap-ов которые возможно продлевают жизнь rfs) Да, времени это занимает (значительно) больше чем просто бекап+рестор за счёт того что надо учитывать ссылки и просто так перенос/swap блока не сделаеш.

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

Я запутался и уже ничего не понимаю.

с чего бы ? если в ФС не разрушена логика и не образовались циклы - проход по дереву закончится, все блоки будут перенесены на свои новые места.

Мне просто непонятно, как это будет работать. И чем это лучше, что есть сейчас.

Да, времени это занимает (значительно) больше чем просто бекап+рестор

Сейчас я двигаю блоки вообще только один раз. На паре тестовых разделов (первый — обычно заполненный раздел и второй — искусственно перемешанный, с жуткой фрагментацией) в худшем случае оставалось 11 блоков, перенос которых образует цикл. Последние замеры показали дефрагментацию на месте в 7.9 МБ/сек (полезные данные), а копирование раздела два раза (оптимистичная оценка dump-restore) в 8.7 МБ/сек.

Вот ещё бы не двигать попусту уже дефрагментированные файлы.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Мне просто непонятно, как это будет работать.

Это элементарный алгоритм «в-лоб»: выбрали очередной блок, выяснили куда его хочется положить, если место сейчас занято то swap, если нет то move. Так как выборка следует обходу дерева и охватывает все занятые блоки ФС то она гарантированно заканчивается.

И чем это лучше, что есть сейчас.

а это наверное вам лучше знать :) вы более в курсе того «что сейчас». Зато есть простор для оптимизаций: за счёт выборки перемещаемого блока, за счёт выбора места расположения, отказа от некотрых перемещений, кеша swap-блоков..в конце концов можно просто сгенерять множество пар(K-N) (откуда-куда) и запрягши теорию графов и паросочетаний получить оптимальную последовательность переносов блоков. Кстати последний вариант более unix-вейный: одна тулза оценивает фрагментацию и генерирует стратегию, другая оптимизирует по критериям (время/память/переносы по диску),а третья уже исполняет напрягая железки на все 100

MKuznetsov ★★★★★
()
Ответ на: комментарий от MKuznetsov

можно просто сгенерять множество пар(K-N) (откуда-куда) и запрягши теорию графов и паросочетаний получить оптимальную последовательность переносов блоков

Так уже. Но запрягать теорию графов не пришлось, так как в полученном графе нет крупных циклов. Максимальный, который я увидел — 11 узлов.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от juk4windows

допилите дефрагментатор для ext4 лучше!!!

Он работает. Что в нём пилить?

GUI для него и всё такое.

Чтоб с квадратиками? Так есть уже смотрелка. Правда она не умеет следить за текущими операциями, но это в планах.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от Eddy_Em

А смысл?

Считаю, что этот вопрос должен быть запрещён к употреблению, наравне с «и чо?».

А смысл?

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

Ну и просто хочется. Когда я доделаю журналирование операций, реализую инкрементальный алгоритм, научу не потреблять немереное количество памяти и добавлю возможность вытаскивать произвольные файлы в начало раздела, я прогоню программу на целевом девайсе, успокоюсь и положу код на полку.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Чтоб с квадратиками? Так есть уже смотрелка. Правда она не умеет следить за текущими операциями, но это в планах.

ага! :)

juk4windows
()

+ feature request:

реализация prefetch: выкладывание файлов на диске *последовательно* согласно порядку их чтения во время загрузки системы для ускорения процесса запуска.

juk4windows
()
Ответ на: комментарий от juk4windows

... для минимизации seek (heads repositioning) операций винчестера, ибо они достаточно много времени просят.

juk4windows
()
Ответ на: комментарий от juk4windows

реализация prefetch: выкладывание файлов на диске *последовательно* согласно порядку их чтения во время загрузки системы для ускорения процесса запуска.

... и добавлю возможность вытаскивать произвольные файлы в начало раздела ...

Я уже думал над этим, так что уже в процессе. Но только для reiserfs, разумеется.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

ЖалЬко, а в дефрагментатор для ext4 это не прилепите? Я чувствую, что вы отличный системный программист.

Кстати, для вас есть супер простые задачки:

https://bugzilla.kernel.org/show_bug.cgi?id=15875

https://bugzilla.kernel.org/show_bug.cgi?id=45571

а вот это вы точно не родите (попыток реализовать это было штук пять - ооооочень сложная проблема) - но вдруг :)

https://bugzilla.kernel.org/show_bug.cgi?id=14505

juk4windows
()
Ответ на: комментарий от i-rinat

Я наблюдаю значительное понижение скорости работы … со временем

Хм, странно: я ничего подобного не наблюдал.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от juk4windows

а в дефрагментатор для ext4 это не прилепите?

Нет, да и зачем дублировать http://e4rat.sourceforge.net/

Кстати, для вас есть супер простые задачки

Спасибо за задачи, но у меня уже есть, чем заняться.

а вот это вы точно не родите

Окей.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от Manhunt

Вот тебе еще идей

По ходу дела мне пришлось разбираться в устройстве ФС. Ну так вот, большая часть этого SMART Placement реализуется автоматически, за счёт устройства B+-дерева. Ключи файлов в одной директории отличаются друг от друга слабо. Ключи данных файла и ключи inode отличаются вообще чуть-чуть. Аллокатор старается класть файлы в порядке, диктуемым ключами. А я вообще тупо выкладываю подряд. Так что в этом плане уже всё круто.

Но так вообще спасибо, идеи здравые.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Там соль в том, чтобы сложить редко модифицируемые файлы (последнее изменение > 60 дней) отдельно от часто модифицируемых (последнее изменение < 30 дней). Область с файлами первого сорта почти не изменяется после начальной дефрагментации: файлы единожды дефрагментированы и плотно уложены рядом друг с другом. Её практически не приходится трогать при повторных запусках дефрагментатора - этот кусок диска и так всегда в порядке.

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

Manhunt ★★★★★
()
Последнее исправление: Manhunt (всего исправлений: 1)
Ответ на: комментарий от Manhunt

Это тоже хорошо, но у меня проблемы другого рода. Мне не хватает понимания на средних уровнях. Точнее, я не могу соединить высокоуровневое «произвести дефрагментацию» в низкоуровневое «переместить блок из позиции A в позицию B, с сохранением корректности ссылок». Последнее я реализовал, общее понимание есть, но все мысли нечёткие.

Допустим у нас есть данные о всех файлах. В силу специфики ФС, файлы почти никогда не будут занимать один экстент, без дырок. Значит нужно определиться с метрикой, по которой определять, нужно делать что-то с файлом или стоит оставить его в покое. Если двигать его, то куда? Свободных мест может не оказаться. Выметать соседей? А если они все нефрагментированы, значит выметать надо не их, а обрабатываемый файл? По какому критерию делать выбор? Не получится ли, что рекурсивные вызовы для передвижения соседей замкнутся и тупо переполнится стек?

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

По визуальному наблюдению за работой виндовых дефрагментаторов (не требующих отмонтирования диска, кстати), в голову приходит следующий алгоритм:
1. Есть курсор, который движется от начала диска к концу. Всё, что лежит до курсора - уже дефрагментировано. Всё что лежит после курсора - подлежит дефрагментации.
2. Выбираем очередной файл, который хотели бы дефрагментировать. Выбор определяется отдельной эвристикой, с учетом группировки по директориям, по частоизменяемости, с учетом допустимого количества фрагментов-на-файл и доступного сразу за курсором свободного места.
3. Сразу за курсором расчищаем место под наш файл, выметая всех кто там оказался куда-нибудь в сторонку (не важно, куда именно).
4. Перемещаем файл на расчищенное место и сдвигаем курсор за конец файла.
5. Если сразу за курсором идет небольшой кусочек свободного места и не-фрагментированный файл, то сдвигаем курсор за этот файл.

Manhunt ★★★★★
()
Последнее исправление: Manhunt (всего исправлений: 1)
Ответ на: комментарий от Manhunt

Перед собственно дефрагментацией, можно было бы смоделировать ход этого процесса, и на модели подобрать такие действия шагов 2 и 5, которые в конечном итоге потребуют наименьшего перемещения данных на диске. Чтобы избежать комбинаторного взрыва, перебор придется ограничить очень небольшой глубиной — но даже в таком виде это могло бы дать заметный прирост в скорости.

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

заметный прирост в скорости

Имелось ввиду: прирост в скорости дефрагментации.

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

Ага, я так и сделал, с курсором и составлением карты переносов. В defrag.cpp есть реализация (simpleDefrag), занимает порядка 20 строк.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от Manhunt

подобрать такие действия шагов 2 и 5, которые в конечном итоге потребуют наименьшего перемещения данных на диске.

первый вариант двигал только то, что можно подвинуть так, чтоб уж сразу на нужное место. После первого перемещения открывались новые ходы, после них следующие и так далее. Каждый раз примерно по 22% от всех необходимых. (С математикой я не дружу, и возможно это очевидный факт, но мне показалось это интересным.) Каждый блок переносится один раз.

А ещё выяснилось, что вариант с предварительной очисткой целевой области работает быстрее, видимо за счёт локализации части чтений и записей с диска. Но при этом блоки двигаются не минимальное число раз, чуть больше. Сколько именно, не оценивал.

i-rinat ★★★★★
() автор топика

Добавил кеш чтения. До этого больше 80% запросов read читали блоки дерева. Работать стало чуть быстрее, но не на много.

i-rinat ★★★★★
() автор топика

Добавил журналирование. Транзакции маленькие, на каждую вызывается fdatasync, так что медленно (у меня в 11 раз медленнее стало, 66 минут против 6). К тому же блоки данных тоже попадают в журнал. Зато есть надежда, что прерванный посередине, дефраг уже не испортит файловую систему, хотя я этого не проверял.

Теперь при запуске в суперблоке отмечается, что ФС грязная, чтобы fsck или монтирование проигрывало транзакции.

Приглашаю тестеров :)

https://github.com/i-rinat/reiserfs-defrag/tarball/journaling

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Добавил склеивание транзакций и возможность исключить из журналирования блоки данных. В этом случае данные всё равно отправляются на запись до изменения метаданных, так что в случае аварийного прерывания работы данные и структуры не теряются. Следующее монтирование или fsck просто проиграют последние транзакции и ФС вернётся в непротиворечивое состояние.

Скорость работы вернулась к тому же значению, какое было без журналирования: 5-6 минут на 3-х гиговый раздел.

https://github.com/i-rinat/reiserfs-defrag/tarball/journaling-merge

i-rinat ★★★★★
() автор топика

tag: tree-through

Убрал квадратичную потребление процессорного времени, на 120-гиговом стало работать почти вдвое быстрее. Но осталась квадратичность за счёт того, что шальные блоки вычёсываются вниз. С каждым заходом их всё больше. Если убрать и это, может стать до 5 раз быстрее, уложится в 60 минут.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Он работает. Что в нём пилить?

Он так работает, что им стрёмно пользоваться. Бывает (довольно часто), что после дефрагментации до перемонтирования FS исчезает свободное пространство. Тьфу-тьфу-тьфу, данные не пропадали, но всё равно стрёмно. Лучше уж на XFS торрентопомойку подержать.

KRoN73 ★★★★★
()
Ответ на: комментарий от KRoN73

Бывает (довольно часто), что после дефрагментации до перемонтирования FS исчезает свободное пространство. Тьфу-тьфу-тьфу, данные не пропадали, но всё равно стрёмно.

Данные не теряет, что ещё нужно? :) Ну и я не смогу его пилить, ибо оно online.

В составе e4rat есть какие-то патчи для большего контроля за тем, где файлы размещаются. Как только они в ядро попадут, начнут появляться умные дефрагментаторы, с очисткой места и прочее.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Данные не теряет, что ещё нужно? :)

С таким поведением — оно странно. Тем более, что не раз уже терял данные на записи ext4 заполненной на 100%: Ext4 такая ext4 (комментарий)

Странная какая-то ФС. За десятки машинолет с reisrefs, xfs, ntfs — такого не было. Даже fat32 глючит только при нештатных отказах, чтобы что-то ломалось при обычной работе — не сталкивался. А вот сервер на ext3 у меня однажды умер безвозвратно (ФС не восстановилась) без какой-либо посторонней симптоматики, просто при работе. Так что, может, у ext4 это генетическое? Не скажу, что такое поведение у неё частое, работа с ней у меня тоже уже за десяток машинолет длится, а сбои — единичные. Но факт их наличия смущает.

KRoN73 ★★★★★
()
Ответ на: комментарий от MKuznetsov

В swap? У вас дефраг получится слоупоснее вендузового.

anonymous
()
Ответ на: комментарий от KRoN73

У меня тоже с ext3 и xfs проблемы были (полный крах раздела при аварийном отключении без отмонтирования). Кстати, один раз и с fat32 было (правда, было это очень давно), но было не смертельно: файлы получилось восстановить.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

полный крах раздела при аварийном отключении без отмонтирования

Это разговор особый. Тут меня не подводили ни разу только reiserfs и ntfs. У всех остальных хоть какие-то неприятность, но случались. Но это понятно и избежать, по крайней мере, понятно как.

Меня больше беспокоят сбои, хоть и при нештатных ситуациях (переполнение диска), но при нормально работающих железе и ОС. Ни зависов, от отрубаний. Даже после потери данных на переполнении, почистишь место, потрёшь битые файлы — и готово, работаешь дальше, накручиваешь аптайм. Но осадочек остаётся (плюс дважды уже терял невосстановимые данные — битые файлы ещё обнаружить надо…)

KRoN73 ★★★★★
()
Ответ на: комментарий от tis

Что за глюк был?

У sparse-файлы вместо номеров блоков указаны нули. При попытке перемещения таких файлов формировались карты переноса с нулём вместо исходной точки. К счастью в коде есть проверки вырожденности карт переноса, поэтому блоки просто оставались там, где были.

У меня на (3 GiB /var) разделе половина оказалась дефрагментирована, а половина нет. Из-за двух разреженных файлов.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Понял :-) А то я на хомяке как раз дефрагом воспользовался, а теперь испугался :-)

Да, кстати, в stuff оверлее есть ебилд для дефрагментатора твоего.

tis ★★
()
Ответ на: комментарий от i-rinat

Все сохранилось/выжило.
Ты б все-таки changelog писал, проще б было понимать что поменялось/что поправил.

Для справки: 440 Гб хомяка, 30 Гб свободно: ровно 22 чaса на дефрагментацию.

tis ★★
()
Ответ на: комментарий от tis

Да, кстати, в stuff оверлее есть ебилд для дефрагментатора твоего.

Спасибо. Очень здорово.

Ты б все-таки changelog писал, проще б было понимать что поменялось/что поправил.

Да я бы с радостью, но едва могу сформулировать, что поменялось, слишком много мелочей там и сям. Но я стараюсь в эту тему выжимку писать, что изменилось в видимом поведении. Хотя бы по-русски.

440 Гб хомяка, 30 Гб свободно: ровно 22 чaса на дефрагментацию.

А какая была версия? Ошибки были? Если версия tree-through, она печатает число листьев в каждом заходе. Не помнишь, сколько там было?

Похоже, к концу раздела число обрабатываемых листьев растёт, и из-за этого сохраняется квадратичность по времени.

i-rinat ★★★★★
() автор топика
Ответ на: комментарий от anonymous

а что вы знаете об устройстве современных дисков?

Круглые керамические пластинки с напылённым магнитным слоем. Крутятся. Считывающие головки, записывающие головки. Дёргаются. Контроллер, кэш.

К чему вопрос?

i-rinat ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.