Jak wykorzystałem schedulera na przykładzie Erlanga i Akki

23 lipca 2018 Tomasz Kowal

W zawodzie programisty bardzo ważny jest dobór narzędzi. Odpowiednio dobrany język programowania, framework webowy albo biblioteka mogą zaoszczędzić wiele godzin pracy. Porównywanie języków jest trudne, ponieważ sensowna próbka statystyczna wymaga wielu wytrenowanych programistów wykonujących to samo zadanie w różnych językach.

Tomasz Kowal. Software Developer w ClubCollect. Codziennie chce się uczyć czegoś nowego. Lubi wyzwania, programowanie funkcyjne i pracę nad dużymi i jeszcze większymi systemami. Dobrze komunikuje się z innymi i lubi dzielić się wiedzą. Pracuje z Erlangiem i Elixirem od 2011 roku. Dokonania Tomka możecie znaleźć na StackOverflow oraz GitHubie.

Tego typu badania są kosztowne i czasochłonne (jednocześnie bardzo wartościowe [1]), ale odpowiadają na pytanie: „który język jest lepszy do tego typu zadania?” W pracy programisty często dostajemy zadania niepodobne do tego, co robiliśmy wcześniej. W takich przypadkach przy wyborze narzędzi musimy zdać się na własny osąd. Możemy zbadać problem, określić jego właściwości, a następnie dopasować narzędzie do problemu.

To też nie jest łatwe, ponieważ zrozumienie kilku narzędzi wymaga dużej ilości czasu. Ten artykuł ma na celu opisanie szczegółowo jednej z właściwości języków i frameworków opartych o aktorów: schedulera zwanego też „planistą” na przykładzie Erlanga i Akki. W tekście będę się posługiwał angielską nazwą „scheduler”, ponieważ polskie tłumaczenie jest bardzo rzadko spotykane.

Erlang oraz Akka oparte są na modelu aktorów. A aktorzy nie powinni współdzielić pamięci, dlatego komunikują się ze sobą tylko przez wysyłanie wiadomości. Modelowany system składa się często z setek tysięcy współpracujących ze sobą aktorów. Aktorzy są niezależni i w teorii mogliby się wykonywać wszyscy równolegle, dzięki czemu programy pisane w tym modelu powinny się łatwo skalować na wiele procesorów lub nawet maszyn.

W praktyce mamy do czynienia z ograniczoną liczbą procesorów i niezbędną częścią systemu opartego o aktorów jest scheduler, który przypisuje aktorów czekających na wykonanie swojego kodu do wolnych rdzeni procesora.

Jaki powinien być dobry scheduler?

Dobry scheduler musi pogodzić trzy sprzeczne ze sobą cele. Powinien:

Zmaksymalizować przepustowość (throughput). Jeśli zarzucimy go kolejką zadań do wykonania, to w danej jednostce czasu chcemy ich wykonać jak najwięcej.
Zminimalizować czas odpowiedzi (latency). Po zakolejkowaniu pojedynczego zadania, chcemy jak najszybciej uzyskać odpowiedź.
Zmaksymalizować „uczciwość” (fairness). Nawet przy dużej kolejce zadań do wykonania, żadne z nich nie powinno zostać zagłodzone.

Nie da się pogodzić wszystkich tych zadań jednocześnie. Schedulery możemy podzielić na wywłaszczające (preemptive) oraz oparte na współpracy (cooperative). Schedulery wywłaszczające mogą przerwać wykonywanie zadania i przełączyć się na inne zadanie, nawet jeśli to pierwsze nie jest skończone. Schedulery oparte o współpracę czekają aż wykonywane zadanie dobrowolnie odda sterowanie. To trochę utrudnia programowanie, ponieważ błąd w postaci nieskończonej pętli może zablokować działanie schedulera lub zająć bezpowrotnie cały jeden rdzeń procesora. Z tego powodu w większości systemów operacyjnych schedulery są wywłaszczające. Przełączanie się między zadaniami generuje dodatkowe koszty, dlatego chociaż schedulery wywłaszczające są najpopularniejsze, to nie zawsze są najlepsze.

Przyjrzyjmy się kilku różnym schedulerom zaczynając od najprostszych:

Erlang przed wersją R11B (która weszła w maju 2016) wprowadził bardzo prosty wywłaszczający scheduler. Składał się on z jednej struktury danych: kolejki procesów do wykonania. Każdy nowy aktor dodawany był na koniec kolejki. Scheduler ściągał z początku kolejki zadanie do wykonania i wykonywał je przez określoną chwilę. Jeśli zadanie się nie zakończyło w wyznaczonym czasie, zostawało przerwane i odłożone na koniec kolejki. Następnie scheduler zaczynał następne.

Ten bardzo prosty model był wystarczający w 2006 roku, ale przestał być, kiedy okazało się, że mamy do dyspozycji więcej procesorów. Erlang R11B i R12B wprowadziły modyfikację. Tym razem schedulerów było tyle, ile dostępnych rdzeni procesora. Współdzieliły one ze sobą jedną kolejkę zadań do wykonania. Kolejka musiała być synchronizowana i przy dużej ilości małych zadań okazywało się, że dużą część czasu pożera czekanie na blokady (lock). W ten sam sposób działa w Akce Default Dispatcher (Thread Pool Executor).

W Akce mamy scheduler kooperacyjny. Punktem, w którym aktor oddaje sterowanie schedulerowi jest koniec przetwarzania wiadomości.

Domyślnie scheduler odkłada aktora do kolejki po przetworzeniu jednej wiadomości, ale ten parametr jest konfigurowalny (nazywa się „throughput”). Przełączanie się między aktorami po każdej wiadomości (throughput = 1) wymaga dodatkowej pracy na załadowanie stanu kolejnego aktora częściej, niż gdy pozwalamy jednemu aktorowi przetworzyć kilka wiadomości. Zmniejsza to ogólną ilość wykonanych zadań w jednostce czasu. Z drugiej strony, pozostali aktorzy szybciej doczekają się swojej kolejki i będą mieli szansę odpowiedzieć na zapytanie. Zwiększając throughput, zwiększamy też opóźnienia i zmniejszamy „uczciwość” (możemy niektórych aktorów zagłodzić).

Zobacz też

Backend Sprawdziliśmy, czy Azure Functions 2.0 jest gotowe do wdrożeń produkcyjnych

Jeżeli przetworzenie jednej wiadomości trwa długo lub w programie mamy błąd typu `while(true)`, blokujemy na stałe jeden z rdzeni. W schedulerze wywłaszczającym w Erlangu tego typu proces zostałby wywłaszczony i chociaż nadal marnowałby zasoby, to szkody byłyby mniejsze. Z drugiej strony zwiększa się koszt czasowy ze względu na częstsze przełączanie między aktorami. Przełączanie może nastąpić nawet przed przetworzeniem jednej wiadomości w całości.

Kolejnym krokiem w ewolucji schedulerów jest przetwarzanie kilku kolejek zadań jednocześnie. Każdy scheduler ma swoją własną kolejkę dzięki czemu nie traci się czasu na synchronizację w czasie ściągania zadań. Czeka się tylko przy ich dokładaniu. Tego typu scheduler w Akce nazywa się Default Dispatcher (Fork Join Pool). W Erlangu jest domyślny od wersji R13B. Dodatkową komplikacją jest teraz sytuacja, w której jeden z procesorów ma pustą kolejkę zadań do wykonania, w czasie gdy inne mogą być przepełnione. Potrzebne są dodatkowe mechanizmy migracji zadań między kolejkami.

Uff… To może być sporo technicznego materiału do przetworzenia, ale po co jako programista miałbym się tym przejmować? Co mi to daje? Możemy wyliczyć wady i zalety obu typów schedulerów!

Przewagą schedulera kooperacyjnego jest większy throughput. Jeśli mamy do wykonania obliczenia naukowe, gdzie odpowiedź wymaga zakończenia wszystkich obliczeń, powinniśmy zmaksymalizować ten parametr.

Jeśli mamy do napisania aplikację webową, prawdopodobnie bardziej zależy nam na tym, żeby czas oczekiwania każdego z klientów był zbliżony i czas odpowiedzi na pojedyncze zapytanie http jak najniższy nawet przy zwiększonym obciążeniu. Wtedy lepiej wybrać scheduler wywłaszczający.

Oczywiście każdy problem ma inne unikatowe właściwości i wybranie właściwego języka programowania nie będzie zależeć wyłącznie od typu schedulera. Nic nie zastąpi przetestowania własnego algorytmu w kilku różnych środowiskach. Może to być jednak wartościowy punkt w debacie nad wyborem technologii.