Coroutine thinking and multi player game server
Henry Heikkinen
to rewrite it in Go. I don't want to write "C++ with Go syntax" but
try to learn the usage of coroutines and channels. What things should
I know to make good use of them?
Also the game world itself is pretty large so this time if possible,
I'd love to implement some kind of scalability over multiple
processes. Is the netchan package meant for this?
I'd like to hear if you know any examples, documents, articles or
anything related to these.
David Roundy
similar using Haskell's lightweight threads and chans, which are very
similar, and I can say that goroutines + chans is a great combination
for this kind of a problem.
For each client connection, I'd have a goroutine running which parses
the client-server protocol and sends the relevant messages via chans
to their destinations, and one goroutine that does the reverse,
reading from one or more chans and sending informations back over the
network. I would then have a separate goroutine for every logical
entity in your system, e.g. one per room and one per table. Each of
these sorts of goroutines will need to keep a map of entity names to
chans and whatever other information is needed (e.g. are they sitting
North or South). The beautiful thing is that all this data is local
to each goroutine, so there is no locking needed beyond what happens
internally in the chans.
I'm not sure if that is helpful advice. In general, where in C++ you
might have an object, in go I would have a goroutine--at least for
this sort of problem. Of course, that's not true for smallish objects
(e.g. cards), but for larger or more complicated objects, that's how
I'd think about making the transition.
David
--
David Roundy
Henry Heikkinen
become if passing chans from place to another.
Since the game is rpg type, should I have a goroutine per monster or
like one for each spawn which is made of about 20 monsters max? Sounds
kind of scary because I'm used to normal threads which waste CPU time
with context switching, locking and stuff.
On 11 helmi, 03:52, David Roundy <roun...@physics.oregonstate.edu>
wrote:
> similar using Haskell's lightweight threads and chans, which are very
> similar, and I can say that goroutines + chans is a great combination
> for this kind of a problem.
>
> For each client connection, I'd have a goroutine running which parses
> the client-server protocol and sends the relevant messages via chans
> to their destinations, and one goroutine that does the reverse,
> reading from one or more chans and sending informations back over the
> network. I would then have a separate goroutine for every logical
> entity in your system, e.g. one per room and one per table. Each of
> these sorts of goroutines will need to keep a map of entity names to
> chans and whatever other information is needed (e.g. are they sitting
> North or South). The beautiful thing is that all this data is local
> to each goroutine, so there is no locking needed beyond what happens
> internally in the chans.
>
> I'm not sure if that is helpful advice. In general, where in C++ you
> might have an object, in go I would have a goroutine--at least for
> this sort of problem. Of course, that's not true for smallish objects
> (e.g. cards), but for larger or more complicated objects, that's how
> I'd think about making the transition.
>
> David
>
Roger Pau Monné
entities that process the data, but I wouldn't advice to use it for
inter-communications of the different logical entities in the system,
it may depend on the level of communication these entities need with
the outside world, but you may end up having a mess of channels and
different message types across the system, which is not really
scalable and adds a lot of overhead to your application. In this
scenario I prefer to use the classical structure of having a goroutine
that handles every logical entity in the system and a reference inside
each entity to the other entities it needs to interact with (and maybe
a mutex).
Hope this helps, Roger.
2011/2/11 Henry Heikkinen <hopso...@gmail.com>:
David Roundy
> Thank you, this helps a lot. I'm just scared of how messy it might
> become if passing chans from place to another.
>
> Since the game is rpg type, should I have a goroutine per monster or
> like one for each spawn which is made of about 20 monsters max? Sounds
> kind of scary because I'm used to normal threads which waste CPU time
> with context switching, locking and stuff.
Hmmm. How I would do that would depend on how the monsters or spawns
interact. In general, it's nice to have goroutines for things that
may interact asynchronously. So if your rpg is turn-based, or
monsters only respond to user input, then probably they don't deserve
goroutines. But if it's a real-time game so that monsters can act
whenever they like, and might respond to events that they perceive,
then I think a goroutine approach might be good.
Although goroutines are cheap, they aren't free. My experience was an
online bridge game, where *everything* is asynchronous except the game
logic, which is a small part of the code, which is why I made the
(over) generailization of objects mapping to goroutines. The primary
advantage of goroutines + chans for game elements is that it allows
you to put your abstractions into code without having to deal with
locks, etc. So if monsters only respond to specific events, then they
can listen on a chan for those events, and then interact by sending
events to other chans. On the other hand, if you have a real-time
timestep-based system, where every timestep each AI decides what to
do, then putting monsters into separate goroutines is probably way
more complex than you want...
David
roger peppe
one of deadlock. usually objects will interact with each other,
and non-hierarchical bidirectional communication is hard
to get right.
i think it's probably best to make goroutines out of independent
pieces of code that have well defined relationships.
another way of doing it is to have the game objects communicate
with a central goroutine rather than directly to each other.
Carl
anything related to these. >>
other priorities... I just want to give my take on it.
mmorpg:
For me the central and most important issue boils down to the one
dominant problem of scalability.
The only mmorpg that I have engaged with as a user is Second life.
Scalability was and still is the single biggest problem they have(!),
both from a technical and from a business perspective. Currently you
can get about 50 Users (Avatars) onto one Simulator, which roughly
equates to one core on one Processor. That makes 4 Simulators on a
quad core server. The simulators are not connected, they are separate
pieces of "land". That is just simply inadequate, especially from a
business perspective.
Scalability is such a dramatically important issue for sl because
obviously you want to be able to do events with more that 50 Users per
location, you want to do a 1000 or 100000 Users (... and up) per
location as in "open-air concerts" or similar events, thats when
things really begin to rock in every sense of the word... last time I
checked 40-50 users would rock the server(simulator) into a crash.
There are additional scalability problems, because each Avatar(User)
can be running its own scripts (behavior animations, radar etc). The
number of scripts running per User will limit the scalability per
location(Simulator) even more. SL therefore has ported Lindenscript so
that the generated bytecode can be executed on Mono, they claim this
would be vastly faster, I have doubts about this, as I have doubts
about all interpreted languages. A number of locations on sl force
you to turn off scripts when you enter the location(Simulator) for
this reason.
So the first question (imo) to be answered in this context is: can
Golang scale significantly higher than C++ in general? Why would it?
What design pattern might it have that sets it apart and enables it to
do that easily. I don't know the answer but it would certainly be
worthwhile to find out.
Maybe it could, if it can fully exploit a distributed computing model
on a tightly coupled cluster of machines (connected with very high
bandwidth), making n-number of cpu's look like one cpu, and thus
enabling vastly more Users per simulator. I think thats the key.
If it could do this better than other languages you would have a
strong business case for porting a large codebase of an existing
physics engine to golang.
The other idea I find appealing is using golang as a scripting
language which compiles on the fly to native code. This in itself
would facilitate a major performance break-thru, I think.
Of course on an mmorpg you have much more than just the physics engine
and scripts. You also have issues around distributed high-performance
data storage, this is yet another performance and scalability
frontier.
I think just about all mmorg's are facing these issues.
sorry for the long rant... :-)
Pete Wilson
I very much doubt that go (or any language) can provide enormous
performance benefits per se.
To simplify, there's the state-changes of each agent in the game, and
their interactions.
You need to compute both.
The longer the range of the interactions, the more interactions you
need to deal with.
A language can let you represent the interactions, and the fact that
all the agents are alive and concurrent, well or badly.
go gives you the abstraction of a go-routine, so that you can simply
represent what the agent is doing in a go-routine, without worrying
about inappropriate messing with the landscape or other agents..
go gives you channels, which allow you to have inter-agent interaction
without the horror and synchronization problems of shared global
state.
Using these at least gives the possibility of enormous scaling (a
processor per agent), while a discrete event (timestep) model almost
certainly doesn't even if you use speculative approaches like TimeWarp
(IIRC)
But to repeat - go will (arguably) let you express your 'model of the
universe' clearly and safely. But it won't provide you with higher
performance than other languages (well, other compiled languages).
To get higher performance, you need (i) faster processors and (ii)
more of 'em. It's unlikely we'll get faster processors (in the sense
of doing floating point adds significantly faster), although if we're
running millions of threads/go-routines on a processor, there's
probably room for more optimisations associated with messaging and
context switching. But that's not a factor of 10 or 100.... So that
says more processors. Lots more processors.
-- P
Lars Pensjö
Lars Pensjö
Alexey Nezhdanov
Ian Lance Taylor
> A bit stray question: is it possible to implement built-in multi-server
> support?
> I mean - like erlang does - with proper setup spawning one more process may
> actually employ a completely different cpu residing on physically different
> computer, while all internal messaging (channels) continue working in
> exactly same way, transparently providing guaranteed message delivery (w/o
> order guaranties) over network.
Communication between threads in a shared memory space and between
threads which do not share memory is inherently different. Go has
chosen to not unify those two different ideas in a single mechanism.
Erlang does unify them, which is appropriate considering that Erlang was
originally designed not for multi-core microprocessors but for separate
processors with high speed network connections.
For communication between programs running on different processors, Go
provides the gob and rpc packages, which can be viewed as a modified
form of channels designed for cases where memory is not shared.
Ian
roger peppe
> For communication between programs running on different processors, Go
> provides the gob and rpc packages, which can be viewed as a modified
> form of channels designed for cases where memory is not shared.
probably should mention netchan here too.
David Roundy
> the difficulty with making all independent objects into goroutines is
> one of deadlock. usually objects will interact with each other,
> and non-hierarchical bidirectional communication is hard
> to get right.
I guess it would depend on the sorts of independent objects that show
up. As long as they are interacting asynchronously (each object
reacts to events as they arrive, and immediately respond to those
events, sending events to objects as needed) it's hard to see how
you'd run into a deadlock.
> i think it's probably best to make goroutines out of independent
> pieces of code that have well defined relationships.
I'm not sure that I see how that differs from independent objects.
> another way of doing it is to have the game objects communicate
> with a central goroutine rather than directly to each other.
--
David Roundy
Andrew Francis
Quick comment. I play with Stackless Python. Stackless gets its ideas
from Limbo ( a part of my interest in Go). Stackless Python's biggest
claim to fame is its use in the construct of EVE-Online. I strongly
suspect that Go would be well suited for writing game servers. From
glancing at the answers, well I see mention of stuff like mutexes,
this seems to be a step in the wrong direction.
Cheers
Andrew
Paul Borman
roger peppe
> On Fri, Feb 11, 2011 at 7:30 AM, roger peppe <rogp...@gmail.com> wrote:
>> the difficulty with making all independent objects into goroutines is
>> one of deadlock. usually objects will interact with each other,
>> and non-hierarchical bidirectional communication is hard
>> to get right.
>
> I guess it would depend on the sorts of independent objects that show
> up. As long as they are interacting asynchronously (each object
> reacts to events as they arrive, and immediately respond to those
> events, sending events to objects as needed) it's hard to see how
> you'd run into a deadlock.
i disagree, although it depends how you set up your object-to-object
communication.
say each object had its own goroutine, doing something like:
func (obj *someObject) run() {
for {
e := <-obj.incoming
switch e.(type) {
case pickedUp:
obj.someonePickedMeUp(e)
etc ....
}
}
the someonePickedMeUp method might wish to send an
event to another object with a similar event loop.
the moment you make a cycle (an easy thing to do if you
haven't got a strictly hierarchical set of objects) then
you'll get deadlock.
>> i think it's probably best to make goroutines out of independent
>> pieces of code that have well defined relationships.
>
> I'm not sure that I see how that differs from independent objects.
i guess what i meant is that the pieces of code should have *statically*
well defined relationships, so you can build a program which is
deadlock-free by construction.
i haven't had much joy trying to come up with a framework
where objects are treated as "agents" and interact on an ad-hoc
basis with other objects. maybe there is a nice way of doing
it - if there is, i'd be very happy to see it.
Lars Pensjö
Henry Heikkinen
supposed to be over 2000 players so I doubt the performance of Go
would be a problem. I've made a prototype which is pretty close to the
C++ implementation but instead of running the player, NPC and item
handlers after each other, it'll run them as goroutines. Those
handlers then start few goroutines to actually handle the stuff.
There's an acceptor goroutine accepting connections. Player handler
iterates over the players receiving, processing and then sending
packets. Item handler keeps track of how long the items will be on
ground and when the ownership of item is released so anyone can pick
up the drop. NPC handler handles all the monsters and other characters
that are controlled by the server. I'll probably later add a shop
handler which will handle shops' stock and stuff.
On 11 helmi, 17:21, David Roundy <roun...@physics.oregonstate.edu>
wrote:
David Roundy
> On 14 February 2011 20:15, David Roundy <rou...@physics.oregonstate.edu> wrote:
>> On Fri, Feb 11, 2011 at 7:30 AM, roger peppe <rogp...@gmail.com> wrote:
>>> the difficulty with making all independent objects into goroutines is
>>> one of deadlock. usually objects will interact with each other,
>>> and non-hierarchical bidirectional communication is hard
>>> to get right.
>>
>> I guess it would depend on the sorts of independent objects that show
>> up. As long as they are interacting asynchronously (each object
>> reacts to events as they arrive, and immediately respond to those
>> events, sending events to objects as needed) it's hard to see how
>> you'd run into a deadlock.
>
> i disagree, although it depends how you set up your object-to-object
> communication.
Yeah, the key is in the asynchronous communication (which I referred
to, but wasn't explicit), which needs to be actually done
asynchronously. If you try to implement an asynchronous communication
using synchronous primitives, then yes, you will run into trouble.
They've just removed the non-blocking send from the language, so now
you'd want do create chans with buffers and then for each send you'd
do something like:
select {
case ch <- value:
default:
go func() { ch <- value }
}
and you've got asynchronous communication. As long as you use this
everywhere (and your code flow is designed to operate asynchronously,
e.g. you never wait for an event before doing something), deadlocks
should be a thing of the past. And rather than having a type switch,
I'd probably have separate channels for separate communications, so
you have just one select switch. But that's mostly just a matter of
taste and static type guarantees.
David
> say each object had its own goroutine, doing something like:
>
> func (obj *someObject) run() {
> for {
> e := <-obj.incoming
> switch e.(type) {
> case pickedUp:
> obj.someonePickedMeUp(e)
> etc ....
> }
> }
>
> the someonePickedMeUp method might wish to send an
> event to another object with a similar event loop.
>
> the moment you make a cycle (an easy thing to do if you
> haven't got a strictly hierarchical set of objects) then
> you'll get deadlock.
>
>>> i think it's probably best to make goroutines out of independent
>>> pieces of code that have well defined relationships.
>>
>> I'm not sure that I see how that differs from independent objects.
>
> i guess what i meant is that the pieces of code should have *statically*
> well defined relationships, so you can build a program which is
> deadlock-free by construction.
>
> i haven't had much joy trying to come up with a framework
> where objects are treated as "agents" and interact on an ad-hoc
> basis with other objects. maybe there is a nice way of doing
> it - if there is, i'd be very happy to see it.
>
--
David Roundy
roger peppe
> They've just removed the non-blocking send from the language, so now
> you'd want do create chans with buffers and then for each send you'd
> do something like:
>
> select {
> case ch <- value:
> default:
> go func() { ch <- value }
> }
>
> and you've got asynchronous communication. As long as you use this
> everywhere (and your code flow is designed to operate asynchronously,
> e.g. you never wait for an event before doing something), deadlocks
> should be a thing of the past.
that's true if all you do is send (and you don't care if events are arbitrarily
reordered).
but what if you actually want to acquire some data from one of these
objects? using a blocking receive will get you into exactly the
same deep water - deadlocks. and using a non-blocking receive isn't
great because then you're likely to miss data even when it's
available.
there's no silver bullet for deadlocks, and
in my experience arbitrary peer-to-peer communications
of this nature make it very easy for the wolf to appear...
> And rather than having a type switch,
> I'd probably have separate channels for separate communications, so
> you have just one select switch. But that's mostly just a matter of
> taste and static type guarantees.
yes, both approaches can be appropriate in different domains.
Lars Pensjö
They've just removed the non-blocking send from the language, so now
you'd want do create chans with buffers and then for each send you'd
do something like:select {
case ch <- value:
default:
go func() { ch <- value }
}
