Hi all! Yep, this is another classic rambling drawn out post from me. Hopefully it'll be relatively interesting food for thought, and I'd like to know if anyone has heard of similar systems in operation? Comments and critique of the concepts here are also welcomed. This relies a little on the distributed server architecture and relevance graph topics I've previously gibbered about, so if you haven't skimmed through it: [LINK] One of the caveats of my library design is to allow rapid prototyping of game worlds, and development-in-situ - basically allow superclients to tweak the game's assets whilst they're live, modifying landscapes, adding dungeons, that kind of thing. One of the problems with developing large-world environments (not just for online games but in general) is asset production, as I'm sure everyone would agree. To counter this the library and toolset design encourages a principle of reuse - for example the same terrain heightmap can be used in many different landscape chunks by setting different base elevations and (90 degree) rotations. This causes a problem when a landscape chunk is editted - if that base asset (the heightmap in this example) is used elsewhere, we cannot allow all those other chunks to be modified. We therefore track reference counts for each asset, and if that usage count isn't 1, we clone the asset and save it as a new one before editing it. Simple enough you think - but this presents a problem when propogating the change - the relevance graph explicitly links assets together (if you're in one POR (see link), the neighbouring PORs have to be loaded). Keeping 'real' references to filenames or DB entries for each linked POR asset IN each POR asset causes a cascade of cloning that runs all the way to the root. Not good. It seems to me, the way to solve this potential cascade is to store the assets in an entry for each POR zone, and store links to each POR there also. When a change is made to a POR, a change notification event is triggered that effects all neighbouring PORs and causes a reload of the (now altered) assets from the linked POR. Ok, so we have control of the change cascade. The next interesting problem is caching of asset data across the microcluster. Since chunks of the relevance graph can be arbitrarily reassigned to different machines, the most space-efficient method of storage is in a central repository (blobs in a DB possibly). Not necessarily the most time-efficient though. I'm considering the use of checksum or MD5 hash comparison to check asset cache validity when loaded, or reloaded, with failed comparisons causing a fetch from the central repository for the cluster. Does this seem sensible enough? Should I use blob storage in my central database or code up a simple ftp using UDP? (This would allow fetching to be done relatively slowly, throttled in with all the usual cluster traffic). [Edited by - _winterdyne_ on November 11, 2005 8:10:20 AM]

If you want massive scalability, then you want distribution of your "central" repository. Looking at something like BitTorrent (or even just rsync) for ideas.

When it comes to splitting all the way to the top of the tree when you do copy-on-write, I don't quite understand what your solution is. Suppose your tree looks like:

top
terrain tile A inst 1
heightmap piece A inst 1
terrain tile A inst 2
heightmap piece A inst 2

Where 'terrain tile A' has two instances, as does the referenced heightmap piece. Now, you edit "heightmap piece A inst 2". This means you have to clone that piece of data, and change the reference in the terrain tile A inst 2. That means you're changing the terrain tile, which means you need to clone that, too. This is the "split to top" problem you're describing.

top
terrain tile A inst 1
heightmap piece A inst 1
terrain tile A' inst 1
heightmap piece A' inst 1

I don't see a way around this -- you are changing what the reference is, so a previous reference to a shared terrain tile now has to be cloned.

Yes, so I propose a further level of abstraction to 'wrap' the modification.
I hope you can follow my xml-style spec here, for the sake of easy mental arithmetic I'll specify that terrain chunks are 100x100 meters:

Here we'll describe three terrain PORs forming the west and east slopes of a hill and the summit.

POR_ROOT{   POR_SUMMIT   {       LOCATION = 0,100,0               // POR Location relative to parent       UNIT_SCALE = METER               // POR Unit scale       TYPE = TERRAIN                   // What kind of POR       TERRAIN_GEOMORPH = SUMMIT.GEO   // Geomorph (terrain descriptor)       TERRAIN_ORIENTATION = NORTH       // Geomorph orientation          NEIGHBOURS       {          POR_WESTSIDE,          POR_EASTSIDE       }   }   POR_WESTSIDE   {       LOCATION = -100,50,0             // POR Location relative to parent       UNIT_SCALE = METER               // POR Unit scale       TYPE = TERRAIN                   // What kind of POR       TERRAIN_GEOMORPH = SLOPE.GEO     // Geomorph (terrain descriptor)       TERRAIN_ORIENTATION = WEST        // Geomorph orientation           NEIGHBOURS       {          POR_SUMMIT       }   }   POR_EASTSIDE   {       LOCATION = 100,50,0             // POR Location relative to parent       UNIT_SCALE = METER               // POR Unit scale       TYPE = TERRAIN                   // What kind of POR       TERRAIN_GEOMORPH = SLOPE.GEO     // Geomorph (terrain descriptor)       TERRAIN_ORIENTATION = EAST        // Geomorph orientation           NEIGHBOURS       {          POR_SUMMIT       }   }}POR_ASSETS // Number in [] indicates usage - actually stored in map{   SLOPE.GEO[2]   SUMMIT.GEO[1]}

Ok, lets assume we want to add a small cave to the west side - the slope geomorph on that side will be changed (and have the cave added to it).

When the change is commited by the superclient the following process occurs on the server:

First, the new geomorph asset is created - this could either be by uploading to server from the superclient (simplest) or by patch-and-exemplar (potentially smaller). Either way, the server gets a new asset - CAVESIDE.GEO. This is immediately placed in a central asset store. Local versions can be cached at loadtime if required.

Next, the POR itself is altered, and its entry in the central database updated.
We now have this structure live, on the server the superclient is connected to, and on the central database.

POR_ROOT{   POR_SUMMIT   {       LOCATION = 0,100,0               // POR Location relative to parent       UNIT_SCALE = METER               // POR Unit scale       TYPE = TERRAIN                   // What kind of POR       TERRAIN_GEOMORPH = SUMMIT.GEO   // Geomorph (terrain descriptor)       TERRAIN_ORIENTATION = NORTH       // Geomorph orientation             NEIGHBOURS       {          POR_WESTSIDE,          POR_EASTSIDE       }   }   POR_WESTSIDE   {       LOCATION = -100,50,0             // POR Location relative to parent       UNIT_SCALE = METER               // POR Unit scale       TYPE = TERRAIN                   // What kind of POR       TERRAIN_GEOMORPH = CAVESIDE.GEO  // Geomorph (terrain descriptor)       TERRAIN_ORIENTATION = WEST        // Geomorph orientation             NEIGHBOURS       {          POR_SUMMIT       }   }   POR_EASTSIDE   {       LOCATION = 100,50,0             // POR Location relative to parent       UNIT_SCALE = METER               // POR Unit scale       TYPE = TERRAIN                   // What kind of POR       TERRAIN_GEOMORPH = SLOPE.GEO     // Geomorph (terrain descriptor)       TERRAIN_ORIENTATION = EAST        // Geomorph orientation           NEIGHBOURS       {          POR_SUMMIT       }   }}POR_ASSETS // Number in [] indicates usage - actually stored in map{   SLOPE.GEO[1]   CAVESIDE.GEO[1]   SUMMIT.GEO[1]}

Finally, the change is propogated through the POR system from POR_WESTSIDE. The only neighbour requiring update is POR_SUMMIT. POR_ROOT as parent also gets the event, but ignores it, since it cannot have clients. POR_SUMMIT however triggers a reload event - the POR descriptors are rechecked against the checksums or hashes in the central database, assets are then released / reloaded accordingly. The cascade in this instance stops at POR_SUMMIT.

It sounds to me as if the reason this stops the cascade is twofold:

1) You don't actually use POR references -- east side is not a reference to westside, with a mirror transform. Thus, changing a POR doesn't, in itself, cause a dependency cascade. The cost for this is lost savings in the cases where you could use references, but those are probably few.

2) You only subscribe to relevant parameters. The neighboring information for a specific POR is not relevant to its neighboring PORs, so of course a change there shouldn't propagate. This is a classic interest filter.

Sure that'll work. You might want to look into making the interest/type filtering a little more explicit (say, use a declarative language for the structure of your PORs), and leverage it more.

Yeah - You can see the start of the descriptive / declarative specification here with the use of TYPE = ... which causes different parameters to be searched for while parsing the descriptor, and the POR to behave differently when being placed in the world editor portion of the superclient. I'm still adding to this as I think of new tricks I want it to be able to do.

I'll probably run with a human readable format similar to this for the time being, but eventually drop to a binary-token form (IFF style) to compress things a little bit, make parsing more efficient and save some bandwidth for the central store, which should speed up recovery time after a cluster restart. (All assets and descriptors are checked at restart)

In terms of the interest filter / relevance graph, I have another thread regarding event filtering and attenuation that I'm going to have to post sooner or later. Filtering is not too much of an issue, but attenuation (a feature I think would kick arse immensely) is causing me a few headaches.