Rozproszone systemy baz danych 101
Lub rozproszone bazy danych - co tak naprawdę oznacza „ skalowanie stron internetowych ”?
Rozproszone systemy baz danych są złożonymi stworzeniami i występują w wielu różnych odmianach. Jeśli zagłębię się w głąb moich słabo zapamiętanych badań na tym uniwersytecie, postaram się wyjaśnić niektóre kluczowe problemy inżynieryjne związane z budowaniem systemu rozproszonej bazy danych.
Najpierw trochę terminologii
Właściwości ACID (Atomowość, Spójność, Izolacja i Trwałość): Są to kluczowe niezmienniki, które należy egzekwować, aby transakcja mogła zostać niezawodnie zrealizowana bez powodowania niepożądanych skutków ubocznych.
Atomowość wymaga, aby transakcja została zakończona lub całkowicie wycofana. Częściowo zakończone transakcje nigdy nie powinny być widoczne, a system musi być zbudowany w taki sposób, aby temu zapobiec.
Spójność wymaga, aby transakcja nigdy nie naruszała niezmienników (takich jak deklaratywna integralność referencyjna) gwarantowanych przez schemat bazy danych. Na przykład, jeśli istnieje klucz obcy, wstawienie rekordu potomnego z czcią dla nieistniejącego rodzica powinno być niemożliwe.
Izolacja wymaga, aby transakcje nie kolidowały ze sobą. System powinien gwarantować takie same wyniki, jeśli transakcje są wykonywane równolegle lub sekwencyjnie. W praktyce większość produktów RDBMS umożliwia tryby, które kompromisują izolację z wydajnością.
Trwałość wymaga, aby po zatwierdzeniu transakcja pozostała w trwałym magazynie w sposób odporny na awarie sprzętu lub oprogramowania.
Poniżej wyjaśnię niektóre techniczne przeszkody, jakie te wymagania występują w systemach rozproszonych.
Architektura dysku współdzielonego: architektura, w której wszystkie węzły przetwarzania w klastrze mają dostęp do całej pamięci. Może to stanowić centralne wąskie gardło w zakresie dostępu do danych. Przykładem systemu z dyskami współdzielonymi jest Oracle RAC lub Exadata .
Architektura Shared Nothing: architektura, w której węzły przetwarzające w klastrze mają lokalną pamięć, która nie jest widoczna dla innych węzłów klastra. Przykładami systemów typu „nic wspólnego” są Teradata i Netezza .
Architektura pamięci współużytkowanej: architektura, w której wiele procesorów (lub węzłów) może uzyskać dostęp do wspólnej puli pamięci. Większość współczesnych serwerów ma pamięć współdzieloną. Pamięć współdzielona ułatwia pewne operacje, takie jak pamięci podręczne lub operacje podstawowe synchronizacji atomowej, które są znacznie trudniejsze w systemach rozproszonych.
Synchronizacja: ogólny termin opisujący różne metody zapewniające spójny dostęp do współdzielonego zasobu przez wiele procesów lub wątków. Jest to o wiele trudniejsze w systemach rozproszonych niż w systemach pamięci współdzielonej, chociaż niektóre architektury sieciowe (np. BYNET firmy Teradata) miały operacje podstawowe synchronizacji w protokole sieciowym. Synchronizacja może również wymagać znacznego obciążenia.
Semi-Join: Prymityw używany do łączenia danych przechowywanych w dwóch różnych węzłach systemu rozproszonego. Zasadniczo składa się z wystarczającej ilości informacji o wierszach, aby połączyć, które są łączone w pakiety i przekazywane przez jeden węzeł do drugiego, aby rozwiązać połączenie. W przypadku dużego zapytania może to obejmować znaczny ruch sieciowy.
Ostateczna spójność: termin używany do opisania semantyki transakcji, która kompromituje natychmiastową aktualizację (spójność odczytów) we wszystkich węzłach systemu rozproszonego w celu zwiększenia wydajności (a tym samym większej przepustowości transakcji) podczas zapisu. Ostateczna spójność to efekt uboczny użycia replikacji kworum jako optymalizacji wydajności w celu przyspieszenia zatwierdzeń transakcji w rozproszonych bazach danych, w których wiele kopii danych jest przechowywanych w oddzielnych węzłach.
Algorytm Lamporta: algorytm do implementacji wzajemnego wykluczania (synchronizacji) między systemami bez pamięci współdzielonej. Zwykle wzajemne wykluczanie w systemie wymaga atomowej instrukcji odczytu-porównania-zapisu lub podobnej instrukcji typu zwykle praktycznego tylko w systemie pamięci współdzielonej. Istnieją inne algorytmy rozproszonej synchronizacji, ale Lamport był jednym z pierwszych i jest najbardziej znany. Podobnie jak większość rozproszonych mechanizmów synchronizacji, algorytm Lamporta jest silnie zależny od dokładnego synchronizacji czasu i zegara między węzłami klastra.
Dwufazowe zatwierdzenie (2PC): rodzina protokołów, które zapewniają, że aktualizacje bazy danych obejmujące wiele systemów fizycznych konsekwentnie zatwierdzają lub wycofują. Niezależnie od tego, czy 2PC jest używane w systemie, czy w wielu systemach za pośrednictwem menedżera transakcji, wiąże się to ze znacznymi kosztami.
W protokole zatwierdzania dwufazowego menedżer transakcji prosi węzły uczestniczące o zachowanie transakcji w taki sposób, aby mogły zagwarantować, że zostanie ona zatwierdzona, a następnie zasygnalizują ten status. Gdy wszystkie węzły zwrócą status „szczęśliwy”, sygnalizuje węzłom, że mają zatwierdzić. Transakcja jest nadal uważana za otwartą, dopóki wszystkie węzły nie wyślą odpowiedzi wskazującej, że zatwierdzenie zostało zakończone. Jeśli węzeł ulegnie awarii przed sygnalizowaniem zakończenia zatwierdzenia, menedżer transakcji ponownie prześle zapytanie do węzła po jego ponownym uruchomieniu, dopóki nie otrzyma pozytywnej odpowiedzi wskazującej, że transakcja została zatwierdzona.
Multi-Version Concurrency Control (MVCC): zarządzanie rywalizacją poprzez zapisywanie nowych wersji danych w innym miejscu i umożliwianie innym transakcjom zobaczenia starej wersji danych do momentu zatwierdzenia nowej wersji. Zmniejsza to rywalizację bazy danych kosztem dodatkowego ruchu zapisu w celu napisania nowej wersji, a następnie oznaczenia starej wersji jako przestarzałej.
Algorytm wyboru: systemy rozproszone obejmujące wiele węzłów są z natury mniej niezawodne niż pojedynczy system, ponieważ występuje więcej trybów awarii. W wielu przypadkach potrzebny jest pewien mechanizm, aby systemy klastrowe radziły sobie z awarią węzła. Algorytmy wyborcze to klasa algorytmów wykorzystywanych do wybierania linii odniesienia w celu koordynowania obliczeń rozproszonych w sytuacjach, w których węzeł „linii odniesienia” nie jest w 100% określony lub wiarygodny.
Partycjonowanie poziome: Tabela może być podzielona na wiele węzłów lub woluminów pamięci masowej według klucza. Umożliwia to podzielenie dużej ilości danych na mniejsze fragmenty i rozłożenie ich na węzły magazynowe.
Podział na fragmenty: zestaw danych może być podzielony poziomo na wiele fizycznych węzłów w architekturze typu „nic wspólnego”. W przypadku gdy partycjonowanie nie jest przezroczyste (tzn. Klient musi znać schemat partycji i ustalić, który węzeł jawnie zapytać), jest to nazywane dzieleniem na fragmenty. Niektóre systemy (np. Teradata) dzielą dane między węzłami, ale lokalizacja jest przezroczysta dla klienta; termin ten nie jest zwykle używany w połączeniu z tego typu systemem.
Spójne mieszanie: algorytm używany do przydzielania danych do partycji na podstawie klucza. Charakteryzuje się równomiernym rozmieszczeniem kluczy mieszających i możliwością elastycznego powiększania lub zmniejszania liczby wiader. Te atrybuty sprawiają, że jest przydatny do partycjonowania danych lub ładowania w klastrze węzłów, gdzie rozmiar może się dynamicznie zmieniać wraz z dodawaniem lub opuszczaniem klastra (być może z powodu awarii).
Replikacja wielostanowiskowa: technika umożliwiająca replikację zapisu w wielu węzłach w klastrze do innych węzłów. Ta technika ułatwia skalowanie, umożliwiając partycjonowanie lub dzielenie niektórych tabel między serwerami, a inne synchronizację w klastrze. Zapisy muszą być replikowane do wszystkich węzłów, w przeciwieństwie do kworum, więc zatwierdzenia transakcji są droższe w architekturze replikacji wieloskładnikowej niż w systemie replikacji kworum.
Przełącznik nieblokujący: przełącznik sieciowy, który wykorzystuje wewnętrzną równoległość sprzętową w celu osiągnięcia przepustowości proporcjonalnej do liczby portów bez wewnętrznych wąskich gardeł. Naiwna implementacja może korzystać z mechanizmu poprzeczki, ale ma złożoność O (N ^ 2) dla portów N, co ogranicza ją do mniejszych przełączników. Większe przełączniki mogą wykorzystywać bardziej złożoną topologię wewnętrzną zwaną nieblokującym minimalnym przełącznikiem rozpinającym, aby osiągnąć liniowe skalowanie przepustowości bez potrzeby stosowania sprzętu O (N ^ 2).
Tworzenie rozproszonego DBMS - jak trudne może być?
Kilka wyzwań technicznych sprawia, że jest to dość trudne w praktyce. Oprócz dodatkowej złożoności budowy systemu rozproszonego architekt rozproszonego DBMS musi przezwyciężyć pewne trudne problemy inżynieryjne.
Atomowość w systemach rozproszonych: jeśli dane aktualizowane przez transakcję są rozproszone na wiele węzłów, zatwierdzenie / wycofanie węzłów musi być skoordynowane. Daje to znaczny narzut w systemach z współdzielonym niczym. W systemach z dyskami współdzielonymi nie stanowi to większego problemu, ponieważ wszystkie węzły są widoczne dla wszystkich węzłów, więc pojedynczy węzeł może koordynować zatwierdzanie.
Spójność w systemach rozproszonych: aby wziąć podany wyżej przykład klucza obcego, system musi być w stanie ocenić spójny stan. Na przykład, jeśli element nadrzędny i podrzędny relacji klucza obcego może znajdować się w różnych węzłach, potrzebny jest jakiś rozproszony mechanizm blokujący, aby zapewnić, że nieaktualne informacje nie zostaną użyte do sprawdzenia poprawności transakcji. Jeśli nie jest to wymuszone, możesz mieć (na przykład) warunek wyścigu, w którym rodzic jest usuwany po zweryfikowaniu jego obecności przed zezwoleniem na wstawienie dziecka.
Opóźnione wymuszanie ograniczeń (tj. Oczekiwanie na zatwierdzenie w celu sprawdzenia poprawności DRI) wymaga blokady na czas trwania transakcji. Tego rodzaju blokowanie rozproszone wiąże się ze znacznym narzutem.
Jeśli przechowywanych jest wiele kopii danych (może to być konieczne w systemach typu nic nie współużytkowanego, aby uniknąć niepotrzebnego ruchu sieciowego z połączenia częściowego), wszystkie kopie danych muszą zostać zaktualizowane.
Izolacja w systemach rozproszonych: w przypadku gdy dane, których dotyczy transakcja, znajdują się w wielu węzłach systemowych, blokady i wersja (jeśli jest używane MVCC) muszą być zsynchronizowane między węzłami. Zagwarantowanie szeregowalności operacji, szczególnie na architekturach z dzielonym brakiem danych, w których mogą być przechowywane nadmiarowe kopie danych, wymaga rozproszonego mechanizmu synchronizacji, takiego jak algorytm Lamporta, który również wiąże się ze znacznym obciążeniem ruchu sieciowego.
Trwałość w systemach rozproszonych: W systemie z dyskami współdzielonymi kwestia trwałości jest zasadniczo taka sama jak w systemie z pamięcią współużytkowaną, z tym wyjątkiem, że rozproszone protokoły synchronizacji są nadal wymagane między węzłami. DBMS musi zapisywać do dziennika w dzienniku i konsekwentnie zapisywać dane. W systemie „nic wspólnego” może istnieć wiele kopii danych lub części danych przechowywanych w różnych węzłach. Potrzebny jest dwufazowy protokół zatwierdzania, aby upewnić się, że zatwierdzenie odbywa się poprawnie w węzłach. Powoduje to również znaczne koszty ogólne.
W systemie „nic wspólnego” utrata węzła może oznaczać, że dane nie są dostępne dla systemu. Aby zminimalizować te dane, można je replikować w więcej niż jednym węźle. Spójność w tej sytuacji oznacza, że dane muszą być replikowane do wszystkich węzłów, w których zwykle znajdują się. Może to spowodować znaczny narzut przy zapisach.
Jedną z powszechnych optymalizacji w systemach NoSQL jest użycie replikacji kworum i ostatecznej spójności, aby umożliwić leniwą replikację danych, jednocześnie gwarantując pewien poziom odporności danych, pisząc do kworum przed zgłoszeniem transakcji jako zatwierdzonej. Dane są następnie replikowane leniwie do innych węzłów, w których znajdują się kopie danych.
Należy pamiętać, że „ostateczna spójność” jest głównym kompromisem w zakresie spójności, który może nie być akceptowalny, jeśli dane muszą być przeglądane spójnie, jak tylko transakcja zostanie zatwierdzona. Na przykład w aplikacji finansowej zaktualizowane saldo powinno być dostępne natychmiast.
Systemy z dyskami współdzielonymi
System z dyskami współdzielonymi to taki, w którym wszystkie węzły mają dostęp do całej pamięci. Zatem obliczenia są niezależne od lokalizacji. Wiele platform DBMS może również pracować w tym trybie - Oracle RAC jest przykładem takiej architektury.
Współdzielone systemy dyskowe mogą być znacznie skalowane, ponieważ mogą obsługiwać relację M: M między węzłami magazynowania i węzłami przetwarzania. Sieć SAN może mieć wiele kontrolerów, a wiele serwerów może uruchamiać bazę danych. Architektury te mają przełącznik jako centralne wąskie gardło, ale przełączniki poprzeczne pozwalają temu przełącznikowi na dużą przepustowość. Pewne przetwarzanie może zostać odciążone na węzłach magazynowania (jak w przypadku Exadata Oracle), co może zmniejszyć ruch na przepustowości magazynu.
Chociaż teoretycznie przełącznik jest wąskim gardłem, dostępna przepustowość oznacza, że architektury współdzielonego dysku będą skalowane dość skutecznie do dużych wolumenów transakcji. Większość głównych architektur DBMS stosuje to podejście, ponieważ zapewnia „wystarczająco dobrą” skalowalność i wysoką niezawodność. W przypadku redundantnej architektury pamięci, takiej jak Fibre Channel, nie ma pojedynczego punktu awarii, ponieważ istnieją co najmniej dwie ścieżki między dowolnym węzłem przetwarzania a dowolnym węzłem pamięci.
Systemy typu Shared-Nothing
Systemy typu nic nie współużytkowane to systemy, w których przynajmniej niektóre dane są przechowywane lokalnie w węźle i nie są bezpośrednio widoczne dla innych węzłów. To usuwa wąskie gardło centralnego przełącznika, umożliwiając skalowanie bazy danych (przynajmniej teoretycznie) do liczby węzłów. Podział poziomy umożliwia podział danych między węzły; może to być przezroczyste dla klienta lub nie (patrz Sharding powyżej).
Ponieważ dane są z natury rozproszone, zapytanie może wymagać danych z więcej niż jednego węzła. Jeśli łączenie potrzebuje danych z różnych węzłów, operacja połowicznego łączenia służy do przesłania wystarczającej ilości danych do obsługi łączenia z jednego węzła do drugiego. Może to spowodować duży ruch sieciowy, więc optymalizacja dystrybucji danych może mieć duży wpływ na wydajność zapytań.
Często dane są replikowane między węzłami systemu współdzielonego-niczego, aby zmniejszyć konieczność łączenia częściowego. Działa to całkiem dobrze na urządzeniach hurtowni danych, ponieważ wymiary są zwykle o wiele rzędów wielkości mniejsze niż tabele faktów i można je łatwo powielać między węzłami. Zazwyczaj są one również ładowane partiami, więc narzut związany z replikacją nie stanowi większego problemu niż w przypadku aplikacji transakcyjnej.
Wewnętrzna równoległość architektury współdzielenia niczego sprawia, że są one dobrze dostosowane do rodzaju zapytań dotyczących skanowania / agregacji tabel charakterystycznych dla hurtowni danych. Ten rodzaj operacji można skalować prawie liniowo wraz z liczbą węzłów przetwarzających. Duże sprzężenia między węzłami zwykle powodują większe obciążenie, ponieważ operacje łączenia częściowego mogą generować duży ruch sieciowy.
Przenoszenie dużych woluminów danych jest mniej przydatne w aplikacjach przetwarzających transakcje, w których narzut związany z wieloma aktualizacjami sprawia, że ten typ architektury jest mniej atrakcyjny niż dysk udostępniony. Dlatego ten typ architektury nie jest powszechnie wykorzystywany w aplikacjach hurtowni danych.
Odłamki, replikacja kworum i ostateczna spójność
Replikacja kworum to narzędzie, w którym DBMS replikuje dane w celu zapewnienia wysokiej dostępności. Jest to przydatne w przypadku systemów przeznaczonych do pracy na tańszym sprzęcie towarowym, który nie ma wbudowanych funkcji wysokiej dostępności, takich jak SAN. W tego typu systemie dane są replikowane w wielu węzłach pamięci w celu zwiększenia wydajności odczytu i pamięci nadmiarowej, aby system był odporny na awarię sprzętową węzła.
Jednak replikacja zapisów do wszystkich węzłów to O (M x N) dla M węzłów i N zapisów. To powoduje, że zapisy są kosztowne, jeśli zapis musi zostać zreplikowany do wszystkich węzłów, zanim transakcja będzie mogła zatwierdzić. Replikacja kworum to kompromis, który pozwala na natychmiastową replikację zapisów do podzbioru węzłów, a następnie leniwe zapisanie do innych węzłów przez zadanie w tle. Zapisy można zatwierdzić szybciej, zapewniając jednocześnie pewien stopień redundancji, zapewniając, że są one replikowane do minimalnego podzbioru (kworum) węzłów, zanim transakcja zostanie zgłoszona jako przypisana do klienta.
Oznacza to, że odczytywanie węzłów poza kworum może wyświetlać przestarzałe wersje danych, dopóki proces w tle nie zakończy zapisywania danych w pozostałych węzłach. Semantyka jest znana jako „Ostateczna spójność” i może, ale nie musi być akceptowalna w zależności od wymagań twojej aplikacji, ale oznacza, że zatwierdzenia transakcji są bliższe O (1) niż O (n) w zużyciu zasobów.
Sharding wymaga od klienta świadomości partycjonowania danych w bazach danych, często przy użyciu pewnego rodzaju algorytmu zwanego „spójnym hashowaniem”. W podzielonej bazie danych klient hash klucz, aby określić, który serwer w klastrze ma wysłać zapytanie. Ponieważ żądania są dystrybuowane między węzłami w klastrze, nie ma wąskiego gardła w pojedynczym węźle koordynującym zapytania.
Techniki te umożliwiają skalowanie bazy danych z prędkością prawie liniową przez dodanie węzłów do klastra. Teoretycznie replikacja kworum jest konieczna tylko wtedy, gdy podstawowy nośnik pamięci ma być uważany za zawodny. Jest to przydatne, jeśli mają być używane serwery towarowe, ale ma mniejszą wartość, jeśli podstawowy mechanizm pamięci ma własny schemat wysokiej dostępności (na przykład SAN z kontrolerami lustrzanymi i łącznością wielościeżkową z hostami).
Na przykład Google BigTable nie implementuje samej replikacji kworum, chociaż działa w systemie plików GFS, klastrowym systemie plików, który korzysta z replikacji kworum. BigTable (lub dowolny system współdzielony-nic) mógłby korzystać z niezawodnego systemu pamięci masowej z wieloma kontrolerami i dzielić dane między kontrolery. Równoległy dostęp zostałby wówczas osiągnięty poprzez partycjonowanie danych.
Powrót do platform RDBMS
Nie ma nieodłącznego powodu, dla którego techniki te nie mogą być używane z RDBMS. Jednak zarządzanie blokadami i wersjami byłoby na takim systemie dość skomplikowane, a każdy rynek takiego systemu prawdopodobnie będzie dość wyspecjalizowany. Żadna z głównych platform RDBMS nie korzysta z replikacji kworum i nie jestem specjalnie świadoma żadnego produktu RDBMS (przynajmniej takiego o znacznym stopniu upowszechnienia), który by to zrobił.
Systemy z dyskami współdzielonymi i bez współużytkowanych systemów można skalować do bardzo dużych obciążeń. Na przykład Oracle RAC może obsługiwać 63 węzły przetwarzające (które same w sobie mogą być dużymi maszynami SMP) i dowolną liczbę kontrolerów pamięci w sieci SAN. IBM Sysplex (klaster komputerów mainframe zSeries) może obsługiwać wiele komputerów mainframe (każda ze znaczną mocą obliczeniową i własną przepustowością we / wy) oraz wiele kontrolerów SAN. Te architektury mogą obsługiwać bardzo duże wolumeny transakcji z semantyką ACID, chociaż zakładają niezawodne przechowywanie. Teradata, Netezza i inni dostawcy tworzą wysokowydajne platformy analityczne oparte na projektach typu „nic wspólnego”, które można skalować do bardzo dużych woluminów danych.
Do tej pory rynek tanich, ale bardzo dużych wolumenów platform ACID RDBMS jest zdominowany przez MySQL, który obsługuje dzielenie na fragmenty i replikację z wieloma wzorcami. MySQL nie używa replikacji kworum w celu optymalizacji przepustowości zapisu, więc zatwierdzanie transakcji jest droższe niż w systemie NoSQL. Sharding pozwala na bardzo wysoką przepustowość odczytu (na przykład Facebook intensywnie korzysta z MySQL), więc ten typ architektury dobrze skaluje się w przypadku obciążeń wymagających dużego odczytu.
Ciekawa debata
BigTable jest architekturą typu „nic wspólnego” (zasadniczo rozproszona para klucz-wartość), jak wskazał Michael Hausenblas poniżej . Moja pierwotna ocena dotyczyła silnika MapReduce, który nie jest częścią BigTable, ale normalnie byłby używany w połączeniu z nim w swoich najczęstszych implementacjach (np. Hadoop / HBase i framework MapReduce Google'a).
Porównując tę architekturę z Teradata, która ma fizyczne powinowactwo między pamięcią a przetwarzaniem (tj. Węzły mają lokalną pamięć zamiast wspólnej sieci SAN), można argumentować, że BigTable / MapReduce to architektura dysku współdzielonego za pośrednictwem globalnie widocznego równoległego systemu pamięci masowej.
Przepustowość przetwarzania systemu w stylu MapReduce, takiego jak Hadoop, jest ograniczona przepustowością nieblokującego przełącznika sieciowego. 1 Przełączniki nieblokujące mogą jednak obsługiwać duże agregaty przepustowości ze względu na równoległość związaną z konstrukcją, dlatego rzadko stanowią one znaczące praktyczne ograniczenie wydajności. Oznacza to, że architektura dysku współdzielonego (być może lepiej określana jako system pamięci współdzielonej) może być skalowana do dużych obciążeń, nawet jeśli przełącznik sieciowy jest teoretycznie centralnym wąskim gardłem.
Pierwotnym punktem było odnotowanie, że chociaż to centralne wąskie gardło występuje w systemach z dyskami współdzielonymi, partycjonowany podsystem pamięci z wieloma węzłami pamięci (np. Serwery tabletów BigTable lub kontrolery SAN) może nadal być skalowany do dużych obciążeń. Nieblokująca architektura przełączników może (teoretycznie) obsługiwać tyle bieżących połączeń, ile ma portów.
1 Oczywiście dostępna przepustowość przetwarzania i we / wy stanowi również ograniczenie wydajności, ale przełącznik sieciowy jest centralnym punktem, przez który przepływa cały ruch.