Baza danych od środka. Analiza działania rozproszonych systemów danych - ebook

W ciągu ostatnich 15 lat powstało tak wiele baz danych i narzędzi, że łatwo się pogubić, jeśli próbuje się zrozumieć przypadki użycia, szczegóły i specyfiki. Większość opracowań na temat systemów baz danych nie opisuje implementacji mechanizmu pamięci masowej. Tymczasem znajomość tych wewnętrznych aspektów jest bardzo ważna dla programistów, inżynierów, architektów i menedżerów.

Aby wybrać odpowiednie narzędzie do pracy, musisz zrozumieć idee i algorytmy stojące za ich projektem.

Michael Klishin, współpracownik RabbitMQ

Ta książka ułatwi Ci zgłębienie koncepcji kryjących się za działaniem nowoczesnych baz danych. Dzięki niej zrozumiesz, w jaki sposób struktury dyskowe różnią się od tych w pamięci i jak działają algorytmy efektywnego utrzymywania struktur B drzewa na dysku. Poznasz implementacje pamięci masowej o strukturze dziennika. Znajdziesz tu również wyjaśnienie zasad organizacji węzłów w klaster baz danych i specyfiki środowisk rozproszonych. Dowiesz się, jak algorytmy rozproszone poprawiają wydajność i stabilność systemu i jak uzyskać ostateczną spójność danych. Ponadto w książce zaprezentowano koncepcje antyentropii i plotek, służące do zapewniania zbieżności i rozpowszechniania danych, a także mechanizm transakcji utrzymujący spójność logiczną bazy.

Najważniejsze zagadnienia:

• klasyfikacja i taksonomia pamięci masowej
• silniki pamięci masowej oparte na B-drzewie i niezmienna struktura dziennika
• struktura plików bazy danych
• pamięć podręczna stron i pule buforów
• systemy rozproszone: złożone wzorce komunikacji węzłów i procesów
• klastry baz danych

Obowiązkowa lektura dla każdego, kto korzysta z jakiejkolwiek bazy danych!

Nate McCall, przewodniczący PMC

Przedmowa

CZĘŚĆ I. Mechanizmy pamięci masowej

1. Wprowadzenie i ogólny zarys

• Architektura DBMS
• Systemy DBMS oparte na pamięci kontra systemy oparte na dyskach
  • Trwałość w magazynach opartych na pamięci
• Kolumnowe i wierszowe systemy DBMS
  • Wierszowy układ danych
  • Kolumnowy układ danych
  • Rozróżnienia i optymalizacje
  • Magazyny z szerokimi kolumnami
• Pliki danych i pliki indeksowe
  • Pliki danych
  • Pliki indeksowe
  • Indeks główny jako pośrednik
• Buforowanie, niezmienność i porządkowanie
• Podsumowanie

2. Podstawy B-drzew

• Drzewa wyszukiwania binarnego
  • Równoważenie drzewa
  • Drzewa dla pamięci masowych opartych na dyskach
• Struktury oparte na dyskach
  • Dyski twarde
  • Dyski półprzewodnikowe
  • Struktury na dysku
• Wszechobecne B-drzewa
  • Hierarchia B-drzewa
  • Klucze oddzielające
  • Złożoność przeszukiwania B-drzewa
  • Algorytm przeszukiwania B-drzewa
  • Liczenie kluczy
  • Dzielenie węzłów B-drzewa
  • Scalanie węzłów B-drzewa
• Podsumowanie

3. Formaty plików

• Motywacje
• Kodowanie binarne
  • Typy podstawowe
  • Ciągi znaków i dane o zmiennym rozmiarze
  • Dane upakowane bitowo: wartości logiczne, wyliczenia i flagi
• Zasady ogólne
• Struktura strony
• Strony podzielone na obszary
• Układ komórek
• Łączenie komórek w strony podzielone na obszary
• Zarządzanie danymi o zmiennym rozmiarze
• Wersjonowanie
• Sumy kontrolne
• Podsumowanie

4. Implementowanie B-drzew

• Nagłówek strony
  • Magiczne liczby
  • Powiązania między rodzeństwem
  • Skrajne prawe wskaźniki
  • Najwyższe klucze węzłów
  • Strony przepełnienia
• Wyszukiwanie binarne
  • Wyszukiwanie binarne ze wskaźnikami kierunku
• Propagowanie podziałów i scaleń
  • Okruszki
• Przywracanie równowagi
• Dołączanie tylko z prawej strony
  • Ładowanie masowe
• Kompresja
• Odkurzanie i konserwacja
  • Fragmentacja spowodowana aktualizacjami i usunięciami
  • Defragmentacja stron
• Podsumowanie

5. Przetwarzanie transakcji i przywracanie poprzedniego stanu

• Zarządzanie buforami
  • Semantyka buforowania
  • Zwalnianie pamięci podręcznej
  • Blokowanie stron w pamięci podręcznej
  • Zastępowanie stron
• Przywracanie poprzedniego stanu
  • Semantyka dziennika
  • Działanie a dziennik danych
  • Zasady kradzieży i wymuszania
  • ARIES
• Kontrola współbieżności
  • Serializowalność
  • Izolacja transakcji
  • Anomalie odczytu i zapisu
  • Poziomy izolacji
  • Optymistyczna kontrola współbieżności
  • Wielowersyjna kontrola współbieżności
  • Pesymistyczna kontrola współbieżności
  • Kontrola współbieżności oparta na blokadach
• Podsumowanie

6. Odmiany B-drzewa

• Kopiowanie przy zapisie
  • Implementowanie kopiowania przy zapisie: LMDB
• Abstrakcja aktualizacji węzłów
• Leniwe B-drzewa
  • WiredTiger
  • Drzewo z leniwą adaptacją
• Drzewa FD
  • Kaskadowanie ułamkowe
  • Przebiegi logarytmiczne
• Drzewa Bw
  • Łańcuchy aktualizacji
  • Ograniczanie współbieżności za pomocą porównywania i zamiany
  • Modyfikacje strukturalne
  • Konsolidacja i zbieranie śmieci
• B-drzewa nieświadome pamięci podręcznej
  • Układ van Emde Boasa
• Podsumowanie

7. Pamięć masowa o strukturze dziennika

• Drzewa LSM
  • Struktura drzewa LSM
  • Aktualizacje i usuwanie
  • Wyszukiwanie w drzewie LSM
  • Iteracja przez scalanie
  • Uzgadnianie
  • Konserwacja w drzewach LSM
• Odczyt, zapis i wzmocnienie przestrzenne
  • Hipoteza RUM
• Szczegóły implementacji
  • Posortowane tabele ciągów
  • Filtry Blooma
  • Lista z przeskokami
  • Dostęp do dysku
  • Kompresja
• Nieuporządkowana pamięć masowa LSM
  • Bitcask
  • WiscKey
• Współbieżność w drzewach LSM
• Układanie dzienników w stos
  • Warstwa translacji pamięci flash
  • Rejestrowanie systemu plików
• LLAMA i uważne układanie na stosie
  • Dyski SSD z otwartym kanałem
• Podsumowanie

Podsumowanie części I

CZĘŚĆ II. Systemy rozproszone

8. Wprowadzenie i przegląd

• Współbieżne wykonywanie
  • Współdzielony stan w systemie rozproszonym
• Błędy obliczeń rozproszonych
  • Przetwarzanie
  • Zegary i czas
  • Spójność stanu
  • Wykonywanie lokalne i zdalne
  • Potrzeba radzenia sobie z awariami
  • Partycje sieciowe i częściowe awarie
  • Awarie kaskadowe
• Abstrakcje systemów rozproszonych
  • Łącza
• Problem dwóch generałów
• Niemożność FLP
• Synchronizacja systemu
• Modele awarii
  • Awaria systemu
  • Błędy pominięcia
  • Przypadkowe błędy
  • Radzenie sobie z awariami
• Podsumowanie

9. Wykrywanie awarii

• Puls i pingi
  • Detektor awarii bez limitu czasu
  • Zewnętrzne sprawdzanie pulsu
• Detektor awarii Phi-Accural
• Plotki i wykrywanie awarii
• Odwracanie problemu wykrywania awarii
• Podsumowanie

10. Wybór lidera

• Algorytm tyrana
• Przełączanie awaryjne na następny w kolejności proces
• Zwykła optymalizacja kandydata
• Algorytm zapraszania
• Algorytm pierścieniowy
• Podsumowanie

11. Replikacja i spójność

• Osiąganie dostępności
• Niesławny CAP
  • Ostrożne korzystanie z CAP
  • Zbiór i uzysk
• Pamięć współdzielona
• Porządkowanie
• Modele spójności
  • Ścisła spójność
  • Linearyzowalność
  • Spójność sekwencyjna
  • Spójność przyczynowo-skutkowa
• Modele sesji
• Ostateczna spójność
• Dostrajana spójność
• Repliki świadków
• Silna ostateczna spójność i typy CRDT
• Podsumowanie

12. Antyentropia i rozpowszechnianie

• Naprawa odczytu
• Skrócone odczyty
• Przekazanie ze wskazówką
• Drzewa Merkle'a
• Wektory wersji bitmapowej
• Rozpowszechnianie plotek
  • Mechanika plotki
  • Sieci nakładkowe
  • Plotki hybrydowe
  • Widoki częściowe
• Podsumowanie

13. Transakcje rozproszone

• Sprawianie, aby działania wyglądały na niepodzielne
• Zatwierdzanie dwufazowe
  • Awarie w grupach w 2PC
  • Awarie koordynatora w 2PC
• Zatwierdzanie trójfazowe
  • Awarie koordynatora w 3PC
• Transakcje rozproszone z użyciem Calvina
• Transakcje rozproszone z użyciem Spannera
• Podział bazy danych na partycje
  • Spójne obliczanie skrótów
• Transakcje rozproszone z rozprzestrzenianiem
• Unikanie koordynacji
• Podsumowanie

14. Konsensus

• Rozgłaszanie
• Niepodzielne rozgłaszanie
  • Synchroniczność wirtualna
  • Niepodzielne rozgłoszenie Zookeeper (ZAB)
• Paxos
  • Algorytm Paxos
  • Kworum w Paxosie
  • Scenariusze awarii
  • Multi-Paxos
  • Fast Paxos
  • Egalitarian Paxos
  • Flexible Paxos
  • Uogólnione rozwiązanie konsensusu
• Raft
  • Rola lidera w algorytmie Raft
  • Scenariusze awarii
• Konsensus bizantyński
  • Algorytm PBFT
  • Odzyskiwanie i punkty kontrolne
• Podsumowanie

Podsumowanie części II

Bibliografia