About

One Universe, Many Scales

One epic meta-game design I first remember talking about a decade ago while working on Warhammer Online is the multi-scale online game: a system of interconnected games in which you choose to be a solo operative, work in a small group, or command epic forces or huge space fleets and influence a single universe however you choose to contribute. It’s a recurring game design meme that I’ve talked about several times since and I’m sure many others have had similar discussions around the globe ever since multiple computers were connected together.

So, I’m super excited to see CCP games take a huge step towards realizing this epic game design dream today by linking the internet spaceship game EVE online with the brand new PS3 first person shooter Dust 514. Players piloting giant spacecraft in EVE online will be able to swoop down from space and interact with other players running around on the planet’s surface playing Dust 514. This is very cool.

I’m also very excited that the two games are connected using the CREST API that I helped to build: an API that will be usable everywhere. Not only will you be able to interact with the EVE universe at every scale from the human to the intergalactic, the clients used to connect to the universe will work on every scale of device from phones to desktops and every scale of interaction from web tools built by 3rd parties, through 5 minute casual experiences to epic space battles played out in full 3D over hours and campaigns played out over years.

Today’s connection of EVE and Dust is a historic moment, but it’s just the beginning of what will be a very exciting second decade for the universe of New Eden.

Creatarr

cc image by vdu, j4mie

One of the things I’ve been tinkering with since leaving Linden Lab is Creatarr: a creative, collaborative social game. Creatarr’s goal is to bring some of the magical collaborative creation found in Second Life to a wider audience and to push creativity in social games and the web beyond virtual farming and impact text on animal pictures.

I quickly got busy building the CREST API for CCP and I’m likely to have even less free time when I start my new gig, but Facebook are happy for me to continue to tinker with Creatarr and I like shipping code, so I’ve decided to make Creatarr public and run it for as long as people are playing. There are plenty of rough edges, but there are also some neat ideas and plenty of fun to be had, so head over to creatarr.com and dive in.

Thanks to @mrkemeny, Irene Soler, Chris James, @yandle and @profaniti for helping to build Creatarr.

Following In My Father’s Footsteps

Tintin Hair

From 2 years before I was born, until just before I started working on Second Life at Linden Lab, my Dad worked at an innovative technology company with a large consumer photography business: Kodak. From January next year I’ll be working at an innovative technology company with a large consumer photography business: Facebook.

Looking at the march of technology from the perspectives of these companies is amazing. I had a summer job building my first web application for Kodak while I was studying Computer Science in Nottingham and remember one of the researchers there joking that film needed to last a long time as a roll would often have pictures of christmas trees at either end with a summer holiday in the middle. Photography was so expensive that people would only take a few dozen pictures a year. Now we happily take a dozen pictures of our lunch, wouldn’t consider buying a telephone without a built in multi-megapixel camera and people upload hundreds of millions of images to Facebook every day.

While the cost of creating photos has fallen to almost zero, their value hasn’t. Some of my most enjoyable moments recently have been looking at and commenting on the latest pictures of my brand new nephew, Charlie, on Facebook and so it goes for Facebook’s other billion users. Photos that are now so cheap to create that Kodak has filed for chapter 11 protection become social objects that are so valuable that Facebook can host the photos for free and still make a good business from advertising around the conversation.

Working for Facebook might seem like a strange move after a decade working on 3D environments, but virtual worlds like Second Life and EVE are also social spaces, just with virtual nightclubs or space battles as the social objects. While 3D environments allow more immersion than Facebook, the price is a much higher barrier to entry. Although a few people from my family tried Second Life while I worked at Linden Lab: most of my family use Facebook already. My brother could create a gallery of pictures of my nephew in Second Life and we could meet there to talk about them, but then most of my nephew’s other aunts and uncles wouldn’t be able to join us. Ubiquity trumps immersion. Virtual worlds like Second Life still need their iPod moment if they’re going to cross the chasm from niche technology used by gamers, early adopters and academics to become a mainstream communication technology. Even though Second Life is free to use and paid for by the publishers of the 3D content, it’s still too hard to navigate for most people to use almost a decade after its launch.

Facebook is already used by a billion people to keep in touch, while still evolving and developing at an incredible pace. I’m going to help new uncles connect with new nephews around the world while working on new technologies, which I think is going to make Facebook a fun and rewarding place to work.

After that, who knows? My Dad’s working on some pretty amazing stuff these days: if I keep following in his footsteps and change keeps accelerating, the next thing is science fiction now, just as Second Life and Facebook were in 1975.

Caching Shared, Private Data With Ningx

As with many other social services, a large amount of the data in EVE Online and Dust 514‘s New Eden universe is shared between subsets of users. Some corporation data should only be accessible to the corporation’s members, market prices should only be accessible to capsuleers and infantry in the region for example.

In order to enforce these rules, the EVE cluster performs a number of access control checks whenever a request is made from an EVE client to the cluster. As a large fraction of calls to the CREST API require these checks to be performed, it would be nice to perform them in Nginx to avoid the overhead of having to make a request to the EVE proxy before returning the cached responses from Nginx. However, duplicating the access control logic within Nginx and trying to keep the two access control implementations in sync is likely to be error prone. As the spying metagame in EVE is arguably bigger than the game itself the consequences of getting the access control logic wrong could be huge. Internet spaceships are serious business.

Fortunately, it’s possible to combine and reuse the load balancing and vary header support techniques previously discussed to avoid both excessive calls from Nginx to the cluster and access control logic duplication.

In addition to annotating responses from the cluster with the address of the proxy containing the character’s session, we also annotate the response with the character’s location, corporation and various other character meta data. The same logic that performs access control checks in the cluster can then add these response headers to the list of vary headers when generating a cache key for a later request on behalf of the same character. Rather than duplicating access control logic, Nginx just needs to make sure that only response headers from the cluster are used for these access control vary headers. If a particular URI is annotated to vary on language and region for example, Nginx will allow the language to be supplied by the client, but the region must be supplied by the cluster in a previous response for the same character.

By reusing the stateful load balancing and vary header support we added to Nginx we’re able to cache data shared between multiple characters without duplicating complex access control logic implemented by the EVE cluster: reducing the CREST load on the EVE cluster without breaking the metagame.

Thanks to @jonastryggvi for working with me on the Caching support and @CCPGames for allowing me to blog about it.

Adding Vary Header Support To Nginx

Although Nginx supports proxy caching it doesn’t provide support for the HTTP Vary header out of the box. This is a problem if you want to use Nginx to proxy different versions of the same URI which Vary on Content-Language or proxy different representations of a RESTful resource specified via the Accept header.

Fortunately it’s relatively easy to add support for the Vary header using the Nginx Lua module and a small amount of Lua, which is much easier than building and maintaining a 3rd party module and doesn’t greatly impact performance.

First, we define a dictionary in the nginx config which will store a mapping from URIs to Vary headers:

lua_shared_dict uriToVary 10m;

Next we define the default location in the nginx config, which will use the lua ProxyRequest function to make a subrequest to /proxy_request then store the Vary header in the response in the dictionary.

location / {

    # make subrequest to /proxy_request, then store response headers
    content_by_lua '
        local vary = require("vary")
        local response = vary.ProxyRequest()
    ';
}

function ProxyRequest()

    -- make subrequest and capture response
    local response = ngx.location.capture("/proxy_request", {
        method = GetRequestMethod(ngx.var.request_method), body = ngx.req.get_body_data()})

    -- forward HTTP headers from response
    for k,v in pairs(response.header) do
        ngx.header[k] = v
    end

    ngx.shared.uriToVary:set(ngx.var.request_uri, response.header["Vary"])

    -- forward status and body from response
    ngx.status = response.status
    ngx.print(response.body)

    return response

end

Finally, we define the /proxy_request location which will use the lua RewriteCache function to combine the uri with the vary headers to generate the final cache key used by the proxy_cache module.

location /proxy_request {
    internal;

    # set defaults
    set $noCache 1;
    set $cacheBypass 1;
    set $cacheKey nil;

    # rewrite using stored data
    rewrite_by_lua '
        local vary = require("vary")
        vary.RewriteCache()
    ';

    # proxy request
    proxy_cache_bypass $cacheBypass;
    proxy_no_cache $noCache;
    proxy_cache_key $cacheKey;
    proxy_cache API_CACHE;
    proxy_pass $proxy$request_uri;
}

function RewriteCache()

    local varyOn = ngx.shared.uriToVary:get(ngx.var.request_uri)
    local cacheKey = nil

    -- if vary unknown for this uri, bypass cache and do not cache
    if varyOn == nil then
        return
    end

    cacheKey = ngx.var.request_uri .. GenerateCacheKey(varyOn, ngx.req.get_headers())
    ngx.var.noCache = 0
    ngx.var.cacheKey = cacheKey
    ngx.var.cacheBypass = 0

end

function GenerateCacheKey(varyOnStr, requestHeaders)

    local cacheKey = ""
    for part in string.gmatch(varyOnStr, "([^,%s+]+)") do

        if requestHeaders[part] then
            cacheKey = cacheKey .. ":" .. requestHeaders[part]
        end

    end

    return cacheKey

end

The first time a URI is requested the cache will be bypassed, but the Vary header from the response will be stored in the shared dictionary. The second time the URI is requested the cache key will be generated from the URI and the appropriate request headers specified in the vary header and the response will be cached. When the URI is subsequently requested with the same set of headers it will be served from the cache.

Note that when the shared dictionary is full it will evict old entries using an LRU scheme. Nginx will generate “ngx_slab_alloc() failed” errors when this occurs, but these can safely be ignored.

Thanks to @jonastryggvi for working with me on the Vary support and @CCPGames for allowing me to blog about it.

Load Balancing Stateful Services With Nginx

The EVE online network architecture uses stateful proxy servers which manage sessions for players connected to the cluster via the EVE client. The client sends requests to the proxy which are forwarded on to sol servers maintaining the game state and the sols send notifications to the proxy which are sent on to the client.

In developing the CREST API we extended the EVE proxies to talk HTTP, then added nginx reverse proxies to the service to provide SSL termination and caching while shielding the EVE proxies from potentially malicious requests.

So, how does nginx know which EVE proxy to send a request to? In the first instance, it just guesses. We set up a set of proxies and use proxy_pass to have nginx just pick one.

upstream eveproxies {
    # List all eveproxies
}

location / {
    proxy_pass http://eveproxies;
}

The proxy can then use the CCP cluster’s RPC machinery to find the character’s session. If nginx has been lucky the request is processed and the response sent back to nginx and from there to the player. If no session exists for the character on any proxy a new session is created and then the request processed as above. If the character session is on a different node the proxy returns an X-accel response to a location which extracts the correct proxy URI from the path and resends the request.

location ~* ^/internal_redirect/(.*) {
    internal;
    proxy_pass http://$1$is_args$args;
}

The performance of this approach can be greatly improved by caching the mapping of authorization headers to proxies, which can be done using a dict and a small piece of lua.

lua_shared_dict tokenToProxy 10m;

location / {

   content_by_lua '
        -- make subrequest and capture response
        local response = ngx.location.capture("/proxy_request", {
            method = GetRequestMethod(ngx.var.request_method),
            body = ngx.req.get_body_data()})

        -- forward HTTP headers from response
        for k,v in pairs(response.header) do
                ngx.header[k] = v
        end

        -- forward status and body from response
        ngx.status = response.status
        ngx.print(response.body)

        -- cache backend for next request
        ngx.shared.tokenToProxy:set(ngx.var.http_authorization,
            response.header["X-Backend"])
    ';
}

location /proxy_request {

    internal;
    set $crestProxy "http://eveproxies";

    rewrite_by_lua '
        ngx.var.crestProxy = ngx.shared.tokenToProxy:get(
            ngx.var.http_authorization)
    ';

    proxy_pass $crestProxy$request_uri;
}

In a configuration with multiple loadbalancers we potentially have to pay the price of one proxy redirection per nginx process. This could potentially be improved by using a shared cache for the authorization to proxy mapping or by using ip affinity to map all requests from a client to a single nginx box, but in practice where the number of requests from a client is much larger than the number of loadbalancers, this improvement is likely to be negligible.

This mechanism ensures that most HTTP requests go straight to the correct proxy without the load balancers having to maintain any state. A new load balancer can be added to the cluster just be being told the addresses of the eve proxies and will quickly start routing requests to the correct location.

Brighton Mini Maker Faire: The Movie

A great video of the Brighton Mini Maker Faire last year by Andrew Sleigh showing the making of You’re The Boss 2. Applications for this year’s Maker Faire are now open and I can’t wait to see what everyone comes up with this year!

Super Hyperpolyglot

A few years ago nearly all the code I wrote was in C++, but increasingly I’m finding myself writing in a variety of mostly C-style languages and having to perform crunching mental gear changes as I switch between them.

In the interests of making these language switches less painful I thought about listing the commonly used features of the languages I commonly use in a side-by-side format. Luckily I’m a lazy programmer, the web is large and there’s nothing new under the sun, so I quickly found Hyperpolyglot which provides commonly used programming language features in a side-by-side format, which is what I wanted. Nearly.

Hyperpolyglot organizes it’s language comparisons in to several catagories: scripting languages, C++ family languages, embeddable languages and so on. In my case (and I suspect in many cases) the languages I wanted to compare were spread across several pages.

After briefly considering some cut and paste to get what I wanted I started playing with Google Spreadsheets, which has a very nifty importHtml function which allowed me to pull the Hyperpolyglot data in to several sheets which can be combined to produce arbitrary language comparisons.

It’s not perfect as different languages have different features and in some cases the Hyperpolyglot data doesn’t use exactly the same terms across tables (“version used” vs “versions used”) and I’m not a spreadsheet ninja, but it’s good enough to generate PDFs like this JavaScript Python Java C++ Comparision. As a Hyperpolyglot derivative work, The Super Hyperpolyglot Spreadsheet is licensed under the Creative Commons Attribution-ShareAlike 3.0 License, please let me know if you improve it.

100 robots Vs The Audience

A couple of years ago I had great fun putting together the London Geek Community iPhone OSCestra at Open Hack London and I’ve been controlling Ableton Live with iPhone tapped to my guitar as part of 100 robots for a couple of years now so when @andybudd suggested I do a digital music thing for the Brighton Digital Festival I immediately thought that it would be fun to combine the 2 projects by doing a 100 robots performance with audience participation.

The iPhone OSCestra was effectively a distributed collaborative mixing desk with each person controlling the volume and effect parameters on one channel of a playing back Ableton Live set. For the 100 robots performance I wanted to go further and have the audience actually adding parts to the musical performance, so @toastkid and I added extra drum, bass, synth and sample tracks to the 100 robots live set and filled them full of samples that could be triggered by the audience.

While having the samples adjust in tempo to match each song was relatively simple, transposing them to match the key of each song was more complicated. First I built a custom slice to midi preset which mapped the sample transpose to a macro control and used it to slice all of the samples to MIDI tracks, then mapped all of the transpose controls to a single MIDI controller and added a MIDI track which output the appropriate controller value for each song to a MIDI output which was looped back in to Live to transpose the samples.

The next question was how to avoid the performance turning in to a mush if multiple drum tracks or bass parts were playing concurrently. To avoid this we put dummy clips on the normal 100 robots which muted the normal parts when the audience triggered parts were playing. In some cases we let the audience parts add to the music, in others the audience parts would play instead of the normal tracks.

A final question was how to avoid max and I getting lost when the normal parts we play along to were replaced by unfamiliar samples. To deal with this we set the clip quantization on the audience triggered clips to values longer than the clip length. This meant that even if alternate baselines were constantly being launched, we would still hear the normal bassline for a while at the end of each quantization period, so we would know where we were with the track. To tune these settings we did some fuzz testing with semi random MIDI data to see how much madness we could deal with and still manage to play the songs.

With the tests done it was time to perform with 100 robots and 100s of people at the Brighton Dome and Museum.

Many thanks to Steve Liddell for recording the Brighton Museum set, @aral for letting us experiment on his update conference and to everyone who participated and watched. If you’d like to host another performance, please get in touch and if you like the music, please check out the 100 robots blog and consider buying our album from bandcamp.

100 robots Attack!

Lots of exciting 100 robots news! Our debut album, Attack!, has been professionally mastered by Chris at Melograf Mastering who has done an amazing job and made the album sound incredible. The new version is already available at bandcamp and will be available on itunes, amazon and many other download services on Monday. To celebrate the launch we’re playing live at The Hope in Brighton tomorrow night and have set up a new blog where we’ll be giving away a track from the album free every month and I’ll be doing most of my 100 robots related music blogging from now on. Head on over and subscribe to the feed so you don’t miss out. Hope to see you at The Hope tomorrow!