Dynamic Shard Allocation

[Arno Haase]

I am thinking about how to build a massively parallel online game on top
of Akka cluster. The game is based on a huge two dimensional "world"
through which players can move.

I would like to scale across several servers, and I would like players
who are close to each other in the game to be co-located on the same server.

Having one actor per player looks like a good fit, but moving these
actors from server to server as the characters move through the world is
tricky.

I know Cluster Sharding, but assignment of entities to ShardRegions is
static.

Any ideas, suggestions or pointers for a design to support this are welcome.

- Arno

[Brian Topping]

I would check out the concept of the "Home Location Register" in the realm of cellular telephony. 

[Arno Haase]

Brian, thanks for the pointer.

I just googled HLR, and the idea I took away is that there is a master
record on a fixed server node (the HLR) with a redundant copy on a
topologically close server node (the VLR) which is updated periodically.

This kind of architecture does not look attractive for my problem, but I
may have missed some key point of HLR / VLR.

But player data changes frequently (several times per second), and I
want to avoid round trips between servers to save bandwidth and reduce
latency. I am looking for a solution that actually moves / migrates the
player actor to a different server node according to where in the game
the player's character has currently moved.

Something like sharding with the same entity moving from shard to shard
over time (and yes, I know that is not how sharding works ;-) )

- Arno

[Brian Topping]

Hi Arno,

What I was considering is the idea that a user is idempotent, but may find itself associated across the cluster to a “world geography”. One shard aggregates users, one shard aggregates geographies. In the analogy, the user shard is the HLR, the geography shard is the VLR. It’s not exact, of course. Communicating between the two is managed by key through the shard region controllers. So the user would maintain the key of the geography that it is currently in, and likewise the geography would maintain a list of the keys for the users that are in it.

From a perspective of locality, it does not change that the user will be instantiated in the node where the shard is “balanced” to. As I re-read your OP, I think I mis-considered your goals.

What if you kept the shard for the geographies and removed it for the users, keeping the latter persistent all the same. Then spread the persistence configuration for users across the cluster (I use ZK for this). The user could then be restored as a child of the geography by the sharded geography actor, on that same node.

A basic implementation would require that the user actor was on one node at a time. You might want some security against the user actor being started in multiple geographies. It might be completely reasonable for the user actor to be multiply available like that, maybe by wiring distributed PubSub into the persistent user actor event loop. I haven’t thought though the scalability or performance of this, just offering ideas.

Brian

> --
>>>>>>>>>>> Read the docs: http://akka.io/docs/
>>>>>>>>>>> Check the FAQ: http://doc.akka.io/docs/akka/current/additional/faq.html
>>>>>>>>>>> Search the archives: https://groups.google.com/group/akka-user
> ---
> You received this message because you are subscribed to a topic in the Google Groups "Akka User List" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/akka-user/_ogMHnVWm78/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to akka-user+...@googlegroups.com.
> To post to this group, send email to akka...@googlegroups.com.
> Visit this group at https://groups.google.com/group/akka-user.
> For more options, visit https://groups.google.com/d/optout.

[Arno Haase]

Hi Brian,

thanks for sharing your ideas.

Am 11.12.2017 um 01:13 schrieb Brian Topping:
> What if you kept the shard for the geographies and removed it for the
> users, keeping the latter persistent all the same. Then spread the
> persistence configuration for users across the cluster (I use ZK for
> this). The user could then be restored as a child of the geography by
> the sharded geography actor, on that same node.
>
> A basic implementation would require that the user actor was on one
> node at a time. You might want some security against the user actor
> being started in multiple geographies. It might be completely
> reasonable for the user actor to be multiply available like that,
> maybe by wiring distributed PubSub into the persistent user actor
> event loop. I haven’t thought though the scalability or performance
> of this, just offering ideas.

Starting player actors as children of geographical regions would provide
locality, and making them PersistentActors would allow (re)starting them
on a different machine as needed.

But that leaves me without all the good stuff that Akka Cluster Sharding
provides:

* Efficient (in terms of latency and bandwidth) lookup of where a
specific player actor currently "lives", i.e. sending a message to it
based on the player's ID

* Ensuring uniqueness while migrating to a new node,

* while ideally minimizing loss of messages while doing so.

The algorithms used in Cluster Sharding rely on a stable mapping from
entityId to shardId. I am looking for a way to get as close as possible
based on a mutable mapping that changes infrequently.

- Arno

PS: What is ZK? I googled it but found only a web framework by that name.

[Brian Topping]

In my view, you'll have to prioritize user actor discovery or locality. I don't think you can get sharding to bring up an actor on an arbitrary node.

The reason for my previous response was you have a 1:n relationship between geographies and users, making instantiated users ideal child actors at runtime.

As far as fast discovery of user actors instantiated in this manner, if I wanted faster resolutionS of users

Sent from my iPhone

[Brian Topping]

In my view, you'll have to prioritize user actor discovery or locality. I don't think you can get sharding to bring up an actor on an arbitrary node.

The reason for my previous response was you have a 1:n relationship between geographies and users, making instantiated users ideal child actors at runtime.

As far as fast discovery of user actors instantiated in this manner, if I wanted faster resolution of users, I would then add the "HLR" concept as a actor that simply maintains a Map from user ID to ActorRef. The HLR would keep a watch on the actors in the map, receiving a Terminated message whenever one was shut down. Then the user actor was started, it would be responsible for its own registration message. This "HLR" could be built as a cluster singleton or with multiple actors using distributed PubSub for redundancy. If performance was not an issue, the HLR could be made persistent. You could also use Distributed Data, but I don't have experience with that yet.

There's a lot of ways to go.

Sent from my iPhone

> On Dec 10, 2017, at 23:04, Arno Haase <arno....@haase-consulting.com> wrote:
>