Řízení souběžnosti multiverze - Multiversion concurrency control

Multiversion concurrency control ( MCC nebo MVCC ), je metoda řízení souběžnosti běžně používaná systémy správy databází k zajištění souběžného přístupu k databázi a v programovacích jazycích k implementaci transakční paměti .

Popis

Bez kontroly souběžnosti, pokud někdo čte z databáze současně s tím, jak do ní píše někdo jiný, je možné, že čtenář uvidí napůl zapsaná nebo nekonzistentní data. Například při bankovním převodu mezi dvěma bankovními účty, pokud čtečka přečte zůstatek v bance, když byly peníze vybrány z původního účtu a než byly uloženy na cílový účet, zdá se, že peníze zmizely z banka. Isolation je vlastnost, která poskytuje záruky při souběžném přístupu k datům. Izolace je implementována pomocí protokolu řízení souběžnosti . Nejjednodušší způsob je nechat všechny čtečky počkat, až se zapisovač dokončí, což je známé jako zámek pro čtení a zápis . Je známo, že zámky vytvářejí konflikty zejména mezi transakcemi s dlouhým čtením a aktualizovanými transakcemi. MVCC si klade za cíl vyřešit problém ponecháním více kopií každé datové položky. Tímto způsobem každý uživatel připojený k databázi uvidí snímek databáze v konkrétním okamžiku v čase. Jakékoli změny provedené zapisovatelem neuvidí ostatní uživatelé databáze, dokud nebudou změny dokončeny (nebo v databázovém smyslu: dokud nebude transakce potvrzena .)

Když databáze MVCC potřebuje aktualizovat část dat, nepřepíše původní datovou položku novými daty, ale místo toho vytvoří novější verzi datové položky. Je tedy uloženo více verzí. Verze, kterou vidí každá transakce, závisí na implementované úrovni izolace. Nejběžnější úrovní izolace implementovanou s MVCC je izolace snímků . S izolací snímků transakce sleduje stav dat jako při zahájení transakce.

MVCC poskytuje konzistentní zobrazení v čase . Čtení transakcí pod MVCC obvykle používá časové razítko nebo ID transakce k určení, jaký stav DB má číst, a přečte tyto verze dat. Transakce čtení a zápisu jsou tedy navzájem izolovány bez nutnosti zamykání. Přestože jsou zámky zbytečné, používají je některé databáze MVCC, jako je Oracle. Zápisy vytvářejí novější verzi, zatímco souběžná čtení přistupují ke starší verzi.

MVCC představuje výzvu, jak odstranit verze, které zastarají a nebudou nikdy přečteny. V některých případech je implementován proces pravidelného procházení a odstraňování zastaralých verzí. Toto je často proces zastavování světa, který prochází celou tabulku a přepíše ji poslední verzí každé datové položky. PostgreSQL může tento přístup použít s procesem VACUUM FREEZE . Jiné databáze rozdělují bloky úložiště na dvě části: datovou část a protokol zpět. Datová část vždy uchovává poslední potvrzenou verzi. Protokol zpět umožňuje obnovení starších verzí dat. Hlavním inherentním omezením tohoto posledně uvedeného přístupu je, že když dojde k úlohám náročným na aktualizace, části protokolu zpět dojde místo a transakce se přeruší, protože jim nelze poskytnout jejich snímek. U databáze orientované na dokumenty také umožňuje systému optimalizovat dokumenty zapisováním celých dokumentů na souvislé části disku-při aktualizaci lze celý dokument přepsat, místo aby byly vyříznuty bity a kusy nebo udržovány v propojeném souvislá struktura databáze.

Implementace

MVCC používá k dosažení konzistence transakcí časová razítka ( TS ) a přírůstková ID transakcí . MVCC zajišťuje, že transakce ( T ) nikdy nebude muset čekat na čtení databázového objektu ( P ) udržováním několika verzí objektu. Každá verze objektu P má jak časovou značku čtení ( RTS ), tak i časovou značku zápisu ( WTS ), která umožňuje konkrétní transakci T i přečíst nejnovější verzi objektu, která předchází transakci časové razítko RTS ( T i ).

Pokud transakce T i chce zapisovat do objektu P a současně se stejným objektem probíhá další transakce T k , musí časové razítko čtení RTS ( T i ) předcházet časovému razítku čtení RTS ( T k ), tj. RTS ( T i ) < RTS ( T k ) , aby byla operace zápisu objektu ( WTS ) úspěšná. Write nelze dokončit, pokud existují jiné nevyřešené transakce s dřívějším čtení razítko ( RTS ) na stejný objekt. Stejně jako stojíte ve frontě v obchodě, nemůžete dokončit svou pokladní transakci, dokud ti před vámi nedokončí svou.

Zopakovat; každý objekt ( P ) má časové razítko ( TS ), ale pokud transakce T i chce zapisovat do objektu a transakce má časové razítko ( TS ), které je starší než aktuální časové razítko objektu, TS ( T i ) < RTS ( P ), pak se transakce přeruší a restartuje. (To je proto, že později transakci již závisí na staré hodnotě.) V opačném případě, T i vytvoří novou verzi objektu P a nastaví čtecí / zapisovací časové razítko TS na novou verzi s časovým razítkem transakce TS ← TS ( T i ).

Nevýhodou tohoto systému jsou náklady na ukládání více verzí objektů do databáze. Na druhou stranu čtení nejsou nikdy blokována, což může být důležité pro pracovní zátěže, které většinou zahrnují čtení hodnot z databáze. MVCC je obzvláště zběhlý v implementaci skutečné izolace snímků , což ostatní metody řízení souběžnosti často dělají buď neúplně, nebo s vysokými náklady na výkon.

Příklady

Souběžné čtení - zápis

V čase = 1 může být stav databáze:

Čas Objekt 1 Objekt 2
0 „Foo“ od T0 "Bar" od T0
1 „Ahoj“ od T1

T0 napsal Objekt 1 = "Foo" a Objekt 2 = "Bar". Poté T1 napsal Objekt 1 = „Dobrý den“ a nechal Objekt 2 na původní hodnotě. Nová hodnota objektu 1 nahradí hodnotu 0 u všech transakcí, které začínají poté, co se T1 potvrdí, ve kterém okamžiku lze verzi 0 objektu 1 sbírat odpadky.

Pokud dlouhotrvající transakce T2 spustí operaci čtení Objektu 2 a Objektu 1 po potvrzení T1 a dojde k souběžné aktualizační transakci T3, která odstraní Objekt 2 a přidá Objekt 3 = "Foo-Bar", bude stav databáze vypadat takto na čas 2:

Čas Objekt 1 Objekt 2 Objekt 3
0 „Foo“ od T0 "Bar" od T0
1 „Ahoj“ od T1
2 (vymazáno) T3 „Foo-Bar“ od T3

V době 2 objektu 2 existuje nová verze, která je označena jako odstraněná, a nový objekt 3. Jelikož souběžně běží T2 a T3, vidí T2 verzi databáze před 2, tj. Před zápisem T3 potvrzeným, protože takový T2 čte objekt 2 = "Bar" a objekt 1 = "Dobrý den". Díky tomu řízení souběžnosti multiversion umožňuje čtení izolace snímků bez jakýchkoli zámků.

Dějiny

Řízení souběžnosti multiverze je podrobně popsáno v dokumentu z roku 1981 „Řízení souběžnosti v distribuovaných databázových systémech“ od Phila Bernsteina a Nathana Goodmana, poté zaměstnáného společností Computer Corporation of America . Článek Bernsteina a Goodmana cituje disertační práci Davida P. Reeda z roku 1978, která zcela jasně popisuje MVCC a prohlašuje ji za originální dílo.

První plavba, komerční databázový software produkt představovat MVCC byl VAX Rdb / ELN , které vyšlo v roce 1984 a vytvořil v Digital Equipment Corporation by Jim Starkey . Starkey pokračoval ve vytváření druhé komerčně úspěšné databáze MVCC - InterBase .

Viz také

Reference

Další čtení

  • Gerhard Weikum, Gottfried Vossen, Transakční informační systémy: teorie, algoritmy a praxe řízení souběžnosti a obnovy , Morgan Kaufmann, 2002, ISBN  1-55860-508-8