Detektor poruchy - Failure detector - Wikipedia

V distribuované výpočty systém, a detektor poruch je počítačová aplikace nebo a subsystém který je odpovědný za detekci uzel selhání nebo havaruje.[1] Detektory poruch byly poprvé představeny v roce 1996 Chandrou a Touegem ve své knize Nespolehlivé detektory poruch pro spolehlivé distribuované systémy. Kniha zobrazuje detektor poruch jako nástroj pro zlepšení shoda (dosažení spolehlivosti) a atomové vysílání (stejná sekvence zpráv) v distribuovaném systému. Jinými slovy, detektory poruch hledají chyby v proces a Systém bude udržovat úroveň spolehlivost. V praxi po detekci selhání detektorů selhání systém zakáže procesy, které dělají chyby, aby zabránil dalším závažným haváriím nebo chybám.[2][3]

V 21. století, detektory selhání jsou široce používány v distribuovaných výpočetních systémech k detekci chyby aplikace, jako je a softwarová aplikace přestane správně fungovat. Vzhledem k tomu, projekty distribuované výpočetní techniky (viz Seznam projektů distribuovaného výpočtu ) se stávají stále populárnějšími, použití detekce selhání se také stává důležitým a kritickým.[4][5]

Původ

Nespolehlivý detektor poruch

Chandra a Toueg, spoluautoři knihy Nespolehlivé detektory poruch pro spolehlivý distribuovaný systéms (1996), přistoupil k konceptu detekce poruchových uzlů zavedením nespolehlivého detektoru selhání.[6] Popisují chování nespolehlivého detektoru selhání v distribuovaném výpočetním systému jako: po každém proces v systému byla zadána lokální součást detektoru selhání, každá lokální komponent prozkoumá část všech procesů v systému.[5] Kromě toho musí každý proces také obsahovat programy které jsou v současné době podezřelé z detektorů poruch.[5]

Detektor poruchy

Tento obrázek popisuje chování typického detektoru selhání (FD).

Chandra a Toueg tvrdili, že nespolehlivý detektor selhání může být stále spolehlivý při detekci chyb způsobených systémem.[6] Zobecňují nespolehlivé detektory poruch na všechny formy detektorů poruch, protože nespolehlivé detektory poruch a detektory poruch mají stejné vlastnosti. Chandra a Toueg dále poukazují na důležitou skutečnost, že detektor poruch nezabrání žádným haváriím v systému, a to ani v případě, že došlo k podezření na havarovaný program dříve. Konstrukce detektoru poruch je zásadním, ale velmi obtížným problémem, který nastal při vývoji systému tolerantní k chybám komponenta v distribuovaném počítačovém systému. Výsledkem je, že byl vyvinut detektor poruch kvůli potřebě detekovat chyby v rozsáhlé informační transakci v distribuovaných výpočetních systémech.[1][3][5]

Vlastnosti

Třídy detektorů poruch se vyznačují dvěma důležitými vlastnostmi: úplnost a přesnost. Úplnost znamená, že detektory poruch naleznou programy, které se nakonec v procesu zhroutily, zatímco přesnost znamená, že správná rozhodnutí, která detektory selhání provedly v procesu.[5]

Stupně úplnosti

Stupně úplnosti závisí na počtu havarovaných procesů podezřelých z detektoru selhání v určitém období.[5]

  • Silná úplnost: „každý vadný každý nezávadný proces je nakonec trvale podezřelý. “[6]
  • Slabá úplnost: „každý vadný proces je nakonec trvale podezřelý z nějakého vadného procesu. “[6]

Stupně přesnosti

Stupně přesnosti závisí na počtu chyb, které detektor poruchy v určitém období udělal.[5]

  • Vysoká přesnost: „Před selháním není podezřelý (kdokoli) žádný proces.“[6]
  • Slabá přesnost: „nikdy není podezření na nějaký vadný proces.“[6]
  • Nakonec silná přesnost: „Po nějaké době od konce počátečního období chaosu, jako je čas, kdy dojde k poslední havárii, není podezření na žádný vadný proces.“[6]
  • Případná slabá přesnost: „Po určitém počátečním období záměny není nikdy podezřelý nějaký bezchybný proces.“[6]

Klasifikace

Detektory poruch lze rozdělit do následujících osmi typů:[1][7]

  1. Perfektní detektor poruch (P)
  2. Nakonec perfektní detektory poruch (♦ P)
  3. Detektory silných poruch (S)
  4. Nakonec silné detektory poruch (♦ S)
  5. Slabé detektory poruch (Ž)
  6. Nakonec slabé detektory poruch (♦ W)
  7. Kvazi perfektní detektory poruch (Q)
  8. Nakonec kvazi-perfektní detektory poruch (♦ Q)

Vlastnosti těchto detektorů poruch jsou popsány níže:[1]

Přesnost

Kompletní-
ness
Silný
Věčný
Přesnost		Slabý
Věčný
Přesnost		Silný
Eventuální
Přesnost		Slabý
Eventuální
Přesnost
Silná úplnostPS♦ P♦ S
Slabá úplnostQŽ♦ Q♦ W

Stručně řečeno, vlastnosti detektorů poruch závisí na tom, jak rychle detekuje poruchový detektor skutečné selhání a jak dobře se vyhne falešné detekci. Dokonalý detektor poruch najde všechny chyby bez jakýchkoli chyb, zatímco detektor slabé poruchy nenajde žádné chyby a udělá četné chyby.[3][8]

Aplikace

Různé typy detektorů poruch lze získat změnou vlastností detektorů poruch.[3][6] První příklady ukazují, jak zvýšit úplnost detektoru selhání, a druhý příklad ukazuje, jak změnit jeden typ detektoru selhání na jiný.

Zvyšování úplnosti

Následuje příklad odebraný z Katedry informatiky na Yale University. Funguje tak, že zvyšuje úplnost detektoru poruch.[6]

zpočátku podezřívá = ∅do navždy: pro každý proces p: pokud můj slabý detektor podezřívá p, pak pošle p všem procesůmpři přijetí p z nějakého procesu q: podezřelí: = podezřelí + p - q

Z výše uvedeného příkladu, pokud p havaruje, pak to slabý detektor nakonec podezřívá. Všechny detektory poruch v systému nakonec budou mít podezření na p kvůli nekonečné smyčce vytvořené detektory poruch. Tento příklad také ukazuje, že detektor selhání slabé úplnosti může také případně podezřívat všechny pády.[6] Kontrola havarovaných programů nezávisí na úplnosti.[5]

Omezení detektoru selhání Ž k detektoru selhání S

Následují argumenty správnosti, které uspokojí algoritmus změny detektoru selhání Ž na detektor poruchy S.[1] Detektor poruchy Ž je slabý na úplnost a detektor poruch S je silný v úplnosti. Oba mají slabou přesnost.[6]

  1. Transformuje slabou úplnost na silnou úplnost.[1]
  2. Zachovává trvalou přesnost.[1]
  3. Zachovává případnou přesnost.[1]

Pokud jsou splněny všechny výše uvedené argumenty, redukce detektoru slabé poruchy Ž na silný detektor poruch S bude souhlasit s algoritmus v distribuovaném výpočetním systému.[1]

Viz také

Reference

  1. ^ A b C d E F G h i D., Kshemkalyani, Ajay (2008). Distribuované výpočty: principy, algoritmy a systémy. Singhal, Mukesh. Cambridge: Cambridge University Press. ISBN  9780521189842. OCLC  175284075.
  2. ^ Aguilera, Marcos Kawazoe; Chen, Wei; Toueg, Sam (04.04.2000). "Detekce selhání a shoda v modelu obnovy po havárii". Distribuované výpočty. 13 (2): 99–125. doi:10,1007 / s004460050070. hdl:1813/7330. ISSN  0178-2770.
  3. ^ A b C d Fischer, Michael J .; Lynch, Nancy A .; Paterson, Michael S. (duben 1985). "Nemožnost distribuovaného konsensu s jedním chybným procesem". J. ACM. 32 (2): 374–382. CiteSeerX  10.1.1.13.6760. doi:10.1145/3149.214121. ISSN  0004-5411.
  4. ^ Holohan, Anne; Garg, Anurag (01.07.2005). "Spolupráce online: Příklad distribuovaného výpočtu". Journal of Computer-Mediated Communication. 10 (4): 00. doi:10.1111 / j.1083-6101.2005.tb00279.x. ISSN  1083-6101.
  5. ^ A b C d E F G h Chandra, Tushar Deepak; Toueg, Sam (1996). Nespolehlivé detektory poruch pro spolehlivé distribuované systémy. Deník ACM. Svazek 43, vydání 2. New York, NY, USA: ACM. str. 225–267. doi:10.1145/226643.226647. hdl:1813/7192. ISBN  978-0897914390.
  6. ^ A b C d E F G h i j k l „FailureDetectors“. www.cs.yale.edu. Citováno 2017-10-23.
  7. ^ Aguilera, Marcos Kawazoe; Toueg, Sam (09.10.1996). Randomizace a detekce selhání: Hybridní přístup k řešení konsensu. Distribuované algoritmy. Přednášky z informatiky. Springer, Berlín, Heidelberg. str. 29–39. CiteSeerX  10.1.1.88.1597. doi:10.1007/3-540-61769-8_3. ISBN  978-3540617693.
  8. ^ Chen, Wei; Toueg, S .; Aguilera, M. K. (leden 2002). "O kvalitě služby detektorů poruch". Transakce IEEE na počítačích. 51 (1): 13–32. CiteSeerX  10.1.1.461.5630. doi:10.1109/12.980014. ISSN  0018-9340.

externí odkazy