Napsal jsem si databázi v C++

Možná někoho napadne, co je to za bláznivý nápad, proč by si někdo psal novou databázi. Není to zbytečná práce? Proč nesáhnout po něčem existujícím? Databází máme přehršel. Na druhou stranu, proč ne. Uplatnění si určitě najde

Co je DocDB^[1]

Nejprve bych trochu poupravil clickbaitový titulek. 

• Určitě se nejedná o „standalone“ databázi, ale o knihovnu pro C++, kdy je databáze integrální součástí C++ projektu – tedy přímo realizovaná ve výsledném programu, nikoliv tedy jako externí server.
• Nejde o relační databázi, ale o NoSQL databázi orientovanou na ukládání a zpracování dokumentů (document-oriented)
• Není postavená na zelené louce, ale využívá existující „databázový engine“ LevelDB^[2]. V dnešní době bych si asi netroufnul navrhovat kompletně celé perzistentní úložiště a vlastnosti, které LevelDB nabízí v tomto případě zcela postačují, ale o tom dále

Doufám, že teď už to nevypadá šíleně. Jde tedy vlastně jen o jakousi nadstavbu nad databází implementující Key-Value úložiště – pro tento low-level přístup já nazývám spíš jako databázový engine. 

Knihovna DocDB spadá někam na úroveň „middle-level“ databáze, protože i přes mnoho užitečných funkcí, které nabízí, doprogramování další věcí se nevyhneme. Což má výhody a nevýhody. Například nevýhodou je, že zde není žádný query language ani query executor, dotazy se samy neoptimalizují, to si musíte zařídit v C++ podle toho, co v databázi potřebujete vyhledat. Na druhou stranu to přináší obrovskou vyjadřující svobodu, vše se programuje v jednom jazyce za masivního používání šablon. 

Když už mluvíme o šablonách, tak DocDB je navržena jako header-only knihovna, právě proto, že drtivá většina tříd a struktur jsou šablony. 

Jak a proč to vzniklo

Napsat si databázi pro C++ nebylo rozhodnutí ze dne na den jako myšlenka šíleného programátora. Když se podíváte na github a najdete nejstarší větev, zjistíte, že první commit do této (již mrtvé větve) byl učiněn v červenci roku 2019. Pokud by se někomu chtělo probírat se historií, nenajde jeden projekt, ale asi čtyři projekty, jako kdyby někdo vývoj v určitém bodě zastavil, všechno smazal a začal znova. A skutečně tak to bylo. V jedné větvi dokonce najdete stabilní verzi která byla nasazena v reálné produkci. Tak i tato větev je dnes mrtvá.

Produkční nasazení jedné z prvních verzí vzniklo pro server zajišťující jistou mobilní hru pro nejmenovanou celostátní televizi. Aplikační server, který se interně jmenoval „game server“ měl klasické uspořádání ve formě load balancer → aplikační servery → databáze. Jako databáze byla zvolena CouchDB, a to z důvodu toho, že herní stav každého hráče byl koncipován jako dokument. Časem se však ukázalo, že i přesto, že CouchDB byla instalována v clusteru o 16 datových uzlech a každý aplikační server měl vlastní agregační uzel, nebyla databáze schopna zvládat některé špičkové zátěže tak, jak bych si představoval. V rámci mé implementace konektoru k této databázi v C++ (jednalo se v zásadě jen o C++ wrapper nad REST API této databáze) vznikl jednoduchý systém pro cachování indexů na straně aplikačního serveru s cílem ulehčit samotné databázi pro některé časově kritické dotazy. Tady se využilo faktu, že CouchDB lze použít i jako message broker a dále pak znalosti, jak se v CouchDB sestavují indexy. Index byl realizován v aplikačním serveru jako jednoduchá mapa klíčů a hodnot.

Cachování indexů na straně aplikačních serverů výrazně pomohlo výkonu, ale časem se objevil jiný problém. Jak přibývalo hráčů, odehraných her a dalších informací, indexy začaly bobtnat a jak jsem předeslal, implementace byla realizována pomocí mapy v paměti, rostla tak i paměťová náročnost aplikačních serverů. Proto jsem postupně paměťové mapy nahradil LevelDB. Tato databáze je snadno dostupná v knihovně libleveldb a kromě pár úprav v programu nevyžaduje žádnou zásadní instalaci a samotný update aplikačních serverů v produkci proběhl naprosto bez problémů.

Integrace do samotného aplikačního serveru si vyžádalo nějakou organizaci uložených dat, což vedlo ke vzniku knihovny DocDB, motivací bylo i možnost využití této knihovny i v některých budoucích projektech, které by nebyly navázané na CouchDB, jinými slovy, aby knihovna nesloužila jen ke cachování indexů, ale aby mohla spravovat i samotné ukládání a načítání dokumentů.

Celá věc se bohužel vyvinula jinak, soutěž byla zastavena a s tím se zastavil nejen vývoj a vylepšování serverů ale i práce na DocDB. Projekt zůstal nedopsaný a chyběla motivace v něm pokračovat. Občas jsem se k tomu vrátil s novými nápady, ale vždycky jsem toho po čase zanechal. 

A současný stav? Zapojil jsem se do komunity kolem protokolu NOSTR^[3] a jako proof of concept jsem se pokusil naprogramovat NOSTR relay. O vlastním protokolu mám v plánu napsat delší článek, takže jej nebudu rozebírat. Samotná relay není nic jiného než dokumentově orientovaná databáze. A to byl impuls dokončit DocDB – i když šlo spíš o kompletní přepis, protože původní kód vznikal v C++14 a časem v C++ 17. Mým požadavkem bylo mít novou knihovnu aspoň v C++20.

Krátce o LevelDB

LevelDB je key-value orientovaná databáze, která k ukládání dat používá levely a immutabilní mapy.  Immutabilní znamená, že každý zápis do databáze vede na vytvoření nové revize databáze která obsahuje změny vůči předchozí revizi. Pokud je změn hodně, jsou změny sloučeny do některého z levelů, přičemž se postupuje od levelu 0 do levelu 7, který je poslední. V každém level (kromě levelu 0) jsou klíče seřazeny, takže nalezení záznamu by mělo být velice rychlé. Díky téhle vlastností je rychlé i slučování levelů, které má složitost O(n). Level 0 je realizován v paměti pomocí map a navíc je zálohován na disku pomocí neseřazeného log souboru. Ostatní levely jsou realizovány v souborech na disku. Při přístupu k levelu se pak soubory cachují v paměti, přičemž velikost cache si mohu zvolit v konfiguraci. Slučování levelů probíhá na pozadí. Spouští se vždy, když daný level dosáhne určité velikosti. 

Z hlediska programátorského rozhraní je používání LevelDB velice jednoduché. Najdeme zde vlastně tři operace. Get(klíč) Put(klíč, hodnota) a Delete(klíč). Pro procházení databáze máme k dispozici databázové iterátory, kterými lze klíče hledat a iterovat nahoru i dolu. 

Mezi pokročilé nástroje pak patří batchové zápisy, které garantují atomický zápis do databáze … a bez nichž se v DocDB neobejdeme. A stejně důležité je schopnost vytvářet dočasné snapshoty, přitom jejich vytvoření je rychlé, protože se využívá vrstvení revizí databáze, takže snapshot není nic jiného, než zamknutá revize, která se drží v paměti (a na disku) tak dlouho, dokud existuje reference, která na ní ukazuje.

Dokumenty

Jak jsem předeslal, DocDB je dokumentově orientovaná databáze. Co je to dokument? Tohle je hlavním důvodem, proč je DocDB plná šablon. Dokument je totiž cokoliv, o čem prohlásíte, že je dokument. Prakticky se jedná o definici typu, který následně vkládáte jako argument do většiny tříd nabízené knihovnou. 

Dokument se definuje pomocí struktury, která musí vyhovovat konceptu^[4] docdb::DocumentDef

struct MyDocumentDef {
   using Type = MyDocument;

   template<typename InputIter>
   static MyDocument from_binary(InputIter b, InputIter e);

   template<typename OutputIter>
   static OutputIter to_binary(const MyDocument &doc, OutputIter out);
};

Protože leveldb ukládá klíče a hodnoty jako binární string, je třeba definovat funkce pro serializaci dokument do binární podoby a pro deserializaci z binární podoby zpět do objektu dokumentu. Vstupní a výstupní iterátory jsou standardní C++ iterátory které pracují s bajty (unsigned char). OutputIter bývá zpravidla instanciován jako std::back_inserter(c).

Deklarace šablon je zde nutností, na různých místech se může objevit iterátory různých typů, ať jde o serializaci do stringu, vektoru, nebo o deserializaci se stringu, vektoru nebo string_view. Serializační a deserializační funkce ví pouze to, že iterátor pracuje s bajty

Vestavěné dokumenty

Knihovna DocDB nabízí tři předem definované dokumenty, které můžeme použít a vyhneme se nutnosti definovat vlastní

• docdb::StringDocument – dokumentem je obyčejný std::string
• docdb::RowDocument – dokumentem je typ docdb::Row, který umožňuje uložit více hodnot z omezené sady podporovaných typů ve formě řádky tabulky. Typ Row se používá k implementaci klíčů, takže se k němu ještě dostaneme
• docdb::StructuredDocument – je navržen jako high-level struktura, která svou organizací připomíná javascriptový objekt a dokonce obsahuje serializaci a deserializaci ve formátu JSON. Ten si zaslouží samostatný článek

Rozdělení keyspace

Vrátím se k počáteční motivaci, kdy bylo potřeba do leveldb ukládat indexy. Ano, správně, jde o množné číslo, indexů bylo víc. A jistě by se nabízelo pro každý index použít jednu instanci leveldb::DB objektu. Není to ale dobrý nápad

• Tyhle objekty já považuji za „těžké“, minimálně proto, že si nárokují vlákno a jeden celý adresář. Je to jako pro každý index vyhradit jednu celou databázi. 
• Mít všechny indexy v jedné DB umožňuje snadněji implementovat transakce s využitím batchových zápisů

V rámci jedné instance databáze ( docdb::Database) je možné globální keyspace rozdělit až na 255 keyspaců a v nich realizovat stejné množství kolekcí. Termínem kolekce se zde rozumí nejen tabulky s daty, ale i indexy a další objekty (viz dále). Tohle číslo odpovídá tomu, že identifikátor keyspace má osm bitů – jeden bajt – a dále pak skutečnost, že jeden keyspace je vyhrazen. Ten má ID=255. V tomto keyspace se nachází tabulka přidělených keyspaces

Z hlediska programátorského rozhraní byla zvolena jiná organizace. Bylo by nepohodlné, kdyby si programátor musel pamatovat, které keyspace má přidělené které kolekci. Místo toho každou kolekci identifikujeme jménem. Kolekce organizujeme podobně jako soubory na disku a není zde omezení na to, co smí a nesmí jméno kolekce obsahovat. Tak můžeme roztřídit kolekce do jmenných prostorů (například „customes.by_id“). Mapování kolekce na keyspace id (zkráceně KID) řeší právě objekt docdb::Database a tyto informace drží v KID=255.

Domnívám se, že limit na 255 kolekcí je dostačující. Pokud opravdu někomu nestačí, pak by se měl zamyslet nad strukturou své databáze. I zde má možnost vytvořit dvě databáze, zvlášť pokud obsahují nezávislé, nepropojené tabulky. .

Příklad: inicializace storage

docdb::PDatabase db = docdb::Database::create(...);
docdb::Storage<MyDocumentDef> tabulka_1(db, "tabulka_1");
docdb::Indexer<docdb::Storage<MyDocumentDef>, IndexFn> tabulka_1_index(tabulka_1, "tabulka_1_index");

Kód pracuje tak, že po inicializace databáze vytvoří nebo připojí kolekci tabulka_1 jako storage (viz dále). Pokud kolekce neexistuje, je založena prázdná, pokud existuje, pak je otevřena. Přístup ke kolekci se pak děje přes objekt uložený v proměnné tabulka_1. Stejným způsobem se inicializuje index, ten máme k dispozici v proměnné tabulka_1_index.

Schéma organizace databáze v C++

┌─────────────────┐      ┌───────────────┐
│docdb::PDatabase │----->│docdb::Database│
└─────────────────┘      └───────────────┘
                             ▲
┌──────────────┐             │  ┌───────┐
│docdb::Storage│ ----------> └──┤Storage│ ─────────── updates ─────┐
└──────────────┘                └───────┘                          │
                                     ▲                             │
┌──────────────────────┐.            │ ┌────────────┐              │
│docdb::Indexer<unique>│-----------> ├─┤Unique index│        ◄─────┤
└──────────────────────┘             │ └────────────┘              │
                                     │                             │
┌─────────────────────┐              │ ┌─────┐                     │
│docdb::Indexer<multi>│ -----------> ├─┤Index│               ◄─────┤
└─────────────────────┘              │ └─────┘                     │
                                     │                             │
┌─────────────────────┐              │ ┌──────────────────────┐    │
│docdb::Indexer<multi>│ -----------> ├─┤Materializovaný pohled│ ◄──┤
└─────────────────────┘              │ └──────────────────────┘    │
                                     │     ▲                       │
                                     │     │ ┌───────────────┐     │
┌─────────────────┐                  │     └─┤Materializovaný│ ◄───┤
│docdb::Aggregator│     -----------> │       │souhrn         │     │
└─────────────────┘                  │       └───────────────┘     │
                                     │                             │
┌───────────────────────────┐        │ ┌──────────────────────┐    │
│docdb::IncrementalAgregator│------> └─┤Materializovaný souhrn│ ◄──┘
└───────────────────────────┘          └──────────────────────┘

Programátor má k dispozici několik tříd, které spolupracují. Na schématu jsem se snažil naznačit právě i vztahy. Vše začíná na objektu docdb::Database který obsahuje společný stav celé databáze, drží také instanci leveldb::DB. Tento objekt je alokován dynamicky pomocí std::make_shared. Programátor k němu přistupuje přes chytrý ukazatel docdb::PDatabase. Zároveň každý další objekt z knihovny DocDB drží jednu referenci, tím je zajištěno, že společná část „nikam sama neodejde“.

Hlavním úložištěm dokumentů je Storage který si alokuje jeden keyspace. Tam budeme ukládat dokumenty. Na Storage se odkazují indexery. Ty si také alokují keyspace, vždy jeden pro každou instanci. Zároveň ale úložiště posílá aktualizace o všech změnách v úložišti všem indexerům.  Tímto způsobem je zajištěna automatická indexace všeho, co se uloží do úložiště.

Indexace probíhá sekvenčně, tedy indexery jsou postupně volány pro každý vložený dokument. Tady by se sice nabízela paralelizace pro zrychlení výkonu, ale nakonec jsem se rozhodl, že nechám paralelizaci na programátorovi. Dokumenty lze vkládat a měnit paralelně a tím docílit paralelní indexace. Jediné místo, kde dochází k serializaci je na úrovni LevelDB

V programu zpravidla držíme celou naši databázi pohromadě, měla by vznikat naráz a zanikat naráz. Přidávání indexů za běhu v zásadě není možné, musel by tam být zámek a to zvyšuje komplexitu celého řešení. Doporučuji tedy pro instanci „celé databáze“ použít strukturu

struct MojeDatabaze {
     Storage dokumenty;
     Indexer1 index1,
     Indexer2 index2,
     MyView view,
     Aggregator aggreg1;

     MojeDatabaze(docdb::PDatabase db)
         :dokumenty(db, "dokument")
         ,index1(dokumenty,"index1")
         ,index2(dokumenty,"index2")
         ,view(dokumeny, "pohled1")
         ,aggreg1(view, "aggreg1") {}
}

MojeDatabaze mojeDatabaze(db);
mojeDatabaze.dokumenty.put(doc);
for (const auto &row: mojeDatabaze.index1.select(key)) {
   //....
}

Jistě si teď někdo všiml, že v tomto příkladě nejsou žádné šablony, ani formát dokumentu, ani informace o tom co se indexuje. To protože použité typy nejsou přímo typy pocházející z DocDB. Ta pravá magie začíná až s použitím klíčového slova using

using Storage = docdb::Storage<MujDokumentDef>;
using Indexer1 = docdb::Indexer<Storage, Indexer1Function, docdb::IndexType::unique, docdb::RowDocument>;
....

Schéma databáze je defacto definováno pomocí vyjadřovacích prostředků jazyka C++. Překladač pak může sestavit kód na míru schématu naší databáze a optimalizovat kód k maximálnímu výkonu.

Typy kolekcí.

Aby článek nebyl dlouhý, představím ještě typy kolekcí, a podrobně si je rozebereme a příště. Nějaké typy už byly představené nepřímo ve schématu, takže si je popišme všechny včetně hlavních vlastností

Storage

Tahle kolekce představuje úložiště. V názvosloví relačních databází by se jednalo o tabulku. Storage však není organizováno po řádcích a sloupcích. Do úložiště ukládáme dokumenty. Ale pokud dokumentem je řádka s pevným formátem, pak to může připomínat tabulku. Dokumenty však mohou být rozvětvenější, strukturovanější.  Na rozdíl od relačních databází, zde může mít každý dokument jiný význam. Není problém míchat zákazníky, košíky, zboží a kategorie v jednom úložišti. Postačí, když každý dokument bude mít nějakou identifikaci typu na stejném místě ve své binární reprezentaci. Indexery pak mohou být napsané tak, aby dokumenty třídily do skupin, například indexer který indexuje zákazníky podle zákaznického ID prostě zpracovává jen zákazníky a jiné typy dokumentů ignoruje

Důležité je, že změny v úložišti lze provádět po celých dokumentech. Změna jednoho bajtu v dokumentu vyžaduje vložit upravený dokument celý.

Cokoliv je zapsáno do úložiště, to je svázáno s unikátím ID: Označuje se DocID. Toto ID začíná na čísle 1 a s každou aktualizací roste nahoru. I změna existujícího dokumentu (jeho nahrazení novou verzí) sváže zápis s novým ID. Tedy pozor, přidělené ID nelze chápat jako automatické číslo v relační databázi. Tam totiž mohu řádku změnit a ponechat si stejné ID. V tomto případě DocID spíš představuje revizi zápisu. Pokud chci evidovat dokumenty podle nějakého ID musím si ho přidat do dokumentu a generovat si ho vlastní kódem.

Úložiště funguje jako „insert only“ databáze. Zapsané dokumenty nelze měnit, ale lze zapsat nový dokument s tím, že se zároveň zapisuje i DocID dokumentu, který je přepsán. Starý dokument pak zmizí z indexu a je nahrazen novým dokumentem. Staré revize zůstávají v úložišti (takže je možné sledovat historii změn), ale je také možné (ručně) provést operaci „compact“ a staré revize smazat.

Indexery

Indexery jsou definované pomocí indexační funkce. Tu specifikuje programátor a její náplní je převést dokument na množinu dvojic klíč=hodnota. Funkce přitom může generovat libovolně velkou množinu těchto dvojic, a může samozřejmě generovat i prázdnou množinu. Pokud množina obsahuje více dvojic, pak klíčové části dvojic musí být unikátní v rámci této množiny. V indexu pak dokument hledáme pod každým generovaným klíčem a kromě přiřazené hodnoty získáme i DocID dokumentu, který dvojici generoval. Pokud funkce pro určitý dokument negeneruje žádnou dvojici, pak tento dokument nebude v tom konkrétním indexu přítomen. Toho lze využít pro roztřídění dokumentů podle typu.

Klíč je typu docdb::Key. Detaily o této třídě rozeberu v dalším článku. Prozatím postačí vědět, že tento typ umožňuje vytvářet vícesloupcové klíče, přičemž každý sloupec může být typu string, unsigned int, double nebo bool (a nějaké další okrajové typy). Klíče jsou  řazeny alphanumericky vzestupně (čísla jsou řazeny tak jak jdou čísla po sobě).

Typem hodnoty je opět dokument, tedy typ, ke kterému existuje DocumentDef definice. Samozřejmě, že to nemusí být stejný typ jako máme v úložišti, pro hodnoty v indexech si můžeme definovat jiný typ dokumentu. Většinou si ale vystačíme s RowDocument, typicky pro uložení čísel, IDček a podobně. 

Nutnou podmínkou pro indexační funkci je, že musí být deterministická. Její výsledek musí záviset pouze na dokumentu, který indexuje. Programátor nemá nástroje na to ovlivnit, ve kterém konkrétním případě se tato funkce volá. Typicky se volá při vložení dokumentu, ale i při přepsání nebo smazání dokumentu – kdy se volá i pro dokument, který byl smazán nebo nahrazen. Je potřeba, aby tato funkce generovala determinicky stejnou množinu klíčů pro všechny situace.

Indexy se dají použít pro hledání dokumentů, protože k nalezenému klíči je přiřazen zdrojový DocID a ten lze získat jako výsledek hledání. Index lze použít také jako materializovaný pohled, kdy využejem hodnoty ( value) k uložení dalších hodnot, například části původního dokumentu, nebo i spočítané hednoty.  Tyto hodnoty lze následně získat přímo z pohledu bez nutnosti načítat data z úložiště.  Další využití hodnoty v indexu může být přidání relevance výsledku například pro následné řazení. Využití indexu jako materializovaného pohledu může být výhodné zejména pro časově kritické hledání. Index může být sestaven na míru danému hledání, a typicky postačí jeden lookup do takového indexu na místě, kde by třeba v relační databázi bylo potřeba kombinovat několik indexů.

Indexy se dále dělí na dvě varianty

• Unique - kdy dokumenty nesmí generovat kolizní klíče. Při případné kolizi pak dochází vyhození výjimky a zpravidla k přerušení aktuální transakce vkládání dokumentu. 
• Multi - dokumenty mohou generovat kolizní klíče (kolizní s klíčemi jiných dokumentů). Toto je na úrovni LevelDB realizováno tak, že DocID dokumentu je součástí klíče jako poslední položka klíče. Hledání pak lze provést prefixem klíče, takže jsou takto nalezeny všechny dokumenty, které mají stejný klíč.

Následuje příklad deklarace indexeru. Vytváří se dva indexy, primární index obsahuje pouze ID zákazníka. Další index indexuje víc položek ze zákazníka jako jméno, společnost, město, telefon atd… Jedná se jen o demonstrační příklad, jak uložit do klíče položku enum IndexedField spolu s hodnotou. Při hledání v tomto indexu pak musíme nejprve specifikovat, jakou položku hledáme a pak hodnotu hledané položky. Bylo by samozřejmě možné to řešit i tak, že pro každou položku vytvořímé nový index (pokud máme volné keyspaces, pak takové řešení dokonce generuje o trochu menší objem indexovaných dat). V těchto indexech se nepoužívá přidružená hodnota, pro hodnoty se používá StringDocument a obsah je vždy prázdný

enum class IndexedField {
    name, company, city, country, phone, email, subsdate, website
};

struct PrimaryIndexFn {
    static constexpr int revision = 1;
    template<typename Emit>
    void operator()(Emit emit, const Customer &row) const {
        emit(row.id,{});
    }
};

struct OtherIndexFn {
    static constexpr int revision = 1;
    template<typename Emit>
    void operator()(Emit emit, const Customer &row) const {
        emit({IndexedField::name, row.fname, row.lname},{});
        emit({IndexedField::company, row.company},{});
        emit({IndexedField::city, row.city},{});
        emit({IndexedField::phone, row.phone1},{});
        emit({IndexedField::phone, row.phone2},{});
        emit({IndexedField::email, row.email},{});
        emit({IndexedField::subsdate, row.subsdate},{});
        emit({IndexedField::website, row.website},{});
    }
};

using Storage = docdb::Storage<CustomerDocument>;
using PrimaryIndex = docdb::Indexer<Storage,PrimaryIndexFn, docdb::IndexType::unique,docdb::StringDocument>;
using OtherIndex = docdb::Indexer<Storage, OtherIndexFn, docdb::IndexType::multi, docdb::StringDocument>;

Souhrny dat (agregace)

Knihovna DocDB nabízí několik nástrojů pro agregaci dat v indexech. Při agregaci se vždy využívá struktura klíče a dále pak přítomnost hodnoty pro každý klíč, tedy jde o použití indexu jako materializovaného pohledu. Například pokud budeme zaznamenávat žáky na škole a jejich prospěch jako číslo známky od 1 do 5, pak klíč bude identifikovat žáka, předmět a třeba úlohu za kterou je hodnocen, hodnotou bude přímo jeho známka.  Agregovat můžeme známky do průměrné známky. Můžeme agregovat přes žáky a pro každého žáka spočítat průměrnou známku. Můžeme ale agregovat přes žáky a předměty, nebo, pokud žák může mít za některé úlohy více známek, můžeme agregovat i přes všechny tři sloupce klíče a získat průměrnou známku za každou úlohu.

Klíč                Hodnota
---------------------------
Žák,Předmět,Úloha   Známka

Možné agregace
Žák                 Průměr
Žák,Předmět         Průměr
Žák,Předmět,Úloha   Průměr

V tomto uspořádání nelze provést agregaci přes úlohy, nebo přes úlohy v předmětech. To by vyžadovalo nový index s jinou strukturou klíče

Na straně hodnot ale můžeme generovat i víc než jednu hodnotu, například počet známek, průměr, nejhorší, nelepší známku, atd. Agregační funkce je samozřejmě třída, která může poskytovat naprosto libovolnou agregaci nad vybranou skupinou dat.

Z hlediska implementace máme několik způsobů, jak provádět agregaci

• Ad-hoc agregace - Agregace je prováděna nad výsledkem (reprezentovaný jako RecordSet). Data se agregují tak jak se načítají řádky z recordsetu a agregují se přes uživatelem dodanou funkci (může být i lambda funkce). Tenhle způsob je nejjednodušší, protože v zásadě zahrnuje dodání agregační funkce ve formě lambda funkce. Pouze v tomto případě může mít agregační funkce i closure, není zde podmínka na deterministické chování funkce. Nevýhodou ad-hod agregace je ta, že se musí provádět opakovaně, protože výsledek se nikam neukládá (pokud si to sám programátor nezařídí jinak). Tento typ agregace implementuje třída  Aggregator≺Keys≻::RecordSet
• Materializované agregace - Jedná se o objekty, které ukládájí výsledky agregací jako index. Zároveň je schopen sledovat změny v datech a provádět agregaci pouze nad změněnými klíči. Práce s takovým objektem je stejná jako práce s materializovaným pohledem. Navíc i tento „index“ může být zdrojem pro další materializované agregace, nebo lze jej procházed s Ad-hoc agregací. Nevýhodou takových agregací je, že programátor musí agregaci aktualizovat. I když to znamená, že agregační objekt provede agregaci pouze změněných dat. Existuje také možnost zapnout automatickou agregaci, která však alokuje vlákno, agregace probíhá na pozadí a může existovat nebezpečí prodlevy mezi změnou v datech a propisem agregovaných výsledků do indexu. Další nevýhodou je, že agregační funkce musí být deterministická a nesmí mít closure. Tuto funkci implementuje  Aggregator≺Keys≻::Materialized
• Incrementalní materializované agregace - Je určitým kompromisem mezi prvním a druhým nástrojem. Jde o materializovaný pohled, který obsahuje agregované výsledky. Agregace probíhá současně s indexací, není zde žádná prodleva nebo potřeba agregaci aktualizovat. Pro některé způsoby použití je dokonce nejrychlejší. Avšak nelze ji použít pro všechny typy agregací. Nejčastěji se hodí pro součty nebo počty a průměry, nehodí se pro maximum a minimum, nebo jen ve speciálních případech. Pracuje tak, že agregační funkce vyzvedne z dokumentu hodnotu, kterou chce agregovat s existující hodnotou. Například pokud jde o součet, pak agregační funkce vezme hodnotu z dokumentu a zároveň vezme aktuální hodnotu pro daný klíč v indexu a obě hodnoty sečte, přičemž výsledek se uloží zpět indexu pod stejný klíč. Pokud je dokument odebrán, musí agregační funkce hodnotu zase odečíst stejným způsobem. To je důvod, proč se tento způsob nehodí pro maxima a minima. Pouze v případě, že by se dokumenty nedaly měnit a mazat, pak by bylo možné použít i tyto typy agregací. Například generování OHLC grafu z provedených obchodů na burzách. Inkrementální agregace se dále hodí například na evidenci score z odehraných her, nebo na evidenci zůstatku na účtu podle provedených transakcí. Tento typ agregace implementuje  IncrementalAggregator≺T≻
• Slučování hodnot při množinových operací -V knihovně existuje nástroj na provádění množinových operací nad výsledky z indexů. Například můžeme hledat ve vícero indexech a potřebujeme průnik obou hledání. Při těchto operacích můžeme definovat funkci, která hodnoty nějak sloučí. Zde jde o jinou variantu ad-hoc agregace. 

Vyhledávání dat

Hledání v indexu

Data lze vyhledávat pouze v indexech. V indexech lze hledat dotazem na konkrétní klíč. V takovém případě je výsledkem buď nalezená hodnota (a případně DocID), nebo odpověď, že klíč nebyl nalezen. V neunikátních indexech (s duplicitními klíči) je nutné ke klíči dodat i konkrétní DocID a pak je získána hodnota pro danou kombinaci klíč a docid, pokud existuje.

Častěji ale hledáme záznamy pro určitý rozsah klíčů.  Přitom asi nejčastěji se hledají všechny výskyty jednoho klíče v indexu s duplicitními kliči, pak získáme všechny dokumenty, které patří pod daný klíč. Případně lze hledat i prefix. To je podobné jako u agregací. Můžeme tedy v indexu obsahující třísloupcové klíče hledat podle prvních dvou klíčů a získáme všechny dokumenty které mají první dva sloupce shodné s hledaným klíčem.

Vyhledávání zajišťují metody definované v rozhraní indexeru.

auto rc1 = <index>.select(key);
auto rc2 = <index>.select_between(key1, key2);
auto rc3 = <index>.select_from(key, docdb::Direction::forward);

Výsledkem hledání je vždy RecordSet. Ten lze použít jako stream výsledků. Definuje iterátor ( InputIterator), takže lze snadno použít range-for procházení nalezených výsledků

for (const auto &result: index.select(key)) {
auto key = result.key;
        auto value = result.value;
        auto docid = result.id;
        ....
}

Použití iterátoru je pohodlné ale je potřeba mít stále na paměti, že jde o stream výsledků. Iterátor není implementován jako ukazatel na výsledek. Používá se zde LevelDB iterátor, ve kterém se data načítají přímo z LDB souborů. Je však možné nechat čtení restartovat pomocí metody rewind() (pokud je k dispozici objekt recordsetu)

Pokud je třeba výsledek agregovat, pak recordset předáme třídě Aggregator spolu s agregační funkcí. Agregované výsledky lze též procházet pomocí for.

Hledání ve vícero indexech

Často se stane, že vyhledávací požadavek zasahuje více indexů. Pak lze postupovat tak, že se vybere jeden index, který sestaví seznam kandidátů a tyto kandidáty se následně filtrují podle dalších podmínek. Přitom se snažíme vybrat index s nejmenší mohutností. Logiku výběru vhodného indexu si musí programátor naprogramovat sám, stejně tak filtraci nalezených dokumentů. Knihovna nabízí pouze funkci odhadu mohutnosti indexu.

Druhým způsobem je nechat vyhledat kandidáty pomocí vícero indexů. Například v projeku NOSTR relay může klient dost široce specifikovat filtry, podle kterých chce hledat uložené dokumenty. Je to přitom implementováno tak, že na každý filtr existuje index. Knihovna pak nabízí třídu RecordsetCalculator. Tato třída implementuje zásobníkovou kalkulačku pro výpočet množinových operací jako je průnik, sjednocení, doplněk atd… 

//(index1 OR index2) AND NOT index3

RecordsetCalculator<RowDocument> calc;
calc.push(index1.select(key1));
    .push(index2.select(key2));
    .OR();
    .push(index3.select(key3));
    .NOT();
    .AND()
    .list(storage, [&](DocID id, const Row &value, const FoundRecord<Doc> &doc) {
        print_result(id,value,doc);
     });

Při práci s hodnotami můžeme definovat agregační funkci jako parametr operací OR and AND. ( OR(aggrfn))

Hledání dokumentů v úložišti

Výsledkem hledání v indexech je vždycky pouze DocID. K získání dokumentu musíme do úložiště (storage). Objekt Storage nabízí funkci find(DocID).

auto fndres = storage.find(docid);
if (fndres) {
    DocID previous_id = fndres->previous_id;
    const auto &document = fndres->document;
}

Funkce find() nevrací přímo dokument, ale objekt, který se chová jako chytrý ukazatel. Je potřeba nejprve zjistit, zda má hodnotu, tím ověříme, že dokument existuje. Pokud existuje, pak přes ukazatel můžeme získat nejen dokument ale i ID dokumentu, který byl nahrazen. Tímto způsobem můžeme procházet historii změn pozpátku do historie.

Kromě hledání podle konkrétního ID můžeme dále úložiště procházet a to pomocí metod select_all() nebo select_from. Výsledkem je opět RecordSet, v tomto případě ale obsahuje položky previous_id, document a  id

for (const auto &row: storage.select_all()) {
    auto id = row.id;
    auto prev_id = row.previous_id;
    const RowDocument &doc = row.document;
    ...
}

Konzistence dat v dynamickém prostředí

Při použití DocDB na serverech bývá požadavek na konzistenci zapsaných dat v dynamicky se měnícím prostředí. Typicky programátor potřebuje garantovat atomické zápisy a také atomické čtení. DocDB k tomu poskytuje dva nástroje (které využívají stejné funkce v LevelDB). Batche a Snapshoty

Batch

Batch umožňuje provést atomický zápis vícero záznamů. DocDB používá batch při zápisu dokumentu a všech indexů, které s dokumentem souvisí. Neměla by tedy nastat situace při které by byl v databázi viděn vložený dokument ovšem ještě bez vytvořených indexů. 

Batche lze použít i při zápisu vícero dokumentů společně. Rozhraní pro zápis dokumentu umožňuje dodat vlastní objekt v podobě docdb::Batch. Ten pak musíme nechat ručně commitnout pomocí db->commit_batch(batch) a tím je zápis dokončen. I když se batch chová jako transakce, tak jsou zde odlišnosti. Na rozdíl od transakce, všechny zápisy pomocí batche nejsou nikde viditelné, nevidí je ani ten, kdo zápisy provádí. Při používání batchů je také třeba zajistit, aby dokumenty nevytvářely kolizní duplicitní klíče, jinak zápis končí výjimkou. Některé kolekce totiž během zápisu mají výhradní zámek na zapisované klíče a při vícenásobném požadavku na stejný klíč se většinou detekuje deadlock a tím se zápis zmaří právě vyhozením výjimky.

docdb::Batch b;
storage.put(b,doc1);
storage.put(b,doc2);
db->commit_batch(b);

Batche v DocDB nabízí další funkce. Každý batch má přiděleno unikátní sériové číslo. Každý batch také může mít zaregistrovaný observer, který je zavolán při událostech before_commit, after_commit a  after_rollback

Snapshot

Snapshot umožňuje atomicky zmrazit aktuální stav databáze. Využívá se samozřejmě implementace snapshotů v LevelDB. Každý druh kolekce, tedy storage, indexer, agregator, má i „view“ variantu ( StorageView, IndexView …), což jsou instance, které poskytují read-only přístup ke kolekcím. Těch lze vytvořit víc a každá může být svázána s jiným snapshotem. Pro atomické vytvoření snapshotu přes několik kolekcí je definovaná funkce  docdb::make_snapshot

auto [index1_view, storage_view] = docdb::make_snapshot(index1,storage);

Tímto způsobem obdržíme snapshot výše uvedených kolekcí v proměnných index1_view a storage_view. Tyto objekty umožňují vykonávat dotazy nad zmraženým stavem databáze přes stejné rozhraní, jako původní kolekce. Ve vícevláknových aplikacích je vytváření snapshotů nad indexy víceméně nutnost. 

Závěr

Mým původním záměrem bylo představit DocDB víc technicky, ale nakonec byl příspěvek mnohem delší než jsem byl ochoten připustit. Rozhodl jsem se tedy představit jen základní vlastnosti databáze a její organizaci – přitom popis je pořád hodně povrchní. Detaily bych se tedy zabýval až dalšími články.

Odkazy

• [1] https://github.com/ondra-novak/docdb - Odkaz na Github

• [2] https://github.com/go­ogle/leveldb - Level DB

• [3] https://nostr.com/ - NOSTR protocol

• [4] https://en.cppreferen­ce.com/w/cpp/language/con­straints - C++ Concepts