Szukasz rozproszonego wzoru blokowania

10

Muszę wymyślić niestandardowy mechanizm \ wzorca blokowania obiektów rekurencyjnych dla systemu rozproszonego w języku C #. Zasadniczo mam system z wieloma węzłami. Każdy węzeł ma wyłączne uprawnienia do zapisu dla n -liczba elementów stanu. Ten sam stan jest również dostępny w formie tylko do odczytu w co najmniej jednym innym węźle. Niektóre zapisy / aktualizacje muszą być atomowe we wszystkich węzłach, podczas gdy inne aktualizacje w końcu staną się spójne poprzez procesy replikacji w tle, kolejki itp.

W przypadku aktualizacji atomowych szukam wzoru lub próbek, które skutecznie pozwalają mi oznaczyć obiekt jako zablokowany dla zapisów, które mogę następnie rozpowszechniać, zatwierdzać, wycofywać itp. Ponieważ system ma wysoki poziom współbieżności, I Zakładam, że będę musiał układać blokady, które przekroczą limit czasu lub zostaną rozwinięte po zwolnieniu blokad.

Transakcja lub wiadomości nie są przedmiotem tego pytania, ale przedstawiłem je dla dodatkowego kontekstu. Powiedziawszy to, nie krępuj się artykułować, jakie wiadomości według Ciebie będą potrzebne, jeśli chcesz.

Oto niejasna próbka tego, co sobie wyobrażałem, chociaż jestem otwarty na wszelkie nowe pomysły oprócz wdrażania zupełnie nowych produktów

thing.AquireLock(LockLevel.Write);

//Do work

thing.ReleaseLock();

Myślałem o użyciu metod rozszerzenia, które mogą wyglądać mniej więcej tak

public static void AquireLock(this IThing instance, TupleLockLevel lockLevel)
{ 
    //TODO: Add aquisition wait, retry, recursion count, timeout support, etc...  
    //TODO: Disallow read lock requests if the 'thing' is already write locked
    //TODO: Throw exception when aquisition fails
    instance.Lock = lockLevel;
}

public static void ReleaseLock(this IThing instance)
{
    instance.Lock = TupleLockLevel.None;
}

Aby wyjaśnić kilka szczegółów ...

  • Cała komunikacja odbywa się za pomocą protokołu TCP / IP za pomocą binarnego protokołu żądania / odpowiedzi
  • Nie ma technologii pośrednich, takich jak kolejki lub bazy danych
  • Nie ma centralnego węzła głównego. W takim przypadku mechanizm blokowania jest definiowany przez inicjatora blokady i partnera, który uszanuje żądanie z pewną formą przerwy w zarządzaniu jego zachowaniem

Czy ktoś ma jakieś sugestie?

JoeGeeky
źródło
Zamki są zazwyczaj standardową funkcją w większości systemów. Myślę, że jest tam również dla C #. (Wynik wyszukiwania Google: albahari.com/threading/part2.aspx ) Czy starasz się osiągnąć coś więcej niż podstawowy Mutex lub semafory?
Dipan Mehta,
2
@DipanMehta Przepraszam, powinienem był zająć się tym jaśniej. Wspomniane węzły to maszyny w sieci. Rozumiem Mutex i Semaphores, że są to zamki dla całej maszyny ( np. Międzyprocesowe ), a nie zamki, które mogą rozciągać się między maszynami w sieci.
JoeGeeky,
@JoeGeeky Twoje pytanie jest tutaj na temat i prawdopodobnie byłoby zbyt teoretyczne dla przepełnienia stosu . Jeśli chcesz ponownie o to zapytać, możesz, ale będziesz potrzebować bardziej skoncentrowanego na kodzie frazowania.
Adam Lear

Odpowiedzi:

4

Dziękuję za wyjaśnienia.

W takim przypadku zaleciłbym użycie modelu publikowania / subskrybowania. Rozproszony protokół blokowania Google Chubby (implementacja Paxos )

Nigdy nie korzystałem z Paxos (lub Chubby), ale wydaje się, że tutaj jest implementacja typu open source .

Jeśli to nie zadziała, możesz zaimplementować własną wersję Paxos, używając na przykład jednego ze zwykłych podejrzanych pod względem bibliotek wiadomości: biblioteki kolejki zero komunikatów , RabbitMQ lub ActiveMQ .


Poprzednia odpowiedź:

Większość sugestii dotyczących SO ( [A] , [B] ) dotyczy korzystania z kolejki komunikatów w celu uzyskania blokady między urządzeniami.

Twoja AcquireLockmetoda wypchnie coś identyfikującego obiekt blokady do kolejki, sprawdzając wcześniejsze wystąpienia blokad przed sukcesem. Twoja ReleaseLockmetoda usunie obiekt blokady z kolejki.

SO użytkownik Atlantis sugeruje, w tym poście , postu Jeff kluczyka dla niektórych szczegółach.

Peter K.
źródło
Dzięki, ale te rozwiązania nie byłyby odpowiednie, ponieważ nie mam centralnego wzorca, bazy danych ani kolejki. Zaktualizowałem pytanie o dodatkowe informacje, aby wyjaśnić niektóre z tych szczegółów.
JoeGeeky,
Nie będę mógł używać tych produktów bezpośrednio, ponieważ istnieje już dobrze zdefiniowany protokół, którego muszę używać do całej komunikacji między węzłami, ale Chubby i Paxos mogą mieć dobrze zdefiniowane wzorce, z których mogę się uczyć. Spojrzę na to.
JoeGeeky
@JoeGeeky Tak, łącze Paxos ma schematy sekwencji, które mogą pozwolić na jego wdrożenie przy użyciu preferowanego łącza komunikacyjnego.
Peter K.,
Chociaż nie jest to bezpośrednia odpowiedź, przeczytanie wszystkich rzeczy Chubby i Paxos pomogło mi zdefiniować własne rozwiązanie. Nie korzystałem z tych narzędzi, ale byłem w stanie zdefiniować rozsądny wzorzec na podstawie niektórych ich koncepcji. Dzięki.
JoeGeeky
@JoeGeeky: Miło było usłyszeć, że to była jakaś pomoc. Dzięki za kleszcza.
Peter K.
4

Wydaje mi się, że masz tutaj kilka mieszanych technologii:

  • komunikacja (na której zasadniczo polegasz jako w 100% niezawodny ... co może być śmiertelne)

  • blokowanie / wzajemne wykluczanie

  • limity czasu (w jakim celu)?

Słowo ostrzeżenia: limity czasu w systemach rozproszonych mogą być obarczone niebezpieczeństwem i trudnością. Jeśli są używane, muszą być ustawiane i używane bardzo ostrożnie, ponieważ masowe przekroczenie limitu czasu nie rozwiązuje problemu, tylko opóźnia katastrofę. (Jeśli chcesz zobaczyć, jak należy stosować limity czasu , przeczytaj i zrozum dokumentację protokołu komunikacji HDLC. To dobry przykład odpowiedniego i sprytnego użycia w połączeniu z inteligentnym systemem kodowania bitów, który umożliwia wykrywanie takich rzeczy, jak linia IDLE) .

Przez pewien czas pracowałem w rozproszonych wieloprocesorowych systemach połączonych za pomocą łączy komunikacyjnych (nie TCP, coś innego). Jedną z rzeczy, których się nauczyłem, było to, że z grubsza uogólniam, istnieje kilka niebezpiecznych miejsc, w których można zaprogramować wiele programów:

  • poleganie na kolejkach zwykle kończy się łzami (jeśli kolejka się zapełni, masz kłopoty. JEŚLI możesz obliczyć rozmiar kolejki, która nigdy się nie zapełni, w takim przypadku prawdopodobnie możesz użyć rozwiązania bez kolejki)

  • poleganie na blokowaniu jest bolesne, spróbuj pomyśleć, czy istnieje inny sposób (jeśli musisz użyć blokowania, spójrz do literatury, rozproszone blokowanie wieloprocesorowe było przedmiotem wielu artykułów acedemicznych w ciągu ostatnich 2-3 dekad)

Muszę kontynuować przy użyciu blokady, a następnie:

Przyjmuję, że przekroczenia limitu czasu będą wykorzystywane wyłącznie w celu odzyskania ostateczności - tj. W celu wykrycia awarii podstawowego systemu łączności. Zakładam dalej, że twój system komunikacji TCP / IP ma wysoką przepustowość i może być traktowany jako małe opóźnienie (najlepiej zero, ale nigdy tak się nie dzieje).

Sugerowałbym, że każdy węzeł ma listę połączeń z innymi węzłami, z którymi może się łączyć. (Węzły nie przejmowałyby się, skąd pochodzi połączenie.) Populacja tabel, z którymi węzły mogą się łączyć, pozostawia się jako osobną rzecz do uporządkowania, nie powiedziałeś, czy byłoby to ustawione statycznie, czy inaczej. Dogodnie ignorowane są również takie kwestie, jak przydzielanie numerów portów IP, w których połączenia przychodzą do węzła - mogą istnieć dobre powody, aby akceptować żądania tylko na jednym porcie lub na wielu portach. Należy to dokładnie rozważyć. Czynniki te obejmują niejawne kolejkowanie, porządkowanie, wykorzystanie zasobów, typ systemu operacyjnego i możliwości.

Gdy węzły dowiedzą się, z kim się łączą, mogą wysłać do tego węzła żądanie blokady i muszą odebrać odpowiedź od blokady z tego zdalnego węzła. Możesz spakować te dwie operacje do opakowania, aby wyglądało atomowo. Skutkuje to tym, że węzły chcące uzyskać blokadę wykonają połączenie w rodzaju:

if (get_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

/* Lock is now acquired - do work here */

if (release_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

wywołania get_lock i release_lock powinny wyglądać mniej więcej tak (w zasadzie):

send_to_remote_node(lock_request)
get_from_remote_node_or_timeout(lock_reply, time)
if (result was timeout) then
  return timeout
else
  return ok

Będziesz musiał bardzo uważać z rozproszonym systemem blokowania, aby jednostki pracy wykonane podczas blokowania były małe i szybkie, ponieważ będziesz mieć wiele zdalnych węzłów potencjalnie czekających na uzyskanie blokady. Jest to skutecznie system wieloprocesorowy / komunikacyjny typu stop-and-wait, który jest solidny, ale nie ma najwyższej możliwej wydajności.

Sugeruje się, aby przyjąć zupełnie inne podejście. Czy można użyć zdalnego wywołania procedury, w którym każde wywołanie RPC zawiera pakiet informacji, które może obsłużyć odbiorca i które eliminują potrzebę blokad?


Po ponownym przeczytaniu pytania wygląda na to, że tak naprawdę nie chcesz zajmować się komunikacją, po prostu chcesz rozwiązać problem z blokowaniem.

Moja odpowiedź może więc wydawać się nieco nie na temat, jednak uważam, że nie można rozwiązać problemu z blokowaniem bez prawidłowego umieszczenia pod nim części. Analogia: zbudowanie domu na złych fundamentach powoduje, że upada ... W końcu.

szybko
źródło
1
Semantyka przekroczenia limitu czasu w dużej mierze służy do radzenia sobie z węzłami, które znikają z sieci, lub do radzenia sobie z dużymi zaległościami w stosach blokowania ... To ograniczy czas spędzony zablokowany podczas oczekiwania na uzyskanie blokady i zapewni osobom proszącym o blokadę możliwość aby uruchomić inne procesy pośród nieoczekiwanych opóźnień, awarii itp. Dodatkowo zapobiegnie to zablokowaniu czegoś na zawsze w przypadku awarii. Doceniam wasze obawy, chociaż w tym momencie nie widzę żadnych alternatyw, biorąc pod uwagę, że w końcu coś zawiedzie
JoeGeeky
Mówiąc o niektórych innych komentarzach, nie używam kolejek per se (w sensie komunikacji asynchronicznej), chociaż spodziewam się, że blokady są nakładane i zwalniane na podstawie wzorca FIFO. Nie do końca pogodziłem się, jak to zadziała pod względem wymaganego wzorca żądania / odpowiedzi innego niż to, będzie musiał w jakiś sposób zablokować i być częścią większego uścisku dłoni. W tej chwili pracuję nad mechanizmem blokowania stosu w ramach jednego węzła, a następnie nad tym, jak będzie on działał w scenariuszu rozproszonym. Zrobię trochę więcej czytania, jak zasugerowałeś. Dzięki
JoeGeeky
@JoeGeeky - FIFO to kolejka. Uważaj na kolejki. Przemyśl tę stronę bardzo uważnie. Wygląda na to, że nie dostaniesz czegoś „z półki”, ale będziesz musiał dokładnie przemyśleć swój problem i rozwiązanie.
szybko_now
Rozumiem ... Próbowałem wyjaśnić różnicę między kolejką FIFO używaną w procesach asynchronicznych ( np. Jeden proces kolejkuje, a następnie drugi usuwa kolejkę ). W takim przypadku trzeba będzie zarządzać kolejnością, ale proces wchodzący do kolejki nie wyjdzie, dopóki (a) nie otrzymają blokady, (b) odmówią blokady lub (c) przekroczą limit czasu i opuszczą linię. Bardziej jak stanie w kolejce w bankomacie. Zachowuje się to jak wzorzec FIFO w przypadku sukcesu, ale procesy mogą pozostawać w porządku przed dotarciem na początek linii. Co do gotowych produktów? Nie, ale to nie jest nowy problem
JoeGeeky
0

Twoje pytanie można łatwo wdrożyć za pomocą rozproszonej pamięci podręcznej, takiej jak NCache. Potrzebny jest pesymistyczny mechanizm blokowania, w którym można uzyskać zamek za pomocą obiektu. Następnie wykonaj swoje zadania i operacje, a następnie zwolnij blokadę, aby inne aplikacje mogły z niej korzystać później.

Spójrz na następujący kod;

Tutaj uzyskasz blokadę na określonym kluczu, a następnie wykonasz zadania (od jednej lub więcej operacji), a następnie wreszcie zwolnisz blokadę, gdy skończysz.

// Instance of the object used to lock and unlock cache items in NCache
LockHandle lockHandle = new LockHandle();

// Specify time span of 10 sec for which the item remains locked
// NCache will auto release the lock after 10 seconds.
TimeSpan lockSpan = new TimeSpan(0, 0, 10); 

try
{
    // If item fetch is successful, lockHandle object will be populated
    // The lockHandle object will be used to unlock the cache item
    // acquireLock should be true if you want to acquire to the lock.
    // If item does not exists, account will be null
    BankAccount account = cache.Get(key, lockSpan, 
    ref lockHandle, acquireLock) as BankAccount;
    // Lock acquired otherwise it will throw LockingException exception

    if(account != null && account.IsActive)
    {
        // Withdraw money or Deposit
        account.Balance += withdrawAmount;
        // account.Balance -= depositAmount;

        // Insert the data in the cache and release the lock simultaneously 
        // LockHandle initially used to lock the item must be provided
        // releaseLock should be true to release the lock, otherwise false
        cache.Insert("Key", account, lockHandle, releaseLock); 
        //For your case you should use cache.Unlock("Key", lockHandle);
    }
    else
    {
        // Either does not exist or unable to cast
        // Explicitly release the lock in case of errors
        cache.Unlock("Key", lockHandle);
    } 
}
catch(LockingException lockException)
{
    // Lock couldn't be acquired
    // Wait and try again
}

Zaczerpnięte z linku: http://blogs.alachisoft.com/ncache/distribut-locking/

Basit Anwer
źródło