Tematem wykładu jest model fizyczny bazy danych - w odróżnieniu od modelu logicznego rozważanego do tej pory. Dla większości użytkowników baz danych znajomość szczegółów technicznych organizacji baz danych w komputerze może nie jest istotna, po to został zresztą wprowadzony poziom logiczny bazy danych, jednakże ogólna orientacja w tym temacie jest pożądana. Umożliwia ona zrozumienie działania baz danych i ich uwarunkowań a co za tym idzie daje możliwość dostrojenia bazy danych w celu efektywniejszego jej działania. Jest więc nieodzowna dla osób administrujących systemami baz danych nie mówiąc już o osobach planujących zbudowanie własnego SZBD.
Zostaną rozważone takie zagadnienia jak: zarządzanie miejscem na dysku, zarządzanie obszarem buforów danych (w RAM) oraz organizacja zapisu rekordów na dysku. Inaczej mówiąc, zostanie opisane działanie modułów SZBD najniższego poziomu jak i wymagane struktury danych.
Zagadnienia budowy indeksów i wykonywania instrukcji SQL zostaną przedstawione na kolejnych wykładach.
Do tej pory zajmowaliśmy się głównie problemami modelu logicznego bazy danych. Teraz przyszła pora poznać szczegóły implementacji modelu logicznego w komputerze czyli szczegóły modelu fizycznego bazy danych. Model ten ściśle zależy od bieżącej architektury systemów komputerowych. Wraz ze zmianami w architekturze model ten ulega i także w przyszłości będzie ulegał zmianom. Zakładamy, że czytelnik zna podstawy budowy współczesnych systemów komputerów w tym nośników przechowywania danych takich jak magnetyczne dyski. Szczegółami technicznymi budowy dysków nie będziemy się zajmować na tym wykładzie.
Model fizyczny bazy danych jest oparty na pojęciach pliku i rekordu. Plik obiektu bazy danych (nazywany też segmentem tego obiektu) składa się z rekordów posiadających ten sam format. Format rekordu jest listą nazw pól z określeniem ich typów danych. Rekord składa się z wartości poszczególnych pól. Niektóre pola są wyróżnione jako klucz wyszukiwania rekordu. Może być więcej niż jeden klucz wyszukiwania rekordu. Na poziomie fizycznym nie wymaga się aby był określony jednoznaczny identyfikator (klucz) rekordu w pliku.
Podstawowymi operacjami na pliku, inicjowanymi przez programy aplikacyjne, są:
Zatem duża różnorodność operacji na bazie danych dostępnych za pomocą instrukcji języka SQL, sprowadza się do tylko czterech na poziomie fizycznym. Oczywiście operacje na słowniku danych również są wykonywane w ten sposób.
Trzeba tu podkreślić, że plik modelu fizycznego bazy danych może być reprezentowany przez plik dostępny w systemie plików komputera ale nie musi. Tak więc pojęcia pliku rekordów z danymi i pliku dyskowego nie są tożsame.
W specjalnym przypadku plik dyskowy może obejmować kilka plików bazy danych (np. w przypadku klastra kilku tabel).
Również w specjalnych przypadkach tabela jest zapisywana w więcej niż
jednym pliku dyskowym np. gdy tabela jest dzielona na partycje, które mogą być
przetwarzane równolegle przez osobne procesy. Wtedy jednemu plikowi modelu
fizycznego bazy danych odpowiada kilka plików dyskowych.
Współczesne systemy zarządzania bazą danych przechowują dane na twardych (magnetycznych) dyskach. Aby wykonać operacje na danych, trzeba je najpierw zapisać w pamięci wewnętrznej RAM, wykonać na nich operacje a następnie przepisać wyniki na dysk. Stąd nieodzowność stosowania operacji We/Wy:
Obie operacje są o rząd wielkości wolniejsze niż operacje w pamięci RAM – muszą być stosowane przez SZBD umiejętnie! Koszt operacji na bazie danych jest przedstawiany jako liczba operacji We/Wy.
Naturalne wydaje się pytanie dlaczego danych nie można przechowywać
w pamięci RAM?
Pierwszym argumentem jest fakt, że pamięć RAM jest chwilowa. Po wyłączeniu komputera z prądu tracimy wszystkie dane. Można tu jednak argumentować, że nie trzeba komputera wyłączać z prądu a wszelkie awarie zasilania rozwiązywać za pomocą urządzenia UPS, które w chwili awarii może przepisać dane na trwały nośnik. Drugim, poważnym argumentem jest istotnie wyższy koszt pamięci RAM niż dysku (rzędu sto razy wyższy). Trzecim, decydującym argumentem było do tej pory to, że stosowane we współczesnych komputerach 32 bitowe adresowanie ogranicza ilość danych, które można zapisać w pamięci RAM. Jednakże znajdujemy się już w trakcie przechodzenia na adresowanie 64 bitowe.Powyższa dyskusja pokazuje, że w niedalekiej przyszłości możemy mieć do czynienia z nowym, alternatywnym modelem fizycznym bazy danych. Na razie jednak jest faktem, że podstawowym nośnikiem przechowywania danych w bazie danych jest dysk magnetyczny. |
Oprócz dysków używa się też obszerniejszych ale za to
wolniejszych w dostępie nośników danych takich jak taśmy magnetyczne, dyski
optyczne, CD ROMy. Służą
one do przechowywania: kopii zabezpieczających bieżącej bazy danych (backup),
dzienników transakcyjnych off-line oraz kopii archiwalnych
danych.
Charakterystyka używania danych przechowywanych na dysku
Natomiast w przypadku taśm
mamy do czynienia z dostępem sekwencyjnym
- dane są odczytywane jedna po drugiej od początku do końca taśmy jako jedna,
długa operacja We-Wy. Zaletami taśm są duża pojemność i niski koszt. Są używane
do archiwizowania i tworzenia kopii zabezpieczających (backup-ów).
W przypadku dysku jako podstawowego nośnika danych w bazie danych nasz ogólny model fizyczny ulega uzupełnieniu o strony dyskowe. Oto jego podsumowanie.
Tabela (relacja) jest reprezentowana przez plik (dyskowy). Plik składa się ze stron. Strona składa się z rekordów. Rekord składa się z pól.
Rys. 8.1 Porównanie pojęć poziomu logicznego i fizycznego
Ponadto:
Gdy rozmiar rekordu jest większy niż rozmiar strony, rekord jest dzielony na części przechowywane na osobnych stronach - najlepiej sąsiadujących na dysku. (Ta cecha nie jest implementowana w każdym systemie SZBD. Jeśli nie jest implementowana projektant bazy danych musi to uwzględnić, dzieląc długie wiersze na części przechowywane albo w tej samej tabeli albo w różnych - np. część atrybutów umieszczamy w jednej tabeli część w drugiej.)
Duże obiekty LOB są trzymane w osobnym obszarze przeznaczonym do ich przechowywania w bazie danych, zwykle jako ciąg sąsiednich stron. W rekordach z danymi znajdują się tylko ich lokalizatory.
Gdy schemat dostępu do danych polega na użyciu powiązanych danych z dwóch lub więcej tabel (np. departamenty i ich pracownicy;
zamówienia i pozycje zamówień), w jednym pliku są zbierane dane z kilku tabel w oparciu o wspólny klucz (np. numer departamentu czy identyfikator
klienta) - mamy wtedy do czynienia z klastrem tabel.
Hierarchia nośników przechowywania danych w bazie danych
Rys. 8.2 Hierarchia nośników przechowywania danych w bazie danych
Te same dane np. rekord pracownika mogą się w tej samej chwili znajdować w trzech różnych miejscach! Co więcej mogą się zmieniać w jednym z nich (w pamięci RAM) powodując brak (chwilowy) synchronizacji. Na ogół zmiany są propagowane z pamięci RAM do dysku i następnie na taśmę. Ale są sytuacje, np. operacja ROLLBACK albo awaria gdy rekord zapisany na dysku lub na taśmie zastępuje rekord zapisany w pamięci RAM.
Przejdziemy teraz do omówienia podstawowych modułów SZBD realizujących operacje na stronach (nie
odwołując się do rekordów), z których
korzystają inne moduły SZBD. Są to:
moduł zarządzania miejscem na dysku oraz moduł zarządzania
buforami w
pamięci RAM.
W pliku mamy dwa rodzaje stron:
Zakładamy także, że system ma możliwość rozszerzania pliku rekordów i alokacji nowych, pustych stron oraz że system ma możliwość zwrotu (dealokacji) nieużywanych stron.
Moduł zarządzania miejscem na dysku (ang. disk space manager) realizuje następujące funkcje:
Rozmiarem strony jest zwykle rozmiar bloku dyskowego i strony są przechowywane jako bloki dyskowe więc odczyt/zapis strony wykonuje się jako pojedyncza operacja We/Wy.
Moduł zarządzający miejscem na dysku ukrywa szczegóły sprzętu i
systemu operacyjnego i umożliwia pozostałym modułom traktowanie danych na
dysku jako zbioru stron.
Moduł zarządzania buforami danych (ang. buffer manager) jest odpowiedzialny za sprowadzanie stron z dysku do puli buforów danych w pamięci RAM. Dane muszą być umieszczone w buforach danych aby procesy SZBD mogły na nich operować! Zapis strony odbywa się w ramce (ang. frame).
Rys. 8.3 Pula ramek
Oprócz puli ramek w pamięci RAM są przechowywane:
Ponadto wszystkie ramki, których licznik odwołań = 0, tworzą listę wolnych ramek (czasami lista ta jest tworzona z opóźnieniem).
Moduł zarządzania buforami danych jest wykorzystywany przez procesy SZBD - przede wszystkim przez procesy realizujące zlecenia użytkowników. Oto szkic jego działania.
Gdy procesowi jest potrzebna strona wykonywany jest algorytm:
Gdy zmienia się zawartość ramki:
Strona w buforze danych może być potrzebna wielu procesom:
Z jednej ramki w pamięci RAM
może korzystać wiele procesów. Sposób korzystania jest określony przez
specjalne procedury, o których będzie mowa w wykładzie o transakcjach.
Strona jest na liście wolnych ramek gdy jej licznik odwołań jest równy 0. Stosowane są następujące strategie wyboru ramki do zastąpienia:
Wydawałoby się, że strategia LRU powinna być zawsze najlepsza.
Okazuje się, jak pokazuje poniższy przykład, że nie jest tak zawsze.
Zjawisko sekwencyjnego zalewania puli ramek:
Stosując strategię LRU powtarzamy wielokrotnie sekwencyjne przeglądanie pliku. Gdy #ramek < #stron w pliku, wtedy każde żądanie strony powoduje operację We/Wy.
Strategia polegająca na wczytaniu najpierw #ramek stron do pamięci RAM, a następnie stosowaniu strategii MRU byłaby lepsza w tym przypadku. Część stron równa #ramek–1 pozostawałaby cały czas w puli buforów, natomiast pozostałe strony wczytywane byłyby kolejno do jednej z ramek.
Podobnie jeśli podejrzewamy, że wczytywane strony nie będą używane w najbliższym czasie, a tak możemy wnioskować w przypadku przeglądania wierszy dużej tabeli, nie opłaca się zastępować stron z rekordami, które są często używane przez strony pochodzące z pełnego przejrzenia wierszy dużej tabeli.
W praktyce proces wykonujący zlecenie użytkownika może posiadać informacje, że pewne strony są często używane i w związku należy je na stałe przechowywać w buforach w pamięci RAM. Komercyjne SZBD w większości realizują taką możliwość.
W stosowanych serwerach wzrastają rozmiary pamięci RAM i w związku z tym także
rośnie liczba buforów danych. Wielokrotnie używane strony powinny więc być stale przechowywane w buforach.
Gdy baza danych jest używana przez aplikację biznesową, przyjmuje się że średnio
co najmniej 90% potrzebnych do wykonania zapytania danych powinno znajdować się w buforach.
Ponadto, jest potrzebny niezależny proces serwera bazy danych, który będzie
regularnie synchronizował zawartości stron
w buforach z tymi na dysku.
W modelu obiektowo-relacyjnym jak i przy implementacji modelu relacyjnego
(np. przy indeksach) występują wartości, które są wskaźnikami do rekordów
(wierszy, obiektów). Wskaźniki są
reprezentowane przez adresy obiektów składowanych na dysku. Gdy obiekty
zostają zapisane w buforach, jest
możliwość przemiany adresów dyskowych na adresy pamięci RAM (ang. pointer
swizzling). Przetwarzanie takich obiektów staje się szybsze. Przy zapisie
obiektu na dysk jest konieczna transformacja odwrotna adresów pamięci RAM na adresy
dyskowe. Potrzebna jest więc tabela odwzorowująca wzajemnie adresy obiektów
na dysku i w pamięci.
Gdy użytkownik potrzebuje konkretnego rekordu z bazy danych, proces obsługujący zlecenie użytkownika:
W punkcie 3 jest potrzebna znajomość struktur zapisu: pól w ramach rekordu i rekordów na stronie. Omówimy je w tej chwili.
Liczba i typy pól są takie same dla wszystkich rekordów w pliku; są zapisane w słowniku danych (katalogu systemowym). Jest kilka alternatywnych formatów zapisu pól w ramach rekordu.
Zapis rekordu składa się ze spójnego obszaru zawierającego ciąg pól P1,...,Pn o stałych rozmiarach D1,...,Dn. Mając adres bazowy (początek rekordu) B łatwo można obliczyć początek i-tego pola jako B+D1+...+Di-1.
Rys. 8.4 Zapis rekordu stałej długości
Istnieją dwa alternatywne formaty (przy założeniu, że #pól jest stała). W pierwszym przypadku, rozdzielamy pola za pomocą specjalnego separatora np. symbolu '$'. W drugim przypadku, na początku zapisu rekordu umieszczamy tablicę wskaźników (offsetów) do początków kolejnych pól.
Rys. 8.5 Zapis rekordu zmiennej długości
W drugim przypadku uzyskujemy:
Powyższą strukturę danych można rozszerzyć do przypadku,
gdy liczba pól jest zmienna – ale ich typ jest określony statycznie w słowniku
danych (katalogu systemowym). Mianowicie przed katalogiem wskaźników do pól
umieszczamy liczbę pól w bieżącym rekordzie (czyli rozmiar tablicy offsetów).
Nie trzeba wtedy reprezentować pól na końcu rekordu nie mających ustalonych wartości, czyli będących
Null.
Z kolei rozpatrzymy formaty zapisu rekordów w ramach strony.
Istnieją dwa alternatywne formaty. W obu przypadkach zapis strony składa się z ciągu miejsc, w każdym z nich albo jest zapisany rekord albo miejsce jest wolne. W pierwszym przypadku, najpierw są zgrupowane wszystkie miejsca zajęte, a następnie wolne. W drugim przypadku, miejsca wolne i zajęte są ze sobą przemieszane - to czy dane miejsce jest wolne czy zajęte wskazuje bit w dodatkowej tablicy Occupied:
Occupied(i)=1
wtedy i tylko wtedy, gdy i-te miejsce na stronie jest zajęte.
Rys. 8.6 Zapis rekordów stałej długości
Przy operowaniu na danych pojawia się potrzeba sięgania do konkretnych rekordów, a nie do wszystkich za każdym razem np. sięgamy do rekordu w oparciu o jego wcześniej wyliczony adres bądź poprzez jego adres znaleziony w indeksie.
Adres rekordu czyli identyfikator rekordu rid, identyfikujący jego położenie na dysku, jest określany następująco:
rid = <id_strony, numer pozycji na stronie>
W przypadku pierwszej struktury przesuwanie rekordów na stronie powoduje zmianę identyfikatora rekordu, co komplikuje odwołania do rekordu przez jego identyfikator rid. W przypadku drugiej struktury rekord nie jest przesuwany na stronie, nie zmienia się więc jego identyfikator.
W przypadku rekordów zmiennej długości adres zapisu rekordu na stronie jest określony przez wartość w tablicy pozycji Poz. Wartość Poz(i) wskazuje na początek zapisu i-tego rekordu, 1<= i <= N. Dodatkowo, wartość Poz(0) wskazuje na początek obszaru wolnych miejsc.
Rys. 8.7 Zapis rekordów zmiennej długości
Adres rekordu czyli identyfikator rekordu rid, identyfikujący jego położenie na dysku, jest określany następująco:
rid = <id_strony, numer pozycji w tablicy Poz>
Gdy przesuwamy i-ty rekord na stronie, jego nowy adres na stronie aktualizujemy w Poz(i). Nie zmienia to indeksu i a zatem nie zmienia także identyfikatora rekordu rid.
Natomiast przy przenoszeniu rekordu na inną stronę, identyfikator rekordu zmienia się. Gdy tego rodzaju operacje są przewidywane, trzeba to uwzględnić w strukturze danych:
Na stronie dyskowej są zapisywane także dodatkowe informacje jak informacje
o transakcjach, które aktualnie wykonują operacje na rekordach przechowywanych
na danej stronie czy powiązania między stronami w ramach struktury danych
pliku rekordów (o tym za chwilę).
Plik stanowi kolekcję stron, z których każda zawiera zero, jeden lub więcej rekordów. Jak wiemy, na pliku są wykonywane następujące rodzaje operacji:
Jest możliwe kilka organizacji pliku rekordów. Podstawowa różnica między nimi polega na tym, czy porządkują one rekordy według wartości pewnego klucza czy nie. Najpierw rozważymy organizacje zapisu nieuporządkowanego (nazywanego potocznie stertą ang. heap).
Organizacja nieuporządkowana jest wygodna przy wykonywaniu zapytań dotyczących wszystkich rekordów lub większości rekordów np.
SELECT
* FROM Emp;
lub
SELECT * FROM Emp e WHERE e.Sal > 1000;
gdy wiemy, że większość pracowników zarabia powyżej 1000.
Plik nieuporządkowany w wersji dwie listy
Rys. 8.8 Zapis pliku w postaci dwóch list
Na jednej liście trzymane są strony z wolnymi miejscami do wstawienia nowych rekordów; na drugiej liście są trzymane strony bez wolnego miejsca do wstawienia nowych rekordów.
Plik nieuporządkowany w wersji katalogu stron
Rys. 8.9 Zapis pliku w postaci katalogu stron
Stan zajętości stron jest zapisywany w osobnym katalogu.
Przy wpisywaniu nowego rekordu, najpierw wybieramy w katalogu stronę z wolnym miejscem, ściągamy ją i wpisujemy rekord.
Alternatywne w stosunku do pliku nieuporządkowanego ogranizacje zapisu polegają na zachowaniu pewnego ustalonego porządku względem klucza rekordu. Przedstawimy dwa takie rozwiązania: plik posortowany i plik haszowany.
Rekordy są zapisywane na kolejnych stronach zgodnie z porządkiem względem klucza wyszukiwania rekordu. Taka reprezentacja jest wygodna gdy rekordy przetwarza się zawsze w pewnym, ustalonym porządku lub tylko pewien ich zakres względem tego porządku np.
SELECT * FROM Emp e ORDER BY e.Sal;
lub
SELECT * FROM Emp
e WHERE e.Sal BETWEEN 1000 and 2000;
W pliku posortowanym wyszukanie rekordu mając dany jego klucz wyszukiwania jest nieco szybsze niż dla pliku nieuporządkowanego, ale ze względu na to, że rekordy znajdują się na dysku, zastosowanie jednej z szybkich metod wyszukiwania jak wyszukiwanie binarne nie jest w pełni możliwe.
Są możliwe dwie implementacje:
1. Pełny ekstent – bloków sąsiadujących ze sobą na dysku – rekordy są uporządkowane według wartości klucza wyszukiwania. Jest problem ze wstawieniem nowego rekordu lub usunięciem rekordu z pliku. Jest możliwość zastosowania wyszukiwania binarnego.
Rys. 8.10 Plik posortowany w postaci pełnego ekstentu
2. Lista bloków (lub ekstentów) – rekordy są uporządkowane według wartości klucza wyszukiwania ale kolejne bloki na liście nie muszą być sąsiednie. Nie ma problemu ze wstawieniem nowego rekordu i usunięciem rekordu z pliku. Bezpośrednio nie ma możliwości zastosowania wyszukiwania binarnego - potrzebna jest więc dodatkowa struktura danych wykorzystująca posortowanie danych (struktura indeksowa - temat ten zostanie omówiony na kolejnym wykładzie).
W obu powyższych metodach, rekordy o tej samej wartości klucza lub zbliżonej znajdują się na tej samej stronie lub
tylko na kilku stronach dyskowych (w pierwszej metodzie nawet na sąsiednich).
Jest to istotne przy wyszukiwaniu, gdyż wyznaczenie wszystkich rekordów o danej
wartości klucza wyszukiwania (lub o wartości zbliżonej) wymaga sprowadzenia tylko kilku
stron, a nie dla każdego rekordu - osobnej strony.
Plik jest kolekcją segmentów (ang. bucket) rekordów. Segment jest to strona główna plus zero lub więcej stron nadmiarowych alokowanych do segmentu w razie potrzeby. Przydział rekordu do segmentu odbywa się w oparciu o wartość funkcji nazywanej funkcją haszującą (mieszającą) zastosowanej do klucza wyszukiwania rekordu, którym jest jedno lub więcej pól rekordu. Mianowicie:
Rys. 8.12 Plik haszowany
Przy tej metodzie, rekordy o tej samej wartości klucza wyszukiwania znajdują się na tej samej stronie lub tylko na kilku stronach dyskowych. Jest to istotne przy wyszukiwaniu, gdyż wyznaczenie wszystkich rekordów o danej wartości klucza wyszukiwania wymaga sprowadzenia tylko kilku stron, a nie dla każdego rekordu osobnej strony.
Organizacja pliku haszowanego jest użyteczna przy wyborze rekordu z pliku w oparciu o wartość lub wartości pewnych pól rekordu np. przy wykonywaniu zapytania
SELECT * FROM Emp e WHERE e.Ename=:Nazwisko;
Natomiast organizacja rekordów w pliku haszowanym nie zachowuje kolejności względem wartości klucza wyszukiwania.
Zastosowanie jednej organizacji rekordów w pliku zazwyczaj nie wystarcza w
aplikacjach baz danych, w których wyszukiwanie odbywa się względem wartości
różnych kluczy wyszukiwania. Rozwiązanie tego problemu polega na
skorzystaniu z osobnych struktur indeksowych. Ich studiowanie rozpocznie się na następnym wykładzie.
W wykładzie tym czytelnik poznał podstawy fizycznego modelu bazy danych opartego na pojęciach pliku, strony, rekordu i buforu danych. Treścią kolejnych wykładów będą zasady funkcjonowania SZBD na gruncie przedstawionego modelu.
Podstawowe dwa moduły niskiego poziomu zasłaniające moduły wysokiego poziomu od szczegółów implementacyjnych modelu fizycznego to moduł zarządzania miejscem na dysku (Disk Space Manager) oraz moduł zarządzania buforami w pamięci RAM (Buffer Manager).
plik - reprezentacja tabeli w modelu fizycznym bazy danych.
rekord - fizyczna reprezentacja wiersza.
pole - reprezentacja wartości w kolumnie (elementu wiersza) w modelu fizycznym bazy danych.
klucz wyszukiwania (rekordu) - wybrane pola rekordu, względem których ma odbywać się wyszukiwanie. Może być wiele kluczy wyszukiwania rekordu.
strona (blok) - fizyczna jednostka przechowywania danych na dysku. Dane są przesyłane między pamięcią wewnętrzną i dyskiem stronami. Na jednej stronie mieści się pewna liczba rekordów.
bufor danych - miejsce w pamięci RAM, do którego sprowadza się stronę z dysku.
LRU - podstawowa strategia zastępowania stron w puli buforów danych; mianowicie zastępuje się stronę, która najdłużej pozostawała nie używana.
plik nieuporządkowany (heap) - plik, w którym rekordy są przechowywane na stronach w dowolnym porządku.
plik posortowany - plik, w którym rekordy są zapisywane zgodnie z porządkiem względem pewnego klucza wyszukiwania rekordu.
plik haszowany - plik, który jest kolekcją segmentów. Podział rekordów na segmenty odbywa się w oparciu o wartość funkcji, nazywanej funkcją haszującą, zastosowaną do klucza rekordu.
funkcja haszująca - funkcja, która wartościom klucza wyszukiwania, przyporządkowuje adres segmentu w pliku haszowanym.
Nie ma zadań do tego wykładu.