👁 93
Guten Morgen, Comrades!
Как я уже писал в паре предыдущих записей, иногда я занимаюсь тем, что анализирую или собираю статистику по каким-то данным. И правда, не всё же время мне обезьянить на Java? Так вот, держите историю про то, как я не разглядел с первого раза совершенно (не)очевидную проблему в производительности.
Был прекрасный августовский вечер, я радовался напиленному и отлаженному за несколько дней абсолютно дичайшему скрипту (типа как вот в этой статье, только несколько детальнее), наваянном прямо на shell’е, и предвкушал, как эта поделка профильтрует очередную охапку пользовательских данных, завернутых через хитро закрученную ж в несколько архивов. «ШТОШ,» – подумал я, – «время 9 вечера, на ЗАВОД мне топать через 12 часов, уж за столько-то времени он должен отработать». Распаковал скриптом 100 архивов, достал данные, сложил что и куда надо, бегло зачекал что получилось, замерил потраченное время. «Нормально, с пивом покатит. Утром на стендапе расскажу команде про предварительные результаты и буду прям спец-молодец. Тем паче, сроки жмут!»
Дальше по классике: шуруем на сервер по ssh, запускаем скриптик в фоновом режиме, stdout и stderr пихаем в файл. Закрываю ноут. Утром следует посмотреть, че он там нафильтровал. Надо обработать 60k архивов, и к 5 утра, по моим расчетам, должно все ну наверняка запроцесситься. АХАХХАХАХА, ну конечно!
8 утра. Турка с кофе традиционно оказывается на плите, а я, собственно, на стуле. Открываю ноут, дальше терминал, cd, всё такое. Так. ТАК. *Сцена, где в глазах рисуется недоумение* А где результат? Что говорит `ps`? Нууу, скрипт не упал, уже радует. Распакованные из архивов данные пихаются во временную директорию, потому что дальше банда `sort’a` и `unique’a` будет нещадно все минимизировать. Для временной директории делаем `ls -l`, и что же мы видим, Ватсон? Распаковано 36 тысяч с чем-то файлов. 36k файлов из 60k, Карл! Что сказать – пиздос, тут даже самому тупому будет понятно, что сроки уже проёбаны. Штош, теперь у меня ещё меньше времени для процессинга – прекрасное начало дня!
Нужно было разобраться, почему всё оказалось так долго. А разгадка была проста.
Первый же вопрос, который звоном ударил в голову – «Почему X файлов процессится за час, а 5X файлов процессился нихрена не за 5 часов?».
Давайте подумаем, как же так получилось.
Ненадолго выбросим из головы файлы. Представьте, что вы пошли в магазин за продуктами, а в руках у вас список того, что нужно купить. Как вы ищете нужную позицию в списке? Правильно, пробегаете глазами по каждой позиции и проверяете каждую – совпадает ли запись с той, что диктует вам голос в голове.
Согласитесь, что проверить, действительно ли вам нужно купить печеньки или пиво было бы проще и быстрее, если бы вы выделили категории «сладкое» и «алкоголь»? Сюрприз! Для этого в том числе существует каталогизация. С файлами, на самом деле, все то же самое.
Возьмем абстрактный пример: хочется обработать 1 000 000 файлов. В самом простом случае они хранятся в виде плоской структуры (простой список). В среднем, получается, чтобы взять какой-то файл по его имени, нужно пробежать 500 000 файлов. А что если запихать это в 1000 каталогов по 1000 файлов? В среднем получится 500 + 500 = 1 000. С тремя уровнями вложенности (по 100 единиц на уровне) этот показатель будет 150. Разница очевидна.
Может, немного бенчмарков? Их есть у меня. Сгенерируем 6 тысяч файлов типа тех, что я уже использовал в примерах. Упакуем дважды их в архив – сделаем почти всё по условиям изначальной боевой задачи. В одном каталоге сделаем плоскую структуру, в другом разобъем на 80 каталогов по 75 файлов. Впрочем, забавы ради сделаем еще трехуровневую структуру по 18 элементов на каждом уровне – это нам еще пригодится. Не будем утруждать себя фильтрацией нужных файликов – только распакуем их и посчитаем, сколько времени нам для этого потребовалось. Для этого нам будет нужна команда `time`:
time funny_script.sh in_flat
И что же у нас вышло?
processing directory «in» real 1m34.113s user 0m32.347s sys 0m46.678s user+sys ≈ 79 sec processing directory «in_flat» real 3m9.373s user 1m17.388s sys 1m37.128s user+sys ≈ 77+97 ≈ 174 sec processing directory «in_triple» real 1m42.273s user 0m33.307s sys 0m49.309s user+sys ≈ 82 sec
Разница между плоской и неплоской структурой получилась практически двукратная. Ого-го! Уже интересно. Но логично. Однако разницы между двухуровневой и трехуровневой структуры практически нет. Рискну предположить, что это обусловлено использованием дерева в нынешних файловых системах для хранения содержимого каталога:
http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
В итоге вернемся к исходной задаче. Чем закончилась та эпопея с фильтрацией файлов? Ну, я заюзал командочку типа такой:
i=0; for f in *; do d=dir_$(printf %03d $((i/300+1))); mkdir -p $d; mv "$f" $d; let i++; done
И в итоге допроцессил эти несчастные файлы, кек.
С одной стороны дичайший стрём – ну очевидная же херня! Даже ежу понятно, что дерево зачастую попроще обойти, чем бежать тупо по списку. С другой логично – если мартышить сплошные микросервисы на Java и вообще всякие абстрактные штуки, глаз замыливается. Короче, иногда стоит задумываться про перформанс не только когда фигачите цилы и структуры данных где-то там в сервисе, ваш кэп.