BAZA vs KWAS

6.1 Bitwa na skróty: BASE vs. KWAS

Popularne relacyjne bazy danych, takie jak MySQL, powstały właśnie na bazie ACID. Ale w ciągu ostatnich dziesięciu lat tak zwane bazy danych NoSQL, które pod tą nazwą łączą kilka bardzo różnych typów baz danych, radziły sobie całkiem dobrze bez ACID. W rzeczywistości istnieje duża liczba programistów, którzy pracują z bazami danych NoSQL i nie dbają w ogóle o transakcje i ich niezawodność. Zobaczmy, czy mają rację.

Nie można mówić ogólnie o bazie danych NoSQL, bo to po prostu dobra abstrakcja. Bazy danych NoSQL różnią się od siebie konstrukcją podsystemów przechowywania danych, a nawet modelami danych: NoSQL jest zarówno zorientowanym na dokumenty CouchDB, jak i grafowym Neo4J. Ale jeśli mówimy o nich w kontekście transakcji, wszystkie wydają się być podobne w jednym: zapewniają ograniczone wersje atomowości i izolacji, a zatem nie zapewniają gwarancji ACID. Aby zrozumieć, co to oznacza, odpowiedzmy sobie na pytanie: co oferują, jeśli nie ACID? Nic?

Nie bardzo. W końcu one, podobnie jak relacyjne bazy danych, również muszą się sprzedawać w pięknym opakowaniu. I wymyślili własny „chemiczny” skrót - BASE.

6.2 PODSTAWA jako antagonista

I tu znowu nie będę się kierował kolejnością liter, ale zacznę od podstawowego terminu – spójności. Będę musiał wyrównać efekt rozpoznawania, bo ta spójność ma niewiele wspólnego z konsystencją z ACID. Problem z terminem spójność polega na tym, że jest on używany w zbyt wielu kontekstach. Ale ta spójność ma znacznie szerszy kontekst użycia i rzeczywiście jest to dokładnie ta spójność, która jest omawiana przy omawianiu systemów rozproszonych.

Relacyjne bazy danych, o których mówiliśmy powyżej, zapewniają różne poziomy izolacji transakcji, a najsurowsze z nich zapewniają, że jedna transakcja nie widzi nieprawidłowych zmian wprowadzonych przez inną transakcję. Jeśli stoisz przy kasie w sklepie iw tym momencie z Twojego konta zostaną pobrane pieniądze na czynsz, ale transakcja z przelewem pieniędzy na czynsz nie powiedzie się i Twoje konto wróci do poprzedniej wartości (pieniądze nieobciążona), to Twoja transakcja płatnicza przy kasie nie zauważy wszystkich tych gestów - w końcu ta transakcja nigdy nie została zrealizowana, a ze względu na wymóg izolacji transakcji jej chwilowe zmiany nie mogą zostać zauważone przez inne transakcje.

Wiele baz danych NoSQL rezygnuje z gwarancji izolacji i oferuje „ewentualną spójność”, dzięki której ostatecznie zobaczysz prawidłowe dane, ale istnieje szansa, że ​​Twoja transakcja odczyta nieprawidłowe wartości - to znaczy tymczasowe, częściowo zaktualizowane lub nieaktualne. Możliwe, że dane staną się spójne w trybie „leniwym” podczas odczytu („leniwy w czasie odczytu”).

NoSQL został pomyślany jako baza danych do analiz w czasie rzeczywistym, a aby osiągnąć większą szybkość, poświęcili spójność. A Eric Brewer, ten sam facet, który ukuł termin BASE, sformułował tak zwane „twierdzenie CAP”, zgodnie z którym:

Dla dowolnej implementacji przetwarzania rozproszonego możliwe jest podanie nie więcej niż dwóch z następujących trzech właściwości:

• spójność danych ( spójność ) - dane w różnych węzłach (instancjach) nie są ze sobą sprzeczne;
• dostępność ( dostępność ) - każde zapytanie kierowane do systemu rozproszonego kończy się poprawną odpowiedzią, ale bez gwarancji, że odpowiedzi wszystkich węzłów systemu są takie same;
• tolerancja partycji (partition tolerancja ) - Nawet jeśli nie ma połączenia między węzłami, nadal działają one niezależnie od siebie.

Jeśli chcesz bardzo prostego wyjaśnienia WPR, proszę bardzo.

Istnieją opinie, że twierdzenie CAP nie działa i jest generalnie formułowane zbyt abstrakcyjnie. Tak czy inaczej, bazy danych NoSQL często odmawiają spójności w kontekście twierdzenia CAP, które opisuje następującą sytuację: dane zostały zaktualizowane w klastrze z kilkoma instancjami, ale zmiany nie zostały jeszcze zsynchronizowane we wszystkich instancjach. Pamiętasz, jak wspomniałem powyżej o przykładzie DynamoDB, który powiedział mi: Twoje zmiany stały się trwałe — oto HTTP 200 dla Ciebie — ale zmiany zobaczyłem dopiero po 10 sekundach? Innym przykładem z codziennego życia programisty jest DNS, system nazw domen. Jeśli ktoś nie wie, to jest to dokładnie „słownik”, który tłumaczy adresy http (s) na adresy IP.

Zaktualizowany rekord DNS jest propagowany na serwery zgodnie z ustawieniami interwału buforowania - dlatego aktualizacje nie są natychmiast zauważalne. Cóż, podobna niespójność czasowa (tj. ostatecznie spójność) może się zdarzyć w klastrze relacyjnej bazy danych (powiedzmy MySQL) - w końcu ta spójność nie ma nic wspólnego ze spójnością z ACID. Dlatego ważne jest, aby zrozumieć, że w tym sensie bazy danych SQL i NoSQL raczej nie będą się bardzo różnić, jeśli chodzi o kilka instancji w klastrze.

Ponadto spójność typu end-to-end może oznaczać, że żądania zapisu będą wykonywane poza kolejnością: to znaczy, że wszystkie dane zostaną zapisane, ale wartość, która ostatecznie zostanie odebrana, nie będzie ostatnią w kolejce zapisu.

Bazy danych Non-ACID NoSQL mają tzw. „soft state” ze względu na model spójności end-to-end, co oznacza, że ​​stan systemu może zmieniać się w czasie, nawet bez wprowadzania danych. Ale takie systemy starają się zapewnić większą dostępność. Zapewnienie 100% dostępności nie jest zadaniem trywialnym, dlatego mówimy o „podstawowej dostępności”. A razem te trzy pojęcia: „zasadniczo dostępny”, „miękki stan” („miękki stan”) i „ewentualna spójność” tworzą akronim BASE.

Szczerze mówiąc, koncepcja BASE wydaje mi się bardziej pustym opakowaniem marketingowym niż ACID – bo nie wnosi nic nowego i w żaden sposób nie charakteryzuje bazy. A dołączanie etykiet (ACID, BASE, CAP) do niektórych baz danych może tylko zmylić programistów. Postanowiłem i tak przybliżyć Wam ten termin, bo trudno go ominąć podczas studiowania bazy danych, ale skoro już wiecie, co to jest, chcę, żebyście jak najszybciej o nim zapomnieli. I wróćmy do pojęcia izolacji.

6.3 Czyli bazy danych BASE w ogóle nie spełniają kryteriów ACID?

Zasadniczo tam, gdzie bazy danych ACID różnią się od baz innych niż ACID, polega to na tym, że bazy danych inne niż ACID faktycznie rezygnują z izolacji. Jest to ważne, aby zrozumieć. Ale jeszcze ważniejsze jest, aby przeczytać dokumentację bazy danych i przetestować ją tak, jak robią to ludzie z projektu Hermitage. Nie jest tak ważne, jak dokładnie twórcy tej lub innej bazy danych nazywają swój pomysł - ACID lub BASE, CAP lub nie CAP. Ważną rzeczą jest to, co dokładnie zapewnia ta lub inna baza danych.

Jeśli twórcy bazy twierdzą, że daje ona gwarancje ACID, to pewnie jest ku temu powód, ale warto samemu to przetestować, żeby zrozumieć, czy tak jest iw jakim stopniu. Jeśli deklarują, że ich baza danych nie daje takich gwarancji, może to oznaczać, że:

• DB nie gwarantuje atomowości. Podczas gdy niektóre bazy danych NoSQL oferują oddzielne API dla operacji atomowych (np. DynamoDB);

• Baza danych nie zapewnia żadnej gwarancji izolacji. Może to oznaczać np., że baza danych nie zapisze danych w takiej kolejności, w jakiej zostały zapisane.

Jeśli chodzi o gwarancję trwałości, wiele baz danych idzie na kompromis w tej kwestii ze względu na wydajność. Zapisywanie na dysk to zbyt długa operacja i istnieje kilka sposobów rozwiązania tego problemu. Nie chcę zbytnio zagłębiać się w teorię baz danych, ale żebyście z grubsza zrozumieli, w którą stronę patrzeć, opiszę ogólnie, jak różne bazy danych rozwiązują problem z trwałością.

Między innymi, aby porównać różne bazy danych, musisz wiedzieć, jakie struktury danych leżą u podstaw podsystemu przechowywania i wyszukiwania danych w danej bazie danych. W skrócie: różne bazy danych mają różne implementacje indeksowania – czyli organizacji dostępu do danych. Niektóre z nich pozwalają na szybszy zapis danych, inne na szybszy ich odczyt. Ale ogólnie nie można powiedzieć, że niektóre struktury danych zwiększają lub zmniejszają trwałość.

6.4 jak różne bazy danych indeksują dane i jak to wpływa na trwałość i nie tylko

Istnieją dwa główne podejścia do przechowywania i pobierania danych.

Najłatwiejszym sposobem na zapisanie danych jest dodanie operacji na końcu pliku w sposób podobny do dziennika (to znaczy operacja dołączania występuje zawsze): nie ma znaczenia, czy chcemy dodać, zmienić czy usunąć dane - wszystko Operacje CRUD są po prostu zapisywane w dzienniku. Przeszukiwanie dziennika jest nieefektywne i właśnie tam pojawia się indeks — specjalna struktura danych, która przechowuje metadane dotyczące dokładnego miejsca przechowywania danych. Najprostszą strategią indeksowania dzienników jest mapa skrótów, która śledzi klucze i wartości. Wartości będą odniesieniami do przesunięcia bajtu dla danych zapisanych wewnątrz pliku, który jest logiem (logiem) i jest przechowywany na dysku. Ta struktura danych jest w całości przechowywana w pamięci, podczas gdy same dane znajdują się na dysku i jest nazywana drzewem LSM (ang. log structured merge).

Pewnie zastanawialiście się: jeśli cały czas będziemy wpisywać nasze operacje do dziennika, to będzie on niebotycznie rósł? Tak, dlatego wymyślono technikę zagęszczania, która „czyści” dane z pewną częstotliwością, a mianowicie pozostawia tylko najbardziej odpowiednią wartość dla każdego klucza lub ją usuwa. A jeśli mamy więcej niż jeden log na dysku, ale kilka i wszystkie są posortowane, to otrzymamy nową strukturę danych o nazwie SSTable („sorted string table”), a to niewątpliwie poprawi naszą wydajność. Jeśli będziemy chcieli posortować w pamięci, otrzymamy podobną strukturę – tzw. MemTable, ale z nią problem polega na tym, że jeśli nastąpi fatalna awaria bazy danych, to dane zapisane jako ostatnie (znajdujące się w MemTable, ale jeszcze nie zapisane do dysk) zostaną utracone. Faktycznie,

Inne podejście do indeksowania opiera się na B-drzewach („B-drzewach”). W B-drzewie dane są zapisywane na dysku na stronach o stałym rozmiarze. Te bloki danych mają często rozmiar około 4 KB i pary klucz-wartość są posortowane według klucza. Jeden węzeł B-drzewa jest jak tablica z łączami do zakresu stron. Maks. liczba łączy w tablicy nazywana jest współczynnikiem rozgałęzienia. Każdy zakres stron jest kolejnym węzłem B-drzewa z łączami do innych zakresów stron.

Docelowo na poziomie arkusza znajdziesz poszczególne strony. Ten pomysł jest podobny do wskaźników w językach programowania niskiego poziomu, z tą różnicą, że te odniesienia do stron są przechowywane na dysku, a nie w pamięci. Kiedy w bazie danych występują INSERT i DELETE, jakiś węzeł może podzielić się na dwa poddrzewa, aby dopasować współczynnik rozgałęzienia. Jeśli baza danych ulegnie awarii z jakiegokolwiek powodu w trakcie procesu, integralność danych może zostać naruszona. Aby temu zapobiec, bazy danych korzystające z B-drzew utrzymują „dziennik zapisu z wyprzedzeniem” lub WAL, w którym rejestrowana jest każda pojedyncza transakcja. Ten WAL jest używany do przywracania stanu B-drzewa, jeśli jest ono uszkodzone. I wydaje się, że właśnie to sprawia, że ​​bazy danych wykorzystujące B-drzewa są lepsze pod względem trwałości. Ale bazy danych oparte na LSM mogą również przechowywać plik, który zasadniczo wykonuje tę samą funkcję, co WAL. Dlatego powtórzę to, co już powiedziałem, a może nie raz: zrozum mechanizmy działania wybranej przez Ciebie bazy danych.

Pewne jest jednak to, że B-drzewa są dobre dla transakcyjności: każdy klucz występuje tylko w jednym miejscu w indeksie, podczas gdy podsystemy pamięci masowej z dziennikiem mogą mieć wiele kopii tego samego klucza w różnych fragmentach (na przykład do czasu przeprowadzane jest kolejne zagęszczanie).

Jednak projekt indeksu ma bezpośredni wpływ na wydajność bazy danych. W przypadku drzewa LSM zapisy na dysku są sekwencyjne, a B-drzewa powodują wiele losowych dostępów do dysku, więc operacje zapisu są szybsze w przypadku LSM niż w przypadku B-drzew. Różnica jest szczególnie znacząca w przypadku magnetycznych dysków twardych (HDD), gdzie zapis sekwencyjny jest znacznie szybszy niż zapis losowy. Odczyt jest wolniejszy na drzewach LSM, ponieważ trzeba przejrzeć kilka różnych struktur danych i tabel SS, które są na różnych etapach zagęszczania. Bardziej szczegółowo wygląda to tak. Jeśli wykonamy proste zapytanie do bazy danych za pomocą LSM, najpierw wyszukamy klucz w MemTable. Jeśli go tam nie ma, patrzymy na najnowszą SSTable; jeśli go tam nie ma, patrzymy na przedostatnią tabelę SSTable i tak dalej. Jeśli żądany klucz nie istnieje, to dzięki LSM dowiemy się tego na końcu. Drzewa LSM są wykorzystywane m.in. w: LevelDB, RocksDB, Cassandra i HBase.

Opisuję to wszystko tak szczegółowo, abyś zrozumiał, że wybierając bazę danych, musisz wziąć pod uwagę wiele różnych rzeczy: na przykład, czy spodziewasz się więcej zapisywać lub odczytywać dane. I jeszcze nie wspomniałem o różnicy w modelach danych (czy trzeba przemierzać dane, tak jak pozwala model grafowy? Czy w ogóle są jakieś relacje pomiędzy różnymi jednostkami w twoich danych - wtedy z pomocą przyjdą relacyjne bazy danych?), oraz 2 typy schematów danych - podczas pisania (jak w wielu NoSQL) i odczytu (jak w relacyjnych).

Jeśli wrócimy do aspektu trwałości, to wniosek będzie następujący: każda baza danych, która zapisuje na dysk, niezależnie od mechanizmów indeksowania, może dać dobre gwarancje trwałości Twoich danych, ale z każdą konkretną bazą danych trzeba sobie poradzić , co dokładnie oferuje.

6.5 Jak działają bazy danych w pamięci

Nawiasem mówiąc, oprócz baz danych, które zapisują na dysk, istnieją również tak zwane bazy danych „in-memory”, które działają głównie z pamięcią RAM. Krótko mówiąc, bazy danych w pamięci zwykle oferują niższą trwałość ze względu na szybsze prędkości zapisu i odczytu, ale może to być odpowiednie dla niektórych aplikacji.

Faktem jest, że pamięć RAM od dawna jest droższa od dysków, ale ostatnio zaczęła gwałtownie taniejeć, co dało początek nowemu typowi bazy danych – co jest logiczne, biorąc pod uwagę szybkość odczytu i zapisu danych z pamięci RAM. Ale słusznie zapytacie: co z bezpieczeństwem danych w tych bazach danych? Tutaj znowu trzeba przyjrzeć się szczegółom implementacji. Ogólnie rzecz biorąc, twórcy takich baz danych oferują następujące mechanizmy:

• Możesz użyć pamięci RAM zasilanej bateriami;
• Możliwe jest zapisywanie dzienników zmian na dysku (coś w rodzaju wspomnianych powyżej WAL), ale nie samych danych;
• Można okresowo zapisywać kopie stanu bazy danych na dysk (co bez użycia innych opcji nie daje gwarancji, a jedynie poprawia trwałość);
• Możesz replikować stan pamięci RAM na inne komputery.

Na przykład baza danych Redis w pamięci, która jest używana głównie jako kolejka komunikatów lub pamięć podręczna, nie jest odporna na ACID: nie gwarantuje, że pomyślnie wykonane polecenie zostanie zapisane na dysku, ponieważ Redis opróżnia dane na dysk (jeśli mieć włączoną funkcję trwałości) tylko asynchronicznie, w regularnych odstępach czasu.

Jednak nie jest to krytyczne dla wszystkich aplikacji: znalazłem przykład kooperacyjnego edytora online EtherPad, który opróżniał się co 1-2 sekundy i potencjalnie użytkownik mógł stracić kilka liter lub słowo, co nie było krytyczne. W przeciwnym razie, ponieważ bazy danych in-memory są dobre, ponieważ dostarczają modele danych, które byłyby trudne do zaimplementowania z indeksami dyskowymi, Redis może służyć do implementacji transakcji - pozwala na to jego kolejka priorytetów.

Relacyjne bazy danych, o których mówiliśmy powyżej, zapewniają różne poziomy izolacji transakcji, a najsurowsze z nich zapewniają, że jedna transakcja nie widzi nieprawidłowych zmian wprowadzonych przez inną transakcję. Jeśli stoisz przy kasie w sklepie iw tym momencie z Twojego konta zostaną pobrane pieniądze na czynsz, ale transakcja z przelewem pieniędzy na czynsz nie powiedzie się i Twoje konto wróci do poprzedniej wartości (pieniądze nieobciążona), to Twoja transakcja płatnicza przy kasie nie zauważy wszystkich tych gestów - w końcu ta transakcja nigdy nie została zrealizowana, a ze względu na wymóg izolacji transakcji jej chwilowe zmiany nie mogą zostać zauważone przez inne transakcje.

Wiele baz danych NoSQL rezygnuje z gwarancji izolacji i oferuje „ewentualną spójność”, dzięki której ostatecznie zobaczysz prawidłowe dane, ale istnieje szansa, że ​​Twoja transakcja odczyta nieprawidłowe wartości - to znaczy tymczasowe, częściowo zaktualizowane lub nieaktualne. Możliwe, że dane staną się spójne w trybie „leniwym” podczas odczytu („leniwy w czasie odczytu”).

NoSQL został pomyślany jako baza danych do analiz w czasie rzeczywistym, a aby osiągnąć większą szybkość, poświęcili spójność. A Eric Brewer, ten sam facet, który ukuł termin BASE, sformułował tak zwane „twierdzenie CAP”, zgodnie z którym:

Dla dowolnej implementacji przetwarzania rozproszonego możliwe jest podanie nie więcej niż dwóch z następujących trzech właściwości:

• spójność danych ( spójność ) - dane w różnych węzłach (instancjach) nie są ze sobą sprzeczne;
• dostępność ( dostępność ) - każde zapytanie kierowane do systemu rozproszonego kończy się poprawną odpowiedzią, ale bez gwarancji, że odpowiedzi wszystkich węzłów systemu są takie same;
• tolerancja partycji (partition tolerancja ) - Nawet jeśli nie ma połączenia między węzłami, nadal działają one niezależnie od siebie.

Jeśli chcesz bardzo prostego wyjaśnienia WPR, proszę bardzo.

Istnieją opinie, że twierdzenie CAP nie działa i jest generalnie formułowane zbyt abstrakcyjnie. Tak czy inaczej, bazy danych NoSQL często odmawiają spójności w kontekście twierdzenia CAP, które opisuje następującą sytuację: dane zostały zaktualizowane w klastrze z kilkoma instancjami, ale zmiany nie zostały jeszcze zsynchronizowane we wszystkich instancjach. Pamiętasz, jak wspomniałem powyżej o przykładzie DynamoDB, który powiedział mi: Twoje zmiany stały się trwałe — oto HTTP 200 dla Ciebie — ale zmiany zobaczyłem dopiero po 10 sekundach? Innym przykładem z codziennego życia programisty jest DNS, system nazw domen. Jeśli ktoś nie wie, to jest to dokładnie „słownik”, który tłumaczy adresy http (s) na adresy IP.

Zaktualizowany rekord DNS jest propagowany na serwery zgodnie z ustawieniami interwału buforowania - dlatego aktualizacje nie są natychmiast zauważalne. Cóż, podobna niespójność czasowa (tj. ostatecznie spójność) może się zdarzyć w klastrze relacyjnej bazy danych (powiedzmy MySQL) - w końcu ta spójność nie ma nic wspólnego ze spójnością z ACID. Dlatego ważne jest, aby zrozumieć, że w tym sensie bazy danych SQL i NoSQL raczej nie będą się bardzo różnić, jeśli chodzi o kilka instancji w klastrze.

Ponadto spójność typu end-to-end może oznaczać, że żądania zapisu będą wykonywane poza kolejnością: to znaczy, że wszystkie dane zostaną zapisane, ale wartość, która ostatecznie zostanie odebrana, nie będzie ostatnią w kolejce zapisu.

Bazy danych Non-ACID NoSQL mają tzw. „soft state” ze względu na model spójności end-to-end, co oznacza, że ​​stan systemu może zmieniać się w czasie, nawet bez wprowadzania danych. Ale takie systemy starają się zapewnić większą dostępność. Zapewnienie 100% dostępności nie jest zadaniem trywialnym, dlatego mówimy o „podstawowej dostępności”. A razem te trzy pojęcia: „zasadniczo dostępny”, „miękki stan” („miękki stan”) i „ewentualna spójność” tworzą akronim BASE.

Szczerze mówiąc, koncepcja BASE wydaje mi się bardziej pustym opakowaniem marketingowym niż ACID – bo nie wnosi nic nowego i w żaden sposób nie charakteryzuje bazy. A dołączanie etykiet (ACID, BASE, CAP) do niektórych baz danych może tylko zmylić programistów. Postanowiłem i tak przybliżyć Wam ten termin, bo trudno go ominąć podczas studiowania bazy danych, ale skoro już wiecie, co to jest, chcę, żebyście jak najszybciej o nim zapomnieli. I wróćmy do pojęcia izolacji.

6.3 Czyli bazy danych BASE w ogóle nie spełniają kryteriów ACID?

Zasadniczo tam, gdzie bazy danych ACID różnią się od baz innych niż ACID, polega to na tym, że bazy danych inne niż ACID faktycznie rezygnują z izolacji. Jest to ważne, aby zrozumieć. Ale jeszcze ważniejsze jest, aby przeczytać dokumentację bazy danych i przetestować ją tak, jak robią to ludzie z projektu Hermitage. Nie jest tak ważne, jak dokładnie twórcy tej lub innej bazy danych nazywają swój pomysł - ACID lub BASE, CAP lub nie CAP. Ważną rzeczą jest to, co dokładnie zapewnia ta lub inna baza danych.

Jeśli twórcy bazy twierdzą, że daje ona gwarancje ACID, to pewnie jest ku temu powód, ale warto samemu to przetestować, żeby zrozumieć, czy tak jest iw jakim stopniu. Jeśli deklarują, że ich baza danych nie daje takich gwarancji, może to oznaczać, że:

• DB nie gwarantuje atomowości. Podczas gdy niektóre bazy danych NoSQL oferują oddzielne API dla operacji atomowych (np. DynamoDB);

• Baza danych nie zapewnia żadnej gwarancji izolacji. Może to oznaczać np., że baza danych nie zapisze danych w takiej kolejności, w jakiej zostały zapisane.

Jeśli chodzi o gwarancję trwałości, wiele baz danych idzie na kompromis w tej kwestii ze względu na wydajność. Zapisywanie na dysk to zbyt długa operacja i istnieje kilka sposobów rozwiązania tego problemu. Nie chcę zbytnio zagłębiać się w teorię baz danych, ale żebyście z grubsza zrozumieli, w którą stronę patrzeć, opiszę ogólnie, jak różne bazy danych rozwiązują problem z trwałością.

Między innymi, aby porównać różne bazy danych, musisz wiedzieć, jakie struktury danych leżą u podstaw podsystemu przechowywania i wyszukiwania danych w danej bazie danych. W skrócie: różne bazy danych mają różne implementacje indeksowania – czyli organizacji dostępu do danych. Niektóre z nich pozwalają na szybszy zapis danych, inne na szybszy ich odczyt. Ale ogólnie nie można powiedzieć, że niektóre struktury danych zwiększają lub zmniejszają trwałość.

6.4 jak różne bazy danych indeksują dane i jak to wpływa na trwałość i nie tylko

Istnieją dwa główne podejścia do przechowywania i pobierania danych.

Najłatwiejszym sposobem na zapisanie danych jest dodanie operacji na końcu pliku w sposób podobny do dziennika (to znaczy operacja dołączania występuje zawsze): nie ma znaczenia, czy chcemy dodać, zmienić czy usunąć dane - wszystko Operacje CRUD są po prostu zapisywane w dzienniku. Przeszukiwanie dziennika jest nieefektywne i właśnie tam pojawia się indeks — specjalna struktura danych, która przechowuje metadane dotyczące dokładnego miejsca przechowywania danych. Najprostszą strategią indeksowania dzienników jest mapa skrótów, która śledzi klucze i wartości. Wartości będą odniesieniami do przesunięcia bajtu dla danych zapisanych wewnątrz pliku, który jest logiem (logiem) i jest przechowywany na dysku. Ta struktura danych jest w całości przechowywana w pamięci, podczas gdy same dane znajdują się na dysku i jest nazywana drzewem LSM (ang. log structured merge).

Pewnie zastanawialiście się: jeśli cały czas będziemy wpisywać nasze operacje do dziennika, to będzie on niebotycznie rósł? Tak, dlatego wymyślono technikę zagęszczania, która „czyści” dane z pewną częstotliwością, a mianowicie pozostawia tylko najbardziej odpowiednią wartość dla każdego klucza lub ją usuwa. A jeśli mamy więcej niż jeden log na dysku, ale kilka i wszystkie są posortowane, to otrzymamy nową strukturę danych o nazwie SSTable („sorted string table”), a to niewątpliwie poprawi naszą wydajność. Jeśli będziemy chcieli posortować w pamięci, otrzymamy podobną strukturę – tzw. MemTable, ale z nią problem polega na tym, że jeśli nastąpi fatalna awaria bazy danych, to dane zapisane jako ostatnie (znajdujące się w MemTable, ale jeszcze nie zapisane do dysk) zostaną utracone. Faktycznie,

Inne podejście do indeksowania opiera się na B-drzewach („B-drzewach”). W B-drzewie dane są zapisywane na dysku na stronach o stałym rozmiarze. Te bloki danych mają często rozmiar około 4 KB i pary klucz-wartość są posortowane według klucza. Jeden węzeł B-drzewa jest jak tablica z łączami do zakresu stron. Maks. liczba łączy w tablicy nazywana jest współczynnikiem rozgałęzienia. Każdy zakres stron jest kolejnym węzłem B-drzewa z łączami do innych zakresów stron.

Docelowo na poziomie arkusza znajdziesz poszczególne strony. Ten pomysł jest podobny do wskaźników w językach programowania niskiego poziomu, z tą różnicą, że te odniesienia do stron są przechowywane na dysku, a nie w pamięci. Kiedy w bazie danych występują INSERT i DELETE, jakiś węzeł może podzielić się na dwa poddrzewa, aby dopasować współczynnik rozgałęzienia. Jeśli baza danych ulegnie awarii z jakiegokolwiek powodu w trakcie procesu, integralność danych może zostać naruszona. Aby temu zapobiec, bazy danych korzystające z B-drzew utrzymują „dziennik zapisu z wyprzedzeniem” lub WAL, w którym rejestrowana jest każda pojedyncza transakcja. Ten WAL jest używany do przywracania stanu B-drzewa, jeśli jest ono uszkodzone. I wydaje się, że właśnie to sprawia, że ​​bazy danych wykorzystujące B-drzewa są lepsze pod względem trwałości. Ale bazy danych oparte na LSM mogą również przechowywać plik, który zasadniczo wykonuje tę samą funkcję, co WAL. Dlatego powtórzę to, co już powiedziałem, a może nie raz: zrozum mechanizmy działania wybranej przez Ciebie bazy danych.

Pewne jest jednak to, że B-drzewa są dobre dla transakcyjności: każdy klucz występuje tylko w jednym miejscu w indeksie, podczas gdy podsystemy pamięci masowej z dziennikiem mogą mieć wiele kopii tego samego klucza w różnych fragmentach (na przykład do czasu przeprowadzane jest kolejne zagęszczanie).

Jednak projekt indeksu ma bezpośredni wpływ na wydajność bazy danych. W przypadku drzewa LSM zapisy na dysku są sekwencyjne, a B-drzewa powodują wiele losowych dostępów do dysku, więc operacje zapisu są szybsze w przypadku LSM niż w przypadku B-drzew. Różnica jest szczególnie znacząca w przypadku magnetycznych dysków twardych (HDD), gdzie zapis sekwencyjny jest znacznie szybszy niż zapis losowy. Odczyt jest wolniejszy na drzewach LSM, ponieważ trzeba przejrzeć kilka różnych struktur danych i tabel SS, które są na różnych etapach zagęszczania. Bardziej szczegółowo wygląda to tak. Jeśli wykonamy proste zapytanie do bazy danych za pomocą LSM, najpierw wyszukamy klucz w MemTable. Jeśli go tam nie ma, patrzymy na najnowszą SSTable; jeśli go tam nie ma, patrzymy na przedostatnią tabelę SSTable i tak dalej. Jeśli żądany klucz nie istnieje, to dzięki LSM dowiemy się tego na końcu. Drzewa LSM są wykorzystywane m.in. w: LevelDB, RocksDB, Cassandra i HBase.

Opisuję to wszystko tak szczegółowo, abyś zrozumiał, że wybierając bazę danych, musisz wziąć pod uwagę wiele różnych rzeczy: na przykład, czy spodziewasz się więcej zapisywać lub odczytywać dane. I jeszcze nie wspomniałem o różnicy w modelach danych (czy trzeba przemierzać dane, tak jak pozwala model grafowy? Czy w ogóle są jakieś relacje pomiędzy różnymi jednostkami w twoich danych - wtedy z pomocą przyjdą relacyjne bazy danych?), oraz 2 typy schematów danych - podczas pisania (jak w wielu NoSQL) i odczytu (jak w relacyjnych).

Jeśli wrócimy do aspektu trwałości, to wniosek będzie następujący: każda baza danych, która zapisuje na dysk, niezależnie od mechanizmów indeksowania, może dać dobre gwarancje trwałości Twoich danych, ale z każdą konkretną bazą danych trzeba sobie poradzić , co dokładnie oferuje.

6.5 Jak działają bazy danych w pamięci

Nawiasem mówiąc, oprócz baz danych, które zapisują na dysk, istnieją również tak zwane bazy danych „in-memory”, które działają głównie z pamięcią RAM. Krótko mówiąc, bazy danych w pamięci zwykle oferują niższą trwałość ze względu na szybsze prędkości zapisu i odczytu, ale może to być odpowiednie dla niektórych aplikacji.

Faktem jest, że pamięć RAM od dawna jest droższa od dysków, ale ostatnio zaczęła gwałtownie taniejeć, co dało początek nowemu typowi bazy danych – co jest logiczne, biorąc pod uwagę szybkość odczytu i zapisu danych z pamięci RAM. Ale słusznie zapytacie: co z bezpieczeństwem danych w tych bazach danych? Tutaj znowu trzeba przyjrzeć się szczegółom implementacji. Ogólnie rzecz biorąc, twórcy takich baz danych oferują następujące mechanizmy:

• Możesz użyć pamięci RAM zasilanej bateriami;
• Możliwe jest zapisywanie dzienników zmian na dysku (coś w rodzaju wspomnianych powyżej WAL), ale nie samych danych;
• Można okresowo zapisywać kopie stanu bazy danych na dysk (co bez użycia innych opcji nie daje gwarancji, a jedynie poprawia trwałość);
• Możesz replikować stan pamięci RAM na inne komputery.

Na przykład baza danych Redis w pamięci, która jest używana głównie jako kolejka komunikatów lub pamięć podręczna, nie jest odporna na ACID: nie gwarantuje, że pomyślnie wykonane polecenie zostanie zapisane na dysku, ponieważ Redis opróżnia dane na dysk (jeśli mieć włączoną funkcję trwałości) tylko asynchronicznie, w regularnych odstępach czasu.

Jednak nie jest to krytyczne dla wszystkich aplikacji: znalazłem przykład kooperacyjnego edytora online EtherPad, który opróżniał się co 1-2 sekundy i potencjalnie użytkownik mógł stracić kilka liter lub słowo, co nie było krytyczne. W przeciwnym razie, ponieważ bazy danych in-memory są dobre, ponieważ dostarczają modele danych, które byłyby trudne do zaimplementowania z indeksami dyskowymi, Redis może służyć do implementacji transakcji - pozwala na to jego kolejka priorytetów.