Предыдущий флешмоб по поводу задачи md5_bruteforce показал, что в простом виде эта задача не очень показательна. Действительно, если проблема в том, чтобы подобрать пароль максимально быстро, то задача решается одним способом (тупо деление всего диапазона по количеству ядер, на каждом ядре простой цикл). Если же цель показать, как можно использовать возможности языка и/или библиотеки в области concurrent programming, то пример не очень выразителен, т.к. в нем мало взаимодействий между параллельно работающими сущностями.
Ув. тов.asfikon, инициатор первого флешмоба с простой реализацией md5_bruteforce, поддерживает список решений в своем посте eax.me/go-goroutines. Там можно найти решения исходной задачи на Go, D, Rust, Scala, Clojure, C++,...
Поэтому в процессе обсуждения результатов простого md5_bruteforce, возникла идея, что данную задачку можно сделать более привлекательной с точки зрения именно concurrency, а не parallel computing. В результате чего новая задача формулируется следующим образом (огромное спасибо ув.тов.swizard-у за первоначальную формулировку):
- Программа представляет собой многопоточное приложение, с архитектурой: мастер + один или несколько воркеров.
- Количество воркеров определяется на старте программы, и, обычно, равно количеству вычислительных ядер в машине.
- Мастер вычитывает задания из stdin построчно и раздаёт их свободным воркерам. Пустые строки могут игнорироваться сразу и не восприниматься как задания. Чтение должно либо чередоваться с обработкой, либо вестись параллельно. Нельзя однократно прочитать содержимое stdin от начала до конца и лишь затем приступить к обработке прочитанного (т.к. программа должна иметь возможность работать в составе, например, конвейера в течении длительного периода и обрабатывать миллионы/сотни миллионов/миллиарды строк с stdin).
- Задание -- это md5-сумма пароля и диапазон возможных значений пароля. И нижняя, и верхняя граница интервала входит в поиск (т.е. диапазон вида [lower,upper]).
- Символы пароля и интервалов могут быть либо цифрами, либо строчными латинскими буквами.
- Пример строки с заданием: fec91335051486b245d74cdb6042d4c0 0ayie zayie
- Воркер получает задание, пытается подобрать значение из указанного в таске диапазона, которое даст такой же md5-хеш. Такое значение может быть, а может и не быть. О результате воркер сообщает мастеру, который печатает отчёт на stdout.
- Получение результата мастером означает, что воркер освободился и может получить следующий таск (если таковые еще есть).
- Диапазоны могут быть заданы некорректно.
- zzz 000 -- нарушение правила lower меньше upper.
- 0000 zz -- в upper меньше символов, чем в lower.
- aaaa aaAz -- символ A не входит в разрешенный алфавит
- Помимо некорректных диапазонов, ошибка может возникать при парсинге строки, и некорректном формате md5-суммы.
- Столкнувшись с ошибкой, воркер должен "упасть" (завершить работу).
- Эту ситуацию должен отловить мастер и запустить вместо упавшего воркера нового. Проблемное задание при этом выбрасывается, но на stderr должен быть отчёт от мастера.
- Если воркер завершил обработку задачи без ошибок, то этот воркер должен быть переиспользован для одного из следующих заданий (если таковые будут). Т.е. допускается создание воркеров по мере необходимости, но не допускается создание/пересоздание воркеров для каждого нового задания.
- Завершение работы программы происходит при достижении конца stdin и завершении обработки всех начатых заданий.
Краткое пояснение о том, чего же мы хотели достичь именно такими условиями, представлено ниже.
Приглашаем всех желающих принять участие в новом флешмобе и попробовать продемонстрировать свое решение этой задачи на любимом языке программирования и/или фреймворке (велосипеде).
Целью является не столько получение максимально быстрых решений -- решение должно просто продемонстрировать что при увеличении доступных ему ядер процессора общее время на обработку задач с stdin уменьшается за счет их распараллеливания. Скорее цель в том, чтобы показать, во что выливается реализация чего-то более-менее напоминающее задачи из реальной жизни. Причем показаны здесь будут разные качества -- и количество кода, и его понятность, и подверженность ошибкам, и количество задействованных инструментов и т.д.
Уже имеющиеся решения:
- на языке Rust от swizard. И более подробное описание у него в ЖЖ.
- на языке C++ и SObjectizer от eao197. И более подробное описание отдельным постом.
- на языке C++ и Synca от Григория Демченко. Отличный пример лаконичного решения на короутинах с использованием инструмента Synca.
Данную задачу мы со swizard-ом сформулировали именно таким образом, чтобы получить более-менее адекватное приближение к реальным задачам.
Мастер -- это аналог менеджера какого-то типа задач внутри приложения. Этот менеджер может получать запросы извне по IPC и решать, что с ними делать. Может читать запросы из БД или получать от какого-то другого менеджера внутри того же самого приложения. Например, менеджер может отслеживать какой-нибудь subject в MQ, читать относящиеся к subject-у сообщения, решать, что с ними делать, отдавать задачи воркерам, собирать результаты и в нужном виде отправлять их обратно в MQ, возможно в какой-то другой subject или группу subject-ов. Или же приложение разрабатывается с прицелом на масштабирование на несколько узлов -- когда мастер один, а воркеры создаются на других машинах и знают только о мастере. В этом случае воркеры вообще не будут иметь возможности отправить результат кому-то кроме мастера.
То, что воркеры могут "падать", так же является попыткой приблизится к реальности. В задаче могут быть какие-то тонкие противоречия, которые можно проверить только после выполнения всей задачи или ее части. Например, воркеру поступает на вход зашифрованное сообщение с подписью и идентификатор ключа, воркер должен взять соответствующий ключ, проверить подпись и, если подпись корректная, попытаться расшифровать сообщение. Тут несоответствие подписи заданному ключу не проверить заранее, это можно сделать только в самом воркере.
Или же в процессе выполнения задачи у воркера может случиться какая-то проблема (например, истечет тайм-аут при обращении к внешнему сервису, отвалится коннект к БД, при выполнении SQL-запроса вылетит какая-то ошибка, связанная с ограничениями схемы данных (например, попытка вставить данные с неуникальным ключем и т.д.). Зачастую при возникновении таких проблем бывает проще рестартовать воркер, чем пытаться восстановиться внутри него.
Требование того, что воркеры должны максимально полно переиспользоваться и не пересоздаваться на каждую задачу так же является приближением к реальным проектам, где старт воркера может быть тяжелой и дорогой операцией. Например, если воркер должен установить собственное подключение к БД, проинициализировать какое-то подключенное к компьютеру устройства, запустить внешний процесс или установить подключение к удаленному серверу...
Поэтому-то в условие кажущейся очень простой вычислительной задачи и было добавлено столько дополнительных пунктов, чтобы придать игрушечной по размеру проблеме черты реального, большого приложения. Но при этом не требовать от разработчика написания чего-то большого и серьезного.
Небольшое примечание специально для тех, кто любит сравнивать размеры программ по количеству физических строк. Это довольно неблагодарное занятие хотя бы потому, что у каждого разработчика свой стиль кодирования. Поэтому, если есть желание подсчитывать количество строк, то имеет смысл хотя бы поудалять из исходника пустые строки и строки, которые содержат только открывающие/закрывающие скобки. Например, пропустив текст через такой простенький Ruby-скрипт:
ARGF.each_line do |line|
if line =~ /(\d|\w)/
puts line
end
end
Комментариев нет:
Отправить комментарий