Недавно мой знакомый Karl (имя изменено) проходил собеседование на должность DevOps и обратился ко мне с просьбой проверить его решение. Я почитал условие задачи и решил, что из нее бы вышел неплохой тест, поэтому немного расширил задачу и написал свою реализацию, а заодно попросил коллегу Alex подумать о своей реализации. Когда все три варианта были готовы, я сделал еще две сравнительные версии на C# и сел писать эту статью. Задача довольно проста, а соискатели находятся на неких ступенях эволюции из админов в программисты, которые я и хотел оценить.
Кому интересны грязные детали, необъективные тесты и субъективные оценки — прошу под кат.
Задача
По условию у нас есть текстовые логи с загрузкой CPU серверов и необходимо делать из них некие выборки.
В итоге для 1000 серверов по 2 CPU за один день получается каталог с 1000 логами в текстовом виде по 2880 записей в таком формате:
1414689783 192.168.1.10 0 87
1414689783 192.168.1.11 1 93
Поля в файле означают следующее:
timestamp IP cpu_id usage
Надо сделать CLI программу, которая берет в качестве параметра имя каталога с логами и позволяет посмотреть загрузку конкретного процессора в промежуток времени.
Программа может инициализироваться неограниченное время, но время выполнения каждого запроса должно быть меньше секунды.
Нужно поддерживать следующие команды для запроса:
1. Команда QUERY — сводная статистика по серверу за диапазон времени
Синтаксис: IP cpu_id time_start time_end
*Время задается в виде YYYY-MM-DD HH:MM
Пример:
>QUERY 192.168.1.10 1 2014-10-31 00:00 2014-10-31 00:05
(2014-10-31 00:00, 90%), (2014-10-31 00:01, 89%), (2014-10-31 00:02, 87%), (2014-10-31 00:03, 94%), (2014-10-31 00:04, 88%)
2. Команда LOAD — средняя загрузка выбранного процессора для выбранного сервера
Синтаксис: IP cpu_id time_start time_end
Пример:
>LOAD 192.168.1.10 1 2014-10-31 00:00 2014-10-31 00:05
88%
3. Команда STAT — статистика всех процессоров для выбранного сервера
Синтаксис: IP time_start time_end
Пример:
>STAT 192.168.1.10 2014-10-31 00:00 2014-10-31 00:05
0: 23%
1: 88%
Разрешается использовать любые языки программирования, сторонние утилиты.
P.S. В изначальном задании подразумевалось, что это интерактивная программа, которая принимает команды с консоли после загрузки. Это не обязательно и программа может быть разбита на раздельные части для загрузки и для выполнения запросов. Т.е. допускается вариант с несколькими скриптами init.sh, query.sh, load.sh и т.д.
В целом, задача весьма прозрачна и в ней напрашивается использование БД, поэтому не удивительно, что все три варианта используют SQLite. Вспомогательные варианты на C# я уже сделал для сравнения скорости и они работают иначе.
Оценка
В готовых решениях я оценивал два фактора с соотношением 40/60%: скорость и качество кода. Методика оценки факторов приведена чуть ниже, но оба фактора никак не относятся к общему вопросу и не показывают степерь «админства» или «программерства», поэтому отдельно я кроме сухих баллов скорости/качества, вывел отдельно субъективную шкалу «админское решение», «программерское», «универсальное». Это ни в каком виде не соревнование и не сравнение скорости разных языков, а скорее оценка подходов к программированию.
Оценка скорости
По условию запрос должен выполняться меньше секунды, но не приведено ни оборудование, ни количество ядер, ни вообще архитектура тестовой станции. На мой взгляд это наводит на мысль, что тест должен выполняться на порядок или два быстрее, чтобы на адекватном оборудовании всегда оставаться в нужных рамках. Заодно это должно натолкнуть на идею масштабируемости — в задаче приводится пример на 2880000 записей за один день, но в реальных условиях их может быть заметно больше (больше серверов и ядер), а диапазон выборки может включать не дни, а месяцы и годы. Значит, идеальное решение должно не показывать зависимости от объема данных и не потреблять лимитированные ресурсы в неограниченном количестве. В этом случае бесконтрольное использование памяти (in-memory tables или хранение в массивах в памяти) это минус, а не плюс, потому как выборка за год на 10000 компьютеров по 8 процессоров это навскидку 42 048 000 000 записей, минимум по 10 байт каждая, т.е. ~420GiB данных. К сожалению, проверить такие объемы мне не удалось из-за ограничений доступной техники.
Для проверки скорости использовалась unix команда time (значение user), а для интерактивных решений — внутренние таймеры в программе.
Оценка качества
Под качеством я в основном понимаю универсальность — универсальность использования, поддержки, доработки. Нет особого смысла в коде, который работает только в строго заданных рамках и никак не может выйти за их пределы, обработать больше данных, быть изменен для других ситуаций и т.д. Например, код на x86 Assembler мог бы быть очень быстрым, но совершенно не гибким и простейшее изменение вроде перехода на IPV6 адреса могло бы стать для него очень болезненным. В первую очередь тут оценивалась обработка входящих параметров: нестандартные ситуации, выборки, дающие 0 результатов, не валидные запросы. Во-вторую — язык программирования, стиль кода, количество и качество комментариев.
Субъективная оценка
Сложно сказать, какой именно параметр определяет, насколько эволюционировал администратор до программиста. Лично я разделяю их по такому принципу: администратор работает с инструментами, а программист создает их. Разница примерно как между профессиональным гонщиком и автомехаником — механик зачастую неплохо водит и знает автомобиль досконально, но гонщик чувствует все заложенные в машину свойства и даже больше. Хороший админ знает скорость работы базы данных, понимает что такое горизонтальное и вертикальное масштабирование, каждый день пользуется индексами. Программист может написать свою БД, использовать вложенные деревья для них, может конвертировать все данные в собственный формат и оставить их на диске, хитрым образом расположенные для быстрого доступа.
В случае, если бы Karl написал прямой перебор данных, ссылаясь на его сверх-производительность, особенно с хешированием или быстрым поиском, это бы значило, что он уже таки стал программистом. Но скорее всего, не имел бы шансов получить работу как DevOps.
Программы
Всего у меня было 5 программ — три участвуют в сравнении, две написаны уже позже, только для проверки некоторых идей и сделаны на C#. Для удобства я программы буду называть именами их авторов.
Karl
Код на github: github.com/Nomad1/testbase/blob/master/karl
Язык: Pyhon 2.7
Зависимости: нет
Интерактивная: да
БД: SQLite, in-memory table
Alex
Код на github: github.com/Nomad1/testbase/blob/master/alex
Язык: Pyhon 2.7
Зависимости: progress, readline
Интерактивная: да
БД: SQLite, in-memory table
Nomad1
Код на github: github.com/Nomad1/testbase/tree/master/nomad1
Язык: Bash
Зависимости: нет
Интерактивная: нет
БД: SQLite
Особенность: внешний .db файл для работы
Nomad2
Код на github: github.com/Nomad1/testbase/tree/master/nomad2
Язык: C#
Зависимости: mono
Интерактивная: да
БД: нет
Особенность: Хэш-таблица по IP адресам
Nomad3
Код на github: github.com/Nomad1/testbase/tree/master/nomad3
Язык: C#
Зависимости: mono
Интерактивная: нет
БД: нет
Особенность: специально подготовленные данные
Тестирование
Для тестирования был написан генератор логов, сначала на bash, потом на C++. Было создано три тестовых набора:
- data_norm — 1000 логов по 2 CPU, один день (~80Mb логов)
- data_wide — 1000 логов по 2 CPU, один месяц (~2.3Gb логов)
- data_huge — 10000 логов по 4 CPU, 5 дней (~10Gb логов)
Запросы формировались по принципу:
- valid — запрос в диапазоне допустимых значений
- wide — запрос шире, чем допустимые значения (захватывает начало или конец диапазона)
- invalid — запрос для отсутствующих данных
Все тесты выполнялись по 4 раза, первое значение откидывалось, остальные усреднялись (чтобы исключить время JIT компиляции, прогрева кеша, загрузки из свопа). Тестирование проводилось на рабочем компьютере под Mac OS 10.13.2 с процессором i7 2.2 GHz, 8GB RAM, SSD диском.
К сожалению, тесты по запросу QUERY не очень показательны у половины программ, потому как вывод на экран зачастую в разы дольше самого запроса. В случае программы Nomad1 вывод может занимать сотни миллисекунд из-за очень медленного форматирования в Bash, в то время как запрос выполняется за миллисекунды. В программе Karl вообще допущена ошибка измерения: считается время выполнения внутреннего запроса для QUERY без вывода на экран. В моем понимании «время выполнения команды» это время между вводом команды и получением результата, поэтому к этой программе пришлось применить штрафы, описанные ниже.
Примечательно, что Karl и Alex не сговариваясь написали программы на python 2.7, с использованием SQLite, в интерактивном режиме (сначала загружаются данные, потом принимаются команды). Программа Nomad1 написана на чистом bash как набор CLI скриптов и тоже использует SQLite.
Программы Nomad2 и Nomad3 интересны общим подходом: в случае с Nomad2 все данные грузятся в память в хэш-таблицу с ключом по IP. В случае с Nomad3 условно принимается, что имя файла это IP адрес и при поиске программа просто считывает файл в память и дальше работает перебором. Оба теста актуальны только для сравнения скорости и не участвуют в оценке качества. Кроме всего прочего, они написаны на C#, который представлен на Unix в виде mono и имеет кучу особенностей. Например, результаты mono32 и mono64 разнятся в разы для того же кода, а на Windows и .Net все работает еще быстрее.
Результаты по скорости
Сами команды запросов я спрячу под кат, чтобы не засорять топик. В таблицах результат записано по три строки на ячейку, это скорость выполнения команд QUERY, LOAD, STAT в секундах.
QUERY 10.0.2.23 1 2014-10-31 09:00 2014-10-31 12:00
LOAD 10.0.2.254 0 2014-10-31 13:10 2014-10-31 20:38
STAT 10.0.1.1 2014-10-31 04:21 2014-10-31 08:51
data_norm/wide:
QUERY 10.0.1.11 0 2014-10-01 09:00 2014-10-31 07:21
LOAD 10.0.2.254 1 2014-10-31 15:55 2014-11-04 10:00
STAT 10.0.1.100 2014-10-31 14:21 2015-01-01 01:01
data_norm/invalid
QUERY 10.0.2.23 1 2015-10-31 09:00 2015-10-31 12:00
LOAD 10.0.2.254 0 2015-10-31 13:10 2015-10-31 20:38
STAT 10.0.1.1 2015-10-31 04:21 2015-10-31 08:51
data_wide/valid:
QUERY 10.0.2.33 0 2014-10-30 09:00 2014-10-31 02:00
LOAD 10.0.0.125 1 2014-10-02 14:04 2014-10-04 20:38
STAT 10.0.1.10 2014-10-07 00:00 2014-10-17 23:59
data_wide/wide:
QUERY 10.0.1.11 1 2014-07-30 09:00 2014-10-01 07:21
LOAD 10.0.0.137 0 2014-10-20 04:12 2015-02-01 00:00
STAT 10.0.3.3 2014-10-20 04:12 2015-02-01 00:00
data_wide/invalid
QUERY 10.0.0.123 1 2015-10-31 09:00 2015-10-31 12:00
LOAD 10.0.0.154 0 2015-10-31 13:10 2015-10-31 20:38
STAT 10.0.0.1 2015-10-31 04:21 2015-10-31 08:51
data_huge/valid:
QUERY 10.0.2.33 0 2014-10-30 09:00 2014-10-31 02:00
LOAD 10.0.0.125 1 2014-10-28 14:04 2014-10-30 20:38
STAT 10.0.1.10 2014-10-28 00:00 2014-10-30 23:59
data_huge/wide:
QUERY 10.0.5.72 0 2014-10-31 09:00 2015-11-03 12:11
LOAD 10.0.0.137 0 2014-10-20 04:12 2015-02-01 00:00
STAT 10.0.3.3 2014-10-20 04:12 2015-02-01 00:00
data_huge/invalid
QUERY 10.0.1.11 1 2014-07-30 09:00 2014-10-01 07:21
LOAD 10.0.0.154 0 2015-10-31 13:10 2015-10-31 20:38
STAT 10.0.0.1 2015-10-31 04:21 2015-10-31 08:51
Было сделано 135 тестов (по 27 на каждую программу), их скорость выполнения приведена в таблице:
| Test | Karl | Alex | Nomad1 | Nomad2 | Nomad3 |
|---|---|---|---|---|---|
| data_norm/valid | 0.008800 0.000440 0.000420 |
0.215300 0.211700 0.217800 |
0.256200 0.007300 0.008300 |
0.002160 0.000130 0.000140 |
0.050200 0.050300 0.052600 |
| data_norm/wide | 0.002640 0.000330 0.000630 |
0.218000 0.212000 0.215000 |
0.716000 0.008000 0.008600 |
0.005000 0.000150 0.000320 |
0.050200 0.005200 0.005500 |
| data_norm/invalid | 0.000063 0.000073 0.000065 |
0.214200 0.209100 0.206300 |
0.007600 0.008300 0.008100 |
0.000008 0.000026 0.000034 |
0.048000 0.053000 0.050000 |
| data_wide/valid | 0.007300 0.005500 0.002300 |
6.237600 6.146500 6.151000 |
1.446000 0.036000 0.069000 |
0.017186 0.001099 0.005665 |
0.167000 0.088000 0.126000 |
| data_wide/wide | 0.006800 0.002100 0.024200 |
6.176600 6.157900 6.326100 |
0.570000 0.039000 0.070000 |
0.008363 0.005818 0.005592 |
0.071000 0.160000 0.159000 |
| data_wide/invalid | 0.000085 0.000110 0.000150 |
6.288100 6.152100 6.130400 |
0.044000 0.040000 0.062000 |
0.000013 0.000040 0.000013 |
0.155000 0.156000 0.164000 |
| data_huge/valid | 0.009107 0.007655 0.012858 |
155.9738 146.5377 140.1752 |
1.401000 0.013300 0.026000 |
0.036806 0.003798 0.003751 |
0.069000 0.066000 0.072000 |
| data_huge/wide | 0.009418 0.013718 0.014266 |
157.1896 148.5435 147.9525 |
1.078000 0.011700 0.026000 |
0.018393 0.000805 0.003329 |
0.072000 0.081000 0.077000 |
| data_huge/invalid | 0.000070 0.000095 0.000081 |
144.7307 158.0090 165.6820 |
0.012000 0.013000 0.023000 |
0.000012 0.000031 0.000013 |
0.054000 0.071000 0.081000 |
Результат по скорости я оценивал математически: для каждого запроса и набора данных считался порядок (десятичный логарифм от времени в микросекундах) и затем он выступал делителем для порядка самого быстрого решения. Таким образом, самое быстрое решение получало коэффициент 1.0, на порядок более медленное 0.5 и т.д. Результат по каждой программе усредняется и умножается на 40.
Для программы Karl, к сожалению, пришлось ввести уменьшающий коэффициент, т.к. она не считала время работы всей команды QUERY, а только внутреннего SQL запроса. Я добавил один порядок (M) ко всем не-пустым результатам QUERY, что уменьшило балл Karl примерно на 2 балла суммарно.
Полную версию таблицы с результатами можно увидеть тут.
Результаты:
Karl: 31/40 (33 без штрафа)
Alex: 15/40
Nomad1: 22/40
Nomad2: 39/40
Nomad3: 21/40
Результаты по качеству
Тесты скорости выявили разные интересные ошибки и подводные камни. Я прячу их под спойлер на случай, если вам взбредет в голову написать свою программу и вы уверены, что наверняка не допустите чужих багов. Программы Nomad2 и Nomad3 тут не разбираются и не оцениваются.
2. Индексы. Alex забыл об индексах вообще. Karl создал индекс из всех полей — IP + Timestamp + CPU. Это оправдано только в очень редких случаях поиска по конкретному Timestamp, но по условию задачи мы всегда делаем выборку по IP + CPU и диапазону Timestamp. Это не критично, если размер базы более-менее адекватный, но для вариантов _wide и _huge это привело к огромным потерям памяти при минимуме выигрыша в скорости. Программа Karl на данных _huge постоянно вылетала с ошибкой «Killed: 9» из-за переполнения памяти и свопа.
3. Включение границ диапазона в расчеты. Nomad1 об этом забыл и его выборка из-за каких-то особенностей преобразования timestamp в bash иногда не включает нижнюю границу (в github есть исправленный результат, но в тесты он не вошел).
4. Использование :memory: таблицы с неизвестным объемом данных.
Это архитектурная ошибка и ее допустили Karl и Alex — они сделали in-memory table, не спрашивая себя о последствиях и объемах. В итоге их программы очень зависимы от объема данных и доступной памяти, что уже видно в тесте data_huge. В реальных условиях такие бы программы не работали или работали с проблемами. Идеальный вариант должен оценивать объем считываемых данных и выбирать тип базы.
5. Проверка входящих данных и ошибок. Тут налажали все — запросы в базу не проверяются на валидность даты, адреса, SQL Injection и т.д. В случае invalid запроса LOAD у Alex вылетает ошибка деления на ноль, у Karl пишется No data, а у Nomad1 вообще нет ни одного Exception и вывод ошибки SQLite в запросе STAT будет перемолот через разбиение строки по знаку |. Ни одна программа не воспринимает IP адрес вида 010.00.020.003. Вылеты от неверных запросов были у всех, но т.к. для тестов пришлось сделать 540+ выполнений команд, у меня не хватило здоровья собрать и разобрать их примеры.
6. Округление результатов для LOAD и STAT. Karl ничего не округлял и вывел число с десятичной точкой, что не смертельно, но не соответствует условию задачи. Alex привел число к INT, отбросив дробную часть целиком.
Все три программы написаны на современных и читабельных языках программирования (VBScript и Brainfuck не замечено). Код на bash чуть менее читабелен, чем версии на Python, но заметно меньше по объему. Код Alex использует сторонние библиотеки readline и progress, написан свой класс для Auto-complete по Tab, есть отдельные функции для хелпов, работы с датой, поддержка перезагрузки данных, обработка ошибок, однако база не закрывается при выходе. Код Karl использует класс для наследования от Cmd, обработку исключений, закрывает БД при выходе, ловит Ctrl-C. К сожалению, комментариев нет ни у кого (с парой не существенных исключений).
Интересный и более программистский подход использует Alex — он для всех трех команд делает одинаковый запрос, а затем в коде считает данные для STAT/LOAD, не пользуясь AVG и GROUP BY. Это существенно снижает объем кода, а скорость выполнения в целом получается такая же, как если переложить эту задачу на БД.
С учетом описанных особенностей и пары дополнительных факторов по качеству я оценил программы так:
Karl: 35/60
Alex: 40/60
Nomad1: 30/60
Выводы
Сумма баллов:
Karl: 66/100
Alex: 55/100
Nomad: 52/100
По баллам и скорости всех обошло решение Karl, потому как решение Alex не конкурентно по скорости из-за отсутствия индексов. Что интересно, как только я сообщил Alex про невысокую скорость, он сказал, что в 82й строке можно добавить индексы, он это планировал и продумал, но решил оставить «на потом». К сожалению, это было уже было после приема программ и заморозки кода, поэтому такое изменение внести было нельзя.
Программы Nomad2 и Nomad3 набрали по скорости 39/40 и 21/40 балла соответственно. Не удивительно, что работа с хеш-таблицей оказалась быстрее БД, пусть и с большими потерями памяти. Работа напрямую с файловой системой оказалась не особо быстрой, но надо понимать, что у такого варианта почти отсутствует время инициализации, у него минимальная нагрузка на память и по большому счету он может использоваться с любыми объемами заранее подготовленных данных.
Вариант Karl за счет «широкого» индекса потреблял больше всех памяти и падал уже при размере данных в 6Гб. Все варианты с :memory: таблицей или хэш-таблицами не смогут работать при объемах 10Гб и выше, в то время как решение с БД в файле не намного медленнее и масштабируется гораздо лучше. К сожалению, вывод данных через bash поставил крест на скорости этой программы.
Работа в виде интерактивных приложений дает существенный прирост к скорости — у программ Nomad1 и Nomad3 явно видно, что даже на пустых запросах около 10 мс для bash и 50 мс для C# уходит только на запуск.
Субъективная оценка
Теперь немного субъективных рассуждений. Особо нервным можно не читать, напомню, что все написанное является моим собственным мнением и скорее всего не совпадет с вашим.
Все три участника использовали SQLite и не стали городить свой велосипед. Это несомненный плюс, но и явно показывает, что все три варианта далеки от чистого программирования. Они решают свою задачу, при чем, достаточно быстро, но без попыток создать собственную In-Memory Database с быстрой индексацией (как в варианте Nomad2) или выборками без предварительной загрузки (как в варианте Nomad3). Чуть-чуть ближе к программерскому решению подход Alex к использованию единого запроса, а потом расчетах LOAD/STAT в коде. Так же я не увидел в коде других «спутников программиста», таких как логи, комментарии, собственные структуры для данных (адрес в IP4 ведь это 32-битное число, а CPU и LOAD — однобайтовые переменные!). Авторы в целом не стали задумываться о хранении данных и по большому счету просто сделали перенос текстовых файлов в бинарный формат SQLite.
Итого, на мой взгляд, решения по субъективным шкалам распределились так:
Самое «админское» решение:
1. Nomad1 — это и команда .import, и передача данных в консольный клиент sqlite вместо коннектора/курсора
2. Karl — работа с индексами, SQL запросы для всех операций, GROUP BY, ORDER BY
3. Alex
Самое «программерское» решение (перк «он создал новый инструмент»):
1. Alex — хорошая структура, работа с массивом данных при выборке, сторонние библиотеки
2. Karl — код c исключениями, очистка данных
3. Nomad1
Самое «универсальное» решение:
1. Nomad1 — команды дописываются отдельными файлами-запросами к готовой БД по аналогии с имеющимися; программа не зависит от объема данных и памяти.
2. Alex — единый запрос выдает массив данных, дальше код их обрабатывает; в шапке файла есть код для работы с файловой БД
3. Karl
Все коды программ, включая генератор, доступны на GitHub:
github.com/Nomad1/testbase
Там же есть команды, которые используются для генерации наборов данных.
Если у кого-то есть желание проверить себя на аналогичном тесте — милости прошу.
P.S. По итогам тестов Nomad1 — программист с 20-летним стажем — получил меньше баллов в данной задаче, чем DevOps и Junior developer. С другой стороны, он еще и автор статьи и было бы, кхм, не корректно присуживать себе более высокие баллы. :)
P.P.S. Написание статьи и выполнение замеров потребовало три рабочих дня, это больше, чем все участники вместе взятые потратили на написание и отладку кода. Производительность автора как писателя — однозначно неудовлетворительная.
Автор: Алексей Гарбузенко
