ProHoster > Blog > podávání > Globals jsou meče pokladů pro ukládání dat. Stromy. Část 1
Globals jsou meče pokladů pro ukládání dat. Stromy. Část 1
Skutečné databázové meče - globals - jsou již dlouho známé, ale stále málokdo ví, jak je efektivně používat, nebo tuto superzbraň vůbec nevlastní.
Pokud při řešení problémů, ve kterých jsou opravdu dobří, použijete globals, můžete dosáhnout vynikajících výsledků. Buď v produktivitě nebo ve zjednodušení řešení problému (1, 2).
Globals jsou speciální způsob ukládání a zpracování dat, zcela odlišný od tabulek v SQL. Objevily se v roce 1966 v jazyce PŘÍUŠNICE) (evoluční vývoj - Cache ObjectScript, dále COS) v lékařské databázi a je tam stále aktivně využívánaa pronikl i do některých dalších oblastí, kde je vyžadována spolehlivost a vysoký výkon: finance, obchodování atd.
Globální systémy v moderních DBMS podporují transakce, protokolování, replikaci a dělení. Tito. lze je použít k budování moderních, spolehlivých, distribuovaných a rychlých systémů.
Globals vás neomezují na relační model. Poskytují vám svobodu vyvíjet datové struktury, které jsou optimalizovány pro konkrétní úkoly. Pro mnoho aplikací může být chytré využití globals skutečně tajnou zbraní, která poskytuje výkon, o kterém si vývojáři relačních aplikací mohou nechat jen zdát.
Globals jako způsob ukládání dat lze použít v mnoha moderních programovacích jazycích, jak na vysoké, tak na nízké úrovni. Proto se v tomto článku zaměřím konkrétně na globály, a ne na jazyk, ze kterého kdysi vzešly.
2. Jak fungují globalizace
Pojďme si nejprve porozumět, jak fungují globalisté a jaké jsou jejich silné stránky. Na globalizaci lze nahlížet z různých úhlů pohledu. V této části článku se na ně podíváme jako na stromy. Nebo jako hierarchické datové sklady.
Jednoduše řečeno, globální je trvalé pole. Pole, které se automaticky uloží na disk.
Těžko si představit něco jednoduššího pro ukládání dat. V kódu (v jazycích COS/M) se od běžného asociativního pole liší pouze symbolem ^ před jménem.
Pro ukládání dat v globálu se nemusíte učit dotazovací jazyk SQL, příkazy pro práci s nimi jsou velmi jednoduché. Dají se naučit za hodinu.
Začněme tím nejjednodušším příkladem. Jednopatrový strom se 2 větvemi. Příklady jsou napsány v COS.
Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"
Při vkládání informací do globálního (příkaz Set) se automaticky stanou 3 věci:
Ukládání dat na disk.
Indexování. To, co je v závorkách, je klíč (v anglické literatuře – „dolní index“) a napravo od rovná se hodnota („hodnota uzlu“).
Třídění. Údaje jsou seřazeny podle klíče. V budoucnu bude při procházení pole prvním prvkem „Sergey Smith“ a druhým „John Sidorov“. Při příjmu seznamu uživatelů z globální databáze neztrácí čas tříděním. Navíc můžete požádat o výstup seřazeného seznamu počínaje jakýmkoli klíčem, dokonce i neexistujícím (výstup začne od prvního skutečného klíče, který následuje po neexistujícím).
Všechny tyto operace probíhají neuvěřitelně rychle. Na mém domácím počítači jsem získával hodnoty až 750 000 insertů/s v jediném procesu. Na vícejádrových procesorech mohou hodnoty dosáhnout desítky milionů vložky/sec.
Samotná rychlost vkládání toho samozřejmě moc neříká. Můžete například velmi rychle zapisovat informace do textových souborů - takto říkalo se Práce na vyřizování víz. Ale v případě globalů ve výsledku získáme strukturované indexované úložiště, se kterým se dá v budoucnu snadno a rychle pracovat.
Největší předností globalů je rychlost, s jakou lze vkládat nové uzly.
Data v globálním jsou vždy indexována. Jejich procházení, jak na jedné úrovni, tak hluboko do stromu, je vždy rychlé.
Přidejme ke globálnímu ještě pár větví druhé a třetí úrovně.
Set ^a("+7926X", "city") = "Moscow"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36
Je zřejmé, že víceúrovňové stromy lze stavět na základě globálů. Navíc je přístup k jakémukoli uzlu téměř okamžitý díky automatickému indexování během vkládání. A na jakékoli úrovni stromu jsou všechny větve seřazeny podle klíče.
Jak vidíte, informace mohou být uloženy jak v klíči, tak v hodnotě. Celková délka klíče (součet délek všech indexů) může dosáhnout 511 bytůa hodnoty 3.6 MB pro Cache. Počet úrovní ve stromu (počet dimenzí) je 31.
Další zajímavý bod. Strom můžete vytvořit bez zadání hodnot uzlů vyšších úrovní.
Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3
Prázdné kruhy jsou uzly, které nemají přiřazenou žádnou hodnotu.
Abychom lépe porozuměli globálům, porovnejme je s jinými stromy: zahradními stromy a stromy názvů souborového systému.
Porovnejme stromy na globálech s nám nejznámějšími hierarchickými strukturami: s obyčejnými stromy, které rostou v zahradách a na polích, stejně jako se souborovými systémy.
Jak vidíme u zahradních stromů, listy a plody se nacházejí pouze na koncích větví.
Souborové systémy - informace jsou uloženy pouze na koncích větví, což jsou plně kvalifikované názvy souborů.
A zde je globální datová struktura.
Rozdíly:
Vnitřní uzly: informace v globálu mohou být uloženy v každém uzlu, nejen na koncích větví.
Externí uzly: Globální musí mít definované hodnoty na koncích větví, zatímco FS a zahradní stromy ne.
Z hlediska vnitřních uzlů můžeme říci, že struktura globální je nadmnožinou struktury jmenných stromů v souborových systémech a zahradních stromech. Tito. flexibilnější.
Obecně platí, že globální je uspořádaný strom s možností ukládat data v každém uzlu.
Abychom lépe porozuměli práci globálů, představme si, co by se stalo, kdyby tvůrci souborových systémů použili k ukládání informací přístup podobný globálům?
Smazání jednoho souboru v adresáři by automaticky odstranilo adresář, stejně jako všechny překrývající se adresáře obsahující pouze jeden právě odstraněný adresář.
Nebylo by potřeba adresářů. Jednoduše by existovaly soubory s podsoubory a soubory bez podsouborů. Při srovnání s obyčejným stromem by se každá větev stala plodem.
Věci jako soubory README.txt nemusí být potřeba. Vše, co bylo potřeba říci o obsahu adresáře, bylo možné zapsat do samotného adresářového souboru. V prostoru cest je název souboru k nerozeznání od názvu adresáře, takže bylo možné vystačit pouze se soubory.
Rychlost mazání adresářů s vnořenými podadresáři a soubory by se dramaticky zvýšila. Na Habré byly mnohokrát články o tom, jak dlouhé a obtížné je smazat miliony malých souborů (1, 2). Pokud však vytvoříte pseudosouborový systém na globálním, bude to trvat sekundy nebo jejich zlomky. Když jsem testoval mazání podstromů na domácím počítači, odstranilo to 1-96 milionů uzlů z dvouvrstvého stromu na HDD (ne SSD) za 341 sekundu. Navíc mluvíme o smazání části stromu a ne pouze celého souboru s globals.
Odstranění podstromů je další silnou stránkou globálů. K tomu nepotřebujete rekurzi. To se děje neuvěřitelně rychle.
V našem stromu to lze provést příkazem Zabít.
Kill ^a("+7926X")
Abychom lépe porozuměli tomu, jaké akce máme k dispozici na globální úrovni, poskytnu krátkou tabulku.
Základní příkazy a funkce pro práci s globals v COS
sada
Nastavení větví uzlu (pokud ještě není definováno) a hodnot uzlů