Hi! I’m a long-time lurker and a very occasional poster on these forums, but I’d like to introduce some of the things I’ve been working
on for the last few years, that I think will be of interest to many here.
The first is a new server-side middleware product for MMO games called SpaceBase (http://paralleluniverse.co/product). To MMO games, SpaceBase is two things: a low-latency 2D/3D spatial data store, and a concurrency/parallelization framework.
At the heart of SpaceBase is a state-of-the-art non-degrading and highly concurrent variant of the R-Tree that’s the core of the spatial data store. Unlike other spatial databases, SpaceBase is especially designed for tracking objects that are constantly moving. You put your game objects into SpaceBase, update them as they move, and perform region queries or spatial joins (say, for broad-phase collision detection). A single update takes ~15us, and a region query (returning ~5 objects out of 2 million) takes ~1.5us. That’s in terms of latency. In terms of throughput, because the underlying data-structure is highly-concurrent, you get nearly linear scalability with the number of threads (depending on how much they trample on each other spatially). In addition, SpaceBase can parallelize even a single query using the fork/join framework.
The other use for SpaceBase is as a concurrency/parallelization framework. If you write your game’s server not as a game loop, but in an event-based manner, you can pass your game logic, physics simulation, AI, etc., as callback to SpaceBase transactions/queries, and SpaceBase will execute them in the fork/join threadpool managed by SpaceBase, taking care of all synchronization for you. SpaceBase employs both lock-free techniques to minimize contention and cache-faults, as well as locks especially built to work hand-in-hand with fork/join for long-running transactions. Those locks don’t reschedule threads but, rather, reschedule fork/join tasks.
SpaceBase is implemented in Java and is intended to run embedded in the game process. It is proprietary, but we’ll gladly send evaluation copies to anyone who wants to try it out.
The other project I’d like to introduce is an open-source in-memory data grid called Galaxy (http://puniverse.github.com/galaxy/). In the near future SpaceBase will be able to run on top of Galaxy to scale horizontally in a cluster. But even when used without SpaceBase, Galaxy can be of use to MMO serveres that require horizontal scaling. Unlike all other IMDGs (Ehcache, Gigaspaces, Infinispan, Gemfire, Coherence, Hazelcast) that use a distributed hash-table (DHT) approach, Galaxy employs a software implementation of a cache-coherence protocol similar to the ones used to coordinate L1 caches in CPUs.
DHTs partition their objects based on their key’s hash, so for every object they quickly know which node it resides on. They have a worst-case scenario of 1 network hop per object access, but that’s the common case as well. Galaxy takes a completely different approach. It migrates objects from node to node as requested. The result is that while the worst case for an object access can be more than 1 network hop, the common case is 0 hops.
Galaxy is meant to serve as a platform for building distributed data-structures. For example, when SpaceBase runs on top of Galaxy, as the objects move in space, they also migrate from one cluster node to another, keeping nearby objects on the same node, while trying to maintain a similar number of objects per node. The result is a dynamically expanding/shrinking “region” nodes.
This blog post explains the reasoning behind Galaxy’s architecture: http://blog.paralleluniverse.co/post/26909672264/on-distributed-memory, and this three-part series describes Galaxy’s implementation in detail: http://blog.paralleluniverse.co/tagged/galaxy-internals
Galaxy is distributed under the LGPL, and is still considered experimental. You can find it on GitHub here: https://github.com/puniverse/galaxy
I would love to get your feedback!
Thanks!