W jesieni 2019 roku w zespole iOS Obłoku Mail.ru miało miejsce długo oczekiwane wydarzenie. Główną bazą danych do trwałego przechowywania stanu aplikacji stał się bardzo egzotyczny dla świata mobilnego. Lightning Memory-Mapped Database (LMDB). Poniżej znajdziecie szczegółowy przegląd w czterech częściach. Na początku porozmawiamy o powodach tak nietrywialnego i trudnego wyboru. Następnie przejdziemy do omówienia trzech filarów architektury LMDB: plików odwzorowanych w pamięci, drzewa B+- i podejścia copy-on-write do realizacji transakcyjności i wielowersyjności. Na koniec, na deser — część praktyczna. W niej omówimy, jak na niskopoziomowym API key-value zaprojektować i wdrożyć schemat bazy z kilkoma tabelami, w tym indeksową.

Spis treści

1. Motywacja wdrożenia
2. Pozycjonowanie LMDB
3. Trzy filary LMDB
   3.1. Filar nr 1. Pliki odwzorowane w pamięci
   3.2. Filar nr 2. Drzewo B+
   3.3. Filar nr 3. Copy-on-write
4. Projektowanie schematu danych na podstawie API key-value
   4.1. Podstawowe abstrakcje
   4.2. Modelowanie tabel
   4.3. Modelowanie powiązań między tabelami

1. Motywacja wdrożenia

Pewnego razu, około 2015 roku, zaczęliśmy analizować, jak często interfejs naszej aplikacji ma opóźnienia. Zajmowaliśmy się tym nie bez powodu. Otrzymywaliśmy coraz więcej skarg, że czasami aplikacja przestaje reagować na działania użytkownika: przyciski się nie wciskają, listy się nie przewijają itd. O mechanice pomiarów opowiadałem na AvitoTech, dlatego tutaj przytaczam tylko przybliżone liczby.

Wyniki pomiarów okazały się dla nas zimnym prysznicem. Okazało się, że problemów spowodowanych zawieszaniem się jest znacznie więcej niż jakichkolwiek innych. Jeśli do tego momentu głównym technicznym wskaźnikiem jakości było bezawaryjne działanie, to po tej świadomości skoncentrowaliśmy się na braku zamrożeń.

Zbudowaliśmy kokpit zawieszeń i przeprowadziliśmy liczbową i jakościową analizę ich przyczyn, co ujawniło głównego wroga — złożoną logikę biznesową, która była wykonywana w głównym wątku aplikacji. Naturalną reakcją na ten bałagan było palące pragnienie rozdzielenia jej na wątki robocze. Aby systemowo rozwiązać ten problem, sięgnęliśmy po architekturę wielowątkową opartą na lekkich aktorach. Jej adaptacji do świata iOS poświęciłem dwa wątki na wspólnym Twitterze oraz artykuł na Habrze. W ramach bieżącej narracji chciałbym podkreślić te aspekty rozwiązania, które wpłynęły na wybór bazy danych.

Model aktorski organizacji systemu zakłada, że wielowątkowość staje się jej drugą naturą. Obiekty modelu w niej chętnie przekraczają granice wątków. I robią to nie czasami i gdzieś, a praktycznie nieustannie i wszędzie.

Baza danych jest jednym z podstawowych komponentów na przedstawionej schemacie. Jej głównym zadaniem jest realizacja makropatternu Wspólna baza danych. Jeśli w światach przedsiębiorstw za jej pomocą organizuje się synchronizację danych między usługami, to w przypadku architektury aktorskiej — dane między wątkami. W ten sposób potrzebna nam była taka baza danych, praca z którą w środowisku wielowątkowym nie powoduje nawet minimalnych trudności. W szczególności oznacza to, że obiekty uzyskane z niej powinny być co najmniej bezpieczne dla wątków, a w idealnym przypadku wręcz niemutowalne. Jak wiadomo, te ostatnie można używać jednocześnie z kilku wątków, nie sięgając po żadne blokady, co korzystnie wpływa na wydajność.

Drugim istotnym czynnikiem, który wpłynął na wybór bazy danych, było nasze chmurowe API. Inspirowało się ono podejściem do synchronizacji, przyjętym w git. Tak jak on, celowaliśmy w API offline-first, które dla klientów chmurowych wygląda więcej niż stosownie. Zakładano, że będą oni tylko raz pobierać pełny stan chmury, a następnie synchronizacja w przeważającej liczbie przypadków będzie następować poprzez nakładanie zmian. Niestety, ta możliwość wciąż pozostaje jedynie w sferze teoretycznej, a w praktyce klienci nie nauczyli się jeszcze pracować z łatkami. Istnieje szereg obiektywnych powodów tego stanu rzeczy, które, aby nie przedłużać wprowadzenia, pozostawimy bez omówienia. Teraz znacznie większe zainteresowanie budzą pouczające wyniki lekcji na temat tego, co się dzieje, gdy API powiedziało „A”, a jego użytkownik nie powiedział „B”.

Wyobraź sobie, że git, wykonując polecenie pull, zamiast stosować patche do lokalnego migawki, porównuje jego pełny stan z pełnym stanem serwera. Będzie to dość trafne wyobrażenie, jak odbywa się synchronizacja w chmurze. Nie trudno się domyślić, że by to wykonać, konieczne jest zaalokowanie w pamięci dwóch drzew DOM z metainformacjami o wszystkich plikach serwerowych i lokalnych. Oznacza to, że jeśli użytkownik przechowuje 500 tysięcy plików w chmurze, to do jego synchronizacji konieczne jest odtworzenie i zniszczenie dwóch drzew z 1 milionem węzłów. A każdy węzeł to agregat zawierający w sobie grafikę pod-obiektów. W tym świetle wyniki profilowania okazały się przewidywalne. Okazało się, że nawet bez uwzględnienia algorytmiki łączenia sam proces tworzenia i późniejszego niszczenia ogromnej liczby drobnych obiektów kosztuje sporo. Sytuację pogarsza to, że podstawowa operacja synchronizacji jest uwzględniona w wielu scenariuszach użytkownika. Ostatecznie naliczamy drugi ważny kryterium w wyborze bazy danych — możliwość realizacji operacji CRUD bez dynamicznej alokacji obiektów.

Inne wymagania są bardziej tradycyjne i ich lista wygląda następująco.

1. Wątkowa bezpieczeństwo.
2. Wieloprocesowość. Dyktowana pragnieniem używania tej samej instancji bazy danych do synchronizacji stanu nie tylko między wątkami, ale także między główną aplikacją a rozszerzeniami iOS.
3. Możliwość przedstawienia przechowywanych bytów jako obiektów niemutowalnych.
4. Brak dynamicznych alokacji w ramach operacji CRUD.
5. Wsparcie transakcyjne dla podstawowych właściwości ACID: atomowość, spójność, izolacja i niezawodność.
6. Szybkość w najpopularniejszych przypadkach użycia.

Dobrym wyborem z takim zestawem wymagań była i pozostaje SQLite. Jednak podczas poszukiwań alternatyw, natrafiłem na książkę „Getting Started with LevelDB”. Pod jej przewodnictwem stworzono benchmark porównujący prędkość pracy z różnymi bazami danych w rzeczywistych scenariuszach chmurowych. Wynik przewyższył najśmielsze oczekiwania. W najpopularniejszych przypadkach — uzyskanie wskaźnika na posortowanej liście wszystkich plików i posortowanej liście wszystkich plików dla podanego katalogu — LMDB okazał się 10 razy szybszy niż SQLite. Wybór stał się oczywisty.

2. Pozycjonowanie LMDB

LMDB to bardzo mała biblioteka (tylko 10K linii), która realizuje najniższy podstawowy poziom baz danych — magazyn.

Przedstawiony schemat pokazuje, że porównywanie LMDB z SQLite, który realizuje jeszcze wyższe poziomy, jest właściwie niepoprawne, tak samo jak porównywanie SQLite z Core Data. Jako równoprawnych konkurentów bardziej sprawiedliwe byłoby przytaczanie takich samych silników-magazynów — BerkeleyDB, LevelDB, Sophia, RocksDB i innych. Są nawet prace, w których LMDB pełni rolę komponentu silnika magazynu dla SQLite. Pierwszy taki eksperyment przeprowadzono w 2012 roku. Przeprowadził autor LMDB Howard Chu. Wyniki okazały się na tyle intrygujące, że jego przedsięwzięcie zostało podchwycone przez entuzjastów OSS, i znalazło swoje kontynuacje w postaci LumoSQL. W styczniu 2020 roku autor tego projektu Den Shearer zaprezentował go na LinuxConfAu.

Główne zastosowanie LMDB znajduje jako silnik dla aplikacyjnych baz danych. Swoim pojawieniem się biblioteka zawdzięcza twórcom OpenLDAP, którzy byli bardzo niezadowoleni z BerkeleyDB jako podstawy swojego projektu. Odrzucając skromną biblioteczkę btree, Howard Chu był w stanie stworzyć jedną z najpopularniejszych współczesnych alternatyw. Tę historię oraz wewnętrznej budowie LMDB poświęcił swoje bardzo fajne wystąpienie „The Lightning Memory-mapped Database”. Dobrym przykładem podbicia magazynu podzielił się Leonid Juriew (aka yleo) z Positive Technologies w swoim wystąpieniu na Highload 2015 „Silnik LMDB — szczególny mistrz”. W nim opowiada o LMDB w kontekście podobnego zadania realizacji ReOpenLDAP, a krytyce porównawczej poddano już LevelDB. Po wprowadzeniu w Positive Technologies pojawił się nawet aktywnie rozwijający się fork MDBX z bardzo atrakcyjnymi funkcjami, optymalizacjami i poprawkami błędów..

LMDB często stosowane jest również jako magazyn as is. Na przykład przeglądarka Mozilla Firefox wybrała go do szeregu potrzeb, a zaczynając od wersji 9, Xcode preferował go bardziej niż SQLite do przechowywania indeksów.

Silnik zyskał na popularności również w świecie mobilnego rozwoju. Można go znaleźć w kliencie iOS dla Telegramu. LinkedIn poszedł jeszcze dalej i wybrał LMDB jako domyślne repozytorium dla własnego frameworka do buforowania danych Rocket Data, o czym opowiedział napisano w jego artykule w 2016 roku.

LMDB skutecznie rywalizuje o pozycję w niszy, którą pozostawił BerkeleyDB po przejęciu przez Oracle. Bibliotekę ceni się za prędkość i niezawodność, nawet w porównaniu z jej odpowiednikami. Jak wiadomo, nie ma darmowych obiadów, dlatego warto podkreślić ograniczenia, z którymi trzeba się zmierzyć przy wyborze między LMDB a SQLite. Schemat powyżej wyraźnie pokazuje, jak osiągnięto większą wydajność. Po pierwsze, nie płacimy za dodatkowe warstwy abstrakcji nad dyskowym magazynem. Oczywiście, w dobrej architekturze i tak nie da się ich uniknąć, a one nieuchronnie pojawią się w kodzie aplikacji, jednak będą znacznie cieńsze. Nie będzie w nich funkcji, które nie są potrzebne konkretnej aplikacji, na przykład wsparcia dla zapytań w języku SQL. Po drugie, istnieje możliwość optymalnego zrealizowania mapowania operacji aplikacyjnych na zapytania do magazynu dyskowego. Jeśli SQLite w swojej pracy opiera się na przeciętnych potrzebach przeciętnej aplikacji, ty jako programista aplikacyjny doskonale znasz główne scenariusze obciążenia. Za bardziej wydajne rozwiązanie trzeba będzie zapłacić wyższą ceną zarówno za rozwój początkowego rozwiązania, jak i jego późniejsze wsparcie.

3. Trzy filary LMDB

Patrząc na LMDB z góry, nadszedł czas, aby zejść głębiej. Następne trzy sekcje będą poświęcone omówieniu podstawowych filarów, na których opiera się architektura magazynu:

1. Pliki mapowane w pamięci jako mechanizm pracy z dyskiem i synchronizacji wewnętrznych struktur danych.
2. Drzewo B+ jako organizacja struktury przechowywanych danych.
3. Copy-on-write jako podejście do zapewnienia właściwości ACID transakcji i wielowersyjności.

3.1. Filar nr 1. Pliki mapowane w pamięci

Wyświetlane w pamięci pliki są tak ważnym elementem architektury, że pojawiają się nawet w nazwie magazynu. Kwestie dotyczące cache'owania i synchronizacji dostępu do przechowywanych informacji są całkowicie oddane systemowi operacyjnemu. LMDB nie zawiera żadnych wewnętrznych pamięci podręcznych. To świadoma decyzja autora, ponieważ odczyt danych bezpośrednio z mapowanych plików pozwala na ominięcie wielu trudności w implementacji silnika. Poniżej przedstawiam z pewnością niepełną listę niektórych z nich.

1. Utrzymanie spójności danych w magazynie podczas pracy z nim z różnych procesów staje się obowiązkiem systemu operacyjnego. W następnym rozdziale ta mechanika zostanie omówiona szczegółowo, z ilustracjami.
2. Brak pamięci podręcznych całkowicie zwalnia LMDB z kosztów związanych z dynamiczną alokacją. Odczyt danych w praktyce polega na ustawieniu wskaźnika na prawidłowy adres w pamięci wirtualnej i to wszystko. Brzmi jak fantastyka, ale w źródłach magazynu wszystkie wywołania salloc są skoncentrowane w funkcji konfigurowania magazynu.
3. Brak pamięci podręcznych oznacza również brak blokad związanych z synchronizacją dostępu do nich. Czytelnicy, których może być dowolna liczba, nie napotykają na swojej drodze do danych żadnego mutexa. Dzięki temu prędkość odczytu ma doskonałą liniową skalowalność wraz z liczbą CPU. W LMDB synchronizacji podlegają tylko operacje modyfikujące. W danym momencie może być tylko jeden pisarz.
4. Minimalna logika pamięci podręcznej i synchronizacji eliminuje kod z niezwykle skomplikowanego typu błędów związanych z pracą w środowisku wielowątkowym. Na konferencji Usenix OSDI 2014 zaprezentowane zostały dwa interesujące badania dotyczące baz danych: „Wszystkie systemy plików nie są stworzone równo: o złożoności tworzenia aplikacji odpornych na awarie” i „Torture to Fun and Profit”. Z nich można wyciągnąć informacje zarówno o bezprecedensowej niezawodności LMDB, jak i o praktycznie bezbłędnej realizacji właściwości ACID transakcji, która przewyższa tę w SQLite.
5. Minimalistyczność LMDB pozwala na całkowite umieszczenie jej kodu w pamięci L1 procesora, co przekłada się na wydajność.

Niestety, w iOS sytuacja z plikami mapowanymi w pamięci nie jest tak różowa, jak byśmy chcieli. Aby świadomiej omówić związane z nimi wady, musimy przypomnieć sobie ogólne zasady realizacji tego mechanizmu w systemach operacyjnych.

Ogólne informacje o plikach mapowanych w pamięci

Z każdym uruchamianym programem system operacyjny wiąże byt zwany procesem. Każdemu procesowi przypisuje się ciągły zakres adresów, w którym umieszcza wszystko, co potrzebne do jego działania. Na najniższych adresach znajdują się sekcje z kodem oraz twardo zakodowane dane i zasoby. Następnie mamy rosnący blok dynamicznej przestrzeni adresowej, dobrze znany jako heap. Zawiera on adresy bytów, które pojawiają się w trakcie działania programu. Na górze znajduje się obszar pamięci używany przez stos aplikacji. Ten z kolei rośnie i maleje, innymi słowy jego rozmiar również ma dynamiczny charakter. Aby stos i heap się nie kolidowały i nie przeszkadzały sobie nawzajem, są rozdzielone na różnych końcach przestrzeni adresowej. Pomiędzy obiema dynamicznymi sekcjami na górze i na dole znajduje się luka. Adresy w tym środkowym obszarze system operacyjny wykorzystuje do asocjacji z procesem różnych bytów. W szczególności może przypisać jakieś ciągłe zestaw adresów do pliku na dysku. Taki plik nazywa się plikiem mapowanym w pamięci.

Przydzielona procesowi przestrzeń adresowa jest ogromna. Teoretycznie liczba adresów jest ograniczona tylko przez rozmiar wskaźnika, który określa się w zależności od bitowości systemu. Gdyby była z nim 1-do-1 skojarzona pamięć fizyczna, to pierwszy proces zjadłby całą pamięć operacyjną, a o żadnej wielozadaniowości nie mogłoby być mowy.

Jednak z własnego doświadczenia wiemy, że nowoczesne systemy operacyjne mogą jednocześnie uruchamiać dowolną liczbę procesów. Jest to możliwe dzięki temu, że przydzielają one procesom mnóstwo pamięci tylko na papierze, a w rzeczywistości ładują do głównej pamięci fizycznej tylko tę część, która jest potrzebna tu i teraz. Dlatego pamięć asocjowana z procesem nazywa się pamięcią wirtualną.

System operacyjny organizuje pamięć wirtualną i fizyczną w postaci stron o określonym rozmiarze. Gdy dana strona pamięci wirtualnej jest potrzebna, system operacyjny ładuje ją do pamięci fizycznej i ustawia między nimi odpowiednie powiązanie w specjalnej tabeli. Jeśli nie ma wolnych slotów, jedna z wcześniej załadowanych stron jest kopiowana na dysk, a potrzebna zajmuje jej miejsce. Procedurę tę, do której niedługo wrócimy, nazywamy swappingiem. Poniżej przedstawiono ilustrujący ten proces rysunek. Strona A z adresem 0 została załadowana i umieszczona na stronie pamięci głównej z adresem 4. Ten fakt znalazł swoje odzwierciedlenie w tabeli powiązań w komórce numer 0.

Z wyświetlonymi w pamięci plikami historia wygląda dokładnie tak samo. Logicznie są one rzekomo ciągłe i całkowicie umieszczone w wirtualnej przestrzeni adresowej. Jednak trafiają do pamięci fizycznej strona po stronie i tylko na żądanie. Modyfikacja takich stron jest synchronizowana z plikiem na dysku. Dzięki temu można wykonywać wejście/wyjście plikowe, po prostu pracując z bajtami w pamięci — wszystkie zmiany będą automatycznie przeniesione przez jądro systemu operacyjnego do oryginalnego pliku.
​
Poniższy obrazek pokazuje, jak LMDB synchronizuje swoje stany podczas pracy z bazą danych z różnych procesów. Mapując pamięć wirtualną różnych procesów na ten sam plik, de facto zmuszamy system operacyjny do transitive synchronizacji niektórych bloków ich przestrzeni adresowej, do których LMDB kieruje swoje zapytania.
​

Ważny szczegół polega na tym, że LMDB domyślnie modyfikuje plik z danymi przez mechanizm wywołania systemowego write, a sam plik jest mapowany w trybie tylko do odczytu. Takie podejście ma dwa ważne konsekwencje.

Pierwsza konsekwencja – wspólna dla wszystkich systemów operacyjnych. Jej istota polega na dodaniu ochrony przed przypadkowym uszkodzeniem bazy danych przez niepoprawny kod. Jak wiadomo, wykonywane instrukcje w procesie mają swobodny dostęp do danych z dowolnego miejsca w jego przestrzeni adresowej. Jednocześnie, jak właśnie wspomnieliśmy, otwarcie pliku w trybie odczytu-zapisu oznacza, że każda instrukcja może go dodatkowo modyfikować. Jeśli zrobi to przez pomyłkę, próbując na przykład nadpisać element tablicy przy nieistniejącym indeksie, może w ten sposób przypadkowo zmienić zamapowany na ten adres plik, co prowadzi do uszkodzenia bazy danych. Jeśli natomiast plik jest zamapowany w trybie tylko do odczytu, próba zmiany odpowiedniej przestrzeni adresowej spowoduje awaryjne zakończenie programu z 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 bezpośrednio, ale bez niego LMDB byłoby nieodpowiednie do działania w tym systemie operacyjnym. Kolejny rozdział poświęcony jest jego omówieniu.

Specyfika zamapowanych w pamięci plików w iOS

W 2018 roku na WWDC odbył się znakomity wykład „Zagłębienie się w pamięć iOS”. W nim mówiono, że w iOS wszystkie strony znajdujące się w pamięci fizycznej należą do jednego z 3 typów: dirty, compressed i clean.

Clean memory to zbiór stron, które mogą być bezproblemowo wyładowane z pamięci fizycznej. Dane znajdujące się w nich mogą być w razie potrzeby ponownie załadowane z ich pierwotnych źródeł. Pliki zamapowane tylko do odczytu należą właśnie do tej kategorii. iOS nie obawia się w każdej chwili wyładować zamapowanych na plik stron z pamięci, ponieważ są one gwarantowanie zsynchronizowane z plikiem na dysku.
​
W dirty memory znajdują się wszystkie zmodyfikowane strony, niezależnie od ich pierwotnego położenia. W szczególności tak będą klasyfikowane także pliki zamapowane w pamięci, zmienione poprzez zapisy do powiązanej z nimi pamięci wirtualnej. Otwierając LMDB z flagą MDB_WRITEMAP, po dokonaniu w niej zmian można się o tym przekonać osobiście.

Gdy aplikacja zaczyna zajmować zbyt dużo pamięci fizycznej, iOS poddaje ją kompresji stron brudnych. Całkowita pamięć zajmowana przez strony brudne i skompresowane nazywana jest tzw. śladem pamięci aplikacji. Po osiągnięciu określonego progu do procesu przystępuje systemowy demon OOM killer i wymusza jego zakończenie. W tym tkwi szczególna cecha iOS w porównaniu do systemów operacyjnych na komputery stacjonarne. W przeciwieństwie do nich, redukcja śladu pamięci poprzez zamianę stron z pamięci fizycznej na dysk w iOS nie jest przewidziana. O przyczynach można jedynie spekulować. Możliwe, że procedura intensywnego przenoszenia stron na dysk i z powrotem jest zbyt energochłonna dla urządzeń mobilnych lub iOS oszczędza zasoby związane z zapisem komórek na dyskach SSD, a może projektantów nie zadowalała ogólna wydajność systemu, w którym wszystko ciągle zamienia się. Tak czy inaczej, fakt pozostaje faktem.

Dobrą wiadomością, o której już wcześniej wspomniano, jest to, że LMDB domyślnie nie używa mechanizmu mmap do aktualizacji plików. Z tego wynika, że dane wyświetlane są klasyfikowane przez iOS jako czysta pamięć i nie przyczyniają się do śladu pamięci. Można to zweryfikować za pomocą narzędzia Xcode o nazwie VM Tracker. Na poniższym zrzucie ekranu widać stan wirtualnej pamięci aplikacji iOS Chmura podczas pracy. Na starcie zainicjowano 2 instancje LMDB. Pierwszej pozwolono na zmapowanie pliku na 1GiB wirtualnej pamięci, drugiej - 512MiB. Mimo że oba magazyny zajmują pewną ilość pamięci rezystentnej, żaden z nich nie przyczynia się do rozmiaru brudnego.

A teraz czas na złe wieści. Dzięki mechanizmowi zamiany w 64-bitowych systemach operacyjnych dla komputerów stacjonarnych każdy proces może zająć tyle wirtualnej przestrzeni adresowej, ile pozwala wolne miejsce na dysku twardym pod jego potencjalny swap. Zastąpienie zamiany kompresją w iOS radykalnie obniża teoretyczny maksimum. Teraz wszystkie aktywne procesy muszą zmieścić się w pamięci głównej (czytaj: operacyjnej), a wszystkie, które się nie zmieszczą, podlegają wymuszonemu zakończeniu. O tym mówi się w powyższym raporcie, jak i w oficjalnej dokumentacji. W konsekwencji, iOS ściśle ogranicza rozmiar pamięci dostępnej do alokacji przez mmap. Oto tutaj Można przyjrzeć się empirycznym granicom alokacji pamięci, które udało się przeprowadzić na różnych urządzeniach za pomocą tego wywołania systemowego. Na najnowocześniejszych modelach smartfonów iOS alokowane są 2 gigabajty, a na najwyższych wersjach iPada - 4. W praktyce oczywiście trzeba kierować się najstarszymi wspieranymi modelami urządzeń, gdzie sytuacja jest znacznie gorsza. Co gorsza, przeglądając stan pamięci aplikacji w VM Tracker, można zauważyć, że LMDB nie jest jedyną, która aspiruje do pamięci mapowanej. Duża część pamięci jest zajęta przez alokatory systemowe, pliki zasobów, frameworki do pracy z obrazami oraz inne, mniejsze drapieżniki.

Na podstawie eksperymentów w Chmurze doszliśmy do następujących kompromisowych wartości alokowanej pamięci LMDB: 384 megabajty dla urządzeń 32-bitowych i 768 megabajtów dla 64-bitowych. Po wykorzystaniu tej ilości wszelkie operacje modyfikacyjne zaczynają kończyć się kodem MDB_MAP_FULL. Tego rodzaju błędy obserwujemy w naszym monitoringu, ale jest ich na tyle mało, że na tym etapie można je zignorować.

Nieoczywistą przyczyną nadmiernego zużycia pamięci przez magazyn może być długoterminowe trwanie transakcji. Aby zrozumieć, jak te dwa zjawiska są ze sobą powiązane, pomocne będzie rozważenie pozostałych dwóch filarów LMDB.

3.2. Filar nr 2. Drzewo B+-

Aby emulować tabele w strukturze klucz-wartość, w jej API muszą znajdować się następujące operacje:

1. Wstawienie nowego elementu.
2. Wyszukiwanie elementu o podanym kluczu.
3. Usunięcie elementu.
4. Iterowanie po przedziałach kluczy w kolejności ich sortowania.

Najprostszą strukturą danych, którą można łatwo zaimplementować dla wszystkich czterech operacji, jest drzewo binarne wyszukiwania. Każdy jego węzeł reprezentuje klucz, dzielący całe podzbiory kluczy potomnych na dwa poddrzewa. W lewym zebrane są te, które są mniejsze od rodzica, a w prawym - które są większe. Uzyskanie uporządkowanego zbioru kluczy osiąga się poprzez jedno z klasycznych przeszukiwań drzewa.

Binarne drzewa mają dwie podstawowe wady, które uniemożliwiają im efektywne działanie jako struktura danych na dysku. Po pierwsze, ich stopień zbalansowania jest nieprzewidywalny. Istnieje znaczne ryzyko uzyskania drzew, w których wysokość różnych gałęzi może się znacznie różnić, co znacznie pogarsza algorytmiczną złożoność wyszukiwania w porównaniu do oczekiwanej. Po drugie, obfitość krzyżowych odwołań między węzłami pozbawia binarne drzewa lokalności w pamięci. Bliskie węzły (pod względem połączeń między nimi) mogą znajdować się na zupełnie różnych stronach w pamięci wirtualnej. W konsekwencji nawet dla prostego przeglądania kilku sąsiadujących węzłów w drzewie może być konieczne odwiedzenie porównywalnej liczby stron. To stanowi problem, nawet gdy rozważamy efektywność binarnych drzew jako in-memory struktury danych, ponieważ stała rotacja stron w pamięci podręcznej procesora to nie jest tania przyjemność. Gdy zaś mowa o częstym ładowaniu powiązanych z węzłami stron z dysku, sytuacja staje się jeszcze gorsza. żałosna.

Drzewa B, będąc ewolucją drzew binarnych, rozwiązują problemy opisane w poprzednim akapicie. Po pierwsze, są samobalansujące. Po drugie, każdy ich węzeł dzieli zbiór potomnych kluczy nie na 2, a na M uporządkowanych podzbiorów, przy czym liczba M może być dość duża, sięgająca setek, a nawet tysięcy.

Dzięki temu:

1. W każdym węźle znajduje się duża liczba już uporządkowanych kluczy, a drzewa stają się bardzo niskie.
2. Drzewo nabywa właściwość lokalności w pamięci, ponieważ bliskie wartości kluczy naturalnie znajdują się blisko siebie w jednym lub sąsiednich węzłach.
3. Zmniejsza się liczba pośrednich węzłów podczas przechodzenia w dół drzewa podczas operacji wyszukiwania.
4. Zmniejsza się liczba odczytywanych docelowych węzłów przy zapytaniach zakresowych, ponieważ w każdym z nich znajduje się już duża liczba uporządkowanych kluczy.

W LMDB do przechowywania danych wykorzystuje się jedną z wariantów drzewa B, znaną jako drzewo B+. Na powyższym schemacie przedstawione są trzy typy węzłów, które się w nim znajdują:

1. Na szczycie znajduje się korzeń (root). Uosabia on nic innego jak koncepcję bazy danych wewnątrz magazynu. W ramach jednej instancji LMDB można tworzyć kilka baz danych, które dzielą między sobą zamapowaną wirtualną przestrzeń adresową. Każda z nich zaczyna się od własnego korzenia.
2. Na najniższym poziomie znajdują się liście (leaf). To one i tylko one zawierają przechowywane w bazie danych pary klucz-wartość. W tym tkwi istota B+-drzew. Jeśli zwykłe B-drzewo przechowuje części value w węzłach wszystkich poziomów, to wariant B+-tylko na najniższym. Ustalając ten fakt, będziemy dalej nazywać podtyp drzewa używanego w LMDB po prostu B-drzewem.
3. Między korzeniem a liśćmi znajduje się 0 lub więcej poziomów technicznych z węzłami nawigacyjnymi (branch). Ich zadaniem jest podział uporządkowanego zbioru kluczy między liśćmi.

Fizycznie węzły to bloki pamięci o z góry określonej długości. Ich rozmiar jest wielokrotnością rozmiaru stron pamięci w systemie operacyjnym, o którym mówiliśmy wcześniej. Poniżej przedstawiona jest struktura węzła. W nagłówku znajduje się meta-informacja, z których najbardziej oczywistą w tym przykładzie jest suma kontrolna. Następnie znajdują się informacje o przesunięciach, według których znajdują się komórki z danymi. W roli danych mogą występować либо klucze, jeśli mówimy o węzłach nawigacyjnych, либо całe pary klucz-wartość w przypadku liści. O strukturze stron można poczytać bardziej szczegółowo w pracy „Ocena wydajnych magazynów klucz-wartość”.

Po zrozumieniu wewnętrznej struktury węzłów-stron, drzewo B LMDB będziemy upraszczać w następujący sposób.

Strony z węzłami są kolejno rozmieszczone na dysku. Strony z większym numerem znajdują się bliżej końca pliku. Tak zwana strona meta (meta page) zawiera informacje o przesunięciach, według których można znaleźć korzenie wszystkich drzew. Po otwarciu pliku LMDB skanuje go strona po stronie od końca do początku w poszukiwaniu ważnej strony meta, a przez nią odnajduje istniejące bazy danych.

Teraz, mając pojęcie o logicznej i fizycznej strukturze organizacji danych, możemy przejść do omówienia trzeciego filaru LMDB. To właśnie dzięki niemu wszystkie modyfikacje magazynu odbywają się transakcyjnie i są od siebie izolowane, nadając bazie danych w ogóle cechę wielowersyjności.

3.3. Filar nr 3. Copy-on-write

Niektóre operacje na drzewie B zakładają wprowadzenie całej serii zmian w jego węzłach. Przykładem jest dodanie nowego klucza do węzła, w którym osiągnięto już maksymalną pojemność. W takim przypadku konieczne jest, po pierwsze, podzielenie węzła na dwa, a po drugie, dodanie odniesienia do nowo utworzonego węzła podrzędnego w jego rodzicu. Procedura ta może być potencjalnie bardzo niebezpieczna. Jeśli z jakiegoś powodu (awaria, wyłączenie zasilania itp.) wystąpi tylko część zmian z serii, to drzewo pozostanie w niespójnym stanie.

Jednym z tradycyjnych rozwiązań zapewniających bazie danych odporność na awarie jest dodanie obok drzewa B dodatkowej struktury danych na dysku — dziennika transakcji, znanego również jako log przedmodyfikacji (WAL). Jest to plik, do którego na końcu zapisuje się planowaną operację przed modyfikacją samego drzewa B. W ten sposób, jeśli w czasie samodiagnozy wykryta zostanie uszkodzenie danych, baza danych konsultuje się z dziennikiem, aby przywrócić porządek.

LMDB jako mechanizm zapewnienia odporności na awarie wybrał inny sposób, który nazywa się copy-on-write. Jego istota polega na tym, że zamiast aktualizować dane na istniejącej stronie, najpierw całkowicie je kopiuje, a wszystkie modyfikacje wprowadza już w kopii.

Następnie, aby zaktualizowane dane były dostępne, należy zmienić odnośnik do aktualnego węzła w jego rodzicu. Ponieważ aby to zrobić, również trzeba go zmodyfikować, jest on najpierw kopiowany. Proces ten kontynuuje się rekurencyjnie aż do korzenia. Ostatnie zmiany dotyczą danych na stronie metadanych.

Jeśli podczas procedury aktualizacji nastąpi awaryjne zakończenie procesu, nowa strona meta może się nie utworzyć, lub nie zostanie zapisana na dysku do końca, a jej suma kontrolna będzie niepoprawna. W obu tych przypadkach nowe strony będą niedostępne, a stare nie ucierpią. Dzięki temu LMDB nie musi prowadzić dziennika zapisu w celu utrzymania spójności danych. De facto struktura przechowywania danych na dysku opisana powyżej, jednocześnie przejmuje tę funkcję. Brak wyraźnego dziennika transakcji to jedna z cech LMDB, która zapewnia wysoką prędkość odczytu danych.

Uzyskana konstrukcja nazywana drzewem B z jedynie dołączanymi elementami naturalnie zapewnia izolację transakcji i wielowersyjność. W LMDB z każdą otwartą transakcją skojarzony jest aktualny na dany moment korzeń drzewa. Dopóki transakcja nie zostanie zakończona, strony związane z nią drzewo nigdy nie będą zmieniane ani ponownie wykorzystywane dla nowych wersji danych. Dzięki temu można pracować przez dowolnie długi czas tylko z tym zestawem danych, który był aktualny w momencie otwarcia transakcji, nawet jeśli magazyn w tym czasie ciągle się aktualizuje. Oto istota wielowersyjności, która czyni LMDB idealnym źródłem danych dla nas wszystkich. UICollectionViewOtwierając transakcję, nie ma potrzeby zwiększania śladu pamięci aplikacji, pilnie wyciągając aktualne dane do jakiejkolwiek struktury in-memory, obawiając się zostać z pustymi rękami. Ta cecha korzystnie odróżnia LMDB od SQLite, który nie może poszczycić się taką całkowitą izolacją. Otwierając w tym ostatnim dwie transakcje i usuwając jakąś wpis w jednej z nich, tej samej wpisu nie będzie można już odzyskać w ramach drugiej pozostającej.

Drugą stroną medalu jest potencjalnie znacznie większe zużycie pamięci wirtualnej. Na slajdzie widać, jak będzie wyglądać struktura bazy danych, gdy jej modyfikacja będzie miała miejsce jednocześnie z 3 otwartymi transakcjami do odczytu, które patrzą na różne wersje bazy danych. Ponieważ LMDB nie może ponownie wykorzystać węzłów osiągalnych z korzeni związanych z aktualnymi transakcjami, magazyn nie ma innego wyboru, jak tylko umieścić w pamięci kolejny czwarty korzeń i ponownie sklonować pod nim modyfikowane strony.

Warto tutaj przypomnieć sobie sekcję o plikach pamięci mapowanej. Choć dodatkowe zużycie pamięci wirtualnej nie powinno nas specjalnie niepokoić, ponieważ nie wpływa na pamięć aplikacji, to jednak zauważono, że iOS jest bardzo oszczędny w jej przydzielaniu, a my nie możemy, jak w przypadku serwera czy komputera stacjonarnego, bez wahania przydzielić regionu LMDB o pojemności 1 terabajta i całkowicie zignorować tę cechę. Należy starać się, aby czas życia transakcji był jak najkrótszy.

4. Projektowanie schemy danych na bazie API klucz-wartość

Analizę API rozpoczniemy od omówienia podstawowych abstrakcji, które oferuje LMDB: środowisko i bazy danych, klucze i wartości, transakcje oraz kursory.

Uwagi dotyczące fragmentów kodu

Wszystkie funkcje w publicznym API LMDB zwracają wynik swojej pracy w postaci kodu błędu, jednak w kolejnych fragmentach kodu jego sprawdzenie zostało pominięte na rzecz zwięzłości. W praktyce używaliśmy naszego forka C++ wrappera lmdbxx, w którym błędy manifestują się jako wyjątki C++.

Jako najszybszy sposób podłączenia LMDB do projektu na iOS lub macOS proponuję mój CocoaPod POSLMDB.

4.1. Podstawowe abstrakcje

Środowisko (environment)

Struktura MDB_env jest zbiornikiem wewnętrznego stanu LMDB. Rodzina funkcji z prefiksem mdb_env pozwala skonfigurować niektóre jego właściwości. W najprostszej formie 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 Chmura Mail.ru zmienialiśmy domyślne wartości tylko dla dwóch parametrów.

Pierwszym z nich jest rozmiar wirtualnej przestrzeni adresowej, na którą mapowany jest plik magazynu. 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ę cechę iOS, maksymalna wielkość magazynu jest dobierana dynamicznie. Zaczynając od pewnej wartości, jest ona kolejno zmniejszana, aż funkcja mdb_env_open nie zwróci wyniku różnego od ENOMEM. Teoretycznie istnieje również przeciwna droga — najpierw przydzielić silnikowi minimalną ilość pamięci, a następnie, w przypadku wystąpienia błędów MDB_MAP_FULL, zwiększać ją. Jednak jest to o wiele bardziej skomplikowane. Powód jest taki, że procedura ponownego przydzielania pamięci (remap) za pomocą funkcji mdb_env_set_map_size unieważnia wszystkie encje (kursory, transakcje, klucze i wartości), które zostały wcześniej uzyskane z silnika. Uwzględnienie takiego obrotu spraw w kodzie znacznie go skomplikuje. Jeśli jednak wirtualna pamięć jest dla Ciebie bardzo ważna, może to być powód, aby przyjrzeć się daleko posuniętemu forkowi MDBX, gdzie wśród deklarowanych funkcji znajduje się „automatyczna, dynamiczna zmiana rozmiaru bazy danych”.

Drugi parametr, którego domyślna wartość nam nie odpowiada, reguluje mechanikę zapewnienia bezpieczeństwa wątków. Niestety, przynajmniej w iOS 10 występują problemy z obsługą lokalnej pamięci wątków. Z tego powodu w powyższym przykładzie magazyn otwierany jest z flagą MDB_NOTLS. Ponadto konieczne było również forkowanie opakowania C++ lmdbxx, aby usunąć zmienne z tym atrybutem i w niej.

Bazy danych

Baza danych to osobny instancja drzewa B, o którym rozmawialiśmy wcześniej. Jej otwarcie odbywa się wewnątrz transakcji, co na początku może się wydawać 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 to encja magazynu, a nie konkretnej bazy danych. Taka koncepcja pozwala na wykonywanie atomowych operacji na encjach znajdujących się w różnych bazach danych. Teoretycznie otwiera to możliwość modelowania tabel w postaci różnych baz, ale w swoim czasie poszedłem inną drogą, opisaną szczegółowo poniżej.

Klucze i wartości

Struktura MDB_val modeluje koncepcję zarówno klucza, jak i wartości. Magazyn nie ma pojęcia o ich semantyce. Dla niego coś, co innego, to po prostu tablica bajtów o określonym rozmiarze. Maksymalny rozmiar klucza to 512 bajtów.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

Za pomocą komparatora magazyn porządkuje klucze rosnąco. Jeśli nie zastąpisz go własnym, będzie używany domyślny, który sortuje je bajt po bajcie w kolejności leksykograficznej.

Transakcje

Zasada działania transakcji jest szczegółowo opisana w poprzednim rozdziale, dlatego tutaj w skrócie powtórzę ich główne właściwości:

1. Wsparcie dla wszystkich podstawowych właściwości ACID: atomowość, spójność, izolacja i niezawodność. Nie mogę nie zauważyć, że w przypadku durability na macOS i iOS występuje błąd, który został naprawiony w MDBX. Więcej informacji można znaleźć w ich README.
2. Podejście do wielowątkowości opisuje schemat „jedno zapisujący / wielu czytających”. Pisarze blokują się nawzajem, ale nie blokują czytelników. Czytelnicy nie blokują ani pisarzy, ani siebie nawzajem.
3. Wsparcie dla zagnieżdżonych transakcji.
4. Wsparcie dla multiwersji.

Multiwersyjność w LMDB jest tak dobra, że chcę pokazać ją w akcji. Z poniższego kodu widać, że każda transakcja działa dokładnie na tej wersji bazy danych, która była aktualna w momencie jej otwarcia, będąc całkowicie izolowaną od wszelkich późniejszych zmian. Inicjalizacja magazynu i dodanie do niego testowego wpisu nie przedstawiają niczego interesującego, dlatego te rytuały pozostawiono w spoilerze.

Dodanie testowego wpisu

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;

// Otwieramy 2 transakcje, z których każda odnosi się
// do wersji bazy danych z jednym wpisem.
mdb_txn_begin(env, NULL, 0, &txn1); // odczyt-zapis
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // tylko odczyt

// W ramach pierwszej transakcji usuwamy istniejący wpis z bazy danych.
mdb_del(txn1, dbi, &key, NULL);
// Zatwierdzamy usunięcie.
mdb_txn_commit(txn1);

// Otwieramy trzecią transakcję, która odnosi się do
// aktualnej wersji bazy danych, gdzie wpis już nie istnieje.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Upewniamy się, że wpis o poszukiwanym kluczu już nie istnieje.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Kończymy transakcję.
mdb_txn_abort(txn3);

// Upewniamy się, że w ramach drugiej transakcji, otwartej w momencie
// istnienia wpisu w bazie danych, wciąż można go znaleźć po kluczu.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Sprawdzamy, że po kluczu otrzymano nie byle jakie śmieci, a ważne dane.
assert(*(int *)val.mv_data == 997);
// Kończymy transakcję, działając z chociaż i przestarzałą, ale spójną bazą danych.
mdb_txn_abort(txn2);

Z własnej rekomendacji sugeruję spróbować przeprowadzić podobny zabieg z SQLite i zobaczyć, co z tego wyjdzie.

Wielowersyjność wnosi bardzo przyjemne korzyści w życie programisty iOS. Dzięki tej właściwości można łatwo i bez wysiłku regulować prędkość aktualizacji źródła danych (data source) dla ekranowych formularzy, mając na uwadze doświadczenie użytkownika. Na przykład weźmy funkcjonalność aplikacji Obłok Mail.ru, jaką jest automatyczne ładowanie treści z systemowej galerii multimedialnej. Przy dobrym połączeniu klient może dodawać na serwer kilka zdjęć na sekundę. Jeżeli po każdym przesłaniu aktualizować UICollectionView multimedia w chmurze użytkownika, to można zapomnieć o 60 klatkach na sekundę i płynności przewijania w trakcie tego procesu. Aby zapobiec częstym aktualizacjom ekranu, należy jakoś ograniczyć tempo zmian danych w bazie UICollectionViewDataSource.

Jeśli baza danych nie obsługuje mnożnych wersji i pozwala pracować tylko z aktualnym stanem, to aby stworzyć stabilny w czasie zrzut danych, należy wykonać jego kopię albo w jakiejś strukturze danych w pamięci, albo w tabeli tymczasowej. Każde z tych podejść jest bardzo kosztowne. W przypadku magazynu w pamięci ponosimy wydatki zarówno związane z pamięcią, wynikające z przechowywania skonstruowanych obiektów, jak i czasowe, związane z nadmiernymi konwersjami ORM. Natomiast tabela tymczasowa jest jeszcze droższą przyjemnością, mającą sens tylko w nietrywialnych przypadkach.

Wielowersyjność LMDB elegancko rozwiązuje problem utrzymania stabilnego źródła danych. Wystarczy po prostu otworzyć transakcję i voilà — dopóki jej nie zakończymy, zbiór danych w naszej gwarancji jest utrwalony. Logika prędkości jego aktualizacji znajduje się teraz całkowicie i wyłącznie w rękach warstwy prezentacyjnej przy całkowitym braku znaczących kosztów zasobów.

Kursory

Kursory dostarczają mechanizm do uporządkowanego iterowania po parach klucz-wartość poprzez przechodzenie drzewa B. Bez nich niemożliwe byłoby efektywne modelowanie tabel w bazie danych, do których przechodzimy.

4.2. Modelowanie tabel

Właściwość uporządkowania kluczy pozwala na budowanie na podstawowych abstrakcjach struktury o wysokim poziomie, jaką jest tabela. Rozważmy ten proces na przykładzie głównej tabeli klienta w chmurze, w której jest przechowywana informacja o wszystkich plikach i folderach użytkownika.

Schemat tabeli

Jednym z częstych scenariuszy, pod który powinien być dostosowany schemat tabeli z drzewem folderów, jest pobieranie wszystkich elementów znajdujących się w określonym katalogu. Dobrym modelem organizacji danych dla efektywnych zapytań tego rodzaju jest Lista Adjacency. Aby go zrealizować na bazie magazynu klucz-wartość, należy posortować klucze plików i folderów w taki sposób, aby były grupowane na podstawie przynależności do nadrzędnego katalogu. Ponadto, aby wyświetlić zawartość katalogu w znanym dla użytkownika systemie Windows (najpierw foldery, następnie pliki, a oba są posortowane alfabetycznie), należy dodać do klucza odpowiednie dodatkowe pola.

Na poniższym obrazku przedstawiony jest sposób, w jaki klucze mogą być reprezentowane jako tablica bajtów, zgodnie z postawionym zadaniem. Na początku umieszczane są bajty z identyfikatorem katalogu nadrzędnego (czerwone), następnie bajty z typem (zielone), a na końcu z nazwą (niebieskie). Po posortowaniu domyślnym komparatorem LMDB w porządku leksykograficznym, są one uporządkowywane w wymagany sposób. Sekwencyjne przechodzenie przez klucze z tym samym czerwonym prefiksem daje nam powiązane wartości w kolejności, w jakiej powinny być wyświetlane w interfejsie użytkownika (po prawej), nie wymagając dodatkowego przetwarzania.

Serializacja kluczy i wartości

Na świecie wymyślono wiele metod serializacji obiektów. Ponieważ jedynym naszym wymaganiem była prędkość, wybraliśmy najszybszą metodę z dostępnych — zrzut pamięci zajmowanej przez instancję struktury języka C. Tak więc klucz elementu katalogu można odwzorować następującą strukturą NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Aby zapisać NodeKey w magazynie, należy w obiekcie MDB_val ustawić wskaźnik na dane na początku struktury, a ich rozmiar obliczyć 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 bazy danych jako ważnym czynniku wyboru wspomniałem o minimalizacji dynamicznych alokacji w ramach operacji CRUD. Kod funkcji serialize pokazuje, jak w przypadku LMDB można całkowicie uniknąć ich podczas wstawiania nowych rekordów do bazy danych. Przybyły z serwera tablica bajtów najpierw zostaje przekształcona w struktury stosowe, a następnie są one w trywialny sposób zrzucane do magazynu. Biorąc pod uwagę, że wewnątrz LMDB również nie ma dynamicznych alokacji, można uzyskać fantastyczną sytuację – wykorzystanie tylko pamięci stosowej do pracy z danymi przez całą drogę od sieci do dysku!

Porządkowanie kluczy z wykorzystaniem binarnego komparatora

Kolejność kluczy jest określana przez specjalną funkcję, nazywaną komparatorem. Ponieważ silnik nie ma żadnej wiedzy o semantyce zawartych w nich bajtów, domyślnemu komparatorowi pozostaje jedynie uporządkować klucze w porządku leksykograficznym, posługując się porównywaniem bajtów. Używanie go do sortowania struktur jest niczym innym jak goleniem przeciwnika siekierą. Niemniej jednak, w prostych przypadkach uważam ten sposób za akceptowalny. Alternatywa opisana jest nieco niżej, a tutaj wspomnę o kilku rozrzuconych na tej drodze pułapkach.

Pierwsza rzecz, o której należy pamiętać — to przedstawienie w pamięci prymitywnych typów danych. Tak więc, na wszystkich urządzeniach Apple, zmienne całkowite przechowywane są w formacie Little Endian. Oznacza to, że najmniej znaczący bajt znajduje się po lewej stronie, a posortowanie liczb całkowitych za pomocą ich porównania bajtowego nie jest możliwe. Na przykład, próba zrobienia tego z zestawem liczb od 0 do 511 doprowadzi do następującego wyniku.

// 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ć przechowywane w kluczu w formacie odpowiednim dla porównywarki bajtów. Potrzebne przekształcenie pomoże wykonać funkcje z rodziny hton* (w szczególności htons dla dwu-bajtowych liczb z przykładu).

Format reprezentacji ciągów w programowaniu — to, jak wiadomo, cały historię. Jeśli semantyka ciągów oraz używana do ich reprezentacji w pamięci kodowanie zakłada, że na jeden znak może przypadać więcej niż jeden bajt, to lepiej od razu zrezygnować z pomysłu używania domyślnego komparatora.

Druga rzecz, którą trzeba mieć na uwadze — zasady wyrównania przez kompilator pól struktury. Z tego powodu w pamięci między polami mogą powstawać bajty z wartościami śmieciowymi, co oczywiście łamie sortowanie bajtowe. Aby wyeliminować śmieci, należy albo deklarować pola w ściśle określonej kolejności, pamiętając o zasadach wyrównania, albo użyć w deklaracji struktury atrybutu packed.

Sortowanie kluczy zewnętrznym komparatorem

Logika porównywania kluczy może okazać się zbyt skomplikowana dla binarnego komparatora. Jednym z wielu powodów jest istnienie wewnątrz struktur pól technicznych. Ilustruję ich pojawienie się na przykładzie już znanego nam klucza dla elementu katalogu.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Pomimo swojej prostoty, w przytłaczającej większości przypadków zużywa zbyt dużo pamięci. Bufor na nazwę zajmuje 256 bajtów, chociaż średnio nazwy plików i folderów rzadko przekraczają 20-30 znaków.

Jedną ze standardowych metod optymalizacji rozmiaru wpisu jest „przycinanie” go do rzeczywistego rozmiaru. Jego istota polega na tym, że zawartość wszystkich pól o zmiennej długości jest przechowywana w buforze na końcu struktury, a ich długości znajdują się w osobnych zmiennych. W zgodzie z tym podejściem, klucz NodeKey jest przekształcany w następujący sposób.

typedef struct NodeKey {
    EntityId parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Następnie przy serializacji jako rozmiar danych podawany jest nie sizeof całej struktury, ale rozmiar wszystkich pól o stałej długości plus rozmiar rzeczywiście używanej 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 przeprowadzonego refaktoryzowania uzyskano znaczną oszczędność miejsca zajmowanego przez klucze. Jednak z powodu technicznego pola nameLength, domyślny binarny komparator nie nadaje się już do porównywania kluczy. Jeśli go nie zastąpimy własnym, długość nazwy będzie bardziej priorytetowym czynnikiem przy sortowaniu niż sama nazwa.

LMDB pozwala przypisać każdej bazie danych własną funkcję porównania kluczy. Robi się to za pomocą funkcji mdb_set_compare wyłącznie przed otwarciem. Z oczywistych powodów, przez cały czas życia bazy danych nie można jej zmieniać. Komparator otrzymuje dwa klucze w formacie binarnym, a na wyjściu zwraca wynik porównania: mniejszy (-1), większy (1) lub równy (0). Pseudokod dla NodeKey wygląda tak.

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 mają ten sam typ, bezwzględne przekształcenie ich reprezentacji binarnej na typ struktury klucza aplikacji jest dozwolone. Jest tutaj jeden niuans, ale zostanie on omówiony nieco niżej w podrozdziale „Czytanie wpisów”.

Serializacja wartości

Praca z kluczami przechowywanych rekordów LMDB przebiega niezwykle intensywnie. Ich porównanie odbywa się w ramach każdej operacji aplikacyjnej, a wydajność całego rozwiązania zależy od szybkości działania porównywarki. W idealnym świecie do porównania kluczy wystarczyłby domyślny binarny porównywacz, ale gdy trzeba użyć własnego, procedura deserializacji kluczy powinna być maksymalnie szybka.

Baza danych nie jest szczególnie zainteresowana częścią wartościową rekordu (wartością). Jej przekształcenie z reprezentacji bajtowej w obiekt następuje tylko wtedy, gdy jest to już wymagane przez kod aplikacyjny, na przykład do wyświetlenia na ekranie. Ponieważ zdarza się to stosunkowo rzadko, wymagania dotyczące szybkości tej procedury nie są tak krytyczne, a w jej realizacji możemy w znacznie większym stopniu kierować się wygodą. Na przykład do serializacji metadanych o jeszcze niezaładowanych plikach używamy NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

Jednak zdarzają się sytuacje, gdy wydajność ma znaczenie. Na przykład, przy zapisywaniu metainformacji o strukturze plików w użytkowym chmurze, korzystamy z tego samego zrzutu pamięci obiektów. Specyfiką zadania dotyczącego formowania ich zserializowanej reprezentacji jest fakt, że elementy katalogu są modelowane przez hierarchię klas.

Aby to zrealizować w języku C, specyficzne pola dziedziczących klas są przenoszone do oddzielnych struktur, a ich powiązanie z bazową klasą ustala się poprzez pole typu union. Aktualna zawartość unii jest określana przez atrybut techniczny type.

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

Zserializowane klucze i wartości można dodawać do magazynu. W tym celu używa się funkcji mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

Na etapie konfiguracji magazynowi można zezwolić lub zabronić przechowywania wielu wpisów z tym samym kluczem. Jeśli duplikacja kluczy jest zabroniona, można przy wstawianiu wpisu określić, czy dozwolone jest aktualizowanie już istniejącego wpisu, czy nie. Jeśli nadpisanie może nastąpić tylko w wyniku błędu w kodzie, można się zabezpieczyć, ustawiając flagę NOOVERWRITE.

Odczyt wpisów

Do odczytu wpisów w LMDB przeznaczona jest funkcja mdb_get. Jeśli para klucz-wartość była wcześniej zapisana w strukturach, to procedura ta 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;​
}

Przedstawiony listing pokazuje, jak serializacja przez zrzut struktur pozwala pozbyć się alokacji dynamicznych nie tylko podczas zapisu, ale także przy odczycie danych. Uzyskany z funkcji mdb_get wskaźnik patrzy dokładnie na ten adres pamięci wirtualnej, w którym baza danych przechowuje bajtowe przedstawienie obiektu. W rzeczywistości mamy do czynienia z pewnym rodzajem ORM, praktycznie bez opłat, zapewniającym bardzo wysoką prędkość odczytu danych. Mimo całej urody podejścia, należy pamiętać o kilku związanych z nim cechach.

1. Dla transakcji tylko do odczytu wskaźnik na strukturę-wartość będzie gwarantowanie pozostawał ważny jedynie do momentu zakończenia transakcji. Jak wcześniej wspomniano, strony drzewa B, na których znajduje się obiekt, dzięki zasadzie copy-on-write pozostają niezmienne, dopóki co najmniej jedna transakcja do nich się odnosi. Jednocześnie, gdy tylko ostatnia związana z nimi transakcja się kończy, strony mogą być ponownie wykorzystane dla nowych danych. Jeśli obiekty muszą przetrwać transakcję, która je utworzyła, trzeba będzie je jednak skopiować.
2. Dla transakcji do odczytu i zapisu wskaźnik na uzyskaną strukturę-wartość będzie ważny jedynie do pierwszej procedury modyfikującej (zapisu lub usunięcia danych).
3. Pomimo że struktura NodeValue nie jest pełnoprawna, a przycięta (patrz podrozdział „Porządkowanie kluczy zewnętrznym komparatorem”), poprzez wskaźnik można spokojnie odwoływać się do jej pól. Ważne, aby jej nie dereferencjonować!
4. W żadnym wypadku nie należy modyfikować struktury przez uzyskany wskaźnik. Wszystkie zmiany powinny być dokonywane tylko za pomocą metody mdb_put. Jednak z całym pragnieniem, aby to zrobić, nie będzie to możliwe, ponieważ obszar pamięci, w którym ta struktura się znajduje, jest zamapowany w trybie readonly.
5. Remapowanie pliku na przestrzeń adresową procesu w celu, na przykład, zwiększenia maksymalnego rozmiaru pamięci za pomocą funkcji mdb_env_set_map_size całkowicie unieważnia wszystkie transakcje i powiązane z nimi encje w ogóle oraz wskaźniki na odczytane obiekty w szczególności.

W końcu jeszcze jedna cecha jest tak podstępna, że jej ujawnienie nie zmieści się po prostu w jeszcze jednym punkcie. W rozdziale o drzewie B przedstawiłem schemat urządzenia jego stron w pamięci. Z niego wynika, że adres początku bufora z serializowanymi danymi może być całkowicie dowolny. Z tego powodu wskaźnik na nie, uzyskany w strukturze MDB_val i przekształcony w wskaźnik na strukturę, w ogólnym przypadku jest niewyważony. Jednocześnie architektury niektórych chipów (w przypadku iOS jest to armv7) wymagają, aby adres wszelkich danych był wielokrotnością rozmiaru słowa maszynowego, innymi słowy, bitowości systemu (dla armv7 — to 32 bity). Innymi słowy, operacja taka jak *(int *foo)0x800002 jest traktowana jak ucieczka i prowadzi do wyroku EXC_ARM_DA_ALIGN. Można uniknąć tak smutnego losu na dwa sposoby.

Pierwszy sprowadza się do wstępnego kopiowania danych do z góry wyrównanej struktury. Na przykład, w przypadku niestandardowego komparatora będzie to przedstawione 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 \/\/ ...
}

Alternatywną drogą jest wcześniejsze powiadomienie kompilatora, że struktury z kluczem i wartością mogą być niewyważone za pomocą atrybutu aligned(1). Na ARM taki sam efekt można osiągnięcie osiągnąć również za pomocą atrybutu packed. Biorąc pod uwagę, że dodatkowo sprzyja to optymalizacji zajmowanej przez strukturę przestrzeni, ten sposób wydaje mi się preferowany, chociaż przywołuje prowadzi do zwiększenia 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;

Zakres zapytań

Aby iterować po grupie rekordów w LMDB, przewidziano abstrakcję kursora. Jak z nim pracować, omówimy na przykładzie dobrze znanej nam tabeli z metadanymi chmury użytkownika.

W ramach wyświetlania listy plików w katalogu należy znaleźć wszystkie klucze, z którymi powiązane są jego podległe pliki i foldery. W poprzednich podrozdziałach uporządkowaliśmy klucze NodeKey w taki sposób, aby były one najpierw uporządkowane według identyfikatora katalogu nadrzędnego. W związku z tym technicznie zadanie uzyskania zawartości folderu sprowadza się do ustawienia kursora na górnej granicy grupy kluczy z określonym prefiksem, a następnie iterowania do dolnej granicy.

Górną granicę można znaleźć "na oko" poprzez sekwencyjne wyszukiwanie. W tym celu kursor ustawiany jest na początku całej listy kluczy w bazie danych i następnie inkrementuje się, aż pod nim znajdzie się klucz z identyfikatorem katalogu nadrzędnego. Podejście to ma dwa oczywiste wady:

1. Liniowa złożoność wyszukiwania, chociaż, jak wiadomo, w drzewach w ogóle, a w drzewach B w szczególności, można to zrobić w czasie logarytmicznym.
2. Na próżno wczytywane są z pliku do pamięci głównej wszystkie strony, poprzedzające poszukiwaną, co jest niezwykle kosztowne.

Na szczęście w API LMDB przewidziano skuteczny sposób początkowego pozycjonowania kursora. W tym celu należy utworzyć taki klucz, którego wartość będzie z góry mniejsza lub równa kluczowi znajdującemu się na górnej granicy przedziału. Na przykład, w odniesieniu do listy na przedstawionym powyżej rysunku, możemy utworzyć taki klucz, w którym pole parentId będzie równe 2, a wszystkie pozostałe będą wypełnione zerami. Taki częściowo wypełniony klucz podawany jest na wejściu funkcji mdb_cursor_get z określeniem operacji 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 górna granica grupy kluczy została znaleziona, to następnie iterujemy po niej, aż napotkamy albo klucz z innym parentId, albo klucze całkowicie się skończą.

do {
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);
    // przetwarzanie...
} while (MDB_NOTFOUND != rc && // sprawdzenie końca tabeli
         IsTargetKey(key));    // sprawdzenie końca grupy kluczy

Co miłe, w ramach iteracji za pomocą mdb_cursor_get otrzymujemy nie tylko klucz, ale i wartość. Jeśli w celu spełnienia warunków zapytania należy sprawdzić także pola z części value rekordu, są one dostępne bez dodatkowych działań.

4.3. Modelowanie relacji między tabelami

Jak dotąd udało nam się omówić wszystkie aspekty projektowania i pracy z jednolitym zbiorem danych. Można powiedzieć, że tabela to zbiór uporządkowanych rekordów składających się z par klucz-wartość. Jeśli przedstawimy klucz jako prostokąt, a związane z nim wartości jako równoległościan, powstanie wizualny schemat bazy danych.

​

Jednak w rzeczywistości rzadko udaje się obejść tak małym kosztem. Często w bazie danych konieczne jest, po pierwsze, posiadanie kilku tabel, a po drugie, wykonywanie zapytań w porządku innym niż klucz podstawowy. Ostatnia część tego rozdziału poświęcona jest ich tworzeniu i powiązaniu.

Tabele indeksowe

W aplikacji chmurowej znajduje się sekcja "Galeria". Wyświetla ona multimedia z całej chmury, posortowane według daty. Dla optymalnej realizacji takiego zapytania obok głównej tabeli należy utworzyć jeszcze jedną z nowym typem kluczy. Będzie zawierała pole z datą utworzenia pliku, które będzie pełniło rolę podstawowego kryterium sortowania. Ponieważ nowe klucze odnoszą się do tych samych danych co klucze w głównej tabeli, nazywają się kluczami indeksowymi. Na poniższym obrazku są one wyróżnione kolorem pomarańczowym.

Aby oddzielić od siebie klucze różnych tabel w jednej bazie danych, dodano im wszystkim dodatkowe pole techniczne tableId. Uczynienie go najważniejszym kryterium sortowania pozwala grupować klucze najpierw według tabel, a następnie wewnątrz tabel według własnych zasad.

Klucz indeksowy odnosi się do tych samych danych, co klucz podstawowy. Bezpośrednie wdrożenie tego właściwości poprzez asocjację kopii części value klucza podstawowego jest nieoptymalne z kilku względów.

1. Z punktu widzenia zajmowanej przestrzeni, ponieważ metadane mogą być dość rozbudowane.
2. Z punktu widzenia wydajności, ponieważ przy aktualizacji metadanych węzły będą musiały dokonać zapisu przy dwóch kluczach.
3. Z perspektywy wsparcia kodu, zapominając o zaktualizowaniu danych w jednym z kluczy, napotykamy trudny do uchwycenia błąd niespójności danych w magazynie.

Dalej omówimy, jak usunąć te niedociągnięcia.

Organizacja relacji między tabelami

Do połączenia tabeli indeksowej z tabelą główną doskonale nadaje się wzorzec „klucz jako wartość”. Jak wskazuje jego nazwa, jako część value indeksowego rekordu występuje kopia wartości klucza głównego. To podejście eliminuje wszystkie wymienione wcześniej wady związane z przechowywaniem kopii części value głównego rekordu. Jedyna opłata — aby uzyskać wartość według klucza indeksowego, należy wykonać 2 zapytania w bazie danych zamiast jednego. Schematycznie uzyskana struktura bazy danych wygląda następująco.

Kolejnym wzorcem organizacji relacji między tabelami jest „nadmiarowy klucz”. Jego sedno polega na dodaniu do klucza dodatkowych atrybutów, które nie są potrzebne do sortowania, lecz do odtworzenia powiązanego klucza. W aplikacji Chmura Mail.ru znajdują się rzeczywiste przykłady jego zastosowania, jednak aby uniknąć głębokiego wnikania w kontekst specyficznych frameworków iOS, podam wymyślony, ale znacznie bardziej zrozumiały przykład.

W chmurowych klientach mobilnych znajduje się strona, na której wyświetlane są wszystkie pliki i foldery, do których użytkownik przyznał dostęp innym osobom. Ponieważ takich plików jest relatywnie mało, a różnego rodzaju związane z nimi specyficzne informacje o publiczności jest wiele (kto ma dostęp, z jakimi prawami itd.), byłoby nieracjonalne obciążać nimi część value rekordu w tabeli głównej. Jeśli jednak zechcemy wyświetlić takie pliki w trybie offline, to gdzieś musimy je jednak przechowywać. Naturalnym rozwiązaniem jest stworzenie odrębnej tabeli dla tych danych. Na schemacie poniżej jej klucz ma prefiks „P”, a placeholder „propname” może być zastąpiony bardziej konkretną wartością „informacje publiczne”.

Wszystkie unikalne metadane, dla których utworzono nową tabelę, są przenoszone do części value rekordu. Jednocześnie, dane dotyczące plików i folderów, które już są przechowywane w głównej tabeli, nie mają być duplikowane. Zamiast tego do klucza „P” dodawane są nadmiarowe dane w postaci pól „node ID” i „timestamp”. Dzięki nim można skonstruować klucz indeksowy, według którego można uzyskać klucz podstawowy, a w końcu metadane węzła.

Podsumowanie

Oceniamy wprowadzenie LMDB pozytywnie. Po nim liczba zawieszeń aplikacji zmniejszyła się o 30%.

Wyniki wykonanej pracy znalazły oddźwięk poza zespołem iOS. Obecnie jedna z głównych sekcji „Pliki” w aplikacji dla Androida również przeszła na korzystanie z LMDB, a inne części są w toku. Język C, w którym zrealizowano magazyn klucz-wartość, okazał się dużym wsparciem, aby początkowo stworzyć aplikacyjną otoczkę wokół niego cross-platformowo w języku C++. Do bezproblemowego połączenia powstałej biblioteki C++ z kodem platformowym w Objective-C i Kotlinie użyto generatora kodu. Djinni z Dropboxa, ale to już zupełnie inna historia.

Źródło: habr.com