Конкурентність і паралелізм в Elixir

Це друга частина серії Percy Grunwald про Elixir. Не пропустімо першу статтю про зіставлення Unicode в Elixir.

Вправи на Exercism невеликі, синтетичні й часто здаються тривіальними. Легко уявити, що досвідченим практикам нічого з них почерпнути. Однак розвʼязування цих синтетичних задач може підштовхнути нас до вивчення й застосування тих частин мови, які ми, можливо, ще не досліджували. Ці нові знання можуть допомогти нам розвʼязувати реальні задачі ефективніше чи виразніше.

Паралельна частота літер - це вправа середньої складності на треку Elixir від Exercism, яка розкриває напрочуд багато цікавих уроків. Щоб успішно розвʼязати цю задачу, наше рішення має виконуватися паралельно в кількох робочих процесах. Досягти справжнього паралелізму в Elixir напрочуд легко порівняно з іншими мовами, але якщо ми ніколи не писали конкурентного коду в Elixir, це може здатися трохи лячним. Розвʼязуючи цю вправу, ми виявимо, зокрема, наскільки легко в Elixir писати код, який може виконуватися конкурентно або паралельно. Застосування цих навичок у нашому коді може суттєво вплинути на продуктивність наших застосунків.

У цій вправі потрібно реалізувати функцію Frequency.frequency/2, яка визначає частоту літер у масиві рядків тексту (англ. string). Обчислення має виконуватися в кількох робочих процесах, кількість яких задає аргумент workers:

iex> Frequency.frequency(["Freude", "schöner", "Götterfunken"], workers)
%{
  "c" => 1,
  "d" => 1,
  "e" => 5,
  ...
  "ö" => 2
}

У цій статті ми дослідимо конкурентність в Elixir, зробивши робоче послідовне рішення цієї вправи конкурентним. Однак перш ніж поринути в код, приділімо хвилинку тому, що насправді означають «конкурентність» і «паралелізм» і як досягти обох в Elixir порівняно з іншими мовами.

Конкурентність і паралелізм

Конкурентність і паралелізм - споріднені терміни, але вони означають не зовсім одне й те саме. Конкурентна програма - це така програма, де кілька задач можуть бути «в процесі виконання», але в кожен окремий момент часу на CPU виконується лише одна задача (наприклад, виконується одна задача, поки інша чекає на IO, як-от читання чи запис на диск або в мережу). З іншого боку, паралельна програма здатна виконувати кілька задач водночас на кількох ядрах CPU.

І конкурентне, і паралельне виконання може дати суттєве прискорення, але можливий обсяг прискорення (якщо він узагалі можливий) залежить від багатьох чинників. Бувають випадки, коли конкурентність чи паралелізм узагалі неможливі: можливо, задача, яку ми намагаємося виконати, не піддається ні конкурентному, ні паралельному виконанню, або ж середовище виконання їх не підтримує. Якщо ж наш випадок таки дозволяє конкурентне чи паралельне виконання, можливе прискорення здебільшого залежить від того, чи обмежена задача IO, чи CPU, і від того, чи доступно більше ніж 1 ядро CPU.

Попри кількість чинників, що впливають на це, є кілька практичних правил, які допомагають визначити, чи можливі конкурентність або паралелізм і на яке прискорення очікувати. По-перше, конкурентне виконання можливе на одному ядрі CPU, а паралельне - ні. По-друге, і паралелізм, і конкурентність мають давати суттєве прискорення для задач, обмежених IO, і це прискорення має бути приблизно однаковим в обох випадках. І нарешті, задачі, обмежені CPU, за конкурентного виконання мають ту саму (або гіршу) продуктивність, і загалом прискорення можливе лише за паралельного виконання на кількох ядрах CPU.

Обчислення частоти літер у цій вправі - приклад задачі, обмеженої CPU, тож згідно з наведеними вище практичними правилами прискорення має бути можливим лише за паралельного обчислення на кількох ядрах CPU.

Конкурентність і паралелізм в Elixir та інших мовах

Багато популярних мов дають нам інструменти для написання конкурентного коду, але досягти паралелізму зазвичай набагато складніше, і тут доводиться йти на компроміси.

Наприклад, конкурентність є невідʼємною складовою JavaScript, що працює на середовищі виконання Node.js, а типові версії функцій, повʼязаних з IO, майже завжди «асинхронні» (тобто конкурентні). Наприклад, fs.ReadFile - конкурентна функція і стандартний спосіб прочитати вміст файлу. Це чудово, але має й недоліки: пекло колбеків або потребу в Promise. Крім того, оскільки Node не розподіляє час CPU рівномірно між задачами, виконання все ще можна заблокувати однією задачею, інтенсивною щодо CPU. Розпаралелити виконання в Node можливо, але аж ніяк не легко. З огляду на те, що Node є однопотоковим, єдиний спосіб досягти паралелізму - вручну породжувати робочі процеси модулем cluster або запускати кілька екземплярів нашої програми й вручну реалізовувати обмін даними між ними.

Python, на відміну від Node, не є конкурентним типово, але дає кілька інструментів для написання конкурентного й паралельного коду. Однак кожен варіант має свої компроміси, і вибір одного з них не обовʼязково очевидний. Можна скористатися модулем threading і змиритися з тим, що global interpreter lock (GIL) обмежує виконання одним потоком за раз, унеможливлюючи паралелізм. Інший варіант - модуль multiprocessing у Python, який обходить обмеження GIL, породжуючи процеси ОС (а не потоки). Використання multiprocessing уможливлює паралелізм, але має компроміс: процеси ОС повільніше породжувати, і вони споживають більше памʼяті, ніж потоки.

Писати конкурентний і паралельний код в Elixir набагато простіше, адже Elixir конкурентний на рівні середовища виконання. Репутація Elixir як надзвичайно масштабованої мови походить від того, що вона працює на віртуальній машині BEAM, яка виконує весь код у надзвичайно легковагих «процесах», що всі виконуються конкурентно всередині VM. Породження процесів BEAM коштує мізерно, і вони споживають крихітні обсяги памʼяті порівняно з потоками й процесами рівня ОС, які породжують модулі конкурентності Python. Крім того, на відміну від циклу подій Node, віртуальна машина BEAM має планувальники, які розподіляють доступний час CPU між усіма процесами, що гарантує: одна задача, інтенсивна щодо CPU, не може заблокувати виконання інших процесів.

Завдяки цій архітектурі перехід від конкурентного виконання процесів до паралельного - це просто питання додавання більшої кількості ядер CPU. Насправді вже багато років BEAM автоматично вмикає можливості симетричної мультипроцесорності (SMP) на багатоядерних системах, що дозволяє планувальникам VM розподіляти час CPU з усіх ядер між запущеними процесами. В Elixir конкурентність не лише невідʼємна складова: тут немає різниці між конкурентним і паралельним кодом. Усе, що потрібно, - писати конкурентний код, а VM автоматично й типово розпаралелить його, якщо доступно більше ніж 1 ядро CPU.

Написання конкурентного коду Elixir з модулем Task

Як зазначено вище, в Elixir конкурентності досягають, розподіляючи операції між кількома процесами BEAM. Ми можемо дуже легко породжувати процеси такими функціями, як Kernel.spawn_link/1, але набагато краще скористатися надзвичайно потужними абстракціями, які надає модуль Task:

Найпоширеніший випадок використання [Task] - перетворення послідовного коду на конкурентний шляхом асинхронного обчислення значення.

Модуль Task дозволяє писати неймовірно чистий конкурентний код в Elixir: жодного пекла колбеків і жодної потреби в Promises.

Для цієї вправи чудовим варіантом є Task.async_stream/3:

async_stream(enumerable, function, options \\ [])

Task.async_stream/3 повертає потік, який виконує задану function конкурентно для кожного елемента в enumerable. Типово кількість породжених процесів (робочих процесів) дорівнює кількості елементів у enumerable. Це дає нам простий спосіб керувати рівнем паралелізму за допомогою аргументу workers (за умови, що в нас достатньо ядер CPU). Усе, що потрібно, - розбити масив літер на потрібну кількість частин і за допомогою Task.async_stream/3 обробити кожну частину в окремому робочому процесі.

Робимо послідовну функцію частоти літер конкурентною

Почнімо з робочої послідовної реалізації з мого рішення:

def frequency(texts, _workers) do
  texts
  |> get_all_graphemes()
  |> count_letters()
end

defp get_all_graphemes(texts) do
  texts
  |> Enum.join()
  |> String.graphemes()
end

defp count_letters(graphemes) do
  Enum.reduce(graphemes, %{}, fn grapheme, acc ->
    if String.match?(grapheme, ~r/^\p{L}$/u) do
      downcased_letter = String.downcase(grapheme)
      Map.update(acc, downcased_letter, 1, fn count -> count + 1 end)
    else
      acc
    end
  end)
end

Ми можемо зробити наведену вище реалізацію конкурентною так:

1. Розбити масив графем, який повертає get_all_graphemes/1, на кількість частин, що дорівнює кількості workers
2. Обробити кожну частину за допомогою count_letters/1 у робочому процесі, використавши Task.async_stream/3
3. Обʼєднати результати з кожного робочого процесу в один результат

Ось діаграма наведених вище кроків:

Щоб увімкнути конкурентну логіку, нам потрібно реалізувати лише 2 нові допоміжні функції: одну для розбиття графем на частини (split_into_chunks/2) і одну для обʼєднання stream результатів від робочих процесів (merge_results/1). Ось один зі способів реалізувати ці допоміжні функції:

defp split_into_chunks(all_graphemes, num_chunks) do
  all_graphemes_count = Enum.count(all_graphemes)
  graphemes_per_chunk = :erlang.ceil(all_graphemes_count / num_chunks)

  Enum.chunk_every(all_graphemes, graphemes_per_chunk)
end

defp merge_results_stream(results_stream) do
  Enum.reduce(results_stream, %{}, fn {:ok, worker_result}, acc ->
    Map.merge(acc, worker_result, fn _key, acc_val, worker_val ->
      acc_val + worker_val
    end)
  end)
end

Коли ці 2 функції реалізовано, щоб змусити функцію frequency/2 виконуватися конкурентно, залишається лише додати виклики нових допоміжних функцій і замінити прямий виклик count_letters/1 на Task.async_stream/3:

def frequency(texts, workers) do
  texts
  |> get_all_graphemes()
  |> split_into_chunks(workers)
  |> Task.async_stream(&count_letters/1)
  |> merge_results_stream()
end

Наведена вище функція - цілком робоча конкурентна реалізація, яка проходить усі тести. Попри конкурентність, код читається точно як звичайний послідовний код, що демонструє силу абстракцій, наданих у Task.

Чи справді конкурентна версія паралельна?

Як я вже згадував раніше в статті, в Elixir немає різниці між конкурентним і паралельним кодом. Якщо ми встановимо workers у число, більше за 1, і маємо більше ніж 1 ядро CPU, віртуальна машина BEAM автоматично розпаралелює виконання породжених процесів.

Типово BEAM запускає по одному планувальнику на кожне доступне (логічне) ядро CPU. Кількість планувальників, які запустила BEAM, можна перевірити за допомогою :erlang.system_info/1:

iex> :erlang.system_info(:schedulers_online)
8

Це максимальна кількість процесів VM, які можуть виконуватися водночас. Якщо встановити workers у число більше за кількість планувальників, це не збільшить паралелізм і може зашкодити продуктивності.

Висновок

Перетворити код із послідовного на конкурентний за допомогою модуля Task в Elixir виявилося набагато легше, ніж очікувалося. Конкурентний код додає трохи складності в розбитті масиву графем і обʼєднанні результатів робочих процесів, але кінцевий результат напрочуд чистий.

До того як розвʼязати цю задачу на Exercism, я чув про Task, але ніколи його не використовував. Після того як я застосував його у своєму рішенні, я тепер вважаю його незамінною частиною свого набору інструментів Elixir.

Цей новий інструмент можна використовувати в багатьох способах, щоб спробувати оптимізувати продуктивність наших застосунків. Більшість вебзастосунків обмежені IO, тож вони виграють від конкурентності, навіть якщо доступне лише одне ядро CPU. Один досить надійний спосіб прискорити вебзастосунок - виконувати HTTP-запити конкурентно:

def call_apis_async() do
  ["https://api.example.com/users/123", ...]
  |> Task.async_stream(&HTTPoison.get/1)
  |> Enum.into([], fn {:ok, res} -> res end)
end

Наведений вище код застосовує Task.async_stream/3, щоб конкурентно викликати всі URL зі списку, замість того щоб чекати на завершення кожного запиту перед початком наступного, що має дати суттєве прискорення залежно від тривалості кожного запиту.