Kauzální konzistence - Causal consistency

Kauzální konzistence je jednou z hlavních pamětí modely konzistence. v souběžné programování, kde souběžné procesy přistupují ke sdílené paměti, a model konzistence omezuje, které přístupy jsou legální. To je užitečné pro definování správného datové struktury v distribuovaná sdílená paměť nebo distribuované transakce.

Příčinná konzistence je „K dispozici v oddílu“, což znamená, že proces může číst a zapisovat do paměti (paměť je k dispozici), i když mezi procesy není funkční síťové připojení (síť je rozdělena); je to asynchronní model. Kontrastuje se silnými modely konzistence, jako je sekvenční konzistence nebo linearizovatelnost, což nemůže být obojí bezpečný a žít pod oddílem a reagují pomalu, protože vyžadují synchronizaci.

Příčinná konzistence byla navržena v 90. letech [1] jako slabší model konzistence pro modely sdílené paměti. Kauzální konzistence úzce souvisí s konceptem kauzálního vysílání v komunikačních protokolech.[2] V těchto modelech je distribuovaná exekuce reprezentována jako částečná objednávka, založená na Lamportově stalo se předtím koncept potenciální kauzality. [3]

Kauzální konzistence je užitečný model konzistence, protože odpovídá intuici programátorů o čase, je dostupnější než silné modely konzistence, přesto poskytuje užitečnější záruky než případná konzistence. Například v distribuovaných databázích kauzální konzistence podporuje pořadí operací, na rozdíl od případná konzistence.[4] Také kauzální konzistence pomáhá s vývojem abstraktní datové typy například fronty nebo čítače. [5]

Protože čas a objednávání jsou pro naši intuici tak zásadní, je těžké se domnívat, že systém nevynucuje kauzální konzistenci. Mnoho distribuovaných databází však tuto záruku postrádá, dokonce i ty, které poskytují serializovatelnost.[6]Klíč zaručuje kauzální konzistenci, ale také si vynucuje silnou konzistenci, čímž se vyhýbá dostupnost pod oddílem Zahrnuje více dostupných databází, které zajišťují kauzální konzistenci MongoDB a AntidoteDB.

Definice

Kauzální konzistence zachycuje potenciální kauzální vztahy mezi operacemi a zaručuje, že všechny procesy sledují kauzálně související operace ve společném pořadí. Jinými slovy, všechny procesy v systému se shodují na pořadí kauzálně souvisejících operací. Mohou nesouhlasit v pořadí operací, které kauzálně nesouvisí.[1]

Pojďme definovat následující vztah. Pokud nějaký proces provádí operaci zápisu A a nějaký (stejný nebo jiný) proces, který pozoroval A, pak provede operaci zápisu B, je možné, že A je příčinou B; říkáme, že A „potenciálně způsobuje“ nebo „kauzálně předchází“ B. Kauzální konzistence zaručuje, že pokud A kauzálně předchází B, pak každý proces v systému pozoruje A před pozorováním B. Naopak, dvě operace zápisu C a D jsou považovány za souběžné, nebo kauzálně nezávislý, pokud žádný kauzálně nepředchází druhého. V tomto případě může proces pozorovat buď C před D, nebo D před C. Vztah příčinné priority ve sdílené paměti souvisí s stalo se předtím vztah v komunikaci založené na zprávách.[3]

Systém tedy poskytuje kauzální konzistenci, pokud platí tato následující podmínka: operace zápisu, které souvisejí s potenciální kauzálností, vidí každý proces systému v pořadí jejich kauzální priority. Různé procesy mohou pozorovat souběžné zápisy v různých objednávkách.[7]

Model kauzální konzistence je slabší než sekvenční konzistence, což zajišťuje, že všechny procesy sledují všechny operace zápisu ve společném pořadí, ať už kauzálně související nebo ne. [8] Kauzální konzistence je však silnější než Konzistence PRAM, což vyžaduje, aby byly navzájem sledovány v běžném pořadí pouze operace zápisu prováděné jedním procesem. [9] Z toho vyplývá, že když je systém postupně konzistentní, je také kauzálně konzistentní. Kauzální konzistence navíc znamená konzistenci PRAM, ale ne naopak.

Příklad

Zde je příklad kauzální konzistence. [10]

Příčinné vztahy jsou respektovány v následující posloupnosti událostí:

P1:Š (x) 1Š (x) 3
P2:R (x) 1Š (x) 2
P3:R (x) 1R (x) 3R (x) 2
P4:R (x) 1R (x) 2R (x) 3

Proces P2 sleduje, čte, dřívější zápis W (x) 1, který se provádí procesem P1. Proto jsou dva zápisy W (x) 1 a W (x) 2 kauzálně příbuzné. V kauzální konzistenci každý proces nejprve pozoruje W (x) 1, než pozoruje W (x) 2. Všimněte si, že dvě operace zápisu W (x) 2 a W (x) 3, bez intervenčních operací čtení, jsou souběžné a procesy P3 a P4 je sledují (čtou) v různých pořadích.

Záruky zasedání

Model kauzální konzistence lze upřesnit na čtyři záruky relace..[11] Lze je shrnout takto:

  • Přečtěte si své zápisy: Pokud proces provádí zápis, stejný proces později sleduje výsledek svého zápisu.
  • Monotónní čtení: je zaručeno, že množina zápisů pozorovaných (čtených) procesem bude monotónně neklesající.
  • Zápisy sledují čtení: pokud některý proces provádí čtení, po kterém následuje zápis, a jiný proces sleduje výsledek zápisu, může také pozorovat čtení (pokud nebyl přepsán).
  • Monotónní zápisy: Pokud některý proces provede zápis, za nímž později následuje další zápis, ostatní procesy je budou sledovat ve stejném pořadí.

Záruky transakční relace pro serializovatelnost a izolaci snímků představují Daudjee a Salem.[12]

Implementace

Systém je abstrahován jako sada komunikujících procesů. Když proces zapisuje do sdílené paměti, implementace odešle tuto událost do ostatních procesů (prostřednictvím sdílené paměti nebo jako zprávu). Kvůli souběžnosti a poruchám může proces přijímat události v libovolném pořadí. Implementace přináší událost, tj. zviditelní ji procesu, pouze pokud byly doručeny všechny události, které ji kauzálně předcházejí. metadata který představuje kauzální vztahy mezi přístupy do paměti.

Stručně řečeno, implementace zahrnuje následující kroky: (1) Udržovat kauzální kontext metadata v každém procesu, aby bylo možné shrnout, jaké aktualizace kauzálně předcházejí aktuálnímu stavu. (2) Když proces aktualizuje paměť, označte událost aktualizace kauzálním kontextem tohoto procesu, abyste shrnuli, jaké aktualizace kauzálně předcházejí této aktualizaci. (3) A proces, který má obdržel některé aktualizace mohou doručit pouze v případě, že značka události kauzálně předchází příčinnému kontextu přijímajícího procesu. (Jako vedlejší účinek doručení přidejte novou událost do příčinného kontextu přijímacího procesu.) Jinak byla aktualizace přijata příliš brzy a musí zůstat do mezipaměti, dokud událost neodpovídá kontextu. Mezitím implementace buď pasivně čeká na přijetí chybějících událostí, nebo je aktivně načte z jejich zdroje.

Tento přístup umožňuje dostupnost pod oddílem.[13]

Existují dvě společná znázornění pro metadata kauzálního kontextu. Jedním z nich je udržovat explicitní graf závislosti vztahu kauzální závislosti. Protože takový graf může růst libovolně velký, událost je často označena pouze svými bezprostředními předchůdci; určení jeho tranzitivních předchůdců vyžaduje distribuovaný přechod grafu. Druhým je udržování a vektorové hodiny, s jednou položkou na proces (nebo skupinu procesů), počítá se počet událostí generovaných procesem nebo skupinou. Tato reprezentace má pevnou velikost a pořadí událostí lze odvodit pomocí jednoduché srovnání vektorů.

Chcete-li přesně určit, které události jsou závislé a které jsou souběžné v systému plně peer-to-peer, je velikost metadat alespoň úměrná počtu aktivních spisovatelů.[14]Přesné určení souběžnosti je však obecně přehnané. Kauzální konzistence vyžaduje pouze to, aby byly kauzálně závislé události doručovány v pořádku; Nezáleží na tom, zda jsou objednány dvě souběžné události. Proto lze velikost libovolně snížit pomocí technik bezpečného přiblížení. [15]V limitu jeden skalární (Lamportovy hodiny[3]) postačuje za cenu odstranění jakékoli souběžnosti. Velikost metadat lze také snížit omezením topologie komunikace; například ve hvězdě, stromu nebo lineární topologii stačí jeden skalární.

Hledání účinných implementací kauzální konzistence je velmi aktivní oblastí výzkumu.

Reference

  1. ^ A b Ahamad, M., Neiger, G., Burns, J. E., Kohli, P., & Hutto, P. W. (1995). Kauzální paměť: Definice, implementace a programování. Distribuované výpočty, 9 (1), 37-49.
  2. ^ Kenneth P. Birman, Thomas A. Joseph (1987). Spolehlivá komunikace za přítomnosti poruch. Trans. na Comp. Sys. (TOCS), 5 (1), 47–76.
  3. ^ A b C Lamport, L. (1978). Čas, hodiny a řazení událostí v distribuovaném systému. Sdělení ACM, 21 (7), 558-565.
  4. ^ Elbushra, M. M. a Lindström, J. (2015). Kauzálně konzistentní databáze. Otevřený deník databází (OJDB), 2 (1), 17-35.
  5. ^ Perrin, M., Mostefaoui, A., & Jard, C. (2016, únor). Příčinná konzistence: mimo paměť. In Proceedings of the 21. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (str. 26). ACM.
  6. ^ K. Daudjee a K. Salem. Líná replikace databáze se zárukou objednání. V Int. Konf. o datovém inženýrství, s. 424–435, duben 2004.
  7. ^ Gogia, R., Chhabra, P., & Kumari, R. (2014). Modely konzistence v distribuovaných systémech sdílené paměti. International Journal of Computer Science and Mobile Computing, 196-201
  8. ^ Lamport, L. (1979). Jak vytvořit víceprocesorový počítač, který správně provádí víceprocesové programy. Transakce IEEE na počítačích, 100 (9), 690-691.
  9. ^ Lipton, R. J. a Sandberg, J. S. (1988). PRAM: Škálovatelná sdílená paměť. Princetonská univerzita, Katedra informatiky, Chicago
  10. ^ Mosberger, D. (1993). Modely konzistence paměti. Recenze operačních systémů ACM SIGOPS, 27 (1), 18-26.
  11. ^ Terry, D. B., Demers, A. J., Petersen, K., Spreitzer, M. J., Theimer, M. M., & Welch, B. B. (1994, září). Záruky relace pro slabě konzistentní replikovaná data. In Parallel and Distributed Information Systems, 1994., Proceedings of the Third International Conference on (str. 140-149). IEEE.
  12. ^ K. Daudjee a K. Salem. Líná replikace databáze s izolací snímků. VLDB 2006.
  13. ^ Carlos Baquero a Nuno Preguiça. Proč jsou logické hodiny snadné. Comm. ACM 59 (4), s. 43–47, duben 2016.
  14. ^ B. Charron-Bost, Velikost logických hodin v distribuovaných systémech. In Information Information Letters, 39 (1) str. 11-16, 1991.
  15. ^ Torres-Rojas, Francisco J. a Ahamad, Mustaque. Věrohodné hodiny: logické hodiny konstantní velikosti pro distribuované systémy. Distributed Computing, 12 (4), 1999.