Jesienią 2019 roku w zespole Mail.ru Cloud iOS miało miejsce długo oczekiwane wydarzenie. Główna baza danych służąca do trwałego przechowywania stanu aplikacji stała się bardzo egzotyczna w mobilnym świecie (LMDB). Poniżej kroju przedstawiamy Wam jego szczegółową recenzję w czterech częściach. Najpierw porozmawiajmy o powodach tak nietrywialnego i trudnego wyboru. Następnie przejdziemy do rozważenia trzech filarów będących sercem architektury LMDB: plików mapowanych w pamięci, drzewa B+, podejścia kopiowania przy zapisie w celu implementacji transakcyjności i wielowersji. Na koniec na deser część praktyczna. Przyjrzymy się w nim, jak zaprojektować i zaimplementować schemat bazy danych z kilkoma tabelami, w tym jedną indeksową, nad niskopoziomowym interfejsem API typu klucz-wartość.
Zawartość
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Motywacja do wdrożenia
Pewnego roku w 2015 roku zadaliśmy sobie trud zmierzenia częstotliwości opóźnień interfejsu naszej aplikacji. Zrobiliśmy to z jakiegoś powodu. Coraz częściej otrzymujemy skargi, że czasami aplikacja przestaje reagować na działania użytkownika: nie można nacisnąć przycisków, nie przewijają się listy itp. O mechanice pomiarów na AvitoTech, więc tutaj podaję tylko kolejność liczb.
Wyniki pomiarów stały się dla nas zimnym prysznicem. Okazało się, że problemów spowodowanych zamrożeniem jest znacznie więcej niż jakichkolwiek innych. Jeśli przed uświadomieniem sobie tego faktu główny techniczny wskaźnik jakości był bezawaryjny, to po skupieniu bez zamrażania.
Po zbudowaniu i po wydawaniu и Analiza ich przyczyn ujawniła, że główny wróg stał się jasny – ciężka logika biznesowa realizowana w głównym wątku aplikacji. Naturalną reakcją na tę hańbę było palące pragnienie wepchnięcia jej do strumieni pracy. Aby systematycznie rozwiązywać ten problem, sięgnęliśmy po architekturę wielowątkową opartą na lekkich aktorach. Poświęciłem go adaptacji na świat iOS na zbiorowym Twitterze i . W ramach obecnej narracji chcę podkreślić te aspekty decyzji, które wpłynęły na wybór bazy danych
Aktorski model organizacji systemu zakłada, że jego drugą istotą staje się wielowątkowość. Obiekty modelu w nim lubią przekraczać granice strumieni. I nie robią tego czasami i tu i tam, ale prawie stale i wszędzie
Baza danych jest jednym z kluczowych elementów prezentowanego diagramu. Jego głównym zadaniem jest implementacja makrowzoru . Jeśli w świecie korporacyjnym służy do organizowania synchronizacji danych pomiędzy usługami, to w przypadku architektury aktora – danych pomiędzy wątkami. Tym samym potrzebowaliśmy bazy danych, która nie sprawiłaby nawet minimalnych trudności podczas pracy z nią w środowisku wielowątkowym. W szczególności oznacza to, że uzyskane z niego obiekty muszą być co najmniej bezpieczne dla wątków, a najlepiej całkowicie niezmienne. Jak wiadomo, tego ostatniego można używać jednocześnie z kilku wątków bez uciekania się do jakiegokolwiek blokowania, co ma korzystny wpływ na wydajność.
Drugim istotnym czynnikiem, który wpłynął na wybór bazy danych było nasze API w chmurze. Został zainspirowany podejściem do synchronizacji przyjętym przez git. Podobnie jak on, dążyliśmy do , co wydaje się bardziej niż odpowiednie dla klientów w chmurze. Zakładano, że pełny stan chmury wypompują tylko raz, a następnie synchronizacja w zdecydowanej większości przypadków nastąpi poprzez wdrożenie zmian. Niestety, ta szansa jest nadal tylko w strefie teoretycznej, a klienci nie nauczyli się pracować z łatami w praktyce. Istnieje wiele obiektywnych powodów, które, aby nie opóźniać wprowadzenia, pozostawimy nawiasy. Teraz o wiele bardziej interesujące są pouczające wnioski z lekcji na temat tego, co się dzieje, gdy interfejs API mówi „A”, a jego konsument nie mówi „B”.
Jeśli więc wyobrazisz sobie gita, który wykonując polecenie pull, zamiast nakładać łatki na lokalną migawkę, porównuje swój pełny stan z pełnym stanem serwera, to będziesz miał w miarę dokładne wyobrażenie o tym, jak przebiega synchronizacja w chmurze klienci. Łatwo się domyślić, że aby to zaimplementować, trzeba przydzielić w pamięci dwa drzewa DOM zawierające metainformacje o wszystkich plikach serwerowych i lokalnych. Okazuje się, że jeśli użytkownik przechowuje w chmurze 500 tysięcy plików, to aby je zsynchronizować, konieczne jest odtworzenie i zniszczenie dwóch drzew zawierających 1 milion węzłów. Ale każdy węzeł jest agregatem zawierającym wykres podobiektów. W tym świetle oczekiwano wyników profilowania. Okazało się, że nawet bez uwzględnienia algorytmu scalania sama procedura tworzenia, a następnie niszczenia ogromnej liczby małych obiektów kosztuje całkiem grosza.Sytuację pogarsza fakt, że podstawowa operacja synchronizacji jest zawarta w dużej liczbie skryptów użytkownika. W rezultacie ustalamy drugie ważne kryterium wyboru bazy danych - możliwość realizacji operacji CRUD bez dynamicznej alokacji obiektów.
Pozostałe wymagania są bardziej tradycyjne i ich cała lista wygląda następująco.
- Bezpieczeństwo nici.
- Przetwarzanie wieloprocesowe. Podyktowane chęcią wykorzystania tej samej instancji bazy danych do synchronizacji stanu nie tylko pomiędzy wątkami, ale także pomiędzy główną aplikacją a rozszerzeniami iOS.
- Możliwość reprezentowania przechowywanych jednostek jako obiektów niemodyfikowalnych
- Brak alokacji dynamicznych w ramach operacji CRUD.
- Obsługa transakcji dla podstawowych nieruchomości : atomowość, spójność, izolacja i niezawodność.
- Szybkość w najpopularniejszych przypadkach.
Przy takim zestawie wymagań SQLite był i pozostaje dobrym wyborem. Jednak w ramach badania alternatyw natknąłem się na książkę . Pod jej kierownictwem napisano benchmark porównujący szybkość pracy z różnymi bazami danych w rzeczywistych scenariuszach chmurowych. Efekt przekroczył nasze najśmielsze oczekiwania. W najpopularniejszych przypadkach – uzyskania kursora na posortowanej liście wszystkich plików i posortowanej liście wszystkich plików dla danego katalogu – LMDB okazał się 10 razy szybszy niż SQLite. Wybór stał się oczywisty.
2. Pozycjonowanie LMDB
LMDB to bardzo mała biblioteka (tylko 10 tys. wierszy), która implementuje najniższą podstawową warstwę baz danych – pamięć masową.
Powyższy diagram pokazuje, że porównanie LMDB z SQLite, który również implementuje wyższe poziomy, generalnie nie jest bardziej poprawne niż SQLite z Core Data. Bardziej sprawiedliwe byłoby przytoczenie tych samych silników pamięci masowej, które stosują równi konkurenci - BerkeleyDB, LevelDB, Sophia, RocksDB itp. Istnieją nawet rozwiązania, w których LMDB działa jako komponent silnika pamięci masowej dla SQLite. Pierwszy taki eksperyment odbył się w 2012 roku przez LMDB . okazał się na tyle intrygujący, że jego inicjatywa została podchwycona przez entuzjastów OSS i znalazła swoją kontynuację w osobie . W styczniu 2020 autorem tego projektu był Den Shearer to na LinuxConfAu.
LMDB jest używany głównie jako silnik baz danych aplikacji. Biblioteka swój wygląd zawdzięcza twórcom , którzy byli bardzo niezadowoleni z BerkeleyDB jako podstawy ich projektu. Zaczynając od skromnej biblioteki , Howard Chu był w stanie stworzyć jedną z najpopularniejszych alternatyw naszych czasów. Poświęcił swój bardzo fajny raport tej historii, a także wewnętrznej strukturze LMDB. . Dobrym przykładem zdobycia magazynu był Leonid Juriew (alias ) z Positive Technologies w swoim raporcie na Highload 2015 . Opowiada w nim o LMDB w kontekście podobnego zadania, jakim jest wdrożenie ReOpenLDAP, a LevelDB był już przedmiotem krytyki porównawczej. W wyniku wdrożenia firma Positive Technologies miała nawet aktywnie rozwijający się fork z bardzo smacznymi funkcjami, optymalizacjami i .
LMDB jest często używany jako magazyn w stanie takim, w jakim jest. Na przykład przeglądarka Mozilla Firefox go do wielu potrzeb, a począwszy od wersji 9, Xcode jego SQLite do przechowywania indeksów.
Silnik odcisnął swoje piętno również w świecie rozwoju urządzeń mobilnych. Mogą znajdować się ślady jego użytkowania w kliencie iOS dla Telegramu. LinkedIn poszedł jeszcze dalej i wybrał LMDB jako domyślną pamięć masową dla własnej platformy buforowania danych Rocket Data, o której w swoim artykule z 2016 r.
LMDB skutecznie walczy o miejsce w słońcu w niszy pozostawionej przez BerkeleyDB po przejęciu przez Oracle. Biblioteka jest uwielbiana za szybkość i niezawodność, nawet w porównaniu z innymi bibliotekami. Jak wiadomo, darmowych obiadów nie ma i chciałbym podkreślić kompromis, z jakim trzeba będzie się zmierzyć przy wyborze pomiędzy LMDB a SQLite. Powyższy diagram wyraźnie pokazuje, w jaki sposób osiągana jest zwiększona prędkość. Po pierwsze, nie płacimy za dodatkowe warstwy abstrakcji na dysku. Wiadomo, że dobra architektura nadal nie może się bez nich obejść i nieuchronnie pojawią się one w kodzie aplikacji, ale będą znacznie subtelniejsze. Nie będą zawierały funkcji, które nie są wymagane przez konkretną aplikację, np. obsługi zapytań w języku SQL. Po drugie, możliwa staje się optymalna implementacja mapowania operacji aplikacji na żądaniach do pamięci dyskowej. Jeśli SQLite opiera się na średnich potrzebach statystycznych przeciętnej aplikacji, wówczas jako programista aplikacji doskonale zdajesz sobie sprawę z głównych scenariuszy obciążenia. Aby uzyskać bardziej produktywne rozwiązanie, będziesz musiał zapłacić wyższą cenę zarówno za opracowanie początkowego rozwiązania, jak i za jego późniejsze wsparcie.
3. Trzy filary LMDB
Po spojrzeniu na LMDB z lotu ptaka przyszedł czas na głębsze spojrzenie. Kolejne trzy sekcje zostaną poświęcone analizie głównych filarów, na których opiera się architektura pamięci masowej:
- Pliki mapowane w pamięci jako mechanizm pracy z dyskiem i synchronizacji wewnętrznych struktur danych.
- Drzewo B+ jako organizacja struktury przechowywanych danych.
- Kopiowanie przy zapisie jako podejście zapewniające właściwości transakcji ACID i wielowersję.
3.1. Wieloryb nr 1. Pliki mapowane w pamięci
Pliki mapowane w pamięci są na tyle ważnym elementem architektonicznym, że pojawiają się nawet w nazwie repozytorium. Kwestie buforowania i synchronizacji dostępu do przechowywanych informacji są całkowicie pozostawione systemowi operacyjnemu. LMDB nie zawiera w sobie żadnych pamięci podręcznych. Jest to świadoma decyzja autora, ponieważ odczyt danych bezpośrednio z mapowanych plików pozwala na znaczne oszczędności w implementacji silnika. Poniżej znajduje się niepełna lista niektórych z nich.
- Utrzymanie spójności danych w magazynie podczas pracy z nimi z kilku procesów staje się obowiązkiem systemu operacyjnego. W następnej części mechanika ta została szczegółowo omówiona wraz z ilustracjami.
- Brak pamięci podręcznych całkowicie eliminuje LMDB z kosztów związanych z alokacjami dynamicznymi. Odczyt danych w praktyce oznacza ustawienie wskaźnika na właściwy adres w pamięci wirtualnej i nic więcej. Brzmi to jak science fiction, ale w kodzie źródłowym pamięci wszystkie wywołania calloc skupiają się na funkcji konfiguracji pamięci.
- Brak pamięci podręcznych oznacza także brak blokad związanych z synchronizacją ich dostępu. Czytniki, których może być jednocześnie dowolna liczba czytelników, w drodze do danych nie napotykają ani jednego muteksu. Dzięki temu prędkość odczytu ma idealną skalowalność liniową w oparciu o liczbę procesorów. W LMDB synchronizowane są tylko operacje modyfikujące. W danym momencie może być tylko jeden pisarz.
- Minimalna logika buforowania i synchronizacji eliminuje niezwykle złożony typ błędów związanych z pracą w środowisku wielowątkowym. Na konferencji Usenix OSDI 2014 przeprowadzono dwa interesujące badania baz danych: и . Można z nich wyciągnąć informacje zarówno o niespotykanej dotąd niezawodności LMDB, jak i o niemal bezbłędnej implementacji właściwości transakcyjnych ACID, przewyższającej tę w SQLite.
- Minimalizm LMDB pozwala na całkowite umieszczenie maszynowej reprezentacji jego kodu w pamięci podręcznej L1 procesora z wynikającą z tego charakterystyką szybkości.
Niestety w iOS, przy plikach mapowanych w pamięci, nie wszystko jest tak bezchmurne, jak byśmy tego chcieli. Aby bardziej świadomie mówić o niedociągnięciach z nimi związanych, należy pamiętać o ogólnych zasadach implementacji tego mechanizmu w systemach operacyjnych.
Ogólne informacje o plikach mapowanych w pamięci
Z każdą uruchomioną aplikacją system operacyjny kojarzy jednostkę zwaną procesem. Każdemu procesowi przydzielany jest ciągły zakres adresów, w których umieszcza wszystko, czego potrzebuje do działania. Pod najniższymi adresami znajdują się sekcje z kodem oraz zakodowanymi na stałe danymi i zasobami. Następny jest rosnący blok dynamicznej przestrzeni adresowej, dobrze znany nam pod nazwą sterty. Zawiera adresy podmiotów, które pojawiają się podczas działania programu. Na górze znajduje się obszar pamięci używany przez stos aplikacji. Albo rośnie, albo kurczy się, innymi słowy, jego wielkość ma także charakter dynamiczny. Aby zapobiec wzajemnemu pchaniu i zakłócaniu się stosu i sterty, znajdują się one na różnych końcach przestrzeni adresowej. Pomiędzy dwiema dynamicznymi sekcjami u góry i u dołu znajduje się dziura. System operacyjny używa adresów w tej środkowej części do skojarzenia różnych podmiotów z procesem. W szczególności może powiązać pewien ciągły zestaw adresów z plikiem na dysku. Taki plik nazywany jest mapą pamięci
Przestrzeń adresowa przydzielona procesowi jest ogromna. Teoretycznie liczba adresów jest ograniczona jedynie wielkością wskaźnika, która jest określona przez pojemność bitową systemu. Gdyby pamięć fizyczna została zmapowana w stosunku 1 do 1, to już pierwszy proces pochłonąłby całą pamięć RAM i nie byłoby mowy o wielozadaniowości.
Jednak z naszego doświadczenia wiemy, że nowoczesne systemy operacyjne mogą jednocześnie wykonywać dowolną liczbę procesów. Jest to możliwe dzięki temu, że przydzielają dużo pamięci procesom tylko na papierze, ale w rzeczywistości ładują do głównej pamięci fizycznej tylko tę część, która jest potrzebna tu i teraz. Dlatego pamięć związaną z procesem nazywa się wirtualną.
System operacyjny organizuje pamięć wirtualną i fizyczną w strony o określonym rozmiarze. Gdy tylko określona strona pamięci wirtualnej jest potrzebna, system operacyjny ładuje ją do pamięci fizycznej i dopasowuje do specjalnej tabeli. Jeśli nie ma wolnych miejsc, jedna z wcześniej załadowanych stron zostanie skopiowana na dysk, a na jej miejsce zajmie żądana. Ta procedura, do której wkrótce powrócimy, nazywa się zamianą. Poniższy rysunek ilustruje opisany proces. Na nim została załadowana strona A o adresie 0 i umieszczona na stronie pamięci głównej o adresie 4. Fakt ten znalazł odzwierciedlenie w tabeli korespondencji w komórce nr 0.
Historia jest dokładnie taka sama w przypadku plików mapowanych do pamięci. Logicznie rzecz biorąc, są one rzekomo stale i całkowicie zlokalizowane w wirtualnej przestrzeni adresowej. Jednakże wchodzą do pamięci fizycznej strona po stronie i tylko na żądanie. Modyfikacja takich stron jest synchronizowana z plikiem na dysku. W ten sposób możesz wykonywać operacje we/wy pliku, po prostu pracując z bajtami w pamięci - wszystkie zmiany zostaną automatycznie przeniesione przez jądro systemu operacyjnego do pliku źródłowego.
â € <
Poniższy obraz pokazuje, jak LMDB synchronizuje swój stan podczas pracy z bazą danych z różnych procesów. Mapując pamięć wirtualną różnych procesów do tego samego pliku, de facto zobowiązujemy system operacyjny do przejściowej synchronizacji między sobą określonych bloków ich przestrzeni adresowych, gdzie szuka LMDB.
â € <
Ważnym niuansem jest to, że LMDB domyślnie modyfikuje plik danych poprzez mechanizm zapisu wywołań systemowych i wyświetla sam plik w trybie tylko do odczytu. Podejście to ma dwie istotne konsekwencje.
Pierwsza konsekwencja jest wspólna dla wszystkich systemów operacyjnych. Jego istotą jest dodanie ochrony przed niezamierzonym uszkodzeniem bazy danych przez błędny kod. Jak wiadomo, instrukcje wykonywalne procesu mają swobodny dostęp do danych z dowolnego miejsca w jego przestrzeni adresowej. Jednocześnie, jak właśnie przypomnieliśmy, wyświetlenie pliku w trybie odczytu i zapisu oznacza, że dowolna instrukcja może go również modyfikować. Jeśli zrobi to przez pomyłkę, próbując np. faktycznie nadpisać element tablicy pod nieistniejącym indeksem, to może przypadkowo zmienić plik mapowany na ten adres, co doprowadzi do uszkodzenia bazy danych. Jeśli plik zostanie wyświetlony w trybie tylko do odczytu, próba zmiany odpowiedniej przestrzeni adresowej doprowadzi do awaryjnego zakończenia programu sygnałem SIGSEGV, a plik pozostanie nienaruszony.
Druga konsekwencja jest już specyficzna dla iOS. Ani autor, ani żadne inne źródła nie wspominają o tym wprost, ale bez tego LMDB nie nadawałby się do działania na tym mobilnym systemie operacyjnym. Dalszy rozdział poświęcony jest jego rozważaniom.
Specyfika plików mapowanych w pamięci w systemie iOS
W 2018 roku na WWDC pojawił się wspaniały raport . Mówi nam, że w iOS wszystkie strony znajdujące się w pamięci fizycznej są jednego z 3 typów: brudne, skompresowane i czyste.
Czysta pamięć to zbiór stron, które można bezboleśnie wyładować z pamięci fizycznej. Dane w nich zawarte można w razie potrzeby ponownie załadować z oryginalnych źródeł. Do tej kategorii należą pliki mapowane w pamięci tylko do odczytu. iOS nie boi się w dowolnym momencie wyładować z pamięci stron zmapowanych do pliku, ponieważ gwarantuje się ich synchronizację z plikiem na dysku.
â € <
Wszystkie zmodyfikowane strony trafiają do brudnej pamięci, niezależnie od tego, gdzie pierwotnie się znajdowały. W szczególności pliki mapowane w pamięci modyfikowane poprzez zapis do powiązanej z nimi pamięci wirtualnej będą klasyfikowane w ten sposób. Otwarcie LMDB z flagą MDB_WRITEMAP, po dokonaniu w nim zmian, możesz to zweryfikować osobiście.
Gdy tylko aplikacja zacznie zajmować zbyt dużo pamięci fizycznej, iOS poddaje ją kompresji brudnej strony. Całkowita pamięć zajmowana przez brudne i skompresowane strony stanowi tzw. ślad pamięci aplikacji. Po osiągnięciu określonej wartości progowej demon systemu OOM Killer pojawia się po procesie i wymusza jego zakończenie. Na tym polega specyfika systemu iOS w porównaniu z systemami operacyjnymi dla komputerów stacjonarnych. Natomiast zmniejszenie zużycia pamięci poprzez zamianę stron z pamięci fizycznej na dysk nie jest możliwe w iOS, a przyczyn można się jedynie domyślać. Być może procedura intensywnego przenoszenia stron na dysk i z powrotem jest zbyt energochłonna dla urządzeń mobilnych, albo iOS oszczędza zasób przepisywania komórek na dyskach SSD, a może projektanci nie byli zadowoleni z ogólnej wydajności systemu, w którym wszystko jest stale zamieniane. Tak czy inaczej, fakt pozostaje faktem.
Dobra wiadomość, o której już wspominaliśmy, jest taka, że LMDB domyślnie nie używa mechanizmu mmap do aktualizacji plików. Oznacza to, że wyświetlane dane są klasyfikowane przez iOS jako czysta pamięć i nie wpływają na zużycie pamięci. Możesz to sprawdzić za pomocą narzędzia Xcode o nazwie VM Tracker. Poniższy zrzut ekranu przedstawia stan pamięci wirtualnej iOS aplikacji Cloud podczas pracy. Na początku zostały w nim zainicjowane 2 instancje LMDB. Pierwszy mógł wyświetlić swój plik na 1GiB pamięci wirtualnej, drugi – 512MiB. Pomimo faktu, że oba magazyny zajmują pewną ilość pamięci rezydentnej, żaden z nich nie wnosi dużego rozmiaru.
A teraz czas na złe wieści. Dzięki mechanizmowi wymiany w 64-bitowych systemach operacyjnych dla komputerów stacjonarnych każdy proces może zajmować tyle wirtualnej przestrzeni adresowej, na ile pozwala wolne miejsce na dysku twardym na jego potencjalną zamianę. Zastąpienie wymiany kompresją w iOS radykalnie zmniejsza teoretyczne maksimum. Teraz wszystkie żywe procesy muszą zmieścić się w pamięci głównej (czytaj RAM), a wszystkie te, które się nie mieszczą, muszą zostać zmuszone do zakończenia. Jest to określone tak, jak wskazano powyżej a w . W rezultacie iOS poważnie ogranicza ilość pamięci dostępnej do alokacji za pośrednictwem mmap. Tutaj Możesz sprawdzić empiryczne ograniczenia ilości pamięci, którą można przydzielić różnym urządzeniom za pomocą tego wywołania systemowego. W najnowocześniejszych modelach smartfonów iOS stał się hojny o 2 gigabajty, a na topowych wersjach iPada - o 4. W praktyce trzeba oczywiście skupić się na najniższych obsługiwanych modelach urządzeń, gdzie wszystko jest bardzo smutne. Co gorsza, patrząc na stan pamięci aplikacji w VM Trackerze, odkryjesz, że LMDB nie jest jedyną bazą podającą się za mapowaną pamięć. Dobre kawałki są zjadane przez systemowe alokatory, pliki zasobów, frameworki obrazów i inne mniejsze drapieżniki.
Na podstawie wyników eksperymentów w Chmurze doszliśmy do następujących wartości kompromisowych dla pamięci przydzielanej przez LMDB: 384 megabajty dla urządzeń 32-bitowych i 768 dla urządzeń 64-bitowych. Po wykorzystaniu tego wolumenu wszelkie operacje modyfikujące zaczynają się kończyć na kodzie MDB_MAP_FULL. Takie błędy obserwujemy w naszym monitoringu, są one jednak na tyle małe, że na tym etapie można je pominąć.
Nieoczywistą przyczyną nadmiernego zużycia pamięci przez magazyn mogą być transakcje o długim czasie trwania. Aby zrozumieć, w jaki sposób te dwa zjawiska są ze sobą powiązane, pomoże nam rozważenie pozostałych dwóch filarów LMDB.
3.2. Wieloryb #2. B+-drzewo
Aby emulować tabele na bazie magazynu klucz-wartość, w jego interfejsie API muszą być obecne następujące operacje:
- Wstawienie nowego elementu.
- Wyszukaj element o podanym kluczu.
- Usuwanie elementu.
- Iteruj po odstępach kluczy w kolejności ich sortowania.
Najprostszą strukturą danych, która może łatwo wdrożyć wszystkie cztery operacje, jest drzewo wyszukiwania binarnego. Każdy z jego węzłów reprezentuje klucz, który dzieli cały podzbiór kluczy podrzędnych na dwa poddrzewa. Lewy zawiera te, które są mniejsze od rodzica, a prawy te, które są większe. Uzyskanie uporządkowanego zestawu kluczy następuje poprzez jedno z klasycznych przejść po drzewie
Drzewa binarne mają dwie podstawowe wady, które uniemożliwiają im skuteczność jako struktury danych opartej na dysku. Po pierwsze, stopień ich równowagi jest nieprzewidywalny. Istnieje duże ryzyko uzyskania drzew, w których wysokość poszczególnych gałęzi może znacznie się różnić, co znacznie pogarsza złożoność algorytmiczną wyszukiwania w stosunku do oczekiwanych. Po drugie, obfitość powiązań między węzłami pozbawia drzewa binarne lokalności w pamięci.Bliskie węzły (w zakresie połączeń między nimi) mogą być zlokalizowane na zupełnie innych stronach pamięci wirtualnej. W konsekwencji nawet proste przejście kilku sąsiednich węzłów w drzewie może wymagać odwiedzenia porównywalnej liczby stron. Jest to problem nawet wtedy, gdy mówimy o efektywności drzew binarnych jako struktury danych w pamięci, ponieważ ciągłe obracanie stron w pamięci podręcznej procesora nie jest tanią przyjemnością. Jeśli chodzi o częste pobieranie z dysku stron powiązanych z węzłami, sytuacja staje się kompletna .
Drzewa B, będące ewolucją drzew binarnych, rozwiązują problemy zidentyfikowane w poprzednim akapicie. Po pierwsze, utrzymują równowagę. Po drugie, każdy z ich węzłów dzieli zbiór kluczy podrzędnych nie na 2, ale na M uporządkowanych podzbiorów, a liczba M może być dość duża, rzędu kilkuset, a nawet tysięcy.
A tym samym:
- Każdy węzeł zawiera dużą liczbę już zamówionych kluczy, a drzewa są bardzo krótkie.
- Drzewo nabywa właściwość lokalizacji lokalizacji w pamięci, ponieważ klucze o zbliżonej wartości naturalnie znajdują się obok siebie w tych samych lub sąsiednich węzłach.
- Liczba węzłów tranzytowych podczas schodzenia z drzewa podczas operacji wyszukiwania jest zmniejszona.
- Liczba węzłów docelowych odczytywanych podczas zapytań o zakres jest zmniejszona, ponieważ każdy z nich zawiera już dużą liczbę uporządkowanych kluczy.
LMDB używa do przechowywania danych odmiany drzewa B zwanej drzewem B+. Powyższy diagram pokazuje trzy typy węzłów, które w nim występują:
- Na górze znajduje się korzeń. Urzeczywistnia to nic innego jak koncepcję bazy danych wewnątrz magazynu. W ramach jednej instancji LMDB można utworzyć kilka baz danych współdzielących zmapowaną wirtualną przestrzeń adresową. Każdy z nich zaczyna się od własnego korzenia.
- Na najniższym poziomie znajdują się liście. One i tylko one zawierają pary klucz-wartość przechowywane w bazie danych. Nawiasem mówiąc, jest to osobliwość drzew B+. Jeśli zwykłe drzewo B przechowuje części wartościowe w węzłach wszystkich poziomów, wówczas odmiana B+ występuje tylko na najniższym. Po ustaleniu tego faktu będziemy dalej nazywać podtyp drzewa używany w LMDB po prostu drzewem B.
- Pomiędzy korzeniem a liśćmi znajduje się 0 lub więcej poziomów technicznych z węzłami nawigacyjnymi (gałęziowymi). Ich zadaniem jest podzielenie posortowanego zestawu kluczy pomiędzy kartki.
Fizycznie węzły są blokami pamięci o określonej długości. Ich rozmiar jest wielokrotnością rozmiaru stron pamięci w systemie operacyjnym, o którym mówiliśmy powyżej. Poniżej pokazano strukturę węzła. Nagłówek zawiera metainformacje, z których najbardziej oczywistą jest na przykład suma kontrolna. Następnie pojawia się informacja o przesunięciach, w jakich znajdują się komórki z danymi. Dane mogą mieć postać kluczy, jeśli mówimy o węzłach nawigacyjnych, lub całych par klucz-wartość w przypadku liści. Więcej o strukturze stron przeczytasz w pracy .
Po zajęciu się wewnętrzną zawartością węzłów strony, drzewo B LMDB będziemy dalej przedstawiać w uproszczony sposób w poniższej formie.
Strony z węzłami są lokalizowane sekwencyjnie na dysku. Strony o wyższych numerach znajdują się na końcu pliku. Tak zwana metastrona zawiera informacje o przesunięciach, według których można znaleźć korzenie wszystkich drzew. Podczas otwierania pliku LMDB skanuje plik strona po stronie od końca do początku w poszukiwaniu prawidłowej metastrony i poprzez to znajduje istniejące bazy danych.
Teraz, mając pojęcie o logicznej i fizycznej strukturze organizacji danych, możemy przejść do rozważenia trzeciego filaru LMDB. To z jego pomocą wszystkie modyfikacje pamięci zachodzą transakcyjnie i w izolacji od siebie, nadając bazie danych jako całości właściwość wielowersji.
3.3. Wieloryb nr 3. Kopiuj przy zapisie
Niektóre operacje na drzewie B wymagają wprowadzenia szeregu zmian w jego węzłach. Jednym z przykładów jest dodanie nowego klucza do węzła, który osiągnął już maksymalną pojemność. W tym przypadku konieczne jest, po pierwsze, podzielenie węzła na dwa, a po drugie, dodanie łącza do nowego, rozwijającego się węzła potomnego w jego rodzicu. Ta procedura jest potencjalnie bardzo niebezpieczna. Jeśli z jakiegoś powodu (awaria, przerwa w dostawie prądu itp.) nastąpi tylko część zmian z serii, wówczas drzewo pozostanie w niespójnym stanie.
Tradycyjnym rozwiązaniem zapewniającym odporność bazy danych na błędy jest dodanie dodatkowej struktury danych na dysku obok drzewa B — dziennika transakcji, znanego również jako dziennik zapisu z wyprzedzeniem (WAL). Jest to plik, na końcu którego zapisana jest zamierzona operacja, ściśle przed modyfikacją samego drzewa B. Dlatego też, jeśli podczas autodiagnostyki wykryte zostanie uszkodzenie danych, baza danych przegląda dziennik, aby uporządkować dane.
LMDB wybrało inną metodę jako swój mechanizm odporności na błędy, zwaną kopiowaniem przy zapisie. Jego istota polega na tym, że zamiast aktualizować dane na istniejącej stronie, najpierw kopiuje je w całości i wprowadza w kopii wszelkie modyfikacje.
Następnie, aby zaktualizowane dane były dostępne, należy zmienić łącze do węzła, które stało się aktualne w jego węźle nadrzędnym. Ponieważ w tym celu również należy go zmodyfikować, jest on również wcześniej kopiowany. Proces jest kontynuowany rekurencyjnie aż do korzenia. Ostatnią rzeczą do zmiany są dane na meta stronie
Jeśli nagle proces ulegnie awarii podczas procedury aktualizacji, to albo nie zostanie utworzona nowa metastrona, albo nie zostanie ona w całości zapisana na dysku, a jej suma kontrolna będzie niepoprawna. W każdym z tych dwóch przypadków nowe strony będą nieosiągalne, ale nie będzie to miało wpływu na stare. Eliminuje to potrzebę zapisywania przez LMDB dziennika z wyprzedzeniem w celu utrzymania spójności danych. De facto opisana powyżej struktura przechowywania danych na dysku jednocześnie przejmuje swoją funkcję. Brak jawnego dziennika transakcji jest jedną z cech LMDB, która zapewnia dużą prędkość odczytu danych
Powstały projekt, zwany drzewem B tylko do dołączania, w naturalny sposób zapewnia izolację transakcji i tworzenie wielu wersji. W LMDB każda otwarta transakcja jest powiązana z aktualnie odpowiednim korzeniem drzewa. Dopóki transakcja nie zostanie sfinalizowana, powiązane z nią strony drzewa nie zostaną nigdy zmienione ani ponownie wykorzystane do nowych wersji danych, dzięki czemu możesz pracować tak długo, jak chcesz, z dokładnie tym zestawem danych, który był w danym momencie istotny transakcja została otwarta, nawet jeśli w tym momencie pamięć jest nadal aktywnie aktualizowana. To właśnie jest istotą multiwersji, czyniącej LMDB idealnym źródłem danych dla naszych ukochanych UICollectionView. Po otwarciu transakcji nie ma potrzeby zwiększania zużycia pamięci aplikacji poprzez pośpieszne pompowanie bieżących danych do jakiejś struktury w pamięci, w obawie, że zostaną z niczym. Ta cecha odróżnia LMDB od tego samego SQLite, który nie może pochwalić się tak całkowitą izolacją. Po otwarciu dwóch transakcji w tym ostatnim i usunięciu określonego rekordu w ramach jednej z nich, nie będzie już możliwe uzyskanie tego samego rekordu w ramach drugiej pozostałej.
Odwrotną stroną medalu jest potencjalnie znacznie większe zużycie pamięci wirtualnej. Slajd pokazuje, jak będzie wyglądać struktura bazy danych, jeśli zostanie zmodyfikowana jednocześnie z 3 otwartymi transakcjami odczytu, przeglądającymi różne wersje bazy danych. Ponieważ LMDB nie może ponownie wykorzystać węzłów osiągalnych z korzeni powiązanych z bieżącymi transakcjami, sklep nie ma innego wyjścia, jak tylko przydzielić kolejny czwarty pierwiastek w pamięci i ponownie sklonować pod nim zmodyfikowane strony.
W tym miejscu warto przypomnieć sekcję dotyczącą plików mapowanych w pamięci. Wydaje się, że dodatkowe zużycie pamięci wirtualnej nie powinno nas zbytnio martwić, ponieważ nie wpływa na zużycie pamięci aplikacji. Jednocześnie jednak zauważono, że iOS jest bardzo skąpy w jego przydzielaniu i nie możemy, tak jak na serwerze czy komputerze stacjonarnym, udostępnić regionu LMDB o wielkości 1 terabajta i w ogóle nie myśleć o tej funkcji. Jeśli to możliwe, powinieneś starać się, aby czas życia transakcji był jak najkrótszy.
4. Projektowanie schematu danych na bazie API klucz-wartość
Rozpocznijmy naszą analizę API od spojrzenia na podstawowe abstrakcje dostarczane przez LMDB: środowisko i bazy danych, klucze i wartości, transakcje i kursory.
Uwaga dotycząca list kodów
Wszystkie funkcje w publicznym API LMDB zwracają wynik swojej pracy w postaci kodu błędu, jednak we wszystkich kolejnych zestawieniach dla zachowania zwięzłości pomijamy jego weryfikację. W praktyce do interakcji z repozytorium używaliśmy nawet własnych Opakowania C++ , w którym błędy materializują się jako wyjątki C++.
Jako najszybszy sposób połączenia LMDB z projektem na iOS lub macOS, sugeruję mój CocoaPod .
4.1. Podstawowe abstrakcje
Środowisko
Struktura MDB_env jest repozytorium stanu wewnętrznego LMDB. Rodzina funkcji z przedrostkiem mdb_env pozwala skonfigurować niektóre jego właściwości. W najprostszym przypadku inicjalizacja silnika wygląda następująco.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);W aplikacji Mail.ru Cloud zmieniliśmy domyślne wartości tylko dwóch parametrów.
Pierwszym z nich jest rozmiar wirtualnej przestrzeni adresowej, na którą mapowany jest plik pamięci. Niestety, nawet na tym samym urządzeniu konkretna wartość może się znacznie różnić w zależności od uruchomienia. Aby uwzględnić tę funkcję systemu iOS, maksymalna pojemność pamięci jest wybierana dynamicznie. Zaczynając od określonej wartości, jest ona kolejno zmniejszana o połowę, aż do osiągnięcia funkcji mdb_env_open nie zwróci wyniku innego niż ENOMEM. Teoretycznie jest też sposób odwrotny - najpierw przydziel silnikowi minimum pamięci, a potem, gdy pojawią się błędy, MDB_MAP_FULL, zwiększ to. Jest jednak o wiele bardziej drażliwy. Powodem jest procedura ponownego przydzielania pamięci (remapowania) za pomocą funkcji mdb_env_set_map_size unieważnia wszystkie elementy (kursory, transakcje, klucze i wartości) otrzymane wcześniej z silnika. Uwzględnienie takiego obrotu zdarzeń w kodzie doprowadzi do jego znacznych komplikacji. Jeśli jednak pamięć wirtualna jest dla Ciebie bardzo ważna, może to być powód, aby przyjrzeć się bliżej rozwidleniu, które zaszło daleko przed nami , gdzie wśród zapowiedzianych funkcji znajduje się „automatyczne dostosowywanie rozmiaru bazy danych w locie”.
Drugi parametr, którego wartość domyślna nam nie odpowiadała, reguluje mechanikę zapewnienia bezpieczeństwa gwintu. Niestety, przynajmniej iOS 10 ma problemy z obsługą lokalnego magazynu wątków. Z tego powodu w powyższym przykładzie repozytorium otwierane jest z flagą MDB_NOTLS. Poza tym było to również konieczne Opakowanie C++ aby wyciąć zmienne z tym atrybutem i w nim.
Bazy danych
Baza danych jest osobną instancją drzewa B, o czym mówiliśmy powyżej. Jego otwarcie następuje w ramach transakcji, co na pierwszy rzut oka może wydawać się nieco dziwne.
MDB_txn *txn;
MDB_dbi dbi;
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);
mdb_txn_abort(txn);Rzeczywiście, transakcja w LMDB jest jednostką przechowującą, a nie konkretną jednostką bazy danych. Koncepcja ta pozwala na wykonywanie niepodzielnych operacji na jednostkach znajdujących się w różnych bazach danych. Teoretycznie otwiera to możliwość modelowania tabel w postaci różnych baz danych, ale kiedyś wybrałem inną ścieżkę, opisaną szczegółowo poniżej.
Klucze i wartości
Struktura MDB_val modeluje koncepcję zarówno klucza, jak i wartości. Repozytorium nie ma pojęcia o ich semantyce. Dla niej czymś innym jest po prostu tablica bajtów o danym rozmiarze. Maksymalny rozmiar klucza wynosi 512 bajtów.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Za pomocą komparatora sklep sortuje klucze w kolejności rosnącej. Jeśli nie zastąpisz go własnym, zostanie użyty domyślny, który posortuje je bajt po bajcie w porządku leksykograficznym.
Transakcje
Struktura transakcji została szczegółowo opisana w , więc tutaj krótko powtórzę ich główne właściwości:
- Obsługuje wszystkie podstawowe właściwości : atomowość, spójność, izolacja i niezawodność. Nie mogę nie zauważyć, że w macOS i iOS występuje błąd dotyczący trwałości, który został naprawiony w MDBX. Więcej możesz przeczytać w ich .
- Podejście do wielowątkowości opisuje schemat „jeden pisarz / wielu czytelników”. Pisarze blokują się nawzajem, ale nie blokują czytelników. Czytelnicy nie blokują autorów ani siebie nawzajem.
- Obsługa transakcji zagnieżdżonych.
- Obsługa wielu wersji.
Multiwersja w LMDB jest na tyle dobra, że chcę ją zademonstrować w akcji. Z poniższego kodu widać, że każda transakcja działa dokładnie z tą wersją bazy danych, która była aktualna w momencie jej otwarcia, całkowicie odizolowana od wszelkich późniejszych zmian. Inicjowanie magazynu i dodanie do niego rekordu testowego nie wnosi nic ciekawego, więc te rytuały pozostawiamy pod spoilerem.
Dodanie wpisu testowego
MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;
mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);
mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);
char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;
int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;
mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);MDB_txn *txn1, *txn2, *txn3;
MDB_val val;
// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only
// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);
// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);
// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);Polecam wypróbować tę samą sztuczkę z SQLite i zobaczyć, co się stanie.
Multiwersja wnosi bardzo fajne korzyści w życie programisty iOS. Korzystając z tej właściwości, można łatwo i naturalnie dostosować częstotliwość aktualizacji źródła danych dla formularzy ekranowych, w oparciu o względy użytkownika. Weźmy na przykład funkcję aplikacji Mail.ru Cloud, taką jak automatyczne ładowanie treści z systemowej galerii multimediów. Przy dobrym połączeniu klient jest w stanie dodać do serwera kilka zdjęć na sekundę. Jeśli aktualizujesz po każdym pobraniu UICollectionView dzięki treściom multimedialnym w chmurze użytkownika możesz zapomnieć w trakcie tego procesu o 60 fps i płynnym przewijaniu. Aby zapobiec częstym aktualizacjom ekranu, musisz w jakiś sposób ograniczyć szybkość zmian danych w pliku bazowym UICollectionViewDataSource.
Jeśli baza danych nie obsługuje wielu wersji i pozwala pracować tylko z bieżącym stanem, to aby utworzyć stabilną w czasie migawkę danych, należy ją skopiować albo do jakiejś struktury danych w pamięci, albo do tabeli tymczasowej. Każde z tych podejść jest bardzo drogie. W przypadku przechowywania in-memory powstają koszty zarówno w pamięci, spowodowane przechowywaniem skonstruowanych obiektów, jak i w czasie, związane z redundantnymi transformacjami ORM. Jeśli chodzi o stół tymczasowy, jest to przyjemność jeszcze droższa, mająca sens tylko w nietrywialnych przypadkach.
Rozwiązanie wielowersyjne LMDB w bardzo elegancki sposób rozwiązuje problem utrzymania stabilnego źródła danych. Wystarczy otworzyć transakcję i voila – dopóki jej nie sfinalizujemy, mamy pewność, że zbiór danych będzie naprawiony. Logika szybkości aktualizacji jest teraz całkowicie w rękach warstwy prezentacji, bez narzutu znacznych zasobów.
Kursory
Kursory zapewniają mechanizm uporządkowanej iteracji po parach klucz-wartość poprzez przechodzenie przez drzewo B. Bez nich niemożliwe byłoby efektywne modelowanie tabel w bazie danych, do której teraz się zwracamy.
4.2. Modelowanie stołu
Właściwość porządkowania kluczy umożliwia konstruowanie abstrakcji wysokiego poziomu, takiej jak tabela na podstawie podstawowych abstrakcji. Rozważmy ten proces na przykładzie głównej tabeli klienta chmury, która buforuje informacje o wszystkich plikach i folderach użytkownika.
Schemat tabeli
Jednym z częstych scenariuszy, dla których należy dostosować strukturę tabeli z drzewem folderów, jest selekcja wszystkich elementów znajdujących się w danym katalogu.Dobrym modelem organizacji danych dla wydajnych zapytań tego typu jest . Aby zaimplementować go na wierzchu magazynu klucz-wartość, konieczne jest posortowanie kluczy plików i folderów w taki sposób, aby były pogrupowane na podstawie ich przynależności do katalogu nadrzędnego. Dodatkowo, aby wyświetlić zawartość katalogu w postaci znanej użytkownikowi systemu Windows (najpierw foldery, potem pliki, oba posortowane alfabetycznie), konieczne jest uwzględnienie w kluczu odpowiednich dodatkowych pól.
Poniższy rysunek pokazuje, jak w zależności od wykonywanego zadania może wyglądać reprezentacja kluczy w postaci tablicy bajtów. Najpierw umieszczane są bajty z identyfikatorem katalogu nadrzędnego (czerwony), następnie z typem (zielony), a na końcu z nazwą (niebieski).Posortowane według domyślnego komparatora LMDB w porządku leksykograficznym, są uporządkowane według wymagany sposób. Sekwencyjne przechodzenie przez klucze z tym samym czerwonym prefiksem daje nam skojarzone z nimi wartości w kolejności, w jakiej powinny być wyświetlane w interfejsie użytkownika (po prawej), bez konieczności dodatkowego przetwarzania.
Serializacja kluczy i wartości
Na świecie wynaleziono wiele metod serializacji obiektów. Ponieważ nie mieliśmy innych wymagań poza szybkością, wybraliśmy dla siebie najszybszy możliwy - zrzut pamięci zajmowany przez instancję struktury języka C. Zatem klucz elementu katalogu można modelować za pomocą następującej struktury NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Zapisać NodeKey w magazynie potrzebnym w obiekcie MDB_val ustaw wskaźnik danych na adres początku struktury i oblicz ich rozmiar za pomocą funkcji sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}W pierwszym rozdziale o kryteriach wyboru baz danych jako ważny czynnik selekcji wspomniałem o minimalizacji alokacji dynamicznych w ramach operacji CRUD. Kod funkcji serialize pokazuje, jak w przypadku LMDB można ich całkowicie uniknąć przy wprowadzaniu nowych rekordów do bazy. Przychodząca tablica bajtów z serwera jest najpierw przekształcana w struktury stosu, a następnie w prosty sposób umieszczana w pamięci. Biorąc pod uwagę, że wewnątrz LMDB również nie ma alokacji dynamicznych, można uzyskać fantastyczną sytuację jak na standardy iOS - do pracy z danymi na całej drodze z sieci na dysk używaj wyłącznie pamięci stosu!
Zamawianie kluczy z komparatorem binarnym
Relacja kolejności kluczy jest określana przez specjalną funkcję zwaną komparatorem. Ponieważ silnik nie wie nic o semantyce zawartych w nich bajtów, domyślny komparator nie ma innego wyjścia, jak tylko ułożyć klucze w porządku leksykograficznym, odwołując się do porównania bajt po bajcie. Używanie go do porządkowania struktur przypomina golenie siekierą. Jednak w prostych przypadkach uważam tę metodę za akceptowalną. Alternatywę opisano poniżej, ale tutaj zwrócę uwagę na kilka grabi rozrzuconych wzdłuż tej ścieżki.
Pierwszą rzeczą do zapamiętania jest reprezentacja prymitywnych typów danych w pamięci. Dlatego na wszystkich urządzeniach Apple zmienne całkowite są przechowywane w formacie . Oznacza to, że najmniej znaczący bajt będzie po lewej stronie i nie będzie możliwe sortowanie liczb całkowitych za pomocą porównania bajt po bajcie. Na przykład próba zrobienia tego z zestawem liczb od 0 do 511 da następujący wynik.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Aby rozwiązać ten problem, liczby całkowite muszą być zapisane w kluczu w formacie odpowiednim dla komparatora bajt-bajt. Funkcje z rodziny pomogą Ci w przeprowadzeniu niezbędnej transformacji hton* (w szczególności htons dla liczb dwubajtowych z przykładu).
Jak wiadomo, format reprezentacji ciągów w programowaniu to całość . Jeśli semantyka ciągów znaków, a także kodowanie użyte do ich reprezentacji w pamięci, sugerują, że na znak może przypadać więcej niż jeden bajt, to lepiej od razu porzucić pomysł stosowania domyślnego komparatora.
Drugą rzeczą, o której należy pamiętać, jest kompilator pól strukturalnych. Dzięki nim w pamięci pomiędzy polami mogą powstawać bajty ze śmieciowymi wartościami, co oczywiście zakłóca sortowanie bajtów. Aby wyeliminować śmieci, należy albo zadeklarować pola w ściśle określonej kolejności, pamiętając o zasadach wyrównania, albo użyć atrybutu w deklaracji struktury packed.
Zamawianie kluczy z zewnętrznym komparatorem
Logika porównania kluczy może być zbyt złożona dla komparatora binarnego. Jednym z wielu powodów jest obecność pól technicznych w konstrukcjach. Zilustruję ich występowanie na przykładzie klucza do elementu katalogu, który jest nam już znany.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Pomimo swojej prostoty, w zdecydowanej większości przypadków zużywa zbyt dużo pamięci. Bufor dla nazwy zajmuje 256 bajtów, choć przeciętnie nazwy plików i folderów rzadko przekraczają 20-30 znaków.
Jedną ze standardowych technik optymalizacji rozmiaru rekordu jest „przycięcie” go do rzeczywistego rozmiaru. Jego istotą jest to, że zawartość wszystkich pól o zmiennej długości przechowywana jest w buforze na końcu struktury, a ich długości przechowywane są w osobnych zmiennych. Zgodnie z tym podejściem kluczem NodeKey zostaje przekształcony w następujący sposób.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Ponadto podczas serializacji rozmiar danych nie jest określony sizeof całą strukturę, a wielkość wszystkich pól to stała długość plus wielkość faktycznie wykorzystywanej części bufora.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}W wyniku refaktoryzacji uzyskaliśmy znaczne oszczędności w przestrzeni zajmowanej przez klucze. Jednak ze względu na dziedzinę techniczną nameLength, domyślny komparator binarny nie nadaje się już do porównywania kluczy. Jeśli nie zastąpimy go własnym, długość nazwy będzie miała wyższy priorytet w sortowaniu niż sama nazwa.
LMDB pozwala każdej bazie danych mieć własną funkcję porównywania kluczy. Odbywa się to za pomocą funkcji mdb_set_compare ściśle przed otwarciem. Z oczywistych względów nie można go zmieniać przez cały okres istnienia bazy danych. Komparator otrzymuje na wejściu dwa klucze w formacie binarnym, a na wyjściu zwraca wynik porównania: mniejszy niż (-1), większy niż (1) lub równy (0). Pseudokod dla NodeKey na to wygląda.
int compare(MDB_val * const a, MDB_val * const b) {
NodeKey * const aKey = (NodeKey * const)a->mv_data;
NodeKey * const bKey = (NodeKey * const)b->mv_data;
return // ...
}Dopóki wszystkie klucze w bazie danych są tego samego typu, bezwarunkowe rzutowanie ich reprezentacji bajtowej na typ struktury kluczy aplikacji jest dozwolone. Jest tu jeden niuans, ale zostanie on omówiony poniżej w podrozdziale „Czytanie zapisów”.
Serializacja wartości
LMDB niezwykle intensywnie współpracuje z kluczami przechowywanych rekordów. Ich wzajemne porównywanie odbywa się w ramach dowolnej zastosowanej operacji, a wydajność całego rozwiązania zależy od szybkości komparatora. W idealnym świecie domyślny komparator binarny powinien wystarczyć do porównania kluczy, ale jeśli trzeba byłoby użyć własnego, to procedura deserializacji w nim kluczy powinna być możliwie najszybsza.
Baza danych nie jest szczególnie zainteresowana wartościową częścią rekordu (wartością). Jego konwersja z reprezentacji bajtowej na obiekt następuje tylko wtedy, gdy jest już wymagane przez kod aplikacji, na przykład, aby wyświetlić go na ekranie. Ponieważ zdarza się to stosunkowo rzadko, wymagania dotyczące prędkości dla tej procedury nie są aż tak krytyczne, a przy jej realizacji możemy znacznie swobodniej skupić się na wygodzie.Na przykład do serializacji metadanych o plikach, które nie zostały jeszcze pobrane, używamy NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Są jednak chwile, kiedy wydajność nadal ma znaczenie. Przykładowo zapisując metainformacje o strukturze plików chmury użytkownika, korzystamy z tego samego zrzutu pamięci obiektów. Najważniejszym elementem zadania generowania ich serializowanej reprezentacji jest fakt, że elementy katalogu są modelowane przez hierarchię klas.
Aby zaimplementować to w języku C, określone pola spadkobierców umieszcza się w odrębnych strukturach, a ich połączenie z bazową określa się poprzez pole typu union. Rzeczywista zawartość unii jest określona poprzez typ atrybutu technicznego.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Dodawanie i aktualizacja rekordów
Zserializowany klucz i wartość można dodać do sklepu. Aby to zrobić, użyj funkcji mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);Na etapie konfiguracji można zezwolić lub zabronić przechowywania wielu rekordów za pomocą tego samego klucza.Jeśli duplikowanie kluczy jest zabronione, to podczas wstawiania rekordu można określić, czy dozwolona jest aktualizacja istniejącego rekordu, czy nie. Jeśli strzępienie może wystąpić tylko w wyniku błędu w kodzie, możesz się przed nim zabezpieczyć, określając flagę NOOVERWRITE.
Czytanie wpisów
Aby odczytać rekordy w LMDB należy skorzystać z funkcji mdb_get. Jeśli para klucz-wartość jest reprezentowana przez wcześniej zrzucone struktury, wówczas procedura wygląda następująco.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}Zaprezentowany zestawienie pokazuje, jak serializacja poprzez zrzut struktury pozwala pozbyć się alokacji dynamicznych nie tylko podczas zapisu, ale także podczas odczytu danych. Pochodzi z funkcji mdb_get wskaźnik patrzy dokładnie na adres pamięci wirtualnej, w którym baza danych przechowuje bajtową reprezentację obiektu. Tak naprawdę dostajemy swego rodzaju ORM-a, który niemal za darmo zapewnia bardzo dużą prędkość odczytu danych. Pomimo całego piękna tego podejścia, należy pamiętać o kilku cechach z nim związanych.
- W przypadku transakcji tylko do odczytu wskaźnik do struktury wartości ma gwarancję, że pozostanie ważny tylko do momentu zamknięcia transakcji. Jak wspomniano wcześniej, strony drzewa B, na których znajduje się obiekt, dzięki zasadzie kopiowania przy zapisie, pozostają niezmienione tak długo, jak długo odwołuje się do nich przynajmniej jedna transakcja. Jednocześnie, po zakończeniu ostatniej transakcji z nimi związanej, strony można ponownie wykorzystać w celu uzyskania nowych danych. Jeśli konieczne jest, aby obiekty przetrwały transakcję, która je wygenerowała, nadal należy je skopiować.
- W przypadku transakcji odczytu wskaźnik do wynikowej struktury wartości będzie ważny tylko do momentu pierwszej procedury modyfikującej (zapisu lub usunięcia danych).
- Chociaż konstrukcja
NodeValuenie pełnoprawny, ale przycięty (patrz podrozdział „Zamawianie kluczy za pomocą zewnętrznego komparatora”), możesz bezpiecznie uzyskać dostęp do jego pól za pomocą wskaźnika. Najważniejsze, żeby tego nie wykreślać! - W żadnym wypadku nie należy modyfikować struktury poprzez otrzymany wskaźnik. Wszelkie zmiany należy wprowadzać wyłącznie za pomocą metody
mdb_put. Jednak niezależnie od tego, jak bardzo chcesz to zrobić, nie będzie to możliwe, ponieważ obszar pamięci, w którym znajduje się ta struktura, jest mapowany w trybie tylko do odczytu. - Ponownie zamapuj plik na przestrzeń adresową procesu, aby na przykład zwiększyć maksymalny rozmiar pamięci za pomocą tej funkcji
mdb_env_set_map_sizecałkowicie unieważnia wszystkie transakcje i powiązane z nimi podmioty w ogóle, a w szczególności wskaźniki do niektórych obiektów.
Wreszcie kolejna cecha jest na tyle podstępna, że ujawnienie jej istoty nie mieści się w kolejnym akapicie. W rozdziale poświęconym drzewu B podałem schemat układu jego stron w pamięci. Wynika z tego, że adres początku bufora z serializowanymi danymi może być absolutnie dowolny. Z tego powodu wskaźnik do nich otrzymany w strukturze MDB_val i zredukowany do wskaźnika do struktury, w ogólnym przypadku okazuje się, że jest niewyrównany. Jednocześnie architektury niektórych chipów (w przypadku iOS jest to armv7) wymagają, aby adres dowolnych danych był wielokrotnością rozmiaru słowa maszynowego, czyli innymi słowy rozmiaru bitowego systemu ( dla armv7 jest to 32 bity). Innymi słowy, operacja taka jak *(int *foo)0x800002 na nich jest równoznaczne z ucieczką i prowadzi do egzekucji z wyrokiem EXC_ARM_DA_ALIGN. Są dwa sposoby uniknięcia tak smutnego losu.
Pierwsza sprowadza się do wstępnego skopiowania danych do wyraźnie dopasowanej struktury. Na przykład w niestandardowym komparatorze zostanie to odzwierciedlone w następujący sposób.
int compare(MDB_val * const a, MDB_val * const b) {
NodeKey aKey, bKey;
memcpy(&aKey, a->mv_data, a->mv_size);
memcpy(&bKey, b->mv_data, b->mv_size);
return // ...
}Alternatywnym sposobem jest wcześniejsze powiadomienie kompilatora, że struktury klucz-wartość mogą nie być wyrównane według atrybutów aligned(1). Na ARM możesz mieć ten sam efekt i użycie spakowanego atrybutu. Biorąc pod uwagę, że pomaga to również zoptymalizować przestrzeń zajmowaną przez konstrukcję, chociaż ta metoda wydaje mi się lepsza do wzrostu kosztów operacji dostępu do danych.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Zapytania o zakres
Aby iterować po grupie rekordów, LMDB zapewnia abstrakcję kursora. Przyjrzyjmy się, jak z tym pracować, na przykładzie tabeli ze znanymi nam już metadanymi chmury użytkownika.
W ramach wyświetlania listy plików w katalogu konieczne jest odnalezienie wszystkich kluczy, z którymi powiązane są jego pliki i foldery podrzędne. W poprzednich podrozdziałach posortowaliśmy klucze NodeKey w taki sposób, że są one uporządkowane głównie według identyfikatora katalogu nadrzędnego. Technicznie więc zadanie odzyskania zawartości folderu sprowadza się do umieszczenia kursora na górnej granicy grupy kluczy o danym przedrostku i następnie iteracji do dolnej granicy.
Górną granicę można znaleźć bezpośrednio poprzez wyszukiwanie sekwencyjne. W tym celu umieszcza się kursor na początku całej listy kluczy w bazie danych i zwiększa go dalej, aż pod nim pojawi się klucz z identyfikatorem katalogu nadrzędnego. To podejście ma 2 oczywiste wady:
- Złożoność poszukiwań liniowych, chociaż jak wiadomo, w drzewach w ogóle, a w drzewie B w szczególności, można je przeprowadzić w czasie logarytmicznym.
- Na próżno wszystkie strony poprzedzające poszukiwaną są przenoszone z pliku do pamięci głównej, co jest niezwykle kosztowne.
Na szczęście API LMDB zapewnia skuteczny sposób na wstępne ustawienie kursora.W tym celu należy wygenerować klucz, którego wartość jest oczywiście mniejsza lub równa kluczowi znajdującemu się na górnej granicy przedziału. Przykładowo w nawiązaniu do listy na powyższym rysunku możemy utworzyć klucz w którym będzie zawarte pole parentId będzie równa 2, a wszystkie pozostałe są wypełnione zerami. Taki częściowo wypełniony klucz podawany jest na wejście funkcyjne mdb_cursor_get wskazując operację MDB_SET_RANGE.
NodeKey upperBoundSearchKey = {
.parentId = 2,
.type = 0,
.nameLength = 0
};
MDB_val value, key = serialize(upperBoundSearchKey);
MDB_cursor *cursor;
mdb_cursor_open(..., &cursor);
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);Jeśli zostanie znaleziona górna granica grupy kluczy, iterujemy po niej, aż albo spotkamy się, albo klucz spotka się z inną parentId, albo klucze w ogóle się nie skończą
do {
rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);
// processing...
} while (MDB_NOTFOUND != rc && // check end of table
IsTargetKey(key)); // check end of keys groupCo ciekawe, w ramach iteracji za pomocą mdb_cursor_get otrzymujemy nie tylko klucz, ale także wartość. Jeśli, aby spełnić warunki próbkowania, trzeba sprawdzić między innymi pola z części wartościowej rekordu, to są one w miarę dostępne bez dodatkowych gestów.
4.3. Modelowanie relacji pomiędzy tabelami
Do tej pory udało nam się uwzględnić wszystkie aspekty projektowania i pracy z jednotabelową bazą danych. Można powiedzieć, że tabela to zbiór posortowanych rekordów składający się z par klucz-wartość tego samego typu. Jeśli wyświetlisz klucz jako prostokąt, a powiązaną wartość jako równoległościan, otrzymasz wizualny diagram bazy danych.
â € <
Jednak w prawdziwym życiu rzadko można obejść się przy tak niewielkim rozlewie krwi. Często w bazie danych wymagane jest, po pierwsze, posiadanie kilku tabel, a po drugie, dokonywanie w nich selekcji w kolejności innej niż klucz podstawowy. Ostatnia część poświęcona jest zagadnieniom ich powstawania i wzajemnych powiązań.
Tabele indeksowe
Aplikacja w chmurze posiada sekcję „Galeria”. Wyświetla treści multimedialne z całej chmury, posortowane według daty. Aby optymalnie zrealizować taki wybór, obok stołu głównego należy utworzyć kolejny z nowym typem kluczy. Będą zawierać pole z datą utworzenia pliku, które będzie stanowić podstawowe kryterium sortowania. Ponieważ nowe klucze odwołują się do tych samych danych, co klucze w tabeli głównej, nazywane są kluczami indeksowymi. Na poniższym obrazku są one zaznaczone na pomarańczowo.
Aby oddzielić od siebie klucze różnych tabel w ramach tej samej bazy danych, do każdego z nich dodano dodatkowe pole techniczne tableId. Nadając mu najwyższy priorytet przy sortowaniu, osiągniemy grupowanie kluczy najpierw według tabel, a w obrębie tabel - według naszych własnych zasad.
Klucz indeksowy odwołuje się do tych samych danych, co klucz podstawowy. Prosta implementacja tej właściwości poprzez powiązanie z nią kopii części wartości klucza podstawowego nie jest optymalna z kilku punktów widzenia:
- Pod względem zajmowanej przestrzeni metadane mogą być dość bogate.
- Z punktu widzenia wydajności, ponieważ podczas aktualizacji metadanych węzła będziesz musiał przepisać je za pomocą dwóch kluczy.
- Z punktu widzenia obsługi kodu, jeśli zapomnimy zaktualizować dane dla jednego z kluczy, otrzymamy nieuchwytny błąd niespójności danych w pamięci.
Następnie zastanowimy się, jak wyeliminować te niedociągnięcia.
Organizowanie relacji między tabelami
Wzór doskonale nadaje się do łączenia tabeli indeksowej z tabelą główną „klucz jako wartość”. Jak sama nazwa wskazuje, część wartości rekordu indeksu jest kopią wartości klucza podstawowego. Takie podejście eliminuje wszystkie wyżej wymienione niedogodności związane z przechowywaniem kopii części wartościowej rekordu pierwotnego. Jedynym kosztem jest to, że aby uzyskać wartość według klucza indeksu, należy wykonać 2 zapytania do bazy danych zamiast jednego. Schematycznie powstały schemat bazy danych wygląda następująco.
Innym wzorcem organizowania relacji między tabelami jest „klucz zbędny”. Jego istotą jest dodanie do klucza dodatkowych atrybutów, które są potrzebne nie do sortowania, ale do odtworzenia powiązanego klucza.W aplikacji Mail.ru Cloud znajdują się jednak prawdziwe przykłady jego użycia, aby uniknąć głębokiego zagłębiania się w w kontekście konkretnych frameworków iOS podam fikcyjny, ale jaśniejszy przykład.
Klienci mobilni Cloud mają stronę wyświetlającą wszystkie pliki i foldery, które użytkownik udostępnił innym osobom. Ponieważ takich plików jest stosunkowo niewiele, a wiąże się z nimi wiele różnego rodzaju konkretnych informacji o charakterze reklamowym (kto ma dostęp, jakie prawa itp.), nieracjonalne będzie obciążanie części wartościowej pliku zapisz go w głównej tabeli. Jeśli jednak chcesz wyświetlać takie pliki w trybie offline, nadal musisz je gdzieś przechowywać. Naturalnym rozwiązaniem jest stworzenie dla niego osobnego stolika. Na poniższym schemacie jego klucz jest poprzedzony literą „P”, a symbol zastępczy „propname” można zastąpić bardziej szczegółową wartością „informacje publiczne”.
Wszystkie unikalne metadane, na potrzeby przechowywania których utworzono nową tabelę, umieszczane są w części wartościowej rekordu. Jednocześnie nie chcesz duplikować danych o plikach i folderach, które są już zapisane w tabeli głównej. Zamiast tego do klawisza „P” dodawane są nadmiarowe dane w postaci pól „ID węzła” i „znacznik czasu”. Dzięki nim można skonstruować klucz indeksowy, z którego można uzyskać klucz podstawowy, z którego finalnie można pozyskać metadane węzła.
Wniosek
Efekty wdrożenia LMDB oceniamy pozytywnie. Po tym liczba zawieszeń aplikacji spadła o 30%.
Wyniki wykonanej pracy odbiły się szerokim echem poza zespołem iOS. Obecnie jedna z głównych sekcji „Pliki” w aplikacji na Androida również została przełączona na korzystanie z LMDB, a inne części są w drodze. Język C, w którym zaimplementowano magazyn klucz-wartość, był dobrą pomocą przy początkowym tworzeniu wokół niego frameworku aplikacji wieloplatformowej w C++. Do bezproblemowego połączenia powstałej biblioteki C++ z kodem platformy w Objective-C i Kotlin wykorzystano generator kodu z Dropbox, ale to zupełnie inna historia.
Źródło: www.habr.com