MARGO

Aktualności

Zegary Lamporta i wzorzec Idempotent Producer (Kafka)

Nasza opinia o konferencji algorytmów rozproszonych dla Big Data sezon 3: historia czasu

Autor: Yannick Decourtray Software Engineer
25/05/2018

Znacie zegary Lamporta? Podczas konferencji Devoxx France 2018 była okazja, w trakcie bardzo interesującej prezentacji DuyHai DOAN, do poznania lub ponownego poznania tego algorytmu, sformalizowanego przez Lesliego Lamporta w 1978 r., częściej niż kiedykolwiek używanego dzisiaj w dziedzinie systemów rozproszonych, który w szczególności skłonił twórców Apache Kafka do wprowadzenia wzorca Idempotent Producer.

 

Co to są zegary Lamporta?

W scentralizowanym systemie istnieje tylko jeden proces, a datowanie zdarzeń jest bardzo proste. Opiera się ono na zegarze fizycznym pojedynczego procesu, a porządkowanie tych zdarzeń nie stanowi problemu. Innymi słowy, można naturalnie wskazać, które zdarzenie miało miejsce przed innym.

W systemie rozproszonym istnieje natomiast wiele powiązanych ze sobą procesów, z których każdy posiada własny zegar fizyczny. Datowanie wydarzeń jest zatem oddzielne dla każdego procesu, a porządkowanie zdarzeń nie jest proste. Innymi słowy, trudno powiedzieć z całą pewnością, że zdarzenie w jednym procesie miało miejsce przed innym w innym procesie.

Algorytm Lamporta proponuje rozwiązanie polegające na ustaleniu częściowej kolejności sekwencji zdarzeń w systemie rozproszonym w oparciu o mechanizm zegarów logicznych. W jakim celu? Otóż w dziedzinie przetwarzania rozproszonego istnieje tak naprawdę szereg problemów rozwiązywanych poprzez logiczne datowanie zdarzeń pomiędzy procesami… W dalszej części przedstawiony został przypadek Apache Kafka, w którym wykorzystane zostały zegary logiczne Lamporta do rozwiązania problemu związanego z trybem Exactly once. Jednak zanim do tego przejdziemy, przeanalizujmy podstawową zasadę.

 

Jak działają zegary Lamporta?

Wyobraźmy sobie system złożony z procesów komunikujących się ze sobą. Jeżeli zdarzenie lokalne występuje jednocześnie w procesie i w procesie b, wszyscy mają świadomość, że tak naprawdę nie dzieją się one w tym samym czasie. Nie można zdefiniować relacji uprzedniości między tymi dwoma zdarzeniami, a dokładna kolejność wykonania każdego z nich nie jest zdefiniowana z logicznego punktu widzenia. O tych wydarzeniach mówi się, że są współbieżne i nie ma między nimi zależności przyczynowej. W rzeczywistości, zawsze z logicznego punktu widzenia, kolejność wykonywania tych zdarzeń nie ma znaczenia.

Z drugiej strony, jeżeli przekazuje komunikat do b, to zdarzenie wysłania komunikatu do występuje bezwzględnie przed zdarzeniem odebrania komunikatu w b. Te dwa zdarzenia są połączone związkiem przyczynowym, a ich logiczny porządek jest precyzyjnie zdefiniowany. Zatem każde zdarzenie poprzedzające wysłanie wspomnianego powyżej komunikatu z procesu jest de facto również wcześniejsze od odbioru komunikatu w b.

To jest właśnie podstawowy postulat Lamporta.

Podsumowując, mamy trzy typy zdarzeń:

  • Zdarzenia lokalne w obrębie procesów,
  • Wysyłanie komunikatów,
  • Odbieranie komunikatów.

Aby móc logicznie datować każde z tych zdarzeń w poszczególnych procesach i razem je uporządkować, Lamport proponuje użycie w każdym procesie prostego licznika, który nazywa Zegarem procesu. Zegar procesu w czasie t zawsze wskazuje datę ostatniego zdarzenia, które miało miejsce w tym procesie. Po uruchomieniu systemu Zegary wszystkich procesów są zsynchronizowane i ustawione na 0.

Po wystąpieniu zdarzenia jest ono datowane w następujący sposób:

  • Jeżeli jest to zdarzenie lokalne, jego logiczną datą będzie Zegar + 1
  • Jeżeli jest to zdarzenie wysyłania komunikatu, jego logiczną datą również będzie Zegar + 1. Ta data zostanie przeniesiona w komunikacie, aby pomóc odbiorcy ustalić logiczną datę własnego zdarzenia odbioru komunikatu.
  • Jeżeli jest to zdarzenie odebrania komunikatu, jego logiczną datą będzie [MAX(Zegar, data przenoszona przez zdarzenie)] + 1

To wszystko! Z tym algorytmem logiczne daty wszystkich zdarzeń odebrania komunikatu są późniejsze od dat zdarzeń, które je poprzedzają niezależnie od tego, czy dane zdarzenia miały miejsce w procesie odbierania, czy w procesie wysyłania komunikatu. Związki przyczynowe są więc zachowane, a porządkowanie zdarzeń jest możliwe.

… Częściowo…

W rzeczywistości nadal występuje problem związany ze wspomnianymi powyżej zdarzeniami współbieżnymi. Pomiędzy dwoma przedmiotowymi procesami występują zdarzenia, które mają tę samą datę logiczną, a jednak nie zdarzyły w tym samym czasie. Jeżeli chcemy ustalić chronologię zdarzeń w systemie rozproszonym, jaką zasadę priorytetu mamy przyjąć do zdarzeń z identyczną datą logiczną? W odpowiedzi na to trudne pytanie Lamport przypomina po prostu, że wydarzenia z tą samą logiczną datą są współbieżne i nie ma między nimi zależności przyczynowej. Zatem dokładna kolejność ich wykonania nie ma wpływu na system.

Niemniej jednak, zgodnie z przyjętą konwencją, aby zapewnić jednakową chronologię dla wszystkich procesów, zdarzenia współbieżne zostaną sklasyfikowane przy użyciu identyfikatora procesu. Dla przykładu zawsze będziemy uważać, że zdarzenie „2” procesu a miało miejsce przed zdarzeniem „2” procesu b. Tylko dlatego, że a występuje przed b w alfabecie. Aby uniknąć komplikacji. Po prostu.

 

Przypadek zastosowania: Kafka i Exactly once delivery

Kafka jest bardzo popularnym brokerem wiadomości w środowisku rozproszonym, początkowo zaprojektowanym w LinkedIn. Obecnie jest zarządzany przez społeczność Apache, która cen go za swoją wydajność i stabilność zarówno przy niskiej, jak i bardzo dużej objętości i zmienności.

Exactly once delivery – co to jest? Na początek wyjaśnijmy tryb domyślny, którym jest At least once delivery.

Jak każdy szanujący się broker wiadomości, Kafka musi zagwarantować prawidłowe przesyłanie otrzymywanych komunikatów do klientów. I tu pojawia się problem: nawet jeżeli wiadomość jest wysyłana przez Apache Kafka, skąd mam mieć pewność, że klient ją odebrał? Powiecie mi, że wystarczy zwykłe potwierdzenie odbioru wysłane w drugą stronę. Co się jednak stanie, gdy w tym konkretnym momencie nastąpi odłączenie od sieci lub klient będzie miał awarię przed wysłaniem tego słynnego ACK?

Otóż, w bardzo tradycyjny sposób dla Kafki, każda niepotwierdzona wiadomość jest uważana za nieodebraną i musi zostać wysłana ponownie. Pomimo ryzyka, że w rzeczywistości klient odbiera i przetwarza wiadomość dwa razy (lub więcej)… To właśnie nazywamy At least once delivery. Innymi słowy, w tym specjalnym trybie ta sama wiadomość może być odebrana przez klienta kilka razy. W tym właśnie trybie klient musi sam być „idempotent” tzn. obojętny na fakt otrzymywania n razy tego samego zdarzenia.

At least once delivery to dobry początek…

Okazuje się, że Kafka oferuje jeszcze więcej… tryb Exactly once delivery. To znaczy, że wiadomość zostanie wysłana tylko raz do każdego klienta. Gwarantowane! Magiczne! Ta o wiele bardziej zaawansowana z technicznego punktu widzenia funkcja, uznawana przez niektórych za duże osiągnięcie, opiera się na trzech koncepcjach: mechanizmie transakcji między partycjami, stałym systemie offsetowym i prawie idempotentności, stosowanym między instancjami brokerów Kafki oraz… nadawcami.

Skomplikowane? Nie wpadajmy w panikę: nie przejmujmy się dwiema pierwszymi koncepcjami, ponieważ w rzeczywistości są one nieistotne! Interesuje nas tutaj trzecia koncepcja, którą szczegółowo omówimy w tym artykule.

Zatem… zastanówmy się trochę. Aby klient otrzymał daną wiadomość tylko raz, musimy być pewni, że Kafka zarejestruje ją tylko raz w jednej ze swoich partycji. Nawet jeżeli istnieją inne kwestie, które należy wziąć pod uwagę (ale które zostały już rozwiązane przez dwie wymienione powyżej koncepcje, których nie będziemy poruszać w tym artykule), ta jest najbardziej podstawowa. W trybie Exactly once, zdarzenie wysłane przez Nadawcę, nawet wielokrotnie, musi być bezwzględnie zarejestrowane jeden i tylko jeden raz przez Apache Kafka.

Jednak Nadawcy również są narażeni na problemy związane z potwierdzeniem – tym razem ze strony Apache Kafka (mikrorozłączenia w sieci, awaria instancji brokera Kafki itp.). Jak zagwarantować, że z jednej strony zdarzenie zostanie zarejestrowane tylko jeden raz, a zależność przyczynowa będzie zachowana, tzn. porządek zdarzeń będzie zachowany, nawet jeżeli jedno ze zdarzeń zostanie na chwilę utracone, a następnie przywrócone?

W takiej sytuacji stosowany jest Idempotent Producer. I to właśnie przypomina zegary Lamporta…

 

Idempotent Producer

Aby zrozumieć, jak to się odbywa, musimy wiedzieć, jak działa Kafka.

Kafka to platforma typu publish/subscribe w systemach rozproszonych, zarządzająca rodzinami komunikatów według Topic. JedenTopic podzielony jest na n partycji rozproszonych w całym klastrze, przy czym węzeł (zwany brokerem) może ewentualnie zarządzać wieloma partycjami. Kiedy Nadawca wysyła komunikat związany z danym Topic , zostanie on skierowany do określonego węzła klastra na podstawie klucza, gdzie zostanie zapisany w jednej partycji. Wiadomości z tym samym kluczem będą zawsze zapisywane na tej samej partycji, a zatem w tym samym węźle Kafki. Przeczytajcie jeszcze raz uważnie ten punkt, jeśli nie jest to całkowicie jasne.

Każdy węzeł przechowuje wartość o nazwie High Watermark dla każdego Nadawcy. To odpowiednik Zegara w algorytmie Lamporta. Ponadto każdy Nadawca zarządza oddzielną sekwencją dla każdej partycji, aby logicznie datować swoje zdarzenia.

Od Kafki oczekujemy szybkości. Zatem Nadawcy są zaprojektowani do wysyłania serii komunikatów bez czekania na potwierdzenie między każdą wiadomością. Potwierdzenia będą przesyłane na bieżąco w sposób asynchroniczny. Jednak co się stanie w przypadku utraty jednego z potwierdzeń? Nadawca oczywiście ponowi próbę wysłania danej wiadomości, ale nie może to spowodować niespójności w kolejności wiadomości rzeczywiście zarejestrowanych po stronie brokera.

Korzystając z algorytmu Idempotent producer, Kafka jest w stanie wykryć te niespójności sekwencji odbioru wiadomości i odrzucić wszystkie kolejne komunikaty. W praktyce, za każdym razem, gdy Nadawca coś opublikuje, komunikat przenosi własny identyfikator logiczny, zwiększany każdorazowo o jeden, a broker potwierdzi go tylko wtedy, gdy identyfikator będzie równy Watermark + 1.

Przy braku dokładnego zastosowania, znajdujemy tu faktycznie istotę algorytmu zegarów Lamporta, podczas gdy teoria ta powstała w 1978 roku, kiedy nie było wielu systemów rozproszonych.

 

Wnioski

Co zabawne, Confluent opublikował 67-stronicową dokumentację [1], w której szczegółowo wyjaśniono sposób implementacji Exactly Once w Kafce. O ile pojęcie idempotentności nadawców pojawia się wielokrotnie, o tyle ścisłe zastosowanie algorytmu zegarów Lamporta do implementacji tego wzorca nie pojawia się ani razu. Co można z tego wywnioskować?

No cóż, być może deweloperzy pracujący nad Kafką nie pamiętali o zegarach Lamporta w trakcie opracowywania swojego rozwiązania. Większość problemów występujących w dziedzinie architektury oprogramowania prawdopodobnie zostało już teoretycznie przedstawionych wiele lat temu, w czasach, kiedy infrastruktury były jednak znacznie mniej złożone. Nawet bez systematycznego poznawania teorii, zdrowy rozsądek podpowiada nam rozwiązania tych problemów, które się z nimi pokrywają.

Dobrze by było, gdyby DuyHai DOAN w trakcie swojej prezentacji w Devoxx podkreślił fakt, że Idempotent producer Kafki może nie być, jak sugerował, ścisłym i mechanicznym zastosowaniem algorytmu zegarów Lamporta, ale wynikiem mądrego przemyślenia, które dowodzi, że ta teoria jest poprawna i bardziej aktualna niż kiedykolwiek.

 

 

Prezentacja DuyHai DOAN, podobnie jak moja, została w dużej mierze zainspirowana tym artykułem: https://cwiki.apache.org/confluence/display/KAFKA/Idempotent+Producer. Niniejsza prezentacja przedstawia w skrócie syntezę wzorca, zachęcamy do przeczytania jej, aby uzyskać więcej szczegółów technicznych.

[1] https://docs.google.com/document/d/11Jqy_GjUGtdXJK94XGsEIK7CP1SnQGdp2eF0wSw9ra8/edit#

 


Autor: Yannick Decourtray Software Engineer
Big Data
Dane
Data Science
Aktualności

Projekty z dziedziny Data Science to wciąż droga pełna przeszkód

Projekty z dziedziny Data Science to wciąż droga pełna przeszkód W czasach, gdy wiele firm pretenduje do miana „spółek działających w oparciu o dane” nadal wiele projektów z zakresu Data Science kończy się porażką. W większości przypadków porażki wynikają z dobrze znanych i powtarzalnych przyczyn. Pierre Fares, Digital Offering & Business Transformation Officer w firmie Margo, opowiada o częstych pułapkach, których bezwzględnie należy unikać.

Więcej 
Aktualności

Tutorial: Podstawy stosowania Pythona do prognozowania szeregów czasowych

W tutorialu wprowadzamy kilka podstawowych pojęć z zakresu szeregów czasowych, aby umożliwić „szybką” predykcję przyszłych wartości w odniesieniu do danych czasowych.

07/11/2018 Więcej 
Aktualności

Utworzenie scentralizowanej platformy zarządzania logami za pomocą pakietu narzędzi Elastic

Ilość danych generowanych przez nasze systemy i aplikacje stale rośnie, co powoduje wzrost liczby centrów danych i systemów przechowywania danych. W obliczu tej eksplozji danych i inwestycji w wiedzę fachową i zasoby, decydenci potrzebują uzasadnionych analiz i zaawansowanych tabel, umożliwiających im zarządzanie swoimi systemami i klientami.

04/06/2018 Więcej 
Aktualności

Data Science w świecie handlu detalicznego: 10 najważniejszych przypadków wykorzystania

Data Science w coraz większym stopniu wpływa na modele biznesowe we wszystkich gałęziach przemysłu, zwłaszcza w sprzedaży detalicznej. Według IBM, 62% detalistów deklaruje, że wykorzystanie technik związanych z Big Data daje im poważną przewagę konkurencyjną. Dzięki data sicence możemy sprawdzić, czego potrzebuje klient i w jakim momencie jest obecnie na wyciągnięcie ręki. Aby to zrobić, musimy jedynie posiadać odpowiednie narzędzia i wdrożyć dobre procedury związane z ich używaniem. W niniejszym artykule przedstawiamy 10 najważniejszych zastosowań data science w handlu detalicznym.

01/06/2018 Więcej 
Aktualności

Wprowadzenie do TensorFlow na datalab od Google Cloud Platform

TensorFlow to biblioteka programów do obliczeń numerycznych, działająca na zasadzie open source od 2015 r., opracowana przez Google. Szczególną cechą TensorFlow jest wykorzystanie diagramów przepływu danych (data flow graphs).

11/05/2018 Więcej 
Aktualności

Krótkie wprowadzenie do chatbotów tworzonych za pomocą Dialogflow

Ostatnio pracuję nad chatbotem, korzystając z aplikacji Google Dialogflow. Niniejszy artykuł zawiera kilka moich uwag dotyczących Dialogflow i chatbotów. Opisuję w nim też sposób, jak stworzyć prostego chatbota za pomocą platformy Dialogflow.

07/05/2018 Więcej