tales from the darkstar
Of protocols and transports
As mentioned in my previous post I worked on the Darkchat server which was going to be demoed and used at JavaOne 2009. The server would be on the public network so that attendees could access it during the convention. For this to work we needed to to be able to limit logins to authorized clients (JavaOne attendees). The details of creating and distributing account usernames and passwords were being worked on and early-on it looked like we would have a way for attendees to register for an account, and for them to create a username and password (the final solution was way cooler than this scheme, perhaps a story for later). The default protocol and transport that comes with Darkstar provides very little security for client logins. The Simple SGS protocol sends usernames and passwords in the clear over TCP. I was concerned that passwords could be snooped (humm.. a conference full of computer geeks, what were the chances? - for answer see below1) and though this was only a demo, what if someone used an important password thinking that it was being protected. In looking at the options and the time that was available two solutions seemed possible, to create an SSL transport to replace TCP, or create a new protocol that included some level encryption. To me, creating a new protocol seemed the easier of the two.
In the Darkstar server are two services that handle the bulk of the communication duties with the client, the client session service and the channel service. These two services implement the most of the ClientSession and Channel semantics that the application sees. They are built on top of a protocol layer. This layer determines the format and content of the messages exchanged between the client and the server. The protocol layer is, in turn, built on top of a transport layer. The transport layer deals with the network connection with the client.
The ComponentRegistry and TransactionProxy objects provide access to the components within the Darkstar kernel such as the data service or the task scheduler.
The ProtocolAcceptor object is responsible for initial client connection and login, including authentication. The client session service registers its interest with the acceptor by calling accept(), passing in a ProtocolListener object. When a successful client connection and login is made the acceptor should call ProtocolListener.newLogin() passing in the authenticated Identity of the client, a SessionProtocol object, and a completion handler. It is the SessionProtocol object which implements the outgoing messages needed by the session and channel services. The implementation must be able to handle sending a session and channel message, a channel join and leave message, and be able to disconnect the client. Exactly how these messages are sent is up to the SessionProtocol implementation and the client. When done processing the new login, the ProtocolListener will call the completion handler with a SessionProtocolHandler object. This object handles the incoming session and channel messages as well as logout and disconnect. It is the responsibility of the protocol implementation to call the SessionProtocolHandler object as needed. Piece of cake.
Now the protocol layer needs only be responsible for the when and what of the messages exchanged between the server and the client. It does not need to worry about the underlying network transport. It can, but it does not need to. There is a set of interfaces in the internal APIs that define a network transport layer. Through these APIs the protocol layer can use existing implementations of network transports and transport providers can code against the API to create new transports. But I will leave the discussion of transports for another post.
There is one item that deserves extra explanation. One of the methods that the protocol acceptor must implement is getDescriptor(). This method returns a ProtocolDescriptor object. The information in this object is used when a client connection must be redirected to another node. In particular, the getConnectionData() returns an array of data that contains the protocol and transport specific information needed by the client to connect to the node described by the descriptor. For example the byte array might contain the IP address and port number needed for a TCP connection. The server does not look at the data, but the client protocol must be able to interpret it. In general, if using the TCP transport supplied with Darkstar, getConnectionData() needs simply to return the data from the transport descriptor's getConnectionData() method. (see either the SGS simple protocol, or the challenge-response descriptor implementations).
For what Darkchat needed, the above steps were rendered trivial by simply copying the SGS simple protocol sources (found in the com.sun.sgs.impl.protocol.simple package) and modifying them to add in a couple of new protocol messages. The new protocol implements a challenge-response login exchange where the server sends a randomly generated challenge to the client and the client responds with their password encrypted using the challenge. The new messages were the client's request for challenge, and the server's message containing the challenge. The new protocol can be found in the Darkchat server sub-project in the com.sun.sgs.impl.protocol.challengeresponse package.
A similar tact was used to create the client-side protocol handler. The client challenge-response code was based on the sources from the sgs-java-client project. Unfortunately the client code in Darkchat is a little hard to follow for two reasons. First, the sgs-java-client code is hard to follow in the first place. Second, there is an extra two layers in the client side stack, one to allow replacement of the underlying Java SE client with one for Java ME, and the second to handle the conversion from Java to JavaFX. The Java ME client was never completed and does not exist in the source tree. Maybe something for the future!
Posted at 05:09PM Jul 27, 2009 by Keith Thompson in Project Darkstar | Comments[0]
I'm baaack.....
Posted at 01:36PM Jul 17, 2009 by Keith Thompson in Project Darkstar | Comments[0]
I can write that service in two lines...
Folks on the forums have requested facilities to support iterating over objects, primarily for debugging, and for obtaining objects by object ID. This capability is not part of the standard API available to a Darkstar application, however it is possible to write a manager to provide this functionally. It turns out that such a manager is quite simple, and can provide a straightforward example of how to create a manager. This note describes how to write, install, and access a new manager and its backing service. For a more rich (read complex) example, check out Seth's blog on writing services.
In Darkstar, managers provide many of the application level APIs. By creating a new manager one can extend the API set with functions that application could not otherwise implement. Underneath the managers, not directly visible to the application, are corresponding services. Services provide the functions needed by their managers and have access to the other services in Darkstar that applications do not have access to.
The example manager described below will be built on a service which will use the DataService to provide the desired functionality.
A Darkstar service must implement the com.sun.sgs.service.Service interface and have a specific constructor. Ignoring Javadoc, import and package statements, the class declaration and constructor look like this:
public class ObjectAccessService implements Service {
private final DataService dataService;
public ObjectAccessService(Properties properties,
ComponentRegistry systemRegistry,
TransactionProxy proxy) {
dataService = proxy.getService(DataService.class);
public ManagedReference<?> createReferenceForId(BigInteger id) {
return dataService.createReferenceForId(id);
}
public BigInteger nextObjectId(BigInteger objectId) {
return dataService.nextObjectId(objectId);
}
return ObjectAccessService.class.getName();
}
public void ready() throws Exception {
// ignore
}
return true;
}
public class ObjectAccessManager {
private final ObjectAccessService service;
public ObjectAccessManager(ObjectAccessService service) {
this.service = service;
}
public ManagedReference<?> createReferenceForId(BigInteger id) {
return service.createReferenceForId(id);
}
public BigInteger nextObjectId(BigInteger objectId) {
return service.nextObjectId(objectId);
}
In order to make the new manager available to the application, both it and its service needs to be installed in the Darkstar server. This is done by adding the following two items to the server's configuration file:
com.sun.sgs.services=mypackage.ObjectAccessService
com.sun.sgs.managers=mypackage.ObjectAccessManager
Obviously the manager and server classes need to be in the class-path of the server.
With the manager installed it is a simple matter for the application to access it:
ObjectAccessManager accessManger = AppContext.getManager(ObjectAccessManager.class);
Though this is an extremely simple example, it does provide a means to iterate over the objects in the system, by their identifier, and given an identifier, get the object. It also demonstrates the basic manager-service operation in Darkstar.
Posted at 06:07PM Oct 20, 2008 by Keith Thompson in Project Darkstar | Comments[0]
Two wrongs don't make a right, ...
B. Server using only modification detection
1"Two wrongs don't make a right, but five rights will get you back on the highway..." refers to the rule from way back, used by Sun East Coast travelers to remember how to get on Rt 101 south from the rental car lot at the San Francisco airport. I often think of it when I see something take a lot of twists and turns. Original author unknown. (Note: things have changed A LOT at SFO, so the rule is no longer valid. At least for getting onto 101)
2The challenge turned out to be one of those DOH! moments. I was certain I had marked all of the cases where the robot changed their own game state (position, hit points, etc). I was also careful to not mark the cases where the game state was not modified. No sense in writing an object that was not changed. Now the way the robot moves is that a task is run periodically that causes the robot to move, attack, etc. and the way that task is scheduled is by calling TaskManager.scheduleTask() at the end of the task. The actual scheduling code looks like this:
4Note that all of the tests described in this note were run with the server using Berkeley DB Java Edition. The C version behaves somewhat differently due to in the way the two version preform locking and can produce very different results when running the same application. At two robots per game, the two versions showed similar relative behavior across the different tests. At 10 robots per game the C version failed to handle the load when modification detection was enabled. For the snowman game the JE seems to scale much better than the C version. Exactly why is not completely understood, and may be worth a post just on that topic. So for now, deciding which DB is best for any given application is hard without actually testing both.
Posted at 03:51PM Oct 03, 2008 by Keith Thompson in Project Darkstar | Comments[0]
Case study: Improving login performance in Project Snowman
Project Snowman is a multiplayer capture-the-flag type game. The goals of the project were to showcase techniques for building a game server using Project Darkstar and to demonstrate the resulting benefits. Part of that demonstration was to show the snowman game server handling hundreds of client logins. To this end a client simulator was created as part of Project Snowman. The client simulator presents a simple GUI which allows the user to move a slider, selecting the number of clients to login to the server and play the game. The first implementation of the client simulator was designed to login clients as fast as possible. When we tested it against the game server the server was swamped after only a couple of hundred logins, performing far below our expectations. The following outlines the investigation into this initial poor login performance and the steps taken to improve it. Before we dive into the investigation, lets look at the login requirements of the snowman game. Being a demonstration, the snowman game login is relatively simple. The server collects clients, or players, as they login, and once the required number of players-per-game is reached, a game is created and started. There is no consideration of which client joins which game, so login identity or order is unimportant. The simple login requirements naturally led to a fairly simple initial implementation. As a Darkstar programer is aware, when a client logs-in, the loggedIn() method is called on the application's AppListener class. The snowman's app listener class looked something like this: public class SnowmanServer implements Serializable, AppListener {
private Collection<SnowmanPlayer> waitingPlayers = // some unordered collection...
public ClientSessionListener loggedIn(ClientSession session) {
AppContext.getDataManager.markForUpdate(this);
SnowmanPlayer player = new SnowmanPlayer(session));
waitingPlayers.add(player);
if (waitingPlayers.size() == NUM_PLAYERS_PER_GAME) {
startGame(waitingPlayers);
waitingPlayers.clear();
}
return player; // player is a ClientSessionListener
}
In this pseudo code, when a client logs-in a player object is created and then added to the list of waiting players. If there are enough players to start a game, startGame() is called, with the set of waiting players. The waiting set is cleared so that the process can repeat.
What the #^@%!& is going on?
Though the login code above was straightforward, it was not immediately clear why it performed so poorly. One of the more useful tools for determining what the Darkstar server is doing is the profile listeners. These can be found in the package:
com.sun.sgs.impl.profile.listener
and Seth has blog entry that has more detail on using Darkstar's profiling sub-system. The particular profile listener that was useful in our case was SnapshotProfileListener. To enable this listener, add the following to the Darkstar server's properties:
com.sun.sgs.impl.kernel.profile.listeners=com.sun.sgs.impl.profile.listener.SnapshotProfileListener
This listener reports, on ten second intervals, the number of successful tasks, the number of tasks run, and the average size of the task queue. It reports this data on server port 43007 and can be easily monitored remotely using telnet:
telnet server.host 43007
will produce output looks something like this:
The report above is showing very low contention, 9,618 tasks succeeded out of 9,629 and the average queue size during that time was less than two tasks. During our simulated login "storm", the profiling information showed that the average queue size rapidly increased, into the hundreds, while the number of successful tasks was much lower than the number of tasks run. It is not unusual to see tasks failing, aborting and rescheduling tasks is how Darkstar manages data contention between competing tasks. However, the number of successful tasks was a fraction of the tasks started, which means that something was highly contentions resulting in very little progress by the server. One way we verified this was to add a configurable delay to the client simulator. When client logins were spaced 200 ms apart the number of failed tasks was greatly reduced as well as the average queue length. Unfortunately, five logins per second was not very exciting.
Examining the loggedIn() method above it is clear that each client login modifies the SnowmanServer object (the app listener) when it changes the contents of waitingPlayers. Since there is only one app listener in the server, and only one task can modify the same object at a time it makes the app listener a single choke point for all logins. Creating a new player and adding it to the waiting set is trivial, and even though there is contention on the app listener object, these login tasks should finish quickly, and for the most part keep out of each other's way. Starting a new game is a different story. To start a new game the server must create a game object, two flag objects, and some number of robot player objects. Each of which are managed objects. In addition, a channel is created and each "real" player (non-robot) joins that channel. While this lengthy game creation is taking place, no other login tasks can succeed because the app listener is being modified. Even worse, it is highly likely that occasionally the game creation will fail, throwing away all that was done.
Since logging-in without creating a game was quick, it seemed desirable to make all logins that speedy. To achieve this, the game creation was moved to a separate task:
public ClientSessionListener loggedIn(ClientSession session) {
AppContext.getDataManager.markForUpdate(this);
SnowmanPlayer player = new SnowmanPlayer(session));
waiting.add(player);
if (waiting.size() == NUM_PLAYERS_PER_GAME) {
AppContext.getTaskManager.scheduleTask(new StartGameTask(waiting));
waiting.clear();
}
return player; // player is also ClientSessionListener
private class StartGameTask implements Task {
Collection<SnowmanPlayer> waitingPlayers = // some unordered collection...
StartGameTask(Collection<SnowmanPlayer> waiting) {
waitingPlayers.addAll(waiting);
}
public run() {
statrtGame(waitingPlayers);
}
By removing the game creation from the login, we shortened the login task in the case that a game is ready to start. Since there is no contention between game creation tasks, those are unlikely to abort. This simple fix was quite effective in reducing task failures, verified by the profiling information, and allowed a much higher rate of client logins. Note that the collisions between the login tasks was reduced, the contention remained unchanged. The next step was an effort to actually reduce the contention.
One of the ideas that has been kicking around the group to deal with the multiple writer problem is to use a series of independent queues, with multiple writers feeding the tops of the queues, and another set of readers emptying the queues. The theory is that if the queues are independent, contention would only occur when the same queue was accessed for write. If there were many queues the chance that two writers hit the same queue at the same time could be small. Mapping this scheme into the snowman server code, we added a set of queues to the app listener object and when a client logged-in, the newly created player was placed into one of the queues. On the back side, a (new) task would read off the queues until it found enough players to start a game. Implementing this was not as straightforward as it sounds. In the app listener you could not just add an array of queues and expect any benefit. This is because changing the state of any one of the queues effectively changes the state of the app listener. We would sill have the single point of contention. Instead, the queues needed to be wrapped in a ManagedObject. This allows the app listener to keep an array of ManagedReferences to the queues. Now the app listener is immutable (in the context of the login task) and no longer a point of write contention (Managed objects, such as the app listener, accessed only for reading can be shared). Ignoring for now the task reading the end of the queues, here is the new app listener and queue objects:
private ManagedReference<Deque<ManagedReference<SnowmanPlayer>>>[] waitingDeques;
public void initialize(Properties arg0) {
this.waitingDeques = new ManagedReference[NUMDEQUES];
for(int i = 0; i < waitingDeques.length; i++) {
Deque<ManagedReference<SnowmanPlayer>> deque = new ManagedDeque<ManagedReference<SnowmanPlayer>>();
waitingDeques[i] = AppContext.getDataManager().createReference(deque);
}
AppContext.getTaskManager().scheduleTask(new MatchmakerTask(waitingDeques));
}
public ClientSessionListener loggedIn(ClientSession session) {
SnowmanPlayer player = new SnowmanPlayer(session);
BigInteger id = player.getSnowmanPlayerRef().getId(); // get a ManagedReference to the player
BigInteger index = id.mod(BigInteger.valueOf((long)NUMDEQUES));
waitingDeques[index.intValue()].get().add(player.getSnowmanPlayerRef());
return player;
}
class ManagedDeque<E> extends LinkedList<E> implements ManagedObject {}
}
There are a couple of important things to note here. First is the use an array of ManagedReferences to keep track of the queues in the app listener. Since the queues are ManagedObjects their persistence is handled by Darkstar so the app listener does not need to maintain references to the queues directly. So a change to the queue does not translate into a change in the app listener object. A potential trap is in selecting a queue to place the player in. A temptation might be to keep a index in order to insert into the queues round-robin or to keep a Random object to distribute the players randomly. The problem would be that an int index or the Random object's state would change, and therefore the app listener would no longer be read only. Luckily, in this example, the player's (ManagedReference) ID can be used to create an index.
On the other end of the queue, the MatchmakerTask can be implemented several different ways. Here is a fairly straightforward approach:
public class MatchmakerTask implements Task, Serializable
{
private List<ManagedReference<SnowmanPlayer>> waitingPlayers;
private ManagedReference<Deque<ManagedReference<SnowmanPlayer>>>[] waitingDeques;
public MatchmakerTask(ManagedReference<Deque<ManagedReference<SnowmanPlayer>>>[] waitingDeques) {
this.waitingPlayers = new ArrayList<ManagedReference<SnowmanPlayer>>();
this.waitingDeques = waitingDeques;
}
public void run() throws Exception {
boolean playersFound = false;
for(int i = 0; i < waitingDeques.length; i++) {
ManagedReference<SnowmanPlayer> nextPlayer = waitingDeques[i].get().poll();
if(nextPlayer != null) {playersFound = true;}
waitingPlayers.add(nextPlayer);
if(waitingPlayers.size() == NUM_PLAYERS_PER_GAME) {startGame(waitingPlayers);}
break;
}
// if no players are found in the queue during this iteration
// schedule a delay for the next polling cycle
// otherwise, schedule the next cycle to occur immediately
if(playersFound)AppContext.getTaskManager().scheduleTask(this);elseAppContext.getTaskManager().scheduleTask(this, POLLING_INTERVAL);}
}
Basically, the task loops once through the set of queues collecting players. If enough for a game are found, a game is started. Before the task ends, it schedules itself to be run again. One could imagine changes in this task, like creating the game in its own task or polling the queues in a more round-robin fashion, but the important accomplishment here is the reduction in contention with the client login task. The code improvements to this point have left only these two points of contention: 1) between login tasks when inserting to the same queue, and 2) between login task and the match maker task when inserting and removing, respectively, from the same queue.
Though the changes so far have achieved a more than satisfactory login rate, there is one more improvement we made. Darkstar provides a utility data structure that we could use as a drop-in replacement for our ManagedDeque. The class com.sun.sgs.app.util.ScalableDeque is an implementation of Deque that provides concurrent, non-contentious, inserts and removals (as long as there is more than one element in the queue). This further reduces the contention between the client login task and the matchmaker task during a login storm.
And there was great rejoicing...
Project Snowman was created by a bunch of folks, and to give credit where credit is due, Tim Blackman, long time Project Darkstar dude, had some time ago mentioned to me the idea of using multiple queues to reduce contention. Owen Kellett, who like myself is a bit newer to Darkstar, implemented the multiple queue mechanism in the snowman server. And David Jurgens, our perennial intern, implemented ScalableDeque. Owen has also posted a blog about Project Snowman that is worth reading. I know Chuck Norris would want you to.
Posted at 10:34AM Sep 25, 2008 by Keith Thompson in Project Darkstar | Comments[1]
in the beginning
So, this is my first entry into the world of blogging. It has come somewhat as a necessity, as I have some material that I wish to disseminate and this, blogging, seems to be the forum of choice. I am currently working on Project Darkstar and I expect most, if not all of my posts here will be related to that effort.
Posted at 10:04AM Sep 24, 2008 by Keith Thompson in Personal | Comments[0]
Today's Page Hits: 20