Creating scalable game backends in Microsoft Orleans part 1

Previously I've written a post introducing Microsoft Orleans to the Gamasutra community and it went quite well. Some people from the game development community joined the lovely Orleans community and I decided to write a series on how to make multiplayer game backend software using Orleans on Gamasutra.

What we are doing ourselves and the previous post's material

We ourselves at NoOpArmy have been in the business of crafting multiplayer games and tools related to them. We've worked on some MMOs and as contractor for multiplayer middleware companies and ... These days we are writing a backend server for online games to provide features like leaderboards, virtual goods, player inventories, timers, match making, real-time message broadcasting with interest management and ... to game developers.

Orleans is an open source revolutionary actor framework for building highly scalable distributed software systems which is used in backend services for games like Halo 4 and 5, the new Age of Empires Castle Siege and in lots of other places. Here we describe how to use Orleans to build a backend service, for more basic introduction read the first post linked at the beginning of the post or Orleans's own docs

Series overview

In the series I'll cover multiple features of a backend and how i think is a good way to make them in Orleans and will try to talk about features which their implementation widely differs from the described ones. For example storing user data is mostly the same operation so I'll not go through binary and string storage as separate topics or will not discuss storing per title/cross title data as a completely different concept. Instead I'll describe say Match Making, Leaderboards, Real-time Messaging and data storage and retrieval which are widely different topics and would require widely different algorithms to work.

The software at the end has the goal to be a scalable backend service which can be deployed to multiple machines for scalability and can serve massive number of users with low latency and ease of maintenance at the same time.

We will open source certain parts of our codebase over time and also use Couchbase as our storage in Orleans which holds hot data on RAM for fast access and scales well. Couchbase itself is written in Erlang which is a good platform for writing highly distributed and scalable software.

In general topics like these will be written

Why Orleans for such a system

So you might ask, you have the standard web platforms with addition of good caches, node.js and even C++ for the task depending on who you are so why Orleans. The answer is that Orleans makes it really easy to write such a system without too much trouble , we did wrote a relatively big system with a Unity client SDK and Couchbase providers for Orleans in about 4 man months.

If you go the web framework route, even if you choose bloody fast ASP.NET core , still you have lots of state which need to be in RAM and caches have a lot of issues, the programming model will be harder and some features like realtime messaging are very hard to build with good perf and latency characteristics in a web framework.

I won't even talk about node.js’s callback hell, lack of async code execution and threads and lots of other issues, go read comparisons of node.js and Erlang for that.

If you want to do it in C++, probably on a single machine your code will be faster and more deficient but good like scaling it easily unless you are a C++ guru which has written this kind of software in C++ for many years. Even in that case, I would like to suggest prototyping something you have written before in Orleans to get a taste of it. This is good enough that once in a while I think it is too good to be true J If you never used actor based frameworks, you’ll be surprised, If you’ve used them, it might sound silly but you will be surprised and you understand the beauty of it even more.

Feature 1: Leaderboards

Leaderboards are an easy problem to solve, right? It depends, If you are talking leaderboards with millions of records and complex sorting algorithms and requirement of fast response times, not that much anymore. Your simple ASP.NET/PHP API with MySQL at the backend will not work as well as it should and even If you substitute MySQL with MongoDB or even Redis it doesn't get too much better. Redis has good data structures to deal with this but Redis itself is only scalable up to a very limited number of machines. Querying data from NoSQL databases is not fast enough for these high number of records as well.

The solution in Orleans would be to implement a leaderboard grain which holds all user scores and their IDs in a list in a grain's state and stores them on disk periodically for fault tolerance. Below is a really simple implementation using a single grain and storage at every change which still works well up to a certain point.

Here is the interface definition

public interface ILeaderBoard : IManagedResource
    {
        Task Initialize(string name,DateTime startAt, DateTime EndTime);
        Task AddPlayerScore(IPlayer player, int score);
        Task<int> GetPlayerRank(IPlayer playerID);
        Task<Tuple<int,List<LeaderBoardEntry>>> GetAroundMe(IPlayer playerID, int count);
        Task<Tuple<int,List<LeaderBoardEntry>>> GetTopEntries(int count,int offset);
        Task FinishLeaderBoardAndRewardPlayers();
    }

The grain key is a string which can be the leaderboard name or a combination of leaderboard name and game name if different games are hosted on the same server.

The implementation is like this

using System;
using System.Collections.Generic;
using System.Threading.Tasks;
using Orleans;
using Interfaces;
using System.Linq;

namespace Collection
{
    public class LeaderBoard : Grain<LeaderBoardState>, ILeaderBoard
    {
        private bool _IsCreated;

        public override Task OnActivateAsync()
        {
            _IsCreated = State.IsCreated;
            return base.OnActivateAsync();
        }

        public async Task AddPlayerScore(IPlayer player, int score)
        {
            AssertIsCreated();
            int index = FindPlayerIndex(player);
            bool isSet = false;
            if (index < 0)
            {
                var name = await player.GetPlayerName();
                State.entries.Add(new LeaderBoardEntry(player.GetPrimaryKeyString(), name, score, DateTime.Now));
                isSet = true;
            }
            else if (State.entries[index].score < score)
            {
                var name = await player.GetPlayerName();
                State.entries[index] = new LeaderBoardEntry(player.GetPrimaryKeyString(), name, score, DateTime.Now);
                isSet = true;
            }
            if (isSet)
            {
                State.entries.Sort((x, y) => y.score - x.score);
                await WriteStateAsync();
            }
        }

        private int FindPlayerIndex(IPlayer player)
        {
            AssertIsCreated();
            return State.entries.FindIndex(x => x.player == player.GetPrimaryKeyString());
        }

        public Task FinishLeaderBoardAndRewardPlayers()
        {
            AssertIsCreated();
            throw new NotImplementedException();
        }

        public Task<Tuple<int, List<LeaderBoardEntry>>> GetAroundMe(IPlayer player, int count)
        {
            AssertIsCreated();
            var index = FindPlayerIndex(player);
            //if not in the board
            if (index < 0)
                return Task.FromResult(Tuple.Create(index, new List<LeaderBoardEntry>()));
            if (State.entries.Count < count)
                return Task.FromResult(Tuple.Create(index, State.entries));
            var halfCount = count / 2;
            var start = (index - halfCount > 0) ? index - halfCount : 0;
            if (State.entries.Count - count < start)
            {
                start = State.entries.Count - count;
            }
            var around = State.entries.GetRange(start, count);
            return Task.FromResult(Tuple.Create(index, around));
        }

        public Task<int> GetPlayerRank(IPlayer player)
        {
            AssertIsCreated();
            return Task.FromResult(FindPlayerIndex(player));
        }

        public Task<Tuple<int,List<LeaderBoardEntry>>> GetTopEntries(int count, int offset)
        {
            AssertIsCreated();
            if (offset > State.entries.Count - 1)
                offset = 0;
            if (offset + count > State.entries.Count - offset)
                count = State.entries.Count - offset;
            return Task.FromResult(Tuple.Create(State.entries.Count, State.entries.GetRange(offset, count)));
        }



        public Task Initialize(string name, DateTime startAt, DateTime EndTime)
        {
            State.start = startAt;
            State.end = EndTime;
            State.IsCreated = true;
            State.Name = name;
            _IsCreated = true;
            return WriteStateAsync();
        }

        public Task<string> GetKey()
        {
            return Task.FromResult(this.GetPrimaryKeyString());
        }

        public Task<string> GetName()
        {
            AssertIsCreated();
            return Task.FromResult(State.Name);
        }

        private void AssertIsCreated()
        {
            if (!_IsCreated)
                throw new InvalidOperationException($"This leaderboard with id {this.GetPrimaryKeyString()} is valid and is created");
        }
    }

    public class LeaderBoardState
    {
        public string Name { get; set; }
        public List<LeaderBoardEntry> entries { get; set; }
        public DateTime start;
        public DateTime end;
        public bool IsCreated { get; set; }
        public LeaderBoardState()
        {
            entries = new List<LeaderBoardEntry>();
        }
    }

}

So first look at the state, I suppose you want leaderboards to be defined before being used so users can not post to wrong leaderboards, the IsCreated field is for that, Name identifies the leaderboard and list of entries is well, list of entries. The time functionality is not implemented so don't care about them much, i put them here for clarity.

The Initialize() method is for initializing the leaderboard definition and setting the IsCreated variable to true. By having IsCreated in each resource which should be defined, you can check validity of the resource without searching in an index, however you need to maintain the index probably either in the database or in another grain for management purposes.

The AddPlayerScore method simply checks the last score of the player and then if current is higher or no score exists, will store the new score and sorts the list again.

Other functions are simple queries executed on the data to get top N entries or N entries around a player or...

Possible improvements

It is possible to improve this by saving data much less frequently like once each 10 seconds if something has changed or use multiple grains and a balanced tree to hold the data but I'll leave those as an exercise to the reader.

Also the algorithms used to sort and search the data are not the most efficient ones. In a software like this you should be very careful of the allocations you do and performance cost of everything, otherwise no one cannot really help you to build a good system which actually works.

Also you can do batching and add all requests for reading and writing to leaderboard to a queue and then simply each 200ms or any other period of time add all scores, sort the list only once and then answer all read requests. The leaderboard can also be made a reentrant grain relatively safely if you are ok with a bit old data.

Let me know what you think and I'll describe storing player data and maybe one other feature