úvod
"Musíš běžet tak rychle, jak můžeš, jen abys zůstal na místě."
a abyste se někam dostali, musíte běžet alespoň dvakrát rychleji!“
(c) Alenka v říši divů
Před časem jsem byl požádán, abych měl přednášku analytici naší společnosti na téma navrhování datových modelů, protože při dlouhém sezení na projektech (někdy i více let) ztrácíme přehled o tom, co se kolem nás ve světě IT technologií děje. V naší společnosti (tak se to stává) mnoho projektů nepoužívá NoSQL databáze (alespoň prozatím), proto jsem se jim ve své přednášce samostatně věnoval na příkladu HBase a snažil jsem se prezentaci materiálu orientovat na ty kteří je nikdy nepoužili, fungovali. Zejména jsem ilustroval některé funkce návrhu datového modelu na příkladu, který jsem četl před několika lety . Při analýze příkladů jsem porovnal několik možností řešení stejného problému, abych divákům lépe předal hlavní myšlenky.
Nedávno jsem si „z ničeho nic“ položil otázku (obzvláště tomu nahrává dlouhý květnový víkend v karanténě), jak moc budou teoretické výpočty odpovídat praxi? Vlastně takhle se zrodil nápad na tento článek. Vývojář, který s NoSQL pracuje několik dní, se z něj nemusí dozvědět nic nového (a proto může rovnou přeskočit polovinu článku). Ale pro analyticiPro ty, kteří ještě s NoSQL úzce nespolupracovali, si myslím, že to bude užitečné pro získání základního porozumění funkcím návrhu datových modelů pro HBase.
Příklad analýzy
Dle mého názoru, než začnete používat databáze NoSQL, je třeba se dobře zamyslet a zvážit pro a proti. Problém lze s největší pravděpodobností vyřešit pomocí tradičních relačních DBMS. Proto je lepší NoSQL bez závažných důvodů nepoužívat. Pokud jste se přesto rozhodli použít NoSQL databázi, měli byste vzít v úvahu, že přístupy k návrhu jsou zde poněkud odlišné. Zejména některé z nich mohou být neobvyklé pro ty, kteří se dříve zabývali pouze relačními DBMS (podle mého pozorování). V „relačním“ světě tedy obvykle začínáme modelováním problémové domény a teprve poté, je-li to nutné, model denormalizujeme. V NoSQL jsme by měl okamžitě zohlednit očekávané scénáře práce s daty a zpočátku data denormalizovat. Kromě toho existuje řada dalších rozdílů, o kterých bude řeč níže.
Podívejme se na následující „syntetický“ problém, se kterým budeme dále pracovat:
Je potřeba navrhnout strukturu úložiště pro seznam přátel uživatelů nějaké abstraktní sociální sítě. Pro zjednodušení budeme předpokládat, že všechna naše spojení jsou vedena (jako na Instagramu, nikoli na Linkedinu). Struktura by vám měla umožnit efektivně:
- Odpovězte na otázku, zda uživatel A čte uživatele B (vzor čtení)
- Povolit přidávání/odebírání připojení v případě přihlášení/odhlášení uživatele A od uživatele B (šablona změny dat)
Samozřejmě existuje mnoho možností, jak problém vyřešit. V běžné relační databázi bychom s největší pravděpodobností jednoduše vytvořili tabulku vztahů (případně typizovanou, pokud například potřebujeme uložit uživatelskou skupinu: rodina, práce atd., do které patří tento „přítel“) a optimalizovat rychlost přístupu by přidala indexy/rozdělení na oddíly. S největší pravděpodobností bude finálový stůl vypadat nějak takto:
user_id
přítel_id
Vasya
Péťa
Vasya
Оля
dále pro přehlednost a lepší porozumění uvedu jména místo ID
V případě HBase víme, že:
- je možné efektivní vyhledávání, které nevede k úplnému prohledání tabulky výhradně na klíč
- ve skutečnosti je to důvod, proč psát SQL dotazy, které mnoho takových databází znají, je špatný nápad; technicky samozřejmě můžete poslat SQL dotaz s Joins a další logikou do HBase ze stejné Impala, ale jak efektivní to bude...
Proto jsme nuceni použít ID uživatele jako klíč. A moje první myšlenka na téma „kde a jak ukládat ID přátel?“ možná nápad uložit je do sloupců. Tato nejviditelnější a „naivní“ možnost bude vypadat nějak takto (říkejme tomu Možnost 1 (výchozí)pro další reference):
RowKey
Sloupce
Vasya
1: Péťa
2: Olya
3: Dáša
Péťa
1: Máša
2: Vasya
Zde každý řádek odpovídá jednomu uživateli sítě. Sloupce mají názvy: 1, 2, ... - podle počtu přátel a ve sloupcích jsou uložena ID přátel. Je důležité si uvědomit, že každý řádek bude mít jiný počet sloupců. V příkladu na obrázku výše má jeden řádek tři sloupce (1, 2 a 3) a druhý má pouze dva (1 a 2) - zde jsme sami použili dvě vlastnosti HBase, které relační databáze nemají:
- možnost dynamicky měnit složení sloupců (přidat přítele -> přidat sloupec, odebrat přítele -> smazat sloupec)
- různé řádky mohou mít různé složení sloupců
Pojďme zkontrolovat, zda naše struktura vyhovuje požadavkům úkolu:
- Čtení dat: abychom pochopili, zda je Vasya přihlášena k odběru Olya, budeme muset odečíst celou řadu pomocí klíče RowKey = „Vasya“ a třídit hodnoty sloupců, dokud v nich „nepotkáme“ Olyu. Nebo iterujte hodnoty všech sloupců, „nesplňujte“ Olyu a vraťte odpověď False;
- Úprava dat: přidání přítele: pro podobnou úlohu musíme také odečíst celou řadu pomocí klíče RowKey = „Vasya“ k výpočtu celkového počtu jeho přátel. Tento celkový počet přátel potřebujeme k určení čísla sloupce, do kterého si musíme zapsat ID nového přítele.
- Změna údajů: smazání přítele:
- Je třeba odečíst celou řadu pomocí klíče RowKey = „Vasya“ a protřiďte sloupce, abyste našli ten, ve kterém je zaznamenán přítel, který má být odstraněn;
- Dále, po smazání přítele, musíme všechna data „posunout“ do jednoho sloupce, abychom v jejich číslování nezískali „mezery“.
Pojďme nyní zhodnotit, jak produktivní budou tyto algoritmy, které budeme muset implementovat na straně „podmíněné aplikace“, pomocí . Označme velikost naší hypotetické sociální sítě jako n. Maximální počet přátel, které může mít jeden uživatel, je (n-1). Toto (-1) můžeme pro naše účely dále zanedbat, protože v rámci použití O-symbolů je to nedůležité.
- Čtení dat: je nutné odečíst celý řádek a iterovat všechny jeho sloupce v limitu. To znamená, že horní odhad nákladů bude přibližně XNUMX(n)
- Úprava dat: přidání přítele: Chcete-li určit počet přátel, musíte iterovat všechny sloupce řádku a poté vložit nový sloupec => O(n)
- Změna údajů: smazání přítele:
- Podobně jako při přidávání - musíte projít všechny sloupce v limitu => O(n)
- Po odstranění sloupců je musíme „přesunout“. Pokud to zavedete „čelem“, pak v limitu budete potřebovat až (n-1) operací. Zde a dále v praktické části však použijeme jiný přístup, který bude implementovat „pseudoposun“ pro pevně stanovený počet operací – to znamená, že na něj bude trávit konstantní čas bez ohledu na n. Tento konstantní čas (přesně O(2)) lze ve srovnání s O(n) zanedbat. Postup je znázorněn na obrázku níže: jednoduše zkopírujeme data z „posledního“ sloupce do sloupce, ze kterého chceme data odstranit, a poté vymažeme poslední sloupec:
Celkově jsme ve všech scénářích obdrželi asymptotickou výpočetní složitost O(n).
Pravděpodobně jste si již všimli, že téměř vždy musíme z databáze přečíst celý řádek a ve dvou případech ze tří jen projít všechny sloupce a vypočítat celkový počet přátel. Proto můžete jako pokus o optimalizaci přidat sloupec „count“, ve kterém je uložen celkový počet přátel každého uživatele sítě. V tomto případě nemůžeme pro výpočet celkového počtu přátel číst celý řádek, ale číst pouze jeden sloupec „počet“. Hlavní věcí je nezapomenout aktualizovat „počet“ při manipulaci s daty. Že. zlepšujeme se Možnost 2 (počet):
RowKey
Sloupce
Vasya
1: Péťa
2: Olya
3: Dáša
počet: 3
Péťa
1: Máša
2: Vasya
počet: 2
V porovnání s první možností:
- Čtení dat: získat odpověď na otázku „Čte Vasya Olyu? nic se nezměnilo => O(n)
- Úprava dat: přidání přítele: Zjednodušili jsme vkládání nového přítele, protože nyní nemusíme číst celý řádek a iterovat jeho sloupce, ale můžeme získat pouze hodnotu sloupce „count“ atd. okamžitě určit číslo sloupce pro vložení nového přítele. To vede ke snížení výpočetní složitosti na O(1)
- Změna údajů: smazání přítele: Při mazání přítele můžeme tento sloupec využít i ke snížení počtu I/O operací při „posunutí“ dat o buňku doleva. Stále však zůstává potřeba procházet sloupce a najít ten, který je třeba odstranit, takže => O(n)
- Na druhou stranu nyní při aktualizaci dat potřebujeme pokaždé aktualizovat sloupec „count“, ale to trvá konstantní čas, což lze v rámci O-symbolů zanedbat.
Obecně se možnost 2 zdá být trochu optimálnější, ale je to spíše jako „evoluce místo revoluce“. K provedení „revoluce“ budeme potřebovat Možnost 3 (sloupec).
Obraťme vše „naruby“: domluvíme se název sloupce ID uživatele! Co se bude psát v samotném sloupci už pro nás není důležité, nechť je to číslo 1 (obecně se tam dají uložit užitečné věci, např. skupina “rodina/přátelé/atd.”). Tento přístup může překvapit nepřipraveného „laika“, který nemá žádné předchozí zkušenosti s NoSQL databázemi, ale je to právě tento přístup, který umožňuje využít potenciál HBase v tomto úkolu mnohem efektivněji:
RowKey
Sloupce
Vasya
Péťa: 1
Olya: 1
Dáša: 1
Péťa
Máša: 1
Vasya: 1
Zde získáváme několik výhod najednou. Abychom jim porozuměli, pojďme analyzovat novou strukturu a odhadnout výpočetní složitost:
- Čtení dat: k zodpovězení otázky, zda je Vasya předplatitelem Olya, stačí přečíst jeden sloupec „Olya“: pokud je tam, pak je odpověď Pravda, pokud ne – False => O(1)
- Úprava dat: přidání přítele: Přidání přítele: stačí přidat nový sloupec „ID přítele“ => O(1)
- Změna údajů: smazání přítele: stačí odstranit sloupec ID přítele => O(1)
Jak vidíte, významnou výhodou tohoto modelu úložiště je to, že ve všech scénářích, které potřebujeme, pracujeme pouze s jedním sloupcem, čímž se vyhneme čtení celého řádku z databáze a navíc výčtu všech sloupců tohoto řádku. Mohli bychom se tam zastavit, ale...
Můžete být zmateni a jít o něco dále cestou optimalizace výkonu a omezení I/O operací při přístupu k databázi. Co kdybychom uložili kompletní informace o vztahu přímo do samotného klíče řádku? To znamená, že klíč bude složený jako userID.friendID? V tomto případě dokonce nemusíme vůbec číst sloupce řádku (Možnost 4 (řádek)):
RowKey
Sloupce
Vasya.Petya
Péťa: 1
Vasya.Olya
Olya: 1
Vasya.Dasha
Dáša: 1
Péťa.Masha
Máša: 1
Péťa.Vasya
Vasya: 1
Je zřejmé, že posouzení všech scénářů manipulace s daty v takové struktuře, jako v předchozí verzi, bude O(1). Rozdíl oproti možnosti 3 bude pouze v efektivitě I/O operací v databázi.
No, poslední "poklona". Je snadné vidět, že u možnosti 4 bude mít klíč řádku proměnnou délku, což může mít vliv na výkon (zde si pamatujeme, že HBase ukládá data jako sadu bajtů a řádky v tabulkách jsou seřazeny podle klíče). Navíc máme oddělovač, který může být v některých scénářích potřeba zpracovat. Chcete-li tento vliv eliminovat, můžete použít hashe z userID a friendID, a protože oba hashe budou mít konstantní délku, můžete je jednoduše zřetězit bez oddělovače. Potom budou data v tabulce vypadat takto (Možnost 5 (hash)):
RowKey
Sloupce
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Péťa: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olya: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dáša: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Máša: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasya: 1
Je zřejmé, že algoritmická složitost práce s takovou strukturou ve scénářích, které zvažujeme, bude stejná jako u možnosti 4 – tedy O(1).
Celkem shrňme všechny naše odhady výpočetní složitosti do jedné tabulky:
Přidání přítele
Kontrola přítele
Odebrání přítele
Možnost 1 (výchozí)
O (n)
O (n)
O (n)
Možnost 2 (počet)
O (1)
O (n)
O (n)
Možnost 3 (sloupec)
O (1)
O (1)
O (1)
Možnost 4 (řádek)
O (1)
O (1)
O (1)
Možnost 5 (hash)
O (1)
O (1)
O (1)
Jak vidíte, možnosti 3-5 se zdají být nejvýhodnější a teoreticky zajišťují provádění všech nezbytných scénářů manipulace s daty v konstantním čase. V podmínkách našeho úkolu není explicitní požadavek na získání seznamu všech přátel uživatele, ale v reálných aktivitách projektu by bylo dobré, abychom jako dobří analytici „předvídali“, že takový úkol může nastat a "roztáhni brčko." Mé sympatie jsou proto na straně varianty 3. Je ale dost pravděpodobné, že v reálném projektu by tento požadavek již mohl být vyřešen jinými prostředky, proto bez obecné vize celého problému je lepší nedělat konečné závěry.
Příprava experimentu
Rád bych si výše uvedené teoretické argumenty vyzkoušel v praxi – to byl cíl myšlenky, která vznikla o prodlouženém víkendu. K tomu je nutné vyhodnotit provozní rychlost naší „podmíněné aplikace“ ve všech popsaných scénářích používání databáze a také nárůst této doby s rostoucí velikostí sociální sítě (n). Cílovým parametrem, který nás zajímá a který budeme během experimentu měřit, je čas, který „podmíněná aplikace“ stráví provedením jedné „obchodní operace“. „Obchodní transakcí“ rozumíme jednu z následujících:
- Přidávání jednoho nového přítele
- Kontrola, zda je uživatel A přítelem uživatele B
- Odebrání jednoho přítele
S přihlédnutím k požadavkům nastíněným v původním prohlášení tedy scénář ověření vypadá následovně:
- Záznam dat. Náhodně vygenerujte počáteční síť velikosti n. Abychom se přiblížili „skutečnému světu“, počet přátel každého uživatele je také náhodná proměnná. Změřte dobu, po kterou naše „podmíněná aplikace“ zapisuje všechna vygenerovaná data do HBase. Výsledný čas pak vydělte celkovým počtem přidaných přátel – takto získáme průměrný čas na jednu „obchodní operaci“
- Čtení dat. Pro každého uživatele vytvořte seznam „osobností“, pro které musíte získat odpověď, zda je uživatel přihlášen k odběru nebo ne. Délka seznamu = přibližně počet přátel uživatele a pro polovinu zaškrtnutých přátel by měla být odpověď „Ano“ a pro druhou polovinu – „Ne“. Kontrola probíhá v takovém pořadí, aby se střídaly odpovědi „Ano“ a „Ne“ (to znamená, že v každém druhém případě budeme muset projít všechny sloupce řádku pro možnosti 1 a 2). Celkový čas promítání se pak vydělí počtem testovaných přátel, aby se získal průměrný čas promítání na subjekt.
- Mazání dat. Odebrat všechny přátele od uživatele. Pořadí mazání je navíc náhodné (to znamená, že původní seznam použitý k záznamu dat „zamícháme“). Celkový čas kontroly se pak vydělí počtem odebraných přátel, aby se získal průměrný čas na kontrolu.
Scénáře je třeba spustit pro každou z 5 možností datového modelu a pro různé velikosti sociální sítě, abyste viděli, jak se čas mění, jak roste. V rámci jednoho n musí být připojení v síti a seznam uživatelů ke kontrole samozřejmě stejný pro všech 5 možností.
Pro lepší pochopení je níže uveden příklad generovaných dat pro n= 5. Zapsaný „generátor“ vytváří jako výstup tři ID slovníky:
- první je pro vložení
- druhá je pro kontrolu
- třetí – ke smazání
{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # всего 15 друзей
{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # всего 18 проверяемых субъектов
{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # всего 15 друзей
Jak vidíte, všechna ID větší než 10 000 ve slovníku pro kontrolu jsou přesně ta, která jistě dají odpověď False. Vkládání, kontrola a mazání „přátel“ se provádí přesně v pořadí uvedeném ve slovníku.
Experiment byl proveden na notebooku se systémem Windows 10, kde v jednom kontejneru Docker běžel HBase a ve druhém Python s Jupyter Notebookem. Dockeru byla přidělena 2 CPU jádra a 2 GB RAM. Veškerá logika, jako je emulace „podmíněné aplikace“ a „potrubí“ pro generování testovacích dat a měření času, byla napsána v Pythonu. Knihovna byla použita pro práci s HBase , pro výpočet hashů (MD5) pro možnost 5 - hashlib
S ohledem na výpočetní výkon konkrétního notebooku byl experimentálně vybrán start pro n = 10, 30, …. 170 – kdy celková provozní doba celého testovacího cyklu (všechny scénáře pro všechny možnosti pro všechna n) byla ještě víceméně přiměřená a vešla se na jeden čajový dýchánek (v průměru 15 minut).
Zde je nutné poznamenat, že v tomto experimentu primárně nehodnotíme absolutní výkonová čísla. Ani relativní srovnání různých dvou možností nemusí být zcela správné. Nyní nás zajímá povaha změny v čase v závislosti na n, protože s přihlédnutím k výše uvedené konfiguraci „testovací stolice“ je velmi obtížné získat časové odhady „očištěné“ od vlivu náhodných a dalších faktorů ( a takový úkol nebyl stanoven).
Výsledek experimentu
První test je, jak se mění čas strávený vyplňováním seznamu přátel. Výsledek je v grafu níže.
Možnosti 3-5 podle očekávání vykazují téměř konstantní dobu „obchodní transakce“, která nezávisí na růstu velikosti sítě a nerozeznatelném rozdílu ve výkonu.
Možnost 2 také vykazuje konstantní, ale mírně horší výkon, téměř přesně 2krát ve srovnání s možnostmi 3-5. A to se nemůže jinak než radovat, protože to koreluje s teorií - v této verzi je počet I/O operací do/z HBase přesně 2x větší. To může sloužit jako nepřímý důkaz toho, že naše zkušební stolice v zásadě poskytuje dobrou přesnost.
Možnost 1 se také, jak se očekávalo, ukazuje jako nejpomalejší a ukazuje lineární nárůst času stráveného vzájemným přidáváním k velikosti sítě.
Pojďme se nyní podívat na výsledky druhého testu.
Možnosti 3-5 se opět chovají podle očekávání – konstantní čas, nezávislý na velikosti sítě. Možnosti 1 a 2 ukazují lineární nárůst času s rostoucí velikostí sítě a podobným výkonem. Navíc se ukazuje, že možnost 2 je o něco pomalejší – zřejmě kvůli nutnosti provést korekturu a zpracovat dodatečný sloupec „count“, který se stává znatelnějším, jak n roste. Ale přesto se zdržím jakýchkoli závěrů, protože přesnost tohoto srovnání je poměrně nízká. Kromě toho se tyto poměry (která možnost, 1 nebo 2, je rychlejší) měnily běh od běhu (při zachování povahy závislosti a „going neck and neck“).
No, poslední graf je výsledkem testování odstranění.
Zde opět žádné překvapení. Možnosti 3-5 provádějí odstraňování v konstantním čase.
Navíc je zajímavé, že možnosti 4 a 5 na rozdíl od předchozích scénářů vykazují znatelně mírně horší výkon než možnost 3. Operace odstranění řádku je zjevně dražší než operace odstranění sloupce, což je obecně logické.
Možnosti 1 a 2 podle očekávání vykazují lineární nárůst času. Zároveň je možnost 2 trvale pomalejší než možnost 1 – kvůli dodatečné operaci I/O pro „udržování“ sloupce počtu.
Obecné závěry experimentu:
- Možnosti 3-5 demonstrují větší efektivitu, protože využívají HBase; Navíc se jejich výkon vzájemně liší o konstantu a nezávisí na velikosti sítě.
- Rozdíl mezi možnostmi 4 a 5 nebyl zaznamenán. To však neznamená, že možnost 5 by neměla být použita. Je pravděpodobné, že použitý experimentální scénář s přihlédnutím k výkonnostním charakteristikám zkušební stolice neumožnil jeho odhalení.
- Charakter nárůstu času potřebného k provedení „obchodních operací“ s daty obecně potvrdil dříve získané teoretické výpočty pro všechny varianty.
Epilog
Provedené drsné experimenty by neměly být brány jako absolutní pravda. Existuje mnoho faktorů, které nebyly zohledněny a zkreslovaly výsledky (tyto výkyvy jsou patrné zejména v grafech s malou velikostí sítě). Například rychlost šetrnosti, kterou používá happybase, objem a způsob implementace logiky, kterou jsem napsal v Pythonu (nemohu tvrdit, že kód byl napsán optimálně a efektivně využíval možnosti všech komponent), snad funkce mezipaměti HBase, aktivita na pozadí Windows 10 na mém notebooku atd. Obecně můžeme předpokládat, že všechny teoretické výpočty experimentálně prokázaly svou platnost. Tedy, nebo alespoň nebylo možné je takovým „útokem zepředu“ vyvrátit.
Na závěr doporučení pro každého, kdo právě začíná navrhovat datové modely v HBase: abstrahujte od předchozích zkušeností s prací s relačními databázemi a pamatujte na „přikázání“:
- Při návrhu vycházíme z úkolu a vzorců manipulace s daty, nikoli z doménového modelu
- Efektivní přístup (bez úplného skenování tabulky) – pouze pomocí klíče
- Denormalizace
- Různé řádky mohou obsahovat různé sloupce
- Dynamická skladba reproduktorů
Zdroj: www.habr.com