[alg] Multi-threading in server applicaties

[Radiant]

Ik ben bezig met een serverapplicatie voor een bestaand spel. Mede doordat ik nu thuis een SMP systeempje heb en door de opkomst van dual core processoren, en omdat het me gewoon interesseert, zou ik graag eens multi-threading gebruiken in mijn applicatie. Ik ben er echter nog niet zeker van hoe.
Clients kunnen connecten naar de server en wisselen tussen bepaalde maps. Alles wordt nu gedaan in één grote event loop die sockets poll't, kijkt of er timers moeten runnen en een aantal andere zaken. Nu is het zo dat dit in mijn test omgeving met max misschien 3 clients nog wel prima gaat. Ik ben echter bang, omdat er nog wel eens heel veel clients tegelijk geconnect kunnen zijn, dat de performance en responsive-heid (nederlands? ) erg achteruit kan gaan, vooral omdat je soms gewoon moet wachten op database/socket acties, system calls e.d.

Nou heb ik zelf al een aantal opties bedacht waar ik threads voor zou kunnen gebruiken:

• Één thread voor elke client. Het grote nadeel hiervan vind ik dat je met veel users online heel veel threads kan hebben lopen. Dit lijkt me dus niet zo'n goed idee. Ik wil ervanuit gaan dat er een onbeperkt aantal users geconnect kunnen zijn, ookal zal dit in de praktijk vast niet mogelijk zijn.
• Socket polling in 1 thread, en AI/Timers in een ander. Hierbij krijg ik het idee dat het vaak kan voorkomen dat 1 thread heel erg veel werk te doen heeft en de ander praktisch uit z'n neus zit te vreten. Ik zou dit graag wat meer balanceren.
• Elke map op 1 thread draaien. Zou wellicht een goeie optie zijn, alhoewel je dan ook weer krijgt dat maps met veel users erop veel meer cpu trekken dan maps die leeg zijn. Ook omdat er soms vrij veel maps tegelijk geladen kunnen zijn zouden er hier ook vrij veel threads tegelijk moeten draaien.

Één probleem waar ik dus tegenaan loop is dat er, in mijn ogen, teveel threads kunnen draaien. Ik weet niet in hoeverre dit een probleem is, maar ik zie veel applicaties die gewoon maar max. 3 tot 5 threads gebruiken voor dit soort dingen.
Nog een probleem waar ik erg mee zit is locking. Denk even dit scenario in:
De client lijst is een vector. Deze moet gelocked worden voor elke thread die ermee wil gaan werken, omdat het natuurlijk niet ineens mag gebeuren dat andere threads er clients uit gaan deleten of clients die nog niet "klaar" zijn toevoegen. Nou kan dit natuurlijk prima, maar denk eens in dat als 1 thread de socket I/O afhandelt die natuurlijk de lijst moet locken, en dan pollen. Dat kan nogal eens lang duren, waarna thread 2 de client lijst lockt omdat hij een client actie gaat afhandelen (de client mag natuurlijk niet ineens gedelete worden tijdens dit proces). Hierop zitten thread 1 en de rest weer te wachten tot de lock wordt vrijgegeven. Hierbij krijg ik dus het gevoel dat ik eigenlijk gewoon een single threaded applicatie aan het schrijven ben, omdat de overige threads eigenlijk altijd wel op een lock zitten te wachten, omdat eigenlijk elke actie wel met een client te maken heeft.

Lang verhaal, maar hier zit ik dus eigenlijk mee Als jullie zo'n soortgelijke applicatie zouden moeten ontwikkelen, hoe zouden jullie dan multithreading implementeren?

[Verwijderd]

Veel threads is niet erg. Probleem is vaak dat threads niet worden verwijderd na gebruik (bijvoorbeeld doordat een gebruiker niet netjes uitlogd) en de communicatie tussen de threads. Bij een gameserver is dat laatste meestal niet zo'n heel groot probleem aangezien de verschillende clients met de server communiseren en niet rechtsstreeks met elkaar. Het niet afsluiten van threads leidt tot extreem groot geheugen gebruik en moet dus voorkomen worden bv door gebruik te maken van thread pools waarbij threads worden hergebruikt en het aantal threads redelijk beperkt blijft

Hoe je de threads verdeeld, per client, per map of per functie (AI vs sockets) hangt nogal sterk af van hoe schaalbaar het moet zijn en de belasting per taak. Aangezien je in principe oneindig veel users wilt ondersteunen (en waarschijnlijk ook oneindig veel per map) is het niet handig alle users in 1 map in 1 thread te stoppen. Al deze users moeten dan op 1 processor draaien. Worst case heb je dus alle gebruikers in 1 thread en je AI in een ander terwijl die AI erg weinig doet. Splitsen is in zo'n situatie meestal handiger. Weet je echter zeker dat je altijd n maps gaat krijgen met maximaal m gebruikers, dan is een splitsing per map zeker te overwegen.

Het locking probleem is een essentieel punt met threads. Doel is om objecten zo kort mogelijk gelocked te houden zodat de verschillende threads min of meer onafhankelijk kunnen functioneren. Maar zelfs als je relatief vaak moet locken kunnen threads nog erg handig zijn. Door onafhankelijke functies in onafhankelijke threads te stoppen kan het zijn dat de verschillende thread logischer en efficienter geprogrammeerd kunnen worden dan als alles in één grote loop geplaatst moet worden. Als je alles in één loop stopt raak je toch vaak het overzicht kwijt.
Het nadeel van threads is natuurlijk dat je niet precies kan bepalen wat wanneer gebeurd. Als in je engine erg veel acties afhankelijk zijn van voorgaande acties kan het gebruik van threads zelfs tegen je werken. Maar met onafhankelijke gebruikers die allen gelijktijdig acties kunnen ondernemen is een sequentieel systeem sowieso niet al te handig.

Tot slot een laatste voordeel van threads. Als je systeem groeit en te groot wordt voor 1 server is het relatief eenvoudig je systeem te splitsen in losse delen die op aparte servers kunnen draaien. Je kan dan bv je map threads op verschillende servers laten lopen terwijl je AI en centrale aanmelding op andere servers draaien.

Je begrijpt het al. Ik zou voor een server systeem altijd wel iets van threads implementeren.

[Alarmnummer]

Radiant schreef op zondag 10 juli 2005 @ 23:41:
Ik ben bezig met een serverapplicatie voor een bestaand spel. Mede doordat ik nu thuis een SMP systeempje heb en door de opkomst van dual core processoren, en omdat het me gewoon interesseert, zou ik graag eens multi-threading gebruiken in mijn applicatie. Ik ben er echter nog niet zeker van hoe.

Multithreading kan je ook uitstekend gebruiken als je een singlecore systeem hebt.

• Één thread voor elke client. Het grote nadeel hiervan vind ik dat je met veel users online heel veel threads kan hebben lopen. Dit lijkt me dus niet zo'n goed idee. Ik wil ervanuit gaan dat er een onbeperkt aantal users geconnect kunnen zijn, ookal zal dit in de praktijk vast niet mogelijk zijn.

In veel systemen is dit wel de standaard oplossing. Check maar eens de RMI-implementatie onder java. Er valt uiteraard iets voor te zeggen en er zijn ook andere oplossingen, maar dit werkt goed genoeg schijnbaar.

• Socket polling in 1 thread, en AI/Timers in een ander. Hierbij krijg ik het idee dat het vaak kan voorkomen dat 1 thread heel erg veel werk te doen heeft en de ander praktisch uit z'n neus zit te vreten. Ik zou dit graag wat meer balanceren.

Balanceren? Kijk.. je hebt gewoon een bepaalde hoeveelheid werkeenheiden te verdelen. Stel dat 1 cpu 199 werkinheden oplost en die andere 1... of ze lossen allebei 100 op.. samen is het nog steeds 200. Multithreaded systemen kunnen vooral handig zijn als je veel aan het locken ben.. Dan kunnen de kosten van het context switchen (het wisselen van thread) opgeheven worden doordat er gemiddeld minder lang gewacht hoeft te worden.

• Elke map op 1 thread draaien. Zou wellicht een goeie optie zijn, alhoewel je dan ook weer krijgt dat maps met veel users erop veel meer cpu trekken dan maps die leeg zijn. Ook omdat er soms vrij veel maps tegelijk geladen kunnen zijn zouden er hier ook vrij veel threads tegelijk moeten draaien.

Waarom ben je niet flexibeleren en ga je werken met een threadpool. Dan kunnen de threads dynamisch toegedeeld worden ipv statisch.

Nog een probleem waar ik erg mee zit is locking. Denk even dit scenario in:
De client lijst is een vector. Deze moet gelocked worden voor elke thread die ermee wil gaan werken, omdat het natuurlijk niet ineens mag gebeuren dat andere threads er clients uit gaan deleten of clients die nog niet "klaar" zijn toevoegen.

Locken is overgewardeerd. Ik werk met concurrency erg veel met immutable structuren. Vaak is het goedkoper om een nieuwe structuur op te bouwen op basis van de bestaande en daarin de wijzigingen door te voren, dan om de structuur te updaten. Ik hoef hierin nagenoeg niet te locken. Dit heeft een aantal voordelen: sneller en veel minder deadlock gevoelig. Uiteraard ontstaat er een stukje non-determinisme maar dat is niet erg.. dat hou je toch in multithreaded systemen. En mijn immutable oplossing is vooral sterk in systemen waar er vaker wordt gelezen dan geupdate.

Lang verhaal, maar hier zit ik dus eigenlijk mee Als jullie zo'n soortgelijke applicatie zouden moeten ontwikkelen, hoe zouden jullie dan multithreading implementeren?

Daarvoor weet ik niet genoeg van de eisen van het systeem. Standaard locken is vragen om problemen. Locken kan erg complex zijn mbt deadlocks en andere liveliness problematiek. Als het extreem belangrijk is dat er geen non determinisme in voorkomt dan zou ik de structuur volledig wegschermen achter zijn eigen thread. Andere threads posten berichten naar de structuur en zijn eigen thread zorgt voor de afhandeling. Op deze manier ben je naar de structuur geen afhandeling meer nodig en aan de voorkant van de structuur kan je met een eenvoudige procuder/consumer werken. Maar er zijn nog meer dan genoeg andere oplossingen... afhankelijk van de eisen Vaak is non determinisme in multithreaded systemen totaal niet erg.. maak er dan goed gebruik van.

[ Voor 5% gewijzigd door Alarmnummer op 11-07-2005 08:29 ]

[Eelke Spaak]

Een simpele oplossing om te voorkomen dat de client lijst teveel gelockt wordt is om elk client object in die vector apart te kunnen locken; misschien een idee?

[Alarmnummer]

Eelke Spaak schreef op maandag 11 juli 2005 @ 10:54:
Een simpele oplossing om te voorkomen dat de client lijst teveel gelockt wordt is om elk client object in die vector apart te kunnen locken; misschien een idee?

Je zult de vector ook moeten locken anders krijg je daar ook race problemen. Dat je daar verschillende locks voor gaat gebruiken is een 2e.

[Radiant]

Ik zat er al aan te denken om 2 locks te maken voor die lists, eentje voor write die gelockt wordt zodra er iets wil lezen uit de lijst, zodat er in die tijd niets verandert kan worden (kunnen wel meerdere threads tegelijk lezen) en een read lock, die gelockt wordt zodra er iets wil schrijven naar de lijst (kan maar 1 thread tegelijk schrijven). Bij een read lock zul je moeten wachten op alle write locks, maar read locks krijgen dan een hogere prioriteit dan write locks. Zal dit een beetje werken in de praktijk?
Zowiezo wou ik ook aparte locks maken op clients natuurlijk, maar het hoeft niet altijd te zijn dat de list ook gelockt is als er iets met een client bezig is (lijkt mij).

Threadpool kende ik nog niet, maar dat lijkt me wel dé oplossing hiervoor. Vooral omdat je de workload dan echt balanceert, gemakkelijk meerdere threads kan aanmaken mocht het echt druk worden en prioriteiten kan toewijzen. Ik ga er vanavond eens mee stoeien Bestaat helaas geen standaard implementatie voor op mijn platform, dus ik zal zelf iets moeten schrijven.

[ Voor 6% gewijzigd door Radiant op 11-07-2005 16:15 ]

[Alarmnummer]

Radiant schreef op maandag 11 juli 2005 @ 16:13:
Ik zat er al aan te denken om 2 locks te maken voor die lists, eentje voor write die gelockt wordt zodra er iets wil lezen uit de lijst, zodat er in die tijd niets verandert kan worden (kunnen wel meerdere threads tegelijk lezen) en een read lock, die gelockt wordt zodra er iets wil schrijven naar de lijst (kan maar 1 thread tegelijk schrijven). Bij een read lock zul je moeten wachten op alle write locks, maar read locks krijgen dan een hogere prioriteit dan write locks. Zal dit een beetje werken in de praktijk?

Dat ligt dus aan hoeveel threads die lijst gebruiken en hoe lang ze hem locken. En verder ligt het ook aan hoe lang die structuur wordt gelocked. Op het moment dat er lang gelockt gaat worden, moeten andere threads dus lang wachten. Dit hoeft trouwens geen probleem te zijn, maar is wel iets waar je rekening mee moet houden.

Ik zou in ieder geval erg goed kijken naar immutable structuren waarbij je gewoon veel minder last hebt van locking problematiek. Sommigen kunnen verwerken met wat verouderde informatie, maar de non determinisme die hieruit voort kan vloeien hoeft helemaal niet zo erg te zijn. Locken kan je verder terugbrengen tot een paar kleine plekken in het systeem.. Op het moment dat je veel reads hebt, en weinig writes, is dit imho een erg goeie oplossing (en non determinisme moet geen probleem zijn)

Zowiezo wou ik ook aparte locks maken op clients natuurlijk, maar het hoeft niet altijd te zijn dat de list ook gelockt is als er iets met een client bezig is (lijkt mij).

Clients dingen laten locken? Schreeuwt om een deadlock.

Threadpool kende ik nog niet, maar dat lijkt me wel dé oplossing hiervoor. Vooral omdat je de workload dan echt balanceert, gemakkelijk meerdere threads kan aanmaken mocht het echt druk worden en prioriteiten kan toewijzen. Ik ga er vanavond eens mee stoeien Bestaat helaas geen standaard implementatie voor op mijn platform, dus ik zal zelf iets moeten schrijven.

Ik maak er vaak gebruik van (ook van dynamische threadpools die meegroeien/krimpen indien nodig). En uiteraard blijven de kosten van thread creatie hierin veel lager lager aangezien threads gerecycled worden.

Op deze manier kan je perfect controleren hoeveel threads er maximaal draaien ipv voor iedere client maar threads op te starten. Server gaat neer op het moment dat er te veel clients op komen en je hebt geen controle.

Wat je ook zou kunnen doen is 1 thread maken die controleerd of clients een request doen. Zo nee.. kan naar de volgende client gesprongen worden. Zo ja? Dan een bericht klaarzetten met daarin de request, en een threadpool deze requests laten afhandelen. Kan je eventueel ook nog met timeouts ed gaan werken. Stel dat een client een nieuw bericht plaatst, terwijl het oude bericht nog niet verwerkt is, dan kan je misschien het oude bericht gaan deleten, of mergen met het nieuwe bericht. Beetje afhankelijk van de inhoud van het bericht.

[ Voor 16% gewijzigd door Alarmnummer op 11-07-2005 16:35 ]

[Radiant]

Alarmnummer schreef op maandag 11 juli 2005 @ 16:28:
[...]

Dat ligt dus aan hoeveel threads die lijst gebruiken en hoe lang ze hem locken. En verder ligt het ook aan hoe lang die structuur wordt gelocked. Op het moment dat er lang gelockt gaat worden, moeten andere threads dus lang wachten. Dit hoeft trouwens geen probleem te zijn, maar is wel iets waar je rekening mee moet houden.

Een thread zou dus alleen moeten wachten als hij wil schrijven naar de lijst, of als hij wil lezen van de lijst terwijl een ander aan het schrijven is of wil gaan schrijven. Met dat "schrijven" bedoel ik verder dus het toevoegen/verwijderen van objecten aan de lijst, niet properties van de objecten veranderen.

Ik zou in ieder geval erg goed kijken naar immutable structuren waarbij je gewoon veel minder last hebt van locking problematiek. Sommigen kunnen verwerken met wat verouderde informatie, maar de non determinisme die hieruit voort kan vloeien hoeft helemaal niet zo erg te zijn. Locken kan je verder terugbrengen tot een paar kleine plekken in het systeem.. Op het moment dat je veel reads hebt, en weinig writes, is dit imho een erg goeie oplossing (en non determinisme moet geen probleem zijn)

Ik snap niet zo goed hoe ik hier gebruik zou kunnen maken van immutable structuren. Omdat clients misschien heel erg veel properties gaan krijgen zou ik elke keer alles moeten uitlezen, meegeven in de constructor als ik het wil veranderen (voor wat ik van immutable structuren heb begrepen in ieder geval). Lijkt me niet erg handig werken, vooral omdat ik een aantal dingen als vaste members heb (als in, geen pointer erheen), zoals sockets.

Clients dingen laten locken? Schreeuwt om een deadlock.

Ik bedoel dus een lock op het client object voor als een thread ermee gaat werken

Ik maak er vaak gebruik van (ook van dynamische threadpools die meegroeien/krimpen indien nodig). En uiteraard blijven de kosten van thread creatie hierin veel lager lager aangezien threads gerecycled worden.

Op deze manier kan je perfect controleren hoeveel threads er maximaal draaien ipv voor iedere client maar threads op te starten. Server gaat neer op het moment dat er te veel clients op komen en je hebt geen controle.

Wat je ook zou kunnen doen is 1 thread maken die controleerd of clients een request doen. Zo nee.. kan naar de volgende client gesprongen worden. Zo ja? Dan een bericht klaarzetten met daarin de request, en een threadpool deze requests laten afhandelen. Kan je eventueel ook nog met timeouts ed gaan werken. Stel dat een client een nieuw bericht plaatst, terwijl het oude bericht nog niet verwerkt is, dan kan je misschien het oude bericht gaan deleten, of mergen met het nieuwe bericht. Beetje afhankelijk van de inhoud van het bericht.

Hmm, ik dacht er zelf aan om gewoon alles via de threadpool te laten verlopen dan, een aantal functies die zichzelf elke keer reposten (zoals socket polling, timer checks, AI, enz), op low priority. Zo heb ik ook niet die ene loop die alles regelt. Scheelt ook weer een beetje in cycles omdat ik dan het pollen gewoon op een infinite timeout kan gooien en niet op 100ms om de timers een beetje accuraat te houden bijv.