Archived Persistence Ids: Get rid of data that needs to be saved even if the chunk/player is unloaded

[Florian]

Name: Persistence Ids
Summary: Get rid of chunk/player data that needs to be saved even if the chunk/player is unloaded
Scope: Engine
Current Goal: Getting rid of chunk/player data that needs to be saved even if the chunk/player is unloaded
Phase: Design
Curator: Florian
Related: Continous saving of the game

How it is currently done?

When a chunk or player gets saved, the game rembers in memory which external entity references the chunk/player is making.
This is done in a map from player/chunk id to a set of valid external references. See field storeMetadata in StorageManagerInternal.

When now a referenced entity gets destroyed, the game / main thread removes the id from all sets of valid external references.

Other entity may reuse the id, but since it remains absent from the set of valid references of all previously stored chunks/players.

When the entities of the chunk or player get restored, the game checks if external references are still in the in memory set of valid external references
which had been maintained even while the chunk was unloaded. For the valid external references it creates inactive EntityRefs.

See field validRefs in EntityRestorer which gets used via EntityRestorer#loadingRef by EntityRefTypeHandler#deserialize and EntityRefTypeHandler#deserializeCollection

Each time the game gets saved the external reference sets of all loaded and unloaded chunks/players get stored in a global store file.

At the start of a game, all external reference sets of all chunks and players get loaded in memory and stay there.

Thus, larger worlds:
- Load slower, as all external references of unloaded chunks and players need to be loaded too
- Need more memory, as all external references of unloaded chunks and players are kept in memory
- Have longer save breaks

Even if you have only a small part of the large world loaded, the performance impact is there never the less.


My suggestion:


Let have entities have a second id, with a so large number room so that it's id never needs to be reused. For example it could be a 64 bit long.

The second id gets only used for persistence, and will thus not impact the game performance otherwise.

This persistence id will be stored in the EntityRef, as there are not always components loaded when it is needed.
In addition the entity manager will maintain a map from persistence id to inactive EntityRef.

The map uses weak values so that it will automatically shrink when the inactive EntityRef gets no longer referenced

When the entity gets saved, only the persistence ids will be used to store relationships.

When a background task loads entities, it knows also only persistence ids.

When the entities get activated on the main thread, it checks if there is an inactive EntityRef for the given persitence id:
- If there is an inactive entity then it gets activated.
- If there is no inactive entity then a new entity with the given persitence id and a new classic ingame id will be created and it will be put in the map.

If a entity gets destroyed, it's entry from the persistence id to EntityMap map gets deleted

if an entity gets created, it will be given a new persitence id and it will be put in the persistence id map.

For this concept to work it is necessary that an active entity has always the same EntityRef.
While on the other hand it must be possible for inactive entities to be garbadge collected and removed from the persistence id map
when they are no longer in use. To ensure this I suggest that we add a map from entity id to active entity. All EntiyRefs get currently stored in a weak values map from id to EntityRef. By adding a second map for the active entties those will be able to survive garbadge colletions.

Example 1: A good case that shows how it is supposed to work:
Entity A refrences Entity B
The entities A and B get saved and unloaded.
The game garbadge collects the inactive EntityRefs of both A and B
Entity A gets activated/loaded: The main thread creates an active EntityRef for A and an inactive one for B and let A reference it.
Entity B gets activated/loaded: The main thread activates the EntityRef of B and "fills it with data"

Example 2: The simple case that also works:
Entity A refrences Entity B
The entities A and B get saved and unloaded.
The game garbadge collects the inactive EntityRefs of both A and B
Entity B gets activated/loaded: The main thread creates an active EntityRef for B and "fills it with data"
Entity A gets activated/loaded: The main thread creates an active EntityRef for A and "fills it with data"

Example 3: A case where no garbadge collection happens:
The entities A and B get saved and unloaded.
Entity A refrences Entity B
Entity B gets unloaded and saved
No garbadge collection happens
Entity B gets activated/loaded: The main thread activates the EntityRef of B and "fills it with data"

Example 4: A not so ideal case:
Entity A references Entity B
Entity A gets saved and unloaded.
Entity B gets destroyed
When Entity A loads it creates an inactive Entity B which will never become active.

Code can handle inactive entities not much different from destroyed entities, as both have no components.
So I think we are fine in the fourth example too.

With this approach no external reference sets needs to be stored and thus unloaded players and chunks have no performance impact. In addition with this approach it is no longer necesssary to store a free id list. Instead the entities can be numerated from 0 again after a load of an existing world. Thus as a small bonus, entity numbers are kept with this approach small and readable.

This approach does not fully solve the issue, that inactive entity refs do not free their id when they get garbadge collected. However it would be possible to have a background task check for free ids if that turns out to be an issue. Or we could let have inactive entities have only a persistence id. They have no components anyway till they are loaded. Although that might require further changes to other code that relies on the entity to have an int as id.

Do you agree to this suggestion or do you have another idea to solve it better?

 

[Immortius]

I wrote this paragraph last - I think I basically rambled on and then arrived back at your suggested solution but from a slightly different direction and perhaps with some tweaks. An after thought is perhaps we should really look at using something like OrientDB for persistence - as a graph database it would have the advantage that we could just invalidate relationships during save (because 2-way relationships).

---

Firstly, how common are external references? My assumption was that they weren't very common, or involved a small set of objects. Perhaps a quick fix would just require a little restructuring to how we're doing things currently - instead of maintaining information per-store, maintain information per-externally referenced object. This way we won't be adding extra data to load for each chunk (and I doubt the majority of chunks have external references)?

Secondly, if every entity is going to have a 64-bit identifier, this might as well replace their 32-bit identifier. There's no point in having both. If we just change entities so that they have a 64-bit identifier that is never reused, it addresses almost all the issues without having to bother with the rest of the convolution. The one thing it doesn't address is ensuring that a destroyed entity remains "destroyed" - currently this is done by tracking the max used id, and a list of unused ids, which doesn't use too much memory due to id reuse. With ids not being reused, tracking this will be tricky. So I guess we wouldn't bother tracking it. We might need to mess with some of the internal data structures which assume reasonably condensed 0-indexed entities. But... perhaps we're attacking this problem in the wrong direction.

Lets define the problem space as:

• We have a number of Stores, each of which contains entities
• Stores can have references to entities in other stores
• Stores can be loaded in any order
• Any combination of stores might be loaded
• If Store A and B is loaded, and references between entities in these stores should behave correctly
• If an entity is destroyed, when a Store which contained an entity that referenced it is later loaded it should correctly not have a reference to an entity.
• It is expected that a given game session won't last more than 7 days (servers will be restarted once a week) - session resources (not necessarily memory) can be exhausted as long as this happens at a reasonably slow rate and without impacting speed.
• There should be no requirement to persist data tying Stores together - so no StoreMetadata.

So, lets say we don't save entity ids at all - entity ids would be assigned only for a single game session - we can refer to them as game session ids, basically. Instead, when we save an entity into that store, it is given a storage id. The persistence layer would remember a mapping between this storage id and the game session id, but never save it. When loading an entity, first the persistence layer checks if it has a game session id or not. If it does, that id is reused, otherwise a new game session id is allocated. Likewise when loading entity refs, it would be checked whether it has an existing game session id, or a new game session id would be reserved. When saving, if an entity or reference doesn't have a storage id mapped to it, that would be created.

An optimization would be releasing a storage id - game session id mapping when the object is no longer loaded and no references are either.

The end result is similar to your suggestion, but it has the advantages that:

• Persistence ids (storage ids) would only be needed for things that are actually persisted.
  
• Doesn't require feeding persistence implementation specific features up into the entity system. The persistence ids would be kept in the persistence layer, not placed in EntityRefs.

 

[Florian]

I would like to add the following aspect to your problem space:

• The preperation time for saving on the main thread should be very small and constant

At restore it is necessary to check if an game session id is still valid. Thus when an entity gets destroyed on
the main thread we need to remove the storage id -> game session id link.
As a result the map from storage id to game session id needs to be managed by the main thread.

For the saving that means that the storage id -> game session id mapping can't be done off the main thread.
Thus as a preperation for saving, we would have to iterate all entities and check which entities they reference in order to
determine their storage ids.

About using 64 bit everywhere: I am not sure how big the performance gain from this IntMaps is. I know that hashmaps in java are very performant,
so having bigger ids might not slow us down so much and might be a viable option.

About the frequency of external references: I agree that they are very exotic. I would even suggest that we don't store them at all
and save us a big deal of trouble. It is very easy for module developers to work around this small limitation.
e.g. instead of having two active blocks reference each other by entity, they could do it by position.
And the interactionTarget (a external reference of a player) is only valid while the plaayer is there anyway.
Or if there is a town entity and building entities are referencing it then they could simply have a town name as reference and use that to lookup the town.
Such a reference replacement is propably easier for the module to handle than a entity ref that is unusable because the target is not loaded.
In case of the town the user can then at least see/edit the town name of the house. If such a name lookup is commonly needed, it could
be implemented as module. e.g. a ExternalReferenceComponent with a name field + some kind of lookup functionailty..

When we don't store external references, then each chunk can use it's own internal numbering of the entities. Thus we won't
need a free list by this appraoch either.

 

[Florian]

Currently planned processing based on a IRC discussion with Immortius:

During the game:

• The main thread keeps a bidirectional map between persistence id <-> entity id
  
• When the main thread creates a persistent entity, it generates a persistence id and adds it to the persistence id map.
• When the main thread makes a entity persistent, it generates a persistence id and adds it to the persistence id map.
  
• When the main thread destroys a persistent entity, it removes it from the persistence id bimap.
• When the main thread makes an entity non persistent, it removes it from the persistent id bimap
  
• The main thread records a delta of all persistent entity changes since the last save
• The main thread records a delta of all bimap perstence id <-> entity id changes since the last save

On chunk/player unload:

• The main thread destroys non persistent entities
  
• The main thread deactivates persistent entities
• A copy of all deactivated entities and the chunk data will be hold till the next save is done
  
• The components will not be serialized like before and thus still have valid EntityRefs

When a save should be created, the following will be done:

• The main thread starts the save thread with
  • the recorded deltas of the entitties
    
  • the recorded deltas of the storage id map (can be included in teh entity delta)
  • other data that nees to be saved
• The main thread contious with new emtpy deltas
• The save thread uses the delta updates it's own copy of all entties
  
• The save thread uses the delta updates it's own copy of a entity id -> persistence id map
  
• The save thread performs the save based on it's own copy of the data
• When the main thread detects that the save thread is done, it will delete data of unloaded chunks/players that got saved.

On chunk/player restore:

• The restore thread checks if ther is a copy of the chunk/player because it has not been fully saved yet, if yes it reactivates it
• Otherwise the restore thread loads the chunk/player from the disk
• The loaded entities have storage ids and are not known to the main thread yet
• When the main thread has time it uses it's persistence id <-> entity id map to lookup the entities
• (If wanted it could wrap it in a RestoredEntityRef with a persistence id, but that isn't needed.)

 

[Immortius]

• When the main thread creates an entity, it generates a persistence id and adds it to the persistence id map.

I disagree with this one line. Again, if persistence ids are given to every entity we might as well make it the only id and simplify the whole model. I think it is important to only allocate them to things that are persisted to avoid wasting them though.

 

[Florian]

My main reason for suggesting to give all entities a storage id at creation was simplicity. I think wasting them through is not an issue, when we use a java long: Even if we create one million per millisecond we won't run out of number for more than 200 years.

However thinking about it, we might want to do the save delta generation only for persistent entities. So the creation of storage ids for persistent entties only might be not so a big step.

The idea to use simply longer ids for entities has the charm of simplicity. I am not sure how big of a performance difference it would make to use longer ids everywhere. Since the introduction of longer ids would make the change even bigger, I suggest we keep us that option for later.

So is the above suposal okay, if we create persistence ids (and deltas) only for persistent entities?

 

[Immortius]

I think at this point we should just forget about persistent ids, change the entity ids to long, and not reuse ids. This solves all the issues and requires the minimum of change. I'm not concerned about a performance hit with this change.

 

[Cervator]

Curiously, just for notification with builds and such, would that be a world breaking change?

Not that there are a lot of worlds to break, so now would be the time

 

[Florian]

Propably not, but it's to early to promise anything.

 

[Cervator]

Bump. I moved this from the Incubator into Core Projects as it seems like an engine level thing.

Have we "finished" this or is it still pending? Or was it more like a one-time thing than an on-going topic to use to describe how persistence ids work?

 

[Florian]

Entity ids are now longs. This is "finished".