Журнал LinuxFormat - перейти на главную

LXF144:erlang

Материал из Linuxformat
Перейти к: навигация, поиск
Подписка на печатную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подписка на электронную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подшивки старых номеров журнала (печатные версии)
Весь 2014 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
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.
Источник — «http://wiki.linuxformat.ru/wiki/index.php?title=LXF144:erlang&oldid=15312»
Персональные инструменты
купить
подписаться
Яндекс.Метрика