Dotazování nad proudy datNDBI001 10.12.2013, Bc. Jan Drozen

O čem bude řeč

Úvod

Motivace

Dotazování

Algoritmy

Shrnutí

Úvod

Systém řízení proudu dat

DBMS > DSMS

DSMS je nadmnožina DBMS

Dají se simulovat pomocí procedurálních

prostředků v DBMS

Rozdíly DBMS oproti DSMS

DBMS

Data trvale uložená

Možnost náhodného

přístupu

Jednorázové dotazy

Velká sekundární

paměť (TB)

DSMS

Proudy jsou dočasné

Pouze sekvenční

zpracování

Dlouhotrvající dotazy

Omezená primární

paměť (GB)

Rozdíly DBMS oproti DSMS - pokračování

DBMS

Data v přesně

definovaném známém

stavu

Relativně statická povaha

Menší nároky na rychlost

Očekáváme přesné

deterministické výsledky

DSMS

Data závislá na pořadí na

vstupu

Velmi velmi častý zápis

Rychlost velmi důležitá

Mohou (musí) stačit pouze

aproximované výsledky

Motivace

Příklady

Tradebot – webový finanční vyhledávač, vyhodnocuje

dotazy vůči aktuálním datům

Dnes už neaktivní

iPolicyNetworks – uplatňování různých pravidel ve velkých

sítích

Také nedostupné

Synchronizace distribuovaných systémů – Yahoo

Monitorování senzorů

Sledování síťového provozu - příklad

Podrobnější motivační příklad

Mějme poskytovatele připojení k Internetu (ISP)

Disponuje rozsáhlou páteřní sítí

Požadavek na trasování paketů a monitorování

provozu

Sledování síťového provozu – pokr.

Řešení

Specializovaný systém pouze pro danou úlohu

Vlastní řešení

Logování a zpětné offline vyhodnocování

Sledování síťového provozu – pokr.

Model sítě:

Linka C propojuje páteřní síť ISP se sítí

koncového zákazníka

Linka B propojuje dva routery uvnitř páteřní

sítě ISP

B a C označíme proudy trasovacích dat

odpovídající provozu na těchto linkách

Sledování síťového provozu – pokr.

Trasovací data obsahují hlavičku formátu:

zdroj– IP adresa odesilatele

cil– IP adresa příjemce

id – identifikační číslo generované odesilatelem, aby

příjemce mohl jednoznačně identifikovat paket

delka – délka daného paketu

cas – informace o tom, kdy byl daný paket

zaznamenán

Sledování síťového provozu – pokr.

Chceme umět formulovat dotaz Q1 takový, že:

Spočítá vytížení linky B průměrovaný po

minutových intervalech

Pokud vytížení překročí určitou míru t, tak

informuje operátora

Sledování síťového provozu – pokr.

Q1:

SELECT upozorniOperatora(SUM(delka))FROM BGROUP BY minuta(cas)HAVING SUM(delka) > t

Možno simulovat pomocí triggerů

Pokud by byl provoz velký (např. optická linka), mohlo

by dojít k problémům

Sledování síťového provozu – pokr.

Chceme umět formulovat dotaz takový, že:

Filtruje provoz pouze v páteřní síti

Rozdělí provoz na jednotlivé proudy

Určí intenzitu provozu v každém proudu

Proud definujeme jako sekvence paketů mezi

určitým zdrojem a cílem

Sledování síťového provozu – pokr.

Q2:

SELECT idProudu, zdroj, cil, SUM(delka) AS delkaProuduFROM (SELECT zdroj, cil, delka, cas

FROM BORDER BY cas)

GROUP BYzdroj, cil, ziskejIdProudu(zdroj, cil, cas) ASidProudu

ziskejIdProudu vrací identifikátor proudu na základě zdroje, cíle a

času

GROUP BY a ORDER BY klauzule

Sledování síťového provozu – pokr.

Chceme umět formulovat dotaz takový, že:

Zjistíme, jakou část provozu páteřní linky

můžeme přiřadit síti zákazníka

Sledování síťového provozu – pokr.

Q4:

SELECT(SELECT COUNT(*)FROM C,BWHERE C.zdroj = B.zdroj AND C.cil = B.cil AND

C.id = B.id)/(SELECT COUNT(*)FROM B)

Operace spojení

Nad proudy dat nemusí stačit paměť

Sledování síťového provozu – pokr.

Chceme umět (naposledy) formulovat dotaz

takový, že:

Bude monitorovat páry zdroj – cíl

V páteřní síti

Pouze pro 5 procent s nejvyšším vytížením

Sledování síťového provozu – pokr.

Q4:

WITH vytizeni AS (SELECT zdroj, cil, SUM(delka) AS provozFROM BGROUP BY zdroj, cil)SELECT zdroj, cil, provozFROM vytizeni AS L1WHERE ( SELECT COUNT(*)

FROM vytizeni AS L2WHERE L2.provoz < L1.provoz) > (SELECT 0.95 * COUNT(*)

FROM vytizeni))

ORDER BY provoz

Dotazování

Problémy při dotazování

Prvky proudu dat přicházejí online

Systém nemá kontrolu nad pořadím, v jakém data

přicházejí

Potenciálně neomezená velikost

Jakmile je prvek proudu dat zpracován, je

archivován nebo zahozen

Pokud chceme jinak, musíme to explicitně

vyjádřit

Typy dotazů

V klasickém DBMS spustíme dotaz a ten po

vykonání vrací výsledky, které zpracujeme

To lze v DSMS samozřejmě také

Jednorázové dotazy (one-time queries)

Zahrnují i zmiňované DBMS dotazy

Rozlišujeme, protože existují i jiné dotazy

Dlouhotrvající dotazy (continuous queries)

Přidaná hodnota DSMS

Dělení dotazů

Podle zpracování

Jednorázové

Dlouhotrvající

Podle pokládání

Předdefinované

Známé před začátkem proudu

Jednoúčelové (ad-hoc)

Vytvořené v průběhu

Problémy s pamětí

Proudy dat jsou potenciálně neomezené -> proto i dotazy

pro zpracování mohou požadovat neomezeně velkou

paměť

DBMS pracují s externí (sekundární) pamětí –

optimalizované algoritmy

Pro DSMS nemusí být použitelné

Nejsou navržené na dlouhotrvající dotazy

Pro vyhodnocování v reálném čase velká latence

DSMS typicky pro takové aplikace

Problémy s rychlostí

V DBMS dotazování nad známými daty

V DSMS při vykonávání dotazu přicházejí nová

data

Rychlost zpracování musí být dostatečně vysoká

Jinak velká latence

Hrozí, že budou data zahozena ještě před

zpracováním

Dále se omezíme pouze na práci s primární

pamětí

Řešení problémů - aproximace

Pokud upustíme od požadavku na exaktní

odpověď, můžeme se zbavit problémů

Ale omezíme si i výrazovou sílu dotazovacího

jazyka

Dotazy vykonávány v omezeně velké paměti

Odpovědi aproximované

Kvalitní aproximace může pro většinu aplikací

bez problémů dostačovat

Aproximace - pokračování

Různé techniky pro aproximace:

Sketch

Náhodné vzorkování

Histogramy

Vlnky (wavelets)

Předmětem výzkumu

Klouzavá okna

Základní myšlenka aproximovaných odpovědí

Nebudeme se dotazovat nad kompletními daty

(celá historie proudu), ale pouze nad nějakým

aktuálním úsekem

Např. data za poslední hodinu, týden,...

Řada výhod:

Dobře definovaná

Jednoduchá sémantika

Klouzavá okna - pokračování

Deterministická

Upřednostňují aktuální data

Typické pro reálné nasazení

Použitelné nejen pro aproximaci, ale i explicitně

pro sémantiku

Právě omezení na určitý časový úsek

Klouzavá okna - pokračování

Ale i zde přetrvávají problémy:

Co když se ani okno nevejde do paměti?

Náročná implementace

Rozšíření SQL a relační algebry o práci s okny

Předmětem výzkumu

Dávkové zpracování, vzorkování,

synopse

(batch processing, sampling, synopses)

Další techniky pro aproximativní dotazování

Budeme uvažovat datovou strukturu, do které můžeme zapisovat (inkrementálně se zvětšuje)

Potřebujeme operace:

update(n-tice)

Aktualizuje strukturu, když přijdou nová data

computeAnswer()

Vrátí nové nebo aktualizované výsledky dotazu

Operace

Jaká je rychlost update a computeAnswer ?

Pokud je jedna z nich pomalejší (obě), než je

průměrná doba mezi příchozími daty, nastává

problém

Zpracování „neudrží krok“ s proudem

Není možné vrátit přesnou odpověď (relativně k

uvažované podmnožině proudu)

Dávkové zpracování

Update je rychlá, computeAnswer pomalá

Přirozeným řešením je zpracovávat data v

dávkách

Data jsou ukládána do mezipaměti (buffering)

Odpovědi jsou spočteny jednou za určitou dobu

Aproximativní v tom ohledu, že odpovědi nejsou v

reálném čase

Vzorkování

Update pomalá, computeAnswer rychlá

Není možné pro výpočet odpovědi použít

všechna potřebná data – přicházejí rychleji,

než jsou zpracovávána

Některé příchozí n-tice jsou přeskočeny

Pouze omezená kvalita výsledků

Pro některé aplikace nevyhovující

Synopse

Chceme update i computeAnswer rychlé

Aproximativní datová struktura

Synopse nebo sketch (skica)

Typicky malá

Menší než přesná reprezentace

Opět předmětem výzkumů

Blokující operace

Blokující operátor je pro dotaz takový operátor,

který potřebuje pro svůj výpočet znát všechna

data, dříve než vydá jakýkoli výstup.

Např. třídění, COUNT, SUM, MIN, MAX, AVG,...

Záleží na pozici ve stromě dotazu

List

Pro DSMS nepoužitelné

Vnitřní uzel

V DSMS možné

Blokující operace - pokračování

Jako kořen může vracet průběžné výsledky dalším operátorům

Pokud je odpovědí jedna hodnota nebo je dostatečně malá - odpovídá jako proud dat – pokud se agregovaná hodnota změní, vrátí ji jako další prvek proudu

Pokud je odpověď delší, je vhodné udržovat datovou strukturu s „aktuálním stavem odpovědi“

Blokující operátory - řešení

Namísto blokujících operátorů jako vnitřních uzlů

použít neblokující alternativy, které fungují

stejně (ale aproximativně)

Např. JUGGLE operátor

Neblokující verze třídění

Přerovnává lokálně data

Negarantuje správný výsledek

Blokující operace – řešení pokračování

Punctuation

Rozhodnutí, že s některými daty se již nebude

pracovat a mohou být poslána na výstup

Např. den >= 10

„všechny další atributy den budou mít

hodnotu alespoň 10“

Data s menší hodnotou mohou být

zpracována a odeslána

Dotazování na starší data

Data nejsou persistentně ukládána

Problém pro jednoúčelové dotazy – některá data

již mohla být zahozena – nemožné odpovědět na

dotaz přesně

Omezení dotazů pouze do budoucnosti

Omezující, ale v praxi použitelné

Možné udržovat agregované informace o proudu

ve specializované struktuře

Zdroj dalších problémů

DSMS Stanford STREAM

Stanford StREam DatA Manager

Prototyp implementace DSMS

Dotazovacím jazykem je rozšíření SQL

Umožňuje FROM klauzulí referencovat relace i

proudy dat

Podpora dotazů nad klouzavými okny

STREAM – klouzavá okna

STREAM – klouzavá okna - pokračování

Časovou známkou může být čas (nečekaně), ale i identifikátor

pořadí

Požadavkem je totálně uspořádaná doména s metrikou

Rozšíření SQL o volitelnou specifikaci okna ve FROM klauzuli

Pomocí hranatých závorek

1. Klauzule rozdělující proud do skupin – okno pro každou skupinu

2. Velikost okna

Ve „fyzických“ jednotkách – např. počet prvků okna

V „logických“ jednotkách – např. počet dní

3. predikát pro filtrování

STREAM – klouzavá okna - pokračování

Fyzická okna

klíčové slovo ROWS (ROWS 50 PRECEDING)

Logická okna

klíčové slovo RANGE (RANGE 15 MINUTESPRECEDING)

STREAM - příklady

Pro následující příklady uvažujme schéma:

záznamy o telefonních hovorech

atributy: id_zakaznika, typ, minut, cas

atribut cas je časovou známkou určující

pořadí

STREAM – příklad I

Chceme spočítat průměrnou délku hovoru,

uvažujíc pouze 10 posledních meziměstských

hovorů pro každého zákazníka

SELECT AVG(S.minut)FROM hovory AS S [PARTITION BY

S.id_zakaznikaROWS 10 PRECEDINGWHERE S.typ = ‘Mezimesto‘]

STREAM – příklad II

Chceme spočítat průměrnou délku hovoru,

uvažujíc pouze meziměstské z deseti posledních

hovorů pro každého zákazníka

SELECT AVG(S.minut)FROM hovory AS S [PARTITION BY

S.id_zakaznikaROWS 10 PRECEDING]

WHERES.typ = ‘Mezimesto‘

STREAM – příklad III

Chceme zjistit průměrnou délku posledních 1000

hovorů, které uskutečnili zákazníci z kategorie

„Gold“

SELECT AVG(V.minut)FROM (SELECT S.minut

FROM hovory AS S, zakaznici AS TWHERE S.id_zakaznika =

T.id_zakaznikaAND T.kategorie = ‘Gold‘)

AS V [ROWS 1000 PRECEDING]

Časové známky

Jsou velmi důležité

V předchozích příkladech jsme používali implcitní

Co se stane, když jsou n-tice původem z různých proudů?

Např. použití operátorů spojení – jakou známku má

dostat výsledek?

Explicitní známky mají jiný problém

Data nemusejí přijít v pořadí podle známek (např.

vlivem stavu sítě)

Časové známky - pokračování

Problém s explicitními známkami prakticky

znemožňuje použití s klouzavými okny

Pokud je proud „téměř“ setříděný, menší

odchylky lze jednoduše řešit pomocí mezipamětí

Časové známky - přidělování

Binární operátory vytvářejí nové prvky – je potřeba jim

určit známky.

Neřešit pořadí

Pštrosí taktika

Předpoklad, že dříve příchozí prvky operátor také dříve

opustí

Implicitní

Pořadí určí uživatel explicitně

Pořadí odpovídající pořadí proudů ve FROM klauzuli

Může vzniknout více prvků se stejnou známkou

Časové známky – příklad

SELECT *FROM S1 [ROWS 1000 PRECEDING],

S2 [ROWS 100 PRECEDING]WHERE S1.A = S2.B

Výstupní n-tice budou setřídění podle známek S1. Uspořádání vůči S2 je ztraceno

Potenciálně nutnost udržovat data v mezipaměti

Pro zajištění správného pořadí

Může se stát, že přijdou další data v S2, která se spojí s daty v S1, která mají menší známky a patří do současného okna

Časové známky - problém

Tento problém se může propagovat stromem dotazu

Použití 1. nebo 2. způsobu přidělování závisí na konkrétní aplikaci

1. způsob pro zvýšení výkonu – použití oken pro aproximaci

2. způsob pro explicitní sémantiku oken

Časové známky – rozlišení přidělování

STREAM umožňuje v dotazu určit způsob přidělování známek

Definuje klíčová slova:

PRECEDING

odpovídá 2. způsobu

RECENT

nové klíčové slovo

odpovídá 1. způsobu

DSMS si může sám určit pořadí n-tic

možno použít pouze s fyzickou specifikací velikosti

okna

STREAM – vykonání dotazu

Exekuční plán (podobně jako v DBMS)

Skládá se z prvků:

Operátory

Fronty (spojují operátory)

Synopse (používají je operátory jako pomocné

datové struktury)

Existují i implementace se sdílenou frontou pro

všechny operátory (Aurora, Eddies)

STREAM – vykonání dotazu – pokrač.

Operátory plánuje centrální plánovač

Během vykonávání dotazu operátor čte data z fronty, aktualizuje synopsi, která mu náleží a zapíše výsledek do výstupní fronty

Operátor pracuje po dobu, kterou mu určí plánovač

Po vypršení této doby předá řízení zpět plánovači

STREAM – vykonání dotazu – pokrač.

Protože uvažujeme i dlouhotrvající dotazy, je

potřeba zohlednit měnící se stav systému

Např. počet konkurentních proudů, množství

dotazů, dostupná paměť

Operátory musí být adaptivní

Algoritmy

Algoritmy

Metriky srovnání algoritmů

Náhodné vzorkování

Předpokládá se použití v systému, kdy malý

vzorek dat zachycuje jejich charakteristiku

V závislosti na požadovaných vlastnostech se

používají různé algoritmy pro vzorkování (např

stratified sampling)

Sketch

Vytváří malý vzorek proudu (v malé paměti)

Používají se hašovací funkce pro výpočty

distribuce prvků v proudu

Histogramy

Struktura používaná pro sumarizaci dat

Znázorňuje distribuci dat v množině

Dají se použít na odhad velikosti dotazu,

aproximativní odpovědi, data mining...

V-Optimální histogram

Rovnoměrný histogram

End-Biased histogram

Zdroj: Wikipedia

V-Optimální histogram

Zdroj:http://www.mathcs.emory.edu/~cheun

g/Courses/584-StreamDB/Syllabus/06-

Histograms/v-opt1.html

Rovnoměrný histogram

End-Biased histogram

Vlnky (wavelets)

Technika pro sumarizaci dat

Používá projekci hodnot na ortogonální bázový

vektor

Je možné data zpět lehce rekonstruovat

Shrnutí

Shrnutí

Viděli jsme množství vlastností a problémů, které

s sebou přináší zpracování proudů dat

Položme si na závěr otázky, které souvisejí s

motivací:

Je efektinější DSMS nebo DBMS s podporou

triggerů, dočasných objektů,...?

Je potřeba vyvíjet univerzální systém nebo je

lepší řešit každý problém speciálně?

Existují nějaké „killer apps“ pro DSMS?

Shrnutí

Pokud si odpovíme ano, znamená to řešit všechny

problémy, se kterými jsme se setkali

Časové známky, klouzavá okna, blokující

operátory,...

i nesetkali

Distribuované DSMS

Z pohledu dotazovacího jazyka

je lepší rozšířit SQL nebo použít něco úplně

jiného?

Zdroje

B. Babcock, S. Babu, M. Datar, R. Motwani, J.

Widom:

Models and Issues in Data Stream Systems,

Stanford University

Data stream management systems na Wikipedii

Prostor pro otázky?„Ptejte se mě na co chcete, já na co chci odpovím.“

Děkuji za pozornost.