Jakie algorytmy / dane do czytania poleciłbyś przy rozwiązywaniu transakcji / blokad odczytu i zapisu?

Uproszczoną klasyczną transakcję bazy danych można wyświetlić jako:

• czytanie M. pozycji
• wykonanie pewnych obliczeń na podstawie tych odczytów
• zapisywanie niektórych wyników N na podstawie tych obliczeń, które mogą obejmować pierwotnie odczytane elementy.

Podczas wykonywania tych transakcji (jednocześnie) należy zachować właściwości ACID .

Dokładnie takie same wymagania (N aktualizacji na podstawie M czyta transakcyjnie) istnieją w innych współbieżnych systemach innych niż DBMS.

Chciałbym dowiedzieć się, jakie algorytmy istnieją do wykonywania / rozwiązywania tych transakcji oraz jakie są względne mocne i słabe strony tych algorytmów. Czy mógłbyś polecić trochę lektury? Mogą to być książki lub referencje / tutoriale online.

Wyjaśnienie:

Na przykład naiwnym algorytmem może być każda transakcja, która przyjmuje jedną globalną blokadę, w efekcie wymuszając pojedyncze wątki i usuwając współbieżność. Nieco bardziej skomplikowanym algorytmem byłyby blokady odczytu / zapisu poszczególnych elementów z uporządkowaniem w celu uniknięcia zakleszczenia). Itp. Czy istnieje dobre źródło dokumentujące różne algorytmy rozwiązywania tego problemu. Przydałaby się nawet odpowiedź, która wskazywała tylko na jeden algorytm z jego siłą i słabościami.

Książka Transactional Information Systems autorstwa Weikum i Vossen obejmuje dość duży obszar, zarówno pod względem teoretycznym, jak i praktycznym, z różnych perspektyw, nie tylko transakcji. Ma około 1000 stron, więc będziesz zajęty przez weekend lub dwa. Z drugiej strony ma prawie 10 lat, więc może być coś bardziej aktualnego. Inne książki z tej linii to Concurrency Control and Recovery in Database Systems autorstwa Bernsteina, P., Hadzilacosa, V. i Goodmana, N., Addisona-Wesleya, 1987, Transaction Processing: Concepts and Techniques autorstwa Jima Graya i Andreasa Reutera oraz Principles Przetwarzania Transakcjiautor: Philip A. Bernstein i Eric Newcomer, 2009. Nie widziałem tego drugiego, ale będąc najnowszym, może to być dobre miejsce na początek, chociaż twoje rozwiązanie można znaleźć w starszych tekstach. Wycieczka do biblioteki może być opłacalna.

Monumentalny tekst w tej dziedzinie to Transakcje atomowe Nancy Lynch i in. Przedstawia formalną relację i dowody wielu rodzajów algorytmów, którymi jesteś zainteresowany. Jest to raczej formalne i żmudne, więc może nie być w twoim guście.

Wiele ostatnich prac poświęcono pamięci transakcyjnej oprogramowania , która stosuje pomysły dotyczące transakcji w aplikacjach wielowątkowych. Każdego roku publikowanych jest kilkadziesiąt publikacji na ten temat: strona wikipedia zawiera wiele odnośników.