Algorytmy i struktury danych

Saga, java, wzorzec projektowy

Wzorzec Saga w architekturze mikroserwisów – Spring Boot i Apache Kafka w praktyce

Saga – wzorzec w architekturze mikroserwisów – czyli Spring Boot i Apache Kafka w praktyce.

W architekturze mikroserwisowej z reguły obowiązuje zasada „Database per Service”, czyli oddzielna baza danych dla każdej usługi. Dzięki temu każdy mikroserwis ma pełną kontrolę nad swoimi danymi i może używać dowolnej technologii bazy danych, a awarie jednego serwisu nie psują danych innych.

Jednak podejście to rodzi wyzwanie: jak zachować spójność danych w procesach biznesowych obejmujących wiele serwisów? Skoro każda usługa ma osobną bazę, nie da się użyć zwykłej transakcji ACID obejmującej wszystkie bazy jednocześnie.

Klasyczne Two-Phase Commit (2PC) – protokół dwufazowego zatwierdzania – teoretycznie pozwala na taką rozproszoną transakcję, ale w świecie mikroserwisów jest rzadko stosowany. 2PC wymaga bowiem koordynatora i blokuje zasoby w wielu bazach; jest skomplikowany, obniża dostępność i nie zawsze jest wspierany przez różne silniki baz danych. Z pomocą przychodzi nam wzorzec Saga – rozwiązanie, które umożliwia realizację transakcji rozproszonych bez globalnej transakcji 2PC.

Czym jest wzorzec Saga?

Saga to sekwencja lokalnych transakcji wykonywanych kolejno w różnych mikroserwisach, które wspólnie realizują jeden proces biznesowy.

Każdy etap Sagi to zwykła transakcja w ramach jednej bazy danych (np. zapis w swojej tabeli), po której serwis publikuje zdarzenie (event) lub komunikat – sygnał do kolejnego kroku w innym serwisie.

Jeśli któryś z etapów się nie powiedzie (np. któryś serwis nie może wykonać swojej operacji z powodu naruszenia reguł biznesowych lub błędu), Saga uruchamia transakcje kompensacyjne, które cofają skutki wcześniejszych operacji, przywracając system do spójnego stanu. W efekcie otrzymujemy mechanizm podobny do rollbacku w klasycznej transakcji, ale realizowany na poziomie aplikacji – poprzez dodatkowe akcje odwracające.

Kluczowe cechy wzorca Saga

  • Lokalne transakcje – Każdy serwis wykonuje swoją część pracy niezależnie, używając własnej bazy i zapewniając lokalną atomowość i integralność danych.
  • Komunikacja asynchroniczna – Po zakończeniu swojej transakcji, serwis informuje inne komponenty wysyłając komunikat/zdarzenie (np. przez Apache Kafka, RabbitMQ itp.). To zdarzenie wyzwala kolejny krok Sagi w innym serwisie.
  • Brak globalnej transakcji – Nie ma jednego globalnego mechanizmu blokującego zasoby we wszystkich bazach. Każdy etap zatwierdza zmiany od razu lokalnie, więc nie występuje problem blokad i oczekiwania na commit wielu baz naraz.
  • Kompensacje zamiast rollbacku – Ponieważ zmiany są zatwierdzane na bieżąco, ewentualne błędy wymagają ręcznego cofnięcia wcześniejszych operacji poprzez wykonanie odwrotnej akcji (np. anulowanie płatności, usunięcie utworzonej rejestracji itp.). Programista musi zaprojektować takie operacje kompensujące – nie dzieją się one automatycznie jak rollback w bazie.
  • Spójność ostateczna (ang. eventual consistency) – Saga zapewnia, że wszystkie serwisy prędzej czy później uzyskają spójny stan danych, ale nie gwarantuje, że w każdej chwili widoczny stan jest spójny (czyli dopuszczamy chwilowe stany pośrednie). To tzw. eventual consistency – ostateczna spójność danych po zakończeniu całej sekwencji.

Podsumowując, Saga pozwala zachować spójność danych w rozproszonym systemie bez potrzeby użycia 2PC. Zamiast jednego wielkiego „commit” na końcu, mamy wiele mniejszych commitów w trakcie procesu, a ewentualne błędy korygujemy dodatkowymi transakcjami kompensującymi. Dzięki temu mikroserwisy pozostają luźno powiązane (komunikują się komunikatami), a cały system unika wad protokołu 2PC (np. blokowania zasobów i pojedynczego punktu awarii w postaci koordynatora).

Saga vs Two-Phase Commit (2PC) – dlaczego Saga wygrywa w mikroserwisach?

Saga vs 2fa

Źródło: microservices.io

Na schemacie porównano tradycyjną rozproszoną transakcję 2PC (u góry) z podejściem Saga (na dole). W 2PC koordynator zarządza jednoczesnym zatwierdzeniem w wielu serwisach, natomiast Saga dzieli proces na serię niezależnych operacji lokalnych, przekazując sterowanie między serwisami za pomocą komunikatów.

W modelu 2PC jeden koordynator najpierw pyta wszystkie uczestniczące serwisy/bazy, czy są gotowe zatwierdzić transakcję (faza prepare), a potem wydaje polecenie commit, jeśli wszyscy byli gotowi (faza commit). Jeśli choć jeden zgłosi problem w fazie przygotowania, koordynator zleca rollback we wszystkich – cała transakcja zostaje anulowana.

W teorii brzmi dobrze, ale w praktyce w środowisku mikroserwisów 2PC nie jest już taki prosty w implementacji:

  • Nie ma wspólnego mechanizmu transakcji dla różnych technologii baz (np. miks SQL i NoSQL).
  • Koordynator staje się wąskim gardłem i potencjalnym pojedynczym punktem awarii (ang. single point of failure).
  • W przypadku awarii lub opóźnień, uczestnicy mogą długo trzymać blokady na danych czekając na decyzję, co ogranicza skalowalność.
  • Implementacja 2PC w obrębie aplikacji jest złożona i podatna na błędy, szczególnie gdy serwisy są rozproszone geograficznie lub sieć jest zawodna.

Saga rozwiązuje te problemy przez rezygnację z globalnej atomowości na rzecz ostatecznej spójności. Każdy serwis od razu finalizuje swoją zmianę (nie czeka na inne serwisy), więc brak globalnych blokad. Koordynacja odbywa się przez wymianę komunikatów/asynchronicznych zdarzeń, np. za pomocą Apache Kafka. Nie potrzebujemy centralnego menedżera transakcji w tradycyjnym sensie – logika kontroli przepływu jest wbudowana w samą aplikację (o podejściach do tej kontroli zaraz powiemy). W razie problemów, Saga zapewnia ręczne odkręcenie (kompensacja) już zatwierdzonych kroków.

Owszem, wymaga to więcej kodu (trzeba przewidzieć i obsłużyć scenariusze kompensacji), ale upraszcza architekturę i zwiększa niezawodność w środowisku rozproszonym. Z punktu widzenia spójności danych, Saga gwarantuje rezultat równoważny 2PC (wszystko albo nic), ale osiągany inną drogą – sekwencją akcji i kompensacji zamiast jednego globalnego commit/rollback.

Uwaga: Warto pamiętać, że Saga nie zapewnia izolacji transakcji w rozumieniu ACID. Równoległe wykonywanie wielu Sag może prowadzić do konfliktów (np. dwa procesy jednocześnie rezerwujące te same zasoby). Programista musi sam zadbać o mechanizmy zapobiegające anomaliom, np. poprzez odpowiednie blokady logiczne czy sprawdzanie wersji danych. Mimo to Saga pozostaje de facto standardem utrzymania spójności danych w świecie mikroserwisów, podczas gdy 2PC jest traktowane jako ostateczność (lub materiał teoretyczny).

Choreografia vs orkiestracja – dwie szkoły implementacji Sag

Wzorzec Saga określa co ma być zrobione (podział transakcji na kroki i kompensacje), ale pozostawia swobodę jak to zaimplementować.

W praktyce spotykamy dwa style koordynacji sag: choreografię oraz orkiestrację. Oba podejścia osiągają ten sam cel, ale różnią się sposobem, w jaki poszczególne serwisy dowiadują się, co mają robić w ramach procesu.

Przyjrzyjmy się im bliżej.

Saga w podejściu choreografii ( ang. choreography)

Choreografia opiera się w 100% na komunikacji asynchronicznej za pomocą zdarzeń domenowych. Nie ma centralnego „reżysera” procesu – każdy mikroserwis sam wie, jakie akcje podjąć w reakcji na dane zdarzenie i jakie zdarzenia wyemitować po wykonaniu swojej pracy. Mówiąc obrazowo, serwisy tańczą ze sobą „w rytmie zdarzeń”, reagując na siebie nawzajem.

Jak to wygląda w praktyce? Rozważmy prosty scenariusz biznesowy systemu szkoleń: zapis kursanta na szkolenie, które wymaga opłaty i ma ograniczoną liczbę miejsc. Załóżmy, że mamy trzy mikroserwisy:

  • Serwis Rejestracji – przyjmuje zgłoszenie na szkolenie od kursanta (np. poprzez REST API) i zapisuje w swojej bazie wstępną rejestrację.
  • Serwis Płatności – obsługuje płatność za szkolenie.
  • Serwis Szkoleń – zarządza danymi o szkoleniach i miejscami na kursach.

W podejściu choreografii przebieg Saga (w wariancie happy path, czyli bez błędów) mógłby być następujący:

  1. Rejestracja kursanta – Serwis Rejestracji otrzymuje żądanie zapisu na szkolenie. Tworzy w swojej bazie wpis rejestracji ze statusem np. PENDING (oczekujące) i publikuje zdarzenie EnrollmentCreated (rejestracja utworzona).
  2. Płatność – Serwis Płatności odbiera zdarzenie EnrollmentCreated (np. z topicu Kafki enrollment-events). Na jego podstawie rozpoczyna proces opłacenia szkolenia przez kursanta. Jeśli płatność się powiedzie, zapisuje w swojej bazie transakcję i wysyła zdarzenie PaymentCompleted (płatność zakończona). Jeśli się nie powiedzie – publikuje zdarzenie PaymentFailed (płatność nieudana).
  3. Reakcja na płatność – Zdarzenie PaymentCompleted trafia do zainteresowanych serwisów. Serwis Rejestracji może je odebrać i zaktualizować status rejestracji na PAID (opłacone). Jednocześnie (równolegle) Serwis Szkoleń również słucha tego zdarzenia – widząc informację o opłaconej rejestracji, próbuje zarezerwować kursantowi miejsce na wybranym szkoleniu (lokalna transakcja w bazie szkoleniowej). Następnie Serwis Szkoleń publikuje zdarzenie SeatReserved (miejsce zarezerwowane) albo SeatReservationFailed (brak miejsca).
  4. Finalizacja lub kompensacja – Załóżmy, że miejsce udało się zarezerwować – SeatReserved zostaje odebrane przez Serwis Rejestracji, który zmienia status rejestracji na CONFIRMED (potwierdzone) i np. emituje zdarzenie EnrollmentCompleted (zapis ukończony), co może posłużyć innym usługom (np. serwisowi powiadomień, który wyśle e-mail z potwierdzeniem). W ten sposób Saga się kończy sukcesem.
    A co jeśli któregoś kroku nie da się wykonać? Np. jeśli Serwis Szkoleń opublikuje SeatReservationFailed (brak miejsc). W choreografii pozostałe serwisy muszą same zareagować na ten fakt. Serwis Rejestracji mógłby w takiej sytuacji oznaczyć rejestrację jako anulowaną (CANCELLED), a Serwis Płatności – po otrzymaniu informacji o nieudanej rezerwacji – mógłby automatycznie zainicjować zwrot płatności (np. publikując zdarzenie PaymentRefunded). Każdy serwis zna logikę kompensacji swojej części: Rejestracja usuwa/znakuje wpis, Płatność robi zwrot, itp. Po wykonaniu kompensacji Saga również się kończy (ostatecznie kursant nie jest zapisany, a pieniądze wróciły – układ wrócił do stanu sprzed procesu).

Widzimy, że w podejściu choreograficznym cała sekwencja jest kontrolowana implicite przez samą kolejność zdarzeń. Zalety tego podejścia to m.in. prostota integracji: dodanie nowego kroku (np. nowego serwisu wysyłającego powiadomienia) często wymaga tylko dołączenia nowego „tancerza do baletu” – nowy serwis zaczyna nasłuchiwać odpowiedniego zdarzenia i reagować, nie trzeba modyfikować centralnej logiki sterującej. Choreografia jest też naturalnie skalowalna i luźno powiązana – serwisy nie wywołują się nawzajem bezpośrednio, komunikują się przez brokera (Kafka), co zmniejsza zależności.

Jednak choreografia ma też wady. Przy rozbudowanych procesach biznesowych kolejka zdarzeń może stać się trudna do prześledzenia – logika jest rozsiana po wielu usługach. Trudniej zrozumieć całościowy obraz, co może utrudnić debugowanie i monitorowanie. W przypadku złożonych kompensacji (wielu rzeczy do odwołania w razie błędu) rozproszona natura choreografii bywa kłopotliwa – trzeba dopilnować, by każdy serwis zareagował poprawnie na zdarzenia błędów. Istnieje ryzyko powstania „tańca chaosu” – gdy logika zależności między zdarzeniami staje się zawiła jak spaghetti. Mimo to, do prostszych procesów lub gdy zależy nam na maksymalnym luzie między serwisami, choreografia bywa wystarczająca.

Zobaczmy fragment kodu obrazujący podejście choreograficzne z użyciem Spring Boot i Kafki. Poniżej przykładowa implementacja obsługi zdarzenia utworzenia rejestracji oraz wysłania zdarzenia płatności (krok 1-2 z naszego scenariusza):

// Serwis Rejestracji – publikacja zdarzenia po zapisaniu rejestracji
@Service
public class EnrollmentService {
    @Autowired
    private KafkaTemplate<String, Object> kafkaTemplate;

    public void registerStudent(Long studentId, Long trainingId) {
        // ... (logika zapisania rejestracji w lokalnej bazie, status PENDING)
        EnrollmentCreatedEvent event = new EnrollmentCreatedEvent(studentId, trainingId);
        kafkaTemplate.send("enrollment-events", event);
        // Zdarzenie 'EnrollmentCreated' zostanie odebrane przez serwis płatności
    }
}

 

// Serwis Płatności – nasłuchiwanie zdarzenia rejestracji i wykonanie płatności
@Service
public class PaymentListener {
    @Autowired
    private KafkaTemplate<String, Object> kafkaTemplate;

    @KafkaListener(topics = "enrollment-events", groupId = "payment-service")
    public void onEnrollmentCreated(EnrollmentCreatedEvent event) {
        // Po otrzymaniu zdarzenia, rozpoczynamy proces płatności
        boolean paid = paymentProcessor.processPayment(event.getStudentId(), event.getTrainingId());
        if (paid) {
            // emitujemy zdarzenie o zakończonej płatności
            PaymentCompletedEvent payEvent = new PaymentCompletedEvent(event.getStudentId(), event.getTrainingId());
            kafkaTemplate.send("payment-events", payEvent);
        } else {
            // emitujemy zdarzenie o nieudanej płatności (do ewentualnej kompensacji)
            PaymentFailedEvent failEvent = new PaymentFailedEvent(event.getStudentId(), event.getTrainingId());
            kafkaTemplate.send("payment-events", failEvent);
        }
    }
}

Powyższy kod ilustruje dwa pierwsze etapy Saga w trybie choreografii. Gdy Serwis Rejestracji utworzy nową rejestrację, publikuje zdarzenie EnrollmentCreatedEvent na temat (topic) enrollment-events. Serwis Płatności (nasłuchujący ten topic dzięki adnotacji @KafkaListener) otrzymuje to zdarzenie i wykonuje logikę opłacenia – tutaj symulowaną przez metodę paymentProcessor.processPayment(...). W zależności od wyniku, publikuje kolejne zdarzenie: PaymentCompletedEvent albo PaymentFailedEvent na topic payment-events. Dalej w Saga kolejne serwisy (np. Serwis Szkoleń) będą nasłuchiwać payment-events i tak dalej. W ten sposób cały przepływ jest napędzany zdarzeniami i żaden centralny komponent nie dyktuje kolejności – każda usługa reaguje autonomicznie.

Saga w podejściu orkiestracji (orchestration)

Drugim podejściem do implementacji Saga jest orkiestracja, gdzie wprowadzamy dedykowany komponent pełniący rolę koordynatora (orkiestratora) całego procesu. Można go sobie wyobrazić jako maestro dyrygującego orkiestrą – jeden centralny serwis wie, jakie kroki powinny nastąpić po kolei i wysyła wytyczne (komendy) do poszczególnych mikroserwisów, czekając na ich odpowiedź. To podejście bywa też nazywane wzorcem Process Manager lub po prostu Saga Orchestrator.

W naszym przykładzie z zapisami na szkolenie moglibyśmy wydzielić np. Serwis Orkiestratora, który koordynuje współpracę pozostałych serwisów (Rejestracji, Płatności, Szkoleń). Przebieg Saga w wariancie orkiestracji (happy path) wyglądałby tak:

  1. Start Saga – Serwis Rejestracji przyjmuje żądanie zapisu kursanta (tak jak wcześniej), tworzy wpis PENDING w swojej bazie ale nie wysyła od razu zdarzenia do wszystkich. Zamiast tego powiadamia Orkiestratora (np. wywołuje metodę orkiestratora lub publikuje specjalny komunikat-komendę). Orkiestrator rozpoczyna nową Sagę, zapisując sobie jej kontekst (np. ID rejestracji, ID kursanta i szkolenia) i przechodzi do kroku 2.
  2. Płatność (komenda) – Orkiestrator wysyła komunikat typu komenda do Serwisu Płatności, np. ProcessPaymentCommand z informacją kogo i za co obciążyć. (W praktyce w świecie Kafki może to być opublikowanie wiadomości na dedykowanym topicu, powiedzmy payment-commands, na którym słucha Serwis Płatności). Następnie orkiestrator czeka na wynik.
  3. Płatność (wynik) – Serwis Płatności otrzymuje komendę, wykonuje płatność i odsyła odpowiedź – np. publikuje zdarzenie PaymentCompleted lub PaymentFailed na inny topic (np. payment-events). Orkiestrator nasłuchuje tych odpowiedzi. Gdy otrzyma wynik płatności, aktualizuje stan Saga (np. odnotowuje “zapłacone” lub “błąd płatności”) i decyduje co dalej.
  4. Rezerwacja miejsca (komenda) – Jeśli płatność się powiodła, orkiestrator wysyła kolejną komendę, tym razem do Serwisu Szkoleń, np. ReserveSeatCommand z informacją o kursancie i szkoleniu. Serwis Szkoleń próbuje zarezerwować miejsce i odsyła wynik – SeatReserved lub SeatReservationFailed.
  5. Zakończenie Saga – Orkiestrator odbiera wynik rezerwacji. Jeśli miejsce zarezerwowano (SeatReserved), może uznać Sagę za zakończoną sukcesem – wówczas np. powiadamia Serwis Rejestracji, wysyłając mu komendę ConfirmEnrollment (aby ten zmienił status rejestracji na potwierdzony), po czym publikuje ewentualne finalne zdarzenie EnrollmentCompleted (do którego mogą się podpiąć inne usługi, np. powiadomień). Jeśli jednak otrzyma informację o braku miejsca (SeatReservationFailed), inicjuje kompensacje: np. wysyła komendę CancelPayment do Serwisu Płatności (żądanie zwrotu pieniędzy) i CancelEnrollment do Serwisu Rejestracji (anulowanie rejestracji). Gdy te zostaną wykonane, Saga kończy się, mając pewność, że wcześniejsze części procesu zostały odwrócone.

Podejście orkiestracji centralizuje logikę sterowania w jednym miejscu.

Zalety takiego rozwiązania są następujące:

  • Cały przepływ procesu jest jasno zdefiniowany w kodzie orkiestratora – łatwiej go śledzić, debugować i testować. Możemy np. logować każdy krok, wiedzieć dokładnie na którym etapie jest Saga.
  • Skomplikowane scenariusze błędów i kompensacji są prostsze do zaimplementowania, bo jedna jednostka (orkiestrator) wie, co już zrobiono, a co trzeba cofnąć. Nie musimy polegać na tym, że każdy serwis osobno „domyśli się” jak zareagować – orkiestrator wydaje polecenia kompensacji świadomie.
  • Możemy łatwo wprowadzać bardziej złożone reguły decyzyjne – np. jeśli płatność nie przeszła, spróbować zapisać to w logu i ponowić za 15 minut itp. – bo mamy centralny punkt, który może ogarnąć takie scenariusze.

Oczywiście są i wady:

  • Orkiestrator to dodatkowy komponent, który trzeba napisać i utrzymywać. Wprowadza pewne sztywne powiązanie – wie o istnieniu innych serwisów i rodzaju akcji, jakie można w nich wykonać (np. musi znać komendę ReserveSeat). Dodanie nowego kroku (np. powiadomienie e-mail) oznacza modyfikację kodu orkiestratora (i potencjalnie obsługi komendy w nowym serwisie).
  • Orkiestrator staje się centralnym elementem procesu – jeśli on zawiedzie, cała Saga może utknąć. Trzeba zadbać o wysoką dostępność orkiestratora i mechanizmy odporności (np. ponawianie niedostarczonych komend, odczytywanie nieprzetworzonych zdarzeń po restarcie itp.). W literaturze wspomina się, że orkiestrator to potencjalny single point of failure (choć można go nadmiarowo zreplikować).
  • Nieumiejętne użycie orkiestracji może prowadzić do mini-monolitu – czyli zbytniego skupienia logiki w jednym miejscu. Trzeba balansować między tym, co koordynuje orkiestrator, a co wciąż samodzielnie robią serwisy.

Implementacja Spring Boot + Kafka

Orkiestrator może komunikować się z serwisami różnymi sposobami. Czasem używa się synchronicznych wywołań REST (np. orchestrator wywołuje endpoint płatności i czeka na response), ale takie podejście częściowo niweluje zalety asynchroniczności. Skoro i tak mamy Apache Kafka, pokażemy wariant w pełni asynchroniczny, gdzie komendy i wyniki są przesyłane jako komunikaty na topicach.

Możemy np. ustalić, że:

  • Orkiestrator publikuje komendy na topicach payment-commands, training-commands itp.
  • Każdy serwis nasłuchuje swojego topicu komend (np. Serwis Płatności – payment-commands).
  • Po wykonaniu, serwis publikuje zdarzenie na swoim topicu zdarzeń (np. payment-events), na które czeka orkiestrator.

Zobaczmy fragment kodu obrazujący prosty orkiestrator Sagi dla naszego procesu zapisu na szkolenie oraz obsługę jednej z komend:

// Orkiestrator Saga – koordynator procesu zapisu na szkolenie
@Service
public class EnrollmentSagaOrchestrator {
    @Autowired
    private KafkaTemplate<String, Object> kafkaTemplate;
    // Metoda rozpoczynająca Sagę zapisu kursanta
    public void startEnrollmentSaga(Long enrollmentId, Long studentId, Long trainingId) {
        // 1. Wyślij komendę do serwisu płatności, aby pobrał opłatę
        ProcessPaymentCommand cmd = new ProcessPaymentCommand(enrollmentId, studentId, trainingId);
        kafkaTemplate.send("payment-commands", cmd);
        // (Zakładamy, że dalsze kroki będą wywoływane w metodach obsługi odpowiedzi poniżej)
    }

    // 2. Nasłuchiwanie wyniku płatności
    @KafkaListener(topics = "payment-events", groupId = "saga-orchestrator")
    public void onPaymentEvent(PaymentEvent event) {
        if (event instanceof PaymentCompletedEvent) {
            PaymentCompletedEvent pay = (PaymentCompletedEvent) event;
            // Płatność ok -> wysyłamy komendę rezerwacji miejsca
            ReserveSeatCommand cmd = new ReserveSeatCommand(pay.getEnrollmentId(), pay.getTrainingId());
            kafkaTemplate.send("training-commands", cmd);
            // (Dalsze kroki w kolejnym listenerze)
        } else if (event instanceof PaymentFailedEvent) {
            // Płatność nie przeszła -> kończymy Sagę kompensując (anulacja rejestracji)
            CancelEnrollmentCommand cancelCmd = new CancelEnrollmentCommand(event.getEnrollmentId());
            kafkaTemplate.send("registration-commands", cancelCmd);
        }
    }

    // 3. Nasłuchiwanie wyniku rezerwacji miejsca
    @KafkaListener(topics = "training-events", groupId = "saga-orchestrator")
    public void onSeatEvent(SeatEvent event) {
        if (event instanceof SeatReservedEvent) {
            // Miejsce zarezerwowane -> potwierdź rejestrację
            ConfirmEnrollmentCommand confirmCmd = new ConfirmEnrollmentCommand(event.getEnrollmentId());
            kafkaTemplate.send("registration-commands", confirmCmd);
        } else if (event instanceof SeatReservationFailedEvent) {
            // Brak miejsca -> zleć kompensację płatności (zwrot)
            RefundPaymentCommand refundCmd = new RefundPaymentCommand(event.getEnrollmentId());
            kafkaTemplate.send("payment-commands", refundCmd);
            CancelEnrollmentCommand cancelCmd = new CancelEnrollmentCommand(event.getEnrollmentId());
            kafkaTemplate.send("registration-commands", cancelCmd);
        }
    }
}

 

// Serwis Płatności – obsługa komendy od orkiestratora
@Service
public class PaymentService {
    @Autowired
    private KafkaTemplate<String, Object> kafkaTemplate;

    @KafkaListener(topics = "payment-commands", groupId = "payment-service")
    public void onPaymentCommand(ProcessPaymentCommand cmd) {
        boolean paid = paymentProcessor.processPayment(cmd.getStudentId(), cmd.getTrainingId());
        if (paid) {
            // odsyłamy zdarzenie z wynikiem pozytywnym
            kafkaTemplate.send("payment-events", new PaymentCompletedEvent(cmd.getEnrollmentId(), cmd.getTrainingId()));
        } else {
            // odsyłamy zdarzenie z wynikiem negatywnym
            kafkaTemplate.send("payment-events", new PaymentFailedEvent(cmd.getEnrollmentId(), cmd.getTrainingId()));
        }
    }
}

Powyższy kod pokazuje uproszczony schemat działania Saga z orkiestratorem. EnrollmentSagaOrchestrator to serwis, który inicjuje Sagę i reaguje na zdarzenia z poszczególnych kroków. Po rozpoczęciu (startEnrollmentSaga) wysyła komendę ProcessPaymentCommand na topic payment-commands. Serwis Płatności nasłuchuje ten topic i wykonuje logikę płatności, po czym publikuje odpowiedni event (PaymentCompletedEvent lub PaymentFailedEvent na payment-events). Orkiestrator (nasłuchujący payment-events) odbiera wynik i w metodzie onPaymentEvent decyduje co dalej: przy sukcesie płatności wysyła komendę rezerwacji miejsca (ReserveSeatCommand na training-commands), a przy porażce – od razu rozpoczyna kompensację, zlecając anulowanie rejestracji (CancelEnrollmentCommand na registration-commands). Analogicznie, wynik rezerwacji miejsca (SeatReserved lub SeatReservationFailed na training-events) jest obsługiwany w onSeatEvent. Po pozytywnej rezerwacji, orkiestrator zleca potwierdzenie rejestracji (ConfirmEnrollmentCommand), a po negatywnej – uruchamia kompensacje: zwrot płatności (RefundPaymentCommand) i anulację rejestracji.

Zauważmy, że w obu podejściach (choreografia i orkiestracja) posługujemy się Kafką do przesyłania zdarzeń/komend, jednak w modelu orkiestracji to orkiestrator wysyła komendy i interpretuje zdarzenia, podczas gdy w choreografii serwisy komunikują się bardziej bezpośrednio przez zdarzenia domenowe.

Warto wspomnieć, że istnieją gotowe frameworki ułatwiające implementację Saga w podejściu orkiestracji – np. orkiestrator oparty o state machine (maszynę stanów) lub dedykowane narzędzia jak Camunda, Temporal. W naszym przykładzie pokazaliśmy jednak, że można zrealizować Sagę samodzielnie, używając po prostu mechanizmu kolejek (Kafka) i trochę kodu koordynującego.

Saga – podsumowanie

Wzorzec Saga stał się fundamentalnym elementem projektowania spójności danych w architekturach mikroserwisowych. Pozwala pogodzić autonomię serwisów (własne bazy danych, brak silnych zależności) z potrzebą realizacji złożonych procesów biznesowych, które wymagają wielu kroków w różnych usługach.

Saga zastępuje tradycyjne transakcje rozproszone (jak 2PC) lżejszym mechanizmem opartym na zdarzeniach i kompensacjach, lepiej dopasowanym do środowisk rozproszonych i skalowalnych.

Omówiliśmy dwa podejścia do implementacji Sag:

  • Choreografia – prosta w implementacji i rozszerzaniu, oparta na luźno powiązanych zdarzeniach, choć trudniejsza w analizie gdy proces mocno się rozrasta.
  • Orkiestracja – z centralnym koordynatorem, zapewnia lepszą obserwowalność i kontrolę nad przepływem (szczególnie przy skomplikowanych scenariuszach i błędach), kosztem dodatkowego komponentu i silniejszego powiązania logiki.

W wielu realnych systemach wykorzystuje się hybrydę tych podejść – np. główny proces realizowany jest przez orkiestratora, ale poboczne działania (jak wysłanie e-maila) mogą być wpinane zdarzeniami w stylu choreografii. Niezależnie od wyboru stylu, kluczowe jest zrozumienie, że Saga to znacznie więcej niż kod – to pewien wzorzec myślenia o transakcjach rozproszonych. Projektując mikroserwisy, warto od początku uwzględnić mechanizmy umożliwiające implementację Sag (np. integrację z brokerem zdarzeń jak Kafka, przygotowanie operacji kompensacyjnych). Dzięki temu unikniemy pokusy niewłaściwych rozwiązań (jak nadmierne łączenie serwisów wspólną bazą czy ryzykowne próby użycia 2PC w środowisku rozproszonym).

Mam nadzieję, że ten materiał pokazał Ci praktycznie, jak Saga działa krok po kroku – od teorii do kodu. Teraz wiesz, że gdy następnym razem staniesz przed zadaniem zapewnienia spójności danych wśród wielu mikroserwisów, wzorzec Saga będzie potężnym narzędziem w Twoim repertuarze, pozwalającym zachować balans między niezależnością usług a niepodzielnością procesów biznesowych.

Powodzenia w implementacji Sag!

No comments
Share:

Struktury danych » Algorytmy i Struktury Danych

Praktycznie każdy program, czy nawet algorytm, operuje na różnego rodzaju danych. Wydajność oraz prostota tych systemów zależy w dużej mierze od postaci przetwarzanych informacji, a co za tym idzie – także wykorzystanych do tego celu struktur danych.

Przyjrzymy się dzisiaj wspólnie podstawowym strukturom danych, które są jednym z podstawowych narzędzi programisty oraz napiszemy proste przykłady z wykorzystaniem gotowych implementacji w Javie.


Co to jest algorytm❓

Algorytm możemy rozumieć jako jednoznaczny przepis postępowania, gdzie zamieniamy jakieś informacje wejściowe na oczekiwany wynik.
Czyli:

  • dostajemy coś na wejściu – np. użytkownik wprowadza dane do naszego systemu,
  • przetwarzamy te informacje – np. sprawdzając ich poprawność, usuwając duplikaty i ostatecznie zapisujemy je w pewnej strukturze danych do późniejszej  obróbki.
    Taka obróbka to może być np. wyciągnięcie najnowszych danych – w zależności od wybranej wcześniej struktury danych możemy to zrobić stosunkowo łatwo lub nie. 🙂
    Dlatego właśnie struktury danych są tak istotne.

Co to są struktury danych? 🤔

Strukturę danych można postrzegać jako swego rodzaju pojemnik na dane, który gromadzi informacje i układa je w odpowiedni sposób.

Zobaczmy, jak mogłoby to wyglądać w praktyce. Wyobraź sobie algorytm, który przetwarza informacje o polskich miastach, a do przechowywania informacji wykorzystuje zwykły tekst, np.

Gdańsk to miasto w północnej części Polski,
w województwie pomorskim, 
położone nad Morzem Bałtyckim. 
Populacja pod koniec 2017 roku wyniosła prawie pięćset tysięcy osób.

Dla człowieka zrozumienie powyższego tekstu nie stanowi większego problemu, jednak komputery nie myślą w tak abstrakcyjny sposób. Bardzo ciężko byłoby przygotować program, który zrozumiałby takie informacje i później mógłby je jeszcze przetwarzać.


Struktura danych

Komputery potrzebują bardziej jednoznacznych komunikatów, nie są też w stanie wywnioskować informacji z kontekstu (na ten moment pomijamy zagadnienia związane ze sztuczną inteligencją). W związku z tym powinniśmy najpierw odpowiednio ustandaryzować informacje i dopiero wtedy przekazać je w postaci zrozumiałej dla algorytmów.


Rekord – statyczna struktura danych

Rekord jest jedną z prostszych struktur danych, która świetnie nadaje się do prezentowania informacji o jednym obiekcie. Ponieważ w trakcie działania algorytmu nie zmienia on swego rozmiaru ani struktury, mówimy, że jest to statyczna struktura danych.

Uporządkujmy teraz dane z poprzedniego przykładu w formie prostego rekordu danych:

{
    name:       "Gdańsk",
    province:   "Pomorskie",
    population: 500000
}

W Javie możemy w tym celu wykorzystać klasę:

public class City {

    private String name;
    private String province;
    private long population;

    public City(String name, String province, long population) {
        this.name = name;
        this.province = province;
        this.population = population;
    }
}

City gdansk = new City("Gdańsk", "Pomorskie", 500000);

Dane zebrane w tej formie są już w pewien sposób uporządkowane, dzięki czemu można je łatwiej przetwarzać i analizować. Rekord bardzo dobrze sprawdza się, gdy chcemy przechować dane na temat tylko jednego obiektu. Jednak co zrobić, kiedy takich obiektów będzie więcej: dziesiątki lub nawet tysiące?


Tablice (Array)

Powiedzieliśmy sobie wcześniej, że chcemy przetwarzać informacje o wszystkich polskich miastach. W takim wypadku sam pojedynczy rekord nie wystarczy.

Z pomocą może przyjść kolejna struktura danych – tablica.
Tablice bardzo dobrze sprawdzają się w sytuacji, gdy mamy pewien zbiór danych tego samego typu, który nie będzie modyfikowany podczas działania algorytmu. Rozmiar tego typu struktur musimy jednak określić już na samym początku, podczas podawania wstępnych parametrów.

City[] cities = new City[100];
cities[0] = new City("Gdańsk", "Pomorskie", 500000);

Inną charakterystyczną cechą tablicy, poza jej stałym rozmiarem, jest umiejscowienie kolejnych jej elementów obok siebie w pamięci, dzięki czemu mamy możliwość prostego i szybkiego dostępu do nich przy pomocy indeksów.

Indeks 0 1 2 3 4
Wartość v1 v2 v3 v4 v5

Tablice mają jednak jedną zasadniczą wadę, mianowicie – jak już wspomniałem – ich rozmiar musi być zdefiniowany już na samym początku, w momencie tworzenia. Wskutek tego przechowywanie w nich zmiennej ilości elementów jest kłopotliwe i może być mało wydajne.

Ten problem nie dotyczy kolejnej struktury, którą za chwilę poznamy.

➡ ZOBACZ 👉: Tablice


Listy (List)

Lista, podobnie jak tablica, przeznaczona jest do przechowywania większej ilości danych. Z tym wyjątkiem, że lista umożliwia łatwe dodawanie nowych elementów.

Listę można postrzegać jako łańcuszek połączonych ze sobą danych. Wiedząc, gdzie znajduje się początek, możemy znaleźć kolejne ogniwa takiej struktury.

Struktury danych lista

Struktury danych lista

Istnieją dwie popularne realizacje struktury listy: tablicowa oraz wskaźnikowa. W Javie obie implementują interfejs List, zatem w wielu przypadkach mogą być one używane zamiennie. Na ostateczną decyzję, którą implementację wybrać wpływ będą miały poszczególne parametry dostosowane do konkretnego projektu i naszych potrzeb (a czasem również preferencji).

Lista tablicowa – ArrayList

Już sama nazwa wskazuje, że do implementacji tej listy została wykorzystana tablica. Jest to tak naprawdę zwykła tablica wyposażona w dodatkowe funkcje, które ukrywają złożoną logikę i umożliwiają np. usunięcie elementu ze środka listy, czy zwiększenie jej rozmiaru.

Dopisanie elementu na końcu listy, gdy rozmiar wewnętrznej tablicy został już wykorzystany, wymusza utworzenie nowego większego obszaru roboczego i przekopiowanie do niego wszystkich bieżących wartości. Natomiast usunięcie elementu ze środka listy wymaga przesunięcia wszystkich kolejnych segmentów w wewnętrznej tablicy o jedną pozycję do tyłu. Natomiast – gdy korzystamy z ArrayList, te wszystkie skomplikowane operacje są wykonywana za nas automatycznie i często nawet nie jesteśmy ich świadomi.

Największą zaletę listy tablicowej stanowi jej prosta nawigacja z wykorzystaniem indeksu. Natomiast wadą jest niska elastyczność i wydajność w przypadku częstych zmian rozmiaru i usuwania elementów. W związku z tym ArrayList świetnie sprawdza się w sytuacjach, kiedy elastyczność odgrywa mniejszą rolę, a potrzebna jest szybka i prosta nawigacja po poszczególnych elementach listy.

List list = new ArrayList();
list.add("A");
list.add("B");
String b = (String) list.get(1);

Lista wskaźnikowa – LinkedList

Implementacja wskaźnikowa wymusza dodanie do każdego elementu listy nowej wartości: wskaźnika, czyli referencji, dzięki czemu zrealizowana jest lokalna nawigacja w liście. W przeciwieństwie do tablicy logiczna kolejność elementów w liście wskaźnikowej może być inna niż jej fizyczne ułożenie w pamięci.

Dodanie nowego elementu do listy w tej implementacji wymaga utworzenia kolejnej wartości i aktualizacji wskaźników. Podobnie wygląda usuwanie elementów. Nawet jeżeli usuniemy komponent ze środka listy, to wystarczy, że zostaną zaktualizowane wskaźniki z pominięciem usuniętego elementu. Nie ma zatem konieczności zmieniania wszystkich pozostałych rekordów. Dlatego tego typu listy bardzo dobrze sprawdzają się w przypadku, gdy często modyfikujemy (dodajemy i usuwamy) elementy z listy. W konsekwencji tracimy jednak możliwość uzyskania szybkiego dostępu do konkretnej wartości przy pomocy indeksu.

List list = new java.util.LinkedList();
list.add("A");
list.add("B");
String b = (String) list.get(1);

Ciekawe jest, że implementacja LinkedList dalej oferuje nam możliwość pobierania elementów przy pomocy indeksu, jednak żeby to zrealizować i odnaleźć odpowiedni rekord – musi przeiterować po jej elementach.

W zależności od ilości wskaźników oraz sposobu ich wykorzystania w liście możemy wyróżnić kilka szczególnych przypadków jej implementacji.

Lista jednokierunkowa

Najprostszą formą listy jest lista jednokierunkowa, w której każdy element zawiera  referencję do kolejnego (lub poprzedniego) komponentu w liście lub do wartości pustej (NULL), jeżeli jest to ostatni jej element.

Lista dwukierunkowa

Lista dwukierunkowa jest rozwinięciem listy jednokierunkowej. W tym wypadku poszczególny rekord w liście zawiera referencję do poprzedniego i kolejnego elementu. Dzięki takiej implementacji można swobodnie poruszać się po liście w górę i w dół.

Lista cykliczna

W tej liście ostatni element jest powiązany z pierwszym, a pierwszy – z ostatnim. Dzięki temu tworzy się zamknięty cykl i możemy poruszać się wkoło. W związku z tym taka lista charakteryzuje się również brakiem początkowego wskaźnika (głowa listy – HEAD) oraz ostatniego (ogon listy – TAIL).


Stos (Stack) – LIFO

Stos nazywany jest również kolejką LIFO, czyli 'ostatni na wejściu, pierwszy na wyjściu’ (z ang. Last In, First Out). Bardzo dobrze nadaje się do sytuacji, gdy chcemy przeprowadzać operacje najpierw na najnowszych danych, a dopiero później – na starszych.

Najłatwiej wyobrazić sobie tę strukturę jako stos talerzy do pozmywania ułożonych jeden na drugim. Zaczynamy od obiektów znajdujących się na samej górze, jednak gdy ktoś w trakcie wykonywania przez nas czynności przyniesie jeszcze brudne naczynia, to wylądują one na samym szczycie stosu.

Natomiast – aby dostać się do elementów znajdujących się na samym dole – trzeba najpierw ściągnąć wszystkie inne.

Podstawowe operacje na stosie to:

  • push (obiekt) – dodanie obiektu na wierzch stosu;
  • pop () – ściągnięcie jednego elementu ze stosu i zwrócenie jego wartości.
Deque<String> stack = new java.util.LinkedList();
stack.push("A");
stack.push("B");

stack.pop();
String a = stack.pop();

➡ ZOBACZ 👉: Stos (Stack) – 7+ tajników implementacji LIFO


Kolejka (Queue) – FIFO

Przeciwieństwem stosu LIFO jest kolejka typu FIFO (ang. First In, First Out), czyli 'pierwszy na wejściu, pierwszy na wyjściu’. W tym przypadku zaczynamy przetwarzanie danych od elementów, które pojawiły się jako pierwsze. Jest to odpowiednik zwykłej kolejki w sklepie.

java.util.Queue<String> queue = new java.util.LinkedList();
queue.add("A");
queue.add("B");

String a = queue.poll();

Szczególną odmianą tej struktury danych jest kolejka priorytetowa. W tej implementacji konkretne rekordy dodatkowo posiadają przypisany priorytet, który wpływa na kolejność późniejszego pobierania elementów z listy. Najpierw przetwarzane są najpilniejsze elementy (o najwyższym priorytecie), a dopiero potem te mniej ważne.

Tego typu kolejki spotyka się przede wszystkim w systemach, gdzie przetwarzane są różnego rodzaju zadania i zależy nam na ich odpowiednim uporządkowaniu.


Zbiór (Set)

Zbiór to kolekcja elementów, która nie może zawierać duplikatów.

W Javie najczęściej wykorzystywane są dwie implementacje: HashSet oraz TreeSet.

Set<String> hashSet = new HashSet<>();
hashSet.add("c1");
hashSet.add("a1");
hashSet.add("b1");
hashSet.add("b1");

Set<String> treeSet = new TreeSet<>();
treeSet.add("c1");
treeSet.add("a1");
treeSet.add("b1");
treeSet.add("b1");

System.out.println(hashSet); // [a1, c1, b1]
System.out.println(treeSet); // [a1, b1, c1]

Główna różnica między tymi dwiema implementacjami polega na tym, że TreeSet wyznacza kolejność elementów (domyślnie jest ona rosnąca), a HashSet – nie. W szczególnych przypadkach może się jednak zdarzyć, że HashSet również posortuje elementy rosnąco, jednak implementacja tego nie gwarantuje.

Chcąc dodać do Set’a instancje swej własnej klasy, musisz pamiętać o odpowiednim zaimplementowaniu metod: hashCode oraz equals. Jeżeli nie zachowasz założeń kontraktu między tymi metodami, możesz spodziewać się bardzo dziwnych błędów. Więcej na ten temat przeczytasz w podlinkowanym artykule.

Dodatkowo w przypadku TreeSet klasy przechowywanych obiektów muszą implementować interfejs: java.lang.Comparable.

  • Zobacz 👉 hashCode i equals – co grozi Ci za złamanie kontraktu między metodami equals i hashCode?

Dynamiczne struktury danych

Dynamiczne struktury danych w przeciwieństwie do statystycznych (takich jak np. rekord) pozwalają na zmianę ich struktury już podczas działania algorytmu.

Jest to bardzo wygodne, ponieważ na starcie bardzo rzadko kiedy wiemy ile i jakie dokładnie dane będziemy przetwarzać.

Taka swoboda ma jednak swoją cenę – tego typu struktury danych są zwyczajnie bardziej skomplikowane. Dostęp do przechowywanych w nich  danych odbywa się często przy pomocy specjalnych wskaźników, a modyfikacje struktury przy pomocy odpowiednich metod.

Całe szczęście, że o ile sami nie chcemy napisać ręcznie implementacji takiej struktury, to cały niezbędny kod powinien być już gotowy i dla nas zostaje tylko wywołanie odpowiedniej metody.

Przykłady struktur dynamicznych to np. stos, kolejka, lista jedno i dwukierunkowa, drzewo itp.


Mapa (Map) 🗺

Mapa to specyficzna kolekcja, która przechowuje pary danych składające się z klucza oraz przypisanej wartości.

Klucz w obrębie mapy musi być unikatowy, natomiast wartości mogą się powtarzać.

Map<String, Integer> map = new HashMap<>();
map.put("Gdańsk", 10);
map.put("Warszawa", 5);
map.put("Warszawa", 7);

System.out.println(map);    // {Gdańsk=10, Warszawa=7}

Na powyższym przykładzie widać, że ponowne przypisanie wartości dla tego samego klucza powoduje nadpisanie poprzedniej wartości.


Struktury danych – Podsumowanie 💪

Struktury danych są bardzo ważnym narzędziem w rękach każdego programisty. Jednak jak z każdym narzędziem, trzeba wiedzieć kiedy i jak z niego skorzystać.
To od nas jako deweloperów zależy, czy dobrze wykorzystamy te możliwości. Dobrze dobrana struktura danych może w znacznym stopniu wpłynąć na czytelność oraz wydajność naszych aplikacji.

6 komentarzy
Share:
Stos – LIFO

Stos (Stack) – 7+ tajników implementacji LIFO

W tym wpisie pokażę Ci, jak twórcy Javy zaimplementowali takie struktury danych, jak FIFOLIFO oraz zdradzę, jak możesz zrobić to samodzielnie.
Następnie przekonam Cię, że wcale nie warto tego robić ręcznie i lepiej skorzystać z ich pracy.
Zapraszam  do lektury.

[SprawnyProgramista_intro]

Z tej serii dowiesz się:

  • co to jest LIFO, FIFO, HIFO, FEFO, FINO oraz FISH; 🙂
  • co to jest i jak działa stos (ang. stack);
  • jak działa kolejka (ang. queue) oraz kolejka priorytetowa (ang. priority queue);
  • jak samodzielnie zaimplementować takie struktury danych;
  • oraz jak korzystać z gotowych rozwiązań.

Stos (ang. Stack)

Programiści bardzo chętnie czerpią z doświadczeń życia codziennego – podobnie jest i w tym wypadku.

Zastanów się – z czym kojarzy Ci się pojęcie stos?

Może to być: stos książek, stos talerzy do zmywania, stos drewna do palenia itp.

Jest to zwyczajnie kilka rzeczy ułożonych jedna na drugiej. Dokładnie tak samo jest w informatyce – stos danych rozumiemy jako zbiór elementów „ułożonych jeden na drugim”.

Jak w takim razie dostać się do poszczególnych elementów w takim stosie?

Wyobraź sobie, że leży przed tobą stos książek ułożonych jedna na drugiej.
Spróbuj teraz wziąć książkę, która znajduje się na samym szczycie tego stosu – będzie to dość łatwe. Prawda?

Teraz zróbmy coś trudniejszego.
Postaraj się wziąć książkę, która jest w środku tego stosu lub na jego samym spodzie.

Co musisz zrobić?
Zakładamy, że nie chcesz mieć porozrzucanych książek po całym pokoju, dlatego najrozsądniej byłoby zdejmować od góry kolejne książki i odkładać je na bok tak długo, aż znajdziesz swoją wybraną książkę.

Taki typ kolejkowaniu elementów nazywamy: LIFO.

LIFO (ang. Last In, First Out)

Wszystkie elementy w stosie ułożone są zgodnie z zasadą LIFO.

LIFO (ang. Last In, First Out) – w dosłownym tłumaczeniu oznacza: ostatnie przyszło, pierwsze wyszło.

Metoda LIFO w kontekście obsługi magazynów nazywana jest również metodą najpóźniejszej dostawy – jako pierwsze zostaną wydane elementy/produkty, które najkrócej były przechowywane.

Wracając do naszego przykładu ze stosem książek.
Żeby wyjąć książkę, która jest na samym dole stosu, musisz zdjąć z niego kolejno wszystkie książki – poczynając od tych na samej górze.

Przez takie ułożenie danych w stosie:

  • łatwo jest zdjąć z niego elementy z samego wierzchu;
  • jeżeli natomiast chcemy pobrać elementy znajdujące się niżej, to musimy przejść przez wszystkie te, które są nad nim.

LIFO vs FIFO

Przeciwieństwem do omawianego tu stosu i organizacji elementów zgodnie z LIFO
jest kolejka z elementami ułożonymi wg zasady FIFO (ang. First In, First Out) – czyli pierwszy na wejściu, pierwszy na wyjściu.

Więcej na ten temat będziesz mógł przeczytać w drugiej części tego wpisu:
Kolejka (Queue) – jak samodzielnie zaimplementować FIFO?

LIFO i stos w informatyce

Bufory w formie stosu LIFO bardzo chętnie wykorzystywane są w informatyce do przechowywania danych lub jako system planowania zadań.

Omówimy sobie teraz główne koncepcje związane z wykorzystywaniem stosu.

Głowa (ang. head)

Zacznijmy od pojęcia głowy (ang. head) stosu – jest to wskaźnik określający, w którym miejscu znajduje się najnowszy/pierwszy element stosu.

Poszczególne operacje, które możemy na nim wykonać, takie jak dodanie elementu do stosu  (ang. push), podejrzenie pierwszego elementu (ang. peek), czy jego pobranie (ang. pop), zawsze operują właśnie na tym wskaźniku.

Stos push (ang. stack push)

Metoda stos push (ang. stack push) polega na dodaniu nowego elementu – „kładziemy” nowy element na wierzchu stosu i od teraz wskaźnik head wskazuje właśnie na ten element.

Stos push (ang. stack push)

Stos push (ang. stack push)

Stos pop (ang. stack pop)

Metoda stos pop (ang. stack pop) zwraca pierwszy element ze stosu, jednocześnie go zdejmując – czyli bierzemy jedną rzecz z samej góry stosu i ją zabieramy. Przez co, po wykonaniu tej metody, wskaźnik head wskazuje na element, który był niżej w stosie lub – jeżeli nie mamy już elementów – to head = null.

Stos pop

Stos peek (ang. stack peek)

Metoda stos peek (ang. stack peek) działa podobnie jak stos pop, zwracając pierwsze element ze stosu, jednak nie modyfikuje zawartości samego stosu. Można ją wykorzystać np. do podejrzenia, jaki element jest na wierzchu naszej struktury danych.

Stos w Javie (ang. Stack Java)

Przyjrzyjmy się teraz bliżej, co Java oferuje nam w kontekście tych struktur danych.

Zamieszczone poniżej fragmenty kodu napisane są w Javie, jednak przykłady są na tyle uniwersalne, że nie powinno być problemu z odniesieniem ich do innych języków programowania.

W Javie mamy do dyspozycji kilka klas implementujących stos i LIFO.
Zaczniemy od java.util.Stack, który jest klasyczną strukturą danych dziedziczącą po java.util.Vector, a co za tym idzie – implementującą między innymi java.util.List.

Przy jej pomocy możemy wykonać wszystkie podstawowe operacje: push, pop i peek.

1. Utworzenie stosu

Stack stack = new Stack();

lub wersja ze wsparciem dla typów generycznych:

Stack<String> stack = new Stack<String>();

2. Dodawanie nowego elementu (ang. stack push)

stack.push("1");

3. Zdjęcie ze stosu pierwszego elementu (ang. stack pop)

String pop = stack.pop();

4. Pobranie pierwszego elementu bez modyfikacji stosu (ang. stack peek)

String peek = stack.peek();

5. Przeszukiwanie stosu (ang. stack search)

Stack<String> stack = new Stack<String>();
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");

// when
int search1 = stack.search("2");    // 3
int search2 = stack.search("0");    // -1

Metoda search zwraca pozycję danego elementu na stosie lub -1, jeżeli nie znajdzie takiego elementu.

UWAGA: Pozycje numerowane są od 1, czyli obiekt, który znajduje się na samej górze stosu, ma numer 1, kolejny 2 i tak dalej.

6. Przeszukiwanie stosu – indeks elementu

Do przeszukiwania stosu możemy również wykorzystać metodę: public int indexOf(Object o) .

UWAGA: W tym wypadku jednak elementy będą numerowane od 0 i zaczynamy liczyć od elementu, który jest na samym dole stosu 🙂

int indexOf1 = stack.indexOf("2");    // 1
int idnexOf2 = stack.indexOf("0");    // -1

7. Przeglądanie stosu (ang. stack iterate)

Elementy na stosie możemy przeglądać na kilka różnych sposobów, np. korzystając ze wbudowanego iteratora: stack.iterator().
W tej sytuacji należy jednak pamiętać, że elementy będą zwracane w kolejności od tego na samym spodzie stosu!

Stack<String> stack = new Stack<String>();
stack.push("A");
stack.push("B");
stack.push("C");

Iterator<String> it = stack.iterator();
while (it.hasNext()) {
	String item = it.next();
	System.out.println(item);
}

Alternatywnie można skorzystać z pętli while oraz metody pop – jak w drugim przykładzie.

while (!stack.isEmpty()) {
	String item = stack.pop();
	System.out.println(item);
}

8. Korzystanie ze stosu przy pomocy strumieni i wyrażeń lambda (ang. stack java stream)

Nic nie stoi na przeszkodzie, żeby ze stosu korzystać przy pomocy strumieni i wyrażeń lambda.
Najpierw pobieramy strumień, korzystając z metody: stream(), i wykonujemy niezbędne operacje.

Poniżej kilka przykładów.

  • Wyświetlenie wszystkich elementów na standardowe wyjście.
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

stack.stream().forEach(System.out::print);
System.out.println();
  • Zamiana stosu na listę.
List<Integer> list = stack.stream().collect(Collectors.toList());
System.out.println(list);
  • Usunięcie wybranych elementów.
stack.removeIf(element -> element > 3);
  • Zamiana stosu na tablicę.
int[] intArray = stack.stream()
		.mapToInt(element -> element)
		.toArray();

System.out.println(Arrays.toString(intArray));

Rekomendowana implementacja stosu w Javie (java.util.Deque)

Na java.util.Stack świat Javy się nie kończy. Do dyspozycji mamy jeszcze chociażby interfejs: java.util.Deque oraz dwie implementacje: java.util.ArrayDeque i java.util.LinkedList.

Mimo iż jest to inny interfejs i inne implementacje, to zasada działania powyższych klas z punktu widzenia użytkownika jest analogiczna.
Możemy skorzystać ze standardowych metod: push, pop i peek oraz w przypadku np. LinkedList wielu innych.

Warto jest się przyjrzeć temu rozwiązaniu nie tylko dlatego, że daje ono więcej możliwości, ale jest to również implementacja rekomendowana przez twórców samej Javy.
Jako główny argument przeciwko java.util.Stack podawany jest fakt, że nie mamy rozdzielonego interfejsu i implementacji, a sama klasa dziedziczy po przestarzałym już java.util.Vector.

Poniżej kilka przykładów z wykorzystaniem Deque.

// given
Deque<Integer> deque = new LinkedList<>();
deque.push(1);
deque.push(2);
deque.push(3);

// when
Integer pop = deque.pop();
Integer peek = deque.peek();
int size = deque.size();

// then
assertThat(pop).isEqualTo(3);
assertThat(peek).isEqualTo(2);
assertThat(size).isEqualTo(2);

Przepełnienie stosu

Poznaliśmy już podstawy, dlatego pobawmy się teraz z odrobinę ciekawszymi zagadnieniami.

A co gdyby tak dodawać do naszego stosu w nieskończoność nowe elementy? 🙂

Wracając do naszego pierwotnego przykładu z książkami – na brak książek w domu nie mogę narzekać, także raczej by mi ich szybko nie zabrakło.
Podejrzewam jednak, że powyżej pewnej wysokości wszystko by całkiem nieźle walnęło… (Znasz taką grę Jenga? Jeżeli nigdy w nią nie grałeś, to gorąco polecam.)

W informatyce taki pomysł musi skończyć się podobnie – coś na pewno się zepsuje lub skończy.

Zasadniczo mamy dwa możliwe scenariusze:

  • skończy nam się pamięć i cała aplikacja się wysypie;
  • lub implementacja stosu uzna, że nie może już przyjmować nowych obiektów i nam to zakomunikuje. Jeżeli odpowiednio przechwycimy taki komunikat, to jest szansa, że uratujemy jeszcze aplikację. Jeżeli nie, to i w tym wypadku całka aplikacja się złoży.
Deque<Long> stack = new LinkedList<>();

long i = 0;
while (true) {
	stack.push(i++);
}

OutOfMemoryError

Po wykonaniu powyższego kodu mój komputer na chwilę przygasł…
Java wykorzystała ponad 600% CPU, po czym cały proces zakończył swój żywot, zgłaszając błąd: java.lang.OutOfMemoryError: Java heap space.

java.lang.OutOfMemoryError: Java heap space

Wniosek z tego przykładu płynie taki, że nie możemy bezkarnie w nieskończoność dodawać elementów do stosu ani żadnej innej struktury danych.

Jeżeli chcemy się ustrzec przed podobnymi problemami, trzeba przemyśleć strategię usuwania starych elementów lub w pewnym momencie powiedzieć STOP i przestać dodawać kolejne elementy.

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.base/java.lang.Long.valueOf(Long.java:1180)
	at pl.stormit.stacklifo.DequeTest.x(DequeTest.java:37)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:566)

Jednak nie tylko my jako szeregowi programiści musimy uważać na tego typu problemy.
Z analogicznymi trudnościami musieli zmierzyć się również programiści samej Javy.

StackOverflowError

Przyjrzymy się teraz bliżej niechlubnemu błędowi: java.lang.StackOverflowError.

Możemy się z nim spotkać, gdy np. napiszemy nieskończoną rekurencję – fragment kodu, który w nieskończoność będzie wywoływał sam siebie.

Kod poniżej z założenia będzie wywoływał w nieskończoność tę samą metodę – chyba że…

@Test
void invinityStack2() {
	invinityStack2();
}

Chyba że skończy nam się miejsce na stosie 🙂

Każde wywołanie metody w Javie odkładane jest na wewnętrznym stosie, a po zakończeniu wykonywania takiej metody zdejmowane z tego stosu.

No chyba że wpadniemy na pomysł, żeby w nieskończoność wywoływać jakąś metodę i cały czas dodawać nowe wpisy do tego stosu.
Wtedy musimy się liczyć, że dostaniemy taki wyjątek:

java.lang.StackOverflowError
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)
	at pl.stormit.stacklifo.DequeTest.invinityStack2(DequeTest.java:43)

Stos w innych językach programowania (PHP, Python, C++)

PHP

W PHP stos możemy zaimplementować z wykorzystaniem np. metod: array_unshift i array_shift lub oprzeć się na gotowych rozwiązaniach.

<?php
class ReadingList
{
    protected $stack;
    protected $limit;
     
    public function __construct($limit = 10) {
        // initialize the stack
        $this->stack = array();
        // stack can only contain this many items
        $this->limit = $limit;
    }
 
    public function push($item) {
        // trap for stack overflow
        if (count($this->stack) < $this->limit) {
            // prepend item to the start of the array
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!'); 
        }
    }
 
    public function pop() {
        if ($this->isEmpty()) {
            // trap for stack underflow
          throw new RunTimeException('Stack is empty!');
      } else {
            // pop item from the start of the array
            return array_shift($this->stack);
        }
    }
 
    public function top() {
        return current($this->stack);
    }
 
    public function isEmpty() {
        return empty($this->stack);
    }
}

Źródło: Data Structures for PHP Devs: Stacks and Queues

Python

W minimalistycznej wersji w Pythonie możemy skorzystać ze zwykłej listy jako stosu.

>>> stack = []
>>> stack.append('A')
>>> stack.append('B')
>>> stack.append('C')
>>> stack.pop()
'C'
>>> stack.pop()
'B'
>>> stack.pop()
'A'
>>> stack.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list

Po więcej szczegółów odsyłam do zewnętrznego artykułu: How to Implement a Python Stack.

C/C++

Przykładowa implementacja stosu w C++.

#include <iostream> 
#include <stack> 
using namespace std; 
  
void showstack(stack <int> s) 
{ 
    while (!s.empty()) 
    { 
        cout << '\t' << s.top(); 
        s.pop(); 
    } 
    cout << '\n'; 
} 
  
int main () 
{ 
    stack <int> s; 
    s.push(10); 
    s.push(30); 
    s.push(20); 
    s.push(5); 
    s.push(1); 
  
    cout << "The stack is : "; 
    showstack(s); 
  
    cout << "\ns.size() : " << s.size(); 
    cout << "\ns.top() : " << s.top(); 
  
  
    cout << "\ns.pop() : "; 
    s.pop(); 
    showstack(s); 
  
    return 0; 
}

Źródło: Stack in C++ STL.

Inny systemy kolejkowania

Do pełnego obrazu sytuacji brakuje nam już tylko wyjaśnienia innych skrótowców, które często pojawiają się w kontekście FIFO.

FCFS (ang. First-Come, First-Served)

FCFS (ang. First-Come, First-Served) – czyli w dosłownym tłumaczeniu: pierwsze przyjdzie, pierwsze będzie podane. Skrótowiec wykorzystywany najczęściej w kontekście zarządzania zapasami.

FEFO (ang. First Expired, First Out)

FEFO (ang. First Expired, First Out) – czyli w dosłownym tłumaczeniu pierwsze, które będzie przedawnione, pierwsze idzie na zewnątrz. Tego typu podejście może być np. wykorzystane przy łatwo psujących się produktach lub takich o krótkim terminie przydatności.

Z punktu widzenia technicznego jest to po prostu kolejka priorytetowa (ang. priority queue).

FINO (ang. First In, Never Out)

FINO (ang. First In, Never Out) – to dowód na to, że programiści też mają poczucie humoru 🙂

FINO możemy przetłumaczyć na: pierwsze weszło, nigdy nie wyszło – co oczywiście ma być prześmiewczą analogią do FIFO i LIFO.

FISH (ang. First In, Still Here)

FISH (ang. First In, Still Here) – akronim FISH powstał na podobnej zasadzie jak FINO, tłumaczymy go jako: pierwsze weszło, ciągle tam jest.

Samodzielna implementacja LIFO (Stack)

Na koniec pobawimy się jeszcze praktycznymi zadaniami.

Powiedzieliśmy sobie, że elementy w stosie ułożone są zgodnie z zasadą LIFO. Jednak sam stos może być zaimplementowany na kilka różnych sposobów.

Najczęściej możemy spotkać się z dwiema implementacjami stosu:

  • opartej o cykliczny bufor danych (ang. circular buffer) lub
  • zaimplementowanej z wykorzystaniem listy – najczęściej listy wskaźnikowej (ang. linked list),
  • choć możliwa jest też implementacja z wykorzystaniem zwykłej tablicy.

Przerobienie tych przykładów nie jest konieczne do zrozumienia omawianych tu pojęć i w zdecydowanej większości przypadków dużo lepszym wyjściem jest skorzystanie z gotowych już klas implementujących stos, takich jak java.util.LinkedList.
Mimo wszystko zachęcam do ich przejrzenia i samodzielnej próby implementacji – jest to świetny sposób na utrwalenie wiedzy w praktyce i pełniejsze zrozumienie tematu.

W poniższych przykładach skupię się na ręcznej implementacji z wykorzystaniem własnej listy wskaźnikowej (ang. linked list).

Interfejs stosu i główne wymagania

Nasz stos powinien implementować wszystkie podstawowe metody, takie jak: pop, push, peek i size. Zanim jednak przejdziemy do samej implementacji, zacznijmy od zdefiniowania interfejsu – czyli określmy, co właściwie będzie robił nasz stos.

Na tym etapie jeszcze nie określamy, jak będzie to realizowane – tym zajmiemy się podczas implementacji.

public interface Stack<T> {
	T peek();

	T pop();

	void push(T value);

	int size();
}

Wewnętrzna struktura przechowująca elementy

Każdy element na naszym stosie będzie się składał z samej wartości przechowywanego elementu oraz informacji o tym, jaki element znajduje się pod nim. Dzięki temu, mając referencję do najwyższego elementu, będziemy mogli dostać się do pozostałych.

private static class Entry<T> {
	private T value;
	private Entry<T>;

	public Entry(T value, Entry<T> prev) {
		this.value = value;
		this.prev = prev;
	}
}

Wskaźnik na głowę (ang. head) stosu

Potrzebujemy jeszcze przechować informację o tym, który element jest na samej górze – robimy to przy pomocy wskaźnika: head.

public class LinkedStack<T> implements Stack<T> {

    private Entry<T> head;
}

Rozmiar stosu (ang. stack size)

Żeby za każdym razem nie liczyć wszystkich elementów, które są na stosie, do przechowania rozmiaru wykorzystamy wewnętrzną zmienną.

private int size = 0;

Dodanie elementu do stosu (ang. push)

Dodając nowy element do stosu:

  • tworzymy wewnętrzną strukturę, która przechowuje nasz element oraz informację o poprzednim elemencie, który był na szczycie stosu, czyli dotychczasowej głowie;
  • podmieniamy wskaźnik przechowujący głowę stosu na nasz nowy obiekt;
  • i na końcu inkrementujemy zmienną przechowującą rozmiar stosu.
@Override
public void push(T value) {
	Entry<T> entry = new Entry<T>(value, head);

	head = entry;

	size++;
}

Zdjęcie elementu ze stosu

Chcąc zdjąć element ze stosu:

  • sprawdzamy, czy stos nie jest pusty (head == null);
  • pobieramy wartość elementu wskazywanego przez head;
  • nadpisujemy wskaźnik head, tak by wskazywał na element znajdujący się pod nim;
  • zwracamy wartość elementu.
public T pop() {
	if (head == null) {
		return null;
	}

	T value = head.value;

	head = head.prev;

	size--;

	return value;
}

Podejrzenie elementu znajdującego się na szczycie stosu

Metoda peek sprawdza, czy stos nie jest pusty i zwraca wartość obiektu wskazywanego przez head.

public T peek() {
	if (head == null) {
		return null;
	}

	return head.value;
}

Pełna implementacja

interface Stack<T> {
	T peek();

	T pop();

	void push(T value);

	int size();
}


class LinkedStack<T> implements Stack<T> {

	private static class Entry<T> {
		private T value;
		private Entry<T> prev;

		public Entry(T value, Entry<T> prev) {
			this.value = value;
			this.prev = prev;
		}
	}

	private Entry<T> head;

	private int size = 0;

	@Override
	public T peek() {
		if (head == null) {
			return null;
		}

		return head.value;
	}

	@Override
	public T pop() {
		if (head == null) {
			return null;
		}

		T value = head.value;

		head = head.prev;

		size--;

		return value;
	}

	@Override
	public void push(T value) {
		Entry<T> entry = new Entry<T>(value, head);

		head = entry;

		size++;
	}

	@Override
	public int size() {
		return size;
	}
}

Zadania do samodzielnego rozwiązania

Jeżeli ciągle szukasz wyzwań i chcesz poćwiczyć zadania z wykorzystaniem stosu – poniżej masz kilka inspiracji.

  • odwrócenie listy elementów przy pomocy stosu;
  • samodzielna implementacja stosu przy pomocy wewnętrznej tablicy.

Rozwiązania wszystkich zadań i inne przykłady kodu znajdziesz na repozytorium github.

Podsumowanie i druga część wpisu

Na dzisiaj to już wszystko. Bardzo Ci dziękuję, że wytrwałeś do końca. Zachęcam Cię przede wszystkim do samodzielnego wypróbowania omawianego dziś stosu oraz rozwiązania zadań. Wynikami swojej pracy możesz jak zawsze podzielić się na grupie.

A już niedługo druga część wpisu: Kolejka (Queue) – jak samodzielnie zaimplementować FIFO?

Dodatkowe materiały:

 

kierunek java

No comments
Share: