автор Ричард Каллос
Wrek - это библиотека Erlang, которую я написал для одновременного выполнения графов зависимостей задач. Его предполагаемая цель - запустить набор заранее определенных задач, между которыми имеется частичный порядок. В этом посте я объясню, почему я написал wrek, для чего его можно использовать и как его использовать.
Мотивация
Рэк возник в результате двух разных сил. Во-первых, мое дилетантское увлечение теорией графов заставило меня попытаться видеть графы везде, где только возможно, что заложило концептуальную основу для этой библиотеки. Во-вторых, я понял, что проект, над которым я работал в Adgear, выиграет от такой библиотеки, в результате чего я наконец начал писать Wrek.
Концептуальный
Граф - это всеобъемлющая структура данных в вычислениях. Когда я узнал об алгоритмах на графах в школе, я был поражен их широким применением. Графы играют важную роль в компиляторах и системах сборки. Различные алгоритмы графов составляют основу того, как мы общаемся друг с другом через Интернет.
Наша повседневная жизнь наполнена списками. У нас есть списки дел, списки покупок, рецепты, контрольные списки, инструкции и многое, многое другое. Однажды я понял, что некоторые из этих списков обманчивы. Некоторые из этих списков на самом деле представляют собой графики, скрытые под одеждой списка; эти списки представляют собой топологические упорядочения ориентированных ациклических графов. Два наиболее очевидных случая этого - списки дел и рецепты. Вы не можете отправить письмо, которое еще не написали, или приготовить спагетти, если вы не вскипятили кастрюлю с водой.
После того, как хитрые графы были обнаружены, я некоторое время размышлял о том, как извлечь выгоду из обработки различных списков, таких как группы DAG, которыми они тайно являются. Самыми явными аналогиями между этими списками и группами DAG были списки дел и рецепты. Они очень напоминали графы зависимостей. В отличие от представления в виде списка, эти графы зависимостей показывают, какие вершины (отдельные задачи) могут выполняться одновременно. Иногда это очевидно (например: я могу нарезать овощи, пока дожидаюсь кипения воды! Я могу начать готовить второй противень печенья, пока первая партия находится в духовке!), Но я надеялся, что акт переформулирования списков в виде графов зависимостей может открыть больше возможностей для параллелизма.
Boil water -- Add pasta -- Cook pasta --.
\
Purée tomatoes --. \
\ \
Chop vegetables -- Combine in saucepan -- Simmer sauce -- Combine pasta and sauce -- Serve
/
Add spices --'
Ребра между вершинами в приведенном выше графе выражают частичный порядок. Вершины, между которыми нет пути, могут выполняться одновременно. Взаимосвязь между вершинами на графе отражает правду на кухне. Пока соус кипит, мы можем приготовить пасту. Неважно, нарезаем ли мы сначала овощи или пюре из помидоров; они оба должны быть готовы, если мы собираемся приготовить какой-нибудь соус.
Несмотря на все мои усилия, я все еще проваливаюсь на кухне. Чтобы изменить этот неудобный факт, я подумал, что было бы интересно попробовать представить рецепты в виде ориентированных графиков с дополнительными данными, например, сколько времени может занять каждый шаг. Это долгое время находилось в моем списке «когда-нибудь проектов», и я вспоминал об этом только тогда, когда начинал думать о проекте, над которым работал в $ JOB.
Практичный
Один из проектов, который я реализовал в прошлом году в Adgear, заключался в удалении дорогостоящих вычислений, которые выполнялись на каждом из наших уже исчерпанных граничных серверов, и замене их системой, которая выполняла дорогостоящие вычисления на одной машине, а затем распределяла результат . Система работала, когда ее никто не трогал, но это был программный эквивалент веток и клейкой ленты; cron и сценарии оболочки. Эту систему по-прежнему было неудобно использовать, и появлялось все больше примеров дорогостоящих вычислений, выполняемых на машинах с дефицитом ЦП. На этом этапе имело смысл начать писать более надежную систему.
Эти дорогостоящие вычисления красиво разложены на списки шагов, которые необходимо выполнить. Получите эти данные, преобразуйте их, трансформируйте еще раз, отправьте некоторые данные на эту группу серверов, отправьте эти другие данные на какую-то другую группу серверов. Сценарии оболочки довольно хорошо кодируют эти конвейеры, поэтому во время реализации это был приемлемый выбор. Через некоторое время меня осенило, что эти списки шагов на самом деле не были списками; они были графами зависимостей. Я попытался раскрыть скрытый параллелизм в сценариях оболочки, приправив их некоторыми фоновыми заданиями и waitpid, но было решено, что имеет смысл перейти на Erlang и извлечь выгоду из всего, что может предложить OTP.
Давай получим "Wrek" ed
(Прошу прощения. Я не удержался.)
Wrek принимает в качестве входных данных графы зависимостей, подобные приведенному выше рецепту спагетти, и выполняет каждую вершину. Природа одновременного выполнения действий, как только они могут выполняться, является общим для любой проблемы, которая может быть представлена графом зависимостей. Структура графа зависимостей, а также задачи, задействованные в каждой из вершин графа, специфичны по желанию пользователя. Следуя тому же общему / конкретному разделению, что и OTP; общая часть этого класса проблем решается модулями wrek и wrek_vert. Конкретная часть предоставляется пользователем в виде карты Erlang, описывающей каждую вершину в графе, и набора модулей обратного вызова, реализующих поведение wrek_vert .
Поведение wrek_vert состоит из одного обратного вызова run/2, где первый аргумент - это список аргументов, которые должны быть отправлены функции обратного вызова, а второй аргумент - это идентификатор процесса, который может предоставить информацию, сгенерированную другие вершины. Ожидаемый результат этой функции обратного вызова:
{ok, Any :: any()} или {error, Reason :: any()}. Если функция обратного вызова завершится успешно, Any будет принят wrek и станет доступным для других wrek_vert процессов. Если функция обратного вызова дает сбой или возвращает ошибку, весь график будет отключен.
Приготовление пасты Эрланг
Следуя надуманному примеру, приведенному выше, давайте приступим к использованию обломков для приготовления макарон. Конечно, наша программа на самом деле не будет делать макароны, но ее результат должен кого-то обмануть.
Глядя на приведенный выше график, кажется, что каждый шаг выполняет одно из трех:
- Добавить ингредиент
- Смешайте ингредиенты в сосуде
- Сделайте что-нибудь с ингредиентами в сосуде
Давайте запишем несколько wrek_vert для каждого из этих действий. Если вам не хочется следовать указаниям в текстовом редакторе, полный код можно найти здесь.
-module(cook_add).
-behaviour(wrek_vert).
-export([run/2]).
run([Ingredient, Quantity], _Pid) ->
io:format(“adding ~s. amount: ~s.~n”, [Ingredient, Quantity]),
{ok, #{added => [{Ingredient, Quantity}]}}.
Это все для cook_add. Он печатает сообщение, а затем создает карту с добавленным ключом, значением которого является проплист с единственной парой.
-module(cook_heat).
-behaviour(wrek_vert).
-export([run/2]).
run([Verb, Noun], _Pid) ->
io:format("~ping ~p.~n", [Verb, Noun]),
{ok, #{}}.
cook_heat тоже довольно короткий. Это тоже очень абстрактно. Его можно использовать для печати сообщения о Verb употреблении любых Noun, а не только ингредиентов для приготовления!
Наш последний модуль обратного вызова немного длиннее, потому что он делает немного больше, чем просто печать сообщения.
-module(cook_combine).
-behaviour(wrek_vert).
-export([run/2]).
run([Ingredients, Vessel], Pid) ->
Fun = fun(Step, Acc) ->
Stuff = wrek_vert:get(Pid, Step, added),
io:format("combining ~p with ~p in ~p.~n", [Stuff, Acc, Vessel]),
Stuff ++ Acc
end,
Stuff = lists:foldl(Fun, [], Ingredients),
io:format("~p now contains: ~p.~n", [Vessel, Stuff]),
{ok, #{added => Stuff}}.
Ожидается, что Ingredients будет списком имен вершин. Наконец, мы используем Pid нашего родительского процесса в качестве аргумента для wrek_vert:get/3. Это позволяет нам использовать данные, созданные модулем обратного вызова cook_add . Соединив все, мы возвращаем новую коллекцию ингредиентов.
Хорошо! Мы почти закончили описывать конкретную часть нашей проблемы! Последний шаг - представить наш граф зависимостей в терминах этих модулей обратного вызова и аргументов, которые мы хотим им передать.
-module(wrek_example).
-export([make_pasta/0]).
make_pasta() ->
application:ensure_all_started(wrek),
Graph = #{
tomatoes => #{
module => cook_add,
args => ["pureed tomatoes", "1 can"],
deps => []
},
vegetables => #{
module => cook_add,
args => ["chopped vegetables", "lots"],
deps => []
},
spices => #{
module => cook_add,
args => ["spices", "to taste"],
deps => []
},
saucepan => #{
module => cook_combine,
args => [[tomatoes, vegetables, spices], saucepan],
deps => [tomatoes, vegetables, spices]
},
simmer_sauce => #{
module => cook_heat,
args => [simmer, sauce],
deps => [saucepan]
},
boil_water => #{
module => cook_heat,
args => [boil, water],
deps => []
},
add_pasta => #{
module => cook_add,
args => ["pasta", "1 handful"],
deps => [boil_water]
},
cook_pasta => #{
module => cook_heat,
args => [cook, pasta],
deps => [add_pasta]
},
mix_pasta_with_sauce => #{
module => cook_combine,
args => [[saucepan, add_pasta], saucepan],
deps => [simmer_sauce, cook_pasta]
}
},
wrek:start(Graph).
Замечательно! Здесь мы создали карту Erlang, ключи которой представляют имена вершин в нашем исходном графе зависимостей, а значениями являются карты, которые определяют модуль обратного вызова, аргументы для передачи в модуль обратного вызова, а также любые зависимости вершины. можно иметь. Поздравляю тех из вас, кто заметил, что мы никогда не процеживаем макароны; Я признался, что устроил катастрофу на кухне. Обещаю, я усвоил урок.
Хорошо, мы закончили кодирование! Давайте запустим ракушку и приготовим макароны!
Прочтите оставшуюся часть этого сообщения в блоге на codeync.global.
Присоединяйтесь к Ричарду Каллосу, разработчику AdGear, в CodeBEAM SF, где он расскажет о wrek.
Первоначально опубликовано на codeync.global.
