Ταυτοχρονισμός και παραλληλισμός στην Elixir

Αυτό είναι το δεύτερο μέρος της σειράς του Percy Grunwald για την Elixir. Μη χάσεις το πρώτο άρθρο για την Αντιστοίχιση Unicode στην Elixir.

Οι ασκήσεις στο Exercism είναι μικρές, τεχνητές και συχνά φαινομενικά ασήμαντες. Είναι εύκολο να φανταστείς ότι έμπειροι επαγγελματίες δεν έχουν τίποτα να μάθουν από αυτές. Ωστόσο, η επίλυση αυτών των τεχνητών προβλημάτων μπορεί να σε ωθήσει να μάθεις και να εφαρμόσεις κομμάτια της γλώσσας σου που μπορεί να μην έχεις εξερευνήσει. Αυτή η νέα γνώση μπορεί να σε οδηγήσει να λύνεις προβλήματα του πραγματικού κόσμου πιο αποδοτικά ή πιο εκφραστικά.

Η Παράλληλη Συχνότητα Γραμμάτων είναι μια άσκηση μέτριας δυσκολίας στη διαδρομή Elixir του Exercism που ξεδιπλώνει έναν εκπληκτικό αριθμό ενδιαφέροντων διδαγμάτων. Για να λύσεις επιτυχώς αυτό το πρόβλημα, η λύση σου θα πρέπει να εκτελείται παράλληλα σε πολλαπλές διεργασίες worker. Το να πετύχεις πραγματικό παραλληλισμό στην Elixir είναι εκπληκτικά εύκολο σε σύγκριση με άλλες γλώσσες, αλλά αν δεν έχεις γράψει ποτέ ταυτόχρονο κώδικα στην Elixir, μπορεί να φαίνεται λίγο αποθαρρυντικό. Ένα από τα πράγματα που θα ανακαλύψεις λύνοντας αυτή την άσκηση είναι πόσο εύκολο κάνει η Elixir το να γράψεις κώδικα που μπορεί να εκτελεστεί ταυτόχρονα ή παράλληλα. Η εφαρμογή αυτών των δεξιοτήτων στον κώδικά σου μπορεί να έχει σημαντικό αντίκτυπο στην απόδοση των εφαρμογών σου.

Αυτή η άσκηση απαιτεί να υλοποιήσεις μια συνάρτηση, τη Frequency.frequency/2, που υπολογίζει τη συχνότητα γραμμάτων σε μια λίστα από συμβολοσειρές. Ο υπολογισμός θα πρέπει να γίνεται σε αρκετές διεργασίες worker, ο αριθμός των οποίων ορίζεται από το όρισμα workers:

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

Σε αυτό το άρθρο, θα εξερευνήσουμε τον ταυτοχρονισμό στην Elixir μετατρέποντας μια λειτουργική σειριακή λύση αυτής της άσκησης σε ταυτόχρονη. Ωστόσο, πριν βουτήξουμε στον κώδικα, ας αφιερώσουμε λίγο χρόνο για να εξετάσουμε τι σημαίνουν στην πραγματικότητα ο "ταυτοχρονισμός" και ο "παραλληλισμός", και πώς να πετύχεις και τα δύο στην Elixir εναντίον άλλων γλωσσών.

Ταυτοχρονισμός και παραλληλισμός

Ο ταυτοχρονισμός και ο παραλληλισμός είναι σχετικοί όροι, αλλά δεν σημαίνουν ακριβώς το ίδιο πράγμα. Ένα ταυτόχρονο πρόγραμμα είναι ένα πρόγραμμα όπου πολλαπλές εργασίες μπορούν να βρίσκονται "σε εξέλιξη", αλλά σε οποιαδήποτε δεδομένη χρονική στιγμή μόνο μία εργασία εκτελείται στην CPU (για παράδειγμα, εκτελείται μια εργασία ενώ μια άλλη περιμένει IO, όπως ανάγνωση ή εγγραφή στον δίσκο ή στο δίκτυο). Από την άλλη, ένα παράλληλο πρόγραμμα μπορεί να εκτελεί πολλαπλές εργασίες την ίδια στιγμή σε πολλαπλούς πυρήνες CPU.

Τόσο η ταυτόχρονη όσο και η παράλληλη εκτέλεση μπορούν να δώσουν σημαντικές αυξήσεις ταχύτητας, αλλά το μέγεθος της επιτάχυνσης που είναι εφικτό, αν υπάρχει, εξαρτάται από πολλούς παράγοντες. Υπάρχουν περιπτώσεις στις οποίες ο ταυτοχρονισμός ή ο παραλληλισμός δεν είναι καν εφικτά. Μπορεί η εργασία που προσπαθείς να ολοκληρώσεις να μην προσφέρεται ούτε για ταυτόχρονη ούτε για παράλληλη εκτέλεση, ή το περιβάλλον εκτέλεσης να μην τα υποστηρίζει. Αν η περίπτωσή σου επιτρέπει ταυτόχρονη ή παράλληλη εκτέλεση, το μέγεθος της επιτάχυνσης που είναι εφικτό εξαρτάται σε μεγάλο βαθμό από το αν η εργασία είναι IO-bound ή CPU-bound, και από το αν υπάρχει διαθέσιμος περισσότερος από 1 πυρήνας CPU.

Παρά τον αριθμό των παραγόντων που συμβάλλουν, υπάρχουν μερικοί "εμπειρικοί κανόνες" για να προσδιορίσεις αν ο ταυτοχρονισμός ή ο παραλληλισμός είναι εφικτός και πόση επιτάχυνση να περιμένεις. Πρώτον, η ταυτόχρονη εκτέλεση είναι εφικτή σε έναν μόνο πυρήνα CPU, αλλά η παράλληλη εκτέλεση δεν είναι. Δεύτερον, ο παραλληλισμός και ο ταυτοχρονισμός θα πρέπει να δίνουν σημαντική επιτάχυνση σε εργασίες IO-bound, και η επιτάχυνση θα πρέπει να είναι ουσιαστικά ίδια και για τα δύο. Τέλος, οι εργασίες CPU-bound θα πρέπει να έχουν την ίδια (ή χειρότερη) απόδοση όταν εκτελούνται ταυτόχρονα, και γενικά αυξήσεις ταχύτητας είναι δυνατές μόνο όταν εκτελούνται παράλληλα σε πολλαπλούς πυρήνες CPU.

Ο υπολογισμός της συχνότητας γραμμάτων σε αυτή την άσκηση είναι ένα παράδειγμα εργασίας CPU-bound, οπότε σύμφωνα με τους εμπειρικούς κανόνες παραπάνω, αύξηση ταχύτητας θα πρέπει να είναι εφικτή μόνο κάνοντας τον υπολογισμό παράλληλα σε πολλαπλούς πυρήνες CPU.

Ταυτοχρονισμός και παραλληλισμός στην Elixir εναντίον άλλων γλωσσών

Πολλές δημοφιλείς γλώσσες σου δίνουν εργαλεία για να γράψεις ταυτόχρονο κώδικα, αλλά το να πετύχεις παραλληλισμό είναι συνήθως πολύ πιο περίπλοκο και γεμάτο συμβιβασμούς.

Για παράδειγμα, ο ταυτοχρονισμός είναι πολίτης πρώτης κατηγορίας στη JavaScript που τρέχει στο περιβάλλον εκτέλεσης Node.js, και οι προεπιλεγμένες εκδόσεις των συναρτήσεων που σχετίζονται με IO είναι σχεδόν πάντα "ασύγχρονες" (δηλαδή ταυτόχρονες). Για παράδειγμα, η fs.ReadFile είναι μια ταυτόχρονη συνάρτηση και ο καθιερωμένος τρόπος για να διαβάσεις τα περιεχόμενα ενός αρχείου. Αυτό είναι εξαιρετικό, αλλά έχει και τα μειονεκτήματά του με τη μορφή της κόλασης των callbacks, ή της ανάγκης για Promises. Επίσης, επειδή το Node δεν κατανέμει τον χρόνο CPU ισόποσα μεταξύ των εργασιών, είναι ακόμα δυνατό να μπλοκάρεις την εκτέλεση με μία μόνο εργασία που καταναλώνει πολλή CPU. Ο παραλληλισμός της εκτέλεσης στο Node είναι εφικτός, αλλά σίγουρα όχι εύκολος. Δεδομένου ότι το Node είναι μονονηματικό, ο μόνος τρόπος για να πετύχεις παραλληλισμό είναι να δημιουργήσεις χειροκίνητα διεργασίες worker με το module cluster ή να τρέξεις πολλαπλά στιγμιότυπα του προγράμματός σου και να υλοποιήσεις χειροκίνητα την επικοινωνία μεταξύ τους.

Η Python, σε αντίθεση με το Node, δεν είναι ταυτόχρονη από προεπιλογή, αλλά σου δίνει πολλά εργαλεία για να γράψεις ταυτόχρονο και παράλληλο κώδικα. Ωστόσο, κάθε επιλογή έχει συμβιβασμούς και το να διαλέξεις μία δεν είναι απαραίτητα απλό. Θα μπορούσες να χρησιμοποιήσεις το module threading και να αντιμετωπίσεις το γεγονός ότι ο global interpreter lock (GIL) περιορίζει την εκτέλεση σε ένα μόνο νήμα τη φορά, κάνοντας τον παραλληλισμό αδύνατο. Η άλλη επιλογή είναι το module multiprocessing της Python, που παρακάμπτει τον περιορισμό του GIL δημιουργώντας διεργασίες του λειτουργικού συστήματος (σε αντίθεση με νήματα). Η χρήση του multiprocessing κάνει τον παραλληλισμό εφικτό, αλλά έχει το μειονέκτημα ότι οι διεργασίες του λειτουργικού συστήματος αργούν περισσότερο να δημιουργηθούν και χρησιμοποιούν περισσότερη μνήμη από τα νήματα.

Το να γράψεις ταυτόχρονο και παράλληλο κώδικα στην Elixir είναι πολύ πιο απλό, αφού η Elixir είναι ταυτόχρονη στο επίπεδο του περιβάλλοντος εκτέλεσης. Η φήμη της Elixir για τεράστια κλιμάκωση προέρχεται από το γεγονός ότι τρέχει στην εικονική μηχανή BEAM, η οποία εκτελεί όλο τον κώδικα μέσα σε εξαιρετικά ελαφριές "διεργασίες" που τρέχουν όλες ταυτόχρονα μέσα στην VM. Οι διεργασίες της BEAM έχουν αμελητέο κόστος δημιουργίας και χρησιμοποιούν ελάχιστη μνήμη σε σύγκριση με τα νήματα και τις διεργασίες επιπέδου λειτουργικού συστήματος που δημιουργούν τα modules ταυτοχρονισμού της Python. Επίσης, σε αντίθεση με τον βρόχο συμβάντων του Node, η VM της BEAM έχει schedulers που κατανέμουν τον διαθέσιμο χρόνο CPU σε όλες τις διεργασίες, κάτι που διασφαλίζει ότι μία μόνο εργασία που καταναλώνει πολλή CPU δεν μπορεί να εμποδίσει την εκτέλεση άλλων διεργασιών.

Λόγω αυτής της αρχιτεκτονικής, το πέρασμα από την ταυτόχρονη εκτέλεση διεργασιών στην παράλληλη εκτέλεση είναι απλώς θέμα προσθήκης περισσότερων πυρήνων CPU. Στην πραγματικότητα, εδώ και πολλά χρόνια η BEAM ενεργοποιεί αυτόματα τις δυνατότητες Συμμετρικής Πολυεπεξεργασίας (SMP) σε συστήματα με πολλούς πυρήνες, κάτι που επιτρέπει στους schedulers της VM να κατανέμουν χρόνο CPU από όλους τους πυρήνες στις διεργασίες που εκτελούνται. Στην Elixir, όχι μόνο ο ταυτοχρονισμός είναι πολίτης πρώτης κατηγορίας, αλλά δεν υπάρχει και καμία διάκριση μεταξύ ταυτόχρονου και παράλληλου κώδικα. Το μόνο που χρειάζεται να κάνεις είναι να γράψεις ταυτόχρονο κώδικα και η VM θα τον παραλληλοποιήσει αυτόματα και από προεπιλογή, αν υπάρχει διαθέσιμος περισσότερος από 1 πυρήνας CPU.

Γράφοντας ταυτόχρονο κώδικα Elixir με το module Task

Όπως αναφέρθηκε παραπάνω, στην Elixir ο ταυτοχρονισμός επιτυγχάνεται κατανέμοντας εργασίες σε πολλαπλές διεργασίες της BEAM. Μπορείς πολύ εύκολα να δημιουργήσεις διεργασίες με συναρτήσεις όπως η Kernel.spawn_link/1, αλλά είναι πολύ καλύτερα να χρησιμοποιήσεις τις εξαιρετικά ισχυρές αφαιρέσεις που παρέχει το module Task:

Η πιο συνηθισμένη χρήση του [Task] είναι να μετατρέψεις σειριακό κώδικα σε ταυτόχρονο υπολογίζοντας μια τιμή ασύγχρονα.

Το module Task σου επιτρέπει να γράψεις απίστευτα καθαρό ταυτόχρονο κώδικα στην Elixir, χωρίς κόλαση των callbacks και χωρίς ανάγκη για Promises.

Για αυτή την άσκηση, η Task.async_stream/3 είναι εξαιρετική επιλογή:

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

Η Task.async_stream/3 επιστρέφει ένα stream που εκτελεί τη δεδομένη function ταυτόχρονα σε κάθε στοιχείο του enumerable. Από προεπιλογή, ο αριθμός των διεργασιών που δημιουργούνται (workers) είναι ίσος με τον αριθμό των στοιχείων του enumerable. Αυτό μας δίνει έναν απλό τρόπο να ελέγχουμε το επίπεδο παραλληλισμού με το όρισμα workers (υποθέτοντας ότι έχουμε αρκετούς πυρήνες CPU). Το μόνο που χρειάζεται να κάνουμε είναι να χωρίσουμε τη λίστα των γραμμάτων στον σωστό αριθμό τμημάτων και να χρησιμοποιήσουμε την Task.async_stream/3 για να επεξεργαστούμε κάθε τμήμα σε ξεχωριστό worker.

Κάνοντας τη σειριακή συνάρτηση συχνότητας γραμμάτων ταυτόχρονη

Ας ξεκινήσουμε με μια λειτουργική σειριακή υλοποίηση από τη λύση μου:

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. Να χωρίσεις τη λίστα των graphemes που επιστρέφει η get_all_graphemes/1 σε αριθμό τμημάτων ίσο με τον αριθμό των workers
2. Να επεξεργαστείς κάθε τμήμα με την count_letters/1 σε έναν worker χρησιμοποιώντας την Task.async_stream/3
3. Να συγχωνεύσεις τα αποτελέσματα από κάθε worker σε ένα μόνο αποτέλεσμα

Ακολουθεί ένα διάγραμμα των παραπάνω βημάτων:

Χρειάζεται να υλοποιήσουμε μόνο 2 νέες βοηθητικές συναρτήσεις για να ενεργοποιήσουμε την ταυτόχρονη λογική: μία για να χωρίσουμε τα graphemes σε τμήματα (split_into_chunks/2) και μία για να συγχωνεύσουμε το stream των αποτελεσμάτων από τους workers (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

Η παραπάνω συνάρτηση είναι μια πλήρως λειτουργική ταυτόχρονη υλοποίηση και περνάει όλα τα tests. Παρόλο που είναι ταυτόχρονη, ο κώδικας διαβάζεται ακριβώς όπως ο συνηθισμένος σειριακός κώδικας, κάτι που δείχνει τη δύναμη των αφαιρέσεων που παρέχει το Task.

Είναι πραγματικά παράλληλη η ταυτόχρονη έκδοση;

Όπως ανέφερα νωρίτερα στο άρθρο, δεν υπάρχει διάκριση μεταξύ ταυτόχρονου και παράλληλου κώδικα στην Elixir. Αν ορίσουμε το workers σε έναν αριθμό μεγαλύτερο του 1, και έχουμε διαθέσιμο περισσότερο από 1 πυρήνα CPU, η VM της BEAM παραλληλοποιεί αυτόματα την εκτέλεση των διεργασιών που δημιουργήθηκαν.

Από προεπιλογή, η BEAM ξεκινά έναν scheduler για κάθε διαθέσιμο (λογικό) πυρήνα CPU. Μπορείς να ελέγξεις τον αριθμό των schedulers που έχει ξεκινήσει η BEAM με την :erlang.system_info/1:

iex> :erlang.system_info(:schedulers_online)
8

Αυτό αντιπροσωπεύει τον μέγιστο αριθμό διεργασιών της VM που μπορούν να εκτελούνται ταυτόχρονα. Ο ορισμός του workers σε έναν αριθμό μεγαλύτερο από τον αριθμό των schedulers δεν αυξάνει τον παραλληλισμό και μπορεί να βλάψει την απόδοση.

Συμπέρασμα

Η μετατροπή του κώδικα από σειριακό σε ταυτόχρονο αποδεικνύεται πολύ πιο εύκολη από το αναμενόμενο με το module Task της Elixir. Ο ταυτόχρονος κώδικας προσθέτει λίγη επιπλέον πολυπλοκότητα στον διαχωρισμό της λίστας των graphemes και στον συνδυασμό των αποτελεσμάτων των workers, αλλά το τελικό αποτέλεσμα είναι εκπληκτικά καθαρό.

Πριν λύσω αυτό το πρόβλημα του Exercism είχα ακούσει για το Task, αλλά δεν το είχα χρησιμοποιήσει ποτέ. Αφού το εφάρμοσα στη λύση μου, τώρα θα το θεωρούσα αναπόσπαστο κομμάτι της εργαλειοθήκης μου για την Elixir.

Θα μπορούσες να χρησιμοποιήσεις αυτό το νέο εργαλείο με πολλούς τρόπους για να προσπαθήσεις να βελτιστοποιήσεις την απόδοση στις εφαρμογές σου. Οι περισσότερες web εφαρμογές είναι IO-bound και επομένως θα επωφελούνταν από τον ταυτοχρονισμό ακόμα και αν υπάρχει μόνο ένας πυρήνας CPU διαθέσιμος. Ένας αρκετά αξιόπιστος τρόπος για να επιταχύνεις μια web εφαρμογή είναι να κάνεις HTTP requests ταυτόχρονα:

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 για να καλέσει όλα τα URLs της λίστας ταυτόχρονα, αντί να περιμένει να ολοκληρωθεί κάθε αίτημα πριν ξεκινήσει το επόμενο, κάτι που θα πρέπει να δίνει σημαντική επιτάχυνση ανάλογα με τη διάρκεια κάθε αιτήματος.