- Подписка на печатную версию:
- Подписка на электронную версию:
- Подшивки старых номеров журнала (печатные версии)
LXF144:erlang
Материал из Linuxformat.
- Erlang Описывается следующей формулой: функциональный язык + процессы
| Erlang |
|---|
|
Содержание |
Erlang: Много-много задач
- Андрей Ушаков завершает серию уроков по Erlang рассмотрением проблемы распараллеливания задач.
О важности многозадачности в современных приложениях сказано уже так много, что смысла повторяться, пожалуй, нет. Многозадачность применима не всегда: в некоторых случаях сам алгоритм не поддерживает распараллеливание, в некоторых случаях побочные затраты на поддержку многозадачности (например, время переключения контекста в многопоточных приложениях) больше, чем получаемая от нее выгода. Если же многозадачность возможна и от нее есть выгода, то существует проблема разделяемого состояния: если с совместно используемыми объектами работать неграмотно, то их состояние может «испортиться».
Конечно, при аккуратной (и правильной) работе с разделяемым состоянием проблем не возникает, но увеличивается сложность кода по сравнению с однозадачной версией.
Большинства этих проблем в Erlang просто нет. Конечно, если алгоритм не поддерживает распараллеливание, то исправить это можно только выбором другого алгоритма. И многозадачная версия практически всегда будет больше и сложнее, чем однозадачная. С другой стороны, создание и уничтожение процессов (это процессы самого языка Erlang, а не ОС) – очень быстрая операция, памяти и ресурсов процессы потребляют мало, создавать их можно много (максимальное количество процессов по умолчанию – 32768, но, используя флаг +P, максимальное количество можно довести до 134217727). И, что является большим плюсом, процессы в Erlang полностью независимы и не содержат совместно используемых объектов. Если двум процессам необходимо взаимодействие, это взаимодействие выглядит следующим образом: один процесс посылает сообщение, а другой процесс это сообщение принимает. Посылка и обработка сообщений происходят очень быстро. Поэтому, если перед вами встает вопрос, использовать ли многозадачность в Erlang – ответ всегда один: если алгоритм позволяет это, то да.
Рассмотрим примитивы, которые мы будем применять для построения многозадачной программы.
- Pid = spawn(Fun) Создает новый процесс, который будет выполнять функцию Fun и возвращать идентификатор этого процесса (process ID). Идентификатор процесса PID – один из типов данных в Erlang; он используется для взаимодействия процессов друг с другом (см. далее).
- Pid! Message Посылка сообщения Message процессу с идентификатором Pid. Сообщение посылается асинхронно, и отправитель не ждет, когда получатель получит сообщение. Если необходимо, чтобы процесс-получатель мог послать отправителю что-нибудь обратно, то процесс-получатель должен знать идентификатор отправителя. Самый удобный способ сделать это – отослать Pid отправителя в сообщении, например, так: ReseiverPID! {Message,self()} (функция self() позволяет процессу узнать свой Pid).
- receive ... end Получение и обработка процессом сообщений из своей очереди.
Конструкция receive выглядит следующим образом:
receive Pattern1 [when Guard1] -> Expression1; Pattern2 [when Guard2] -> Expression2; … [after Time -> AfterExpression] end
Когда сообщение доставляется процессу, оно помещается в очередь сообщений данного процесса. Когда выполнение процесса попадает в конструкцию receive, процесс просматривает свою очередь сообщений и последовательно проверяет каждое сообщение на соответствие одному из шаблонов PatternN (и на соответствие guard-выражению GuardN, если такое есть). Как только соответствие будет установлено, на этом поиск оканчивается, и конструкция receive возвратит значение – соответствующее выражение ExpressionN. Если для данного сообщения ни одного соответствия не найдено, то данное сообщение откладывается обратно в очередь (оно будет просмотрено в следующей конструкции receive), и для просмотра берется следующее из очереди. Если все сообщения из очереди просмотрены и ни для одного из них не найдено соответствия, то, что будет происходить дальше, зависит от наличия секции after. Если секции after нет, то конструкция receive будет ждать, пока в очереди не появится новое сообщение, если же секция after есть, то через Time миллисекунд конструкция receive возвратит значение выражения AfterExpression.
Вот в принципе и все необходимое (для начала) знание, чтобы создавать многозадачные приложения на Erlang.
Следует сказать пару слов о создании распределенных приложений. При создании распределенных приложений используются те же самые примитивы, что и при создании многозадачных приложений. Новым тут является только понятие узла – экземпляра виртуальной машины, запущенной локально либо удаленно (для того, чтобы экземпляр виртуальной машины считался узлом, при запуске необходимо указать его имя, например, при помощи ключей -sname либо -name). После создания узла Node на нем можно создать новый процесс при помощи функции spawn: Pid = spawn(Node, Fun). После этого вся работа с процессом на удаленном узле строится точно так же, как и с локальными процессами: используется идентификатор созданного процесса Pid для взаимодействия с ним.
Пример
Для демонстрации всего рассказанного выше (и чтобы не заскучать), давайте создадим простую распределенную систему - а точнее, создадим обычный и распределенный вариант одной и той же задачи и сравним их. Возьмем в качестве примера задачу поиска пароля по хэшу MD5 и решим ее обычным перебором. Для простоты ограничим набор символов, используемых в пароле, только цифровыми символами (0 ... 9).
Для начала введем несколько вспомогательных функций, которые будут использоваться в обоих вариантах. Во время работы мы захотим оценить время, затрачиваемое тем или иным вариантом. Текущее время в формате {MegaSeconds, Seconds, MicroSeconds} мы можем получить, вызвав функцию now(). Вспомогательный метод calc_work_time/2 позволит вычислить количество секунд между двумя измерениями:
calc_work_time(Now1, Now2) ->
{MegaSecs1, Secs1, MicroSecs1} = Now1,
{MegaSecs2, Secs2, MicroSecs2} = Now2,
(MegaSecs2-MegaSecs1)*1000000+(Secs2-Secs1)+(MicroSecs2-MicroSecs1)*1.0e-6.
Для поиска нам нужно уметь генерировать очередную строку, после чего вычислять для нее хэш MD5 и сравнивать с исходным. Для генерации мы каждой строке сопоставим целочисленный номер так, чтобы номера и строки располагались в одном порядке: строке “0” будет соответствовать номер 0, строке “1” – номер 1, …, строке “00” – номер 10, строке “01” – номер 11, и т.д. Вспомогательные методы generate_string_by_number/2, generate_string_by_number/4 и correct_number/3 реализуют данную функциональность. С точки зрения внешнего (относительно этих методов) кода, метод generate_string_by_number/2 является интерфейсом к данной функциональности.
generate_string_by_number(0, Alphabet) -> [lists:nth(1,Alphabet)];
generate_string_by_number(Number, Alphabet) ->
{CorrectNumber, StringLength} = correct_number(Number,length(Alphabet), 1),
generate_string_by_number(CorrectNumber, StringLength,Alphabet, []).
generate_string_by_number(0, StringLength, [First|_],GeneratedPart) ->
lists:duplicate(StringLength-length(GeneratedPart),First) ++ GeneratedPart;
generate_string_by_number(Rest, StringLength, Alphabet,GeneratedPart) ->
Index = (Rest rem length(Alphabet)),
NewRest = Rest div length(Alphabet),
generate_string_by_number(NewRest, StringLength, Alphabet, [lists:nth(Index+1, Alphabet)]++GeneratedPart).
correct_number(Number, AlphabetCount, CheckStringLength) ->
StringCountInRange = trunc(math:pow(AlphabetCount, CheckStringLength)),
if
Number < StringCountInRange -> {Number,CheckStringLength};
true -> correct_number(Number-StringCountInRange, AlphabetCount, CheckStringLength+1)
end.
И что еще нам нужно из вспомогательных методов – это метод, позволяющий получить максимальный целочисленный номер для заданной максимальной длины строки. Это делает метод generate_number_by_string_length/2:
generate_number_by_string_length(MaxStringLength,AlphabetCount) -> (AlphabetCount*(1-trunc(math:pow(AlphabetCount,MaxStringLength))) div (1-AlphabetCount))-1.
Со вспомогательными функциями все, и теперь можно перейти к основным функциям. Рассмотрение мы начнем со случая простого последовательного поиска. В этом случае нам понадобятся всего два метода: для запуска поиска (search/0) и для просмотра очередного варианта (search/4). Обратите внимание, что поиск не содержит явного цикла для просмотра вариантов: вместо этого метод просмотра очередного варианта (search/4) вызывает рекурсивно сам себя для просмотра следующего варианта. А благодаря тому, что в этом методе рекурсия хвостовая, этот метод разворачивается в цикл. Очень элегантно, не правда ли?
search(SourceMD5, _, CurrentNumber, MaxNumber)
when CurrentNumber > MaxNumber -> {cant_find, SourceMD5};
search(SourceMD5, Alphabet, CurrentNumber, MaxNumber) ->
GeneratedString = generate_string_by_number(CurrentNumber, Alphabet),
GeneratedStringMD5 = erlang:md5(GeneratedString),
if
SourceMD5 == GeneratedStringMD5 -> GeneratedString;
true -> search(SourceMD5, Alphabet, CurrentNumber+1, MaxNumber)
end.
search() ->
Alphabet = [$0, $1, $2, $3, $4, $5, $6, $7, $8, $9],
Source = “01234321”,
SourceMD5 = erlang:md5(Source),
Now1 = now(),
Result = search(SourceMD5, Alphabet, 0, generate_number_by_string_length(10, length(Alphabet))),
Now2 = now(),
{calc_work_time(Now1, Now2), Result}.
Осталось только привести объявления модуля и экспортируемых функций:
-module(md5_sequential_search). -export([search/0]).
Вот и все с последовательным поиском. Запускаем среду выполнения Erlang, в консоли Erlang запускаем сначала компиляцию с(md5_sequential_search)., а потом и выполнение нашей программы md5_sequential_search:search(). При запуске на моей машине (ноутбук Acer Aspire 7520G: процессор AMD Turion64×2 TL-58 1,9 ГГц, 2ГБ ОЗУ), приложение находит искомую строку “01234321” по ее хэшу MD5 за 158,234 секунд.
Перейдем теперь к распределенному варианту. В нем мы также используем вспомогательные функции calc_work_time/2 и generate_string_by_number/2. Но, в отличие от обычного варианта, мы введем несколько ролей, которые будут соответствовать разным компонентам, выполняющимися в разных Erlang-процессах. Это следующие роли: инициатор, координатор, обработчики.
Инициатор создает необходимое количество обработчиков (каждый в своем процессе), после чего создает координатор (тоже в своем процессе) и передает ему список идентификаторов процессов обработчиков. Координатор проходится по списку обработчиков и каждому из них посылает сообщение ({are_you_ready, CurrentPID, SourceMD5, Alphabet}) с требованием подтвердить свою готовность. Обработчик, получая данное сообщение, отправляет координатору сообщение с подтверждением готовности ({ready_master,HandlerPID}).
Координатор, после получения подтверждения о готовности, посылает сообщение с заданием на поиск хэша MD5 для строк, чей номер лежит в диапазоне [FromNumber, ToNumber] ({search,FromNumber, ToNumber}).
Обработчик при получении данного сообщения начинает поиск: если для какой-либо строки будет найдено соответствие с искомым MD5-хэшем, то координатору будет послано сообщение о том, что строка найдена ({found, GeneratedString}); если же обработчик в заданном ему диапазоне ничего не найдет, то будет послано соответствующее сообщение координатору ({not_found, HandlerPID}). Если координатор получает сообщение, что искомая строка найдена, он это сообщение пересылает инициатору и останавливает свою работу и работу обработчиков. Получив от обработчика сообщение, что в заданном диапазоне ничего не найдено, координатор посылает обработчику новое задание с новым диапазоном. Если обработчиками просмотрено все множество строк (из нашего ограничения на длину и набор символов) и не найдено ни одной строки, MD5-хэш которой совпадает с искомым, то инициатору будет послано соответствующее сообщение ({not_found}).
Вот и все о разных компонентах и их взаимодействии.
Давайте теперь посмотрим, как это все реализовано – и начнем с обработчиков:
start_search_handler() ->
receive
{are_you_ready, MasterPID, SourceMD5, Alphabet} ->
MasterPID ! {ready_master, self()},
search_handler(MasterPID, SourceMD5, Alphabet)
end.
search_handler(MasterPID, SourceMD5, Alphabet) ->
receive
{search, FromNumber, ToNumber} ->
portion_search(MasterPID, SourceMD5, FromNumber, ToNumber, Alphabet),
search_handler(MasterPID, SourceMD5, Alphabet)
end.
portion_search(MasterPID, _, ToNumber, ToNumber, _) ->
MasterPID!{not_found, self()};
portion_search(MasterPID, SourceMD5, FromNumber, ToNumber, Alphabet) ->
GeneratedString = generate_string_by_number(FromNumber, Alphabet),
GeneratedStringMD5 = erlang:md5(GeneratedString),
if
SourceMD5 == GeneratedStringMD5 -> MasterPID!{found, GeneratedString};
true -> portion_search(MasterPID, SourceMD5, FromNumber+1, ToNumber, Alphabet)
end.
Метод start_search_handler/0 используется для запуска обработчика, метод search_handler/3 – обработчик сообщений от координатора, в методе portion_search/5 происходит поиск хэша MD5 для строк, чей номер лежит в диапазоне [FromNumber, ToNumber].
Теперь перейдем к координатору:
main_search_handler(MasterPID, SourceMD5, Alphabet, PortionSize, MaxNumber, HandlerPIDList) ->
process_flag(trap_exit, true),
CurrentPID = self(),
lists:foreach(fun(HandlerPID) ->
link(HandlerPID),
HandlerPID ! {are_you_ready, CurrentPID, SourceMD5, Alphabet}
end, HandlerPIDList),
main_search_handler(MasterPID, SourceMD5, Alphabet, 0, PortionSize, MaxNumber, 0).
main_search_handler(MasterPID, _, _, _, _, MaxNumber, ResponseCount)
when ResponseCount >= MaxNumber ->
MasterPID!{not_found},
exit(stop_work);
main_search_handler(MasterPID, SourceMD5, Alphabet, CurrentNumber, PortionSize, MaxNumber, ResponseCount)
when CurrentNumber >= MaxNumber ->
receive
{stop} -> exit(stop_work);
{found, GeneratedString} -> MasterPID!{found, GeneratedString},
exit(stop_work);
{not_found, _} -> main_search_handler(MasterPID, SourceMD5, Alphabet, MaxNumber, PortionSize, MaxNumber,
ResponseCount+PortionSize)
end;
main_search_handler(MasterPID, SourceMD5, Alphabet, CurrentNumber, PortionSize, MaxNumber, ResponseCount) ->
receive
{stop} -> exit(stop_work);
{ready_master, HandlerPID} ->
ToNumber = min(CurrentNumber+PortionSize, MaxNumber+1),
HandlerPID!{search, CurrentNumber, ToNumber},
main_search_handler(MasterPID, SourceMD5, Alphabet, ToNumber, PortionSize, MaxNumber, ResponseCount);
{found, GeneratedString} -> MasterPID!{found, GeneratedString},
exit(stop_work);
{not_found, HandlerPID} ->
ToNumber = min(CurrentNumber+PortionSize, MaxNumber+1),
HandlerPID!{search, CurrentNumber, ToNumber},
main_search_handler(MasterPID, SourceMD5, Alphabet, ToNumber, PortionSize, MaxNumber, ResponseCount+PortionSize)
end.
Метод main_search_handler/6 используется для запуска координатора и отсылки сообщений обработчикам с требованием подтвердить свою готовность; метод main_search_handler/7 используется для взаимодействия с обработчиками.
И, наконец, инициатор. На самом деле у нас два инициатора: один (метод start_search/0) – для запуска простого многозадач-ного поиска на данном узле (экземпляре виртуальной машины), другой (метод start_distributed_search/0) – для запуска распределенного поиска на разных узлах (на одном или разных компьютерах). Самая большая разница между ними в том, как (и где) создаются обработчики (координатор создается на том же узле, что и инициатор). При простом многозадачном поиске обработчики создаются вызовом spawn/1 (версия spawn, в которой не указывается узел). При распределенном поиске обработчики создаются вызовом spawn/2 (версия spawn, в которой указывается узел, где создается процесс). В нашем модельном инициаторе список узлов, на которых будут создаваться процессы, задается прямо в теле метода; в реальном же приложении список узлов будет, скорее всего, браться из конфигурационного файла.
start_distributed_search() ->
Alphabet = [$0, $1, $2, $3, $4, $5, $6, $7, $8, $9],
Source = “01234321”,
SourceMD5 = erlang:md5(Source),
MaxNumber = generate_number_by_string_length(10, length(Alphabet)),
ProcessCount = 4,
PortionSize = 100000,
NodeList = ['node1@beerzone2', 'node2@beerzone2'],
{HandlerPIDList, _} = lists:mapfoldl(fun(_, CurrentNodeList) ->
[NodeHead | NodeOther] = CurrentNodeList,
HandlerPID = spawn(NodeHead, fun() -> start_search_handler() end),
{HandlerPID, NodeOther++[NodeHead]}
end, NodeList, lists:seq(1, ProcessCount)),
Now1 = now(),
CurrentPID = self(),
MainHandlerPID = spawn(fun() -> main_search_handler(CurrentPID, SourceMD5, Alphabet, PortionSize,
MaxNumber, HandlerPIDList) end),
Result = process_response(),
MainHandlerPID!{stop},
Now2 = now(),
{calc_work_time(Now1, Now2), Result}.
start_search() ->
Alphabet = [$0, $1, $2, $3, $4, $5, $6, $7, $8, $9],
Source = “01234321”,
SourceMD5 = erlang:md5(Source),
MaxNumber = generate_number_by_string_length(10, length(Alphabet)),
ProcessCount = 2,
PortionSize = 100000,
HandlerPIDList = [spawn(fun() -> start_search_handler() end) || _ <- lists:seq(1, ProcessCount)],
Now1 = now(),
CurrentPID = self(),
MainHandlerPID = spawn(fun() -> main_search_handler(CurrentPID, SourceMD5, Alphabet, PortionSize,
MaxNumber, HandlerPIDList) end),
Result = process_response(),
MainHandlerPID!{stop},
Now2 = now(),
{calc_work_time(Now1, Now2), Result}.
process_response() ->
receive
Response -> Response
end.
Осталось только привести объявления модуля и экспортируемых функций:
-module(md5_distributed_search). -export([start_search/0, start_distributed_search/0]).
Чтобы запустить распределенный поиск, необходимо сделать следующее. Предположим, что имя компьютера – beerzone2 (как у меня). Мы хотим запустить обработчики на узлах node1@beerzone2, node2@beerzone2. В теле программы, в методе start_distributed_search/0 устанавливаем список узлов NodeList в ['node1@beerzone2', 'node2@beerzone2']. После этого мы создаем три экземпляра консоли: в двух мы запускаем виртуальную машину с ключами -sname node1 и -sname node2, а в третьей – виртуальную машину с ключом -sname main (очень важно, чтобы все взаимодействующие узлы в распределенной системе имели имена одного типа: либо короткие, либо длинные). В главной консоли (запущенной с ключом -sname main) запускаю сначала компиляцию с(md5_distributed_search)., а потом и выполнение нашей программы md5_distributed_search:start_distributed_search(). При запуске на моей машине (ноутбук Acer Aspire 7520G: процессор AMD Turion64 x2 TL-58 1,9 ГГц, 2 ГБ ОЗУ), приложение находит искомую строку “01234321” по ее хэшу MD5 за 76,984 секунды.
В качестве заключения
Итак, написать распределенную систему для решения любой задачи легко. Язык Erlang позволяет создавать любое серверное и распределенное ПО любой сложности, по производительности не уступающее такому же ПО, написанному на других языках, а по качеству кода и надежности сильно превосходящее их.
Полезные сайты и книги
- http://www.erlang.org/ – главный сайт (с документацией и исходным кодом среды).
- http://www.trapexit.org/ – сайт Erlang-сообщества (форум, вики, решения, учебные пособия, справочные материалы).
- http://erlanger.ru/ – сайт русского Erlang-сообщества.
- http://groups.google.com/group/erlang-russian – русское Erlang-сообщество на Google.
- http://www.tryerlang.org/ – онлайн-интерпретатор Erlang.
- Martin Logan, Eric Merritt, and Richard Carlsson “Erlang and OTP in Action”.
- Francesco Cesarini, Simon Thompson “Erlang Programming A Concurrent Approach to Software Development”.
- Joe Armstrong “Programming Erlang: Software for a Concurrent World”.
История Erlang
- 1982–1985 Эксперименты в Ericsson Computer Science Laboratory по программированию в области телекоммуникаций на более чем 20 языках. Вывод: нужен высокоуровневый символический язык для достижения высокой производительности труда (наподобие Lisp, Prolog, Parlog и т.д.).
- 1985–1986 Эксперименты с Lisp, Prolog, Parlog и т.д. Вывод: язык должен содержать примитивы для поддержки параллелизма и восстановления после сбоев. Он должен также поддерживать детализацию параллелизма, чтобы один асинхронный процесс телефонии соответствовал одному процессу в языке. Т.о., было принято решение разработать свой собственный язык, основываясь на Lisp, Prolog и Parlog, но с поддержкой параллелизма и восстановления после сбоев на уровне языка.
- 1987 Первые эксперименты с Erlang.
- 1988 Фаза 1: Прототип показан внешним пользователям. Erlang вышел за пределы лаборатории.
- 1989 Фаза 2: Воссоздана 1/10 полной MD-110 системы. Итог: создание программ более чем в 10 раз эффективнее, чем в PLEX.
- 1990 Erlang представлен на ISS’90, что привело к появлению новых пользователей, например, Bellcore.
- 1991 Версия Erlang выпущена для пользователей. Erlang представлен на Telecom’91. Появилась новая функциональность, такая как ASN/1 – компилятор, графический интерфейс и т.д.
- 1992 Появление большого числа новых пользователей Erlang. Erlang портирован на большинство платформ: VxWorks, PC, Macintosh и т.д.
- 1993 В Erlang добавлена поддержка распределенных вычислений. Принято решение продавать реализацию Erlang внешним организациям.
- 1998 Реализация Erlang становится opensource.
- 2006 Поддержка симметричной многопроцессорности встроена в исполняющую среду и виртуальную машину Erlang.
