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

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

Przykładowy program

Instalacja

Opis instalacji dotyczy środowiska Linux/Unix.

  1. Pobieramy oprogramowanie BerkeleyDB ze strony http://www.oracle.com/technology/software/products/berkeley-db/db/index.html. Wybieramy wersję 4.8.30 ponieważ pobranie najnowszej wymaga rejestracji.
  2. rozpakowujemy archiwum do katalogu projektu:
    $ tar -xvzf db-4.8.30.tar.gz
    $ mv db-4.8.30 berkeleydb
  3. konfigurujemy ustawiając katalog instalacji, budujemy i instalujemy:
    $ cd berkeleydb/build_unix
    $ ../dist/configure
    $ make
    $ sudo make install
kod programu
#include <iostream>                           
#include <string.h>                           
#include <db_cxx.h>                           
 
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

Obciążenie bazy danych w systemie z serwerem cache'u

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: 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

pl/dydaktyka/ztb/2010/projekty/nosql_key_value/start.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0