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.

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] NetGames 2002

Summary of selected papers about MMOG architecture from the NetGames 2002 conference.

Aarhus et al., Generalized Two-Tier Relevance Filtering of Computer Game Update Events.

• Two-tiered means network communication is limited to a dedicated concentrator layer
• TCP
• Consistency within the server layer requires to pass the world state between servers.
• Clients connect to concentrators based on network topology, not their position in the game world.
• The concentrators are constructed to be application independent
• Dead-reckoning schemes
• Clients connect to a concentrator, not to the server logic. Hence, client connection is never lost if a game server crashes.

---

Bharambe et al., Mercury: A Scalable Publish-Subscribe System for Internet Games.

• distributed content-based publish-subscribe system
• subscription language expressive enough to allow game-specific subscriptions (eg x in [10,20] && y <= [40,50], or team == "MyTeam"). In the subscription {x in [10,20] && y >0}, a hub for x is more efficient at relaying an event than a hub for y.
• routing mechanism based on a circle of modular software hubs, each hub storing subscriptions.
• Evaluation: network topology simulator in which nodes are randomly assigned as hubs [unrealistic]
• Metrics:
  • Number of publications routed by a node. All nodes end up having the same routing load (ie scalability achieved).
  • Number of subscriptions stored by a node. Virtual world is a square, hence the central zone receives more players and subscriptions than peripheral zones.
  • Delay for a publication to reach the interested subscribers. Increases linearly with the number of nodes [not scalable!]

---

Cronin et al., An Efficient Synchronization Mechanism for Mirrored Game Architectures.

• Trailing State Synchronization (TSS)
• Optimistic algorithm: execute commands as they are received and rollback when late messages are received.
• TSS runs a delayed "trailing" copy of the live game state. Trailing copy is able to re-order messages and execute them in chronological order.
• It's cheaper to execute a command multiple times than to make snapshots of the game state
• Preserving random events was hard

---

Farber, Network game traffic modelling.

• Traffic modeling from logs of a 36 hour LAN. Matches of 8 to 30 players.
• Server sends 16kbps to each client
• Each client sends 1 kbps to the server
• Both client and server receive 20-25 packets/sec.
• Packet size varies a lot.
• Probability density function of client-server and server-client packet size and latency modeled by Extreme Value distribution: F(x) = exp(-exp(-(x-a)/b)). (long-tail behavior)

---

Fiedler et al., A Communication Architecture for Massive Multiplayer Games.

• World cut in rectangle or hexagon tiles.
• Players subscribe to current and tiles adjacent to closest current tile corner.
• Each tile contains an environment and an interaction channel.
• Environment channel for static data. Static objects generate bandwidth only when someone interacts with them, not by themselves. A static object does not interact with other static objects. Consumes low bandwidth. Uses TCP.
• Interaction channel for active objects. Active objects interact with static and active objects.
• Tiles are managed by one or more servers (n to n relationship). Server only provides constant data such as terrain and objects within the map. Server only cares about the environment channel. Collision detection on clients. Scales with the number of tiles, not the number of clients.
• Authoritative objects are on the machine that instantiates them. Other clients have duplicates/"proxies". Collision detection and other object-object interactions are calculated on clients. Affected object instances publish their updates on the interaction channel of the object's current tile.

---

Griwodz et al., State replication for multiplayer games

• Player-to-player interactions require low latency (= high urgency).
• In case of congestion, less urgent events may be dropped. Results in a game of lower quality, but still running.
• Rare player-to-environment actions require high reliability
• Game designers define when they build the game which actions are urgent and which are relevant.
• Clients connect to a nearby proxy. Proxies are interconnected.
• Participants belong to target groups. Each target group can be contacted through a channel.
• Overlay network of proxies distribute events to target group members.

---

Henderson, Observations on game server discovery mechanisms.

• Analyzing network traffic to know how FPS servers work.
• Game servers register to server directories. Client gets server list from directory using UDP. Same structure as Napster.
• Method: 3 Half-Life US server directories were queried four times a day for a month.
• Problem of directories: single points of failure, stale information (70% of servers not active anymore), redundant info (90% of servers register to all directories), and no congestion control

---

Mauve et al, A Generic Proxy System for Networked Computer Games.

• Move intelligence and server functionality to the border of the network
• Some server functionality can be delegated to the proxies.
• Proxies located close to the players (need ISP support). Therefore, they could execute client code as well (anti-cheat).
• Proxies can reduce the server load in doing packet processing and filtering.
• Overlay network enables traffic rerouting around congested areas, network fault detection and node-failure recovery.