MMO interest management: send each player less

Intro

0:00 Hello and welcome back to episode twenty, where we're going to get our server to keep up with a lot more players, by sending each of them less. Let's begin with a quick look at where we're going to be by the end of the episode.

0:13 Five hundred bots set off across the island, and the server keeps its twenty ticks a second. Each player gets the players near them, and their names and levels once a second, so the server sends each of them a lot less.

0:31 On the website of the series you can find more information about the project. The code for the project is open source on GitHub, tagged at each step of each episode so that you can follow along.

Last time

0:43 Now, before we get to today's work, let's quickly go over what we did last time. Our game went onto a VPS from DreamHost, with two cores and Docker. A compose file for the server publishes the game's ports and the website, and none of the rest of our stack, as Docker publishes past the firewall. Deploy dot s h sends a commit and its certificates over a single SSH connection, builds it next to the release that runs, and starts each container from the new release. Our certificate named the server's address as a domain, so it failed to verify, and now an address goes on as an IP. And under load, the VPS kept up its twenty ticks a second to about four hundred players, and fell behind past that, which is what we're going to work on today.

Today

1:26 Today, our bots start taking trips across the island, so that they spread out like players would. Then the server splits the island into cells, and sends each player what's in the cells around them, which is called interest management. We measure it, and a profile tells us where the rest of the time goes. With that, we shorten how far each player sees, and send names and levels once a second, as they hardly ever change. We measure each change on its own, and the last one on the VPS too. All right, let's get started with what each player gets right now.

Everyone hears everyone

1:59 Each tick, our server sends each player the whole world: all the players, and all the monsters. So with N players, it sends N worlds of N players each, twenty times a second, which grows with the square of the players, as we saw back in episode four. Since episode eight, the server serializes the world once a tick, and the time goes into sending it. It's a lot for the players too: with five hundred players on my machine, each of them gets about three hundred and eighty kilobytes a second, which is about three megabits, and the server sends one hundred and ninety megabytes a second in all. And most of it is wasted, as the client draws fog from fifty metres out, and everything past a hundred and forty is gone in it. A player needs the players and monsters near them, and that's the idea behind interest management.

Interest management

2:47 We're going to split the island into square cells of thirty-two metres, like the chunks our client draws since episode sixteen. Each tick, the server puts each player and monster into the cell it stands in. A player gets what's in their own cell, and in the cells up to three away in each direction, so everyone within ninety-six metres at least, which is about where the fog is half-way. All the players in a cell get one world between them, so the server can put it together once, and they share its bytes, like all the players did since episode eight. Measuring the distance between each pair of players would grow with the square of the players again, while finding a cell's neighbours is a lookup. A player who walks out of that range drops out of your world, and comes back when they're near again, at a distance where the fog hides about half of a player.

Bots that go places

3:34 Before we write any of that, there's a problem with our benchmark. This is where twelve hundred of our bots were, four minutes after they joined, drawn over the island, and they're nearly all around the middle. Our bots hold a random direction for up to three seconds, like someone at the keys, so they wander about where they joined, which is the middle for a new player. One thousand one hundred and forty-two of them are within fifty metres of the middle, so everyone is near everyone, and interest management couldn't save anything. Real players go places, to the camps or to the coast, and our bots should too.

4:07 In wander dot h, we include limits and optional, for the trip and for travel further down. After the random direction and the hold, we add a struct, Trip, for somewhere a bot heads for across the island. It has where it's going, to x and to z, and two fields to tell when the bot is stuck. Closest is the nearest it has got so far, which starts at infinity, from the standard library's numeric limits, and stuck counts the steps that didn't get it any closer. Random trip picks a place within a hundred and seventy metres of the middle, where most of the island is, and its comment says so. Travel returns the input to send from where the bot is, a direction towards the end of the trip. It returns nothing once the bot is there, or has stopped getting closer, which is why it's an optional, like the one we saw with the frame reader in episode three. Wander dot c c includes c math, for the square root, the sine and cosine, and hypot, numbers, for pi, and optional, and it has three constants: the reach, a hundred and seventy metres, there, which is three metres from the end, and stuck, three steps. Random trip takes two numbers from a uniform distribution between zero and one, the first for an angle around the middle, and the second for how far from the middle the trip ends. That distance is the reach times the square root of the second number. The comment says why: the square root spreads the trips evenly over the circle's area, like our skeletons' wandering in episode ten. Random trip returns where that angle and that distance land, with the cosine for x and the sine for z. Travel takes the trip by reference, as it changes the trip's closest and stuck, and it takes x and z, where the bot is now. It measures how far the end of the trip is, along x and along z, and the distance in a straight line, with hypot. Within three metres, the bot is there, and travel returns nothing. If the bot is half a metre closer than ever before, closest moves, and stuck goes back to zero. Otherwise, stuck counts up, and on its third step without getting closer, the bot gives up, which is what happens when it runs into the sea or a lake. Otherwise, the input is the direction to the end, scaled to a length of one, and the bot runs. Bot dot h includes optional, and wander dot h, which bot dot c c had before, as the bot now keeps the trip it's on, if any. It also keeps where it is, x and z, and stay, how many more times it wanders before it sets off again. Bot dot c c includes optional, for travel's input, and random, for how long a bot stays, and receive now looks through the players in each world, and when it finds the bot's own, keeps its position. The server sends us our id in each world, so the bot can tell which one is its own. In wander, the comment says what a bot does now: like players, it goes somewhere on the island, and stays around there for a while. With no trip and no more wandering to do, it picks a new trip. On a trip, it travels, and once travel returns nothing, the trip is over, and the bot is going to wander for five to fifteen steps. Without a trip, it wanders as before, and counts a step down. On a trip, the timer fires each second, so the bot can correct its course, and while it wanders, it holds each direction for half a second to three, as before. Travel is where a bot decides where to go, so the new test pins down that a bot travels until it arrives or stops getting closer, and it needs no server. It starts with a trip to ten metres along x, and from the middle, travel has to return an input, which we check with assert true, as the lines after it read the input. The input points along x, with a length of one, and the bot runs. From eight metres, the bot is within three, so it's there, and travel returns nothing. Then a blocked trip, to ten metres along x again, for a bot that can't move from four metres, like one up against the coast. It still gets an input three times, and gives up on the fourth, which is its third step without getting closer.

8:06 With trips, four minutes after they joined, the twelve hundred bots are spread over the island, around the lakes and up to the coast. Two hundred and sixty of them are within fifty metres of the middle now, the ones whose trips end there, or take them through it. With the bots spread like this, each one is near a share of the others, and the share depends on how far each player sees.

Measuring first

8:27 Before we change the server, let's measure it with the bots that go places. Load dot s h adds a hundred bots a step this time, for twelve steps, so that each step's new bots are a small share of the players, as they all start in the middle. Each step takes close to a minute, so this is sped up. The server keeps its twenty ticks a second up to eight hundred players, and with a thousand, it manages fourteen point eight, and with twelve hundred, it's down to ten point two. That's more than last episode's server managed with its wandering bots, which I ran in steps of a hundred as well: it fell behind past five hundred, with seventeen point six ticks a second at six hundred. The server hasn't changed since, while the bots have. A profile of that run puts the time on the kernel sending packets, like we're going to see with these bots, and each tick sends about as many bytes. So the wandering bots make each packet cost the kernel more, for a reason I haven't tracked down yet.

Cells on the server

9:23 The cells go in a header of their own, interest dot h, as working out who gets what is a job of its own, and one we can test without a network. It includes compare, which the spaceship operator further down needs, c s t d int, map and vector, and our world's header, for the players and monsters. K cell size is thirty-two metres, with a comment that says it's like the client's chunks. K interest cells is three, and its comment gives the distance: so that a player gets everyone within ninety-six metres. A cell is two ints, x and z, which count the cells from the middle of the island. The spaceship operator, set to default, which C++ twenty gave us, writes all six comparisons for us, member by member, so cells can be the keys of a map. Cell of gives the cell that a point on the island is in. A view is what the players in a cell get: here holds the players in that cell, who are going to receive it, and players and monsters are the ids near it. And views takes the world's players and monsters, and returns a view for each cell with players in it. The views hold ids, and not copies of the players, as the server is going to look up each player's bytes by their id. In interest dot c c, we include c math, for floor, along with map and vector, and cell of divides x and z by the cell size, and rounds down with floor. A cast alone would round towards zero, so minus ten and plus ten would land in one cell, and the cell around the middle would be twice as wide as the others. Views first sorts the players into their cells, a map from a cell to the ids in it, and then the monsters, in a map of their own, as a cell can have monsters in it and no players. Each of the two loops looks at each unit once, so this part grows with the players, and not with their square. The views go in a map by cell as well, and for each cell with players in it, its view starts with those players as here. Then it looks at the cells around it, three each way, so seven by seven, with near as the cell it's looking at, the cell's x and z moved along by d x and d z. Any players in it go into the view, and so do any monsters, so a player sees the skeletons near them, and not the ones across the island. Each found is declared inside its if, which C++ seventeen allows, so it lives no longer than its if, and the two don't clash. The cells are a map, so a cell nobody stands in takes no memory, though looking it up still costs a little. With a thousand players in a hundred cells or so, that's about ten thousand lookups a tick, where comparing each pair of players would be half a million. In interest test dot c c, the test checks that each player gets what is near it, and it runs views on a few players and a monster, without a server or a network. Player one stands near the middle, player two sixty metres along x and forty back, and player three two hundred metres away. A monster stands twenty metres the other way from the middle. Each player is in a cell of their own, so there are three views, and assert eq stops the test there if there aren't, as the lines after it look the views up. Player one's view is for player one, and it has players two and one, as player two's cell comes first in the order we look at them, and the monster, which stands in the cell next to theirs along x. Player three is six cells along x from player one, and five from player two, so its view has player three and nothing else, with no monster either, as the skeleton's cell is seven cells away from player three's. So if views reached too far, player two would turn up in player three's view, and the test would fail. In the server's CMakeLists, interest dot c c joins the core library, and its test the server's tests.

13:02 Now, let's look at how the bytes of each cell's world get put together. Each cell gets a world of its own, and a player is in the worlds of all the cells near them, so serializing each cell's world would serialize each player many times over. In episode eight, we saw that protobuf reads two messages that follow each other as one, with the fields of both, and that's what we're going to build on. So parts dot h includes string, for the bytes of each piece, and string view, so that split can take the pieces without copying them. Piece takes a player, and returns its bytes, as a world with that player alone in it. Its comment says why: protobuf reads worlds that follow each other as one, so pieces put one after another make a world. A second piece does that for a monster, with the monster alone in its world. And split, which packed a world into datagrams for UDP, now packs pieces instead, with the time their world was sent, into parts of up to twelve hundred bytes. In parts dot c c, we include string, string view, and utility for move. Piece puts the player in a world, and serializes that world. So its bytes start with the field's number and the player's size, like any player in a world, which is what lets pieces go one after another. And a monster's piece is made like a player's, in a world of its own. Split used to fill a protocol world for each part, which the server then serialized, and now the pieces are serialized already, so it groups them first, as string views, and then copies each group's bytes once, into its part. Split goes through the pieces, and puts them into groups. A group is full when the next piece wouldn't fit next to the room we leave for the header and the client's own fields, and then a new group starts. A piece's size counts the bytes for its field's number and its size, so the three bytes we used to add for those go. Then each group becomes a part: a small world with the time it was sent, its part's number and how many parts there are, serialized, and the group's pieces appended to it. The header's fields come first and the pieces after them, which protobuf doesn't mind, and each part moves into the list, so its bytes aren't copied again. In the parts tests, we include vector, as the parts are a vector of strings now, where they used to be worlds. So a helper, called split too, takes a whole world and returns its parts, like split did before, so that the tests can still start from a world. Its comment says what it does: the world's players and monsters, each in a piece, split into parts. For each player in the world, it makes a piece and adds it to the vector of pieces, and then it does that for each monster, and splits those. Split takes string views, so the helper makes a vector of views over its strings, from their beginning and end, in braces. And parse reads a part's bytes back into a world, and expects protobuf to read them without an error. It uses expect true, as GoogleTest's assert macros return from the function they're in, which works in a function that returns nothing, and not in one that returns a world. With those two, the tests check what they did before. The world of two hundred players still comes out in parts that each fit a datagram, with room after each of them for the client's own fields, and once parse has read it back into a world, each part has its number, how many parts there are, and the time it was sent, and their players still add up to two hundred. In the second test, the parts come out of split as strings, and each of them goes through parse before parts adds it, like the client parses each datagram into a world when it arrives. And when a part is lost, its players stay where they were, while the players in the parts that arrived move on.

16:44 In server dot c c, we include string view, for the pieces, and our interest header. Broadcast used to fill one world with all the players and monsters as it went, and now each of them becomes a message of its own, so that code moves into two functions in the unnamed namespace. To protocol takes a player's id and the player, and fills in the protocol's Player with what broadcast used to set: where they are, their name, which way they face, what they're doing, their level, and their health. The most health they can have comes from their level, and to protocol returns the Player, which the caller serializes into a piece. Under it, we write a second to protocol, which does that for the protocol's Monster, with its id, its name, where it is, which way it faces and what it's doing. Then come the level and the most health the monster keeps, as a skeleton is made with its level, and doesn't gain any from experience. Both overload the to protocol we had for the motion, so the argument picks which one runs. Then broadcast, where most of the old body goes, as the world is put together differently now, and its comment says how it works: each player and monster is serialized once a tick, and what each cell gets is put together from those pieces. The pieces go into two maps by id, one for the players and one for the monsters, as each cell is going to look up its pieces by the ids in its view. So first, a piece for each player, from its protocol Player, and then a piece for each monster, from its protocol Monster. Both happen inside the serialize zone that Tracy has shown us since episode eight. Then the time we're sending at, which goes into each world, so the bots can tell how old it is. Then a loop over the views, one for each cell with players in it. For each cell, the pieces are the bytes of the players and the monsters near it, as string views, which point at the bytes in the two maps, without copying them. A string view is a pointer and a length, so a vector of them is cheap to build for each cell, as long as the maps they point into last, which they do, until the end of broadcast. The players in a cell get one world between them, so they share its bytes, as the comment says. Whole is the cell's world for TCP, and parts are its datagrams for UDP, and both are made the first time a player in the cell needs them, so a cell with nobody on UDP doesn't split its pieces. Then, for each player in the cell, we look up their session, as the loop goes through the cell's players now, where it used to go through the sessions, and a player without one is skipped. Each of them gets the own message, with their id, their experience and what the next level takes, along with the island's seed, as before. It's built for each player, as it's theirs alone, and it's a few bytes, so serializing it for each of them costs little. Over UDP, the cell's parts are split from the pieces the first time, and each of its players gets them, with their own message after each part. Each part goes into a shared pointer to a constant string, so all the players in the cell send from those bytes, which are freed once the last send is done. A datagram arrives whole or not at all, so it needs no size in front, as the comment over that loop says. Over TCP, the cell's whole world is a stamp with the time it was sent, and then the pieces, one after another, which protobuf reads as one world. The session puts each message's size in front of it, as it has since episode three, and the bytes we count for the dashboard are that size, the world and the own message. Then the session sends the whole world, which the cell's players share, followed by the own message, which is theirs alone. In the client's main, the log line said how many players were online, and now it's how many are nearby, as that's what the world we get holds. Let's look again at how a cell's world is put together, from views of pieces we've already serialized, so each player is serialized once a tick, whatever the number of cells near them.

20:36 Let's play it, with two hundred bots that have had ten to twenty seconds to set off, and the client's terminal under its window. I log in, in the middle, and run towards the camera, away from where the bots started. The log line counts the players near me each time the number changes. As I run, players drop out of my world behind me, and others come into it ahead, and the count goes down, as fewer of the bots have come out this far. Nobody pops up close to me, as a player comes into my world at ninety-six metres or more, where the fog hides about half of them.

21:13 Once it's built, the interest test and the parts tests pass, with the pieces put together into the worlds the clients have read all along.

21:21 Now the benchmark again, with the cells, a hundred bots a step, sped up. The server keeps its twenty ticks a second up to a thousand players, where it managed fourteen point eight before, and with twelve hundred, it's down to fifteen point five.

21:43 Side by side, the server used to fall behind past eight hundred players, and with the cells, it keeps up to a thousand. With twelve hundred, it manages fifteen point five ticks a second instead of ten point two. Past a thousand players, it still falls behind, so before we change anything else, let's find out where the time goes now.

Where the time goes

22:04 Like in episode eight, the server runs from the profile image, with perf next to it, and a thousand bots, which joined between fifty seconds and a minute and a half before. Profile dot s h records the server for ten seconds, and folds the samples for a flame graph.

22:21 Nearly all of the tick is still in broadcast, even with the cells. And most of that is send to, the kernel sending our datagrams, at eighty-six percent of the samples, while serializing the pieces and packing them into parts takes one point five percent. Inside send to, most of the time goes on each packet's way through the kernel's network stack. Netfilter, which runs the firewall's rules on each packet, and the bridge that Docker's network is made of, take thirty-four percent of the samples between them. So the cost is per packet, and the way to cut it is to send fewer packets, which means fewer bytes for each player. With the bots spread like on the map, each player still gets about fifty-seven percent of the others, as the island is small next to how far a player sees, and new players gather in the middle, where they start.

A shorter view

23:08 So, let's work out how far a player needs to see the others. The fog starts fifty metres from the camera, and hides everything by a hundred and forty. The nameplates show within fifty metres, so that's where players need to know who's who. Two cells each way gives everyone within sixty-four metres, so a player comes into view further out than the nameplates, and partly in the fog. At sixty-four metres, the fog hides about a sixth of a player, so you can see a player appear, though at a distance, and a lot of MMOs accept that. And it cuts each player's share of the others, to about thirty-five percent, from fifty-seven, with the bots spread like they were.

23:51 In interest dot h, k interest cells goes from three to two, and the comment over it now says sixty-four metres, while the rest of the server works out the cells' views from that constant.

24:01 Let's measure the shorter view, with the benchmark again, sped up. The server keeps its twenty ticks a second all the way to twelve hundred players, the most the benchmark adds, and there, a tick takes forty-five milliseconds at the median, out of the fifty it has.

Names and levels, once a second

24:24 Next, let's look at what goes into each player's entry in the world. Where they are, which way they face, what they're doing and their health change from one tick to the next. Their name doesn't change, and their level and most health change when they go up a level. Yet each tick, the server sends them all, twenty times a second, and the name is the biggest field of an entry. So the server is going to send those once a second, with each twentieth world, and leave them out of the others. Back in episode three, a test pinned down that protobuf doesn't send a field that's zero, and it leaves out an empty string too. No player has an empty name, or level zero, so a world without them can't be mistaken for one where they changed. So the client keeps the last name, level and most health it had for each player and monster, whenever a world comes without them. A player who comes into view, or who logs in near us, has no name until the next full world, up to a second later, so the client is going to wait for the name before it draws their nameplate.

25:23 In server dot h, the server counts its broadcasts, in broadcasts, which starts at zero. In server dot c c, k full every is twenty, with a comment that says it's a second's worth of ticks. In broadcast, full is true when the count is zero, so for the first broadcast, and each twentieth after it. Over it, we write why: names, levels and the most health a unit can have change now and then, so they go out once a second, and the clients keep them in between. Then the count goes up, and back to zero after nineteen, so it stays below twenty. A count that kept going up would overflow its int after a few years of ticks. The percent sign is the remainder after dividing by k full every, which is what takes it back to zero. Then, for each player, the entry starts as to protocol's Player, with everything in it, and unless the world is a full one, the entry loses its name, its level and its most health, with clear name, clear level and clear max health. Clearing a field puts it back to its default, empty or zero, which protobuf leaves out of the piece. And the monsters lose those three fields too, unless the world is a full one. A skeleton's name, level and most health don't change at all, while a player who walks up to a camp needs them for the skeletons' nameplates, so they go out once a second as well. In parts dot c c, update is a template, for players and monsters alike, as both have a name, a level and a most health. Over it goes the reason: names and levels come once a second, and protobuf leaves out a field that's empty or zero, which no name or level is, so we keep the last ones we had. It takes what we know of a unit, and what has arrived. Merged starts as a copy of what arrived, and gets the known name where its own is empty. Where its level is zero, it gets the known level, and where its most health is zero, the known most health. Then merged moves into what we know, in place of the old entry. Add calls update for each player, and each monster, where it used to replace them with what had arrived. On the client, the nameplates, the player frame and the character screen show names and levels, so each of them waits until those have arrived. In nameplates dot c c, a figure without a name gets no nameplate yet, and the comment says why: names come once a second, so one we've just met waits for its nameplate. In player frame dot c c, the frame waits for our level, which comes with our name, as its comment says, and the character screen waits for our level too. The new parts test checks that parts keeps names and levels between the ticks that send them, as parts is where the client puts each world together, over UDP and over TCP alike. A full world gives player one level four, and the next world has the names left out, and the players half a metre further along. Parts adds the full world, and then the next one, as the client would. After both, player one still has its name and its level, and it's at the new position.

28:20 And the benchmark once more, with names and levels once a second, sped up. With twelve hundred players, a tick now takes twenty-eight milliseconds at the median, where it took forty-five, and the server sends two hundred and fifty megabytes a second, where it sent three hundred and seventy.

28:42 All four, on the left: sending everything, then the cells at ninety-six metres, sixty-four, and with names and levels once a second. Sending everything falls behind past eight hundred players, and ninety-six metres past a thousand, while the last two keep their twenty ticks a second up to twelve hundred. On the right, what the server sends each second, which is what each change was about. With five hundred players, each player now gets about ninety-six kilobytes a second, where they got three hundred and eighty.

On the VPS

29:10 Now let's go back to the VPS, where last episode's lag showed up. Before any of today's changes to the server, but with the bots that go places, it kept up its twenty ticks a second to about four hundred players, like last time, and fell behind past that. Deploy dot s h sends it this commit, and the server builds and starts it, which is sped up.

29:32 Then the benchmark, on the VPS, with its bots on the VPS too, sped up. With five hundred players, where it managed twelve point eight ticks a second before, it now keeps up its twenty, and it keeps them up to seven hundred players, while with a thousand, it's down to ten point five.

29:47 On the VPS, with the run from before and the one from after side by side, the server used to fall behind past about four hundred players. Now it keeps up its twenty ticks a second to seven hundred, on a server with two cores that the bots share.

Docs

30:04 Last, in the README, the part on the bots says that they take trips across the island now, and the paragraph on the broadcast says where its time goes, which is the kernel sending each packet. Then a new section, what each player gets, on the cells, how far a player sees, and names and levels once a second, with a table of today's numbers from my machine, and the VPS's under it. The table has a row for each change, with how many players it keeps up with, and what each player gets with five hundred online, so whoever reads the repo can see what each change was worth. And the part on deployment runs the benchmark on the VPS in ten steps, and says how many players the VPS keeps up with now.

Wrap-up

30:44 So, today our bots started taking trips across the island, so that they spread out like players. The server sorts the players and monsters into cells, and the players in a cell share a world of what's around them, put together from pieces it serializes once a tick. With that, the server kept up with a thousand players where it managed eight hundred, and a profile showed where the rest of the time goes: the kernel spends it on each packet, so the way forward was fewer bytes. Each player now sees the others within sixty-four metres, past the nameplates, and gets their names and levels once a second. And the VPS keeps up its twenty ticks a second to about seven hundred players, where it fell behind past about four hundred.

Playing it

32:20 Let me know in the comments what you'd like to see next. And if you want to follow along with the series, subscribe to the channel. I hope you find this useful, and thanks for watching.