Drzewo LSM: Jak Cassandra, RocksDB i LevelDB Szybko Zapisują Dane

Memtablica: Pisanie Nigdy Nie Dotyka Pierwszy Raz Dysku

Kiedy drzewo LSM otrzymuje zapis, nie szuka miejsca na dysku do umieszczenia go tam. Zamiast tego zapis jest wprowadzany do memtablicy, struktury uporządkowanej w pamięci, zwykle listy skokowej lub drzewa równoważnego, która przechowuje najnowsze zmiany. Ponieważ memtablica istnieje w pamięci RAM, wprowadzanie do niej jest bardzo szybkie, a ponieważ jest uporządkowana według klucza, późniejsze operacje, takie jak zakresowe skanowanie lub zatwierdzanie, mogą przechodzić po niej w porządku bez dodatkowej pracy. Każdy zapis również zostaje dołączony do dziennika zanimotrotowania na dysku przed lub obok wprowadzenia do memtablicy. Ten dziennik jest tarczą zapobiegającą awariom: jeśli proces awaryjnie zatrzyma się przed zatwierdzeniem memtablicy, dziennik może być ponownie uruchomiony, aby odtworzyć zawartość memtablicy. Sam dziennik jest pisanym jedynie w sekwencji, więc jest ekonomiczny nawet jeśli dotyka dysku przy każdym zapisie. Memtablica ma stałą pojemność, często mierzoną w dziesiątkach megabajtów. Gdy się wypełni, silnik przechowywania zamarza ją, zaczyna nową pustą memtablicę do przyjmowania nowych zapisów i harmonogramuje zatwierdzenie zamarzniętej do zapisu na dysku. To przekazanie pozwala zapisań nadal płynąć bez blokady na operacjach I/O dyskowych w większości przypadków. Aktualizacje i usunięcia są obsługiwane w ten sam sposób co nowe zapisy: aktualizacja to tylko nowa wartość zapisana pod istniejącym kluczem, a usunięcie to specjalny oznak nazywany tombstonem. Niektóra z tych operacji nie szuka ani nie modyfikuje starej kopii klucza. Starożytna kopia po prostu leży tam stale gdzieś na dysku, aż do kompresji, która w końcu zauważa i odrzuci ją. To jest podstawowa uproszczenie, które sprawia, że pisanie drzewa LSM tak szybkie: dodawanie teraz, czyszczenie później. Ponieważ czytania muszą zobaczyć najnowsze dane, memtablica zawsze jest pierwszym miejscem, w którym sprawdzane są dane przed konsultacją czegoś na dysku, ponieważ przechowuje najnowszą stan kluczaany który został niedawno zapisany.

SSTables: Niezmienne, Posortowane, Fluszowane Sequencjalnie

Kiedy memtable jest fluszowany, jego posortowane treści są zapisywane na dysku jako SSTable (Sorted String Table). Charakterystycznym celem SSTable jest to, że jest ona niezmienna: raz zapisana, jej bajty nigdy się nie zmieniają. Ta jedna decyzyjna wyboru eliminuje całą kategorię problemów, które krucytują w miejscowym przechowywaniu. Nie ma potrzeby blokad do ochrony pliku podczas zapisu, nie ma ryzyka, że awaria zostawi stronę połowie aktualizowanej, a buforowanie staje się trywialne, ponieważ buforowany blok nigdy nie może stać się przestarzały. Ponieważ memtable był już posortowany, zapisanie go jako SSTable to pojedyncze liniowe przejście: silnik strumieniowo wypisuje pary klucz-wartość na dysk w kolejności rosnących kluczy, w jednym długim sekwencyjnym zapisie. Sekwencyjne zapisy są znacznie szybsze niż losowe zapisy na dyskach obrotowych, ponieważ między operacjami nie ma czasu wyszukiwania, a także są przyjazne do pamięci flash, która cierpi na uszkodzenie i powiększenie zapisów ze względu na małe losowe aktualizacje. Sztukę SSTable zwykle zawiera więcej niż tylko czyste dane. Zwykle zawiera również rzadszy indeks mapujący klucze do offsetów bajtów, dlatego wyszukiwanie nie musi skanować całego pliku, a często ma malutki stopień zawierający podsumowanie zakresu kluczów pokrytych przez plik. Niektóre silniki również przechowują sumy kontrolne bloków do wykrycia uszkodzeń. Podczas życia bazy danych wiele SSTable akumuluje na dysku, jedno dla każdego fluszu memtable plus każdego wyniku kompaktacji. Jedna klasa może technicznie istnieć w wielu SSTableach jednocześnie, jeśli została ona zapisana, a następnie później aktualizowana. Tylko kopię z najnowszego SSTable, lub z memtable, jeśli jeszcze nie został on fluszony, jest obecną wartością; reszta są przestarzałe, ale nadal fizycznie obecne do momentu kompaktacji ich usunięcia.

Sprawdzanie memtabli, a następnie SS tabel najnowszych od najstarszych

Pisania w drzewie LSM są tanie dokładnie dlatego, że czytania noszą koszt. Aby odpowiedzieć na wyszukiwanie dla danego klucza, silnik nie może sprawdzić jednego miejsca; musi potencjalnie przeszukać memtable oraz każdą SS tabelę na dysku. Zawsze zaczyna od memtabli, ponieważ ona przechowuje najnowsze, jeszcze nieprzelane pisania. Jeśli klucz jest tam znaleziony, wyszukiwanie się kończy natychmiast. Jeśli klucz nie znajduje się w memtable, silnik przenosi do SS tabel, sprawdzając je w kolejności od najnowszych do najstarszych. Ta kolejność ma znaczenie, ponieważ klucz może zostać zapisany wielokrotnie na różnych SS tabelach, a tylko najnowsza wersja jest poprawna. W chwili, gdy znaleziono pasujący klucz w SS tabeli, wyszukiwanie się kończy, ponieważ dowolna starsza kopię tego klucza z SS tabeli jest stalej na podstawie definicji. Jeśli znaleziona wpis jest tombstonem, silnik zgłasza klucz jako usunięty zamiast kontynuować wyszukiwanie starszej, teraz nieistotnej wartości. W najgorszym przypadku, klucz, który nigdy nie został ostatnio zapisany i w ogóle nie istnieje, wymusza na silniku sprawdzenie memtabli oraz każdej SS tabeli przed stwierdzeniem, że jest brakujący. To jest rozmnazanie czytania: jedno logiczne odczyt przekształca się w wiele fizycznych wyszukiwań plików. Gdy więcej SS tabel pojawia się między kompaktacjami, obroty czytania i najgorszy przypadkowy koszt rosną, co stanowi centrale ceny, którą drzewo LSM płaci za szybkie pisania. Wyszukiwania z zakresem, które pytają o wszystkie klucze między dwoma granicami, stoją przed podobnym wyzwaniem: silnik musi łączyć wyniki z memtable oraz każdej SS tabeli, która jest relevancka, biorąc najnowszą wersję każdego klucza, który pojawia się więcej niż raz, co stanowi więcej pracy niż pojedyncze uporządkowane przejście przez jedno struktury B-tree.

Filtry Blooma: Pominanie plików, które nie mogą zawierać klucza

Sprawdzanie każdego SSTable przy każdym odczycie stanie się niewygodnie wolne po upływie kilku dni. Standardowym rozwiązaniem jest filtr Blooma, mała i ekonomiczna struktura danych probabilistyczna tworzona razem z każdym SSTable podczas pisania. Filtr Blooma może szybko i prawie bez użycia pamięci odpowiedzieć na jedno pytanie: czy istnieje szansę, że ta klucz występuje w tym pliku?Filtr Blooma działa poprzez haszenie klucza za pomocą wielu niezależnych funkcji haszujących i ustawianie odpowiednich bitów w tablicy bitowej na jedynkę. Aby sprawdzić, czy klucz może być obecny, te same funkcje haszujące są ponownie zastosowane, a silnik sprawdza, czy wszystkie odpowiednie bity są ustawione. Jeśli nawet jeden bit jest zerowy, klucz jest na pewno nie w tym pliku, i plik można pominąć całkowicie bez dotarcia do dysku. Jeśli wszystkie bity okazują się być ustawione, klucz może być obecny, więc silnik musi rzeczywiście odczytać indeks pliku, aby potwierdzić to, co niesporadycznie oznacza odbior niepotrzebnej operacji zwanej fałszywym pozytywem. Krytycznie, filtr Blooma nigdy nie tworzy fałszywych negatywów: nigdy nie stwierdzi, że klucz jest brakujący, gdy na prawdę jest tam.Beerzeczko i ekonomiczność filtrów Blooma, często tylko kilka bitów na klucz, pozwalają je przechowywać w pamięci nawet gdy podstawowe pliki SSTable są zbyt duże do buforowania. To pozwala bazy danych pominąć większość niewymiarowych plików na dysku przy jednym szybkim sprawdzeniu w pamięci, znacznie obniżając powiększenie odczytu opisane wcześniej bez renuncjacji na żadne z korzyści dla strony pisania projektu LSM.Średnica fałszywych pozytywnych jest dostosowalna: przydzielanie więcej bitów na klucz prowadzi do mniejszej liczby odbiorów niepotrzebnych, ale z kosztem większej pamięci, dlatego operacjonerzy mogą wymieniać pamięć za opóźnienie w odczytach w zależności od ich obciążenia roboczego.

Kompresja: Merging SSTables i Przeznaczenie Kompromisu między Drzewem B-Tree

Kompresja jest tłem procesu, który utrzymuje drzewo LSM zdrowym w czasie. Okresowo wybiera on zestaw SSTable, łączy je w nowe, większe SSTable i usuwa oryginały. Podczas łączenia, gdy ten sam klucz pojawia się w wielu plikach wejściowych, zachowuje się tylko najnowsza wersja, a kamienie grobu można w końcu usunąć, gdy silnik jest pewny, że żaden starszy SSTable nie nadal przechowuje danych, które powinny być ukryte. To zwalnia miejsce na dysku i zmniejsza liczbę plików, których przyszłe odczyty muszą sprawdzić, co bezpośrednio obniża intensyfikację odczytu. Kompresja ma jednak swoje koszty. Zajmuje ona czas I/O dyskowy i CPU do ponownego zapisu danych, które już raz były zapisane, co nazywa się intensyfikacją pisania: pojedyncze logiczne zapisy mogą być w końcu ponownie zapisywane wielokrotnie podczas kolejnych rund kompresji. Różne silniki planują kompresję inaczej, na przykład strategie stopniowo rozmiarowe, które łączą pliki o podobnym rozmiarze, lub strategie poziomowe, które organizują SSTable w poziomy z rosnącym rozmiarem, ale wszystkie one zarządzają tą samą podstawową równowagą między liczbą akumulujących się plików a ilością ponownego zapisu potrzebnego do utrzymania tej liczby na niskim poziomie. Oto gdzie porównanie do drzewa B-Tree staje się konkretne. Indeks drzewa B+ aktualizuje dane w miejscu: zapis oznacza znalezienie właściwej strony liści i bezpośredniego modyfikowania jej, co utrzymuje koszt odczytu przewidywalnym i niskim, typowo jedno przejrzenie do pojedynczego aktualizowanego miejsca, ale sprawia, że losowe zapisy są drogimi, ponieważ każdy może dotknąć innego, przypadkowo położonego strony dysku. Drzewo LSM odwraca to całkowicie: zapisy są sekwencyjne i tanie, dowolne miejsce jest dozwolone, ponieważ nic nie jest szukane w miejscu, ale odczyty muszą potencjalnie sprawdzić wiele lokalizacji i polegać na tłem kompresji, aby utrzymać tę liczbę ograniczoną. Niektóre zarysowne projekty nie są stricte lepsze; drzewo LSM jest często wykorzystywane w obciążeniach zintensyfikowanej pisemnej pracy, takich jak inwentaryzacja logów lub dane serii czasowej, podczas gdy obciążenia zintensyfikowane odczytowej pracy z mało zapisami często preferują drzewa B-Tree. Wybór silnika przechowywania jest naprawdę wyborem między kosztami intensyfikacji odczytu i nakładów tła kompresji, a kosztem losowego zapisu.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz LSM Tree: How Cassandra, RocksDB, and LevelDB Write Fast i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.