Writing ad hoc threaded code is almost always more difficult than it is worth. You might be able to get it to work, but the next guy in your code is probably going to break it by accident, or find it so hard to deal with, they will want to rewrite it. So you want some kind of simplifying policy about how to develop threaded code. It needs to perform well (the primary reason for doing threading in the first place, other than dealing with blocking), require little mental overhead or boiler plate code, and ideally be able to be used by more junior developers than yourself.
Functional parallelism only extracts a small fraction of available performance, at least in larger, "interesting" problems. Data parallelism is often better at extracting more performance. In the case of large online game servers, the ideal thing to parallelize across are game entities. There are other types of entities that we can generalize to, as well, once this is working.
Here's what I've come up with...
Generally, you want to avoid ticking entities as fast as possible. While this makes a certain amount of sense on the client (one tick per graphics frame) to provide the smoothest visual experience, on the server it will consume 100% of the CPU without significantly improving the player's experience. One big downside is that you can't tell when you need to add more CPUs to your cluster. So I prefer event driven models of computing. Schedule an event to occur when there is something necessary to do. In some cases, you may want to have periodic events, but decide what rate is appropriate, and schedule only those. In this way, you can easily see the intrinsic load on a machine rise as more work (entities) are being handled. So the core assumption is: we have a collection of entities, handling a stream of events.
We built an event dispatcher. It is responsible for distributing events (that usually arrive as messages) to their target entities. I've discussed a number of means to route those messages and events in other posts. When an event is available, the system has the entity consume the event, and runs an event handler designed for that type of event.
You don't want to spawn a thread per entity. There could be thousands of entities per processor, and that would cause inefficient context switching, and bloat memory use for all those threads sitting around when only a few can run at a time. You also don't want to create and destroy threads every time an entity is created or destroyed. Instead, you want to be in control of the number of threads spawned regardless of the workload. That allows you to tune the number of threads for maximum performance and adjust to the current state of affairs in the data center. You create a thread pool ahead of time, then map the work to those threads.
It would be easy enough to use an Executor (java), and Runnables. But this leads to an unwanted problem. If there are multiple events scheduled for a single entity, this naive arrangement might map two events for the same target to different threads. Consequently, you would have to put in a full set of concurrency controls, guarding all data structures that were shared, including the entity itself. This would counteract the effect of running on two threads, and make the arrangement worthless.
Instead, what I did was to create a separate event queue per entity, and make a custom event dispatcher that pulled only a single event off the queue. The Runnable and Executor in this better set up are managing entities (ones with one or more events on their private queues). Any entity can be chosen to run, but each entity will only work on a single event at a time. This makes more efficient use of the threads in the pool (no blocking between them), and obviates the need for concurrency control (other than in the queues). Event handlers can now be written as if they are single threaded. This makes game logic development easier for more junior programmers, and for those less familiar with server code or with Java (e.g. client programmers).
Obviously, this applies to data that is owned by a single entity. Anything shared between entities still needs to be guarded. In general, you want to avoid that kind of sharing between entities, especially if you have a large scale game where entities might be mapped across multiple machines. You can't share data between two entities if they are in different processes on different machines (well there is one way, but it requires fancy hardware or device drivers, but that is another story). So you will be building for the distributed case anyway. Why not do it the same way when the entities are local?
I found a number of posts about executors and event dispatching that touched on these ideas, but there was nothing official, and there seemed to be a lot of debate about good ways to do it. I'm here to say it worked great. I'd love to post the code for this. Again, maybe when Quantum is available, you'll see some of this.
Showing posts with label Architecture. Show all posts
Showing posts with label Architecture. Show all posts
Tuesday, February 17, 2015
Wednesday, August 15, 2012
Time Management and Synchronization
A key principle of online games is synchronization. Keeping the various players in synch means giving them practically identical and consistent experiences of the virtual world. The reason this is hard is that they are separated by network delays, and worse, those delays are variable.
The ideal situation would be that all players saw exactly the same thing, and that there were no delays. How do we approach that ideal? Consider a use case: there is an observer that is watching two other players (A and B) racing toward a finish line. The observer should see the correct player cross first, and see that happen at the correct time delay from the beginning of the race. To make that sentence make sense, we need a consistent notion of time. I call this Virtual Time, and my views are drawn from computer science theory of the same name, and from the world of Distributed Interactive Simulation.
Let's say the start of the race is time zero. Both racers' clients make the start signal go green at time zero, and they begin accelerating. They send position updates to each other and the observer throughout the race, and try to render the other's position "accurately". What would that look like? Without any adjustment, on A's screen, he would start moving forward. After some network latency, B would start moving forward, and remain behind A all the way to the finish line. But on B's screen, B would start moving forward. After some network latency, B would start receiving updates from A, and would render him back at the start line, then moving forward, always behind. Who won? The Observer would see A's and B's updates arrive at approximately the same time, and pass the finish line at approximately the same time (assuming they accelerate nearly equally). Three different experiences. Unacceptable.
Instead, we add time stamps to every update message. When A starts moving the first update message has a virtual time stamp of zero. Instead of just a position, the update has velocity, and maybe acceleration information as well as the time stamp. When it arrives at B, some time has passed. Let's say it is Virtual Time 5 when it arrives. B will dead reckon A using the initial position, time stamp, and velocity of that time zero update to predict A's position for time 5. B will see himself and A approximately neck and neck. Much better. The Observer would see the same thing. As would A (by dead reckoning B's position).
This approach still has latency artifacts, but they are much reduced. For example, if A veered off from a straightline acceleration to the finish line, B would not know until after a little network delay. In the mean time, B would have rendered A "incorrectly". We expect this. When B gets the post-veering update, it will use it, dead reckon A's position to B's current Virtual Time, and compute the best possible approximation of A's current position. But the previous frame, B would have rendered A as being still on a straight line course. To adjust for this unexpected turn, B will have to start correcting A's rendered position smoothly. The dead reckoned position becomes a Goal or Target position that the consumer incrementally corrects for. If the delta is very large, you may want to "pop" the position to the correct estimate and get it over with. You can use the vehicle physics limits (or a little above) to decide how rapidly to correct its position. In any case, there are lots of ways to believably correct the rendered position to the estimated position.
Note that during the start of the race, at first B would still see A sitting still for a period of time, since it won't get the first update until after a network delay. But after the first delay, it will see that the estimated position should be up near where B has already moved itself. The correction mechanism will quickly match A's rendered position to the dead reckoned one. This may be perceived as impossibly large acceleration for that vehicle. But incorrect acceleration is less easily detected by a person than incorrect position, or teleporting.
Another use case is if A and B are firing at each other. Imagine that B is moving across in front of A, and A fires a missile right when B appears directly in A's path. Let's assume that the client that owns the target always determines if a missile hits. If we were not using dead reckoning, by the time the missile update arrived back at B, B would have been 2 network delays off to the side, and the missile would surely miss. If we are using dead reckoning, A would be firing when B's estimated position was on target. There might be some discrepancy if B was veering from the predictable path. But there is still one more network latency to be concerned about. By the time the firing message arrives at B, B would be one network latency off to the side. B could apply some dead reckoning for the missile, flying it out a few Virtual Time ticks, but the angle from the firing point might be unacceptable, and would definitely not be the same as what A experienced.
A better, more synchronized, more fair experience would be to delay the firing of the missile on A, while sending the firing message immediately. In other words, when A presses the fire button, schedule the execution of the fire event 5 Virtual Time units in the future. Send that future event to B, and to itself. On both A and B, the fire event will occur simultaneously. I call this a "warm up" animation. The mage winds up, the missile smokes a bit before it fires, or whatever. The player has to learn to account for that little delay if they want the missile to hit.
If you have a game where firing is instantaneous (a rifle, or laser), this is a pretty much impossible problem. You have to put in custom code for this. The shooter decides ahead of time where the bullet will hit, and tells the target. By the time the target is told, both shooter and target have moved, so the rendering of the bullet fly out is not in the same location in space, and will possibly go through a wall. The point of impact is also prone to cheating, of course. I don't like games that have aiming for this reason. They are very difficult to make fair and cheat proof. I prefer target based games. You select a target, then use your weapons on it. The distributed system can then determine whether it worked. Aiming, and determining hits, shooting around corners, etc. is a tough problem. FPS engines are really tough. You should seriously consider whether your game needs to bite off that problem, or if you can make it fun enough using a target based system, and a little randomness. Then add decorative effects that express what the dice said.
The key take away with Time Management, Virtual Time, and synchronization is that whichever client actions are occurring on (A, B, or Observer), they occur in the same time axis. There are nice time synchronization algorithms (look up NTP), that rely on periodically exchanging time stamps using direct messages. And you can solve a lot of problems using events that are scheduled to occur in the future based on Virtual Time timestamps. One challenge though is how to keep the simulation that is being run using Virtual Time in synch with animation and physics that you might be tempted to run using real time. Or what you think is real time. You may have a game that you can pause. How does that work? Do you freeze the animation or not? You are already dealing with different concepts of time. Consider adding Virtual Time. And the notion of Goal positions.
The ideal situation would be that all players saw exactly the same thing, and that there were no delays. How do we approach that ideal? Consider a use case: there is an observer that is watching two other players (A and B) racing toward a finish line. The observer should see the correct player cross first, and see that happen at the correct time delay from the beginning of the race. To make that sentence make sense, we need a consistent notion of time. I call this Virtual Time, and my views are drawn from computer science theory of the same name, and from the world of Distributed Interactive Simulation.
Let's say the start of the race is time zero. Both racers' clients make the start signal go green at time zero, and they begin accelerating. They send position updates to each other and the observer throughout the race, and try to render the other's position "accurately". What would that look like? Without any adjustment, on A's screen, he would start moving forward. After some network latency, B would start moving forward, and remain behind A all the way to the finish line. But on B's screen, B would start moving forward. After some network latency, B would start receiving updates from A, and would render him back at the start line, then moving forward, always behind. Who won? The Observer would see A's and B's updates arrive at approximately the same time, and pass the finish line at approximately the same time (assuming they accelerate nearly equally). Three different experiences. Unacceptable.
Instead, we add time stamps to every update message. When A starts moving the first update message has a virtual time stamp of zero. Instead of just a position, the update has velocity, and maybe acceleration information as well as the time stamp. When it arrives at B, some time has passed. Let's say it is Virtual Time 5 when it arrives. B will dead reckon A using the initial position, time stamp, and velocity of that time zero update to predict A's position for time 5. B will see himself and A approximately neck and neck. Much better. The Observer would see the same thing. As would A (by dead reckoning B's position).
This approach still has latency artifacts, but they are much reduced. For example, if A veered off from a straightline acceleration to the finish line, B would not know until after a little network delay. In the mean time, B would have rendered A "incorrectly". We expect this. When B gets the post-veering update, it will use it, dead reckon A's position to B's current Virtual Time, and compute the best possible approximation of A's current position. But the previous frame, B would have rendered A as being still on a straight line course. To adjust for this unexpected turn, B will have to start correcting A's rendered position smoothly. The dead reckoned position becomes a Goal or Target position that the consumer incrementally corrects for. If the delta is very large, you may want to "pop" the position to the correct estimate and get it over with. You can use the vehicle physics limits (or a little above) to decide how rapidly to correct its position. In any case, there are lots of ways to believably correct the rendered position to the estimated position.
Note that during the start of the race, at first B would still see A sitting still for a period of time, since it won't get the first update until after a network delay. But after the first delay, it will see that the estimated position should be up near where B has already moved itself. The correction mechanism will quickly match A's rendered position to the dead reckoned one. This may be perceived as impossibly large acceleration for that vehicle. But incorrect acceleration is less easily detected by a person than incorrect position, or teleporting.
Another use case is if A and B are firing at each other. Imagine that B is moving across in front of A, and A fires a missile right when B appears directly in A's path. Let's assume that the client that owns the target always determines if a missile hits. If we were not using dead reckoning, by the time the missile update arrived back at B, B would have been 2 network delays off to the side, and the missile would surely miss. If we are using dead reckoning, A would be firing when B's estimated position was on target. There might be some discrepancy if B was veering from the predictable path. But there is still one more network latency to be concerned about. By the time the firing message arrives at B, B would be one network latency off to the side. B could apply some dead reckoning for the missile, flying it out a few Virtual Time ticks, but the angle from the firing point might be unacceptable, and would definitely not be the same as what A experienced.
A better, more synchronized, more fair experience would be to delay the firing of the missile on A, while sending the firing message immediately. In other words, when A presses the fire button, schedule the execution of the fire event 5 Virtual Time units in the future. Send that future event to B, and to itself. On both A and B, the fire event will occur simultaneously. I call this a "warm up" animation. The mage winds up, the missile smokes a bit before it fires, or whatever. The player has to learn to account for that little delay if they want the missile to hit.
If you have a game where firing is instantaneous (a rifle, or laser), this is a pretty much impossible problem. You have to put in custom code for this. The shooter decides ahead of time where the bullet will hit, and tells the target. By the time the target is told, both shooter and target have moved, so the rendering of the bullet fly out is not in the same location in space, and will possibly go through a wall. The point of impact is also prone to cheating, of course. I don't like games that have aiming for this reason. They are very difficult to make fair and cheat proof. I prefer target based games. You select a target, then use your weapons on it. The distributed system can then determine whether it worked. Aiming, and determining hits, shooting around corners, etc. is a tough problem. FPS engines are really tough. You should seriously consider whether your game needs to bite off that problem, or if you can make it fun enough using a target based system, and a little randomness. Then add decorative effects that express what the dice said.
The key take away with Time Management, Virtual Time, and synchronization is that whichever client actions are occurring on (A, B, or Observer), they occur in the same time axis. There are nice time synchronization algorithms (look up NTP), that rely on periodically exchanging time stamps using direct messages. And you can solve a lot of problems using events that are scheduled to occur in the future based on Virtual Time timestamps. One challenge though is how to keep the simulation that is being run using Virtual Time in synch with animation and physics that you might be tempted to run using real time. Or what you think is real time. You may have a game that you can pause. How does that work? Do you freeze the animation or not? You are already dealing with different concepts of time. Consider adding Virtual Time. And the notion of Goal positions.
Tuesday, May 29, 2012
Let's Call it MLT.
I need a name for the Ultimate Online Game Framework we've been discussing so people know what I'm refering to (crazy idea, or something for that project). I want it to be the greatest thing in the world. And as everyone knows, that is a nice MLT (Mutton, Lettuce and Tomato sandwich). I was toying with calling it Quantum, because I like the thought of Quantum Entanglement to represent entity state replication. So maybe the Quantum Distributed Entity System (QDES), and later the Quantum this and that.
I'm also really stuck on what language to write it in. C++ or Java. I think it is critical that a game development team use the same language on client and server. Otherwise the team gets split in half, and winds up not talking enough. Being able to swap people onto what ever needs work is really important for keeping to a schedule. And hiring from two piles of expertise is just that much harder. Java has so many great libraries. But C++ is so much more popular in the game industry. On mobile, you've got Objective-C. If you're using Unity, you've got C#.
To be honest, most of your game logic should probably be written (at least initially) in your favorite scripting language. Java and C++ both support Python, Lua, Javascript for example. IKVM appears to allow Mono to be embedded in Java, so you could maybe even do C# on both sides. This argument (http://www.mono-project.com/Scripting_With_Mono) is certainly compelling. Ever heard of Gecko? It embeds a C++ compiler so you can compile and load/run C++ "scripts" at run time. The reason I bring up all these options is: you could implement client and server in different languages, but embed the same scripting engine in both sides, so the game developers get the benefit of reusing their staff on both sides.
If the architecture and design of QDES is awesome enough, someone might reimplement it in their favorite language anyway. Or port it to a very different platform that doesn't support whatever language choice we make. So maybe the choice I'm stuck on isn't that serious right now. Maybe I should just start with the architecture and design.
I'm drafting some high level requirements and am thinking I'll post them here on a "page" instead of a blog article. Not sure how comments and such would work with that however. But I wanted something stickier than a post and something I could update and have a single reference to. Same with the designs as they start to come.
Anyway. Thanks for being a sounding board. Maybe some of you and your friends will have time to contribute to (or try out) all this. (And I haven't completely forgotten about doing that tech survey to see what other similar projects are out there in the open source world. I found a few. Some are a little dusty. Some are a little off track from what I'm thinking.)
I'm also really stuck on what language to write it in. C++ or Java. I think it is critical that a game development team use the same language on client and server. Otherwise the team gets split in half, and winds up not talking enough. Being able to swap people onto what ever needs work is really important for keeping to a schedule. And hiring from two piles of expertise is just that much harder. Java has so many great libraries. But C++ is so much more popular in the game industry. On mobile, you've got Objective-C. If you're using Unity, you've got C#.
To be honest, most of your game logic should probably be written (at least initially) in your favorite scripting language. Java and C++ both support Python, Lua, Javascript for example. IKVM appears to allow Mono to be embedded in Java, so you could maybe even do C# on both sides. This argument (http://www.mono-project.com/Scripting_With_Mono) is certainly compelling. Ever heard of Gecko? It embeds a C++ compiler so you can compile and load/run C++ "scripts" at run time. The reason I bring up all these options is: you could implement client and server in different languages, but embed the same scripting engine in both sides, so the game developers get the benefit of reusing their staff on both sides.
If the architecture and design of QDES is awesome enough, someone might reimplement it in their favorite language anyway. Or port it to a very different platform that doesn't support whatever language choice we make. So maybe the choice I'm stuck on isn't that serious right now. Maybe I should just start with the architecture and design.
I'm drafting some high level requirements and am thinking I'll post them here on a "page" instead of a blog article. Not sure how comments and such would work with that however. But I wanted something stickier than a post and something I could update and have a single reference to. Same with the designs as they start to come.
Anyway. Thanks for being a sounding board. Maybe some of you and your friends will have time to contribute to (or try out) all this. (And I haven't completely forgotten about doing that tech survey to see what other similar projects are out there in the open source world. I found a few. Some are a little dusty. Some are a little off track from what I'm thinking.)
Friday, May 25, 2012
Essential Components of the New Framework
What are the components that are absolutely essential to get right in the Ultimate MMO Framework (still need a catchy name)? If had those components today, you'd be using them in your current game, even if you had to integrate them to a bunch of other stuff you have to get a full solution. If we could build those essential pieces, and they were free, I think they would slowly take over the industry, shouldering less effective solutions out of the way. If each piece can be made independent of the others, there is a better chance the system will be adopted even if someone thinks it isn't all a perfect fit.
It is tempting to start with message passing. After all, it isn't an online game without that. But there are a lot of great message passing systems. There might even be some decent event handling systems. And there are definitely some good socket servers that combine the two. While I see problems with these that could be improved, and I see missing features, I think message passing is a second priority. You could make do with an existing system, and swap it out later. Although, I don't know how you can get away from the assumption that you have a publish/subscribe api that the higher levels can use.
More essential is the Entity System. It is where game play programmers interact with your system, and when done well, much of the rest of the system gets abstracted away. The decisions made here are what enable a server to scale, a client to stay in synch, content to get reused in interesting ways, and game play to be developed efficiently. BTW, what I mean by an Entity is a game object. Something that represents a thing or concept in the game world. The term comes from discrete event simulation. Jumping ahead a bit, the Entity System needs to be Component oriented such that an Entity is aggregated from a collection of Components. The Entity State system is the basis of replication to support distributed computation and load balancing, and of persistence. Done well, the Entity System can be used for more than just visible game objects, but could support administrative and configuration objects as well.
Related, but probably separatable is the Behavior system. How do get Entities to do something, and how do they interact with one another? I don't mean AI, I mean behavior in the OO encapsulated-state-and-behavior sense. It will be interesting to distinguish between and tie together AI "plans", complex sequences of actions, and individual behavior "methods". And, of course, the question of languages, scripting and debugging land right here. (A second priority that relates to Behaviors is time management. How do you synchronize client and server execution, can you pause, can you persist an in-flight behavior?)
Content Tools are the next big ticket item. If the Framework is stable enough, a new game could be made almost exclusively using these tools. Close to 100% of your budget would be spent pushing content through them in some imaginary perfect world. These tools allow for rapid iteration and debugging across multiple machines, and multiple platforms. It is not clear how much of the tools can be made independent of Entity state and behavior choices.
What other systems are absolutely essential? They drive everything else? They don't already exist, and you feel like you always have to rebuild them?
What do you think? Wouldn't it be cool to have a standalone Entity System that you could use in your next game? What if it came with a collection of Components that solved a lot of major problems like movement, collision, visibility, containment?
It is tempting to start with message passing. After all, it isn't an online game without that. But there are a lot of great message passing systems. There might even be some decent event handling systems. And there are definitely some good socket servers that combine the two. While I see problems with these that could be improved, and I see missing features, I think message passing is a second priority. You could make do with an existing system, and swap it out later. Although, I don't know how you can get away from the assumption that you have a publish/subscribe api that the higher levels can use.
More essential is the Entity System. It is where game play programmers interact with your system, and when done well, much of the rest of the system gets abstracted away. The decisions made here are what enable a server to scale, a client to stay in synch, content to get reused in interesting ways, and game play to be developed efficiently. BTW, what I mean by an Entity is a game object. Something that represents a thing or concept in the game world. The term comes from discrete event simulation. Jumping ahead a bit, the Entity System needs to be Component oriented such that an Entity is aggregated from a collection of Components. The Entity State system is the basis of replication to support distributed computation and load balancing, and of persistence. Done well, the Entity System can be used for more than just visible game objects, but could support administrative and configuration objects as well.
Related, but probably separatable is the Behavior system. How do get Entities to do something, and how do they interact with one another? I don't mean AI, I mean behavior in the OO encapsulated-state-and-behavior sense. It will be interesting to distinguish between and tie together AI "plans", complex sequences of actions, and individual behavior "methods". And, of course, the question of languages, scripting and debugging land right here. (A second priority that relates to Behaviors is time management. How do you synchronize client and server execution, can you pause, can you persist an in-flight behavior?)
Content Tools are the next big ticket item. If the Framework is stable enough, a new game could be made almost exclusively using these tools. Close to 100% of your budget would be spent pushing content through them in some imaginary perfect world. These tools allow for rapid iteration and debugging across multiple machines, and multiple platforms. It is not clear how much of the tools can be made independent of Entity state and behavior choices.
What other systems are absolutely essential? They drive everything else? They don't already exist, and you feel like you always have to rebuild them?
What do you think? Wouldn't it be cool to have a standalone Entity System that you could use in your next game? What if it came with a collection of Components that solved a lot of major problems like movement, collision, visibility, containment?
Saturday, May 19, 2012
Why I don't like threads
People say I'm crazy because I don't like threads in this day and age of multicore processors. But I have good reason based on years of experience, so hear me out.
Doing threading well is harder than most people think. Making a decision to multithread your application imposes on all developers, including those less experienced with such things than the ones normally making that decision. I like to think that framework and server developers are much more experienced with such things than game developers who might be plugging stuff into the server. And framework developers are building their framework to be used by those game play programmers. Play to your audience. Wouldn't it be better if they never had to know about threading issues? I believe it is possible to build a framework that insulates regular developers from such concerns (the communicating sequential process model).
Now I'm a big fan of using threading for what it is good for: dealing with interrupts that should be serviced asap without polluting your main application with lots of polling and checking. Examples of this would be a background thread for servicing the network (you want to drain the network buffers quickly so they don't overflow and back things up and cause retransmissions); background file or keyboard I/O which needs to rarely wake up and service an incoming or outgoing IO buffer; remote requests that block for a long time and would otherwise stall the app (like a DB request, or http request). Note in particular that none of these are high performance computations. They are really dominated by the blocking/waiting time. The use of a thread in this case is really all about an easier programming model. The background thread can be written as a loop that reads or writes using blocking, and since it is not done on the main thread, the main thread doesn't have checks and polling sprinkled in.
Most of the time, when you have some heavy computation to do, it will eventually scale up to require more than a single machine anyway. So you are going to have to write your system to be distributed and communicate between the machines using messages anyway. If you have already done that work, you can easily use it within a single machine that has many cores. If you try to build a system that makes use of the many cores within a machine by using threads, and you also solve the distributed case, you've doubled your work and maintenance effort. One of the best ways to decompose a problem to be solved by worker threads is to deliver the work in a task queue and have them contend for it. As each is pulled off, it is processed by a handler function. This is exactly the same approach you would use for the distributed case. So the only difference is that in one case you have messages passing between processes on the same machine, or task-messages passing between threads. Yes, I understand the performance difference. But if your app is that performance sensitive, the inter-process message passing can be implemented using shared memory and avoid the kernel switches when delivering a message to the current machine. The intent here is to save you from the double implementation, save your framework users from having to deal with thread programming, and the performance difference is pretty small.
There is also a big problem with heavily threaded apps in production. There are pretty lousy tools for helping you figure out thread related performance problems. When you are only dealing with background interrupt-handling threads, there are not going to be serious performance problems unless one of the background threads starts polling wildly and consuming 100% cpu. But if a highly multithreaded app starts using too much CPU, or starts being unresponsive, how do you tell what is actually happening among the various threads? They don't have names, and the kernel isn't very good about helping you keep track of what work happens on each thread. You wind up having to build your own instrumentation into the application every time there is such a problem. And doing a new build and getting it into production is a lot of effort. On the other hand, if you follow the distributed model, you can easily see which process is spiking CPU. You can easily instrument the message flows between processes to see if there is too much or too little inter-process communication. Often you wind up logging all such traffic for post-mortem analysis anyway. Remember, you are not likely to have the luxury of attaching a debugger to a production process to grab stack traces, or what not. So you are going to be staring at a monolithic multithreaded app and trying to guess what is going on inside.
Problems in threaded apps tend to be subtle, they wind up being hard to debug, and often only show up after the app has been running at production loads for quite a while. Writing good threaded software is the responsibility of every programmer that touches an app that adopts it, and the least experienced programmer in that app is the one you have to worry about. Operating and debugging the app in production is not easy. These are the reasons I don't like threads. I'm not afraid of them. I understand them all too well. I think there are better ways (CSP) that are actually easier and faster to develop for in the first place. And you are likely to have to adopt those ways in any case as you scale beyond a single machine.
More thoughts on this subject here: http://onlinegametechniques.blogspot.com/2009/02/manifesto-of-multithreading-for-high.html
(Any position statement like this is going to sound a little nuts if you try to apply to every conceivable situation. What I was thinking about when I wrote this was a server application, in particular, something large scale, and event oriented. If, for example, you are writing a graphical client on a 360, using multiple processes would be looney. Multiple processes listening on the same socket can be a problem (with some workarounds). You might not be able to abide even a shared memory message passing delay between components, like in a rendering pipeline. Interestingly, these examples are all amenable to the same analysis: what is the response time required, what resources are being shared, how much will the computation have to scale up, is the physical hardware intrinsically distributed anyway? My point is the default answer should be to encapsulate any threading you *have to* do so that the bulk of your development doesn't have to pay the daily overhead of always asking: is that line of code accessing anything shared; is this data structure thread safe? It slows down important conversations, and it leaves shadows of a doubt everywhere.)
Doing threading well is harder than most people think. Making a decision to multithread your application imposes on all developers, including those less experienced with such things than the ones normally making that decision. I like to think that framework and server developers are much more experienced with such things than game developers who might be plugging stuff into the server. And framework developers are building their framework to be used by those game play programmers. Play to your audience. Wouldn't it be better if they never had to know about threading issues? I believe it is possible to build a framework that insulates regular developers from such concerns (the communicating sequential process model).
Now I'm a big fan of using threading for what it is good for: dealing with interrupts that should be serviced asap without polluting your main application with lots of polling and checking. Examples of this would be a background thread for servicing the network (you want to drain the network buffers quickly so they don't overflow and back things up and cause retransmissions); background file or keyboard I/O which needs to rarely wake up and service an incoming or outgoing IO buffer; remote requests that block for a long time and would otherwise stall the app (like a DB request, or http request). Note in particular that none of these are high performance computations. They are really dominated by the blocking/waiting time. The use of a thread in this case is really all about an easier programming model. The background thread can be written as a loop that reads or writes using blocking, and since it is not done on the main thread, the main thread doesn't have checks and polling sprinkled in.
Most of the time, when you have some heavy computation to do, it will eventually scale up to require more than a single machine anyway. So you are going to have to write your system to be distributed and communicate between the machines using messages anyway. If you have already done that work, you can easily use it within a single machine that has many cores. If you try to build a system that makes use of the many cores within a machine by using threads, and you also solve the distributed case, you've doubled your work and maintenance effort. One of the best ways to decompose a problem to be solved by worker threads is to deliver the work in a task queue and have them contend for it. As each is pulled off, it is processed by a handler function. This is exactly the same approach you would use for the distributed case. So the only difference is that in one case you have messages passing between processes on the same machine, or task-messages passing between threads. Yes, I understand the performance difference. But if your app is that performance sensitive, the inter-process message passing can be implemented using shared memory and avoid the kernel switches when delivering a message to the current machine. The intent here is to save you from the double implementation, save your framework users from having to deal with thread programming, and the performance difference is pretty small.
There is also a big problem with heavily threaded apps in production. There are pretty lousy tools for helping you figure out thread related performance problems. When you are only dealing with background interrupt-handling threads, there are not going to be serious performance problems unless one of the background threads starts polling wildly and consuming 100% cpu. But if a highly multithreaded app starts using too much CPU, or starts being unresponsive, how do you tell what is actually happening among the various threads? They don't have names, and the kernel isn't very good about helping you keep track of what work happens on each thread. You wind up having to build your own instrumentation into the application every time there is such a problem. And doing a new build and getting it into production is a lot of effort. On the other hand, if you follow the distributed model, you can easily see which process is spiking CPU. You can easily instrument the message flows between processes to see if there is too much or too little inter-process communication. Often you wind up logging all such traffic for post-mortem analysis anyway. Remember, you are not likely to have the luxury of attaching a debugger to a production process to grab stack traces, or what not. So you are going to be staring at a monolithic multithreaded app and trying to guess what is going on inside.
Problems in threaded apps tend to be subtle, they wind up being hard to debug, and often only show up after the app has been running at production loads for quite a while. Writing good threaded software is the responsibility of every programmer that touches an app that adopts it, and the least experienced programmer in that app is the one you have to worry about. Operating and debugging the app in production is not easy. These are the reasons I don't like threads. I'm not afraid of them. I understand them all too well. I think there are better ways (CSP) that are actually easier and faster to develop for in the first place. And you are likely to have to adopt those ways in any case as you scale beyond a single machine.
More thoughts on this subject here: http://onlinegametechniques.blogspot.com/2009/02/manifesto-of-multithreading-for-high.html
(Any position statement like this is going to sound a little nuts if you try to apply to every conceivable situation. What I was thinking about when I wrote this was a server application, in particular, something large scale, and event oriented. If, for example, you are writing a graphical client on a 360, using multiple processes would be looney. Multiple processes listening on the same socket can be a problem (with some workarounds). You might not be able to abide even a shared memory message passing delay between components, like in a rendering pipeline. Interestingly, these examples are all amenable to the same analysis: what is the response time required, what resources are being shared, how much will the computation have to scale up, is the physical hardware intrinsically distributed anyway? My point is the default answer should be to encapsulate any threading you *have to* do so that the bulk of your development doesn't have to pay the daily overhead of always asking: is that line of code accessing anything shared; is this data structure thread safe? It slows down important conversations, and it leaves shadows of a doubt everywhere.)
Sunday, January 16, 2011
Topics are not Message Types
I periodically have an unproductive conversation about how to use Topics/Categories vs how to use Message Types. Hopefully this time will be better.
Both things appear to be used to "subscribe", and both wind up filtering what a message handler has to process and gets to process. If they can be used for exactly the same purposes, it is "just" policy as to what you use each one for. That has to be wrong, otherwise there would not be *two* concepts. Tus, there has to be a useful distinction. So let's define what they are and what their responsibilities are.
First a definition or two:
Categories are names (or numbers) that are used to decompose a stream of messages into groups. In JMS they are called Topics, but I'm going to avoid that term in case the implementation of Topics in JMS implies something I don't mean. A message is sent on, or "to" a single Category. A consumer subscribes to one or more Categories. Sophisticated message publish/subscribe or producer/consumer implementations can support wildcards or bitmasking to optimize subscription to large sets of Categories. (While not very germane to this discussion, I believe JMS can only have wildcards at the end of a Topic, and only at a dot that separates portions of the Topic. My view of wildcards and Category masking does not have that limitation. But that shouldn't affect my arguments.)
It is critical to have a mechanism that efficiently filters network messages so that a consuming process is not "bothered" by messages arriving that are immediately discarded. Running the TCP stack, for example, can wind up consuming large fractions of the CPU, and if the message is discarded, even after a simple inspection by your message framework, that is totally wasted processing. Further, if the messages are traveling over a low bandwidth link to a player, for example, it can badly affect their experience as it steals network resources from more important traffic. So we want the sender, or some intermediary to filter the messages earlier.
Early distributed simulation implementations (DIS) used multicast groups, and relied on the Network Interface hardware to filter out any messages in groups that the consumer had not subscribed to. Ethernet Multicast tends to broadcast all messages, and rely on the NIC of each host to inspect and filter unwanted messages. That is better than having the kernel do it. Switches get into the picture, but are very simplistic when it comes to multicast. When there are more than a few groups, switches and NICs will become promiscuous, and all messages get broadcast anyway, and wind up in each destination's kernel. They are filtered there, but much of the network stack has already executed. To get around that, physical network segmentation with intelligent bridges were built to copy a message from one segment to another. The bridge or rebroadcaster or smart-router would crack open each message and send it into another segment based on configuration, or a control protocol (subscription request messages).
Ancient history. However, it formed the origin of the concept of numeric Categories. A message is sent to a single Category. A consumer subscribes. The Channel/Category/Subscription manager maintains the declared connectivity and routes the messages.
So. Categories are used to optimize routing. They minimize the arrival of a message to a process. So far, this has nothing to do with what code is run when it arrives.
Message types are also names but are used to identify the meaning of a message; what the message is telling or requesting of the destination; what code should run when the message arrives (or what code should not run). Without a message type, there would be only one generic handler. In the old days, that master-handler would be a switch statement, branching on some field(s) of the message (lets call that field the message type, and be done with it).
There is some coded, static binding of a message type to a piece of code; the message handler. Handler X is for handling messages of type Y. A piece of code cannot process fields of a message different than what it was coded for. There is little reason to make that binding dynamic or data-driven. Static binding is "good". It leads to fewer errors, and those error can be caught much earlier in the development cycle. Distributed systems are hard. You don't really want to catch a message-to-code mismatch after you've launched. One way to think about this static binding is as a Remote Procedure Call. You are telling a remote process to run the code bound to message Y. In fact, you can simplify your life by making the handler have the same name as the message type, and not even register the binding.
A message can be sent to any Category regardless of the message's type. There is no checking in code that a choice is "legal". The Category can be computed, and the message is bound to that value dynamically. Instances of the same message type can be sent to one of any number of Categories. Consumers can subscribe to any Category whether they know how to process all the message types it contains or not.
So. Back to the distinction. When code is declared to be able to handle messages of type Y, that does not imply that all message instances of type Y should arrive at the process with that handler. You may want to do something like load balancing where half the messages of type Y go to one process, and the other half go to a tandem process. So message types are independent of Categories. The two concepts are orthogonal.
When a process is subscribed to a Category, there is no guarantee to the subscriber about the message types that a producer sends to that Category. It is easy to imagine a process receiving messages it does not know how to handle. The sender can't force the receiver to write code, but the sender can put any Category on a message it wants. So Categories are independent of message types. The two concepts are orthogonal.
Now. With respect to hierarchy. Message type names can be declared within a hierarchical namespace. That can be pretty useful. At the end of the day, however, they are simply some strings, or bit strings. In a sophisticated system that maps message types to message classes (code), the class hierarchy may mirror the type name hierarchy, and have interesting semantics (like a handler for a base message class being able to handle a derived message class). But mostly, message type name hierarchy is useful to avoid collisions.
In systems like JMS, Categories (Topics) are also hierarchical. This is also done to avoid collisions in the topic namespace, and for organization. But it is also useful for wildcard subscription.
Now "the" question: are Categories within the Message Type Hierarchy, or are Message Types within the Category hierarchy? Or are they orthogonal to one another? I submit that a message of a given type means the same thing no matter which Category it arrived on. Further, the same message type can be sent to any Category and a Category can transport any number of different message types.
Since there is only one message exchange system, Categories cannot be reused for two purposes without merging the message streams. That leads to inefficiency. If you reuse a message type name for two different purposes, you run the risk of breaking handler code with what appears to be a malformed message. That leads to crashes. You could permit that kind of reuse, and institute policy and testing to keep those things from mingling (e.g. reuse message types, but only on different topics), but it is a looming disaster. I would put in some coordination mechanism or name spacing to keep the mingling from happening at all.
So what are the consequences:
Unless you talk about virtual hosts, or virtual processes, multiple independent connections to the message system, thread-local subscriptions. You can do *anything* in software. But should you?
Both things appear to be used to "subscribe", and both wind up filtering what a message handler has to process and gets to process. If they can be used for exactly the same purposes, it is "just" policy as to what you use each one for. That has to be wrong, otherwise there would not be *two* concepts. Tus, there has to be a useful distinction. So let's define what they are and what their responsibilities are.
First a definition or two:
- Hierarchical: a name is defined hierarchically if the parent context is needed to ensure the child is distinct from children of other parents when the children have the same name. The parents provide the namespace in which the child is defined.
- Orthogonal: names are independent of one another, like dimensions or axes in mathematics.
Categories are names (or numbers) that are used to decompose a stream of messages into groups. In JMS they are called Topics, but I'm going to avoid that term in case the implementation of Topics in JMS implies something I don't mean. A message is sent on, or "to" a single Category. A consumer subscribes to one or more Categories. Sophisticated message publish/subscribe or producer/consumer implementations can support wildcards or bitmasking to optimize subscription to large sets of Categories. (While not very germane to this discussion, I believe JMS can only have wildcards at the end of a Topic, and only at a dot that separates portions of the Topic. My view of wildcards and Category masking does not have that limitation. But that shouldn't affect my arguments.)
It is critical to have a mechanism that efficiently filters network messages so that a consuming process is not "bothered" by messages arriving that are immediately discarded. Running the TCP stack, for example, can wind up consuming large fractions of the CPU, and if the message is discarded, even after a simple inspection by your message framework, that is totally wasted processing. Further, if the messages are traveling over a low bandwidth link to a player, for example, it can badly affect their experience as it steals network resources from more important traffic. So we want the sender, or some intermediary to filter the messages earlier.
Early distributed simulation implementations (DIS) used multicast groups, and relied on the Network Interface hardware to filter out any messages in groups that the consumer had not subscribed to. Ethernet Multicast tends to broadcast all messages, and rely on the NIC of each host to inspect and filter unwanted messages. That is better than having the kernel do it. Switches get into the picture, but are very simplistic when it comes to multicast. When there are more than a few groups, switches and NICs will become promiscuous, and all messages get broadcast anyway, and wind up in each destination's kernel. They are filtered there, but much of the network stack has already executed. To get around that, physical network segmentation with intelligent bridges were built to copy a message from one segment to another. The bridge or rebroadcaster or smart-router would crack open each message and send it into another segment based on configuration, or a control protocol (subscription request messages).
Ancient history. However, it formed the origin of the concept of numeric Categories. A message is sent to a single Category. A consumer subscribes. The Channel/Category/Subscription manager maintains the declared connectivity and routes the messages.
So. Categories are used to optimize routing. They minimize the arrival of a message to a process. So far, this has nothing to do with what code is run when it arrives.
Message types are also names but are used to identify the meaning of a message; what the message is telling or requesting of the destination; what code should run when the message arrives (or what code should not run). Without a message type, there would be only one generic handler. In the old days, that master-handler would be a switch statement, branching on some field(s) of the message (lets call that field the message type, and be done with it).
There is some coded, static binding of a message type to a piece of code; the message handler. Handler X is for handling messages of type Y. A piece of code cannot process fields of a message different than what it was coded for. There is little reason to make that binding dynamic or data-driven. Static binding is "good". It leads to fewer errors, and those error can be caught much earlier in the development cycle. Distributed systems are hard. You don't really want to catch a message-to-code mismatch after you've launched. One way to think about this static binding is as a Remote Procedure Call. You are telling a remote process to run the code bound to message Y. In fact, you can simplify your life by making the handler have the same name as the message type, and not even register the binding.
A message can be sent to any Category regardless of the message's type. There is no checking in code that a choice is "legal". The Category can be computed, and the message is bound to that value dynamically. Instances of the same message type can be sent to one of any number of Categories. Consumers can subscribe to any Category whether they know how to process all the message types it contains or not.
So. Back to the distinction. When code is declared to be able to handle messages of type Y, that does not imply that all message instances of type Y should arrive at the process with that handler. You may want to do something like load balancing where half the messages of type Y go to one process, and the other half go to a tandem process. So message types are independent of Categories. The two concepts are orthogonal.
When a process is subscribed to a Category, there is no guarantee to the subscriber about the message types that a producer sends to that Category. It is easy to imagine a process receiving messages it does not know how to handle. The sender can't force the receiver to write code, but the sender can put any Category on a message it wants. So Categories are independent of message types. The two concepts are orthogonal.
Now. With respect to hierarchy. Message type names can be declared within a hierarchical namespace. That can be pretty useful. At the end of the day, however, they are simply some strings, or bit strings. In a sophisticated system that maps message types to message classes (code), the class hierarchy may mirror the type name hierarchy, and have interesting semantics (like a handler for a base message class being able to handle a derived message class). But mostly, message type name hierarchy is useful to avoid collisions.
In systems like JMS, Categories (Topics) are also hierarchical. This is also done to avoid collisions in the topic namespace, and for organization. But it is also useful for wildcard subscription.
Now "the" question: are Categories within the Message Type Hierarchy, or are Message Types within the Category hierarchy? Or are they orthogonal to one another? I submit that a message of a given type means the same thing no matter which Category it arrived on. Further, the same message type can be sent to any Category and a Category can transport any number of different message types.
Since there is only one message exchange system, Categories cannot be reused for two purposes without merging the message streams. That leads to inefficiency. If you reuse a message type name for two different purposes, you run the risk of breaking handler code with what appears to be a malformed message. That leads to crashes. You could permit that kind of reuse, and institute policy and testing to keep those things from mingling (e.g. reuse message types, but only on different topics), but it is a looming disaster. I would put in some coordination mechanism or name spacing to keep the mingling from happening at all.
So what are the consequences:
- There is no need to include Category when registering a message handler.
- Category subscription occurs separately from handler-to-message-type mapping, and affects the entire process.
- There is no need to build a message dispatcher that looks at Categories.
Unless you talk about virtual hosts, or virtual processes, multiple independent connections to the message system, thread-local subscriptions. You can do *anything* in software. But should you?
Thursday, October 28, 2010
Use of public/private keys to avoid a race condition
I inherited an interesting technique when I took over the server of SHSO. The use of signatures to avoid a race condition that can occur when a player is handed off between hosts. The use case is: the client requests that the Matchmaker connect them to a game "room" server that has a new game session starting. That room needs correct information about the player, what level they are, what they own, etc. How do you get it to the room before the client connects to that room and the data is needed? A couple of approaches:
A quick review of cryptography. Yes, I am totally oversimplifying it, and skipping a lot of the interesting bits, and optimization and stuff. However, it is fun to talk about...
A public/private key works by taking advantage of mathematics that is easy to compute in one direction, but really hard to compute in the other direction. The most common is factoring very large integers that are the product of two very large prime numbers. There is only one way to factor the product, but you have to compute and try pretty much every prime number up to the square root of the product, and that can take a looong time.
A public key can be used to encrypt plain text, and the private key is the only thing that can be used to unencrypt it. That means only the owner of the private key can read the plain text (including any else that had access to the public key).
On the other hand, a signature is created by *unencrypting* the plain text using the private key. The public key can then be used to *encrypt* the signature and test if the result equals the plain text again, thereby verifying the signature, and proving that the signature and plain text came from the owner of the private key exactly as they sent it.
Back to the story...the player data is signed using the private key by the Matchmaker and delivered to the client when the Matchmaker directs the player to the correct room. The client cannot tamper with their data without getting caught. The client then sends the data to the game room with the signature when it connects. The room server checks the signature using the public key, and can tell that the data is unmodified and came indirectly from the Matchmaker.
Why not just encrypt the data? The room server could have been set up to be able to unencrypt. Answer: The client wants to read and use its player's data. It wouldn't be able to do that if it were encrypted. And sending it twice (plain, and encrypted) is a waste.
One interesting thing to note is that the client never saw the public, nor the private key.
OK. I know it seems pretty wasteful to send all this data down to the client, just to have it sent back up to a different host in the server. After all, we are talking about bandwidth in and out of the data center, and more importantly, bandwidth in and out of the client's home ISP connection. Only half bad. The client needed the data anyway. It is not the greatest approach, but it is what we have. As Patton is quoted: A good solution applied with vigor now is better than a perfect solution applied ten minutes later.
BTW, another reason this was built this way was that originally the system couldn't predict which room the player would wind up in, so the client needed to bring their data with them.
And that is a segue to the topic of scaling across multiple data centers. It might start to make sense of that extra bandwidth question.
- You don't. You just leave the client connected but in limbo until their data arrives through the back end asynchronously. This is a pretty normal approach. Sometimes the data arrives before the client makes the connection. So you have to cover both of those cases.
- You don't. You leave the client in limbo while the room fetches the data through the back end synchronously. This is also pretty normal, but blocks the thread the room is running on, which can suck, especially if other rooms on the same host and process also get blocked. Yes, you could multithread everything, but that is not easy (see my manifesto of multithreading!). Or you could create a little state machine that tries to remember what kind of limbo the client is in: just-connected, connected-with-data-fetch-in-progress, etc. Personally, I don't allow the processes that run the game logic to open a connection directly to the DB and do blocking queries. DB performance is pretty erratic in practice, and that makes for uneven user experience.
- Or have the data arrive *with* the connection. From the client. Interesting idea. But can you trust the client? That is where signed data comes in.
A quick review of cryptography. Yes, I am totally oversimplifying it, and skipping a lot of the interesting bits, and optimization and stuff. However, it is fun to talk about...
A public/private key works by taking advantage of mathematics that is easy to compute in one direction, but really hard to compute in the other direction. The most common is factoring very large integers that are the product of two very large prime numbers. There is only one way to factor the product, but you have to compute and try pretty much every prime number up to the square root of the product, and that can take a looong time.
A public key can be used to encrypt plain text, and the private key is the only thing that can be used to unencrypt it. That means only the owner of the private key can read the plain text (including any else that had access to the public key).
On the other hand, a signature is created by *unencrypting* the plain text using the private key. The public key can then be used to *encrypt* the signature and test if the result equals the plain text again, thereby verifying the signature, and proving that the signature and plain text came from the owner of the private key exactly as they sent it.
Back to the story...the player data is signed using the private key by the Matchmaker and delivered to the client when the Matchmaker directs the player to the correct room. The client cannot tamper with their data without getting caught. The client then sends the data to the game room with the signature when it connects. The room server checks the signature using the public key, and can tell that the data is unmodified and came indirectly from the Matchmaker.
Why not just encrypt the data? The room server could have been set up to be able to unencrypt. Answer: The client wants to read and use its player's data. It wouldn't be able to do that if it were encrypted. And sending it twice (plain, and encrypted) is a waste.
One interesting thing to note is that the client never saw the public, nor the private key.
OK. I know it seems pretty wasteful to send all this data down to the client, just to have it sent back up to a different host in the server. After all, we are talking about bandwidth in and out of the data center, and more importantly, bandwidth in and out of the client's home ISP connection. Only half bad. The client needed the data anyway. It is not the greatest approach, but it is what we have. As Patton is quoted: A good solution applied with vigor now is better than a perfect solution applied ten minutes later.
BTW, another reason this was built this way was that originally the system couldn't predict which room the player would wind up in, so the client needed to bring their data with them.
And that is a segue to the topic of scaling across multiple data centers. It might start to make sense of that extra bandwidth question.
Subscribe to:
Posts (Atom)