Friday, December 12, 2008

Single Writer Authoritative Simulator

We can now see how an Entity can have a local cache populated with all the remote Entity proxies it needs by using Interest Management and data distribution over a publish and subscribe message system.

One tough problem remains. What do you do about race conditions if two simulators modify the same Property on an Entity at around the same time? Lightly digging into this reveals a decent solution where such writes would be resolved at a central location and distributed from there so all consumers see the same ordering. However, allowing multiple writers to a single Property can lead to inconsistencies that need sophisticated transaction management.

The easier approach is to disallow multiple writers. Ensure that all properties of an Entity are modified only by that Entity. Any other Entity that wants to make a change must send a request. This boils down to "Communicating Sequential Processes", and is a well-understood computer science paradigm. Normally the Entity stays on one host for a good period of time, and the Entity is said to be Owned by the associated simulator.

The owning Simulator is said to be the authoritative simulator. All computation that affects that Entity is performed on the owning simulator. The values it computes are pushed out to other interested simulators where they become proxies/reflections/replicas, and are read-only.

The single writer paradigm allows a junior game content developer to remain blissfully unaware of concurrency. They think about one Entity at a time. An interaction with another Entity is not trying to read or write to a concurrently evolving set of variables. Instead it is sending a request to the other Entity, which will eventually get around to handling the request sequentially. The developer can think in single-threaded terms. Yay! In fact, the simulator is also made single-threaded so there can be no mistakes (note this still leaves ways to make good use of multiple cores).

The behavior that is running on an Entity is able to immediately read any of the Properties of Entities in which it has already expressed an interest. Since the simulator is single threaded, this can be done without locks. The properties of the proxies are only updated when the message system is ticked, and since the simulator is single-threaded, that is done after the Entities are done executing. Note that because we use state push, the property values of the proxies have the lowest latency *possible*. We can also apply latency hiding techniques to further improve the proxy's estimate of the value on the authoritative simulator.

All this results in a very accurate and familiar representation of a computing environment that appears to have all Entities on the same machine. But since it is actually distributed, its performance will scale. The distributed nature is abstracted away without impacting the developer.

If you are thinking about multi-entity transactions, you'll have to wait for it...

2 comments:

  1. I'm not sure how this solves the race-condition problem when two simulators try to update the same property of the same entity. This may be because I haven't met "Communicating Sequential Processes" before. Can you elaborate?

    When a non-authoritative simulator sends a request to update a property of a remote entity, how does the host simulator deal with the request? Does the request include the new and old values of the property? Could the request be rejected if it appears to be based on old data?

    Gary

    ReplyDelete
  2. As far as the owner of the Entity is concerned, one request or the other is handled first. Since the owner is the only one writing to that Entity, and each simulator is single-threaded, the writes cannot be intermingled.

    I'm guessing you are worried about read-read-update-update when you wanted read-update read-update. That is an atomicity problem, and is solved by encapsulating the "transaction" in a single event handler that is run by the owner. Each read-update action is then fully handled by the target Entity one at a time.

    The other solution would be to perform these kinds of computations using transitive computation (e.g. increment).

    ReplyDelete