Własna baza NoSql – docelowa gramatyka, implementacja parsera i bazy noSql

Cześć,
kontynuując temat rozpoczęty w poprzednim wpisie, dziś pokaże jak wykorzystując antlr’a zbudować własny język którego będzie można użyć do napisania własnej bazy NoSql. Jeśli nie czytałeś poprzedniego wpisu – zapoznaj się z nim koniecznie – link do wpisu.

No to zacznimy… Od początku – czyli genezy tego co napiszemy.
Oprzemy się na już istniejącej bazie NoSql – na Redisie. Pisząc „oprzemy się” mam na myśli że protokół (język) którym będziemy się posługiwać w komunikacji z ta bazą będzie podobny. Ok, zdefiniujmy wymagania funkcjonalne – nasza baza danych powinna zapewnić takie jak:

– zapis/odczyt wartości tekstowej
– zapis/odczyt tablicy
– zapis/odczyt słownika
– sprawdzenie typu klucza
– możliwość usunięcie klucza

plus:

– powinna obsługiwać wiele połączeń jednocześnie
– powinna być dostępna via TCP
– powinna zapewnić atomowość operacji
– powinna zawierać obsługę błędów

Projekt nazwałem dumnie „RedisByMM” :) co nieco przypomina „PhpBB By Przemo” ;)

Jeszcze jedno wtrącenie na temat samych języków – mamy dwa „typy” języków – deklaratywne i imperatywne. Imperatywne języki to takie w których za pomocą składni języka opisuje się proces mający doprowadzić do żądanego efektu – czyli np. Python, C, Java itp.
Deklaratywne języki to języki w których nie opisuje się procesu w którego rezultacie coś ma się wykonać tylko opisujemy co chcemy uzyskać – przykładem jest SQL.

Nasz język będzie deklaratywny a sama gramatyk będzie wyglądać tak:

Widzimy że komendy jakie będzie implementować to po prostu:

sadd – dodaj do słownika
sdel – usuń ze słownika
sget – pobierz ze słownika
ladd – dodaj do listy
ldel – usuń z listy
lget – pobierz z listy
lgetall – pobierz całą zawartość listy
lpop – pobierz element z listy i go usuń z niej
get – pobierz wartość typu string
setv – dodaj klucz z wartością string
gettype – sprawdź typ
delk – usuń klucz

Dobra, dość gadania – czas coś napisać.
Zainstalujmy sobie pierw antlr:

Gdy to już mamy możemy w pliku gramatyki wygenerować sobie parser i lekser. Oczywiście w Pythonie.

Wygenerowało nam to kilka plików:

Te pliki zapakowałem do folderu lexical_libraries i stworzyłem taką strukturę katalogów (modułów):

Oczywiście venv i venv1 to virtualenvy – po prostu:)

Definiujemy sobie od razu setup.py:

deklarując w nim chociażby biblioteki zależne – jedna od używania parsera, leksera i listenera a druga zapewniająca dostęp po TCP używając pętli zdarzeń – antlr4 i gevent. Oczywiście gevent odchodzi trochę w cień kiedy mamy asyncio – ale nadal działa fajnie:)

Zauważ proszę że mamy jeden entrypoint – usytuowany w folderze database, pliku main i funkcji „run”.
Jego zawartość wygląda tak:

Całość jest dość prosta i polega na uruchomieniu serwera TCP używając gevent’a – więcej o tym możesz poczytać w tym wpisie.
Skupimy się tylko na tym kawałku:

W nim, dla każdego polecenia które przyjdzie do serwera, tworzymy obiekt leksera, parsera i listenera. Działanie leksera i parsera jest dla nas nieco „przeźroczyste” – my implementacje dokonujemy w Listenerze. Listener pozwala nam wykonać odpowiednie czynności przy „wejściu” na token jak i przy „wyjściu” z tokena. Nasza klasa powinna dziedziczyć po klasie listenera która została dla nas wygenerowana a naszym zadaniem jest nadpisanie tylko odpowiednich funkcji:

Wszystkie przeciążone tu metody znajdują się w klasie nadrzędnej. Zobacz proszę na którąkolwiek parę funkcji „enter-exit” np:

Przy każdym wejściu w token (czyli de facto przy każdym poleceniu skierowanym do bazy danych) używamy fabryki modułów i zapisujemy stworzoną klasę jako „current_module” – gdyż w ramach jednego połączenia nie będziemy mieli więcej niż jednej komendy w jednym czasie. Zobaczmy jak wygląda fabryka:

Nie robi ona zbyt dużo – tworzy ona z przekazanego argumentu (nazwy tokena) nazwę modułu odpowiedzialnego za wykonanie logiki, wiec np. dla „GET” będzie to klasa „GetModule”. Plik ten będzie init’em modułu „modules”, czyli znajdzie się w katalogu modules, w pliki __init__.py:

Każdy moduł będzie działał na „contextach” jak i na obiekcie bazy danych. Każdy moduł będzie musiał dziedziczyć po klasie która pozwoli mu „żyć” w ekosystemie projektu. Klasą bazową dla każdego modułu będzie klasa Module:

Jak pewnie się domyślasz po ciele tej klasy – każdy moduł będzie musiał mieć zdefiniowaną swoją metodę „_run” oraz posiadać klasę wewnętrzną o nazwie „ClassContext” – czyli naszym kontekście wywołania modułu.

Kontekst to nic innego jak lista argumentów dla modułu. Zauważ że poza metodami inicjalizującymi są jeszcze metody z serii „set_*” pozwalające zbudować pełny kontekst.

Przejdźmy przez te metody może na przykładzie polecenia:

Czyli np:

Przetwarzając takie polecenie wejdziemy pierw do metody „enterSetv” gdzie zbudujemy moduł odpowiedzialny za to polecenie. Moduł jest jeszcze bez kontekstu – tzn że nie zebraliśmy dla niego argumentów. Parser „przegląda” zadany mu string od lewej do prawej. Więc jak już pisałem – pierw trafi na słowo SETV i odpali dla niego funkcję enterSetV a My w niej stworzymy sobie odpowiednią klasę i zapamiętamy ją:)

Dalej w gramatyce możemy trafić na spację – olewamy i dalej na „klucz”. Nie mamy w parserze zdefiniowanej funkcji „enterKey” gdyż nie ma takiej potrzeby. Za to mamy „exitKey”:

Zobacz że w nim w ramach zapamiętanego modułu odpalamy „set_key”, czyli:

a więc tworzymy nowy kontekst (odpowiedni dla wybranego modułu) uzupełniając go o wartość wybranego klucza.

Ufff. Niby skomplikowane.. Ale nie do końca.

nie mogłem się powstrzymać :D

Dość śmieszków, lecimy dalej:)
Jak już dla modułu SETV zebraliśmy „klucz” czyli w naszym przykładzie „aa” to czas na zebranie wartości.
Parser odpali wtedy metodę exitVal a ona wykona metodą set_value uzupełniając nasz kontekst o wartość. I teraz na wyjściu całego polecenia, czyli na „exitSetv” możemy wykonać metodę „run” naszego modułu a jej rezultat wysłać do podłączonego klienta!

Zobacz że w przypadku komendy SETV dałem możliwość utworzenia kilku klucz na raz, np:

Ale nic to nie zmienia w gruncie rzeczy dla naszej implementacji – po prostu dla takiego polecenia zbierzemy trzy konteksty:)

Może żeby wszystko było turbo jasne i proste przejdziemy przez proces dla jeszcze jednego polecenia, np:

Czyli polecenia dodającego element do listy. A dokładnie wiele elementów do jednej listy. Dla przykładu:

Parser przeglądając dostarczony mu kod zacznie przeglądać go od lewej do prawej czyli pierwsze co znajdzie to słowo „LADD” i dopasuje go do gramatyki odpalając przy tym metodę „enterLadd”:

która korzystając z fabryki stworzy i zapamięta odpowiedni moduł. Moduł który zostanie wybrany to LaddModule:

Dalej parser (pomijając spacje) trafi na „klucz” i zgodnie z wcześniejszym opisem – w metodzie „exitKey” stworzy kontekst dla wcześniej wybranego modułu i uzupełni go o wartość „key”.

Nie bez przyczyny wybrałem komendę LADD, gdyż różni się ona od reszty jedną rzeczą – ma ona różną ilość kluczy i wartości a dokładniej – ma jeden klucz i niezliczoną ilość wartości. Generuje nam to problem, gdyż dotychczas mieliśmy sytuacje jasną – tworzymy klucz, potem dopisujemy wartość, kolejny klucz i kolejna wartość i tak dalej. Każdy klucz to nowa instancja klasy ClassContext odpowiedniej dla danego modułu. Teraz mam zgrzyt pod tytułem – tworzymy klucz, potem dopisujemy wartość, potem znów wartość.. I tu jeb – nie mam kontekstu do którego moglibyśmy dopisać wartość (nie miało co nam go stworzyć). Problem rozwiązałem warunkowym „doklejaniem” nowego kontekstu w momencie kolekcjonowania wartości:

a samo set_value rozszerzyłem to:

co jednoznacznie rozwiązuje nam problem:)

W ramach praktyki zachęcam do zaproponowania lepszego rozwiązania tego problemu – gdyż trochę słabo robić warunek dla jednego modułu.

Doobra, skoro już wiemy jak działa listener i jak kolekcjonujemy w pamięci argumenty dla każdego polecenia – czas zajrzeć do implementacji faktycznej bazy danych.

Dobra, więc nasza baza danych będzie reprezentowana w pamięci jako słownik. Zaskakujące, prawda? ;)

A każdy moduł będzie sobie odpalał konkretną metodą naszego interfejsu, np dla LADD funkcja _run() będzie wyglądać:

Idąc tym tropem sprawdźmy więc jak wygląda moduł database.

Metoda „add_to_list”:

jest bardzo prosta – jeśli pod kluczem nic nie ma, to co tworzymy, jeśli jest – to dopisujemy. Warto jednak zatrzymać się na chwilę nad tym czym jest „self.__data” :) ponieważ tu jest coś ciekawego:

Więc czym jest ten SynchronizedAccessDict? To coś co pomoże nam spełnić wymóg atomowości każdego polecenia.

Przeciążamy tutaj metody związane z operacją na słowniku i opakowujemy je w chroniący je nazwany semafor. Dzięki czemu dwie operacje na tym samym klucz zawsze wykonają się sekwencyjnie. Stan naszej bazy będzie spójny. Ten byt – nazwany semafor dopisałem sobie i wygląda tak:

czyli nic innego jak słownik (kolejny) semaforów – opuszczanych i zakładanych w razie potrzeby:)

Łał, mamy już sporo! Mamy gramatykę, parser, lekser, listener, obsługę atomowości… W sumie to można by już kończyć, ale została nam jeszcze jedna rzecz. Parser rzuca nam całkiem przyjemne błędy, warto je zwrócić użytkownikowi, np. podając samą komendę parser sugeruje że dalej powinna być spacja:

lub

Gdzie w drugim przypadku – pierwsza linijka jest od parsera a druga od nas – jako runtime error.

ewentualnie w przypadku słownika:

gdzie chcieliśmy pobrać coś ze słownika korzystając przy tym z klucza „intowego”. Runtime od nas informujący że nie dość że składnia jest nie poprawna to jeszcze pytamy o klucz który nie istnieje!

Dobra, żeby dodać komunikaty parsera do komunikacji z klientem należy stworzyć nowy listener i dodać go:

mowa oczywiście o

Natomiast sam ErrorListener jest bardzo prosty:

wyśle on wygenerowany, przefiltrowany błąd do użytkownika podłączonego do bazy.

Zerknij na demo naszego języka:

Powoli kończąc – nie wiem czy widzisz tutaj ogrom możliwość jakie ta technologia daje. Ja stworzyłem język deklaratywny, ale nic nie stoi na drodze byś Ty stworzył język imperatywny:)
Spokojnie jesteś w stanie po przeczytaniu tych dwóch wpisów stworzyć język który będzie albo dla zabawy – np będzie miał składnie wzorowaną na memach albo dla zysku – będzie np. obsługiwał kilka centrali o różnych interfejsach:)

Oczywiście kod który przedstawiłem nie jest wolny od błędów – np dodaj wartość string pod jakimś kluczem a potem potraktuj ten klucz metodą np. LADD :) exception gwarantowany:)

Tak czy siak – pokazuje ideę, więc jest wartościowy. Kod udostępniam zainteresowanym – https://gitlab.com/kajzur/redisbymm