Autor Wątek: Optymalna struktura sieciowego serwera gry  (Przeczytany 4688 razy)

Offline Fenel

  • Użytkownik

# Sierpień 19, 2014, 11:33:02
Proste, a zarazem skomplikowane pytanie, które podejście jest Waszym zdaniem lepsze:

1. Na jednym wątku trzymam listener i czekam na połączenia, dla każdego nowego połączenia odpalam nowy wątek i w nim używając blokujących socketów czekam na pakiety od clienta, do ich obsługi odwołuję się do głównej klasy zarządzającej serwerem Game (za pomocą wskaźnika przekazanego podczas tworzenia wątku), mam jeszcze jeden dodatkowy wątek w którym działa logika servera (AI aktorów itd...). Lecz tutaj zaczynają pojawiać się problemy, oczywiście chodzi o synchronizację wątków. To podejście mam zastosowane obecnie, lecz server potrafi się wysypać przy jakimś evencie powodującym bardziej złożone zachowanie (śmierć gracza w otoczeniu innych graczy i wielu potworów, powoduje podział doświadczenia algorytmem, gdzie tutaj wątki potrafią się rozjechać, odwołać się do usuniętego obiektu mimo wcześniejszego sprawdzenia, czy wskaźnik dalej na niego wskazuje). Czy jeżeli skrupulatnie wstawię w kod mutexy i postaram się chronić obiekty, które nie są safe-threaded to ugram stabilność?
2. Inną ideą jest wrzucenie absolutnie wszystkiego w jeden wątek, jednak po szybkim przerobieniu kodu zauważyłem, że obsługa każdego pojedynczego gracza jest za wolna (nie dziwię się, skoro każdy socket musi czekać na odczytanie w selectorze, a czasami czekanie się przedłuża do kilkunastu ms, np. gdy trzeba wykonać bardziej skomplikowany pathfinding, co powoduje już lagi). Jakieś pomysły, jak temu zaradzić?
3. Ostatni pomysł to podzielenie serwera jedynie na dwa wątki: jednym oczekuję na selectorze na pakiety od graczy i nasłuchuję listenerem, a w drugim obsługuję logikę servera (AI actorów itd...). Lecz tutaj też pojawia się potrzeba synchronizacji. Standardowo mutexy?

Konkludując sam się dziwię, że przez długi czas wszystko działało sprawnie bez żadnej synchronizacji wątków, nie wiem tylko, czy to dzięki back-endowi SFMLa czy szczęściu ;)

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 19, 2014, 13:43:58
Cytuj
1. Na jednym wątku trzymam listener i czekam na połączenia, dla każdego nowego połączenia odpalam nowy wątek...
W tym momencie przestałem czytać. Na bank to nie jest dobre podejście, bo jest spory narzut na przełączaniu wątków.

Cytuj
2. Inną ideą jest wrzucenie absolutnie wszystkiego w jeden wątek, jednak po szybkim przerobieniu kodu zauważyłem, że obsługa każdego pojedynczego gracza jest za wolna (nie dziwię się, skoro każdy socket musi czekać na odczytanie w selectorze, a czasami czekanie się przedłuża do kilkunastu ms, np. gdy trzeba wykonać bardziej skomplikowany pathfinding, co powoduje już lagi). Jakieś pomysły, jak temu zaradzić?
W ten sposób z tego co wiem działa Quake, a wywołanie select() powinno wychodzić natychmiast jeżeli któryś z wątków ma coś do zrobienia. Pamiętasz poza tym, że select() zwraca zbiory gniazd, więc po jednym select() możesz obsłużyć wszystko, co dotychczas czekało przed wywołaniem select() ponownie.

Podstawowym pytaniem jednak jest: skąd na serwerze wziął się u Ciebie pathfinding (który powinien być na kliencie) i czemu zajmuje kilkanaście ms.

Cytuj
3. Ostatni pomysł to podzielenie serwera jedynie na dwa wątki: jednym oczekuję na selectorze na pakiety od graczy i nasłuchuję listenerem, a w drugim obsługuję logikę servera (AI actorów itd...). Lecz tutaj też pojawia się potrzeba synchronizacji. Standardowo mutexy?
Mutexy są najprostszym, relatywnie wydajnym i najbardziej leniwym podejściem. Możesz się zainteresować też lockless programming i operacjamowymi atomowymi, jeżeli przy mutexach nadal będzie słabo, ale to wymaga już całkiem sporo kombinowania (dużo więcej, niż się na początek wydaje - sam się na tym sparzyłem).

Cytuj
Konkludując sam się dziwię, że przez długi czas wszystko działało sprawnie bez żadnej synchronizacji wątków, nie wiem tylko, czy to dzięki back-endowi SFMLa czy szczęściu ;)
Zależy co konkretnie robiłeś. Typy podstawowe, jeżeli są dobrze wyrównane (a domyślnie kompilator o to dba) na x86 mają pewne gwarancje atomowości zapisu i odczytu, więc nie trudno o kod wielowątkowy, który będzie poprawny bez jakichkolwiek innych mechanizmów synchronizacji.

volatile int tasks_to_do = 0;
volatile int tasks_done = 0;
volatile bool thread_exit = false;
volatile bool thread_exited = false;

void thread_function()
{
    while(!thread_exit)
    {
        while( tasks_done >= tasks_to_do ) Sleep(1);
        do_task( tasks_done++ );
    }
    thread_exited = true;
}

void do_some_tasks()
{
    start_thread( thread_function() );
    tasks_to_do += 3;
    do_something_else();
    tasks_to_do += 3;
    while( tasks_done < 2 ) Sleep(1);    // czekamy na skończenie pierwszych 2 zadań
    do_something_else();
    while( tasks_done < tasks_to_do ) Sleep(1);    // czekamy na skończenie wszystkich

    thread_exit = true;
    while( !thread_exited ) Sleep(1);
}
Jeżeli niczego nie przeoczyłem, taka konstrukcja powinna działać bez zarzutu.[/code]

Offline bies

  • Użytkownik

# Sierpień 19, 2014, 13:54:54
Jeżeli niczego nie przeoczyłem (...)
http://msdn.microsoft.com/en-us/library/12a04hfd.aspx -- tylko dla niektórych opcji MS VC++. Normanie używa się std::atomic<>.

Co do samego pytania: w miarę wydajnie i w miarę prosto jest zrobić wątek do odbierania i pulę wątków obsługującą odpowiedzi. Pula wątków dostaje zapytania z wątku odbierającego przez blokującą kolejkę (lock-free na start jest trudne). Pula wątków może mieć N wątków (optymalnie liczba rdzeni x doświadczalnie wyznaczony mnożnik). Należy przyjrzeć się danym używanym przez pulę wątków i zminimalizować blokowanie. To wystarczy.
« Ostatnia zmiana: Sierpień 19, 2014, 13:59:59 wysłana przez bies »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 19, 2014, 14:04:59
Cytuj
http://msdn.microsoft.com/en-us/library/12a04hfd.aspx -- tylko dla niektórych opcji MS VC++. Normanie używa się std::atomic<>.
W tym przypadku to konkretnie akurat nie ma znaczenia - jedyne czego wymagam tutaj od "volatile" to fakt, żeby prędzej czy później dana wartość trafiła pod adres w pamięci. Co do std::atomic<> to się zgodzę - tutaj używam założenia atomowości read/write na typach podstawowych, co jest słuszne dla x86, ale dla innych architektur już być nie musi.

Offline yarpen

  • Użytkownik

# Sierpień 19, 2014, 20:50:33
Jeżeli niczego nie przeoczyłem, taka konstrukcja powinna działać bez zarzutu.
To juz zalezy od tego, co robia do_task i do_something_else i czy operuja na tych samych danych. Jezeli np. do_something_else zapisuja cos z czego do_task ma pozniej korzystac, to nie ma gwarancji, ze watek w tle nie odczyta starej wartosci (odczyta nowe tasks_to_do jako pierwsze). Musialbys dodac bariery.

// korekta tagów -Xirdus
« Ostatnia zmiana: Sierpień 19, 2014, 20:53:11 wysłana przez Xirdus »

Offline Fenel

  • Użytkownik

# Sierpień 19, 2014, 23:41:22
Na ten moment już nie na szybko przerobię kod na używanie selectora i obsługę AI w jednym wątku i podzielę się rezultatami (teraz zauważyłem, że spiesząc się wczoraj w nocy obsługę client'ów zrobiłem na pętli i spradzaniu, czy socket jest gotów to odczytu, pewnie powodowało to samo w sobie pewien narzut...)

Co do pathfindingu - chodzi mi o sytuację, gdzie któryś gracz teleportuje się w inne miejsce na mapie lub zmienia piętro, czym wywołuje funkcję szukania drogi dla kilku actorów, będących w zasięgu wzroku czyli +- obszar około 25 na 25 pól (wplotłem tu odpowiedź o wyszukiwaniu drogi na serwerze ;) ). Z tymi kilkunastoma ms przesadziłem, na ten moment będzie to kilka ms.

Wąskim gardłem polegania na jednym wątku w moim przekonaniu może być własnie opisany wyżej moment, gdzie serwer musi wykonać więcej czynności w jednym obiegu niż zwykle. Na ten moment co 100ms puszczam iterację w pętli po wszystkich actorach i wykonuję co mają do wykonania - może tutaj coś mógłbym ugrać? Może iterować po części, obsłużyć selector, iterować kolejną część? Kwestia tego, ile na tym ugram, bo dojdzie problem synchronizacji akcji graczy z tym, co się dzieje z actorami.

Offline yarpen

  • Użytkownik

  • +1
# Sierpień 19, 2014, 23:57:15
Powinienes rozbic to na kilka warstw. Sieciowa powinna jedynie odbierac dane i wrzucac je na jakas kolejke, niekoniecznie od razu obslugiwac. Kolejka moze byc obslugiwana albo przez glowny watek albo w ogole jakis inny. Obsluga konkretnych eventow to jeszcze inna sprawa, path-finding idealnie nadaje sie do puszczenia w tle.

Offline albireo

  • Użytkownik

# Sierpień 20, 2014, 00:00:14
To juz zalezy od tego, co robia do_task i do_something_else i czy operuja na tych samych danych. Jezeli np. do_something_else zapisuja cos z czego do_task ma pozniej korzystac, to nie ma gwarancji, ze watek w tle nie odczyta starej wartosci (odczyta nowe tasks_to_do jako pierwsze). Musialbys dodac bariery.
Jawne bariery byłby potrzebne tylko jeśli chciałoby się to uruchomić na czymś innym niż x86.

Offline Fenel

  • Użytkownik

# Sierpień 20, 2014, 00:18:10
Powinienes rozbic to na kilka warstw. Sieciowa powinna jedynie odbierac dane i wrzucac je na jakas kolejke, niekoniecznie od razu obslugiwac. Kolejka moze byc obslugiwana albo przez glowny watek albo w ogole jakis inny. Obsluga konkretnych eventow to jeszcze inna sprawa, path-finding idealnie nadaje sie do puszczenia w tle.
Dobrze mówisz, nie mam podziału na warstwy, część kodu odpowiedzialną za obsługę pakietów napisałem kilka lat temu i nic w niej nie zmieniałem oprócz poprawek by działała na coraz to nowszych rewizjach SFML, a przez te 3-4 lata nabrało się nowych umiejętności. Na obecnym etapie już coś w tym rodzaju muszę zaimplementować bo powoli zbliżam się do posiadania wszystkich funkcjonalności które zakładałem by ukończyć pierwszą wersję...

Jawne bariery byłby potrzebne tylko jeśli chciałoby się to uruchomić na czymś innym niż x86.
Myślałem nad postawieniem serwera na ARM, ale mija się to z celem gdy do testów mam starego, wg. internetu mającego kilka WAT tdp Pentiuma 3, który teraz wytrzymuje i powinien także z dodanymi kolejnymi funkcjami w serwerze wytrzymać kilkunastu clientów (zapomniałem o terminalu HP z AMD Geode, który bierze znikome ilości prądu a wytrzymuje trochę więcej od powyższego Pentiuma), a na późniejsze czasy nie widzę problemu w wykupieniu VPS'a lub na początku, by nie bawić się z kompilacjąna linuxie i jego konfiguracją odpalić na laptopie z Brazosem na domowym łączu (30/6 Mbps, brak innych użytkowników przez większość czasu).
« Ostatnia zmiana: Sierpień 20, 2014, 00:21:54 wysłana przez Fenel »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 20, 2014, 09:28:43
Cytuj
Co do pathfindingu - chodzi mi o sytuację, gdzie któryś gracz teleportuje się w inne miejsce na mapie lub zmienia piętro, czym wywołuje funkcję szukania drogi dla kilku actorów, będących w zasięgu wzroku czyli +- obszar około 25 na 25 pól (wplotłem tu odpowiedź o wyszukiwaniu drogi na serwerze ;) ). Z tymi kilkunastoma ms przesadziłem, na ten moment będzie to kilka ms.
Pathfinding 25x25 pól to powinien zajmować kilka mikrosekund, a nie milisekund. Poza tym robiąc pathfinding od gracza do wszystkich AI możesz wyznaczyć ścieżki dla wszystkich AI za jednym zamachem.

Cytuj
Na ten moment co 100ms puszczam iterację w pętli po wszystkich actorach i wykonuję co mają do wykonania - może tutaj coś mógłbym ugrać? Może iterować po części, obsłużyć selector, iterować kolejną część? Kwestia tego, ile na tym ugram, bo dojdzie problem synchronizacji akcji graczy z tym, co się dzieje z actorami.
A czy wszyscy aktorzy muszą robić wszystko w jednym momencie? Bo jak ich porozrzucasz, to nie będziesz miał "kupy" obliczeń co 100ms, tylko mniej więcej stałą ilość.

Pozostaje jeszcze kwestia wydajności samej logiki aktorów - tutaj naprawdę też mi ciężko wyobrazić sobie coś, co by wymagało więcej niż kilku mikrosekund na aktora (albo nawet na wszystkich) przy dobrze napisanym kodzie.

Cytuj
Powinienes rozbic to na kilka warstw. Sieciowa powinna jedynie odbierac dane i wrzucac je na jakas kolejke, niekoniecznie od razu obslugiwac. Kolejka moze byc obslugiwana albo przez glowny watek albo w ogole jakis inny. Obsluga konkretnych eventow to jeszcze inna sprawa, path-finding idealnie nadaje sie do puszczenia w tle.
Taak... uniwersalny sposób rozwiązania wszelkich złożonych problemów: rozbić na warstwy i połączyć kolejkami. W efekcie chyba bezpowrotnie minął nam czas gdy gry były mega responsywne i dynamiczne za czasów Atari, C64 i Amigi, bo teraz wszędzie mamy bufory i kolejki. Teraz nawet jak podłączy się stare Atari 2600 do nowego telewizora, to dostaje się latency gratis (jednoczesne podłączenie do "nowego" i "starego" TV daje nausznie wyczuwalne opóźnienie dźwięku - słychać podwójnie). Na obecnych platformach jest jeszcze gorzej, bo API graficzne mogą zbuforować do 3 klatek wprzód zanim je wyślą do GPU.

Ech, taki mały rant mi wyszedł, ale i tak polecam odgrzebać Atari czy C64 i podłączyć do jakiegoś starego TV żeby przypomnieć sobie jak wygląda gra działająca w 50 FPS bez gubienia klatek i natychmiastową reakcją na user input. To się po prostu czuje. :)

Cytuj
path-finding idealnie nadaje sie do puszczenia w tle.
Nie pathfinding 25x25 pól. :) Taki bez większego wysiłku zrobisz dużo szybciej na miejscu i w dodatku zaoszczędzisz sobie 2 thread switche.

Offline bies

  • Użytkownik

# Sierpień 20, 2014, 10:09:42
Jawne bariery byłby potrzebne tylko jeśli chciałoby się to uruchomić na czymś innym niż x86.
Tak by się mogło wydawać bo odczyt i zapis inta na x86 jest atomowy. Ale to nie wszystko co robisz, np. fetch-and-add już atomowy nie jest. Popatrz np. tutaj: https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/arch/x86/include/asm/atomic.h?id=refs/tags/v3.16.1 (LOCK_PREFIX to z grubsza asm lock).

Offline albireo

  • Użytkownik

# Sierpień 20, 2014, 10:24:40
Tak by się mogło wydawać bo odczyt i zapis inta na x86 jest atomowy. Ale to nie wszystko co robisz, np. fetch-and-add już atomowy nie jest. Popatrz np. tutaj: https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/arch/x86/include/asm/atomic.h?id=refs/tags/v3.16.1 (LOCK_PREFIX to z grubsza asm lock).
Zakładając, że tylko jeden wątek modyfikuje to przykładowe tasks_to_do, to to czy fetch-and-add jest atomowe czy nie, nie ma znaczenia, wystarczy, że zapis inta jest atomowy i fakt, że x86 ma gwarancje dotyczące kolejności odczytu i zapisu do pamięci (dlatego nie potrzeba barier).

Offline bies

  • Użytkownik

# Sierpień 20, 2014, 10:37:09
Zakładając, że tylko jeden wątek modyfikuje to przykładowe tasks_to_do, to to czy fetch-and-add jest atomowe czy nie, nie ma znaczenia, wystarczy, że zapis inta jest atomowy i fakt, że x86 ma gwarancje dotyczące kolejności odczytu i zapisu do pamięci (dlatego nie potrzeba barier).
Tak, jeśli tylko jeden wątek pisze nie ma problemu. Ale jeśli chciałoby się uruchomić dwa (czyli w powyższym przykładzie łącznie trzy wątki) które robią task_done++ to już gwarancji nie ma.

Offline lethern

  • Użytkownik

# Sierpień 20, 2014, 12:08:02
Taak... uniwersalny sposób rozwiązania wszelkich złożonych problemów: rozbić na warstwy i połączyć kolejkami. W efekcie chyba bezpowrotnie minął nam czas gdy gry były mega responsywne i dynamiczne
No, bez przesady.. doom3 też miał tak jakby kolejkę między "frontend i backend" silnikiem, nie? ;p No i, da się taką kolejkę zrobić bez "blokowania i innych drogich multithread rzeczy"

Offline Fenel

  • Użytkownik

# Sierpień 20, 2014, 12:37:51
Zaimplementowałem porządnie socket selector i wszystko działa jak powinno na jednym wątku. Tyle w kwestii raportu z pola walki, następne pytania ku wzbogaceniu dyskusji na pewno prędzej czy później jeszcze zadam.

Dzięki za odpowiedzi.