Základní principy databází reálného času

Základní principy databází reálného času

Článek pojednává o různorodých problémech týkajících se návrhu a implementace databázových systémů reálného času. Jsou zde uvedeny rozdíly mezi klasickými systémy reálného času a konvenčními databázovými systémy na jedné straně a RTDBS s širšími požadavky na straně druhé. Rovněž je zdůrazněna sémantika aplikací a popsáno, jak je možné ji využít pro zlepšení činnosti RTDBS. Stěžejní části článku se zabývají možnostmi plánování činnosti CPU, přístupu k datům a vstupně-výstupních operací. Kromě toho jsou zmíněny i vhodné vlastnosti paměťově rezidentních databází pro použití v prostředí reálného času.
Klíčová slova: systém reálného času, databázový systém reálného času, transakce, kritický termín, zamykání dat, konzistence dat, plánování transakcí, inverze priorit, souběžné řízení.

1. Úvod

Tradiční systémy reálného času (real-time systems) zpracovávají svá data ve strukturách zcela závislých na aplikaci. V souvislosti s neustálým rozvojem se aplikace tohoto typu rozšiřují a vyžadují efektivní přístup k většímu množství dat. Proto se stává nezbytností zpracovávat a uchovávat data i v těchto systémech v systematické a organizované podobě. Klasické databázové systémy mají nástroje a možnosti, jak zabezpečit takovou organizaci dat, a proto je v posledních letech patrný zájem sloučit databázové technologie a technologie reálného času. Výsledným integrovaným systémům, které mají schopnosti databáze a přitom respektují časová omezení a nároky kladené na systémy reálného času, se obecně říká databázové systémy reálného času (real-time database systems, RTDBS).

Stejně jako konvenční databázové systémy, i RTDBS fungují jako skladiště dat, mají efektivní algoritmy ukládání dat a dokážou vyhledávat data a manipulovat s nimi. Avšak jako části systémů reálného času, jejichž úlohy jsou spojeny s časovými požadavky, musí RTDBS navíc zajistit určitý stupeň spolehlivosti právě v případě požadavků systému na časovou odezvu.

Mezi příklady aplikací, které pracují s velkými objemy dat a mají přísné požadavky na dobu zpracování, lze uvést systémy v letectví, obranné systémy, výrobní provozy s podporou počítačového řízení, systémy vzdušného a pozemního řízení provozu a v neposlední řadě i burzovní a bankovní systémy. Konkrétním příkladem je radarový obranný systém, který detekuje „obrázky“ letadel, jež jsou potom porovnávány s databází známých obrázků. Výsledek porovnání může být využit k řízení dalších akcí, např. k rozhodnutí o strategii bojové akce. Tvrdé časové požadavky jsou zde zřejmé.

2. Porovnání s klasickými databázemi

Konvenční databázové systémy pro aplikace reálného času nejsou vhodné. Liší se od RTDBS v mnoha aspektech. Klasické databázové systémy staví na první místo logickou konzistenci dat, k zajištění které často používají uzamykání dat pro čtení nebo změnu údajů a blokují tak jiné transakce v činnosti. V takových případech je velmi složité předvídat délku zpoždění, jelikož blokování transakcí může nabývat podoby kaskády. Často je proto nemožné odhadnout dobu odezvy.

Dále je třeba zdůraznit zcela odlišné požadavky na výkonnost a kritéria přesnosti. Na rozdíl od konvenčních databázových systémů, jejichž hlavním cílem je poskytovat „průměrně“ rychlou dobu odezvy, RTDBS musí být vyhodnocovány podle toho, jak často transakce promeškávají svůj kritický termín, jaké je průměrné zpoždění transakcí nebo jaké jsou náklady způsobené transakcemi, které promeškaly kritický termín.

3. Charakteristika a požadavky databázových systémů reálného času
Nejčastěji jsou RTDBS charakterizovány dvěma parametry:

1. přístupem k datům v časovém omezení,
2. přístupem k datům, která mají dočasnou platnost.

Uvedené operace zahrnují sběr dat z operačního prostředí, jejich zpracování v kontextu informací získaných v minulosti a poskytování včasné výsledné odezvy. Dále obsahují také zpracování nejen archivních, ale i dočasných dat, která ztrácejí svou platnost po uplynutí určité doby. Na rozdíl od klasických databázových systémů jsou data v RTDBS spojena s dalšími vlastnostmi, které pramení ze skutečnosti, že použitá data v případě časově kritických aplikací musí co nejpřesněji odrážet aktuální stav zkoumaného reálného prostředí. Data jsou získávána v diskrétních intervalech, a proto jsou jen jakousi aproximací reality. S ubíhajícím časem se tato aproximace stává méně přesnou, až dosáhne bodu, kdy již hodnota neodráží skutečný stav reality. Proto se rozlišují tyto pojmy:

• Časová značka, kdy byla hodnota získána.
• Absolutní interval platnosti jako časový interval, ve kterém je aktuální hodnota dat považována za platnou. Hodnota dosahuje absolutní časové konzistence pouze tehdy, když platí t_n– t_x < a_x kde tn je aktuální čas, t_x je časová značka x a a_x je absolutní interval platnosti hodnoty x.
• Relativní interval platnosti je spojen s množinou dat Sy použitých k odvození nové hodnoty y. Taková množina hodnot Sy je relativně časově konzistentní, pokud časová diference mezi y a daty v dané množině Sy není větší než interval relativní platnosti. Například radarem se měří okamžitá rychlost pohybujícího se letadla, přičemž je známa jeho poslední zaměřená pozice. Z těchto dvou údajů lze vypočítat novou pozici. Aby však byl výsledek platný, měly by být obě hodnoty zaznamenány v intervalu jedné sekundy.

Časové nároky na odezvu systému, vynucené systémovým prostředím, potom spolu s přirozeně dočasnou platností dat určují časové požadavky na transakce. Proto korektnost databázových transakcí v reálném čase nezáleží pouze na rychlosti logických výpočtů, ale rovněž na čase, kdy jsou výsledky transakce vyřízeny.

Nejčastěji jsou časové požadavky vyjádřeny jako kritické termíny transakcí. Transakcím tohoto typu, které mají explicitně definovány časové požadavky, se říká transakce v reálném čase.

Jak již bylo zmíněno, RTDBS je možné považovat za zdokonalené databázové systémy, které podporují transakce v reálném čase. Transakce v reálném čase by měla být ukončena do svého kritického termínu, aby byl zajištěn maximální přínos transakce pro aplikaci. Takové požadavky lze však často velmi obtížně splnit. V případě, že transakce svůj kritický termín nesplní, se hovoří o tzv. zpožděné transakci. RTDBS se liší ve způsobu, kterým se obsluhují zpožděné transakce. Zpožděná transakce může mít pro systém pozitivní, nulový nebo negativní přínos a podle toho je s touto transakcí dále nakládáno.

4. Odhad časové odezvy – předvídatelnost

Velmi rozšířená je představa, že zpracování v reálném čase je ekvivalentem rychlého zpracování, což ovšem není pravda. Zatímco obvykle je rychlost zpracování odvozována z průměrné výkonnosti, v případě systémů reálného času je třeba brát v úvahu nejhorší možnou výkonnost. To znamená, že při návrhu zejména náročných systémů reálného času (hard real-time systems) je nutné počítat s nejhorším možným případem. Důležitou vlastností RTDBS tedy není ani tak rychlost, jako spíše včasnost, tzn. schopnost produkovat očekávané výsledky včas, tj. v určeném čase, a předvídatelnost, tzn. schopnost pokud možno co nejvíce deterministické činnosti pro plnění specifikací systému.

Jelikož požadavky na výkonnost mohou být rozdílné podle typu konkrétní aplikace, termín předvídatelnost by měl být chápán v tomto kontextu. Hard real-time system musí být předvídatelný v tom smyslu, že jejich uživatel je schopen vědět předem, zda budou úlohy splněny před svým kritickým termínem. Tato předvídatelnost bude možná pouze v případě, že je známa nejhorší doba vykonání úlohy a data i zdroje vyžadované úlohou. V případě RTDBS však tyto informace není možné vždy získat. Na rozdíl od klasických aplikací reálného času zde existuje několik faktorů, které ztěžují odhad časové odezvy transakcí, jenž je nezbytným předpokladem úspěšného plánování transakcí. Především, vykonání transakce je téměř vždy závislé na datech a zdrojích systému. Garantovat absolutně splnění termínu vyžaduje enormní předimenzování zdrojů. Plně transakční přístup znamená využívat mnoho databázových protokolů, jejichž časové odezvy jsou nepředvídatelné. Například protokoly souběžného řízení často používají blokování a opětovné spouštění transakcí. Požadavek zajistit tzv. vlastnosti ACID (atomic – logická skladba systému z entit, consistence – bezespornost, isolation – oddělenost, durability – trvalost) může mít za následek velké režie systému, což je nevhodné pro spolehlivý odhad odezvy systému. Databáze jsou často tak rozsáhlé, že není možné je umístit do operační paměti. Proto je při práci využíván diskový systém počítače (pevný disk), což zvyšuje náklady na systém způsobené vyhledáváním informací na disku. Posledním nepříznivým faktorem je možnost závislosti doby vykonání transakce na velikosti databáze. Jestliže je táž transakce, která je realizována, v rozsáhlé databázi, doba provedení transakce bude delší než v databázi malé.

Jelikož se RTDBS používají pro velmi specializované aplikace, jsou často využívány speciální techniky pro zlepšení odezvy systému. Například není-li databáze příliš rozsáhlá, je možné ji umístit do operační paměti a vyloučit tak vstupně-výstupní operace. V závislosti na každé konkrétní aplikaci je rovněž možné vyhnout se zajišťování některých nepotřebných vlastností ACID, což podstatně sníží režii systému. V některých systémech reálného času mohou být úlohy nebo transakce analyzovány předem. Znalost požadavků kladených na zdroje a chování transakcí za běhu aplikace může vést k efektivnějšímu plánování a souběžnému řízení.

5. Plánování transakcí

Transakcím je v systémech RT udělován přístup k procesoru na základě jejich priorit. Tyto priority mohou být navrženy na základě experimentu tak, aby zajistily optimální činnost systému. Nejčastějším druhem experimentu je měření počtu transakcí, které promeškají svůj kritický termín. Při tomto měření se implicitně předpokládá, že transakce mají stejnou prioritu.

Transakce má mnoho vlastností, které mohou její prioritu ovlivnit:

• kritičnost – čím je transakce více kritická, tím má vyšší prioritu,
• kritický termín – čím bližší je kritický termín, tím vyšší je priorita,
• množství zbývající činnosti – transakci s menším množstvím zbývající práce může být přidělena vyšší priorita,
• množství již vynaloženého výpočetního výkonu – transakci, na kterou systém již vynaložil velké množství výpočetního výkonu, může být přidělena vyšší priorita,
• stáří – transakci, která přišla dříve, bývá přidělena vyšší priorita než pozdější transakci.

Obecně je problém optimálního plánování transakcí výpočetně neřešitelný. Je proto nutné se spokojit s heuristickými postupy. Dále jsou podrobněji rozvedeny nejčastěji používané algoritmy.

5.1 EDF – Execute Deadline First
Algoritmus EDF přednostně zpracovává transakce s nejbližším kritickým termínem. Pracuje spolehlivě, jestliže systém není zahlcen transakcemi. Jeden způsob, jak řešit tento problém, je zavést do systému tzv. ovládač zahlcení. Ovládač zahlcení definuje pravidla pro odmítání přicházejících transakcí při přetížení systému velkým počtem transakcí. Bez tohoto ovládače mají téměř všechny transakce ve velmi zatíženém systému dlouhou dobu odezvy.

5.2 AED – Adaptive Earliest Deadline
Algoritmus AED kombinuje ovládač zahlcení s algoritmem EDF. Když transakce přijde, systém ji vloží do fronty nevyřízených transakcí. Jestliže je jí přiřazena pozice v intervalu 1 až H (kde H je parametr), transakce je přiřazena skupině, která se nazývá hit, zatímco zbývající jsou zařazeny do skupiny miss. Cílem je pokusit se splnit všechny kritické termíny ze skupiny hit, a pokud zbývá nějaký čas, uskutečnit transakce ze skupiny miss. Transakce ve skupině hit jsou řízeny algoritmem EDF. Transakce ve skupině miss jsou prováděny, jestliže ve skupině hit neexistují žádné nevyřízené transakce, v pořadí jejich umístění ve frontě.

Jestliže je transakce jednou přiřazena určité skupině, zůstává v této skupině stále. Jinými slovy, transakce jednou přiřazená do skupiny hit nemůže být v žádném případě přiřazena do skupiny miss a naopak. Po vykonání transakce je tato odstraněna ze souboru nevyřízených transakcí.

H je řídicí parametr pro daný systém reálného času. Jestliže se H blíží nekonečnu, systém se transformuje na EDF, jestliže H = 0, systém se transformuje na systém s náhodným výběrem transakcí. H bývá nastavováno podle následujícího algoritmu.

Tyto hodnoty jsou v systému měřeny opakovaně. Když systém spustí experiment, přiřadí prvních H transakcí skupině N_h a skupině N všechny transakce, které přijdou. Počty transakcí ve skupinách N_h a N musí být vhodně navrženy. Potom jsou obě tyto skupiny sledovány, jak splní kritické termíny. Z tohoto měření se vypočte úspěšnost a spustí se další krok, v němž systém zvýší hodnotu H o 5 %. To se opakuje, dokud není parametr S_a po měření menší než 0,95. Klesne-li S_a pod 0,95, parametr H je naopak snížen.

Obecné schéma iteračního kroku k tedy je:

1. H(k) = 1,05S_hH(k – 1),
2. jestliže je S_a < 0,95, potom H(k) = min {H(k – 1); 1,25S_a n}

   kde n je celkový počet transakcí aktuálně vykonaných v systému.

Tento algoritmus zajistí, že pokud je v systému malý počet transakcí, téměř všechny jsou umístěny v třídě hit. Je-li blíže k bodu, kde S_a je menší než 0,95 (tj. více než 5 % transakcí promeškalo svůj kritický termín), H je sníženo. Faktor 1,25 byl vybrán na základě zkušenosti. V porovnání s algoritmy EDF má algoritmus AED lepší výsledky.

Algoritmus AED implicitně předpokládá, že všechny transakce mají v systému stejnou prioritu. Neplatí-li to, je nutné brát ohled na jejich priority a je rovněž nutné tento algoritmus modifikovat roz-dělením transakcí do tříd priorit. Tyto třídy jsou definovány dynamicky na základě hodnot priorit transakcí. Jestliže X je průměrná hodnota priorit transakcí ve třídě C, třída C obsahuje transakce s prioritami v intervalu (X/S_F, XS_F), kde S_F je faktor pokrytí definovaný uživatelem. Při zpracovávání transakcí se rozsahy intervalů jednotlivých tříd mění. Jestliže třída neobsahuje žádnou transakci, je zrušena.

Když se v systému objeví transakce, je třeba zjistit, zda ji není možné umístit do nějaké existující třídy. Jestliže taková třída existuje, přidá se transakce této třídě a přepočítá se její spodní a horní mez. Pokud volná třída neexistuje, vytvoří se nová.

Transakce každé třídy jsou pomocí procedury algoritmu AED rozděleny do skupin hit a miss. Jakmile je transakce přidělena platné třídě, náhodně se vloží do souboru nevyřízených transakcí a určí se, zda spadá do skupiny miss nebo hit. Pro každou třídu je nutné počítat řídicí parametr H_i, který je analogií parametru H v algoritmu AED. Schéma priorit je takovéto:

1. Transakce ve třídě s vyšší hodnotou (přiřazená skupině hit nebo miss uvnitř této třídy) mají vždy přednost před transakcemi z třídy s nižší hodnotou.
2. Jestliže dvě transakce (A a B) spadají do skupiny hit a stejné třídy, vykoná se nejdříve ta transakce, která má nejbližší kritický termín.
3. Jestliže A náleží do skupiny hit a B do skupiny miss a obě jsou ve stejné třídě, A má prioritu před B.
4. Jestliže A i B patří do miss ve stejné třídě a hodnota priority A je větší než hodnota priority B, má A prioritu před B; jestliže obě mají stejnou hodnotu priority, má prioritu ta, která je v souboru nevyřízených transakcí na nižší pozici.

Tyto algoritmy mají jednu nevýhodu: rozdílné chování k dlouhým a krátkým transakcím. Krátké transakce, které přijdou před kritickým termínem jiných (delších) transakcí, budou realizovány dříve než tyto dlouhé transakce. Experimentálně bylo zjištěno, že dlouhé transakce výrazně zvyšují pravděpodobnost nesplnění kritického termínu (v obou algoritmech, EDF i AED).

5.3 AEVD – Adaptive Earliest Virtual Deadline
AEVD je rozšířená verze algoritmu AED. Jediný rozdíl mezi AEVD a AED je ve způsobu přiřazování priorit transakcím v třídě hit.

V algoritmu AEVD se absolutní kritický termín nahradí virtuálním kritickým termínem a priority se přiřazují v opačném pořadí.

Virtuální kritický termín je vypočítán následovně. Předpokládejme, že lze odhadnout dobu realizace příchozí transakce T, označme ji C_T. Předpokládejme, že maximální a minimální doba realizace transakcí v celém systému je C_max a C_min. Pak definujme rychlostní faktor transakce T takto:

kde a je řídicí parametr z intervalu 0 Ł a Ł 1.

Jestliže d_T je absolutní kritický termín transakce T, její virtuální kritický termín V_T v čase t je:

a je parametr, který zajišťuje zvýhodnění dlouhých transakcí. Zvýšením rychlostního faktoru transakce se zvětší její virtuální kritický termín a to sníží její prioritu. Nejdelší transakce, jejichž doba vykonání je C_max, mají rychlostní faktor roven a a nejkratší, jejichž doba uskutečnění je C_min, mají rychlostní faktor roven 1.

Systém může nastavovat hodnotu a adaptivně během práce RTDBS tak, že měří počet promeškaných transakcí v závislosti na době jejich realizace. Potom je vypočtena lineární regrese těchto dat. Jestliže je směrnice regresní přímky kladná, znamená to, že delší transakce promeškávají svůj kritický termín a a musí být sníženo. Je-li směrnice záporná, parametr a musí být zvětšen. Ideální situace nastává, je-li směrnice přímky nulová.

6. Souběžné řízení

Souběžné řízení řeší problém vzájemné interakce mezi transakcemi tak, aby nebyla porušena konzistence dat. V tradičních databázových aplikacích je důležitým požadavkem zajistit souběžné řízení transakcí tak, aby výsledný efekt souběžného běhu byl stejný jako při jejich sériovém běhu v určitém pořadí. Pojem sériové konzistence transakčního zpracování je zaveden a používán jako vhodný prostředek korektnosti klasického transakčního plánování. Je však samozřejmé, že tato podmínka rovněž přináší nutnost blokovat a opětovně spouštět transakce. Někdy bývá navrhováno, aby se v jednoprocesorovém systému transakce sekvenčně zpracovávaly a zcela se odstranilo souběžné zpracování transakcí. Smyslem je snížit režii souběžného zpracování a automaticky zajistit sériovou konzistenci. Odstranit souběžnost však není vhodné, mají-li transakce různou délku. Vyskytne-li se krátká transakce za dlouhou transakcí, její odezva v sekvenčním zpracování může být delší než v souběžném.

V RTDBS u souběžného řízení převažují protokoly založené na zamykání dat a tzv. optimistické protokoly souběžného řízení. Podrobněji je o těchto protokolech pojednáno v [9].

7. Speciální techniky RTDBS

7.1 Databáze v operační paměti
Jak již bylo zmíněno, jedním z největších problémů při návrhu RTDBS je dlouhé a často nepředvídatelné zpoždění, způsobené přístupem k datům na disku. Nabízí se možnost trvale uložit celou databázi do operační paměti a v této paměti s ní i pracovat, čímž se vyloučí vstupně-výstupní přístup k diskům, velké vytížení procesoru mezioperačním ukládáním přenosových dávek do vyrovnávací paměti a v neposlední řadě odpadnou problémy priorit a časování přístupů na disk. V porovnání s přístupem na disk je přístup do operační paměti mnohem rychlejší a je snáze předvídatelný. Tyto vlastnosti jsou v RTDBS velmi žádoucí, a dokonce mohou být nezbytné v případě, že transakce mají extrémně tvrdé časové požadavky.

I tento přístup však má své nevýhody. Především, paměťově rezidentní databáze jsou dražší než klasické diskové systémy. Přestože se technologie zvyšování hustoty paměťových médií stále vyvíjí a cena těchto médií klesá, neustále existují limity množství dat, které lze rezidentně umístit do paměti. Dalším problémem v souvislosti s operační pamětí je její nestálost. Data uložená v hlavní paměti jsou obvykle ztracena při výpadku napájení nebo při poruše procesoru. Proto paměťově rezidentní databáze stále vyžadují přístup k disku pro zálohování a ukládání souborů s údaji o monitorování systému (log-files). Klasické zotavovací protokoly, které zpětně naplňují paměť celou databází z diskové zálohy a následně použijí záznamy o výkonu transakcí (transaction logs) k úpravě databáze, aby byla aktuální, jsou pro použití v systémech reálného času příliš pomalé. Oblast efektivního zálohování a obnovy paměťově rezidentních databází se neustále vyvíjí.

V klasických databázových systémech jsou datové struktury a algoritmy zpracovávání dotazů optimalizovány na redukci počtu přístupů na disk a zlepšení přenosu datových bloků. Při použití paměťově rezidentních databází jdou tyto principy stranou a v popředí je snaha redukovat zatížení CPU a množství potřebné paměti. Konvenční přístupové metody a databázové struktury jsou v tomto případě neefektivní. Databáze v operační paměti rovněž může být organizována jinak než na disku. Například je možné šetřit kapacitou paměti. Jestliže se údaj vyskytuje v databázi víckrát než jednou, je možné jednoduše uložit pouze jednu kopii položky a zavést na ni ukazatele. Také indexové schéma může být u databází v operační paměti odlišné. Obecná indexová schémata v systémech na disku jsou tzv. B-stromy. Jelikož je index uložen na disku v blocích, musí být tyto bloky máloúrovňové. Průchod mnohaúrovňovými stromy v operační paměti je mnohem rychlejší. Z toho důvodu je možné při použití databáze v operační paměti mít stromy s více úrovněmi než při použití diskového systému. Proto byla pro takovýto systém navržena jistá modifikace B-stromu, tzv. T-strom, což je binární strom s více prvky na jeden uzel.

Požadavky na zkrácení přístupové doby a zvýšení rychlosti vyřízení transakce rovněž ovlivňují výběr mechanismu souběžného přístupu. Souběžný přístup také redukuje zpoždění v důsledku čekání na data uzamčená jinou transakcí. V tomto případě tedy lze zvětšit zrnitost zamykání, tzn. velikost působnosti transakce vymezené zámkem, aby bylo možné snížit režii systému spojenou s počtem kontrolovaných zámků.

Vývoj v této oblasti zdaleka není ukončen. Specifika oblasti systémů reálného času vyžadují určitý individuální přístup a univerzální řešení RTDBS neexistuje.