Publikacje
Spring Security return URL after login
There is a good convenience to user’s usability, allowing to return to requested, unreacheable resource (before login), when the authenticaton has been processed properly.
Spring Security allows to define return URL after login by using SimpleUrlAuthenticationSuccessHandler
. To configure this feature, you need to define the bean in security context:
<beans:bean id="simpleUrlAuthenticationSuccessHandler" class="org.springframework.security.web.authentication.SimpleUrlAuthenticationSuccessHandler">
<beans:property name="defaultTargetUrl" value="/account"/>
<beans:property name="targetUrlParameter" value="spring-security-redirect"/>
</beans:bean>
<http ...>
<form-login ... authentication-success-handler-ref="simpleUrlAuthenticationSuccessHandler" />
</http>
Now, if user log in successfully, then will be redirected to the URL passed into spring-security-redirect
login form parameter (e.x. in hidden field).
NOTE: if you are using own form template, don’t forget about generate the hidden field, for e.x. get r attribute from URL:
<input type="hidden" name="spring-security-redirect" value="<c:out value="${param.r}" />">
NOTE2: Use c:out value="${param.r}"
instead of simple ${param.r}
, because c:out
prevent to inject executable code [read more].
The tag can automatically escape XML tags so they aren’t evaluated as actual tags.
How to redirect user when it is not signed-in?
The example above provides us the way of redirecting user, when access the login form. We have passed the parameter r to the form, but it is still not provided to the login form page in query string.
Even user access the protected
page, the ExceptionTranslationFilter
is executed. There are two reasons, when we looking for resolve this problem:
- When user is not logged in, so don’t have any roles, so don’t have permission to show a resource. Then
AuthenticationEntryPoint
should be executed.UX: User should be redirected to the login form to allow obtain the credentials. - The second, when user is logged in and don’t have role (credential) that allow to access the protected resource. Then
AccessDeniedHandler
should is executed.UX: The403
(Access Denied) page should be displayed. In nice form, obviously.
Now we will consider the first case, when user is trying to access protected resource, will be redirected to the login page, and then, should be redirected back to the resource to consider second case.
Define custom AuthenticationEntryPoint
implementation to return user to the login page, with defined parameter r
filled as current page:
@Component(value = "customAuthenticationEntryPoint")
public class CustomAuthenticationEntryPoint implements AuthenticationEntryPoint {
private String loginPageUrl;
private boolean returnParameterEnabled;
private String returnParameterName;
@Override
public void commence(HttpServletRequest request, HttpServletResponse response,
AuthenticationException reason) throws IOException, ServletException {
if(null == loginPageUrl || "".equals(loginPageUrl))
throw new RuntimeException("loginPageUrl has not been defined");
String redirectUrl = loginPageUrl;
if(isReturnParameterEnabled()) {
String redirectUrlReturnParameterName = getReturnParameterName();
if(null == redirectUrlReturnParameterName || "".equals(redirectUrlReturnParameterName))
throw new RuntimeException("redirectUrlReturnParameterName has not been defined");
redirectUrl += "?" + redirectUrlReturnParameterName + "=" + request.getServletPath();
}
RedirectStrategy redirectStrategy = new DefaultRedirectStrategy();
redirectStrategy.sendRedirect(request, response, redirectUrl);
return;
}
public String getLoginPageUrl() {
return loginPageUrl;
}
public void setLoginPageUrl(String loginPageUrl) {
this.loginPageUrl = loginPageUrl;
}
public boolean isReturnParameterEnabled() {
return returnParameterEnabled;
}
public void setReturnParameterEnabled(boolean returnParameterEnabled) {
this.returnParameterEnabled = returnParameterEnabled;
}
public String getReturnParameterName() {
return returnParameterName;
}
public void setReturnParameterName(String returnParameterName) {
this.returnParameterName = returnParameterName;
}
}
And configure this bean with tag:
<http ... entry-point-ref="customAuthenticationEntryPoint">
<form-login login-page="/login" authentication-failure-url="/login?authfailed=1" authentication-success-handler-ref="simpleUrlAuthenticationSuccessHandler" />
</http>
<beans:bean id="customAuthenticationEntryPoint" class="pl.athlan.util.CustomAuthenticationEntryPoint">
<beans:property name="loginPageUrl" value="/login" />
<beans:property name="returnParameterEnabled" value="true" />
<beans:property name="returnParameterName" value="r" />
</beans:bean>
<beans:bean id="simpleUrlAuthenticationSuccessHandler" class="org.springframework.security.web.authentication.SimpleUrlAuthenticationSuccessHandler">
<beans:property name="defaultTargetUrl" value="/account"/>
<beans:property name="targetUrlParameter" value="spring-security-redirect"/>
</beans:bean>
That’s all. Hope will help.
TIP: to save your time, don’t try to fight with configuration of ExceptionTranslationFilter
. I have tried to override org.springframework.security.web.access.ExceptionTranslationFilter, without effects:
<beans:bean id="exceptionTranslationFilter" class="org.springframework.security.web.access.ExceptionTranslationFilter">
<beans:property name="authenticationEntryPoint" ref="customAuthenticationEntryPoint"/>
<beans:property name="accessDeniedHandler" ref="accessDeniedHandler"/>
</beans:bean>
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:
- Lazy loaded with create an
private static
field_instance
filled bynull
(by default Java object initialization). The instance is created, when thestatic
methodgetInstance()
is called. - Create an class instance in advance, just before class is loaded to memory by declaring a value of
priate static
field_instance
by calling theprivate
constructornew 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.
- Algorytm skalowalnego zrównoleglonego mnożenia macierzy (PDF, ~0.75 MB)
- MatrixParallelMultiplication.adb (ADA95 implementation)
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).
- Klasa Cache, Cache_Exception, abstrakcja Cache_Engine
- Klasa Cache_Engine_File, która bazuje na plikach
- Klasa Cache_Engine_Filelock, która bazuje na plikach + tworzy pliki .lock
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.
Optymalizacja zapytań MySQL dla koniunkcji wielu danych
Nie raz, nie dwa mieliśmy sytuację, która wymagała od nas koniunkcji warunków większej ilości danych lub dane te były tekstowe, ale niedługie. Niby nic, klucze załatwiają sprawę, ale sięgając do kodu gry bukmacherskiej, musiałem ją nieco zoptymalizować pod względem częstego wyciągania danych. Baza rozrosła się dość szybko, dlatego niezbędna była lekka modyfikacja jej struktury.
Moim zadaniem było bardzo częste wyciągnięcie ID meczu, który musiał na raz (AND) być zgodny z żądaną datą, nazwą drużyny pierwszej oraz drugiej. Informacji do warunków dostarczał system. Oprócz daty, są to dane tekstowe, więc połączyłem je ze sobą CONCAT i stworzyłem z nich sumę md5. Indeks, po którym baza szukała, był już krótszy od warunków, bo zawierał zawsze 32 znaki. Pierwszym warunkiem koniunkcji zawsze była suma md5 wymienionych wcześniej pól rekordu, nazwałem to suma kontrolna rekordu, potem faktyczna wartość pól, aby w razie zdublowania sumy kontrolnej (czego się nie spodziewamy, bo zakres wariacji jest ogromny, ale dla idei) wybrać prawidłowy rekord. Do tej pory wystarczało…
Gdy baza rozrasta się, problemem staje się wyszukiwanie. O ile suma kontrolna to już krok w stronę optymalizacji, dla >100k rekordów, baza danych potrzebowała co najmniej 0.05 sekundy na zwrócenie wyniku. Postanowiłem dodać odcisk palca sumy kontrolnej. Najlepszym rozwiązaniem okazało się dodanie jednego bajtu, który zrobił magię w bazie danych. Jedno pole TINYINT – 8 bitów, zakres 0-255 bez znaku. Założenia odcisku palca:
- jest wartością liczbową oraz zajmuje tylko jeden bajt, aby oszczędzić miejsca w rekordach oraz indeksach bazy danych,
- nie musi być uniwersalny (unikalny), a jedynie grupować odciski palców w mniejsze, a liczniejsze zbiory.
Rozwiązanie, które zastosowałem przy generowanu odcisku palca sumy kontrolnej, również nie jest skomplikowane:
- Odcisk palca to suma kolejnych znaków sumy kontrolnej rekordu, gdzie 0 – 9 zachowują swoje wartości, a litery [a-f] przyjmują kolejno [10-15], dokładnie jak w przeliczaniu pojedynczych wyrazów systemu liczbowego o podstawie 16 (HEX) na dziesiętny.
- Skoro jest to suma, to wartość minimalna jest dla samych zer, zatem MIN = 0.
- Wartość maksymalną można stworzyć podając same maksymalne wartości F, zatem MAX = 480.
- 480 mieści się na 9 bitach (min. 2 bajty, zakres 0-65535 bez znaku, tracimy 65055 wartości), dzieląc liczbę przez 2 tracimy unikalność odcisku dwukrotnie, ale zmieścimy się na ośmiu bitach, czyli jednym bajcie – możemy użyć typu TINYINT (zakres 0-255 bez znaku, nasza to 0-240), zatem tracimy tylko 15 niewykorzystanych wartości.
Przeprowadzamy testy naszego rozwiązania.
Stwórzmy przykładową tabelę danych test_md5_index, która będzie przechowywała wartości tekstowe w polach data_content, data_content2, data_content3. Tabela może zawierać pole dodatkowe, ale te trzy będziemy wykorzystywać w naszym wyszukiwaniu. Ważnym jest to, że warunkiem jest koniunkcja (AND), dlatego możemy stworzyć sumę (analogicznie do sumy logicznej) md5 jako odcisk palca tych pól, który zapiszemy w data_sum varchar(32). Dodatkowo stworzymy odcisk palca odcisku palca – jednobajtowe pole data_sum_index TINYINT.
Od razu zakładamy klucz podstawowy na data_id oraz klucz dla zapytania, który będzie go wykorzystywał, czyli szukanie wspólnie po data_sum_index oraz data_sum.
CREATE TABLE test_md5_index (
data_id int(11) unsigned NOT NULL AUTO_INCREMENT,
data_sum_index tinyint(1) unsigned NOT NULL,
data_sum varchar(32) NOT NULL,
data_contents text NOT NULL,
data_contents2 text NOT NULL,
data_contents3 text NOT NULL,
PRIMARY KEY (data_id),
KEY data_index (data_sum_index, data_sum)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=1;
Pora stworzyć funkcję, która przeliczy nam nowy, krótszy odcisk palca na podstawie poprzedniego:
CREATE FUNCTION TestIndexChecksum(sSum VARCHAR(32)) RETURNS TINYINT
BEGIN
DECLARE sSumPart VARCHAR(1);
DECLARE iSumPart TINYINT;
DECLARE iSum SMALLINT DEFAULT 0;
DECLARE i INT;
IF (SELECT sSum NOT REGEXP '^([a-z0-9]){32}$') THEN RETURN 0; END IF;
SET i = 1;
WHILE i <= LENGTH(sSum) DO
SET sSumPart = SUBSTR(sSum, i, 1);
SET iSumPart = (SELECT (CASE WHEN sSumPart = 'a' THEN 10 WHEN sSumPart = 'b' THEN 11 WHEN sSumPart = 'c' THEN 12 WHEN sSumPart = 'd' THEN 13 WHEN sSumPart = 'e' THEN 14 WHEN sSumPart = 'f' THEN 15 ELSE 0 END));
IF iSumPart = 0 THEN
SET iSumPart = sSumPart;
END IF;
SET iSum = iSum + iSumPart;
SET i = i + 1;
END WHILE;
RETURN iSum / 2;
END;
Aby przeprowadzać testy, stwórzmy sobie procedurę, która wstawi nam N losowo, jakkolwiek wypełnionych rekordów do bazy danych:
CREATE PROCEDURE TestIndexesPrepareTest(IN i INT)
BEGIN
TRUNCATE TABLE test_md5_index;
WHILE i > 0 DO
INSERT INTO test_md5_index SET
data_contents = (SELECT REPLACE(CONCAT(RAND() * 32), ".", "")),
data_contents2 = (SELECT REPLACE(CONCAT(RAND() * 32), ".", "")),
data_contents3 = (SELECT REPLACE(CONCAT(RAND() * 32), ".", "")),
data_sum = CONCAT(data_contents, data_contents2, data_contents3),
data_sum_index = TestIndexChecksum(data_sum);
SET i = i - 1;
END WHILE;
END;
Po wykonaniu CALL TestIndexesPrepareTest(100000)
mamy przygotowane małe środowisko testowe.
Przygotujmy kilka zapytań do bazy danych, wybieramy losowy rekord, na którym będziemy testowali wyniki. Wykonujemy zapytanie z ręcznie wpisaną wartością warunku wybranego rekordu, sprawdźmy, jak szybko zostanie odnaleziony:
SELECT * FROM test_md5_index WHERE data_sum = "24045771412594250684228176888212";
Average: ~0.0506 sec
SELECT * FROM test_md5_index WHERE data_sum_index = 68 AND data_sum = "24045771412594250684228176888212";
Average: ~0.0004 sec (UWAGA! Specjalnie w warunku nie użyłem zwróconej warości funkcji, tylko dałem ją na sztywno, ręcznie wpisaną – funkcja by była wykonywana dla każdego porównania rekordu z osobna!).
Nasze zapytanie działa znacznie szybciej (~120 razy dla 100k rekordów) kosztem niewielkiej pamięci – po 1 bajcie do rekordu oraz po 1 bajcie do jego indeksu.
Zapewne istnieją szybkie silniki indeksowania danych, natomiast, gdy jesteśmy skazani np. na InnoDB z założeń technicznych – nie oznacza, że się nie da.
Mam nadzieję, że komuś się przyda.
MySQL tags
We wpisie Chmura tagów w PHP, w którym został przedstawiony problem budowy chmury tagów zapisałem przykładowe zapytanie prezentujące przykładowe dane dla klasy, które dosłownie zabija bazę danych zliczając za każdym razem ilość występowań tagów. Dostając feedbacki, zauważyłem, że problem ten jest bagatelizowany przez wiele osób. Spróbujmy zbudować bardziej optymalne rozwiązanie zarządzania strukturą danych w taki sposób, aby dane wyciągać bardzo bezboleśnie.
Zbudujmy przykładową strukturę bazy danych tagów, do której będziemy przypinać różne rzeczy – newsy, artykuły, galerie zdjęć, zdjęcia, cokolwiek.
Najprostsza tabela db_tags o polach:
- tag_id, UNSIGNED, aby zwiększyć zakres INT – wartości ujemne nie są nam porzebne. Oczywiście primary key oraz auto increment.
- tag_name, chociażby varchar(255)
- tag_count, UNSIGNED, INT, ponownie bez znaku, aby zwiększyć zakres, wartości ujemne są nam niepotrzebne. Tutaj będziemy przechowywać liczbę reprezentującą, ile razy użyto tagu do oznaczenia dowolnego zestawu informacji.
CREATE TABLE db_tags (
tag_id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY ,
tag_name VARCHAR(255) NOT NULL ,
tag_count INT UNSIGNED NOT NULL
) ENGINE = INNODB;
Zastanówmy się, po czym będziemy sortować tagi. Warto założyć klucz na pole tag_count, znacznie przyspieszy późniejsze sortowanie wyników po najpopularniejszych tagach. Jeżeli chcemy sortować po liczbie występowań tagu oraz nazwie (aby chmura była alfabetycznie), warto założyć wspólny klucz na tag_name oraz tag_count. Osobiście sortowanie alfabetyczne zostawiam implementacji klasie tagów dla ksort(), bowiem zapytanie wyciągające tagi jest obarczone limitem, zatem wspólny klucz w bazie danych nie jest mi potrzebny – mniej danych w indeksach.
ALTER TABLE db_tags ADD INDEX (tag_count);
Tworzymy dowolną strukturę danych, która będzie podpinała się do naszych tagów. Pamiętajmy, że do tagów może podpinać się (a przynajmniej powinno, zależy od założeń początkowych projektu) wiele struktur jednocześnie. Wybrałem najbardziej pospolite – newsy w tabeli db_news.
CREATE TABLE db_news (
news_id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
news_title TEXT NOT NULL,
news_content TEXT NOT NULL
) ENGINE = INNODB;
Pozostało nam stworzyć tabelę wiążącą nasze newsy z tagami (nie tagi z newsami). Tabelę nazwałem db_news_tags. Zawierać ona będzie tylko dwa pola przechowujące identyfikator newsa oraz przypisanego do niego tagu, zachowując typ danych wiążących, czyli INT UNSIGNED. Zakładam wspólny primary key dla obu pól.
- handler_item – klucz ID newsa,
- handler_node – klucz ID tagu.
CREATE TABLE db_news_tags (
handler_item INT UNSIGNED NOT NULL,
handler_node INT UNSIGNED NOT NULL,
PRIMARY KEY (handler_item, handler_node)
) ENGINE = INNODB;
Buduję relacyjną bazę danych. Gdy jakiś tag zostanie usunięty, bądź gdy jakiś news zostanie usunięty, automatycznie powinien zniknąć wpis z tabeli db_news_tags, zatem używamy kluczy obcych:
ALTER TABLE db_news_tags ADD FOREIGN KEY (handler_item) REFERENCES db_news (news_id) ON DELETE CASCADE;
ALTER TABLE db_news_tags ADD FOREIGN KEY (handler_node) REFERENCES db_tags (tag_id) ON DELETE CASCADE;
Tak zaprojektowaną strukturę danych mogę spokojnie używać do przechowywania danych. Pozostaje kwestia obliczania ilości występowań tagów. Istnieją co najmniej dwie szkoły.
- Każda zmiana danych w db_news_handler wywołuje procedurę liczącą tagi. Trzeba mieć na uwadze, że tagi są przeliczane od początku mielenie bazy, ale de facto proces odbywa się po kluczach. Zaletą rozwiązania jest to, że przy bardzo rozbudowanych strukturach (np. liczymy tylko aktywne i widoczne tagi) procedura uwspólnia nam warunki podliczania, używając jej w wielu miejscach nie musimy się martwić o redefiniowanie triggerów.
- Dla przedstawionego przykładu w tym poście wystarczy inkrementacja licznika przy dodaniu i dekrementacja przy usunięciu tagu. W większości przypadków właśnie takiego rozwiązania powinno się używać.
Luźny komentarz techniczny (problems, tips & tricks): Aby ominąć problemy wynikłe z założenia w punkcie pierwszym, równie dobrze możemy napisać procedury, które inkrementują/dekrementują liczbę tagów w zależności od warunków (np. tylko wtedy, kiedy tag jest aktywny i widoczny w serwisie). Nikt nie powiedział, że procedury muszą liczyć wszystko od początku możemy się na takie rozwiązanie zgodzić, rezygnujemy natomiast z synchronizacji licznika podczas zmiany warunków, wówczas podczas każdej zmiany warunków, trzeba przekręcić licznik od początku, zliczając wszystkie rekordy wg. ustalonych warunków ręcznie. Triggera należałoby również umieścić w UPDATE (zmiana stanu tagu, np. z niewidocznego na widoczny, z aktywnego na nieaktywny). I to jest najrozsądniejsze rozwiązanie.
W naszym przypadku ograniczymy się do dwóch triggerów, które będą trzymały rękę na pulsie w momencie przypisania tagu do struktury INSERT oraz zerwaniu przypisania DELETE. Zatem:
CREATE TRIGGER NewsTagsCountInsert AFTER INSERT ON db_news_tags
FOR EACH ROW BEGIN
UPDATE db_tags SET tag_count = tag_count + 1 WHERE tag_id = NEW.handler_node;
END
CREATE TRIGGER NewsTagsCountDelete AFTER DELETE ON db_news_tags
FOR EACH ROW BEGIN
UPDATE db_tags SET tag_count = tag_count - 1 WHERE tag_id = OLD.handler_node;
END
Komentarz: bardziej eleganckim w większej strukturze danych byłoby wywołanie procedur inkrementujących i dekrementujących licznik – wówczas wykonywalibyśmy procedury (nie zapytania) w wielu strukturach wiązanych (nie tylko newsy, a video, ankiety, etc). Zmiana implementacji liczenia tagów byłaby wówczas wiele prostsza – zmienialibyśmy tylko procedurę, a nie każdy TRIGGER z osobna, zatem:
CREATE PROCEDURE TagsCountIncrement(IN iTagID INT)
BEGIN
UPDATE db_tags SET tag_count = tag_count + 1 WHERE tag_id = iTagID;
END
CREATE PROCEDURE TagsCountDecrement(IN iTagID INT)
BEGIN
UPDATE db_tags SET tag_count = tag_count - 1 WHERE tag_id = iTagID;
END
CREATE TRIGGER NewsTagsCountInsert AFTER INSERT ON db_news_tags
FOR EACH ROW BEGIN
CALL TagsCountIncrement(NEW.handler_node);
END
CREATE TRIGGER NewsTagsCountDelete AFTER DELETE ON db_news_tags
FOR EACH ROW BEGIN
CALL TagsCountDecrement(OLD.handler_node);
END
Finalnie, z czystym sumieniem:
SELECT tag_name, tag_count FROM db_tags ORDER BY tag_count LIMIT 0, 50
MySQL DELETE JOIN
Składowanie danych w kilku tabelach połączonych relacyjnie to bardzo dobry pomysł. Chyba najprostszym przykładem jest forum dyskusyjne: struktura oraz content postów mogą spokojnie być trzymane w osobnych tabelach. To samo tyczy się danych użytkowników. Rekordy rozbite na kilka tabel stają się mniej rozbudowane, o ile w ogóle występują – istnienie zawartości pola nie jest wtedy wymagane (użytkownik nie podał danych = nie ma rekordu).
Zaznaczając JOIN’ujemy tabele w zależności od potrzeb, co zdarza się bardzo często. O UPDATE JOIN już wspominałem, też bardzo wygodna operacja, natomiast, co w przypadku, gdy musimy usunąć rekord uzależniony od wartości pola w innej tabeli? Sprawa jest banalnie prosta.
Na początek kilka technicznych uwag, na które łatwo można się nadziać:
- Najczęściej będziemy mieli przypadek, w którym wartość pola musi być znana = rekord w tabeli obok musi istnieć. Nie zapomnijmy o pełnym złączeniu tabel INNER JOIN.
- Gdy czyścimy śmieci w bazie danych, chcemy, aby wartość pola była konkretna lub niezdefiniowana, tabele możemy złączyć lewostronnie LEFT JOIN.
- Składnia DELETE FROM jest bardzo podobna do SELECT. Zaznaczamy alias_tabeli.* jako wybór rekordu do usunięcia. Możemy usuwać rekordy z kilku tabel oddzielając zaznaczenia przecinkami.
Przy JOIN’ach wymagane jest zdefiniowanie aliasów i sprecyzowanie, co chcemy usunąć alias_tabeli.*(edit: nie jest wymagane definiowanie aliasów, przykłady niżej)
Przykłady.
Dane userów mam składowane w dwóch tabelach – w jednej podstawowe dane (id, name, pass, pass_salt, mail, status_active), w kolejnej dane (data [jako handler user -> user_data], data_* [* – jakieśdane]). Chcę usunąć wszystkich użytkowników, którzy zarejestrowali się przed 48-godzinami i nie aktywowali swoich kont, aby zwolnić unikalne nazwy użytkowników i adresy email. Jednym kryterium jest user_status_active z tabeli users, kolejnym jest data user_data_join z tabeli users_data. Jako, że mam założony kaskadowy foregin key na pole user_data w tabeli users_data, przy usunięciu rekordu z tabeli users pozbędę się również jego danych, o co dbać nie muszę przy wypisywaniu alias_tabeli.*. W przypadku, kiedy nie miałbym założonego foregin key, musiałbym obsłużyć usunięcie rekordu z users_data wypisując po przecinku tabelę. Zatem:
DELETE item.* FROM `cms_members` AS `item`
INNER JOIN `cms_members_data` AS `item_data` ON (item.user_id = item_data.user_data)
WHERE item.user_state_active = 0 AND item_data.user_data_join < NOW()
~Tiraeth przesłał rozwiązanie beż użycia aliasów i słowa kluczowego JOIN, odwołujemy się po nazwie tabeli:
DELETE cms_members.* FROM `cms_members`, `cms_members_data`
WHERE cms_members.user_id = cms_members_data.user_data AND user_state_active = 0 AND user_data_join < NOW()
Podzapytanie oraz INNER JOIN generuje nam iloczyn kartezjański:
INNER JOIN and , (comma) are semantically equivalent in the absence of a join condition: both produce a Cartesian product between the specified tables (that is, each and every row in the first table is joined to each and every row in the second table).
Mam nadzieję, że komuś się przyda.
„Rekurencja” w funkcjach/procedurach MySQL
Odzwyczajony od blogowania, zaabsorbowany przez niekorzystnego dla planet i blogosfery stanu rzeczy Social Media, postanowiłem wrzucić kolejny wpis, w podzięce za porady uzyskane z blogów kolegów z branży. Ostatnio moim zadaniem było zaprojektowanie struktury tabel bazy danych, która wraz z drzewem z zagłębieniem kategorii, ma przechowywać dane na temat cen za ogłoszenia publikowane w tych kategoriach.
Założenia wstępne wyglądały następująco:
- Każda kategoria może mieć rodzica, ale nie musi.
Jak komu wygodnie, postanowiłem wybrać rozwiązanie z polem category_parent int(11) UNSIGNED, domyślnie NULL (bez rodzica). - Kategorie mogą mieć ustaloną cenę za opublikowanie ogłoszenia, ale nie muszą.
Dodałem pole category_data_price float(6,2) UNSIGNED, domyślnie NULL (niezdefiniowana). - Kategorie, które nie mają zdefiniowanej ceny, a mają rodzica, przejmują cenę rodzica w zagłębieniu do nieskończoności. W przypadku, kiedy cena jest niezdefiniowana również dla rodziców, cena stanowi NULL.
Potrzebne mi było zapytanie, które zwróci mi zwyczajnie listę wszystkich kategorii wraz z cenami, uwzględniając zagłębienia, w jakich dana kategoria się znajduje. Podejścia składowania cen są dwa:
- Można zapisywać tylko cenę kategorii, która jest dla niej zdefiniowana, a przy wyciąganiu danych rekurencyjnie sprawdzać procedurą/funkcją cenę rodzica, jeżeli jest niezdefiniowana. I tak w kółko do przypadku, gdy któraś z kategorii będzie już miała zdefiniowaną cenę, bądź nie będzie się już gdzie zagłębić (kategoria nie ma rodzica).
- Można zapisać dwie ceny dodając pole dodatkowe, które przy będzie przechowywało wartość ceny, biorąc ją przy sprawdzaniu cen tylko przy zapisie rekordu do bazy danych.
Sposób drugi wydaje się być bardziej rozsądny w przypadku większej ilości zapytań podejmujących dane z bazy. Pierwszy odwrotnie – częściej wpisujemy coś do bazy. Z początku wybrałem pierwszy sposób, przy założeniu, że ceny będą generowane tylko w panelu administracyjnym, zatem zapytanie nie będzie wykonywane często. Niestety, moje myślenie jest bardziej abstrakcyjne, nastawione na elastyczność rozwiązań, w przyszłości cel istnienia bazy może się zmienić.
Tak czy siak, dla obu rozwiązań, trzeba stworzyć procedurę sprawdzającą ceny po rodzicach. Wygląda mniej więcej tak:
CREATE FUNCTION AnnouncementsCategoriesGetPrice(iCategoryId int(11)) RETURNS float(6,2)
BEGIN
DECLARE iResult FLOAT(6,2);
DECLARE iPointer INT(11);
SET iPointer = iCategoryId;
SET iResult = (SELECT category_data_price FROM cms_announcements_categories WHERE category_id = iPointer);
WHILE (iResult IS NULL AND iPointer IS NOT NULL) DO
SET iResult = (SELECT category_data_price FROM cms_announcements_categories WHERE category_id = iPointer);
SET iPointer = (SELECT category_parent FROM cms_announcements_categories WHERE category_id = iPointer);
END WHILE;
RETURN iResult;
END
Stosować ją można dla SELECT’u kategorii lub do pozyskania wartości pola tymczasowego przy zapisie do bazy.
Mam nadzieję, że komuś się przyda.