Czy optymistyczna współbieżność na obiekt sugeruje możliwość szeregowania, jeśli transakcja nigdy nie obejmuje wielu obiektów?

Biorąc pod uwagę system, który zapewnia:

• Optymistyczna kontrola / kontrola współbieżności dla każdego obiektu (przy użyciu CAS - Check-and-Set)
• Transakcje, które nigdy nie muszą obejmować więcej niż jednego obiektu.
• Izolacja migawki

Czy ten system jest uznawany za możliwy do serializacji ?

Od izolacji migawki

W anomalii skosu zapisu dwie transakcje (T1 i T2) jednocześnie odczytują nakładający się zestaw danych (np. Wartości V1 i V2), jednocześnie dokonują rozłącznych aktualizacji (np. Aktualizacje T1 V1, aktualizacje T2 V2), a na koniec jednocześnie zatwierdzają, żadna z nich nie widziała aktualizacja wykonana przez drugą osobę. Gdyby system był szeregowalny, taka anomalia byłaby niemożliwa, ponieważ albo T1, albo T2 musiałyby wystąpić „pierwsze”, a byłyby widoczne dla drugiego. Natomiast izolacja migawek umożliwia anomalie skosu zapisu.

Jako konkretny przykład, wyobraźmy sobie, że V1 i V2 to dwie wagi utrzymywane przez jedną osobę, Phila. Bank pozwoli deficytowi V1 lub V2 osiągnąć deficyt, pod warunkiem, że suma utrzymywana w obu nigdy nie będzie ujemna (tj. V1 + V2 ≥ 0). Oba salda wynoszą obecnie 100 USD. Phil inicjuje jednocześnie dwie transakcje, T1 wycofuje 200 USD z V1, a T2 wycofuje 200 USD z V2.

Na tej podstawie wydaje się, że możliwość przekrzywienia zapisu jest jedynym powodem, dla którego system gwarantujący, że izolacja migawek nie jest serializowalna.

Jednak w systemie, który nie zezwala na transakcję obejmującą wiele obiektów (w powyższym przykładzie V1 i V2) wydaje się niemożliwe wystąpienie skosu zapisu .

Dlatego system opisany powyżej jest szeregowalny. Czy to jest poprawne?

Nie, nie sądzę, aby twoje ustalenia doprowadziły do ​​systemu, który powinniśmy uznać za możliwy do serializacji.

Izolacja migawek to technika zapewniająca, że ​​transakcja widzi ten sam zestaw danych przez całą transakcję. Izolacja migawek zapewnia pewne gwarancje, ale nie definiuje wszystkich cech niezbędnych do zrozumienia, w jaki sposób transakcje naprawdę działają (chyba że zdecydujemy się połączyć izolację migawek i MVCC).

Izolacja migawek jest najczęściej implementowana przy użyciu MVCC, Multi Consistency Control. MVCC definiuje więcej szczegółów transakcji w kontekście ich migawek: mówi się, że wymagają one izolacji tylko w przypadku zapisu konfliktu (tylko lokalizacje lub lokalizacje + wartości, w zależności od implementacji). MVCC zapewnia zrelaksowany model spójności i cierpi na przekrzywienie zapisu.

Modele zrelaksowanej spójności są trudne do zrozumienia, ponieważ są jak hybryda pomiędzy brakiem izolacji a pełną izolacją.

Zacznijmy więc od ścisłego modelu współbieżności. Dwie transakcje muszą być odizolowane od siebie, jeśli jedna zapisuje dane, które druga albo odczytuje, albo zapisuje (i odwrotnie ...).

Kiedy nie wiemy, dlaczego transakcja odczytuje dane, musimy założyć, że inna odczytana wartość może zmienić zachowanie klienta, dlatego warunek nakładających się transakcji wskazuje na izolację. Bez izolacji odczyt nieaktualnych danych w migawce może z łatwością wykazywać swobodną spójność, co jest innym terminem, dla którego występuje niespójność, czyli błąd.

Musimy jedynie wziąć pod uwagę dokładne dane odczytane lub zapisane przez transakcje, wszelkie dane poza tym zestawem nie muszą być brane pod uwagę. Jednak bardzo ważne jest, aby zdawać sobie sprawę, że kiedy mówimy o danych odczytywanych przez transakcję, koniecznie musimy uwzględniać wszystkie dane „meta” (oraz dane i metadane odczytywane przez operacje meta, takie jak sprawdzanie ograniczeń). Przykłady metadanych to / metaoperacje to: identyfikacja unikalnego nowego klucza głównego; innym jest suma całej kolumny; innym jest poszukiwanie czegoś i nie znajdowanie go; wyszukiwania zasięgu lub sumy. To odnosi się do komentarza @ Matthew na temat zapobiegania duplikatom, a także odpowiedzi @Tersosauros, w której uważa stan.

Na przykład oznacza to, że dwie transakcje nakładają się (wymagają izolacji), gdy obie wstawiają wiersz (zakładając unikalne ograniczenie klucza podstawowego), ponieważ sprawdzenie ograniczenia klucza jest równoznaczne z odczytaniem całej kolumny klucza podstawowego. Jako kolejny przykład szukanie czegoś i znajdowanie go jest jak czytanie tej jednej wartości, jednak nie znajdowanie tego jest jak patrzenie na każdą wartość w kolumnie.

MVCC chroni tylko przed nakładającymi się lub sprzecznymi zapisami, ale nie chroni przed odczytami (chyba, że ​​również napisane przez tę transakcję). Tak więc, aby uzyskać błąd spójności w MVCC, wszystko, co musimy zrobić, to odczytać coś, co zostało zmienione przez inną transakcję (gdzie inna transakcja dzieje się po uzyskaniu migawki formatora, ale zatwierdza się jako pierwsza), podczas gdy druga transakcja nadal korzysta ze starych danych i podejmuje inną decyzję w oparciu o te nieaktualne dane w porównaniu z aktualnymi danymi. Łatwiej jest to spowodować, niż myślisz.

Zrelaksowana spójność to kolejny sposób na stwierdzenie potencjalnie niespójności lub podatności na błędy. (Zrelaksowanej spójności nie należy mylić z ostateczną spójnością, która jest inną popularną formą podatną na błędy niż „NoSQL”).

Jeśli chodzi o twoje pytanie, gdy mówisz, że transakcje nigdy nie muszą obejmować więcej niż jednego obiektu, musi to dotyczyć zarówno odczytów i zapisów, jak i metadanych (i operacji meta), w tym sprawdzania spójności, agregacji całych kolumn, kontroli nieobecności, wyszukiwania zakresu itp. .: jeśli tak, to jak dotąd tak dobrze.

Jednak...

Biorę z twojego pytania, że ​​używasz izolacji migawek (MVCC) na poszczególnych obiektach (powiedzmy raczej niż blokowanie obiektu). (Wspominasz także o CAS; słyszałem o porównywaniu i zamianie oraz testowaniu i ustawianiu, ale nie sprawdzaniu i ustawianiu, chociaż zakładam, że jest podobnie).

Twój opis pytania sugeruje mi, że „obiekty” mają więcej niż jedno pole, w przeciwnym razie postanowienia pytania byłyby niepotrzebne.

Dlatego, ponieważ twoje obiekty migawkowe / obsługiwane przez MVCC mają więcej niż jedno pole, masz skłonność do pisania w pojedynczych obiektach. Jeśli dwie transakcje aktualizują ten sam obiekt w tym samym czasie, można odczytać pole wartości obiektu, które stało się nieaktualne przez jednoczesną inną transakcję na tym samym obiekcie, i kontynuować bez wiedzy o potencjalnej niespójności (inaczej błąd).

Zamiast tego można użyć blokowania obiektu, co uniemożliwiłoby nawet dwóm transakcjom (w celu aktualizacji) spojrzenie na ten sam obiekt, jeśli inna transakcja była już w trakcie przetwarzania.

Uważam, że alternatywną formę izolacji migawek można wykonać bez użycia modelu porównawczego uszkodzonego zestawu zapisu tylko MVCC. Możesz więc (algorytmicznie) wypromować zestaw porównawczy z trybu tylko do zapisu, aby uwzględnić również zestaw do odczytu. Wtedy dwie transakcje aktualizujące ten sam obiekt nie byłyby w stanie spowodować skosu zapisu (ponieważ ta, która próbuje później zatwierdzić, zostałaby przerwana). Myślę, że może to być odpowiednie rozwiązanie opisywanego problemu, ponieważ już czerpiesz większość korzyści, które kupiłby nam MVCC, wykluczając transakcje z wieloma obiektami.

(Musimy tylko wziąć pod uwagę dokładne i określone elementy / pola odczytane lub zapisane, ale musimy uwzględnić te odczytane jako metadane, potencjalnie podczas operacji na meta, aby zapobiec przekrzywieniu zapisu (tj. Błądowi). Jeśli usuniemy zestaw odczytu z zestawu porównawczego lub nie uwzględniamy metadanych (potencjalnie wykorzystywanych przez operacje meta), wówczas mamy model, który pozwoli na błąd.)

Myślę, jak stwierdził @ pjc50 , ^{(Podkreślenie dodane :)} „ jeśli transakcje są ograniczone do odczytu / zapisu pojedynczego obiektu”, wówczas „odpowiedź brzmi tak”. Myślę jednak, że tam, gdzie to spada, leży idea jednego obiektu.

W przykładzie zaczerpniętym z izolacji migawki T1 i T2 nie dzielą żadnej wartości. Nadal jednak mają one potencjał zniekształcania zapisu, ponieważ „ żadne [nie] widziało aktualizacji wykonanej przez inne ” ^źródło . W związku z tym możliwość transakcji, aby zobaczyć wszystkie inne aktualizacje przed zatwierdzeniem, sprawia, że ​​transakcja jest naprawdę możliwa do serializacji.

Od serializacji :

Możliwość szeregowania harmonogramu oznacza równoważność (w wyniku, stan bazy danych, wartości danych) z harmonogramem szeregowym (tj. Sekwencyjny bez transakcji pokrywających się w czasie) z tymi samymi transakcjami.

Niestety z tego powodu (i jak zauważa @Matthew Mark Miller ) musimy również wziąć pod uwagę stan i wartości. Biorąc to pod uwagę, dwie transakcje z wykorzystaniem OCC mogą potencjalnie wypaczać zapis przy każdym zapisaniu dowolnego stanu bazy danych .