Colyseus Extensions to Mercury

Recall that each object within the game instance needs to discover objects within its area-of-interest for running its think functions. To locate these objects, each object periodically registers a persistent query or a subscription for objects within its area-of-interest. For example, in Quake II, this is the region of space which is visible to the primary object from its current location. While each object in any game may have a large number of attributes (e.g., x,y & z coordinates, health, textures, ammo, etc.), only a small subset of these, which we call naming attributes (e.g. x,y & z coordinates, team, etc.), are ever used to identify if an object is within another's area-of-interest. Objects periodically send events or publications containing the current values of these naming attributes, as well as their GUID and SID.

We use a modified version of Mercury to handle the routing of publications to the interested subscribers. As a first step, we convert Mercury from a insert/query system to a publish/subscribe system. We do this in much the same way that the Scribe [14] system uses standard DHTs. Subscriptions are routed much like queries and stored for an short period of time. Publications are routed like data items. However, when a publication reaches its routing destination, instead of being stored, it is matched against all subscriptions and delivered to any interested subscribers. We call the node where the matching occurs the rendezvous point (RP). Note that the resulting Mercury publish-subscribe system supports much richer content-based subscriptions than the Scribe system.

Mercury's usefulness for this setting arises from a number of properties: first, objects can register their interests as multi-attribute range-based queries - well suited to describing regions of space. Second, Mercury supports low-latency delivery by providing a tunable⁶, logarithmic bound on the number of hops required for publication delivery. Third, since Mercury stores data contiguously in the routing overlay and supports caching of routes, we can expect Mercury to perform especially well with the locality patterns of game object publications. We evaluate how well Mercury's caching works for our game publication workload in Section 7. Fourth, it balances routing load dynamically by assigning nodes appropriate responsibilities. For our Quake II design, it accomplishes an adaptive partitioning of the game world such that load balance is achieved. One weakness of Mercury is that it does not handle matching on a large number of attributes well. However, we find that area-of-interest filtering can be accomplished with a relatively small number of naming attributes.

We should note that even hop routing is insufficient for the interactive response required by games like Quake II. The $\log n$ hop delivery delay is mitigated to a large extent by the fact that Colyseus uses Mercury only for discovering primary objects; once discovered, replicas establish direct connections to the primaries for keeping themselves up-to-date. However, in certain situations (for example, when short-lived objects like missiles are created and fired), even discovering the primary copy very fast is important. To support better interactive response, we have made two key extensions to the above basic design: Soft-state Triggers and Predictive Publications/Subscriptions.