COMPUTERWORLD
pod kapotou
Paralelismus a databáze

V souvislosti s dnešními změnami informačních systémů někdy říkávám cimrmanovsky - budoucnost patří paralelismu. O jaké změny jde a proč paralelismus? Známí protagonisté paralelních architektur Ö zsu a Valduriez uváděli v r. 1994, že množství počítačově zpracovávaných informací v podniku roste ročně o 30% a množství transakcí vzroste 10× v následujících pěti letech. Mění se ovšem i podoba transakcí. Zatímco v minulosti se vystačilo s jednoduchými transakcemi (běžný OLTP), systémy pro podporu rozhodování generují transakce podstatně složitější. Situaci lze popsat tak, že databázové servery by měly poskytnout vysokou průchodnost systému a dobré časy odezvy pro různé typy transakcí na velmi velkých databázích.

Efektivní provoz DBS je závislý na velikosti vnitřní paměti a disků. Tyto parametry se stále zlepšují, nicméně hlavní brzda - přístup na disk - se příliš zlepšit nedaří. Zatímco počet MIPSů rostl o 40% za rok, průchodnost se u magnetických disků zvětšila za posledních 10 let pouze 2× . Dílčími řešeními jsou např. disková pole, sdílení disků paralelních počítačů a řada dalších hardwarových architektur, samozřejmě i (geografické) rozmisťování dat (viz např. varianty distribuovaných databází).

Největším přínosem pro provoz databázového systému jsou dnes ovšem paralelní architektury. Umožňují zlepšit čtyři základní rysy sledované u každého SŘBD:

  • cena - architektura složená z levnějších základních elementů je levnější než např. střediskový počítačový systém.
  • provoz - pro dotazy v paralelním prostředí je charakteristické zpracování typu inter-query - paralelní zpracování dotazů (tj. několik dotazů je vyhodnocováno současně) a intra-query - paralelní zpracování dotazu, tj. dotaz je dokomponován na části, které jsou zpracovávány současně.
  • škálování - úměrně s rozšiřováním požadavků lze přidávat další elementy (procesory, paměti) a zvyšovat výkon. Cílem je zvýšení celkové rychlosti zpracování (speedup) a udržení výkonu při zvětšení velikosti databáze (scaleup). Např. vytvoření nějaké sestavy na databází velikosti 1 GByte zabere čas t. Zvětší-li se databáze 10× a zvětší-li se také výpočetní zdroje 10× , měl by zůstat zachován i čas t.
  • dostupnost dat - je zajištěna vícenásobnými kopiemi dat.

Hlavním cílem paralelismu je tedy zvýšení výkonu:

  • paralelní systém by měl být rychlejší než sekvenční,
  • paralelní systém by měl dát skoro lineární škálování (speedup nebo scaleup, nebo obojí).

Připomeňme, že paralelní systémy je nutno odlišovat od dalšího typu architektur - distribuovaných systémů. Zatímco v případě paralelních architektur jde o více CPU fyzicky spojených do kompaktního celku, u distribuovaných architektur jsou CPU obvykle distribuovány geograficky. Paralelní systémy představují pokus konstruovat rychlejší a také levnější centralizovaný počítač, distribuované systémy speciálně v databázích vycházejí z potřeby nabídnout lokálně autonomní systémy s možností globálního či integrovaného pohledu. V distribuovaných databázích se dotazy a další požadavky na manipulaci s daty provádějí nezávisle v různých místech a částečné výsledky na základě komunikace mezi místy přispívají k vytvoření celkového výsledku.

Použití paralelismu v databázích

Paralelní zpracování dotazů a paralelní zpracování dotazu míří do dvou sfér aplikací, které existují v rámci organizace buď samostatně nebo současně. V prvním případě jde o velké množství poměrně jednoduchých transakcí (OLTP), které je nutné zpracovávat současně. Cílem je tedy dosáhnout co největšího množství transakcí za sekundu (t/s). Příkladem takové transakce (dotazu) je "Najdi informace o zaměstnanci Novákovi". Druhý typ zpracování se týká spíše podpory rozhodování, kdy potřebujeme projít velké množství dat, provést agregace apod. Např. "Spočti, kolik je zákazníků" může být takovým dotazem. Je-li relace ZÁKAZNÍK rozložena např. na 4 disky čtyř procesorů, lze dotaz rozložit, provádět paralelně a syntetizovat výsledek. Jsou-li zákazníků 4 miliony, získá se výsledek 4× rychleji než v případě běžného zpracování s jednoprocesorovým strojem.

Důležité je, že ne každá z paralelních architektur či software pro ně vytvořeného je vhodná pro oba uvedené typy úloh.

Typy paralelních architektur

Paralelismus v souvislosti s databázemi provází již od počátku tzv. velká debata o tom, jakou podobu by měla paralelní architektura mít. Nejtypičtější dnešní paralelní architektury zahrnují "sdílení ničeho" a "sdílení všeho". V první případě (obr. 1) má každý procesor svou přímo přístupnou paměť a přímo přístupné disky. Procesory mezi sebou komunikují zasíláním zpráv. Na opačné straně spektra stojí architektura "sdílení všeho" (obr. 3), nazývaná také “sdílení paměti”, ve které všechny procesor mají přímý přístup ke společné paměti a přímý přístup ke všem diskům. Alternativou mezi oběma architekturami je "sdílení disků" (obr. 2) dovolující pouze přístup ke všem diskům při zachování privátní paměti pro každý procesor.

 

disk disk ... disk

procesor procesor procesor

paměť paměť paměť

SÍŤ

 

Obr. 1: Architektura "sdílení ničeho"

 

procesor procesor procesor

paměť paměť paměť

SÍŤ

 

 

 

 

Obr. 2: Architektura "sdílení disků"

 

 

 

procesor procesor procesor

SÍŤ

Globální paměť

 

 

 

 

Obr. 3: Architektura "sdílení všeho"

 

  • Sdílení paměti více procesory přes společnou sběrnici (symetrické multiprocesory, SMP) je řešení zdánlivě jednoduché. Dosažení vysokého výkonu je ale drahé a technologicky náročné, přestože je dost jednoduše programovatelné. Výsledný systém nelze dynamicky rozšiřovat. Typickým představitelem architektury "sdílení všeho" je multiprocesorový systém Sequent Symmetry (řada S2000 nebo řada S5000) nebo RM1000 firmy Pyramid Techn. Přes prvotní omezení (8-16 procesorů) jsou dnes dosažitelné konfigurace i s několika desítkami procesorů.
  • Při sdílení ničeho (masivně paralelní procesory, MPP) existuje ke každému procesoru část databáze na disku a všechny operace pracující s daty na tom disku je nutné vykonávat na tomto procesoru. Tato architektura je náročná na projekci databáze, tj. na řešení otázky, jaká data uložit ke kterém procesoru. Programování v takové architektuře je obtížné. Důležité také je, že každý dotaz je paralelizován. Není tedy možné převést centralizovaný SŘBD přímo do této architektury. Výhodou oproti sdílení disků je, že zprávy vyměňované mezi procesory obsahují pouze užitečná data. Z MPP hardware jmenujme SP2 Scalable Powerparallel Systém firmy IBM.
  • Sdílení disků je náročné na zajištění konsistence dat (stránky s týmiž daty jsou např. aktualizovány současně na různých procesorech). Každý výpočetní systém má jednu kopii SŘBD. Mezi uzly jsou vyměňovány stránky (nejen užitečná data), což vede k větším nárokům na komunikaci, tj. k existenci různých synchronizačních protokolů. Sdílení disků používá např. Oracle na počítači nCUBE firmy nCUBE. S 64 uzly sdílejícími 128 disků bylo dosaženo velmi rychlého transakčního systému (1000 t/s podle testů TPC-B).

V případě výpadku procesoru v architektuře "sdílení disků" se zpracování přesune na další procesory. U architektury "sdílení ničeho" se ztrácí přístup k části databáze.

Mezi paralelní architektury se dnes ještě řadí tzv. klastry. Jde o hardwarovou architekturu, ve které jsou uzly založené na SMP spojené do sítě. Uzly komunikují pomocí zpráv. Tímto způsobem lze docílit rozšiřitelnosti, která schází samotným strojům SMP. Např. pomocí dvanácti Alpha serverů firmy Digital založenými na True Cluster se 4 procesory lze složit fyzickou sestavu se 16× 4 procesory.

Přes malou rozšiřitelnost, má ovšem architektura SMP dvě zásadní výhody nad architekturou MPP:

  • Díky sdílené paměti neexistuje žádná prodleva při výměně zpráv v komunikaci, synchronizace je levná, vyžaduje mechanismy nízké úrovně, vyvážení zátěže je jednodušší, protože operační systém může pro každý připravený proces alokovat libovolný volný procesor.
  • Paralelní zpracování v MPP klade důraz na rovnoměrné zatížení zúčastněných počítačů. Jde o obtížné otázky dosud ne příliš vyřešené ani na teoretické úrovni. Paralelismus také klade nové nároky na optimalizátor dotazů.

Paralelní databázové servery

Na základě obecných idejí paralelismu se teprve vytvářejí paralelní SŘBD, či paralelní databázové servery. Známým paralelním databázovým produktem je NonStopSQL firmy Tandem. V systému NonStopSQL verzi z r. 1986 šlo o první distribuovaný SQL s vysokým výkonem - 200 t/s. V paralelních verzích z r. 1989 a 1994 je využita technologie "sdílení ničeho" pro paralelní zpracování dotazu způsobem, že se stoupajícím počtem procesorů klesá lineárně rychlost vyhodnocení dotazu. Relace jsou při tom horizontálně distribuovány mezi disky k jednotlivým procesorům. V OLTP dosahuje konfigurace se 110 uzly a 800 GByte databází 21 000 t/min. (podle testů TPC-C) .

Lineární zvýšení výkonu s počtem přidávaných procesorů dosahuje také architektura Computing Surface firmy Meiko. Jednotlivé moduly jsou procesory SPARC s operačním systémem Solaris propojené pomocí paralelní vnitřní sítě CSN (Computing Surface Network). Ta umožňuje nezávislou komunikaci každého modulu s každým. Úspěšný projekt z hlediska databází v této architektuře a současně absolutní světové prvenství představuje paralelní server Oracle (Oracle RDBMS V 6.2) z r. 1991. Přidáváním procesorů lze dosáhnout průchodnosti od 30 do 1000 a více t/s.

Je jistě zajímavé sledovat “svatou válku” o to, která architektura je lepší. Spíše je třeba říci, na co se jednotlivé varianty hodí. Obecně vzato SMP se je vhodnější pro OLTP aplikace se stabilním provozem či pomalým nárůstem provozu s daty od 10 do 100 GByte. MPP systémy se hodí pro složité analytické aplikace, kde růst provozu je nepredikovatelný, s daty i přes 200 GByte.

A jak se k paralelismu staví 4 u nás nejznámější databázové firmy? Po několik let existují databázové servery Oracle pro všechny typy paralelních architektur.

Server bývá často implementován jako multi-threaded (vícevláknový), tj. operační systém rozdělí program server na části (threads), které pošle na jednotlivé procesory. Použití této technologie je typické pro Sybase SQL Server nebo pro Informix - OnLine Dynamic Server verze 7.1. Informix využívá DSA (Dynamic Scalable Architecture) a buduje paralelismus na klastrech. Informix v r. 1995 rozšířil DSA architekturu na MPP platfomu a nabídnul OnLine Extended Parallel Server (XPS) verze 8.0

Sybase je založen na dvouúrovňové architektuře software. Tzv. navigátor (Navigation server z r. 1994) řídí pole nezávislých SQL strojů. Jeho další verze se nazývá Sybase MPP. Co se týče optimalizace zpracování dotazů v paralelním prostředí, patří dnes Sybase SQL server zřejmě ke špičce v této oblasti. Data rozdělená na jednotlivé servery v paralelní architektuře mohou vykazovat i nerovnoměrné rozložení. Pak mohou mít jednotlivé servery pro jeden požadavek různé plány vyhodnocení.

Konečně přístup IBM k MPP je reprezentován verzí DB2/6000 Parallel Edition.

Paralelismus je charakterizován poměrně jednoduchým vybudováním prostředí pro paralelní provádění výpočtu. Na druhé straně je pro něj velmi těžké napsat obecný optimalizátor dotazů tak, aby by byl automaticky generován optimální plán. Dokonce se zdá, že se již objevují složitostní hranice možností optimalizace. Připomeňme však, že tyto problémy provázejí optimalizaci i v sekvenčním případě.



<seznam dílů seriálu>   <COMPUTERWORLD>