Tidbits about the WoW backend

This discussion with Joe Rumsey, a software engineer for World of Warcraft at Blizzard, took place in 2013, but I'm only posting about it now.

• Their database has 50% read and 50% write. There used to be more writes because the durability of player's equipment used to decrease often in combat. They have a proxy in front of the DB. The proxy flushes to DB periodically. Around 20 shards per DB. Transactions: inventory, trade, zone change, but not combat/monsters state.
• 800-meter zones. Sort of dynamic zone borders. Would rather have one big zone on one server than two zones with a lot of exchange between them on different servers. Objects are mirrored on adjacent zones. If a zone falls, the entire server falls. To move an entity between two servers, server 1 flushes the entity to DB then server 2 retrieves it from DB; the two servers never exchange the player data.
• The game server ticks at 2.5 times per second.
• The clients connect to a proxy.
• JSON vs binary messages: JSON's performance is fine 95% of the time.

Blizzard's Hadoop platform

Talk given by Brian Griffith and Amanda Gerdes at the OC Hadoop user group meeting in October 2013.

Blizzard uses the same Hadoop platform for Diablo 3, Starcraft 2, WoW, and Hearthstone. This platform went live in March 2013. Before this platform, game developers would log game events in log files, and use custom scripts to ETL these log files into relational databases for analysis. Problem: cumbersome, hard to maintain, low performance.

Solution: game developers, on their own, decide what to track in their game, and send that data to the platform. Instead of a log file, the game developers send protobuf objects. The 20 nodes in the Hadoop cluster receive and deserialize around a billion objects per day. The message's headers determine where to store each protobuf object within Hadoop. Blizzard also uses Hadoop as an operational data store. The cluster runs map-reduce jobs to filter and aggregate the stored protobuf objects. Currently, the 20 nodes store 60TB, but now that Blizzard realizes what they can do with Hadoop, they plan a 100-node cluster storing 1PB. Current bottleneck: CPU for deserialization. They rarely hit the disk for data so no IO waiting bottleneck.

For the messaging, they use a federation of machines running RabbitMQ. 50 producers worldwide (China, Europe, US, etc.) and 8 consumers (most likely in the Blizzard headquarters in California). When an Internet cable got cut with China, some messages were queued for 40 hours.

The analysts were using Greenplum for processing game data in parallel and ETL. Now that Hadoop is in place, they could start using Pig for ETL. But sales and customer data still come from relational databases, and the Greenplum is great at ETL. So there is no reason to force analysts into Hadoop. Solution: ETL jobs pull data from Hadoop and store it into Greenplum for warehousing. Greenplum is still in charge of its own ETL jobs.

Some data (such as a character's level or class in WoW) stay interesting across patches, but others (such as transmogrification usage) are only interesting when the feature launches. So the platform allows to build KPIs daily (e.g. activity aggregated per character level) and dive deep on demand.

Use case: WoW economy. Every gold transaction is sent to Hadoop. Reduce step aggregates by NPC id, item id, or player id. Makes it possible to:

• Check if the gold sinks follow designers' expectations.
Detect networks of gold farmers.
• Keep an eye on auction house prices.
• More ...

Importing Chinese characters from CSV file to SQL server

Problem:

Error 0xc02020a1: Data Flow Task 1: Data conversion failed. The data conversion for column "Column 0" returned status value 4 and status text "Text was truncated or one or more characters had no match in the target code page.". (SQL Server Import and Export Wizard)

Solution:

Scalability for Virtual Worlds - Gupta 2009

Scalability for Virtual Worlds, Gupta 2009

• Clients run the logic. Since server is only used for persistence and message forwarding, it can handle more clients.
• Problem: weak clients may not be able to execute all the updates they receive in a timely manner. Solution: action-based server-side IM: find the read/write sets each action impacts (transitive closure of the following actions), and notify concerned clients to rollback.
• Clients apply local actions to an optimistic model, and apply remote actions to a stable model. When applying the same action to optimistic and stable models, and the resulting models differ, need to rollback: the client asks the server to broadcast a fix it proposes. All other clients execute the fix, and if they conflict, send their own fix.
• Problem: solving long chains of conflict resolutions takes bandwidth and time. Solution: reject fix messages that cause a chain longer than a certain threshold.
• Experiment: 64 client machines running 1 bot each, moving every 300ms. When a bot collides into walls or another bot, it switches direction (more walls = more time to execute collision detection, more bots = more frequent conflicts). 1 server machine. Emulab with average latency between 2 machines of 238ms. Java.
• Good: Collision detection takes 7ms per action, while computing an action closure takes 0.04ms. Hence, a traditional server executing the logic lags after 30 bots, while the simply-forwarding server lags after 3000 bots.
• Bad: at least 20% extra bandwidth compared to server with logic. Drop 10% of actions to break long closure chains if bots are clustered together and move fast.

MapReduce for MMOs

MapReduce is a powerful tool to parallelize batches of computations. MMOs may sometimes have to run batches, but from what local game companies tell me, nobody in the game industry is currently using MapReduce. I guess, this is mostly due to studios not knowing what to do with it. Here are some examples.

Business intelligence

Basic metrics such as weekly play time or stop rate can give a rough perspective of the retention of an MMO. These metrics can be estimated with a couple SQL queries on dumps of the production database(s). It starts taking more time and effort to distinguish accross server shard, faction, race, or class. Still, a SQL script running for a few hours can do the job. Fancier analyses such as machine learning or social network graphs explorations take even more time and effort. MapReduce can be used to tune machine learning algorithms through Mahout, and even to process graphs (Google's Pregel also seems interesting for parallel processing of graphs: the Pregel version of PageRank takes 15 lines of code).

Detecting bots, hacks, or gold farmers is not as straightforward, but I think it is doable. First, the typical deviant behaviors have to be determined and made explicit by humans. For instance, speed-hackers send too many messages per second to the server, while gold farmers interact with less players, but more intensely, than normal players. Then, detecting deviant behaviors can be a machine learning classification or a graph parsing problem. In both cases, MapReduce can help.

Game-specific

Matchmaking and ladder: Some pre-calculations or updates to parameters of the ladder and match-making algorithms could be done offline by a small MapReduce cluster. A player's skill is unlikely to change much in 12 hours, so a cron task could run the job twice a day. According to Josh Menke from Blizzard, matchmaking involves gradient descent or Gaussian Density Filtering. Not sure whether Mahout supports GDF, but gradient descent is supported.

Tuning and balancing can take days for system designers. MapReduce could do that automatically: each mapper job is given a particular set of system parameters: player 1 has skill A (cost x SP and inflicts y damage) and skill B (cost z SP and heals w HP), player 2 has skill C (...) and skill D (...). Mappers run a few hundred Monte-Carlo simulations of a player 1 versus player 2 match with a fixed set of parameters (player1:A,B; skillA:x,y; skillB:z,w; ...). When done, mappers pass average statistics (win/loss ratio, average amount of gold at the end of the match, ...) of the 100 matches to reducers who sort them. The interesting configurations for balance are those with a win/loss ratio close to 50%. Naturally, this brute-force way of balancing assumes a proficient AI, and designers will still have to tweak the configurations returned by MapReduce so that they feel fun.

Practical concerns

Engineering detail: MMOs have hundreds of shards, but really only one MapReduce cluster should be needed. Each shard could send its jobs to the MapReduce cluster when it needs them done, and wait asynchronously for the MapReduce answer on a particular port. If the MapReduce job uses data from the production database, producing a daily dump may induce a temporary extra load on the shard's database machines, but this should be fine during empty hours.

MapReduce can be a double-edged sword if overused. Exploring the parameter space of learning algorithms too aggressively may lead to less accurate models.

Edit: Some people have been using MapReduce for analytics: mogade's platform and keighl have been using it through mongodb, but it's more of an engineering constraint (scatter-gather queries in a nosql DB to build a ladder board) than an analytics or machine-learning endeavor.

Scaling League of Legends

Notes from a 2011 Qcon talk about scaling the non-gaming server side of League of Legends. They are not worried about persistence during a game, but rather in the match-making, lobby, or store. They have soft real-time requirements: not the order of 10ms, more the order of a few seconds. [Twitter and Facebook are soft RT too]

Scaling

Scalability: it's easier to constrain what the logic developers are allowed to do, than to define what they are not allowed to do. Examples: Map/Reduce is a whole paradigm (you have to make your logic fit into a map() and a reduce()), NoSQL's unstructured data is a double-edge sword (you lose the ability to join, but queries come back faster), and when you're partitioned, you pick to be either atomic/consistent or available

46:50: Scaling should be dynamic/elastic; you need cluster recomposition and stateless growth patterns. Hence the system should be dynamically configurable. On the fly, you should be able to adjust the thread pool size, add/remove roles to machines, and switch logic or system algorithms.

Food for thought: list all the benefits/tricks a load balancer can provide to your system.

Caching

Caching provides flexibility: failovers, distribution of workload (hot code updates or restarts). Coherence is a distributed cache used between Hibernate and the DAO layer as "cache-through". If the DAO asks Coherence and there's a cache miss, then Coherence asks Hibernate (itself using a Coherence cache, or calling MySQL over the network if cache miss).

24:00: How to be sure that cache and DB are consistent? Do not cache! Query the DB directly, latency of few sec is OK for soft RT.

11:30: Serialize the work, not the data. It's faster to serialize the work to the data, than to unserialize the data, work on it, then serialize the result. Avoid moving the data all over the network towards where the process is. It's also easier to distribute the work to all the DB nodes than to send to/receive from all the nodes.
The objects sent on network between server and DB should be small: if you have to edit only one field, you should not have to send a big object of 1MB.

Logging and Testing

42:30: They log each function call with how long it took; overhead of 1% performance, but huge value if able to graph/plot the logs. Compare the average call duration in the last few minutes to the usual average to detect problems.

17:15: Keep in mind that the code will be used/executed in a data center, not on your laptop. 51:25: They use EC2 for load testing. 1000 threads per node, each thread simulating 1 user. Realistic because not all clients (threads) are same speed in real-life, and EC2 network is not always the best/reliable. It's not the most performant, but it looks like a quick-and-dirty way to load test. One of their scale testing environment has more than 50 machines.

[Literature] Tolkien: An Event Based Storytelling System

In this short paper from 2009, Satish et al. introduce Tolkien, an event-based storytelling system. This paper has an obvious link to interactive storytelling and fiction, but there could also be interesting applications to non-static or random content-generation in MMOG as well.

The authors define a story as a time-ordered coherent sequence of events. They consider a database filled with events and event-related data (video, audio, images, texts). Storytelling is simply retrieving appropriate events from the database in a particular order, and filter/adapt them to a particular audience. The filtering allows to show personal events such as birthdays to friends and relatives, music-related events to music-lovers or professional events such as conference talks to coworkers. Interactive storytelling approaches are inefficient in filtering large collections of events and most do not adapt to their audience.

[In the rest of the article, it is quite hard to understand in details what happens because the authors change their notations and names regularly. For instance, they use "objects" without having defined what they are. The "preference triple" definition has only two components. And so forth...

Each node of a directed acyclic graph represents an event. Events contain a spatio-temporal description and a semantics I_type. Edges are relations that connect events. Since relations are heterogeneous, they need different labels (found in the vocabulary L).

The storytelling process consists of two phases. First, the author specifies which events can be included in the story. Then the selected events are processed into a story tailored to the preferences of each member of the audience. (see figure below)

Story scripting

The scripting language the author can use to write the story script is actually a pseudo-SQL language. Example:

FIND $events FROM aParticularFile
FOR e IN $events
{
   FIND $museumsAtNY WHERE (activity = 'museum' 
                            AND datetime = '24 December 2008')
}
TELL $museumsAtNY

Compiling based on audience's preferences

Each member of the audience has its own preferences. For each member of the audience, these preferences are computed into a preference list, which is a a set of (pref_name, score). The score is a float between -1 (dislike) and 1 (like). For event e_i and person p_j, event interestingness is computed from the attributes of e_i and the preference list of p_j. It reflects how much an event should be incorporated into a specific viewer's story.

Story interestingness defines how interesting a story will be for a particular viewer. It is updated each time an event is added to the story. The addition of an event to the story aims at keeping story interestingness as high as possible. It can happen that the author's script requires to add an event reducing the story interestingness.

Architecture

Concretely, the viewer's preferences could be retrieved from a Google Calendar, Twitter or Facebook page (hence the WWW on the architecture diagram). The description of the rest of the architecture is given by the authors quite consicely:

The script contains a specification of the story as well as instructions on how to modify it depending of the audience. The script is first analyzed by a Script Processor to check for lexical errors. This provides the Compiler an error-free script with which it creates an operator tree. This operator tree would be stored in a cache. Once the preference list of the audience is known to the Run Time Processor, this tree is converted to a series of Index lookups and queries to the Eventbase. This database contains detailed event descriptions with the relevant media items. The results of these queries are then collected and sent to the Web-UI.
-- Arjun et al.