Hierarchia pamięci

• Pamięć podręczna (cache)
• Pamięć wirtualna
• Pamięć drugorzędowa
• Pamięć trzeciorzędowa

Pamięć główna
Każdy bajt może być uzyskany w tym samym okresie czasu. Typowy czas dostępy waha się od 10 – 100 nanosekund. Wszystko co dzieje się w komputerze – wykonywanie instrukcji, manipulacja danymi, etc. odbywa się za pośrednictwem pamięci głównej.

Pamięć wirtualna
Większość maszyn używa 32-bitowej przestrzeni adresowej – czyli mamy 2^32 adresów – 4 bilony różnych adresów. Ponieważ każdy bajt ma własny adres, to typowa pojemność pamięci wirtualnej wynosi 4 GB. Ze względu na swoje duże rozmiary przechowywana jest na dyskach – podzielonych na bloki – pamięć ma strony – tego samego rozmiaru. Jak to jest wykorzystywane w systemach baz danych? Zarządzają one swoimi danymi przez pamięć wirtualną – system operacyjny dostarcza im potrzebnych danych za pomocą mechanizmu stronicowania. „Pamięciowe systemy baz danych” – jak większość aplikacji – są w pełni użyteczne jeśli dane są małe na tyle, że nie ma potrzeby wymiany danych. Przy 32-bitowej przestrzeni adresowej aplikacje mogą trzymać na raz nie więcej niż 4 GB danych. Dlatego wielkie systemy zarządzania baz danych trzymają dane bezpośrednio na dyskach – ograniczone są tylko pojemnością użytego dysku.

Pamięć drugorzędowa
Wolniejsza, ale bardziej pojemna. Najczęściej używane są dyski magnetyczne, jednak czasem zdarzają się również optyczne i magneto-optyczne. Dyski są używane do przechowywania stron pamięci wirtualnej używanych przez aplikacje. Pliki są przenoszone pomiędzy pamięcią a dyskiem w blokach, pod kontrolą o.s. lub db s. Czytanie pliku odbywa się za pośrednictwem buforowanie, czyli czytania pliku fragmentami, blokami. Bufor znajduje się w pamięci głównej. Po skonsumowaniu zawartości przez aplikację, do bufora kopiowany jest kolejny fragment pliku. DBMS zarządza blokami dysku samodzielnie, rzadziej za pomocą o.s.

Pamięć trzeciorzędowa
W przypadku dużych baz danych, przechowujących terabajty danych zwykła pamięć drugorzędowa nie wystarcza. Z pomocą przychodzi pamięć trzeciorzędowa. Charakteryzuje się nieco wyższym czasem dostępu (czytania / pisania) niż pamięć 2-go rzędowa. Ale o ile przy pamięciach 2-go rzędowych czas dostępu jest mniej więcej taki sam dla wszystkich danych, czas dostępu pamięci 3-cio rzędowych rożni się, w zależności jak blisko jest do punktu czytania / pisania. Wyróżniamy:

• Tape Storage – najstarszy i najprostszy rodzaj. Dane nagrywane są na taśmach przechowywanych na półkach. Operatorem jest człowiek, który musi odnaleźć i zamontować właściwą taśmę. Szukanie konkretnych danych dalej przebiega w następujący sposób: taśma jest przewijana do danej lokalizacji, znalezione dane zostają skopiowane na nośnik pamięci drugorzędowej lub do pamięci głównej. Zapisywanie – w analogiczny sposób.
• Optical Juke Boxes – “szafa grająca” złożona z półek, na których znajdują się dyski optyczne – CDROM. Mechaniczne ramię odnajduje właściwą płytę z danymi i dostarcza głowicy czytającej, po czym dane są kopiowane na dysk twardy.
• Tape Silos – ulepszona wersja Tape Storage – jednostka wielości pokoju, zbudowana z półek wypełnionych taśmami. Posiada mechaniczne ramię, wyszukujące odpowiednią taśmę. O wiele szybsza niż Tape Storage.

Trwałe i ulotne przechowywanie (pamięć)

Definicje powyższych pojęć są intuicyjne: pamięci ulotne nie pamiętają co przechowują po wyłączeniu zasilania, w przeciwieństwie do pamięci trwałych. Rozważania na ten temat są bardzo ważne, ponieważ jedną z podstawowych własności DBMS jest możliwość zachowywania danych nawet w przypadku braków zasilania. Urządzenia magnetyczne, taśmy są trwałe, podobnie jak optyczne (CDROM) z tą różnicą, że CDROMy nie można powtórnie zapisywać. Generalnie pamięci 2-go i 3-cio rzędowe są trwałe. Pamięć główna jest przykładem pamięci ulotnych. DBMS, który działa na maszynie z ulotną pamięcią musi robić kopię zapasową na dysku, zanim zmiana dotrze do bazy – dlatego wszelkie zapytania, modyfikacje wymagają dużej liczby operacji I/O. Alternatywą są pamięci FLASH.

Pamięć drugorzędowa

Dyski

Używanie pamięci drugorzędowej jest jedną z podstawowych charakterystyk DBMS. A pamięci drugorzędowe prawie w całości bazują na dyskach magnetycznych.

Mechanizmy dysków
Jak jest zbudowany dysk? Składa się z talerzy złożonych z dwóch powierzchni, na których zapisane są bity. Bity organizuje się w ścieżki w postaci koncentrycznych okręgów. Następnie ścieżki organizowane są w sektory (kawałki okręgów oddzielone od siebie lukami [gaps]). Sektory są atomowymi jednostkami, jeśli chodzi o czytanie i pisanie.

Kontroler dysku
Dyski sterowane są za pośrednictwem kontrolera. Jego zadaniem jest:

• kontrola mechanizmu przesuwającego głowice do właściwych pozycji. Przy ustalonej pozycji jedna ścieżka z każdej powierzchni jest pod głowicą i może być odczytana lub nadpisana. Ścieżki, które są pod głowicami w tym samym czasie tworzą cylinder.
• wybór powierzchni do czytania lub zapisu, wybór ścieżki i sektora
• odpowiedzialny za wiedzę, kiedy w czasie obracania talerzy, żądany sektor zacznie się pojawiać pod głowicą,
• transfer czytanych/zapisywanych bitów z/do pamięci głównej.

Charakterystyka przechowywania dyskowego

• prędkość obrotowa,
• liczba talerzy,
• liczba ścieżek na powierzchnię,
• liczba bajtów na ścieżkę,

Charakterystyka dostępu do dysku
Analizując DBMS musimy dowiedzieć się nie tylko jak dane są przechowywane, ale również w jaki sposób przebiega ich manipulacja. Ponieważ wszystkie wyliczenia mają miejsce w pamięci głównej, jedynym zadaniem dysku jest dostarczenie danych do pamięci. Dane są czytane blokami gdy:

• głowica przesunie się nad cylinder zawierający ścieżkę, na której znajduje się blok,
• sektory zawierające blok przesuną się pod głowicą w czasie obracania talerzy.

• czasu potrzebnego procesorowi i kontrolerowi aby przetworzyć zamówienie,
• czasu przeszukiwania (umieszczenie głowicy nad cylindrem),
• opóźnienia obrotowego (obrót, aby 1-szy sektor znalazł się pod głowicą) – średnio, pół obrotu,
• czasu transmisji (obrót wszystkich żądanych sektorów i luk pomiędzy nimi wokół głowicy).

• wczytać blok do pamięci głównej,
• przeprowadzić wszystkie pożądane zmiany,
• zapisać nową zawartość bloku na dysk,
• zweryfikować dane, w razie potrzeby.

Efektywne wykorzystywanie pamięci 2-rzędowej.

Two Phase, Multiway Merge Sort (Sortowanie zewnętrzne)
Jednym z algorytmów, które musiały się zmienić pod wpływem takiego modelu (I/O) jest klasyczny Merge Sort, którego pochodna jest bardzo popularnym algorytmem sortującym w aplikacjach bazodanowych. Składa się z dwóch faz:

• faza 1: posortuj kawałki danych (rozmiar = dostępna wielkość pamięci operacyjnej) – czyli każdy rekord jest częścią posortowanej listy. Może wystąpić wiele posortowanych list.
• faza 2: połącz wszystkie posortowane listy w jedną.

• wypełniamy dostępną pamięć blokami z sortowanej relacji,
• sortujemy i zapisujemy w nowym miejscu na dysku.

Faza 2 polega na łączeniu wygenerowanych list. Można łączyć je parami, tak jak w klasycznym Merge Sort. Wymaga to czytania wszystkich danych 2logn razy, przy n listach. Lepszym rozwiązaniem jest wczytanie po jednym bloku, z każdej listy do bufora, znajdującego się w pamięci głównej. Dla małych relacji (liczba podlist nie jest astronomiczna) jest to b.dobry sposób. Listę wynikową zapisujemy w buforze wyjściowym według zasady:

• znajdź najmniejszy element z 1 –szych elementów,
• dołącz znaleziony na pierwsze wolne miejsce w buforze wynikowym,
• jeśli bufor się przepełnia – zapisz zawartość na dysku i ponownie zainicjuj bufor w pamięci,
• jeśli blok, z którego pochodził dołączony element wyczerpał się, wczytaj kolejny blok z tej samej podlisty – jeśli nie ma już nowych bloków zostaw bufor pusty i nie rozważaj dalej tej listy.

Przyśpieszanie dostępu do pamięci 2-go rzędowej

• układanie bloków, które są udostępniane razem na tym samym cylindrze, (zyskujemy czas szukania i ewentualne opóźnienie obrotowe)
• dzielenie danych na kilka mniejszych dysków,(w ten sposób mamy więcej głowic czytających i zapisujących – zwiększamy w ten sposób liczbę czytanych/zapisywanych bloków w jednostce czasu)
• dublowanie dysku – umieszczanie na dysku kilku kopii jego zawartości,
• użycie algorytmu planowania, aby wybrać najwłaściwszą kolejność obsługi żądań,
• podwójne buforowanie – wcześniejsze czytanie bloków do pamięci i późniejsze ich wykorzystywanie.

Organizowanie danych w cylindrach

• Za: dobre dla aplikacji, w których dostęp może być przewidziany z wyprzedzeniem, tylko jeden proces używa dysku,
• Przeciw: nie użyteczne, gdy nie wiadomo jak będą dostarczane dane.

Użycie wielu dysków

• Za: zwiększa możliwości obsługi żądań pisania/czytania,
• Problem: żądania czytania lub pisania dla jednego dysku nie mogą być realizowane w jednym czasie.
• Przeciw: koszt kilku dysków.

Dublowanie (Mirroring)

• Za: zwiększa możliwości obsługi żądań pisania/czytania, nie ma problemu obsługi żądań z tego samego dysku, działa nawet gdy jeden z dysków padnie – obraz jest na innym.
• Przeciw: płacimy za 2, 3 dyski a mamy pojemność jednego.

Planowanie algorytmem windowym (elevator alg.)

• Za: skraca średni czas pisania/czytania bloku, gdy dostęp do bloków jest losowy,
• Problem: jest efektywny, gdy jest dużo czekających zamówień, zatem średnie opóźnienie dla zgłaszającego procesu jest duże.

Prefetching (podwójne buforowanie)

• zapisywać posortowane podlisty na całych, sąsiednich cylindrach, gdzie kolejnymi blokami ścieżek są kolejne bloki listy,
• czytać całe ścieżki lub cylindry za każdym razem, gdy chcemy kolejne rekordy z danej listy.

• Za: przyśpiesza dostęp, gdy potrzebne bloki są znane, ale czas żądań zależy od danych, jak w fazie 2 TPMMS.
• Przeciw: Wymaga dodatkowej pamięci, nie użyteczne, gdy dostęp jest losowy.

Disk Failures

• najbardziej popularną formą błędu jest nieregularny błąd (intermittent failure) – próba czytania lub pisanie sektora nie powiodła się, ale po kilku kolejnych próbach osiągamy sukces.
• Bardziej poważną formą błędu jest media decay –jeden lub więcej bitów ulega trwałemu zniszczeniu, staje się niemożliwym do zapisania / odczytania bez względu na liczbę podjętych prób.
• Kolejna forma to błąd zapisu – nie możemy ani zapisać wartości, ani odczytać poprzednio zapisanej w tym sektorze. Prawdopodobną przyczyną tego była awaria zasilania podczas zapisywania.
• Najbardziej poważnym błędem jest disk crash – cały dysk staje się niedostępny, nagle i trwale.

Intermittent failures
Zwykle sektory na dyskach mają pewne zbędne bity – sumy kontrolne. Dzięki nim wiemy, czy to co czytaliśmy z sektora jest poprawne czy nie. Podobnie jest z pisaniem. Zwykłe funkcja czytająca dane zwraca parę (w,s), gdzie w – dane, s – status. Przy błędach tej klasy, możemy trzymać status „bad” kilka razy, ale w końcu dostaniemy „good”. Jednak czasami możemy zostać oszukani. Prawdopodobieństwo jest jednak niewielkie. Przy zapisywaniu możemy próbować czytać sektor po zapisie i weryfikować, czy proces przebiegł pomyślnie.

Sumy kontrolne
Każdy sektor ma kilka dodatkowych bitów, zwanych sumami kontrolnymi – zbiór bitów zależnych od danych przechowywanych w tym sektorze. Jeśli podczas czytania odkrywamy, że suma kontrolna się nie zgadza, zgłaszamy status „bad”. W p.p. zgłaszamy „good”. Mogą oczywiście wystąpić przekłamania, ale używając dostatecznie długiej sumy (liczba bitów) redukujemy ten problem.
Prosta forma sum kontrolnych bazuje na parzystości. Jeśli jest nieparzysta liczba 1-nek, mówimy że bit parzystości to 1, 0 w p.p. Gdy zapisujemy sektor można liczyć bit parzystości i dołączać na koniec sekwencji bitów. Zatem, każdy sektor będzie miał bit parzystości 0.

Stable Storage
Sumy kontrolne pomagają nam wykryć błąd – ale nie umożliwiają korekty. Dlatego jest stabilne przechowywanie, które polega na parowaniu sektorów. Każda para reprezentuje zawartość jednego sektora X. Para składa się z lewej i prawej kopii: XL i XR. Zakładamy, że kopie są uzupełnione o bity parzystości, uniemożliwiające przekłamania. Zakładamy, że jeśli funkcja czytająca zwraca (w,good) dla XL i XR to w jest prawdziwą zawartością sektora.
Pisanie odbywa się w następujący sposób:

• zapisz wartość X w XL. Sprawdź status i jeśli jest „bad” powtórz zapisywanie. Jeśli po kilku próbach ciągle mamy status „bad” stwierdzamy błąd nośnika (media failure) w sektorze. Co zrobić? Podmienić uszkodzony sektor zapasowym.
• powtórz to samo dla XR.

• aby dostać wartość X, odczytaj XL. Jeśli zwrócony zostanie status „bad”, powtórz operację kilka razy. Jeśli dostaniemy status „good” to ok.
• jeśli nie można czytać XL, powtórz dla XR.

Error Handling Capabilities of Stable Storage

• Media failures – jeśli po zapisaniu X w XL i XR jeden z nich staje się trwałe niedostępny, możemy dostać wartość X od drugiego. Jeśli XR padł, a XL nie, to czytamy XL, a na XR nie zwracamy uwagi. Jeśli tylko XL padło, to czytając dostaniemy status „bad”. Idziemy do drugiego kroku, czyli czytamy z XR. Jeśli oba zawiodły – mamy problem.
• Write failure – przypuśćmy, że w czasie zapisywanie X wyłączyli zasilanie. Stracimy X w pamięci oraz kopia X na dysku zostanie prawdopodobnie przekłamana (np. pół sektora nowe, pół stare). Po włączeniu zasilania i sprawdzeniu XL i XR jesteśmy w stanie uzyskać starą lub nową wartość X. Mamy 2 przypadki:
  • błąd wystąpił w czasie zapisywania XL. Powinniśmy odkryć, że status XL jest „bad”. Nie zajmowaliśmy się XR, więc jest tam poprawna stara wartość X. Kopiujemy do XL z XR.
  • bąd wystąpił po zapisie XL. Czytamy wartość XL i aktualizujemy XR.

Recovery from Disk Crashes

RAID level 1

Bloki parzystości (Parity blocks) RAID level 4

Przykład

Czytanie może odbywać się zwyczajnie. Załóżmy, że mamy dyski 1,2,3 i 4 – nadmiarowy. Czytamy z 1 blok. W tym samym czasie możemy przeczytać dane z tego samego dysku wykorzystując pozostałe, czyli 2 + 3 + 4 modulo 2 po każdym bicie.
Zapisywanie – na dysk z danymi + modyfikacja odpowiedniego bloku na dysku nadmiarowym. Można to zrobić za pomocą 4 operacji I/O:

• czytamy starą wartość zmienianego bloku,
• czytamy odpowiadający blok z dysku nadmiarowego,
• zapisujemy nowy blok na dysku,
• obliczamy i zapisujemy blok na dysku nadmiarowym.

Przykład

Zobaczmy co stanie się, gdy jeden z dysków ulegnie awarii. Jeśli będzie to dysk nadmiarowy, to zamieniamy na nowy dysk i obliczamy sumy. Jeśli padnie dysk z danymi, zmieniamy na nowy i obliczamy jego dane na podstawie pozostałych. Jak? Przyświeca zasada: Każdy bit jest sumą modulo 2 odpowiednich bitów ze wszystkich dysków.

RAID level 5

Przykład

Jak poradzić sobie z wieloma, jednoczesnymi awariami dysków? Odp: RAID level 6

• występuje każda kombinacja trzy elementowej kolumny z 0 i 1, z wyjątkiem 0 0 0.
• kolumny dysków nadmiarowych mają tylko jedną 1,
• kolumny dysków z danymi mają co najmniej dwie 1.

Odzyskiwanie
Załóżmy, że mamy awarię dwóch dysków: a i b. Ponieważ wszystkie kolumny macierzy są różne, można znaleźć taki wiersz r w którym wartości dla a i b są różne. Załóżmy, że a w wierszu r ma 0, a b 1. Możemy policzyć dane z b dodając do siebie modulo 2 wszystkie inne dyski, które mają 1 w wierszu r. Teraz odtwarzamy zawartość dysku a. Szukamy wiersza, w którym w kolumnie a jest 1. Zawartość dysku a to suma modulo 2 wszystkich innych dysków mających 1 w tym wierszu.