====== Bazy danych klucz wartość ====== Osoba realizująca referat: Kamil Kupiec Tematem referatu będzie omówienie baz typu klucz-wartość i zaprezentowanie BerkeleyDB. Zostaną również omówione bazy danych klucz-wartość przechowujące dane wyłącznie w pamięci ulotnej takie jak Memcached i Dreamcache. Na końcu zostanie przedstawiony przykład wykorzystania przez aplikację napisaną w PHP cache'u udostępnianego przez Memcached oraz Dreamcache. ===== Wstęp ===== Baza danych klucz-wartość w odróżnieniu od relacyjnej bazy danych nie przechowuje danych w tabelach (relacjach) ale w parach odpowiednio klucz i wartość. Taka baza danych umożliwia dostęp do przechowywanych wartości po podaniu klucza. Odpowiada ona tablicy asocjacyjnej, mapie lub słownikowi. Bazy danych klucz wartość realizowane są zwykle przez zastosowanie drzew poszukiwań (np. BST, AVL, R-B Tree, B-Tree) lub przez tablice haszujące. Klucz może być reprezentowany zwykle przez dowolny rodzaj danych, najczęściej jednak jest to łańcuch znaków. Możemy zdefiniować trzy podstawowe operacje logiczne na takiej bazie danych: * **Add(key, value)** - Dodaje rekord do bazy danych, dostępny po podaniu klucza. * **Lookup(key)** - Zwraca zawartość rekordu o kluczu key * **Remove(key)** - Usuwa rekord z tablicy asocjacyjnej Operacje te są zależne od konkretnej implementacji i mogą mieć inną nazwę. Zwykle również baza taka implementuje dodatkowe polecenia. Baza danych składa się z rekordów, logiczne rekord reprezentuje jeden wpis w bazie danych. Każdy taki rekord składa się z dwóch części: klucza rekordu i danych rekordu. Ponieważ bazy klucz-wartość używają parowania klucza z wartością są często postrzegane jako dwukolumnowa baza danych. Jednak dane przechowywane w rekordzie (value) mogą być typem złożonym, często przechowywane są obiekty lub struktury. Proces ten efektywnie zamienia 2-kolumnową bazę danych w n-kolumnową, gdzie n-1 jest przeznaczone na dane a 1 kolumna na klucz. W tym przypadku warto zauważyć, że jedna baza danych klucz-wartość jest jakby jedną tabelą w relacyjnej bazie danych. Jednak wiele systemów komputerowych używa więcej niż jednej bazy danych klucz-wartość tak jak relacyjna baza danych używa więcej niż jednej tabeli. W przeciwieństwie do RDBMS baza klucz-wartość przechowuje pojedynczą kolekcję rekordów zorganizowaną w wybrany sposób (B-tree, hash). W relacyjnej bazie system przechowywania danych jest ukryty. Często aplikacje korzystające z bazy danych są zaprojektowane w taki sposób aby pojedyncza baza danych przechowywała ustalony rodzaj danych. Pociąga to konieczność używania wielu baz danych w jednej aplikacji. Rozważmy przykładowo aplikację do bankowości. taka aplikacja może zarządzać danymi związanymi z kontami bankowymi, rachunkami walutowymi, rachunkami maklerskimi, lokatami, kredytami itd. Aplikacja taka musi również zarządzać informacjami o osobach, instytucjach itd. W tradycyjnej relacyjnej bazie danych taki zbiór informacji byłby reprezentowany przez złożony zbiór tabel. W przypadku bazy klucz-wartość wszystkie te informacje byłyby podzielone i utrzymywane przy użyciu wielu baz. ===== Bazy persystentne ===== Bazy danych klucz-wartość są rozwiązaniem szeroko używanym ze względu na wydajność i lekkość. Jest wiele implementacji baz danych klucz wartość. Oto niektóre z nich: * BerkeleyDB * Riak * HamsterDB * Membase * Tokyo Cabinet * Amazon SimpleDB Poniżej omówię bazę BerkeleyDB. ==== BerkeleyDB ==== BerkeleyDB jest implementacją bazy danych typu klucz-wartość będąca obecnie własnością Oracle.\\ Jest wbudowaną (embedded) bazą danych przeznaczoną do ogólnego zastosowania. === Licencja === BerkeleyDB dostępna jest zarówno na licencji Open Source jak i komercyjnej. === Wspierane środowiska === BerkeleyDB może być używana w aplikacjach poprzez jej API dostępne dla wielu języków: * C/C+ + * Java * języki skryptowe: Perl, Python, PHP, Ruby i inne Api umożliwia zapis do bazy, odczyt oraz inne zaawansowane operacje takie jak np. zarządzanie transakcjami. Ponieważ BerkeleyDB rozwiązaniem typu "embedded" pozwala ona na bardzo szybkie wykonywanie operacji. Baza dostępna jest jako biblioteka, którą można skompilować i zlinkować razem z własną aplikacją. === Opis technologii === Pobieranie rekordu z bazy danych często określa się mianem operacji get(). Analogicznie zapis rekordu w bazie określany jest mianem operacji put(). Podczas operacji zapisu do bazy danych rekord jest wstawiany zgodnie z porządkiem określonym przez wybraną strukturę danych. Jeśli wstawimy rekord o kluczy który już istnieje w bazie danych wtedy istniejący rekord zostanie zastąpiony nowym. Istnieje również opcja obsługi zduplikowanych rekordów pozwalająca w takim przypadku przechowywać oba rekordy w bazie. BerkeleyDB oferuje też specjalny rodzaj bazy zwaną pomocniczą bazą danych (secondary database), która spełnia rolę indeksu. Normalnie przeszukiwanie danych odbywa się wyłącznie po kluczu (key) natomiast pomocnicza baza (index) pozwala na przeszukiwanie na podstawie zawartości (value). Baza posiada również funkcję cache'u dodatkowo przyspieszającą operacje na często używanych danych. obsługa cache'u jest przeźroczysta dla aplikacji używającej bazy danych. == Wewnętrzne struktury przechowywania danych == Technologia umożliwia zdefiniowanie wewnętrznej struktury służącej do przechowywania danych. Różne metody dostępu do danych posiadają swoje unikalne zalety i wady: * **B-Tree**\\ Dane są przechowywana w zrównoważonym drzewie w sposób uporządkowany. Zarówno klucz jak i wartość mogą być wartościami złożonymi (np. strukturami). * **Hash**\\ Dane przechowywane są w tablicy haszującej. Podobnie jak w przypadku B-drzewa zarówno klucz jak i wartość mogą być typami złożonymi. * **Queue**\\ Dane przechowywane są w kolejce jako elementy o stałej długości. Każdy rekord używa wewnętrznego numeru jako klucza. Ten sposób został zaprojektowany do szybkich wstawień na koniec kolejki oraz szybkich operacji wyciągania z kolejki pierwszego elementu. == Wybór struktury == Do typowych zastosowań wybierzemy B-drzewo lub tablicę haszującą. Dla małych zbiorów danych, które mogą w całości pomieścić się w pamięci ulotnej nie ma różnicy pomiędzy strukturą B-drzewa a tablicy haszującej. Oba spiszą się zadowalająco. Domyślnie jest używana struktura B-drzewa. Warto zwrócić uwagę na to, iż głownie powinien nas interesować rozmiar danych na których operujemy w trakcie działania aplikacji, nie natomiast rozmiar całego zbioru danych. Wiele aplikacji posiada duży zbiór danych, lecz operuję tylko na ich małej części. Gdy danych jest na tyle, że niezbędne jest przechowywanie ich w pamięci trwałej trzeba rozważyć następujące opcje: * **B-drzewo** - gdy klucze dobrze się sortują i mamy pewność, że po pobraniu danego klucza będziemy pobierać jego sąsiadów. * **Tablica haszująca** - gdy nasza baza danych jest bardzo duża. Dla każdej z metod przechowywania baza musi przechowywać pewną ilość informacji wewnętrznych. Ilość ta jest większa dla B-drzewa niż dla tablicy haszującej. Efektem tego jest większa liczba operacji I/O w przypadku B-drzewa niż tablicy haszującej dla bardzo dużych zbiorów danych. Dodatkowo jeśli zbiór danych jest na tyle duży, że praktycznie przy każdym zapytaniu muszą być wykonywane operacje I/O wtedy tablica haszująca jest o wiele lepszym wyborem. == Ograniczenia i przenośność == BerkeleyDB umożliwia operowanie na bazach danych mieszczących się w całości w pamięci (cache) jak i na bazach przechowujących wiele milionów rekordów. Baza może przechować zbiór danych o rozmiarze do 256 TB a pojedynczy klucz lub rekord mogą mieć rozmiar maksymalnie 4 GB. Według twórców baza przechowuje dane w formacie binarnym, który jest przenośny między platformami, również między architekturami big-endian i litte-endian. === Ciekawostki === W relacyjnej bazie danych MySQL do wersji 5.1 była możliwość wybrania BerkeleyDB jako silnika bazy danych.\\ źródło: [[http://dev.mysql.com/doc/refman/5.0/en/storage-engines.html|http://dev.mysql.com/doc/refman/5.0/en/storage-engines.html]] W najnowszej wersji BerkeleyDB zostało dodane SQL API udostępniające interpretację zapytań SQL.\\ źródło: [[http://www.oracle.com/technology/products/berkeley-db/sql.html|http://www.oracle.com/technology/products/berkeley-db/sql.html]] === Przykładowy program === == Instalacja == //Opis instalacji dotyczy środowiska Linux/Unix.// - Pobieramy oprogramowanie BerkeleyDB ze strony [[http://www.oracle.com/technology/software/products/berkeley-db/db/index.html|http://www.oracle.com/technology/software/products/berkeley-db/db/index.html]]. Wybieramy wersję 4.8.30 ponieważ pobranie najnowszej wymaga rejestracji. - rozpakowujemy archiwum do katalogu projektu: $ tar -xvzf db-4.8.30.tar.gz $ mv db-4.8.30 berkeleydb - konfigurujemy ustawiając katalog instalacji, budujemy i instalujemy: $ cd berkeleydb/build_unix $ ../dist/configure $ make $ sudo make install == kod programu == #include #include #include int main(int argc, char * argv[]) { try { // create database handle Db db(0,0); // open the database using the handle db.open(NULL, "./my_db", NULL, DB_BTREE, DB_CREATE, 0644); // create records char first_key[] = "first_record"; u_int32_t key_len = (u_int32_t) strlen(first_key); char first_value[] = "Hello World - BerkeleyDB style!"; u_int32_t value_len = (u_int32_t) strlen(first_value); Dbt key(first_key, key_len + 1); Dbt value(first_value, value_len + 1); // insert into database int ret; ret = db.put(0, &key, &value, DB_NOOVERWRITE); if(ret == DB_KEYEXIST) { std::cout << "hello_world: " << first_key << "already exists in db" << std::endl; } // read teh value stored Dbt stored_value; ret = db.get(0, &key, &stored_value, 0); // print the fetched value std::cout << (char *) stored_value.get_data() << std::endl; // close the db handle db.close(0); } catch(DbException &dbex) { std::cout << "hello_world: exception caught: " << dbex.what() << std::endl; } } == kompilacja == kompilacja wymaga wskazania katalogu z plikami ".h" (domyślnie /usr/local/BerkeleyDB.X.X/include). == wyniki działania == Niestety nie udało się prawidłowo skonfigurować środowiska dla Cpp. ===== Bazy in-memory ===== Bazy danych nie konieczne muszą przechowywać dane w pamięci trwałej. Istnieją bazy danych przechowujące rekordy wyłącznie w pamięci ulotnej. Ogromną zaletą takiej bazy jest czas dostępu do danych. Wiadomo, że pamięć dyskowa jest kilka rzędów wielkości wolniejsza niż pamięć RAM. W pewnych zastosowaniach jest to ogromna zaleta. W tym rozdziale omówię zastosowanie baz klucz-wartość przechowywanych w pamięci ulotnej jako cache. Przykładowe implementacje: * Memcached * Dreamcache * Dynamo (technologia Amazon) * Velocity (technologia Microsoft) ==== Bazy klucz-wartość jako cache ==== Najczęstszym zastosowaniem baz klucz-wartość przechowywanych w pamięci jest użycie ich jako cache, który zmniejsza ilość zapytań do właściwej bazy danych (np. relacyjnej) przechowując ostatnio przesyłane dane. Rozwiązanie to jest szeroko stosowane w branży IT m. in. przez Facebook, Amazon, Google. === Obciążenie bazy danych w systemie bez serwera cache'u === {{:pl:dydaktyka:ztb:2010:projekty:nosql_key_value:nosql_key_value_no_cache.jpeg|}} === Obciążenie bazy danych w systemie z serwerem cache'u === {{:pl:dydaktyka:ztb:2010:projekty:nosql_key_value:diagnosql_key_value_cache.jpeg|}} ==== Memcached ==== Memcached jest darmowym oprogramowanie pozwalającym na cache'owanie. Stworzone zostało w celu zwiększenia wydajności aplikacji webowych przez zmniejszenie narzutu na komunikację z bazą danych. === Licencja === Oprogramowanie wydane na licencji Open Source. === Wspierane języki programowania === Implementacje API memcached dostępne są dla następujących języków: * C, C+ +, C# * Java * PHP * Perl, Python === Opis technologii === Memcached jest bazą klucz-wartość przechowującą dane w pamięci. Działa on w systemie jako serwer usług. Rekordy składają się z klucza (key), czasu wygaśnięcia (expiration time), opcjonalnych flag i danych (value). Jako dane możemy przechowywać dowolne wartości, muszą być jednak wcześniej poddane pewnej serializacji. Mogą to być ciągi znaków, obiekty, nawet całe wyniki zapytania do bazy danych. Serwery memcached nie synchronizują danych pomiędzy sobą a operacje wstawiania i pobierania danych wykonywane są w stałym czasie. Memcached został zaprojektowany jako serwer cache, więc rekordy są usuwane po określonym czasie. === Protokół memcached === Najważniejsze polecenia protokołu memcached to: * **set** - wstawia rekord do bazy * **get** - pobiera rekord o podanym kluczu * **delete** - usuwa rekord o podanym kluczu jeśli taki istnieje w bazie * **stats** - wyświetla statystyki Protokół memcached jest używany również przez inne rozwiązania np. MemcacheDB i Dreamcache. === Przykładowe wykorzystanie w PHP === Poniższy przykład ilustruje przykładowe zastosowanie Memcached. Zaczynamy od definicji adresów poszczególnych serwerów Memcached. $MEMCACHE_SERVERS = array( "10.1.1.1", //web1 "10.1.1.2", //web2 "10.1.1.3", //web3 ); Następnie tworzymy instancję obiektu Memcache dostarczonego przez API: $memcache = new Memcache(); foreach($MEMCACHE_SERVERS as $server){ $memcache->addServer ( $server ); } Poniższy kod sprawdza czy rekord o podanym kluczu znajduje się w cache'u a w przypadku niepowodzenia (miss) pobiera dane z relacyjnej bazy danych MySQL a wynik zapytania zapisuje do cach'u. $huge_data_for_page = $memcache->get("huge_data_for_page"); if($huge_data_for_page === false){ $huge_data_for_page = array(); $sql = "SELECT * FROM hugetable WHERE timestamp > lastweek ORDER BY timestamp ASC LIMIT 50000"; $res = mysql_query($sql, $mysql_connection); while($rec = mysql_fetch_assoc($res)){ $huge_data_for_page[] = $rec; } // cache for 10 minutes $memcache->set("huge_data_for_page", $huge_data_for_frong_page, 600); } === Instalacja Memcached i konfiguracja PHP === //Przeprowadzona w środowisku Linux/Unix// Instalujemy Memcached i php5-memcache z pakietów: $ sudo aptitude install memcached php5-memcache Dopisujemy linijkę w pliku php.ini: extension=memcache.so; Uruchamiamy ponownie serwer www i uruchamiamy Memcached jako demona: $ memcached -d === program === Nie można przesłać kodu na wiki: Cannot send POST to doku.php - method not implemented? plik: {{:pl:dydaktyka:ztb:2010:projekty:nosql_key_value:nosql_key_value_memcache_test.tar.gz|}} ==== Dreamcache ==== === Licencja === Apache License 2.0 === Opis technologii === Dreamcache jest to szybki serwer cache'ujący stworzony w laboratorium Onetu (Dreamlab Onet.pl). Jest to rozwiązanie o podobnej funkcjonalności do memcached, lecz dodające kilka możliwości: * definiowanie przestrzeni nazw - umożliwia przechowywanie różnych obiektów pod tym samym kluczem pod warunkiem, że znajdują się w różnych przestrzeniach nazw. * ustalanie quoty dla przestrzeni nazw. Dreamcache operuje na protokole Memcached co umożliwia wymienność rozwiązań === Instalacja === //W środowisku Unix/Linux// Po ściągnięciu źródeł konfigurujemy i instalujemy bibliotekę oraz serwer w standardowy sposób: $ ./configure --path=/usr --sysconfdir=/etc $ make $ sudo make install Następnie uruchamiamy serwer dreamcache: $ /usr/bin/dreamcache Wspomniana wcześniej aplikacja webowa działa identycznie jak w przypadku Memcached. ===== Literatura ===== * [[http://www.oracle.com/technology/products/berkeley-db/index.html| Dokumentacja BerkeleyDB]] * [[http://memcached.org/|Memcached]] * [[http://dreamcache.sourceforge.net/index.html| Dreamcache]] * [[http://nosql-database.org/|http://nosql-database.org/]]