Double-checked locking with Singleton pattern in Java

I just faced problem with synchronization many threads starting at the same time (with microseconds difference) and creating single object instance of connection to the database using a Singleton Pattern in Java. As a result I had many connections except one. The sent queries counter has been set to smaller value as excepted in simulations.

I have just Google’d the IBM article by Peter Haggar, Senior Software Engineer “Double-checked locking and the Singleton pattern”.

Problem overview

Creating an singleton in Java is simple to implement. There are two common ways to create singleton:

  1. Lazy loaded with create an private static field _instance filled by null (by default Java object initialization). The instance is created, when the static method getInstance() is called.
  2. Create an class instance in advance, just before class is loaded to memory by declaring a value of priate static field _instance by calling the private constructor new SingletonClass();

1st implementation with lazy initialization

package pl.athlan.examples.singleton;
 
public class Singleton {
	private static Singleton _instance; // null by default
 
	private Singleton() {
	}
 
	public static Singleton getInstance() {
		if(_instance == null) {
			_instance = new Singleton();
		}
 
		return _instance;
	}
}

2nd implementation with eager initialization

package pl.athlan.examples.singleton;
 
public class Singleton {
	private static Singleton _instance = new Singleton(); // object is created just after class is loaded into memory
 
	private Singleton() {
	}
 
	public static Singleton getInstance() {
		return _instance;
	}
}

Motivation.

Imagine two separated threads with is delegated to call getInstance() method at the same time.

Thread #1 Thread #2 value of _instance
Singleton.getInstance() null
Singleton.getInstance() null
if(_instance == null) null
if(_instance == null) null
_instance = new Singleton() [object #1]
_instance = new Singleton() [object #2]

As a result, two object has been created, because thread #2 hasn’t noticed the object creation.

If your object stores common data like a (in my case) database queries counter or the creation of the object is time-expensive when the system just hang out for many threads – this situation have not to occur.

Sloving the problem.

The problem slove is to synchronize the threads while accessing getInstace method. You can simply write:

public static synchronized Singleton getInstance()

but this solution produces an huge overhead to synchronize all threads calling this method. The better solution is to synchronize the fragment of code which checks an existance and creates the object in fact, except of returing if it already exists.

Finally solution:

package pl.athlan.examples.singleton;
 
public class Singleton {
	private volatile static Singleton _instance;
 
	private Singleton() {
	}
 
	public static Singleton getInstance() {
		if(_instance == null) {
 
			// causes that this block will be processed in sequence in parallel computing mode
			synchronized(Singleton.class) {
 
				// if previous sequence created the instance, just omit object creation
				if(_instance == null) {
					_instance = new Singleton();
				}
			}
		}
 
		return _instance;
	}
}

The volatile keyword assigned to _instance field provides the synchronization.

If there is no instance of the object, the synchronized block will begin. It means that all processes are queued to access that block. After access just ensure one more time, if the single object is not exists in fact, because the process doesn’t know what happened before it has rached the queue. If any process before queueing has created the object, just ommit the creation.

Hope it helped!

NOTE: Note that implementing Singleton by an ENUM is thread-safe and reflection-safe.

 

Parallel Matrix Multiplication in ADA95

I want to share my elaboration about Parallel Matrix Multiplication I have writed (as extra task) by the way Parallel Computations which is one of my subject in Silesian University of Technology in the Computer Science course I attend. The elaboration have been written of course in Polish.

I have sloved this problem very simply in ADA95 programming language, which gives an opportunity to write parallel programs very easly in Pascal-like syntax.

My solution of this problem divides an elementary operations between 1 to N provided processors, distributed with shared memory CRCW PRAM model (Parallel Concurrent Read and Concurrent Write). In particular, you can fire up computing in only one processor. Elaborate discuss about problems with value of memory cells working as an accumulator in adding (+) process. It’s overall only.

Finally, I have compiled the code under GNAT 2011 compiler in GPS 2011 IDE (GNAT Developer Studio). For people interested in ADA95 programming and Parallel Computations I recommend some polish books avaiable for example in Silesian Libraries:

  • Porębski, W. (2003). ADA95 Wprowadzenie do Programowania. Michałowice: Komputerowa Oficyna Wydawnicza “HELP”, Piotr Gomoliński.
  • Czech, Z. (2010). Wprowadzenie do obliczeń równoległych. Warszawa: Wydawnictwo Naukowe PWN.
  • Ben-Ari, M. (2009). Podstawy Programowania współbieżnego i rozproszonego (strony 99-133). Warszawa: WNT.

Xin Wang reveals another ways to slove this problem in Scalable Parallel Matrix Multiplication Algorithms with
Application to a Maximum Entropy Problem
publication, but it is only math theory, without implementation.

You can easly write parallel prorgams using MPI library for C++ or Parallel library Java. In general, there are many ways to implement algorythms, but the most important in Parallel Computations is not implementations, but problem decomposition and hardware structure of computing processors which exchanges information with each other.

Have fun!

 

 

PHP cache, semafory

Praktyka cache‘owania danych jest powszechna wśród programistów aplikacji webowych ze względu na optymalizację dostępu do danych bezpośrednio ze źródła ich pochodzenia, a w szczególności:

  • trudność dostępu (np. wykonanie skomplikowanych połączeń),
  • ograniczenia dostępu (np. limit odpytywania),
  • długi czas oczekiwania na dane; powodów jest wiele.

O ile tematyką stworzenia samego mechanizmu cache zajęli się m.in. Nospor, możecie podejrzeć jak to wygląda w Zend_Cache, Symfony, czy Kohana; tak ja chciałbym zwrócić uwagę na jeszcze jedną rzecz.

Zazwyczaj schemat kodu wygląda mniej więcej tak:

< ?php
$oCache = new Cache(); // tworzony jest jakis obiekt cache
 
if($oCache->expired(3600) || !is_array($aData = $oCache->load())) // sprawdzamy, czy jest cache i nie wygasł
{
  $aData = $oModel->GetSomething(); // zbieramy dane z bazy danych
  $oCache->save($aData);
}
 
// $aData przechowuje nasze dane do użytku
?>

Symulacja, parę linijek kodu, a ile nieszczęść.

Wszystko działa pięknie, dopóki nie spotkamy się z sytuacją, gdy setki osób (procesów) jednocześnie zechcą zbierać takie dane z bazy danych. Przeprowadźmy zatem krótką dywagację. Załóżmy, że użytkownik #1 wchodzi na stronę, stwierdza, że nie ma cache, lub jest nieświeży, wówczas przechodzi do połączenia się z bazą danych i zaczyna zbierać dane. W tym samym czasie, zanim użytkownikowi #1 zostaną zwrócone dane wchodzi użytkownik #2, który stwierdza, że nie ma cache, bo użytkownik #1 jeszcze nie zebrał danych, postanawia połączyć się z bazą i zrobić to samo, co użytkownik #1, powtarzając niepotrzebnie czynność i dodatkowo obciążając bazę. Można by iść dalej i wprowadzić n użytkowników, którzy powtarzają czynność, dopóki dane nie pojawią się w cache i kolejni użytkownicy będą z niego korzystać. Co się stanie natomiast, gdy kolejka tak narośnie, że użytkownikowi #1 zabraknie zasobów systemowych, aby ukończyć proces zbierania danych, co spowoduje, że pozostałym też? Kolejka będzie wydłużała się w nieskończoność, póki system operacyjny nie podejmie żadnych działań (np. odłączy bazę danych, lub po prostu wyłączy serwer, np. w IIS7 wyłączy cały application pool). Aby doszło do tej kolizji nie jest potrzebne wcale natężenie użytkowników, serwer może akurat np. zajmować się wysyłką maili lub nieoptymalnie zrobionym procesem, który zajmuje zasoby, a w tym czasie wejdzie tylko pięciu użytkowników.

Parę linijek kodu, a ile nieszczęść.

Pojęcie semafora.

Semafor w informatyce – jest chronioną zmienną lub abstrakcyjnym typem danych, który stanowi klasyczną metodę kontroli dostępu przez wiele procesów do wspólnego zasobu w środowisku programowania równoległego.

Więcej na temat semaforów na Wikipedii, bądź w Podstawy informatyki / Stefan Węgrzyn. – Warszawa : Państwowe Wydawnictwo Naukowe, 1982.

Podejście do problemu.

< ?php
$oCache = new Cache();
 
if($oCache->expired(3600) || !is_array($aData = $oCache->load()))
{
  $oCache->savePrepare(); // stawiamy semafor
 
  $aData = $oModel->GetSomething();
  $oCache->save($aData); // metoda save() może (nie musi) od razu zwolnić semafor, gdy próba zapisu się zakończy
  // jeżeli metoda save() nie zwalnia zasobu, możemy np. użyć:
  // $oCache->saveFinalize();
}
 
// $aData przechowuje nasze dane do użytku
?>

Rozwiązaniem jest zastosowanie semafora blokującego dostęp do zasobu (w tym przypadku abstrakcyjnie “cache”, mniej abstrakcyjnie może być to plik na dysku, przestrzeń w pamięci operacyjnej, rekord w bazie danych, cokolwiek, co cache przerzymuje). Dla wartości semafora = 1 zasób jest wolny (nieużywany, jest 1 cache), gdy jest mniejszy/równy 0 zasób jest zajęty, ktoś z niego “korzysta”. Zajętość zasobu powinna być sprawdzana przy próbie odczytu. Dopóki zasób nie zostanie zwolniony, nie będzie można określić, czy są dane w cache. Jeżeli nie można określić, czy dane są w cache, należy zaczekać na zwolnienie zasobu.

Teraz nasze rozwiązanie nie dopuści do przytoczonej w powyższym przykładzie sytuacji. Zanim cache nie zostanie odblokowany po próbie zapisu, nie uzyskamy odczytu, czekając na niego i nie przechodząc w skrypcie nigdzie dalej.

Gdy save() się nie powiedzie? Można zastosować timeouty odczytu na load(). Wówczas złapalibyśmy wyjątek i przeszli dalej do realizacji zapisu, tak, jakby semafora nie było.

Implementacja.

Do swoich kodów podchodzę jak najbardziej abstrakcyjnie (tutaj idealnie nada się wzorzec fabryki), zatem stworzyłem klasę Cache, która obsługuje ‘silniki’ implementujące interfejs Cache_Engine. Jednym z nich jest silnik Cache_Engine_File, który wykorzystuje pliki na dysku do składowania cache.

Najprostszym semaforem dla plików jest funkcja flock() (gotowe, sprawdzone rozwiązanie, w dodatku na poziomie systemu plików, nic tylko implementować). Sprawa wygląda bardzo prosto, dopóki nie zwolnimy flagi LOCK_EX po jej założeniu, ludzie nie będą czytali z pliku, czekając na zwolnienie dostępu. Ktoś powie: truizm, blokować pliki powinno się przed wykonywaniem na nich operacji. Tak. Ale grunt, w którym miejscu to zablokowanie nastąpi. Wykorzystujemy blokowanie do wyższego celu.

Wg. dokumentacji nie można polegać na flock() w przypadku Windows98 oraz systemów FAT32. Zbyt dużym poziomem abstrakcji jest dla mnie stawianie serwisu na pamięci flash lub Win98, ale faktycznie, najprostsza pamięć flash z systemem FAT32 może się czasem zdarzyć w serwerowniach i nie jest to wcale taki głupi pomysł. Co wtedy? Jako semafor możemy stworzyć plik z suffiksem .lock obok tworzonego pliku cache. Gdy plik istnieje oznacza to, że cache jest zablokowany, jeżeli nie – jest wolny. Czekamy tak długo, aż zostanie usunięty plik .lock.

Przykładowy kod źródłowy.

Przykładowy kod źródłowy obsługuje Cache_Engine_File oraz Cache_Engine_Filelock, gdzie w drugim przypadku można klasy użyć spokojnie na partycjach FAT32. Kod jest przykładowy, dlatego nie obsługuje m.in. zagnieżdżania plików w katalogach, usuwanie cache’u itd, zaimplementowałem tylko zapis i odczyt.

Klasy zostały napisane tak, aby zgłaszane przez nie błędy były zgodnie z ideologią hierarchiczną Exceptions w PHP, przy okazji zapraszam do lektury wpisu “Wyjątki w PHP” autorstwa Tomasza Jędrzejewskiego (Zyxits).

Przykładowe czekanie na zwolnienie pliku .lock:

< ?php
 
protected function _waitUnlock($iWaitTimeout)
{
  if($iWaitTimeout)
  {
    try
    {
      // quick first check
      if(is_file($this->_path(false, 'lock')))
      {
        // wait for unlock file
        $iWaitTimeout /= 1000000;
        $iLockTime = microtime(true);
        $bLockWait = true;
 
        // wait for the file
        try
        {
          while(is_file($this->_path(false, 'lock')))
          {
            $iLockWaitDelta = microtime(true) - $iLockTime;
 
            if($iLockWaitDelta > $iWaitTimeout && $iWaitTimeout !== true)
              { $bLockWait = false; break; }
 
            usleep(rand(1, 999));
          }
        }
        // cache lock path does not exists
        catch(Cache_Exception_Runtime $oE) {}
 
        if(!$bLockWait)
          throw new Cache_Exception_Runtime('Unable to access cache, it is totally locked, after "' . $iWaitTimeout . '" s.');
      }
    }
    // cache lock path does not exists
    catch(Cache_Exception_Runtime $oE) {}
  }
  else
  {
    try
    {
      if(is_file($this->_path(false, 'lock')))
        throw new Cache_Exception_Runtime('Unable to access cache, it is currently locked, after "' . $iWaitTimeout . '" s.');
    }
    // cache path does not exists
    catch(Cache_Exception_Runtime $oE) {}
  }
 
  return true;
}
 
?>
 

Indeksowanie baz danych, funkcje mieszające

Występowanie złożonych baz danych jest coraz bardziej popularne, a komercyjne rozwiązania praktykują składowanie informacji nie tylko na pojedynczych bazach, przestrzeniach, dyskach, czy nawet serwerach. Szybki dostęp do danych to podstawa, dlatego pochylimy się nad czysto teoretycznym problemem dostępu do informacji, które wprawdzie są rozwiązane i zaszyte w mechanizmach poruszania się po większości baz, natomiast ich znajomość pozwoli dodatkowo zoptymalizować struktury, które projektujemy. Z góry podkreślam, że artykuł jest bynajmniej wyczerpujący, specjalistycznej i bardziej szczegółowo zarysowanej teorii baz danych należy szukać w publikacjach i tu zachęcam do odwiedzenia politechnicznych bibliotek.

Baza danych jako zbiór informacji powinna oferować trzy podstawowe operacje:

  • Szukanie jako dostęp do pojedynczego, unikatowego „obiektu” (zazwyczaj rekordu) w bazie danych.
  • Wyszukiwanie jako dostęp do elementów spełniających dane kryteria.
  • Modyfikacja danych.

Pojęcie klucza

Kluczem w bazie danych jest atrybut każdego elementu/rekordu jakiejś klasy (np. pojedynczej tabli danych), który pomoże go zidentyfikować przy szukaniu lub wyszukiwaniu w sposób jednoznaczny (wtedy mówi się o kluczu podstawowym Primary Key) lub niejednoznaczny (wtedy mówi się o indeksie Index). Za pomocą klucza jesteśmy w stanie dostać się do rekordu przeszukując tylko strukturę indeksów, zamiast samą bazę.

Skrócenie drogi dostępu

Przy szukaniu konkretnego elementu, którego unikalny atrybut jest z góry znany używamy właśnie kluczy podstawowych. Jest to gigantyczne przyspieszenie procesu wyszukania elementu. Jak wiemy, niektóre klucze zachowują pewną prawidłowość, na przykład stale rosną. Najprostszym przykładem jest identyfikator rekordu, którego wartość zazwyczaj się inkrementuje. Klucze to nic innego jak para informacji: wartość klucza oraz adres komórki pamięci, do której klucz należy.

Wykorzystanie klucza podstawowego to wskazanie miejsca ulokowania rekordu w dowolnej pamięci (na przykład adresu pamięci, adresu na dysku, offset w pliku, itd.)

Uporządkowany zbiór kluczy podstawowych

Co nam daje uporządkowany zbiór kluczy? Żeby dowiedzieć się, gdzie w pamięci jest ulokowany nasz rekord, najpierw trzeba dostać się do wartości klucza. W przypadku uporządkowanego zbioru danych wartości kluczy możemy w łatwy sposób go odnaleźć, na przykład metodą połowienia zbioru lub dostępu do wcześniej ułożonego drzewa. Najoptymalniejsze do odszukiwania jest drzewo ważone, ponieważ w przypadku nieważonego przy stale wzrastającej wartości klucza przy prawidłowości, że prawe gałęzie drzewa mają wartości większe, drzewo rosłoby tylko w jedną stronę, a w rezultacie otrzymalibyśmy listę, w której odszukiwanie nie jest optymalnym rozwiązaniem. Ważenie drzewa nie jest jednak rozsądnym rozwiązaniem w bazach danych, w których jest więcej żądań (a właściwie czasu propagacji) do zapisu danych, niż odczytu.

Suma sumarum, w zależności od typu bazy (relacyjna, obiektowej, strumieniowej, itd.) oraz jej złożoności, należy wybrać odpowiedni mechanizm układania indeksów.

Funkcja mieszająca

Rodzi się pytanie. Gdy mamy taką strukturę składowania indeksów niejednoznacznych, tj. kilka rekordów może mieć dokładnie taką samą wartość klucza. Prostym przykładem jest indeksowanie dłuższych ciągów znaków, do których chcemy mieć natychmiastowy dostęp bez wyszukiwania ich w bazie danych w sposób bezpośredni. Do identyfikacji takich struktur służą funkcje mieszające. Przykład. Wyobraźmy sobie, że podczas zapisu danych podając dane jako argument funkcji mieszającej, zamieniamy każdy znak ciągu znaków na odpowiadający mu kod ASCII, następnie sumujemy liczby i dzielimy modulo 90, nasz wynik to wartość indeksu. Tę samą operację wykonujemy dla kryterium późniejszego wyszukiwania podając go jako argument funkcji mieszającej. Wystarczy porównać nasze kryterium z kluczami. Mamy 90 możliwości otrzymanych wyników.

Działanie funkcji mieszającej:

Im większe modulo, tym bardziej rozległy indeks i bardziej unikatowy indeks. Niestety, pod jednym kluczem może znajdować się wiele rekordów, przykładowo: ABC, CAB, AAD, AE, F, itd… wówczas występuje tzw. kolizja. Podstawową wadą funkcji mieszającej może być złożoność obliczeniowa dla zwracanej wartości. Ponadto obecne systemy baz danych zapewniają ciągłość z góry zadeklarowanej pamięci, zatem przeszukiwanie takich komórek może być znacznie szybsze, od przeszukiwania kluczy. Funkcja mieszająca plus indeksowanie adresów jest zdecydowanie dobrym rozwiązaniem, gdy przeszukiwanie indeksów jest korzystniejsze pod względem czasu dostępu do informacji (np. czas propagacji dysku, odszukanie fragmentu pliku, etc.).

Występowanie kolizji

Metod obsługi kolizji jest bardzo wiele. Podstawową jest stworzenie listy elementów, które są przypisane do danego klucza. Może ich być wiele, natomiast to i tak bardzo dobra optymalizacja przeszukiwania bazy danych.

Częstotliwość występowania kolizji w grubym przybliżeniu obrazuje wykres. Zauważmy, że jeżeli wyczerpiemy ~60% możliwości wystąpienia tych samych kluczy, kolizyjność wzrasta wykładniczo, a używanie funkcji mieszących przy wstawianiu rekordu bazy danych staje się nieoptymalne, w zależności od implementacji korekcji kolizji (powtórzenia rozwiązania kolizji). Przy dołączaniu elementu do listy jednokierunkowej (wcześniejszy obraz) nie stanowi to jednak większego problemu. Gdy < 60% możliwości kluczy jest niewykorzystanych, występowanie kolizji jest znikome.

Idealna funkcja mieszająca

Mówiąc o idealnej funkcji mieszającej mamy na myśli skonstruowanie takiej funkcji, która przyporządkuje mniej więcej po tej samej liczbie swoich zwracanych wartości, tj. dla naszego przykładu modulo 90, każdy klucz będzie miał porównywalną liczbę rekordów przypisanych do danego indeksu. Intuicyjnie: można to wykonać tylko wtedy, kiedy z góry znamy dziedzinę tej funkcji bądź w przybliżeniu spodziewamy się znanych danych wejściowych. Budowanie idealnych funkcji mieszających jest skomplikowaną operacją matematyczną. Jednym ze sposobów do naszego przykładu, przy znanej dziedzinie funkcji mieszającej jest przypisywanie kolejnym literom wag, które po zsumowaniu i podzieleniu przez modulo, jest wygenerowanie takiej kombinacji wag, żeby zwracane wartości były równie często obliczane dla całej dziedziny funkcji (każda liczba modulo jest wykorzystywana po mniej więcej N razy).

Zakończenie

Temat teoretycznych rozważań budowy baz danych na pewno będę kontynuował. Tak, jak zaznaczyłem we stępie, artykuł bynajmniej wyczerpuje tematykę, a zainteresowanych zapraszam do przekroczenia progów politechnicznych bibliotek.