Synchronization Through Memcache

In web and server-side development, a memcache is a remote service that keeps transient data in temporary, in-memory store and allows for fast access. It is usually based on keys which identify values being stored and retrieved. Due to storing technique – RAM rather than actual disks – it offers great speed (often less than few milliseconds per operation) while introducing a possibility for values to be evicted (deleted) if memcache runs out of space. Should that happen, oldest values are usually disposed of first.

This functionality makes memcache a good secondary storage that complements the usual persistent database, increasing the efficiency of the system as a whole. The usual scenario is to poll memcache first, and resort to querying the database only if the result cannot be found in cache. Once the query is made, its results are memcached for some reasonable amount time (usually called TTL: time to live), depending on allowed trade-offs between speed and being up-to-date with our results.

While making applications more responsive is the primary use case for memcache, it turns out that we can also utilize it for something completely different. That’s because memcache implementations offer something more besides the obvious get/set commands. They also have operations which make it possible to use memcache as synchronization facility.

Podstawowa wielowątkowość w Javie

W Javie nietrudno natrafić na metody z klasy Object, bo pojawiają się one w kontekście dowolnego obiektu, do którego się odwołujemy. Wśród tych metod można zauważyć kilka, których przeznaczenie nie jest zrazu oczywiste; są to wait, notify i notifyAll. Lektura dokumentacji może nas pouczyć, że mają one coś wspólnego z wątkami… Ale czemu coś takiego jak wątki ma swoje “wtyki” już na tak niskim poziomie? Ano dlatego, że w Javie wielowątkowość jest pewnego rodzaju młotkiem, którego posiadanie zamienia wiele napotkanych zadań i problemów w gwoździe. Opowiem dzisiaj co nieco o podstawach posługiwania się tym tępym narzędziem :)

Zacznijmy od tego, że kiedy rozdzielamy program na więcej niż jeden wątek, prawie natychmiast pojawia się problem synchronizacji. Może on mieć wiele form, ale zaryzykuję stwierdzenie, że najczęściej występują dwie poniższe:

• ochrona jakiegoś zasobu (w bardzo ogólnym sensie) przez równoczesnym dostępem z więcej niż jednego wątku
• oczekiwanie wątków na jakieś zdarzenia i ich powiadamianie, gdy te zdarzenia zachodzą

Implementacje pierwszego przypadku nazywa się powszechnie sekcjami krytycznymi. W Javie siedzą one tak głęboko, że są częścią samego języka i mają swoje własne słowo kluczowe: synchronized. (Jest to właściwie dokładny odpowiednik lock z C#). Słowem tym możemy oznaczać metody lub bloki kodu, czyniąc je kodem synchonizowanym. Taki kod może być – dla danego obiektu – wykonywany tylko przez jeden wątek naraz. Wszystko więc, do czego się w takim kodzie odwołujemy, jest chronione przed jednoczesnym dostępem wielu wątków – tak jak w przykładzie poniżej:

I tak mniej więcej przedstawiaj się podstawy wielowątkowości w Javie. Bardziej zaawansowane obiekty sychronizacyjne – jak choćby te z pakietu java.util.concurrent wykorzystują te własnie podstawowe mechanizmy zapewniania wyłączności oraz powiadamiania. Jeśli piszemy kod, który korzysta z współbieżności w prosty sposób, możemy wykorzystać je bezpośrednio.

Kod otwarty na zdarzenia

Wydaje mi się, że przynajmniej pod kilkoma względami programowanie przypomina prowadzenie samochodu. Obu tych umiejętności względnie łatwo się nauczyć i niemal niemożliwe jest zapomnieć. Po nabyciu pewnej wprawy mamy też wystarczającą biegłość, by nie musieć koncentrować całej uwagi na którejś z tych czynności. Wyjątkiem są jedynie te miejsca, w których zalecane jest zachowanie szczególnej ostrożności.
Dla mnie (i pewnie nie tylko dla mnie) takimi miejscami w kodzie są styki programu z otoczeniem, przez które musi przebiegać jakaś komunikacja polegająca na wymianie danych i/lub informacji o zdarzeniach. Fragmenty te są ważne i nierzadko problematyczne, gdyż często pociągają za sobą konieczność dopasowania sposobu wykonywania programu do zewnętrznych wymagań. Jak na skrzyżowaniu, trzeba czasem chwilę poczekać i przynajmniej parę razy obejrzeć się dookoła.

W tym kontekście używa się słowa ‘synchronizacja’, jednak kojarzy mi się ono nieodparcie z programowaniem współbieżnym. To trochę złe skojarzenie, bowiem nie trzeba wcale tworzyć kilku wątków czy procesów, by kwestia zaczynała mieć znaczenie. Wystarczą operacje wejścia-wyjścia (zwłaszcza względem mediów wolniejszych niż lokalny system plików) lub obsługa jakiegoś rodzaju zdarzeń zewnętrznych, albo chociażby RPC (Remote Procedure Call – zdalne wywoływanie procedur) – ale oczywiście ta lista nie wyczerpuje wszystkich możliwości. Ogólnie chodzi o wszelkie odstępstwa od możliwości wykonywania programu krok po kroku – a właściwie kroczek za kroczkiem, gdzie każda sekwencja stałej liczby instrukcji zajmuje umowną, niezauważalną chwilę.

Jeśli by się nad tym zastanowić przez moment, to takich sytuacji jest sporo. Ba, właściwie to wspomniane scenariusze sekwencyjne są raczej wyjątkiem, a nie regułą. Dzisiejsze aplikacje działają w wielozadaniowych środowiskach, na ograniczonych pulach zasobów, wymieniają dane przez różne (niekoniecznie szybkie) kanały informacji, i jeszcze dodatkowo są pod ciągłą presją wymagań co do cechy określanej angielskim słówkiem responsiveness – czyli “komunikatywności z użytkownikiem”. Nic dziwnego, że wspomniane przeze mnie wcześniej ‘punkty szczególnej ostrożności’ stają się na tyle istotne, że zazwyczaj to wokół nich buduje się całą architekturę programu.
W jaki sposób są one realizowane? Zależy to od wielu czynników, w tym od rodzaju aplikacji oraz możliwości i struktury systemowego API, które ona wykorzystuje. Tym niemniej można wyróżnić kilka schematów, aplikowalnych w wielu sytuacjach – chociaż nie zawsze z równie dobrym skutkiem. Są nimi:

• Aktywne czekanie (busy waiting, active polling), polegające na ciągłym dopytywaniu się o rezultat operacji czy też informację o tym, czy oczekiwane zdarzenie zaszło. Stosowane w praktyce sprowadza się do pętli podobnej do poniższej:
  1. while (!WaitFinished()) { }

  i jest przestępstwem ściganym z urzędu w każdym rozsądnym zespole projektowym :) Istnieją aczkolwiek okoliczności łagodzące, zezwalające na jego popełnienie pod ściśle określonymi warunkami. Musimy jedynie być pewni, że zużywanie do 100% czasu procesora przez nasz program jest akceptowalne i że między kolejnymi zapytaniami możemy też zrobić coś produktywnego. Tak się składa, że istnieje typ aplikacji, w którym oba te warunki mogą być spełnione: gry. Ich pętla główna to nic innego jak aktywne czekanie na informacje o zdarzeniach z renderowaniem kolejnych klatek w tak zwanym międzyczasie.

• Na wpół aktywne czekanie (soft busy waiting) to złagodzona wersja powyższego. Nie zasypujemy już systemu żądaniami z prędkością światła, a jedynie co jakiś czas. Pomiędzy nimi program może zająć się swoimi sprawami albo po prostu… spać:
  1. while (!WaitFinished()) { Sleep(50); }

  Takie krótkie drzemki zdecydowanie zmniejszają zużycie procesora przez aplikację, ale nie dają jej dużego pola manewru. Ta metoda jest więc stosowalna główne dla usług działających w tle. A raczej byłaby, gdyby nie istniały znacznie lepsze :)

• Przerywalne oczekiwanie (interruptible waiting) to stan zawieszenia w oczekiwaniu na zdarzenie (np. koniec długiej operacji), podczas którego możliwa jest jednak reakcja na pewne szczególne okoliczności. Koncepcja takiego oczekiwania jest zapewne dobrze znana programistom linuksowym, jako że tam niemal każda operacja może zostać przedwcześnie przerwana przyjściem sygnału do procesu. Ów sygnał może być złapany i w konsekwencji obsłużony, lecz nie powinno to pociągać za sobą żadnych skomplikowanych operacji.
  Przerywalne oczekiwanie jest akceptowalnym sposobem działania programów funkcjonujących w tle, na przykład jako usługi systemowe. Niespecjalnie za to nadaje się dla aplikacji z UI – chyba że co jakiś krótki czas pozwolimy na obsłużenie wejścia od użytkownika. Wtedy jednak jest to już raczej wariant soft busy waiting.
• Asynchroniczne wywołanie zwrotne (asynchronous callback) znaczy mniej więcej tyle, co “zrób to i powiedz mi, kiedy skończysz” albo “powiadom mnie, gdy to się zdarzy”. W obu przypadkach musimy dostarczyć mechanizm wywołania zwrotnego (callback), zintegrowany z naszą aplikacją. To dosyć wygodne, jeśli i bez tego działa ona na zasadzie sterowania zdarzeniami (event-driven) i rzeczone wywołanie możemy potraktować jako jeszcze jedną sytuację do obsłużenia. (Dlatego komponent BackgroundWorker z Windows Forms jest tak prosty w użyciu). Gorzej jest wtedy, gdy na potrzeby asynchronicznego callbacku musimy rozbić na kilka części (i stanów) program, który bez tego działałby niemal sekwencyjnie.
  Osobną kwestią jest też sposób realizacji callbacka. W dużej mierze zależy on od możliwości języka. W jednych jest to bardzo wygodne (C#, Python, większość języków skryptowych), w innych nieco mniej (Java), a w jeszcze innych ledwo da się to zrobić (C++, a jakże).

Między powyższymi sposobami możliwe są “konwersje”, oczywiście do pewnego stopnia. Wymagać to może uruchomienia dodatkowego wątku, w którym wykonujemy polling operację asynchroniczną lub wręcz blokującą, i którego stan możemy odpytywać lub otrzymać jako sygnał na obiekcie synchronizacyjnym po wejściu w stan przerywalnego czekania.
Nieczęsto jednak taka zabawa ma uzasadnienie. W najlepszym razie otrzymamy rozwiązanie równoważne, a najgorszym stracimy na wydajności operacji dostosowanej pod konkretny typ powiadamiania. Lepiej jest jednak trzymać się tego, co dana platforma i API nam proponuje.

Synchronizacja wątków w Javie

Deweloperzy programujący wielowątkowo zapewne znają klasyczne typy wykorzystywanych przy okazji obiektów. Są to na przykład semafory, sekcje krytyczne (zwane też semaforami binarnymi) czy zdarzenia (events). Wszystkie one służą oczywiście do synchronizacji wątków tak, aby wykluczyć jednoczesny, wykluczający się dostęp do jednego zasobu.

Tego typu obiekty są wykorzystywane jednak głównie wtedy, kiedy mechanizm wątków jest zrealizowany w sposób specyficzny dla systemu operacyjnego – jak choćby poprzez API z Windows lub bibliotekę pthreads z Linuxa. Jeśli jednak mamy szczęście pracować z językiem, którego wielowątkowość jest częścią, wówczas korzysta się zwykle z nieco innych technik.
Taka sytuacja jest na przykład w Javie. Tam każdy obiekt (czyli instancja klasy dziedziczącej z java.lang.Object) może być użyty jako obiekt synchronizujący. Z grubsza działa to w ten sposób, że gdy jeden z wątków zadeklaruje wykorzystanie danego obiektu – przy pomocy słowa kluczowego synchronized – pozostałe nie mogą zrobić tego samego. Taka synchronizacja może odbywać się na wiele (składniowych) sposobów, jak choćby zadeklarowanie całej metody jak synchronizowanej:

W tym prościutkim przykładzie mamy zagwarantowane, że żaden postronny wątek nie wtrąci się w operację inkrementacji ze zwróceniem wartości (która nie jest atomowa) i stan licznika będzie zawsze poprawny.
Tak więc mamy semafory tudzież sekcje krytyczne. A co np. ze zdarzeniami (sygnałami)? Otóż każdy obiekt posiada metody wait i notify, umożliwiające czekanie na powiadomienie z innego wątku i oczywiście wysłanie takiego powiadomienia. Całkiem skuteczne i dosyć proste; naturalnie na tyle, na ile proste może być programowanie wielowątkowe :)

Ale czy oryginalne? Otóż dziwnym trafem na platformie .NET cała sprawa wygląda niemal dokładnie tak samo :) Odwzorowania przytoczonych elementów Javy w C# to odpowiednio: lock (z dokładnością do kilku niuansów), Monitor.Wait i Monitor.Pulse. Sam sposób tworzenia wątków jest zresztą też bardzo bardzo podobny.
Wszelka zbieżność przypadkowa? Zdecydowanie nie. Lecz dobre rozwiązania warto jest przecież rozpowszechniać :]