Abstrakcja Remote Procedure Call ukrywa złożoność komunikacji między klientem a serwerem w aplikacji rozproszonej.

Celem tego zadania jest sprawienie, by wyglądało to tak blisko, jak to tylko możliwe do wywoływała zwykłej funkcję we własnej przestrzeni procesów. Niestety jest to abstrakcja niedoskonała, ponieważ kod klienta musi radzić sobie z wieloma trybami awarii, które mogą wystąpić w systemie rozproszonym.

RPC składa się z trzech części. Biblioteka funkcji po stronie klienta definiująca interfejs aplikacja-program, protokół serializacji/komunikacji i biblioteka obsługi oraz zestaw funkcji obsługi po stronie serwera.

Funkcje po stronie klienta po prostu porządkują (marshaling) swoje argumenty (patrz IDL) i przekazują je do warstwy komunikacyjnej, która przesyła argumenty do serwera i rozpakowuje wynik zwrócony przez serwer.

Oryginalny mechanizm RPC, obecnie nazywany ONC-RPC, został opracowany przez Sun Microsystems w ramach ich projektu Network File System (NFS) w celu utworzenia współdzielenia plików. NFS został częściowo zaimplementowany w jądrze, więc wolumen NFS można było zamontować tak, jakby był zwykłym systemem plików.

Mając to za inspirację, Twoim zadaniem jest zaimplementowanie pomniejszonej wersji sieciowego systemu plików w przestrzeni użytkownika. Zaimplementuj niezbędne wywołania systemowe do wymiany danych. Nie używaj innych narzędzi RPC. Metody, które co najmniej powinny być zaimplementowane w bibliotece to:

    File *open(const char *pathname, char *mode);

    ssize_t read(void *buf, size_t count);
    ssize_t write(void *buf, size_t count);
    off_t lseek(off_t offset, int whence);

    int chmod(const char *pathname, mode_t mode);
    int unlink(const char *pathname);
    int rename(const char *oldpath, const char *newpath);

Zasymuluj uwierzytelnianie (jesteś tym, za kogo się podajesz) i autoryzację (masz uprawnienia do robienia tego, o co prosisz) za pomocą 64-bitowego numeru jako tokena „auth”. Normalnie byłoby to zapewniane przez usługę uwierzytelniającą lub przez inny odpowiedni mechanizm, ale możesz użyć getrandom(2) do wygenerowania liczby losowej.

Użyj UDP do wymiany informacji. Ponieważ protokół UDP jest „niewiarygodny”, każde żądanie skierowane do serwera powinno zawierać token uwierzytelniania i drugi 64-bitowy losowo wygenerowany numer sekwencyjny. Każda odpowiedź z serwera powinna zawierać numer sekwencyjny wskazujący, na które żądanie klienta odpowiada serwer.

Klient powinien utrzymywać limit czasu (timeout) dla każdego żądania skierowanego do serwera. Biblioteka klienta może ponowić próbę po upływie limitu czasu. Jeśli drugie żądanie nie powiedzie się lub nie zwróci żadnego wyniku, klient powinien zgłosić niepowodzenie (poprzez zwracaną wartość) do aplikacji.

Aby uniknąć radzenia sobie ze współbieżnością, możesz założyć, że serwer obsługuje tylko jedno żądanie na raz. Współbieżne żądania zostaną po prostu umieszczone w kolejce nasłuchującego gniazda.

To zadanie proszę raczej wykonać w C lub C++.

W tym zadaniu celem jest napisanie prostej aplikacji konsolowej z wykorzystaniem istniejącej implementacji RPC, a dokładnie wykorzystanie gRPC do napisania prostej rozmowy przez sieć (chat-server).

Jako protobuf (Protocol Buffers) wykorzystać można poniższy szkielet:

message Empty {}

message Note {
    string name = 1;
    string message = 2;
}

service ChatServer {
    rpc ChatStream (Empty) returns (stream Note);
    rpc SendNote (Note) returns (Empty);
}

lub przykładowe inne z dostępnych tutoriali np. tutaj.

Napisz aplikacje z wykorzystaniem języka Python.

• (5pt) Odwrotny indeks (Inverted Index)
• (5pt) Mnożenie macierzy przez wektor
• (5pt) Mnożenie macierzy przez macierz
• (15pt) System do rekomendacji np. filmów. Opis problemu oraz rozwiązania z wykorzystaniem MapReduce pdf lub pdf

(30pt) W tym zadaniu zaprojektuj i zaimplementuj odporną na błędy usługę klucz/wartość (service key/value), korzystając z replikacji primary/backup (leader/followers). Aby upewnić się, że wszystkie strony (klienci i serwery) zgadzają się, który serwer jest podstawowym, a który zapasowym, wprowadzimy rodzaj serwera głównego, zwanego master. Master monitoruje, czy każdy dostępny serwer jest aktywny, czy nieaktywny (wysyłając heartbeat). Jeśli bieżący primary lub backup ulegnie awarii, master wybiera serwer, który ma go zastąpić. Klient komunikuje się z masterem, aby znaleźć bieżący primary. Serwery współpracują z masterem, aby w danym momencie aktywny był co najwyżej jeden serwer podstawowy.

Zaimplementowana usługa klucz/wartość umożliwia też wymianę uszkodzonych serwerów. Jeśli primary ulegnie awarii, master będzie promować backup jako primary. Jeśli backup ulegnie awarii, albo zostanie promowany na primary, to master będzie starał się zwerbować nowy serwer jako backup (jeśli w ogóle są dostępne bezczynne (idle) serwery) i primary wyśle pełną bazę danych do nowego backupa.

Tutaj formalnie (wysyłanie może być długie dla dużych baz danych) po wysłaniu aktualnego snapshot'a powinien wysłać kolejne operacje na bazie, aby upewnić się, że baza danych backupu pozostanie identyczna z bazą danych primary, która oczywiście dalej działa.

Primary musi wysłać nie tylko operacje 'zapisu', ale także 'odczytu' do backupa (jeśli są takie) i musi poczekać, aż backup odpowie przed wysłaniem odpowiedzi do klienta. Pomaga to zapobiec działaniu dwóch serwerów jako primary ("split-brain"). Przykład: S1 jest primary, a S2 to backup. Master decyduje (niepoprawnie), że S1 nie żyje i promuje S2 jako primary. Jeśli klient uważa, że S1 jest nadal primary i wyśle do niego operację, S1 przekazuje operację do S2, a S2 odpowie z błędem wskazującym, że nie jest już backup. S1 może następnie zwrócić błąd do klienta, wskazując, że S1 może już nie być primary. Klient może następnie zapytać mastera o prawidłowe primary (S2) i wysłać do niego operację.

Schemat przedstawiony w tym zadaniu nie określa pełnego protokołu; musisz dopracować/zmodyfikować/zmienić protokół. Protokół ma podobieństwa z zestawem replik MongoDB (chociaż MongoDB wybiera lidera w wyborach podobnych do Paxos). Wzoruj się też wykładem: wybór lidera, replikacja, większość (majority), kworum, itp.

Zaimplementuj usługę klucz/wartość z master/primary/backup oraz przykładowego klienta jako osobne programy (procesy), które komunikują się przez sieć (standardowe sockety z tcp lub udp), tutaj można wykorzystać RPC.

(20pt) Kiedy wysyłamy zdjęcie na Instagram lub wykonujemy transakcję w aplikacji bankowej, system backendowy przypisuje unikalny identyfikator (UID) do nowo utworzonego obiektu. Ten identyfikator jest zwykle używany jako klucz podstawowy w niektórych tabelach baz danych i może służyć do wydajnego pobierania obiektu.

Oczywiście mamy automatyczną inkrementację kluczy głównych w SQL. Problem tej funkcji jest jednak taki, że działa tylko na jednej bazie danych, ponieważ wiąże się z blokowaniem, a zatem nie jest skalowalny. A jeśli potrzebuję milionów UID-ów na sekundę dla aplikacji takich jak Slack, Youtube, ... ? Celem tego zadania jest zaprojektowanie generatora UID na dużą skalę.

Jeśli chodzi o generowanie UID, konieczne jest rozróżnienie dwóch typów UID. Po pierwsze, istnieje losowy UID bez oczywistych znaczeń semantycznych. Po drugie, istnieje sekwencyjny UID który wprowadza nam pewien porządek.

W tym zadaniu skupiamy się na sekwencyjnych UID-ach, ponieważ większość aplikacji nie rozdaje UID-ów ludziom. Poniżej znajdują się podstawowe wymagania funkcjonalne systemu:

• Możliwość generowania dziesięciu milionów sekwencyjnych identyfikatorów UID na sekundę
• UID muszą zachowywać pewien poziom (nie musi być dokładnie co jeden!) informacji o porządku
• możliwość dostosowania szybkości wytwarzania UIDów w oparciu o zapotrzebowanie
• system powinien być skalowalny i wysoce dostępny

Przykład: Uruchamiamy usługę dozorcy i nadzorcę klastra (supervisor). Nadzorca klastra domyślnie tworzy N pracowników (workers). Tworzony pracownik rejestruje się u dozorcy i uzyskuje unikalny identyfikator pracownika (proste liczby całkowite). Każdy pracownik odpowiada dozorcy. Gdy pracownik ulegnie awarii, jego węzeł zostanie usunięty, a dozorca powiadomi nadzorcę. Jak zatem rozdać pracę pracownikom? Przykładowe rozdzielenie pracy

      +-----------+--------------+-----------+----------+------------------+
      | timestamp | ID pracownik | ID wątku  | ID ...   | lokalny licznik  |
      +-----------+--------------+-----------+----------+------------------+
          a-bitow     b-bitow       c-bitow     d-bitow       e-bitow

      gdzie np. a+b+c+d+e=128-bits

Podsumowując należy zaprojektować i zaimplementować algorytm do rozproszonego uporządkowanego generowania UIDów.

• tworzenie węzłów, ich połączenie oraz komunikację za pomocą komunikatów
• zapewnia interfejs do implementacji własnych algorytmów
• udostępnia (prosty) graficzny interfejs użytkownika do obsługi debugowania algorytmów
• udostępnia dziennik i regulowaną prędkość komunikacji (patrz np. Raft wizualizacja)
• ...

• (5pt) Dijkstra BFS (wykład)
• (5pt) Bellman-Ford BFS (wykład)
• (5pt) Ustalenie globalnego stanu systemu, czyli algorytm Chandy-Lamport (wykład)
• (5pt) Wybór lidera na pierścieniu (wykład)
• (5pt) Prosty Paxos (wykład)
• (5pt) Zrandomizowany algorytm konsensusu Ben-Or (wykład)
• (5pt) Algorytm Króla w modelu bizantyjskim (wykład)