Szczegóły ebooka

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

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

Alex Petrov

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

  • Tytuł: Baza danych od środka. Analiza działania rozproszonych systemów danych
  • Autor: Alex Petrov
  • Tytuł oryginału: Database Internals: A Deep Dive into How Distributed Data Systems Work
  • Tłumaczenie: Małgorzata Dąbkowska-Kowalik, Witold Sikorski
  • ISBN: 978-83-289-1333-2, 9788328913332
  • Data wydania: 2024-09-17
  • Format: Ebook
  • Identyfikator pozycji: badaod
  • Wydawca: Helion
  • Kategoria wiekowa: 16+