Make tree-structure great again!

Guten Morgen, Comrades!

Как я уже писал в паре предыдущих записей, иногда я занимаюсь тем, что анализирую или собираю статистику по каким-то данным. И правда, не всё же время мне обезьянить на Java? Так вот, держите историю про то, как я не разглядел с первого раза совершенно (не)очевидную проблему в производительности.

Firstly:

Q: b00blik, why not English again?

A: Cuz this is 65/35 coolstory/tech. Please, use Google Translate or other service if you are too smart to read my ‘smekhuechki’ in Russian or Russian is not your mother tongue.

Ну, а вдруг кто-то из-за рубежа накликает до этой ссылки, лол.

Был прекрасный августовский вечер, я радовался напиленному и отлаженному за несколько дней абсолютно дичайшему скрипту (типа как вот в этой статье, только несколько детальнее), наваянном прямо на 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`: 

И что же у нас вышло?

Почему сложил второй и третий результат?

Вкратце: сколько времени заняла работа вызова вне ядра (user-mode) + внутри ядра (sys).

Подробное пояснение можно найти вот тут: https://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time1

Разница между плоской и неплоской структурой получилась практически двукратная. Ого-го! Уже интересно. Но логично. Однако разницы между двухуровневой и трехуровневой структуры практически нет. Рискну предположить, что это обусловлено использованием дерева в нынешних файловых системах для хранения содержимого каталога: 

https://stackoverflow.com/questions/4003885/200-000-images-in-single-folder-in-linux-performance-issue-or-not

http://ext2.sourceforge.net/2005-ols/paper-html/node3.html

В итоге вернемся к исходной задаче. Чем закончилась та эпопея с фильтрацией файлов? Ну, я заюзал командочку типа такой:

И в итоге допроцессил эти несчастные файлы, кек.

С одной стороны дичайший стрём – ну очевидная же херня! Даже ежу понятно, что дерево зачастую попроще обойти, чем бежать тупо по списку. С другой логично – если мартышить сплошные микросервисы на Java и вообще всякие абстрактные штуки, глаз замыливается. Короче, иногда стоит задумываться про перформанс не только когда фигачите цилы и структуры данных где-то там в сервисе, ваш кэп.