Dlaczego disruptor jest szybki?

W moim poprzednim wpisie W poszukiwaniu szybkości, wspomniałem o ciekawej bibliotece stworzonej przez firmę LMAX, mianowicie disruptor. Jest szeroko używanym narzędziem w sporej części aplikacji, gdzie frazy takie jak low-latency lub high throughput ścielą się gęsto, a osoby je tworzące próbują rozwiązywać problemy obsługujące, nie jeden tysiąc żądań na sekundę, ale sto tysięcy. Pod pewnym względem, niszowe, bo i specyfika problemu nie jest tak potoczna. Nie tak potoczna, jak RESTowe kontrolery automatycznie konfigurowane przez Spring Boota. Zresztą, czy sam wiesz jaka jest przepustowość Twojej aplikacji?

Nakreślenie i zrozumienie problemu

Tworząc aplikacje bądź systemy, które mają działać wedle jasno określonych kryteriów trzeba być bardzo metodycznym. Nie ma co liczyć na ślepy traf i liczyć, że system będzie działał wedle założeń przez przypadek. Twórcy disruptora również kierowali się tymi przesłankami, a ta świetna biblioteka powstała przez przypadek jako efekt uboczny. Ich celem było stworzenie bardzo wydajnego i szybkiego systemu i aby tego dopiąć, zaczęto zbierać szczegółowe statystyki jak poszczególne fragmenty tegoż systemu radziły sobie z przetwarzaniem. Okazało się, że serce ich systemu, zaawansowana logika biznesowa, mająca wyróżniać ich na tle konkurencji, przez swoją kapitalną wydajność zajmuje zaniedbywalny fragment czasu, ale na nic się to zda, jeśli lwią część czasu pochłaniało przekazywanie danych pomiędzy kolejkami i to właśnie te miejsca miały determinować, czy osiągną wyznaczone założenia, przekładające się na sukces systemu oraz firmy.

Poznali więc dokładnie, gdzie musi być przyłożona siła, aby efekt był możliwie największy. Z tego mamy pierwszy, bardzo prosty wniosek:

Mierzyć, mierzyć i jeszcze raz mierzyć. Nigdy nie działać na ślepo.

Blokowanie źródłem całego zła

Skuteczne tworzenie wydajnych systemów nie musi się wiązać z przełomowymi odkryciami. Czasami przestrzeganie prostych wytycznych może w znaczący sposób poprawić wydajność systemu. Weźmy np. wszelkiej maści pauzy w systemie. Nikt przy zdrowych zmysłach nie wywołuje Thread.sleep(), ale opóźnienia wynikające z aktywnego oczekiwania na wynik operacji, czyli domyślne synchroniczne wywołanie metod, również takim opóźnieniem może się okazać. Trzeba więc mocno się pilnować, aby ciężkie procesy były przerzucane na poboczne wątki. Idąc dalej, sama synchronizacja wątków odczytujących kolejne obiekty ze źródła danych, podobnie, może okazać się zauważalna. Choć przy głębszym zastanowieniu jest to oczywiste, że walka o zasoby występuje, ale czy zastanawiałeś się jakie opóźnienia są generowane przy synchronizacji wątku, który wkłada obiekt na kolejkę i kolejnego wątku, który ten obiekt odczytuje? W większości systemów, czas poświęcony na tego typu operacje, nie ma znaczenia, ale jeśli mierzysz wysoko i Twoim celem jest przetwarzanie setek tysięcy zapytań na sekundę, są to sprawy, których nie można zaniedbać.

Trzeba uzmysłowić sobie pewną brzydką cechę szybkich systemów. Kolejka, która wyznacza pewną granicę pomiędzy procesami i służy do przenoszenia danych pomiędzy jednym a drugim, z reguły najczęściej znajduje się w dwóch stanach: albo jest prawie pusta, albo prawie pełna. Powodem oczywiście jest różna szybkość producenta i konsumenta danych używających kolejki. Zmusza to poszczególne wątki do czekania aż zwolni się miejsce na kolejny zestaw danych, przy pełnej kolejce, albo czekanie aż pojawi się nowy zestaw. Dodatkowo kolejka, aby zapewnić funkcjonalność, musi utrzymywać parametry jak wielkość (size), głowę (head) i ogon (tail) w pełnej spójności. To implikuje potrzebę synchronizacji i często kończy się użyciem locków.

Zauważono to również przy tworzeniu disruptora. Wszelkie opóźnienia wynikające z synchronizacji wątków powinny być usunięte. Oczywiście jeśli nie ma danych do konsumpcji, wątek odpowiedzialny za odczyt, musi poczekać aż takowe się pojawią. Niemniej proces odczytu nie powinien co do zasady mieć żadnego wpływu na opóźnienia zapisu i vice versa.

Osiągnięto to, używając bufora cyklicznego (ring buffera), czyli stałej tablicy posiadającej indeks (na ogół) na następny element. Choć faktyczna implementacja w bibliotece jest nieco bardziej skomplikowana, indeks na następny element możemy sobie wyobrazić jak ciągle rosnącą wartość sequence, którą dzielimy modulo przez rozmiar tablicy.

long sequence = sequence + 1;
long nextIndex = sequence % bufferSize;

Cała tablica jest wypełniona wcześniej zaalokowanymi obiektami do transferu danych. Unikamy w ten sposób opóźnień związanych z alokacją podczas procesowania oraz niepotrzebnych konfliktów dostępu. Zarówno producent jak i konsument danych, utrzymuje swój własny indeks, czyli informację o miejscu, gdzie aktualnie znajduje się element zainteresowania.

Naturalnie, patrząc na schemat powyżej, łatwo dostrzec pewien haczyk. Jeśli producent jest znacznie szybszy niż konsument, nie unikniemy sytuacji, w której czekamy, aż wszyscy konsumenci pobiorą dany element. Inaczej to wygląda w odwrotnej sytuacji, mamy sporo kontroli nad tym, jak chcemy oczekiwać na kolejne elementy poprzez implementację interfejsu WaitStrategy, a wybór zależy tylko i wyłącznie od naszych wymagań. Tym bardziej pokazuje to, że znajomość rozwiązywanego problemu, i co za tym idzie systemu, nie jest do przecenienia. A więc:

Blokowanie faktycznie jest źródłem całego zła, podobnie jak śmiecenie pamięci zbędną alokacją obiektów.

Zainteresowanie sprzętem

Tworząc aplikację, najczęściej nie zwracamy tak często uwagi, jak używa ona zasobów sprzętowych. Używając chmury, kontenerów i szeroko pojętej wirtualizacji, ten trend się posuwa nawet dalej. Zupełnie szczerze, właśnie o to w nim chodzi, aby „za bardzo się nie przejmować infrastrukturą”, bo naszym nadrzędnym celem jest rozwiązanie problemu biznesowego. Gdy mówimy jednak o zadaniu, które wprost jest zależne od nadzwyczajnej szybkości przetwarzania, użycie zasobów i wszelkie zagadnienia dotykające interakcji hardwareu z kodem nie może już zostać zignorowane. Ten właśnie aspekt często nosi miano mechanical sympathy. Zasadnie, twórcy disruptora uznali, że jest to dla nich bardzo istotne.

Użycie ring buffera, oprócz oczywistego zysku związanego z brakiem locków i powodowanymi przez nie opóźnieniami, posiada dodatkowy pozytywny wpływ niewyrażony wprost. Wspomniane wcześniej kolejki potrzebują synchronizacji przy utrzymywaniu stanu, w tym poprawy wartości wielkość (size), głowę (head) i ogon (tail) kolejki. Powoduje to, że rozpatrując nawet najprostszy scenariusz, mając jednego producenta i konsumenta, mamy dwa procesy modyfikujące pamięć. Im więcej procesów, tym więcej powyższych modyfikacji. Jest to o tyle istotne, bo ma spory wpływ na szybkość odczytu danych.

Tutaj warto nadmienić, jak procesor pobiera dane z pamięci potrzebne do wykonania danego zadania. Procesor dzieli od głównej pamięci parę poziomów cache, które mają przyspieszyć działanie. W momencie wykonywnia operacji, procesor najpierw przegląda pierwszy poziom cache (L1) w poszukiwaniu danych, później drugi (L2) i na końcu trzeci (L3). Jeśli dane nie są dostępne w cache, ostatnim krokiem jest odwołanie się do głównej pamięci.

Im dalej procesor sięga tym większą pamięć ma do dyspozycji, ale też więcej czasu ta operacja pobierania danych zajmuje. Dodatkowo, dane są pobierane nie pojedyńczo, ale w grupach odpowiadających rozmiarowi linii cache. Mamy tutaj więc pewną prawidłowość, w zależności jak „poprawnie” nasze dane są poukładane w pamięci, i jak niezmienne są, tym więcej czasu procesor spędza na wykonywaniu operacji i tym mniej czasu marnuje na pobieraniu potrzebnych danych z coraz dalszych miejsc. Istotne, dane z cache nadają się do użytku jeśli są spójne. Jeśli nastąpiła modyfikacja w innym miejscu, np. inny wątek działający na kolejnym procesorze dokonał zmiany zmiennej zawierającej się we wczytanej linii cache, dane muszą być przeładowane z głównej pamięci.

Wracając do poprzedniej myśli, mając parę procesów modyfikujących kolejkę, parametry takie jak głowa czy ogon kolejki, mogą się zmieniać niezależnie, a źródło tych zmian może pochodzić z osobnych procesów ulokowanych na różnych procesorach w ramach jednej maszyny. Jeśli dodamy do tego brak gwarancji ulokowania tych parametrów na osobnych liniach cache, łatwo możemy zauważyć, jak dużo pracy mogą sobie nastręczać procesy współdzielące kolejkę, „psując” sobie nawzajem dane zawarte w cache L1, L2 i L3.

Powyższe, stało się kolejnym punktem optymalizacji w disruptorze. Skoro w ramach bufora cyklicznego, proces utrzymuje tylko informację o indeksie, wprost skorelowanym z sekwencją, trzeba zadbać, aby sekwencja jednego procesu, nie była wczytywana w ramach linii cache innego procesu, który może zmodyfikować jakąkolwiek wartość w tej linii. Jeśli więc zobaczysz takie fragmenty kodu jak:

abstract class RingBufferPad
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

to nie będzie to już dla Ciebie tajemnicą, dlaczego tak wydajna i zaawansowana biblioteka w ogóle zawiera takie kawałki kodu. Oczywistym staje się zabieg dopełnienia linii cache. Ten fragment powoduje, że wartość sekwencji będzie jedyną modyfikowaną wartością w ramach danej linii i będzie to przeprowadzane tylko przez jeden proces, do którego ta sekwencja należy. Uchroni to ring buffer i całą bibliotekę, przed problemem opisanym wcześniej, nazywanym false sharing. Ważne, ten zabieg działa przy założenie że linia cache ma 64 bajty (co jest popularnym rozmiarem w architekturach procesorów).

Kolejnym, choć mniej spektakulranym i drobnym zabiegiem jest fakt, ze rozmiar ring buffera musi być potęgą dwójki. Nie ma w tym nic dziwnego, bo system binarny jest oczywistym wyborem dla maszyn, T800 na pewno by się zgodził. Natomiast, narzucając to proste wymaganie, za darmo otrzymujemy operacje jak operatory binarne i przesunięcia bitów, gdy chcemy odszukiwać elementy wewnątrz naszego bufora w bardzo wydajny sposób.

protected final E elementAt(long sequence)
{
    return (E) UNSAFE.getObject(entries, REF_ARRAY_BASE + ((sequence & indexMask) << REF_ELEMENT_SHIFT));
}

Ogólnie rzecz biorąc, zabiegi zastosowane znacznie wykraczają poza znajomość dobrego algorytmu czy też trików w naszym ulubionym języku, ale im bardziej wyśrubowane wymagania stawiamy, tym więcej na znaczeniu zyskują rzeczy, które wcześniej całkowicie pomijaliśmy. Pozwolę sobie to podsumować następująco:

Jeśli chcemy osiągnąc coś niestandardowego, musimy opuścić znajome i oklepane rozwiązywania. Trzeba spojrzeć na zadanie z innej strony i próbować zrozumieć nawet te aspekty problemu, które wykraczają poza naszą początkową domenę.

Słowo na koniec

Szybkość oferowana przez bibliotekę disruptor jest ciężka do pobicia w swojej wydajności. Pochodzi z głębokiego zrozumienia jak działa nie tylko jvm ale i hardware, na którym uruchamiamy nasze aplikacje. Naturalnie, nie trzeba być specjalistą z architektury procesorów i konstrukcji pamięci operacyjnych aby z niej korzystać, ale trzeba być świadomym pewnych kompromisów, jakie jej użycie wymaga. Już kiedyś wspominałem, nie ma darmowych obiadów, więc jeśli zdecydujemy się na zastosowanie disruptora u siebie, będziemy musieli podążać pewną konwencją i strukturą, jak nasz system jest budowany. Będziemy musieli uważać jak go rozwijamy i mierzyć jego osiągi, aby wycofywać się z błędnych decyzji, co na końcu, zaowocuje wyjątkowo wydajnym systemem.

Na koniec tylko wspomnę, opisana wyżej biblioteka to jest tylko narzędzie i jak z każdym narzędziem, dobierajmy je wedle potrzeb i używajmy tak, aby czerpać maksymalne korzyści. Nie patrzmy na wszystko jak na gwoździe, bo chcemy koniecznie użyć ulubionego młotka.