Agones: Game Server Allocation advanced filtering: player count, state, reallocation

[markmandel]

Dependent on #1033

(Not a detailed design ticket, just putting down the basic idea to get the conversation started)

Is your feature request related to a problem? Please describe.
In both session based games and persistent games, it would be useful to be able to do something akin to:
_Just give me a GameServer that has room for 2 (or n number) players, regardless whether it is Allocated or not_

Which would pass back a GameServer if it had capacity available, and if not, would Allocate a whole new one (with enough initial capacity), and return that instead.

This would be useful for:

• Automating matchmaking backfill operations
• matchmaking players to persistent worlds that have capacities (#1034 helps here too)

Describe the solution you'd like

Some kind of adjustment to GameServerAllocation that accounts for capacity of players that are available. Maybe a way to choose what State(s) are in the Allocation pool? (Ready or Allocated??)

This probably requires much thought, and would want to tie into #1197 so they don't conflict with each other.

Describe alternatives you've considered
Having a totally different Allocation path for player capacity based allocations -- but then we will likely end up with a huge number of paths for different types of allocations.,

Additional context
Can't think of anything else.

[markmandel]

Objective

Already defined above

Background

These are terms that are currently used in Player Tracking:

• Player Capacity: Max number of players that could end up in a GameServer
• Player Count: The number of players that are in a GameServer currently
• Player Availability: Capacity - Count. (this is new for this ticket)

Requirements and Scale

• Is a high throughput operation, so will need to have an implementation that allows for this.
• Will need similar scaling characteristics to current Allocation policy.
• Will sit behind a feature flag of “PlayerAvailableAllocation”
• Will still need to adhere to Packing and Distributed optimisation patterns
• Will still need to be filterable on required and preferred match labels/expressions

Design Ideas

We extend the required and preffered sections of GameServer Allocation to allow for player availability and game
server state filtering (Credit), as well as allow allocation to "re-allocate" an already Allocated GameServer.

This should be extensible to other types of allocation strategies down the line, as well as having applicability
outside of only player tracking re-allocation. This approach also doesn’t require a breaking change to the existing
allocation implementation.

For example, the current way of allocating against Ready GameServers (which would be default, and therefore backward compatible) would become:

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
  gameServerState: Ready # Allocate out of the Ready Pool (which would be default, so backward compatible)

Wherein:

• gameServerState - is the state of the GameServers to search, limited to Ready and Allocated.
  By default this would Ready, which is the same as the current implementation.

Therefore, to attempt to find a GameServer that has room for between 2 and 10 players, that is already Allocated, and if
not found, to then find a Ready one that has the same amount or more of capacity, and move it to Allocated, this would look like the following:

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  preferred:
    - matchLabels:
        agones.dev/fleet: simple-udp
      gameServerState: Allocated # new state filter: allocate from Allocated servers
      players: # new player availability filter
          minAvailable: 2
          maxAvailable: 10
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
      players: # new player availability filter
          minAvailable: 2
          maxAvailable: 10
    gameServerState: Ready # Allocate out of the Ready Pool (which would be default, so backward compatible)

Wherein:

• players.minAvailable - is the minimum number of players to match against (default: 0)
• players.maxAvailable - is the maximum number of players to match against (default: max(int))

This works since the preferred section would currently Allocated GameServers first, and if it failed to match, then search then would move onto the required section.

This would also need to eventually be expanded to the gRPC Allocation Service API, but the same format could be reused.

Removing GameServers from the pool on re-allocation

One concern with this design is that you could continually get the same GameServer over and over again on re-allocation, which could send way more players to a particular GameServer than may be desired.

To solve that problem, we can use already existing Agones alloction constructs to solve this: matchLabel selectors
and also being able to set annotations and labels on a GameServer at allocation time.

For example, we can extend the example above and also add a user defined label agones.dev/sdk-available to our
GameServers that indicates that there are slots available for a player to fill.

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  preferred:
    - matchLabels:
        agones.dev/fleet: simple-udp
        agones.dev/sdk-available: "true" # this is important
      gameServerState: Allocated # new state filter: allocate from Allocated servers
      players: # new player availability filter
          minAvailable: 2
          maxAvailable: 10
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
    gameServerState: Ready # Allocate out of the Ready Pool (which would be default, so backward compatible)
  metadata:
    annotations:
      waitForPlayers: "2" # user defined data to pass to the game server so it know when to switch back the agones.dev/sdk-available label
    labels:
      agones.dev/sdk-available: "false" # this removes it from the pool

Upon allocation the value of agones.dev/sdk-available is set to false, thereby taking it out of the preferred
re-allocation pool. From the annotation data we're passing through (in this case, telling the game server binary to
potentially wait for 2 players to connect), the game server binary can use the SDK.SetLabel(...)

This strategy will need to be documented, but also have applicability outside of only allocating by player count
-- for example, it could also be used where GameServer containers host multiple instances of a GameSession.

It also allows users to utilise their own labelling names and systems that make sense for their game.

The downside here being that the onus is on the user to pass the required information down to the GameServer to know when to add the GameServer back into the pool. Long term, we could look at doing some of this automatically, but it would be best to get user feedback first on this initial implementation before going down that path.

Technical Implementation

• Much like we keep a ready cache, we should also keep a cache of Allocated game servers that have a player availability greater than 0. This may be able to be pre-sorted based on packing rules. This should be the first place that is searched for Allocations that match the label selectors.
• If we cannot find a previously Allocated GameServer that matches the criteria required, then we fall back to searching for a Ready GameServer - but with the additional requirement of making sure the players available of the Ready GameServer is greater than or equal to that which is requested.
• This is likely going to require some refactoring of the ListenAndAllocate function, as it is currently optimised for only the Ready policy.
• When allocating a GameServer, whether Ready or Allocated, an annotation of agones.dev/last-allocated with a
  timestamp of that moment will be applied. This has two pieces of functionality: (a) so that SDK.WatchGameServer() (or
  any listener to events) can see when a GameServer is re-allocated (b) we can take advantage of CRD generational
  locking so that when re -allocating we know the resource is up to date, and is still available to be re-allocated.

Alternatives Considered

New Allocation Pathway

We could implement a whole new Allocation pathway (which we discussed earlier), which seems untenable.

Allocation "policy"

Previous design used an allocation policy to switch out strategies. That was deemed too inflexible when compared to
this current design.

[markmandel]

/cc @domgreen who I know is working on similar things right now

[markmandel]

@pooneh-m do you see any issues here? Especially when it comes to multi-cluster allocation? I couldn't see any, but wanted to double check.

[markmandel]

One thought that came to mind - if I send multiple requests for a GameServer with available for 1 player - I shouldn't repeatedly get the same GameServer -- at least not in the some n time period. Otherwise, race condition city.

One thing we could probably take advantage of in that GameServer get refreshed every 30 seconds even if it hasn't changed -- so we can leverage the GameServer capacity cache, such that when we pass back an Allocated GameServer with capacity, it gets removed from the GameServer availability cache.

That being said, when each GameServer gets refreshed is not in our control - so it would be any time _up to_ 30 seconds -- so this might be a good first step -- but we may also want to keep our own list of GameServers that we hold onto for a little while as "allocated, but via availability" unless it gets genuinely updated (i.e. status change, player count change etc), in which case, update the cache, to try and mitigate this race condition.

[pooneh-m]

@pooneh-m do you see any issues here? Especially when it comes to multi-cluster allocation? I couldn't see any, but wanted to double check.

For multi-cluster allocation, it translates the allocation status to gRPC error; so for example for the lack of capacity, ResourceExhausted is used. I think for player capacity the same error should be returned. The API should remain consistent with GameServerAllocation.

For the overall API design, I wonder if we should still categorize the player count criterium as part of required or preferred.

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
    policy:
      type: "Players"
      players:
        available: 2

Should it also support range?
It would help to list different user journeys for the design. e.g.:

• allocate a game server with at least 2 player capacity
• allocate a game server with exactly 2 player capacity

If there are multiple criterium, how can we stack rank them? Is it part of the user journey?

[markmandel]

For the overall API design, I wonder if we should still categorize the player count criterium as part of required or preferred.

AAAAAH YES! :cartwheeling: I was trying to see if there was a way to do something like this, but for whatever reason did not see this path! I like this a lot! Thank you @pooneh-m for this direction! I also love the idea of supporting ranges as well. Makes perfect sense.

I'm actually now wondering if we do away with policy all together, and expand on required and preferred to cover this use case, but potentially more.

So, say you wanted to do a standard situation of: _give me a game server with an availability of 2 or more players, but if not available, allocate a Ready GameServer_, you could do something like:

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  preferred:
    - matchLabels:
        agones.dev/fleet: simple-udp
      gameServerState: Allocated # new state filter: allocate from Allocated servers
      players: # new player availability filter
          minAvailable: 2
          maxAvailable: 999
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
    gameServerState: Ready # Allocate out of the Ready Pool (which would be default, so backward compatible)

So first pass of the allocation system would look at the preferred block (which does have the ability to provide multiple options if the first once cannot be provided), and if it could not find anything, move onto required - which would do the usual allocation strategy (or whatever is specied here).

This would remove policy from the Allocation design above, which may make optimisation more complex, but does provide a much more flexible set of allocation options.

You could do things like _Give me an already Allocated GameServer with availability for 2 players, but no nothing if you can't find one._, which you absolutely couldn't before, which I think could be quite useful :+1:

Thoughts?

[aLekSer]

That's really much more flexible design, I like it.
Could minAvailable be 0? Say we want to get the GameServer which is occupied.
The only two opposite issues which come to my mind, when you want to find for maxAvailable equals to say 5. And then all of a sudden 6 players disconnects and your GameServer would not meet the original criteria, that it actually had 1 when you made an original GameServerAllocation request - there was only one available slot (1<5).
The second one is about minAvailable . We should prohibit users to reconnect to the same GameServers, otherwise at some point minAvailable could become 0. And we should not return the same GameServer twice as a result of 2 consequent calls to GameServerAllocation with the same query parameters.

[EricFortin]

The second one is about minAvailable . We should prohibit users to reconnect to the same GameServers, otherwise at some point minAvailable could become 0. And we should not return the same GameServer twice as a result of 2 consequent calls to GameServerAllocation with the same query parameters.

I don't think we should get in the way of a player reconnecting since this is usually a game design decision. Furthermore, if integration has been done correctly, the user reconnecting should have disconnected beforehand so the used capacity wouldn't change. The reconnect flow is supported in multiple games. Also, I am not sure how reactive the player tracking is but if a developer elect to use packed as allocation strategy and makes multiple consecutive allocations. I believe we should return the same server as long as there is enough capacity.

I also have a question on the design, will the capacity based allocation also respect allocation strategy? By that I mean in a packed model, will it try to allocate allocated game server on the same node if possible?

[markmandel]

So to all the points about returning the previously returned GameServer are 100% valid. One thought I had though was to have an extra new element of hold - which is to say, "Don't re-allocate this GameServer for _duration_ after it has been Allocated", so something like this:

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  preferred:
    - matchLabels:
        agones.dev/fleet: simple-udp
      gameServerState: Allocated # new state filter: allocate from Allocated servers
      players: # new player availability filter
          minAvailable: 2
          maxAvailable: 999
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
    gameServerState: Ready # Allocate out of the Ready Pool (which would be default, so backward compatible)
  hold: 5s

So this would make the request for the GameServer with at least 2 players, and then give the client 5 seconds to do it's connection and registration before opening it up again for new players to come back in.

This would give you a way to limit the race conditions you might get when re-allocating the same GameServer, but allow for a GameServer to do whatever game specific thing we expect it to do in that time (we could track this on an GameServer Annotation) -- or you could opt out entirely, and leave it at it's default of 0.

The other option is tracking what we expect the capacity _should_ be post Allocation, but I think that's too complicated -- at least for a first pass.

How do we feel about something like that?

I also have a question on the design, will the capacity based allocation also respect allocation strategy? By that I mean in a packed model, will it try to allocate allocated game server on the same node if possible?

Absolutely - we mentioned that in the initial design :+1: Optimisation strategies are a definite must for sure.

Packed would target the Node with the most allocated game servers (which is what is does already), and then look for the most full one.

Distributed would likely do it's usual randomisation thing.

That what you expected?

[markmandel]

Just gently bumping this, to see if the above makes sense. If so, I can update the design above to incorporate these changes.

[pooneh-m]

Perhaps hold should be an environment variable vs per request setting. Timed resource reservation will be difficult to track and predict.

I think a matchmaker should reserve a game server, allocate it for x number of players and release it. When a game server is reserved, it will not be returned to any other matchmaker until it is ready to accept more players (was released). So another approach could be to provide an API call for releasing an allocation lock, controlled by a matchmaker.

[markmandel]

Perhaps hold should be an environment variable vs per request setting. Timed resource reservation will be difficult to track and predict.

Let's remove the hold idea for now, your follow up comments provide some interesting insights I want to explore more, and I think we can use for at least the first pass implementation. But I think we (a) need to have _something_ at a per GameServer level, as different types of game server will likely have different connection requirements (lobbies vs game sessions for example). I also think we can solve this on a per GameServer basis using the CRD locking functionality of the K8s api.

So another approach could be to provide an API call for releasing an allocation lock, controlled by a matchmaker.

I'm a bit hesitant to add yet another API endpoint -- but your comment here made me realise something cool, we could actually do exactly what you suggest now, but without another API! We can do it with labels, and the Agones game server SDK!

For example, if I did:

apiVersion: "allocation.agones.dev/v1"
kind: GameServerAllocation
spec:
  preferred:
    - matchLabels:
        agones.dev/fleet: simple-udp
        agones.dev/sdk-available: "true" # this is important
      gameServerState: Allocated # new state filter: allocate from Allocated servers
      players: # new player availability filter
          minAvailable: 2
          maxAvailable: 999
  required:
    matchLabels:
      agones.dev/fleet: simple-udp
    gameServerState: Ready # Allocate out of the Ready Pool (which would be default, so backward compatible)
  metadata:
    labels:
      agones.dev/sdk-available: "false" # this removes it from the pool

So what does this do?

• If the GameServer is Ready, allocate as per normal
• If the GameServer is Allocated, only return it if the agones.dev/sdk-available label value is set to true.
• Once Allocated, set agones.dev/sdk-available to false.

This would mean if we re-allocated a GameServer that was in an Allocated state, it automatically drops itself out of the pool of re-allocatable GameServers, because it no longer is valid for the search conditions :smile:

How then would the GameServer set itself to being available again to being re-allocated? It can do this now through SDK.WatchGameServer(...), and then set the label agones.dev/sdk-available back to being true as appropriate for the game.

The downside here being that it is onto the user to pass the relevant information down to the gameserver (likely through annotations) to determine when it should reset itself - but maybe that's a great first pass at this functionality, and we can then get more sophisticated (maybe extend hold to be more intelligent)? as we get more feedback.

(A) Did that make sense and (B) WDYT of that approach?

[pooneh-m]

I like the idea! GameServer should have enough information on the capacity to lock/unlock itself for allocation by setting the labels. Maybe the label should be more self explanatory e.g. allocation-lock?

[markmandel]

Maybe the label should be more self explanatory e.g. allocation-lock?

The label could be whatever the user wants! (we should document this as a solution once we implement this - how to use these type of strategies for different types of scenarios).

What's nice about this too - you can allocate based on player capacity, but you could also use this for running multiple sessions per single Game Server as well. It has a really flexible set of applications.

Sounds like I need to update the design doc above though!

[markmandel]

Updated design above:
https://github.com/googleforgames/agones/issues/1239#issuecomment-683147308

[domgreen]

Catching up on this one very late but this looks fantastic ... the ability to prefer a Allocated GS with a user defined label is exactly what I was hoping for.

I am currently doing this by using the k8s APIs and label selectors to find a pod/gs so bundling it into the allocator makes perfect sense.

[domgreen]

@markmandel thinking around this as I'm redoing some matchmaking myself ... will this also allow us to reserve those spots on the allocated gs?

Main issue I'm looking at is joinig race condition:

• A+B try to get 2 spaces
• C try to get 1 space
• C joins gs first
• A joins gs
• B unable to join due to limits

Actually see there was some discussion between yourself and @pooneh-m around this https://github.com/googleforgames/agones/issues/1239#issuecomment-708660247

[markmandel]

@markmandel thinking around this as I'm redoing some matchmaking myself ... will this also allow us to reserve those spots on the allocated gs?

I think the approach outlined above essentially does, because the GameServer gets to decide when to put itself back into the pool of selectable allocated game servers when it is appropriate for that game. Some of this will need to be handled by the matchmaker though to align matchmaking requests with appropriate game servers.

So in your example (I'm assuming A, B and C are requests for GameServers - or are they players?):

Assuming A, B and C are requests for GameServers:

1. A+B try to get 2 spaces: each will get separate GameServer instances that have room for 2 connection
2. C try to get 1 space: they also get their own GameServer - unless the GS received puts itself back in the pool before then because it still has room / has accepted connections in a timely manner (an exercise for the user)

Assuming A, B and C are players:

1. A+B try to get 2 spaces: this would be a single request for a GameServer with room for 2 players, so you would get 1 GameServer that has room for 2 players (let's assume there is)
2. C try to get 1 space: You are only going to get the GameServer A+B connects to if it puts itself back in the pool, because it knows it has room. So there is no way for it to reconnect to the same GameServer unless it knows it has room.

Since K8s gives us generational locking on Resources, we can't accidentally allocate a GameServer to both requests.

I would still be inclined to have some race condition checking at the GameServer level anyway - just because I don't know if we can always _totally_ remove that race condition, or at least as a safety measure, but I think we can keep it to a minimum.

[markmandel]

Just a heads up - starting some work on this. 😃

[markmandel]

Fun question for you all - do you think that this functionality should live between one feature gate, or two?

My current WIP code has two feature flags, as each part of the functionality felt separate to me. But would love to hear thoughts.

• The StateAllocationFilter flag controls the gameServerState filter functionality.
• The PlayerAllocationFilter flag controls the players filter functionality.

I originally had this as one AdvancedAllocationFilter flag (or something similar), but decided I didn't like it too much, as it does actually seem to be two different pieces of functionality in the Allocation system.

What do people think?

[domgreen]

I think this makes alot of sense as both features can be used individually :+1:

[rcreasey]

Yeah, this is good for my purposes as well :)

[markmandel]

Just a status update, since I know this is a hot feature request! Work is going well! I just wrote the following e2e test to test out allocating a GameServer and then retrieves it again via an Allocated required state filter, and then the same with preferred.

So far so good!

Next step, writing out a e2e test to try the same with player counts, but I'm not expecting trouble there since it's just another filter to allocation.

func TestCreateFleetAndGameServerStateFilterAllocation(t *testing.T) {
    t.Parallel()

    fleets := framework.AgonesClient.AgonesV1().Fleets(framework.Namespace)
    fleet := defaultFleet(framework.Namespace)
    ctx := context.Background()

    flt, err := fleets.Create(ctx, fleet, metav1.CreateOptions{})
    require.NoError(t, err)
    defer fleets.Delete(ctx, flt.ObjectMeta.Name, metav1.DeleteOptions{}) // nolint:errcheck

    framework.AssertFleetCondition(t, flt, e2e.FleetReadyCount(flt.Spec.Replicas))

    fleetSelector := metav1.LabelSelector{MatchLabels: map[string]string{agonesv1.FleetNameLabel: flt.ObjectMeta.Name}}
    gsa := &allocationv1.GameServerAllocation{
        Spec: allocationv1.GameServerAllocationSpec{
            Required: allocationv1.GameServerSelector{LabelSelector: fleetSelector},
        }}

    // standard allocation
    gsa, err = framework.AgonesClient.AllocationV1().GameServerAllocations(fleet.ObjectMeta.Namespace).Create(ctx, gsa, metav1.CreateOptions{})
    require.NoError(t, err)
    assert.Equal(t, string(allocationv1.GameServerAllocationAllocated), string(gsa.Status.State))

    gs1, err := framework.AgonesClient.AgonesV1().GameServers(fleet.ObjectMeta.Namespace).Get(ctx, gsa.Status.GameServerName, metav1.GetOptions{})
    require.NoError(t, err)
    assert.Equal(t, agonesv1.GameServerStateAllocated, gs1.Status.State)

    // now let's get it back again as required
    gsa = gsa.DeepCopy()
    allocated := agonesv1.GameServerStateAllocated
    gsa.Spec.Required.GameServerState = &allocated

    gsa, err = framework.AgonesClient.AllocationV1().GameServerAllocations(fleet.ObjectMeta.Namespace).Create(ctx, gsa, metav1.CreateOptions{})
    require.NoError(t, err)
    assert.Equal(t, string(allocationv1.GameServerAllocationAllocated), string(gsa.Status.State))
    assert.Equal(t, gs1.ObjectMeta.Name, gsa.Status.GameServerName)

    gs2, err := framework.AgonesClient.AgonesV1().GameServers(fleet.ObjectMeta.Namespace).Get(ctx, gsa.Status.GameServerName, metav1.GetOptions{})
    require.NoError(t, err)
    assert.Equal(t, agonesv1.GameServerStateAllocated, gs2.Status.State)

    require.Equal(t, gs1.ObjectMeta.Name, gs2.ObjectMeta.Name)
    require.NotEqual(t, gs1.ObjectMeta.ResourceVersion, gs2.ObjectMeta.ResourceVersion)

    // and again as preferred
    gsa = &allocationv1.GameServerAllocation{
        Spec: allocationv1.GameServerAllocationSpec{
            Required: allocationv1.GameServerSelector{LabelSelector: fleetSelector},
            Preferred: []allocationv1.GameServerSelector{
                {
                    LabelSelector:   fleetSelector,
                    GameServerState: &allocated,
                },
            },
        }}

    gsa, err = framework.AgonesClient.AllocationV1().GameServerAllocations(fleet.ObjectMeta.Namespace).Create(ctx, gsa, metav1.CreateOptions{})
    require.NoError(t, err)
    assert.Equal(t, string(allocationv1.GameServerAllocationAllocated), string(gsa.Status.State))
    assert.Equal(t, gs1.ObjectMeta.Name, gsa.Status.GameServerName)
}

Once that e2e done and working, I'll start breaking this into smaller code pieces and start submitting PR's while I work on the docs. 👍🏻

[dzmitry-lahoda]

it seems it little bit overlap with open-match? is it any and what it can replace in open-match? we are integrating open-match, but could go agones+custom redis, and the more agones gets of open-match the less our code.

[WilSimpson]

Here is a dynamic way around the hold/lock issue, however it would require coupling between the server and agones which I'm not sure is desirable. Due to this, the feature could be disabled by default and enabled in the server sdk on a per-server basis. This way it would not effect performance of either agones or the server in anyway when disabled.

You could send a playerId as metadata with a game server allocation. The game server sdk watches for changes to this specific metadata. When PlayerConnect is called, it removes the metadata matching the connection id. The allocation controller then considers minAvailable, it adds the current player capacity plus the number of playerIds in the metadata. The metadata could also contain a player allocation time, and after a set time it is forcefully deleted.

This would deal with race conditions and it is still on the game server to be put back in the pool.