Systém správy datových toků - Data stream management system

A systém pro správu datových toků (DSMS) je počítačový softwarový systém pro nepřetržitou správu datové toky. Je to podobné jako a Systém pro správu databází (DBMS), který je však určen pro statická data v konvenčních databáze. DSMS také nabízí flexibilní zpracování dotazů, takže lze potřebné informace vyjádřit pomocí dotazů. Na rozdíl od DBMS však DSMS provede a průběžný dotaz který se provádí nejen jednou, ale je trvale nainstalován. Dotaz je proto průběžně prováděn, dokud není výslovně odinstalován. Protože většina systémů DSMS je řízena daty, kontinuální dotaz vytváří nové výsledky, pokud do systému dorazí nová data. Tento základní koncept je podobný Složité zpracování událostí takže se obě technologie částečně spojují.

Funkční princip

Jedním z důležitých rysů systému DSMS je možnost zpracovávat potenciálně nekonečné a rychle se měnící datové toky tím, že nabízí flexibilní zpracování současně, i když existují pouze omezené zdroje, jako je hlavní paměť. Následující tabulka poskytuje různé principy DSMS a porovnává je s tradičními DBMS.

Systém správy databáze (DBMS)Systém správy datových toků (DSMS)
Trvalá data (relace)těkavé datové toky
Náhodný přístupSekvenční přístup
Jednorázové dotazyKontinuální dotazy
(teoreticky) neomezené sekundární úložištěomezená hlavní paměť
Relevantní je pouze aktuální stavZohlednění pořadí vstupu
relativně nízká rychlost aktualizacepotenciálně extrémně vysoká rychlost aktualizace
Malé nebo žádné časové požadavkyPožadavky v reálném čase
Předpokládá přesné údajePředpokládá zastaralá / nepřesná data
Plánovatelné zpracování dotazůVariabilní příjezd dat a charakteristiky dat

Zpracování a streamování modelů

Jednou z největších výzev pro DSMS je zpracovávat potenciálně nekonečné datové toky pomocí pevného množství paměti a bez náhodného přístupu k datům. Existují různé přístupy k omezení množství dat v jednom průchodu, které lze rozdělit do dvou tříd. Na jedné straně existují kompresní techniky, které se snaží shrnout data, a na druhé straně existují okenní techniky, které se pokoušejí rozdělit data na (konečné) části.

Synopse

Myšlenkou kompresních technik je udržovat pouze přehled dat, ale ne všechny (surové) datové body datového proudu. Algoritmy se pohybují od výběru náhodných datových bodů zvaných vzorkování až po sumarizaci pomocí histogramů, vlnek nebo skicování. Jedním jednoduchým příkladem komprese je nepřetržitý výpočet průměru. Místo zapamatování každého datového bodu obsahuje souhrn pouze součet a počet položek. Průměr lze vypočítat vydělením součtu číslem. Je však třeba zmínit, že přehledy nemohou přesně odrážet data. Zpracování založené na přehledech tedy může produkovat nepřesné výsledky.

Okna

Namísto použití přehledů ke kompresi charakteristik celých datových proudů se okenní techniky dívají pouze na část dat. Tento přístup je motivován myšlenkou, že jsou relevantní pouze nejnovější údaje. Okno proto nepřetržitě vyřízne část datového proudu, např. posledních deset prvků datového proudu a tyto prvky bere v úvahu pouze během zpracování. Existují různé druhy takových oken, jako jsou posuvná okna, která jsou podobná FIFO seznamy nebo omílání oken, které vyřezávají nesouvislé části. Kromě toho lze okna také rozlišit na okna založená na prvcích, např. K posouzení posledních deseti prvků, nebo časově založená okna, např. K posouzení posledních deseti sekund dat. Existují také různé přístupy k implementaci oken. Existují například přístupy, které používají časová razítka nebo časové intervaly pro okna celého systému nebo okna založená na vyrovnávací paměti pro každý jednotlivý krok zpracování. Zpracování dotazu na posuvné okno je také vhodné k implementaci v paralelních procesorech využíváním paralelismu mezi různými okny a / nebo v rámci každého rozsahu okna.[1]

Zpracování dotazů

Protože existuje spousta prototypů, neexistuje standardizovaná architektura. Většina DSMS je však založena na dotaz zpracování v DBMS pomocí deklarativních jazyků k vyjádření dotazů, které jsou přeloženy do plánu operátorů. Tyto plány lze optimalizovat a provádět. Zpracování dotazu často sestává z následujících kroků.

Formulace průběžných dotazů

Formulace dotazů se většinou provádí pomocí deklarativních jazyků jako SQL v DBMS. Vzhledem k tomu, že neexistují žádné standardizované dotazovací jazyky, které by vyjadřovaly souvislé dotazy, existuje mnoho jazyků a variací. Většina z nich však vychází z SQL, tak jako Kontinuální dotazovací jazyk (CQL), StreamSQL a ESP. Existují také grafické přístupy, kde každý krok zpracování je rámeček a tok zpracování je vyjádřen šipkami mezi rámečky.

Jazyk silně závisí na modelu zpracování. Pokud se například ke zpracování používají okna, musí být vyjádřena definice okna. v StreamSQL, dotaz s posuvným oknem pro posledních 10 prvků vypadá takto:

VYBRAT AVG(cena) Z examplestream [VELIKOST 10 ZÁLOHA 1 TUPLE] KDE hodnota > 100.0

Tento proud nepřetržitě vypočítává průměrnou hodnotu „ceny“ posledních 10 n-tic, ale bere v úvahu pouze ty n-tice, jejichž ceny jsou vyšší než 100,0.

V dalším kroku je deklarativní dotaz přeložen do plánu logického dotazu. Plán dotazu je směrovaný graf, kde uzly jsou operátory a hrany popisují tok zpracování. Každý operátor v plánu dotazů zapouzdřuje sémantiku konkrétní operace, jako je filtrování nebo agregace. V DSMS, které zpracovávají relační datové toky, jsou operátoři stejní nebo podobní operátorům Relační algebra, takže existují operátory pro operace výběru, projekce, spojení a nastavení. Tento koncept operátora umožňuje velmi flexibilní a všestranné zpracování DSMS.

Optimalizace dotazů

Plán logických dotazů lze optimalizovat, což silně závisí na modelu streamování. Základní koncepty pro optimalizaci nepřetržitých dotazů jsou stejné jako koncepty z databázové systémy. Pokud existují relační datové toky a plán logického dotazu je založen na relačních operátorech z Relační algebra, může optimalizátor dotazů použít algebraické ekvivalence k optimalizaci plánu. Může se jednat například o posunutí operátorů výběru dolů ke zdrojům, protože nejsou tak výpočetně náročné jako operátory spojení.

Kromě toho existují také optimalizační techniky založené na nákladech, jako v DBMS, kde je plán dotazů s nejnižšími náklady vybrán z různých ekvivalentních plánů dotazů. Jedním příkladem je volba pořadí dvou po sobě jdoucích operátorů spojení. V DBMS se toto rozhodnutí většinou provádí pomocí určitých statistik příslušných databází. Jelikož však data datových toků nejsou předem známa, neexistují v DSMS žádné takové statistiky. Je však možné po určitou dobu sledovat datový proud, abychom získali určité statistiky. Pomocí těchto statistik lze dotaz také později optimalizovat. Na rozdíl od DBMS tedy některé DSMS umožňují optimalizovat dotaz i za běhu. Proto DSMS potřebuje některé strategie migrace plánu, aby nahradil spuštěný plán dotazů novým.

Transformace dotazů

Protože logický operátor je zodpovědný pouze za sémantiku operace, ale nesestává z žádných algoritmů, musí být plán logického dotazu transformován na spustitelný protějšek. Tomu se říká plán fyzických dotazů. Rozdíl mezi logickým a fyzickým plánem operátora umožňuje více než jednu implementaci pro stejného logického operátora. Například spojení je logicky stejné, i když ho lze implementovat různými algoritmy jako a Vnořené připojení smyčky nebo a Třídit-sloučit spojení. Všimněte si, že tyto algoritmy také silně závisí na použitém proudu a modelu zpracování. Všimněte si, že dotaz je k dispozici jako plán fyzických dotazů.

Provádění dotazů

Vzhledem k tomu, že plán fyzických dotazů se skládá ze spustitelných algoritmů, lze jej provést přímo. Za tímto účelem je plán fyzických dotazů nainstalován do systému. Spodní část grafu (plánu dotazů) je připojena k příchozím zdrojům, což mohou být vše jako konektory k senzorům. Horní část grafu je připojena k odchozím propadům, což může být například vizualizace. Vzhledem k tomu, že většina systémů DSMS je řízena daty, je dotaz spuštěn odesláním příchozích datových prvků ze zdroje přes plán dotazu do jímky. Pokaždé, když datový prvek předá operátor, provede operátor svou specifickou operaci s datovým prvkem a předá výsledek všem následným operátorům.

Příklady

Viz také

Reference

  1. ^ De Matteis, Tiziano; Mencagli, Gabriele (25. března 2016). „Parallel Patterns for Window-Based Stateful Operators on Data Streams: Algorithmic Skeleton Approach“. International Journal of Parallel Programming. 45 (2): 382–401. doi:10.1007 / s10766-016-0413-x. S2CID  255600.
  2. ^ Abadi; et al. Aurora: Systém pro správu datových toků. SIGMOD 2003. CiteSeerX  10.1.1.67.8671.
  3. ^ Jianjun Chen; David J. DeWitt; Feng Tian; Yuan Wang (2000). „NiagaraCQ: Škálovatelný systém nepřetržitých dotazů pro internetové databáze“ (PDF). Oddělení počítačových věd. University of Wisconsin – Madison. SIGMOD. Citováno 21. listopadu 2018.
  4. ^ Arasu, A., et. al. STREAM: Stanfordský systém pro správu datových proudů. Technická zpráva. 2004, Stanford InfoLab.
  5. ^ Chandrasekaran, S. a kol., „TelegraphCQ: Kontinuální zpracování toku dat pro nejistý svět.“ CIDR 2003.
  • Aggarwal, Charu C. (2007). Datové toky: modely a algoritmy. New York: Springer. ISBN  978-0-387-47534-9.
  • Golab, Lukasz; Özsu, M. Tamer (2010). Správa datového proudu. Waterloo, USA: Morgan a Claypool. ISBN  978-1-608-45272-9.

externí odkazy