Feature Request: Backfill Support

[calebatwd]

Is your feature request related to a problem? Please describe.
Matches can be created without being full. At the same time, matches that were “full,” can have changing rosters from the perspective of the game host. Developers need a way to fill partially full matches. Additionally, the reasons and criteria used to fill matches change over time as the game progresses (e.g. highly skilled players leave one team, a friend has joined from outside matchmaking, etc).

For users of the matchmaker, solving this backfill problem should result in quicker times to match, and matches that are filled with more players; it will be more likely that any joined server will be full or quickly filled. From a developer perspective, it is very hard to work with a backfill system that competes with tickets being allocated to new servers. Methods to achieve this generally take the form of introducing lag to compensate for startup delay of servers, and failure to do so correctly can break matchmaking or overwhelm the system.

Here are a few common issues associated with directly running a match function as a backfill request:

Backfill Storms - If backfilling encounters issues that prevent successful backfill for a short period, matchmaking generates new game hosts since players aren't being drained into existing games. The game hosts start and try backfilling, resulting in further failure. More game hosts. More failed backfills. If left unresolved, the issue balloons and eventaully becomes a scale problem. Etc. Etc. This is especially problematic for long running game hosts (like lobby servers or mmos)

Immediacy Problem - Servers scheduled for allocation need to be immediately available for backfill. Without this, during the lag between a server allocation request and it coming online for backfill requests, many extraneous servers can be created leading to a cascading effect that can lead to service failure and extremely sparse server density.

Player Density - Similarly to the immediacy problem above, backfill requests that aren’t processed during every match function window are missed and can result in new matches being created despite having partially full games. This decreases the ability for the developer to fill those games, and ultimately ties game-host player-density directly to the rate at which a game developer is able to meet the matchmaking sync windows. This necessitates the need for some state to exist in the matchmaker to be available during matchmaking windows on a consistently recurring basis.

Describe the solution you'd like

Describe alternatives you've considered

Additional context

[Laremere]

Previous discussion on backfill:
#1149
#1148
#1114

None of them got very far, so closing them in favor of this discussion which will be more targeted at finding the solution and implementing changes to OM.

[scosgrave]

Thanks for opening this issue and adding some context to the problems associated with backfilling. I would also like add a few situations where I think backfilling will be required by game servers so we can be sure to hit as many of the primary use cases as possible. Feel free to add more use-cases if I missed any.

• Player(s) drop out of an existing game therefore substitute(s) are required
• Player(s) who were matched into a server do not ever attempt to connect. The server decides they are no longer going to join, and requires backfilled players.
• Player(s) create game(s), set the rules, the map etc and the game server requires players to backfill into the new game
• A game is created above minimum required players, but below capacity and remaining spaces require backfill
• A party partially fills a team and requires other players / teams to join them in order to proceed
• A long running world server has players leave therefore substitute(s) are required
• The available capacity of world servers causes more instances to be scaled up; these new instances require players to be backfilled into them

Also, thanks to @andrewgrundy for help with coming up with the list.

[scosgrave]

I reviewed the list of backfill situations I presented in my last comment and added technical requirements that would be needed to support each of them. My requirements might be a little opinionated because I was thinking of a certain implementation when I wrote them, so please let me know if you think there are any missing requirements, or if they should change in some way.

Situation:

Player(s) drop out of an existing game therefore substitute(s) are required

Support Needed in Open Match:

• Need way for game server to register that it wants players backfilled (either by overloading an existing API or by creating an API)
• Need the API to allow server to specify the number of backfill slots that are open
• Need the API to allow server to specify how a client should connect to it (ip and port, domain name + port + path, protocol)
• Need the API to allow server to specify a unique identifier (session ID (more useful), or server ID (less useful)) that the client can present when it does connect, so game server can determine if client arrived due to a match on a previous backfill request
• Need the API to allow server to specify a TTL for the backfill request (maybe this is an implementation detail?)
• Need Open Match to delete backfill requests when they have expired
• Need the API to allow the server to specify the Match Profile its current session is using, so backfill only considers players that match the profile.
• Need way for Open Match to prioritize matches made due to backfill requests
• Open Match should attempt to prevent new matches from going to new servers if they fit the requirements of an incoming backfill request

Situation:

Player(s) who were matched into a server do not ever attempt to connect. The server decides they are no longer going to join, and advertises open spaces.

Support Needed in Open Match:

• Need way for backfill request to specify a weight, so that backfill requests from many servers with the same profile are not competing equally for the same player pool when their need for backfill is not equal. If a spot can be taken by an AI player, maybe it gets a lower weight. If a spot can only be taken by a real client, and this is a long-running session, then the weight may be higher. If the spot can only be taken by a real client, but the session is nearly done, it might get a lower weight.

Situation:

Player(s) create game(s), set the rules, the map etc and search for participants

Support Needed in Open Match:

• Need way for server that requested backfill to be able to cancel request. This is to handle the case where a player creates a game, and then decides they meant to use different settings. We don't want the initial request for backfill to live in Open Match until the TTL is reached.
• Need way for backfill request to specify the types of players wanted if there is no existing Match Profile that matches what the game server wants

Situation:

A game is created above minimum required players, but below capacity and remaining spaces are advertised

Support Needed in Open Match:

• Nothing needed in addition to what is already mentioned for other situations. I think this situation could benefit from the request weight concept mentioned previously.

Situation:

A party partially fill a team and require other players / teams to join them in order to proceed

Support Needed in Open Match:

• Nothing needed in addition to what is already mentioned for other situations.

Situation:

A long running world server has players leave therefore substitute(s) are required

Support Needed in Open Match:

• Need an "extensions" section in the backfill request so that a long-living world can specify if a special event is happening, or if any other special context exists on this server that might elevate its need for backfills or necessitate the need for a specific type of player to be backfilled in. Having an "extensions" section also provides more game-specific flexibility in the other situations as well.

Situation:

The available capacity of world servers causes more instances to be scaled up; these spaces are then advertised

Support Needed in Open Match:

• Nothing needed in addition to what is already mentioned for other situations.

Situation:

A game server that has previously advertised its backfill slots has players join it through mechanisms other than Open Match (via a party system, or social platform, for instance).

Support Needed in Open Match:

• Need the ability to update outstanding backfill requests in Open Match so the number of available slots is accurate after the players join.

[scosgrave]

I wrote up some implementation ideas that I think will allow us to satisfy the requirements I detailed in my last comment. Feel free to add pros and cons, or add your own ideas to these as well.

Idea: Server Backfill Ticket (single ticket representing all open slots)

Description

This approach views Open Match as a clearing house where you have tickets indicating demand for matches coming in from game clients, and tickets representing supply coming from game servers. Open Match then matches demand with supply.

This description is to help readers understand where the idea came from, not to describe how it works in absolute terms. Open Match will still default to making matches between players, even if there are no "supply" tickets; it is assumed that when matches are made, there will be a place for them to go to. The addition of game server generated backfill tickets is to help game servers that desire backfill to get prioritized during matchmaking.

The game server will create a backfill ticket when it wants players matched into it, when a game session is already running. The backfill ticket will indicate the match profile that the game server is running (and possibly other parameters to help make sure the most relevant clients join), the server connection details, the number of players already playing, and the number of additional players desired.

The backfill tickets also contain some other info in them that allows Match Profiles to define Pools for them. When matchmaking runs the MMF will query Open Match for the Pools associated with the Match Profile. The backfill tickets will be put into a Pool as a result. The MMF then needs to evaluate the backfill tickets, and see if any of the players in the other Pools satisfy the backfill tickets. If they do, then a match is made with the player and backfill tickets, and given a high score so the Evaluator prioritizes backfill matches. The Director or Allocator/RM would then skip asking Agones for a game server, and return the backfill ticket's server connection data when a client from the match asks for connection data.

Pros

• Could potentially do this without modifying Open Match at all which could result in a faster development time and fewer bugs

Cons

• Using the same API endpoint for client match requests, and backfill requests may expose the system to security issues where game clients are posting backfill requests
• It is hard to cancel tickets, or have them expire (would need the MMFs to match all expired tickets into a match to get rid of them)
• It may be confusing, and possibly adding technical limitations, to overload the concept of tickets and have them for both game clients and servers.
• May not be able to support games where the client is creating a game session based on many tune-able parameters

Idea: Server Backfill Ticket (1 ticket per open slot)

Description

This is similar to the previous approach, except instead of having 1 ticket that has a field for the number of open slots on the server, there would be 1 ticket per open slot, and these tickets representing slots would no longer exist after being added to a match.

Pros

• Could potentially do this without modifying Open Match at all which could result in a faster development time and fewer bugs
• This approach gets around the problem of the single ticket approach where we aren't able to update the backfill ticket with the number of remaining slots.

Cons

• Does not work well for games with large server capacities
• Using tickets means we would be adding more tickets to the DB, reducing space for client tickets and increasing query response sizes
• It is hard to cancel tickets, or have them expire (would need the MMFs to match all expired tickets into a match to get rid of them)
• The API for posting tickets could be used by game clients to post fake backfill slots if the backfill ticket creation process is not properly secured
• May not be able to support games where the client is creating a game session based on many tune-able parameters

Idea: New Backfill Request API (new data type, not tickets)

Description

Game servers will make a Backfill Request to Open Match, providing the Match Profile name that they are currently running, number of available slots, TTL, connection info, etc, to Open Match. The Backfill Requests will be provided to MMFs as an additional argument that they can consider when making matches. If a match is for backfill, it gets additional info indicating connection settings, and the backfill request ID. When the Evaluator is going through matches, if it allows a backfill proposal, it adjusts the number of open slots remaining on the backfill request. If no more slots are available after the decrement, the backfill request would be deleted.

There would also be an API available to allow game servers to cancel their backfill requests, or update them with a different slot count.

Pros

• Using backfill specific requests, not tickets, makes it easier to delete or update the requests
• Works well for servers with many or few backfill slots open
• Does not increase the number of queries on the ticket DB
• Does not create additional copies of tickets in memory

Cons

• May require running and maintaining another database
• Requires new APIs for creating, querying, updating and deleting backfill requests
• May add additional work for the Evaluator, or necessitate the need for a custom Evaluator more often so backfill matches can be properly prioritized based on each game's backfill strategy, and for the added backfill request available slots update
• May not be able to support games where the client is creating a game session based on many tune-able parameters

Idea: Server Generated Match Profiles

Description

The game server registers a new Match Profile with Open Match when it wants players backfilled into it. The backfill Match Profile would include server connection details in it that could be used later during the game server allocation process. The Match Profile would also have a weight in it that would be added to the matches made, and would also have a TTL defined, after which time it would no longer be run. The Match Profile would need to run against an existing MMF that knew how to handle making matches for it.

Pros

• It's easier for the Director to manage the TTL and remove the Match Profile than it is for Open Match to remove tickets
• It doesn't use the same APIs that the game clients use, making it easier to manage those pieces of logic separately
• It also forces MMFs to separate out their backfill logic more than the 'ticket' based approach since they would no longer be considering backfill tickets in all Match Profiles
• It allows the game client more flexibility in creating new games with many tune-able parameters. The game client doesn't need to select from a rigid set of game modes that each have pre-defined Match Profiles.

Cons

• Adding more Match Profiles means increased query load on Open Match's DB in the form of 1 extra query per backfill Match Profile
• Adding a backfill Match Profile that is the same as an existing Match Profile in terms of tickets it will consider will result in the Evaluator seeing more duplicate matches
• Adding a backfill Match Profile that is the same as an existing Match Profile in terms of tickets it will consider will result in the MMF needing to use twice as much memory because it will be have 2 instances of the same Pool, one for each Profile.
• We would need to limit the number of Match Profiles that were generated for backfill in order to prevent Open Match from trying to process too many Match Profiles

[Laremere]

Throwing some numbers out there:
T = number of player tickets = 50,000
k = average number of non-backfill profiles a ticket matches against = 2
B = number of active backfill requests = 1,000
A = average number of tickets which could match the given backfill request = 100

If backfills are tickets, the number of tickets transmitted to match function requests is:
Tk + B = 50,0002 + 1,000 = 101000

However if backfill requests are additional profile runs, suddenly:
Tk + BA =50,000*2 + 1,000 * 100 = 200000

These are random numbers, but show how making backfill profiles become a very large factor quickly, making the system sensitive overall. There would have to be additional work on methods to reduce this. The backfill requests would need to do a very good job of estimating what ranges it should search for to only get a few tickets, or the query logic would have to be extended to support some method of rating, ordering, and limiting.

That's also not considering the information locality which a MMF having multiple backfills could support: If it already uses a ticket for one backfill, it can choose to not use that ticket for other matches or backfills.

If they ran in seperate profiles, either backfills would have to be greedy and send a lot of matches to the evaluator to try and get one through, or there's good chance of collision and wasting cycles colliding with other backfill MMF runs.

[calebatwd]

@adumovic ping

[scosgrave]

@Laremere - thanks for providing an illustration of the extra load the "Server Generated Match Profile" approach would introduce. I agree that this approach is probably not the direction we want to go in.

[adumovic]

Sorry i am late to the party! We have done a few internal implementations of backfill with our version of open match have a some learnings i think would be useful to this discussion (and indeed, guided our current implementation of backfill).

First of all, we tried a few approaches (both on paper and some as actual SPIKEs/POCs). One of the one that is ostensibly the easiest, is using the existing concept of a ticket to represent backfill tickets as well.
(I think the concept of a backfill ticket hasn't formally been defined here but i think colloquially we can all agree its "an object that represents the current and desired state of a game server".)

When trying to implement backfill tickets reusing the existing ticket system, there were a few things that stuck out as blockers right away: In the existing ticket system, tickets are immutable.

There are good reasons why tickets are immutable, and a lot of performance and coordination freebies from having immutable tickets! Imagine if all the om-query cache layers have to suddenly worry about not only caching but caching the right version of a ticket (and guaranteeing synchronous access for reads/writes)

The other thing we quickly realized was that we could not achieve our primary goals without mutable backfill tickets.
The primary one here being immediacy; if a new match is created that needs backfill, the representation of that match needs to exist immediately and any subsequent queries that either create new matches (for new servers) or could assign existing tickets to the newly minted backfill ticket, can do so.
Any gap in time between these two events breaks the concept of immediacy and re-introduces the possibility of backfill storms and low player density.
Simulating an immutable ticket, by deleting a ticket and recreating a new version of it with updated properties also has the same immediacy problem, due to the gap in time between the two operations.
After considering these and other concerns, we ended up making the following changes:

• Introduced a ticket that represents a backfill state/desired state.
• Introduced a new database specifically for backfill tickets
• Exposed a "backfill" service that knew how to implement a few limited operations against backfill tickets: (Create, Approve, Update, Delete)
• This service became the owner of backfill data and ensured all writes were synchronized to avoid issues with multiple reader/writes (servers, functions, cleanup workers)

The main benefits of this approach were that servers were fully responsible for approving backfill tickets depending on their state, and functions could author whatever they wanted and represent the backfill ticket with any data they chose. Servers then just need to check in to approve or update the ticket before the proposed ticket assignments expired.

If desired we can share more details about the specifics our implementation. I want to take some time to weight in on the existing proposals here.

[adumovic]

Idea: Server Backfill Ticket (single ticket representing all open slots)

This flow is very similar to the approach we took, in that match functions get to observer tickets and backfill tickets and match them together.
The main difference between what we did and this proposal is that we made it so that not only can game servers create backfill tickets, match functions can create them too. In fact, if you make a match that will lead to a server allocation, you need a backfill ticket representation of that created simultaneously so that if that proposal is approved, and in fact, while it IS being approved, match functions can in good faith find these backfill tickets and update them with new tickets.
This means a server could start and discover that it is 100% full during the delay between the backfill ticket being proposed and approved by the server.
This solves the immediacy problem but does involve a bit of complexity to implement!

Idea: Server Backfill Ticket (1 ticket per open slot)

I think this is problematic since you can't prevent many servers to be allocated at the same time as they don't know about eachother until these new tickets are created, in the meantime, more servers may sneak in, causing an explosion of tickets representing open slots

Idea: New Backfill Request API (new data type, not tickets)

This is very very similar to what we ended up implementing.
We have both a custom ticket (backfill ticket) and apis for approve/update/delete/create on them.
This is more complicated but we could not figure out a way around the immediacy problem without this.
Our approach differs in that we allow both servers and match functions to create backfill tickets.
Without the ability for backfill tickets to be created on the fly we could not solve the immediacy problem.
Also, instead of all these tickets being provided when match functions run, we liked the flexibility and scalability of allowing these backfill tickets to be queried just like other tickets.

Idea: Server Generated Match Profiles

As @Laremere has already noted, more match profiles can lead to a lot of extra executions.
Or first attempt to make a very simple backfill design essentially exposed a way for a backfilling server to execute a custom function run on demand against the backend and get any resulting matches directly. This lead to the backfill storms that @calebatwd described above.

I think the idea of having them be profiles made on demand would limit the possibility of this but still have noticeable increase in load.
This solution also does not solve the immediacy problem.

General Feedback:

In general, we could not think of a single solution that involved creating backfill tickets only outside of the matchmaker that solved the immediacy problem

[scosgrave]

Thanks for your feedback on the ideas I had @adumovic !
I agree that the ideas I put forward do not address the immediacy problem you described. The solution we decide on should definitely allow both match functions and game servers to create backfill tickets.
It looks to me like the "New Backfill Request API" idea gives us a lot of flexibility in our design, solves the immediacy problem and would also prevent complicated logic (and bugs) from being introduced into the ticketing system. I think this is the general approach we should take going forward, unless there are any objections.

Question:

Also, instead of all these tickets being provided when match functions run, we liked the flexibility and scalability of allowing these backfill tickets to be queried just like other tickets.

What benefits do you get by allowing the match functions to query the backfill tickets as opposed to just providing the relevant backfill tickets (the backfill tickets associated with a match profile) to the match function?

[Laremere]

It looks to me like the "New Backfill Request API" idea gives us a lot of flexibility in our design, solves the immediacy problem and would also prevent complicated logic (and bugs) from being introduced into the ticketing system.

+1, this seems like the most fruitful way to move forward. I'm not as worried about bugs, we have good test coverage. However, if backfill api ends up being a super set (or nearly so) to tickets once we get a concrete API draft, I'm going to question whether we should move the logic into tickets. I like the idea of unconstrained thinking with the API first though, so start with that.

[aLekSer]

(I think the concept of a backfill ticket hasn't formally been defined here but i think colloquially we can all agree its "an object that represents the current and desired state of a game server".)

BackfillTicket should contain GS data and MatchProfile also.
Assuming that MMF is responsible to query all BackfillTickets. Resulting Backfill Matches, with say desired - current number of tickets in it, is not full and it is not possible to evaluate it in the same way and compare with other full Matches.
Secondly resulting Match should contains GS connection information (which was previously ), which could be stored in match.Extensions map and a bool that GS Allocation by Director is not needed for this Match.

[aLekSer]

Sharing the diagram which was presented on a Contributors Meeting:

An assumption was made that Game could start partially filled, say 30 out of 40 players in capacity. Director on the diagram create a BackfillTicket with 30/40 state. And MMF later on creates a Match with 10 ticket only in it.
And Backfill Request could be made by a GameServer or by the Director after the Game was started and players already connected.

Another Option on a graph marked as Option 2:

I assume one other option which @adumovic explained is just not to return the assignment, create BackfillTicket in MMF and leave BackfillTicket without a GameServer's connection info in it until GameServer is ready.
In second option would all matches be complete only, or partially filled is allowed in this scenario with additional Approve on BF Ticket?
And in case of this option I assume there is one more component which would assign all previously matched tickets without being full later on. So we need to have mapping - Match (Tickets in it) -> BackfillTicket to get connection info on a later stages, don't we?

[aLekSer]

Gathering some answers after discussion with Scott and Andy. In the form of meeting notes. A subject to correction.

1. What will happen after the Director receives a partial complete match. Should Director allocate GS or request FetchMatches again to create allocated matches later on until it receives a full one?
   a. Allocate half full, when match completes, take all tickets from BF ticket and assign them all together. Ticket are in waitingAssignment state
   b. Set assignments to a partial complete match, and if more players come in, we give the same assignment.

2. What does approving BackfillTicket mean?
   Approval - actual DGS make this request. BF ticket ID got sent to DGS, approve API call is used to take tickets that are waiting and assign them to this GS.
   Tickets which were included in BF Ticket could not be queried and form a new match for a specific amount of time, in other words they are not showing up in queries, no link to BF id, until they are approved.

3. Does BF ticket contain SearchFields (not MatchProfile)?
   It store the query which was used to make this match, replays the query as searchFields in BF ticket, should be customisable enough.
   That way BF could appear at the same place as someone query normal tickets. Good for Skill based MM. Flexibility to dynamically change. Skill Range. It could be changed over time. Relaxation of the searchFields over time should be possible.

4. The current flow assumes that Backfill queries have priority over normal requests. What do you think?
   Up to the MMF. Add guidance how to avoid extra server allocation, and how to make higher player density

5. Clean up service to clean expired tickets. MMF and DGS could update BF ticket.

6. How does unassigned (without GS and created by MMF) BF tickets receive GS assignment?
   DGS approves BF ticket ID Backfill API SetConnection on a BF ticket and release it.

7. Who would Assign all tickets in BF ticket. Would Director be responsible for this?
   Not director, Internals of OM, who would release tickets after DGS calls to approve.
   If regular ticket assigned to BF ticket and expires, tickets should be returned to the pool of tickets.

A concepts of bags inside Backfill Ticket was introduced, contain the number of tickets which could be used to Backfill.

MMF if new state of BF ticket is accepted, it goes into that BF ticket.

[aLekSer]

There is a draft sequence diagram for first two tickets and one BF tickets created. Some arrows under questions marked with cross. I am not sure would DGS poll Backfill API to see if it has new tickets which need to be approved or accepted by DGS.

A link to the diagram in Mermaid format https://gist.github.com/aLekSer/655c43bd622199c4752bd77a6b1180d6

[Laremere]

There's good design discussion happening in the design doc. Posting here with an exploration of design options I'm doing that's inspired by the design problems encountered there (and being solved in a different way).

Firstly, here's a basic pre-backfill cycle for Open Match:

The flow is very simple, and is parallelizable. Multiple director workers could be calling fetch matches independently, and they have no need to coordinate. Additionally the load on the database (redis) is relatively low.

Failure recovery is also well understood:

Server Startup Immediacy issue

However, when it comes to backfill creating tickets immediately, there's a problem:

We need the backfill ticket to be created in the first fetch match cycle to solve the immediacy issue, however the second fetch match cycle (which in best case is the same director, but could be a different worker) now is unable to allocate the new tickets. The server is not yet know, or if it was, is not included in the information it was given.

Backfill Contention issue

There is a fairly simple happy path for backfill, where the game quickly acknowledges a new match (players being added to the exiting game) and assigns those player tickets:

This allows handling of changes to the game where a backfill was made without knowledge of a state change on the game server. (alternatively, state changes on the game server without knowledge of a backfill happening. However we need to chose one source of truth here, and the game server is the best choice.)

Another case is when the game has finished, and the game server shut down. It should send a delete request to the backfill ticket to clean that up, but if the director tries to contact it and fails, then it needs to return the tickets.

This however can lead to an odd (albeit unlikely) case where the game server receives acknowledgements out of order:

From game server code point of view, it is preferable that things are simple. As much as we can enforce that one only request is being processed at a time, the better things are. Obviously this conflicts with the goal of immediacy.

Possible solution: Backfill Awaiting

I think it's possible to simplify all of these problems with a new concept: Backfill tickets can be in a "awaiting" state (name tbd, I want to go with "pending" but that is already used to mean something different for normal tickets, so I'd prefer to not overload)

Any time that a backfill ticket is returned in a match, it is put into an "awaiting" state, until it is put back into an active state by assign tickets (or another call on the backend, but assign tickets would work)

Any match which contains a backfill ticket that is in an awaiting state is simply dropped before being returned from fetch matches. This may seem odd, but it allows the whole system to correctly operate without contention issues. MMFs should not inspect the status of the backfill ticket (we could hide it, if we wanted to). They simply operate as if the suggestion they're making will actually go through. If the backfill ticket is active, the suggestion will go through. However with the awaiting status, OM would basically go "it's nice that you want to do that, but we can't do it yet."

As a (I tried to make) simple example:

• Player creates Ticket 1
• Director calls fetch matches
  • MMF runs, putting Ticket 1 and a new Backfill ticket into match 1.
  • Evaluator accepts match 1.
  • Synchronizer marks Ticket 1 as pending.
  • Backend creates Backfill Ticket in the awaiting state, and returns match 1.
• Director begins allocating a gameserver, but will take awhile.
• Another player creates Ticket 2
• Director calls fetch matches
  • MMF runs, putting Ticket 2 and the existing Backfill ticket (currently awaiting) into match 2.
  • Evaluator accepts match 2.
  • Match 2 is dropped without setting Ticket 2 as pending (as normally done in the synchronizer)
• Director sees no new matches, still waiting on match 1 to finish allocating.
• Another player creates Ticket 3
• Success! the game server is allocated, and assigned to Ticket 1 and the Backfill Ticket
• Director calls fetch matches
  • MMF runs, putting tickets 2 and 3 into match 3 with the backfill ticket (no longer awaiting)
  • Evaluator accepts match 3
  • Synchronizer marks tickets 2 and 3 as pending
  • Backend updates the Backfill ticket with new info from MMF (3 players in match instead of only 1) and set to be awaiting.
• Director sees match 3.
• Director asks the game server if it can accept the 2 players, it says yes and tickets 2 and 3 are assigned to the game server, backfill ticket is no longer awaiting.

It'd be a similar workflow if acknowledgement from the game server took long enough that multiple cycles progressed.

[aLekSer]

I totally agree with the approach provided by Scott. I was thinking of similar way of changing the state of Backfill Ticket to unavailable for some time, while one Director acquired and locked it as a mutex. In this case for allocating GS.
One follow up question.
Can we make GS acknowledgement step as optional? If for example we have number of open slots in BackfillTicket we can always control the number of regular ticket's assignments the Director have made.
This acknowledgement would be from Director to the GameServer directly. Director->>GS: RequestAck. Or GameServer should poll BackfillTickets and approve it in this case GameServer ->> Backfill way of communication happens?
I assume in the your proposed design there is no need to store unassigned_tickets somewhere, we just return to the pool of all tickets, if Backfill Ticket is in awaiting or locked state.

[Laremere]

As mentioned on slack, we had a good meeting this morning diving into the current details and proposals.
Today I'm going to work on an iteration of the design that @aLekSer started, and hopefully we can get sign off on it in tomorrow's contributor meeting.

[Laremere]

Also, in our discussion it was pointed out that Game Servers receiving a request to accept matches is a non-starter, which invalidates my proposal from yesterday.

My new version of the design, mostly going off of previous designs but modifying to meet our discussion today: https://docs.google.com/document/d/1wUdFHoFTybQrzIlpK_oCV_EIBFbDIpY6A1vklfgiR0Y/edit#

[castaneai]

Hi.
I'm glad to hear that Backfill support will be available soon.

I don't see any field in the Backfill message to determine how many players need to be filled.
If many tickets are issued in a short period of time, MMF may assign too many tickets to a single Backfill.

Is there any way to solve this? (or use the extensions field?).

[aLekSer]

@castaneai

We decided not to have separate fields other than those in a regular Ticket. You should use Extensions for this and write MMF to treat those Extensions right.
There would be an example (and PR with it soon) on how to use OpenSlots parameter in Extensions.

[scosgrave]

I have created a list of tests we can run in order to determine what kind of performance we can expect when using Backfill to place players in matches. We can also use the results of these tests to measure how much Open Match's performance is changing from release to release. Feel free to leave comments if you think any of the tests don't make sense, or need to be modified. Thanks!

https://docs.google.com/document/d/1c32YB0UzsM1Tm9XUDxWriclYhuP6PRTk6ol5mzgQoU4/edit?usp=sharing

[aLekSer]

I am adding more description with answers for FAQ and other interesting details here:
https://docs.google.com/document/d/1kHNXUL423um7ZuuAxrCGsw7LqWl2d44NSw4lXBr-tK8/edit#
Will open a PR to docs repo soon after merge of initial Backfill Guide portion.
Director changes pseudocode:

if match.Backfill == nil { 
         do the same actions as before.
} else if {
	if match.AllocateGameServer == true{
		AllocateGameServer as before but propagate match.Backfill.Id to the GameServer, 
                do not assign resulting tickets to the GameServer, they would be assigned by AcknowledgeBackfill
        } else {
	        do not allocate and do not assign tickets
	        some other regular logic like gather metrics and log
	}
}

[castaneai]

Hi. I tried the Backfill feature in v1.2.0-rc.

I used the "openSlots" extension key to specify the number of players for the backfill, referring to examples. It almost works!

However, there is one case that is not taken into account in the examples: in the MatchFunction, calling setOpenSlots does not always guarantee that the player will reach the GameServer afterwards.
Strictly speaking, do we need to acquire a lock on the slots with a timeout? We have adopted the method of calling setOpenSlots after a player connects to the GameServer. This method sometimes causes player overflow, but the GameServer detects it and kicks the overflowing players out of the room to avoid the problem. This idea is based on Eventual Consistency.

The code I have tested is below.
https://github.com/castaneai/openmatch-local-dev/blob/b2dc26b856ab16570b2dfd13c9b668891f141705/tests/backfill_test.go

I'd like to hear your opinions on this issue. Thanks!

[andrewgrundy]

In the even a player doesn’t reach the game server, the game server can create another backfill to fill the slot. In the even the original backfill was for multiple slots, the game server can update the existing backfill adding +1 to the number of available slots.

…

On 23 Apr 2021, at 04:07, castaneai ***@***.***> wrote: Hi. I tried the Backfill feature in v1.2.0-rc. I used the "openSlots" extension key to specify the number of players for the backfill, referring to examples. It almost works! However, there is one case that is not taken into account in the examples: in the MatchFunction, calling setOpenSlots does not always guarantee that the player will reach the GameServer afterwards. Strictly speaking, do we need to acquire a lock on the slots with a timeout? We have adopted the method of calling setOpenSlots after a player connects to the GameServer. This method sometimes causes player overflow, but the GameServer detects it and kicks the overflowing players out of the room to avoid the problem. This idea is based on Eventual Consistency. The code I have tested is below. https://github.com/castaneai/openmatch-local-dev/blob/backfill/tests/backfill_test.go <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_castaneai_openmatch-2Dlocal-2Ddev_blob_backfill_tests_backfill-5Ftest.go&d=DwMCaQ&c=RKDswobrOGdp5vDCbl5XjxW8HqrsRSr80dGTvu3rE9Q&r=OiIm2MnYkasytSfnek08hoZLrVOOUEPyq8ouViqN00Q&m=v6DaRJqZwXEtGk2UM7krTeuaA_C6ioI-ox9FRNtWuAo&s=04jmOQNon9JVE0o7cjlHHbbLkHG_FO7NuoJvYJhFQW0&e=> I'd like to hear your opinions on this issue. Thanks! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_googleforgames_open-2Dmatch_issues_1240-23issuecomment-2D825353888&d=DwMCaQ&c=RKDswobrOGdp5vDCbl5XjxW8HqrsRSr80dGTvu3rE9Q&r=OiIm2MnYkasytSfnek08hoZLrVOOUEPyq8ouViqN00Q&m=v6DaRJqZwXEtGk2UM7krTeuaA_C6ioI-ox9FRNtWuAo&s=wBYb9-0xIYq_TuoM2ADJjbsWxQ0wSu9zdz7tRIXv2Ss&e=>, or unsubscribe <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_notifications_unsubscribe-2Dauth_AQFD5INC55CEJLLVEXMGQQLTKDP7VANCNFSM4PL27ITA&d=DwMCaQ&c=RKDswobrOGdp5vDCbl5XjxW8HqrsRSr80dGTvu3rE9Q&r=OiIm2MnYkasytSfnek08hoZLrVOOUEPyq8ouViqN00Q&m=v6DaRJqZwXEtGk2UM7krTeuaA_C6ioI-ox9FRNtWuAo&s=xkFhO1dKn5DJWVONKQRfBvMZwioBxvmg2XOhd3Px1pQ&e=>.