Felhőbeli kihívások: Szinkronizálás

  • 10 perc

A maximális teljesítmény eléréséhez az elosztott tevékenységeknek képesnek kell lenniük arra, hogy az adatok sérülésének vagy inkonzisztenciájának kockázata nélkül kezeljék egyidejűleg a megosztott adatokat. A szinkronizáló mechanizmusok úgy tesznek eleget ennek a követelménynek, hogy lehetőséget biztosítanak a programozóknak a tevékenységek által végrehajtott műveletek (olvasás és írás) sorrendjének szabályozására. A GraphLab például lehetővé teszi, hogy egyidejűleg több tevékenység is működjön ugyanannak a gráfnak különböző csúcsain. Ez a képesség versenyhelyzethez vezethet, amelyben két tevékenység egyszerre kísérel meg adatokat módosítani egy megosztott élen, sérült értéket eredményezve. A megoldást az a szinkronizálási módszer jelent, amely biztosítja, hogy az elosztott tevékenységek kölcsönösen kizárólagos adathozzáférést szerezzenek. Ez az úgynevezett kölcsönös kizárás, vagy mutex tulajdonság.

Széles körben alkalmazzák a memóriamegosztási programozási modellről szóló szakaszban ismertetett három szinkronizálási módszert, a szemaforokat, a zárolásokat és a határokat. Ezeknek a módszereknek a hatékony alkalmazása kritikus fontosságú cél az elosztott programok fejlesztése során. Például, bár egy határ viszonylag egyszerűen implementálható, az elosztott programok teljes végrehajtási ideje így a leglassabb tevékenységén fog múlni. Egy olyan elosztott rendszerben, amilyen a felhő, ahol a heterogenitás természetes, ez a helyzet erősen leronthatja a teljesítményt. A megoldandó probléma olyan szinkronizálási módszerek alkalmazása, amelyek nem befolyásolják károsan a teljesítményt.

A szinkronizálási mechanizmusoknak a kölcsönös kizáráson kívül az elosztott programok más tulajdonságait is garantálniuk kell. Először is, ha egy tevékenység egy kritikus szakasz elérésére tesz kísérletet, végül sikerrel kell járnia. Ha két tevékenység egyszerre próbál elérni egy kritikus szakaszt, akkor csak az egyik járhat sikerrel. A helyzet azonban nem mindig a várt módon alakul. Ha az $A$ tevékenység például sikeresen megszerzi a lock1 zárolást, a $B$ tevékenység pedig ezzel körülbelül egy időben megszerzi a lock2 zárolást, akkor ha az $A$ tevékenység kísérletet tesz a lock2 zárolás megszerzésére, a $B$ tevékenység pedig a lock1 zárolás megszerzésére, úgynevezett holtpont jön létre. Az ilyen patthelyzetek elkerülése komoly megoldandó probléma az elosztott programok fejlesztése során, különösen akkor, ha a tevékenységek száma nő, és minden kölcsönös kizárási mechanizmusnak biztosítania kell a holtpontmentességet.

Az $A$ és $B$ tevékenység példáját továbbgondolva most tekintsük a tevékenységek egy nagyobb, $\lbrace A, B, C, \cdots, Z \rbrace$ halmazát. Lehetséges, hogy kölcsönös kizárás biztosításával az $A$ tevékenység a $B$ tevékenységre várakozik, ha $B$ egy $A$ által igényelt zárolást tart fenn. A $B$ viszont a $C$ tevékenységre várakozhat, ha $C$ egy $B$ által igényelt zárolást tart fenn. Az egymásra várakozó tevékenységek sora akár a $Z$ tevékenységig is tarthat. Konkrétan a $C$ várakozhat a $D$-re, a $D$ az $E$-re és így tovább az $Y$ tevékenységig, amely a $Z$ tevékenységre várakozik. Az ilyen várakozási láncokat általában tranzitív lezárásnak nevezzük. Tranzitív lezárás esetén körkörös várakozás alakulhat ki. Az ilyen helyzet rendszerint feloldhatatlan holtponthoz vezet, amely egy teljes elosztott program vagy rendszer leállását okozhatja. Végezetül megjegyzendő, hogy minden kölcsönös kizárási mechanizmus központi kérdése az egymásra várakozási reláció. Egyetlen kölcsönös kizárási protokoll, még a legokosabb sem zárhatja ki az előfordulását.2 Normál helyzetben a tevékenységeknek várhatóan véges (ésszerűen rövid) ideig kell várakozniuk. De mi történik, ha egy zárolást vagy tokent fenntartó tevékenység összeomlik? Ez a kérdés már az elosztott programokkal kapcsolatos következő probléma, nevezetesen a hibatűrő képesség témakörébe tartozik.

Tudta?

Az elosztott rendszerekben a kölcsönös kizárás két fő osztály, a tokenalapú és az engedélyalapú egyikébe sorolható be.

A tokenalapú módszer az elosztott program tevékenységei között átadott egyetlen üzenettel, egy úgynevezett tokennel valósítja meg a kölcsönös kizárást. A token beszerzése a zárolás megvalósításának tekinthető. Ennek megfelelően a tokent birtokló tevékenység hozzáfér a megosztott adatokhoz, a többi tevékenységnek viszont ki kell várnia, hogy sorra kerüljön. A tokenalapú módszert használó tevékenységek általában logikailag körkörösen vannak elrendezve. Amikor egy feladat végez, továbbadja a tokent a körben utána következőnek. A következő tevékenység eldöntheti, hogy hozzáfér a megosztott adatokhoz, vagy egyszerűen továbbadja a tokent annak, amelyik a körben őt követi.

A tokenalapú módszer elejét veszi, hogy egy tevékenység egyáltalán ne férjen hozzá az adatokhoz, mert igazságosan biztosítja, hogy minden tevékenység lehetőséget kapjon a hozzáférésre. Nagy hátránya azonban egy, a megbízhatósággal kapcsolatos probléma. Arról van szó, hogy ha a token elveszik a hálózaton (például hálózati hiba következtében), vagy a tokent éppen birtokló tevékenység összeomlik, többnyire csak egy bonyolult elosztott eljárás bevonásával oldható meg, hogy az elosztott program továbbra is megfelelően működjön. Egy token elvesztése egy elosztott rendszerben a rendszer felskálázásával egyre súlyosabb problémát jelent. Ez abból ered, hogy nagyméretű rendszerekben a gép- és hálózati hibák valószínűsége is nagyobb.

Az engedélyalapú módszerrel a kölcsönös kizárás annak megkövetelésével érhető el, hogy a tevékenységek engedélyt (például zárolást) kérjenek a megosztott adatok eléréséhez. Az a módszer implementálható központosított és decentralizált algoritmussal is. A központosított algoritmus egy koordinátort használ, amely megadja az engedélyeket. Egy tevékenység bármikor a koordinátorhoz fordulhat, hogy engedélyt kérjen. A koordinátor vagy megadja, vagy megtagadja az engedélyt attól függően, hogy más tevékenységek már hozzáférnek-e a kért adatokhoz. A koordinátor gondoskodik arról, hogy egy megosztott adatot egyszerre csak egy tevékenység írhasson, de megengedheti, hogy ugyanannak az adatnak több tevékenység általi olvasása is folyamatban legyen.

A központosított algoritmusok könnyen implementálhatók, elkerülik a tevékenységek hozzáféréstől való megfosztását, és igazságosak. Az engedélyek megadhatók például abban a kérésük sorrendjében, egy előre megadott időtartamra, ezzel biztosítva, hogy minden tevékenységnek lehetősége legyen a kérésére. A központosított algoritmusoknak azonban súlyos hátrányai is vannak. Először is, a koordinátor rendszerkritikus meghibásodási pontot (SPOF) képez. Ez azt jelenti, hogy a koordinátor meghibásodása esetén az egész rendszer leáll. Másodszor, a koordinátor szűk keresztmetszet lehet a teljesítmény szempontjából, különösen a csomópontok és a felhasználók számának felskálázása esetén.

A központosított algoritmusoknak ezt a két hátrányát elkerülendő, a decentralizált algoritmusok a központi koordinátor több koordinátorra való felosztását javasolják.1 Emiatt ahhoz, hogy egy feladat (írási) engedélyt szerezzen, meg kell kapnia a koordinátorok többségének szavazatát (a szavazási mechanizmusok beiktatását ennek a modulnak a 4. leckéje tárgyalja részletesebben). Nyilvánvaló, hogy az ilyen engedélyek beszerzése által az elosztott program kevésbé lesz sérülékeny a rendszerkritikus meghibásodási pontokkal szemben. Még pontosabban, egy decentralizált kölcsönös kizárási algoritmussal rendelkező elosztott program $2K + 1$ koordinátor közül $K$ darab meghibásodását viseli el.1 A decentralizált algoritmusok a teljesítménynek a központosított algoritmussal megjelenő szűk keresztmetszetét is megszüntetik. A decentralizált algoritmusok implementálása és karbantartása bonyolultabb, mint a központosítottaké. Az implementálás és a karbantartás bonyolultsága általában gátolja a skálázhatóságot, különösen a vezérlő üzenetek számának jelentős növekedése esetén.


Hivatkozások

  1. A. S. Tanenbaum és M. V. Steen (2006. október 12.). Elosztott rendszerek: Principles and Paradigms Prentice Hall, Second Edition
  2. M. Herlihy és N. Shavit (2008. március 14.). The Art of Multiprocessor Programming Morgan Kaufmann, First Edition

Tesztelje tudását

1.

Tekintsük a következő függvényt:

transaction (Account source, Account destination, double amount)
{
  Acquire lock on source;
  Acquire lock on destination;
  withdraw(from, amount);
  deposit(to, amount);
  Release lock on destination;
  Release lock on source;
}

Tegyük fel, hogy kezdetben az A és a B számlán is 100 dollár van, és az alábbi műveletek egyidejűleg vannak végrehajtva úgy, hogy mindkét művelet egyszerre zárolja a forrásszámlát (a tranzakciós függvény 3. sorában):

1 Transaction(A,B,50); and Transaction(B,A,10);

Mi lesz az eredmény?