Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Due to spam on this forum, all posts now need moderator approval.

 Entire forum ➜ MUDs ➜ General ➜ Suggested protocol for server to client "out of band" messages

Suggested protocol for server to client "out of band" messages

It is now over 60 days since the last post. This thread is closed.     Refresh page


Pages: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 21  22  23  

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #285 on Tue 02 Mar 2010 11:27 PM (UTC)
Message
As long as there's a clear distinction between instance and model, and this isn't tied to any particular method of computing it, it's probably ok.

I disagree that there should be only one ID field, quite simply because that forces you into a particular way of generating that ID. If you have instance ID and model ID, you're free to use that instead of going through some other complex computation to figure out some item's "unique global hash including instance and model stuff". (The very notion sounds complicated enough, and frankly kind of like overkill in many cases.)


By the way...
Quote:
I am guessing at this stage that rooms are unique (ie. the vnum would adequately identify them) but no doubt this isn't strictly true? For example, in an instance, or if you have rooms generated at runtime? Can anyone clear that up?

There is no requirement in general at all that rooms be unique. In fact, vehicle systems tend to have prototype rooms for e.g. the cockpit and then instantiate that room many times.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Twisol   USA  (2,257 posts)  Bio
Date Reply #286 on Tue 02 Mar 2010 11:40 PM (UTC)
Message
David Haley said:
I disagree that there should be only one ID field, quite simply because that forces you into a particular way of generating that ID. If you have instance ID and model ID, you're free to use that instead of going through some other complex computation to figure out some item's "unique global hash including instance and model stuff". (The very notion sounds complicated enough, and frankly kind of like overkill in many cases.)


I was thinking that the ID field could also be a JSON object or array, not just a simple number or string, to accommodate most scenarios. I don't know about other interfaces, but with the JSON interface for MUSHclient I've just finished writing, you could do something like this, treating the ID as a completely opaque object:

json_data = [=[
  {
    "foo": "bar",
    "bar": "baz",
    "id":{
      "type": "npc",
      "id": "1234567890"
    }
  }
]=]

data = json.decode(json_data):to_lua()
id = data[id]
to_server = {
  action = "take",
  object = id,
}

FooBarToServer(json.encode(to_server):to_json())


The code doesn't ever have to know what exactly the ID is composed of. If it wants to display the ID, well, I don't know.

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #287 on Tue 02 Mar 2010 11:45 PM (UTC)
Message
If the id can be a composite of several fields, that's fine. (I don't really care if it's composite using JSON or something else.) Basically, I don't want it to be a single string or number, because I think that makes it much more complicated to do item caching on worlds that treat models and instances differently. If you can assume certain guarantees about models and instances, you should be able to take advantage of them even if SMAUG (or whatever) doesn't let you make those guarantees.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Twisol   USA  (2,257 posts)  Bio
Date Reply #288 on Tue 02 Mar 2010 11:50 PM (UTC)
Message
Sure, that's fine. Sensible!

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
Top

Posted by Nick Gammon   Australia  (23,165 posts)  Bio   Forum Administrator
Date Reply #289 on Tue 02 Mar 2010 11:57 PM (UTC)
Message
Before I present my proposed system I want to at least convince myself it will work, and am inching painstakingly towards that end.

It will however have the following characteristics:


  • Information will be cached at the client end in such a way that is is language-independent (that is, you could use Lua, JSON, or Swahili for that matter).

  • It will efficiently cache things which have the same attributes (eg. if the server generates 1000 level 4 wolves, their information only needs to be stored once).

  • Caching will survive over client restarts, or server reboots, without any problems

  • The information cached can be added to (eg. adding extra fields) without any problems

  • Server writers do not need to add any extra information, such as version numbers, to their data

  • The cached information could even be shared between servers without problems (eg. production and development servers)

  • You can change your design (eg. switch from Lua to JSON) in mid-stream without affecting the way the caching works (of course, some items may become irrelevant but they won't cause problems per se).

  • It should cope with things like corpses decaying, although I have yet to put that particular part to the test yet

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #290 on Wed 03 Mar 2010 12:10 AM (UTC)
Message
Quote:
Caching will survive over client restarts, or server reboots, without any problems

Out of curiosity, why?

On many servers, when you restart the server and recreate the world, all the GUIDs will change. Therefore your caching will no longer be relevant.

Of course for some servers, the GUIDs are unique across sessions as well as intra-session, so this would work.

Surviving over client restarts seems reasonable.

Quote:
You can change your design (eg. switch from Lua to JSON) in mid-stream without affecting the way the caching works (of course, some items may become irrelevant but they won't cause problems per se).

This seems like an over-complication IMHO.

Quote:
It should cope with things like corpses decaying, although I have yet to put that particular part to the test yet

More generally, this is the problem of items deviating from their models over time. An item's description changing over time isn't too different from an item's durability changing as it gets whacked in combat. The main difference is the frequency of these changes.



Have you considered using a temporal model of some sort, where a server can provide the GUID as well as the last time at which it was updated, which would make it easy to know if you should refresh your cache? This is easier than version numbers, IMO.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,165 posts)  Bio   Forum Administrator
Date Reply #291 on Wed 03 Mar 2010 01:56 AM (UTC)
Message
David Haley said:

Quote:
Caching will survive over client restarts, or server reboots, without any problems

Out of curiosity, why?


Well, if you have lots of room descriptions, like:


A hollow cavern deep underground
Hollow and barren of color and light, this place is overwhelming with
sounds and moisture.  The sound of water dripping and wails of pain and
death can be heard all around you.  Whatever resides in this awful place
does not welcome strangers.


... it seems wasteful to re-download them on a server reboot if you can avoid doing it.


David Haley said:

Have you considered using a temporal model of some sort, where a server can provide the GUID as well as the last time at which it was updated, which would make it easy to know if you should refresh your cache? This is easier than version numbers, IMO.


My system - which I am getting closer to having working nicely - has more than one component.

One is a GUID, which indeed is likely to be temporary. However the attributes of the thing the GUID refers to (eg. "A large fire ant wanders here, cautious of your intrusion.") are likely to be fixed. This second part - the attributes - are what are cached.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,165 posts)  Bio   Forum Administrator
Date Reply #292 on Wed 03 Mar 2010 02:00 AM (UTC)
Message
David Haley said:

Quote:
You can change your design (eg. switch from Lua to JSON) in mid-stream without affecting the way the caching works (of course, some items may become irrelevant but they won't cause problems per se).

This seems like an over-complication IMHO.


It's a side-effect of the simplicity of the system.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #293 on Wed 03 Mar 2010 04:15 AM (UTC)
Message
Quote:
... it seems wasteful to re-download them on a server reboot if you can avoid doing it.

Well, it does seem wasteful. But the alternative -- of persisting across sessions -- means that GUIDs now have to be properly unique across sessions, so that you don't get object #1234 that is now a sword rather than the cached helmet that you have. In other words you force the expansion of the scope "globally unique" from not just one session, but to all sessions of the MUD. Your current GUID generation approach does not enforce this, for example: its GUIDs are unique only within one session.

Quote:
My system - which I am getting closer to having working nicely - has more than one component.

One is a GUID, which indeed is likely to be temporary. However the attributes of the thing the GUID refers to (eg. "A large fire ant wanders here, cautious of your intrusion.") are likely to be fixed. This second part - the attributes - are what are cached.

What I mean is that invariably you will need to refresh these attributes from time to time, for example as corpses deteriorate, if room descriptions change with the seasons, etc.

(Speaking of which, how will you handle dynamic room descriptions?)

My point was that a temporal (not temporary) approach can help you easily determine when a cache is stale. If you get GUID 1234 last modified time 5678, and your cache is dated 5677, you know that you need to update it.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,165 posts)  Bio   Forum Administrator
Date Reply #294 on Wed 03 Mar 2010 05:39 AM (UTC)

Amended on Wed 03 Mar 2010 05:42 AM (UTC) by Nick Gammon

Message
OK, well the solution is that we don't "just" have a GUID.

In my playing around with making these plugins work, I have identified three things that characterize a "thing" on the MUD:


  1. A unique identifier (GUID) so you know one item from another one

  2. Some fixed, or rarely-changing, attributes, like description, mob type, name, class, race, faction, level etc.

  3. Some attributes that change rapidly, for example hit points during a battle, level (for a player), mana etc.


Now the GUID is absolutely required for making sure that you address an action to the correct thing. For example, if there are five mobs in the room, and you are in a group of five, your strategy may be to hit one of them with all five of you, or to maybe sheep one, stun another, sap a third, and then take on the remaining two. Even if the mobs are in every other way identical, the GUID is needed to distinguish one identical thing from another one.

The fixed attributes (like a lengthy room description) are what are candidates to be cached, since that is likely to be the major part of the attributes, therefore taking up bandwith to transmit, but change infrequently.

Finally, the volatile attributes, like current HP, or weapon wear-and-tear, are not good candidates for caching.

My basic strategy is to send from server to client those three things (GUID, attributes, volatile attributes) however since the fixed attributes change rarely we merely send a hash of the attributes. An example of this is the "where am I" message:


location={uid="r.2";hash="390422BACF";}


This tells the player s/he is in room r.2 and the room's attributes, hashed, are 390422BACF.

Now the server knows the attributes of this room actually are:


type="room";name="Limbo";desc="You float in a formless void, detached from all sensation of physical\nmatter, surrounded by swirling glowing light which fades into the\nrelative darkness around you without any trace of edge or shadow.\n";terrain="city";area="52E6691941";


And you can test that in MUSHclient by doing this:


s = [[type="room";name="Limbo";desc="You float in a formless void, detached from all sensation of physical\nmatter, surrounded by swirling glowing light which fades into the\nrelative darkness around you without any trace of edge or shadow.\n";terrain="city";area="52E6691941";]]

print (utils.tohex (utils.md5 (s)))


It prints "390422BACF6924FE26C933EF2C26AF07" - I have chosen to truncate the hash to 10 characters (40 bits).

Now what the server does is store that text string in a STL map under the key "390422BACF".

The first thing the client does upon seeing this location message is to see if it knows of "390422BACF" in its in-memory table. If not, it looks on its SQLite database for it. And as a last resort it asks the server to please send the data corresponding to "390422BACF". The server *will* know how to do that, because it stored the data in memory the moment it produced the hash in the first place.

When the response arrives at the client end, the client saves it in memory, and writes it to the database. That way it *never* needs to ask for that particular item again. Not if the server is rebooted, not if the client is restarted, and not 10 years in the future. The reason is, that since the data is stored, keyed by the hash of the data itself, it must necessarily always be the right data. (This is how Git stores your files internally BTW).

Since the data being stored is simply a string of text, it is resistant to:


  • The data format being changed (the hash would change too)

  • More fields being added (the hash would change)

  • Spelling mistakes being corrected (the hash would change)


What the client does upon seeing the hash for "390422BACF" describing this room is to get the actual data (from memory, the database or the server) and then parse that data at runtime to extract out the room name, description, etc.


The only real potential problem is that the data format may change, or be expanded, resulting in a whole lot of stuff on the database that will never be used. To combat that you simply store it with a date/time stamp, and then periodically clean up the database by deleting old records. If they are in fact redundant, well and good, you have saved some disk space. If not, they will be re-downloaded next time they are required.

David Haley said:

What I mean is that invariably you will need to refresh these attributes from time to time, for example as corpses deteriorate, if room descriptions change with the seasons, etc.

(Speaking of which, how will you handle dynamic room descriptions?)


Well you have two alternatives. One is to simply allow the new descriptions to generate a new hash. For example, on my test database I now have a number of items like this:


dsc="The corpse of the bone naga is buzzing with flies."


So in this case, the GUID stays the same (it is the same item) but the description has changed, so a new hash has been downloaded. This is probably pretty OK, it just means that instead of one entry on the database the naga might have 5 or 6 (one for each stage of decomposition).

Alternatively, you could override the description, that is, move it to the "volatile" part of the message. This probably defeats the savings of caching a bit, but could be considered as another approach.

The same would apply to dynamic room descriptions - whatever the description is, if it is the same as another room's it will generate the same hash, if not, it will get a new one.


- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Xtian   (53 posts)  Bio
Date Reply #295 on Wed 03 Mar 2010 08:24 AM (UTC)
Message
Very interesting. Instead of the server sending a GUID/equivalence-class-ID pair it sends a GUID/hash(over applicable values) pair. Great thing is that this is rather trivially implemented on the server-side.

And of course a server _could_ choose to send the equivalence-class-ID instead of a hash-over-values if it wanted to (but omitting the guaranteed consistency you have with using a hash).

Keep up the great work! Can't wait testing a first implementation when its ready.
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #296 on Wed 03 Mar 2010 03:09 PM (UTC)
Message
I'm not sure that only 40 bits is wise if the idea is that these things stick around "forevermore" and that many items are likely to have many versions as descriptions change etc. You're increasing the probability of collision significantly. It's not so much that a trillion items isn't enough, it's that the likelihood of thinking you have something cached already when it's really something else goes up a lot.

It is good though that the distinction between volatile and generally unchanging attributes is not made explicitly. It's more like you have a list of things given to you, and then a key to a list of other things, and if the server decides to change what is and isn't considered volatile, then things "just work". That is something I was worried about: different servers might have very different notions of what is and isn't volatile and therefore it would be inappropriate for the protocol to enforce decisions about those.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,165 posts)  Bio   Forum Administrator
Date Reply #297 on Wed 03 Mar 2010 07:06 PM (UTC)
Message
I'm worried about collisions myself, and have built code into the server to detect them. When it generates a hash it compares the value already in the table to the one that generated the hash. If they are different we have a collision and the server shuts down before that duplicated hash gets "into the wild". It is a simple matter to increase the hash size, the only reason for scaling it back it to try to reduce message sizes.

The problem with my collision detection is that it only detects a collision in one server session, however that is probably adequate given that the hashes are all generated from the same data, so next time the server reboots it should generate, by and large, the same set of hashes again.

To try to get a look at the scale of the problem I checked out from the Mangos database how many of various things it stores for WoW objects, items, quests etc. ...


18375 object templates
34393 items
329259 creature loot templates
27352 creature templates
8687 quests 
-------
719973 total


Now 2^40 gives you 1099511627776 possible hashes, so assuming that your MUD is no larger than WoW, each single item has 1,527,156 slots to choose from before it collides.

I think that probably with that many possibilities *plus* the server hash-detection code, the likelihood that a duplicate hash will get loose is acceptably low. In any case, increasing the hash size in no way compromises the general design.


I'm glad you like the general design, and in fact the volatile attributes could be added to a static attribute to override it (providing the client takes the static ones first from the database, and adds in the volatile ones afterwards, overwriting where required). Maybe there is a mob that is almost always level 10, but occasionally a level 50 version is created. In this case the "level=10" could be part of the static section, but "level=50" could be in the volatile part, overwriting it.

My initial testing shows that accessing an hashed attributes from the database take an average of 0.001 seconds, and of course is much faster if it is already in the client memory. To download an unknown one is slower, but as the server services such requests in its main comms loop, which is throttled to 0.25 seconds per pass, the average time to receive an attribute from the server is just under 0.25 seconds. In practice you don't notice this, because for one thing you are often receiving attributes from the local cache, and for another this exact same delay is built into processing commands, so a pause of 0.25 seconds is what you expect *anyway* when you type "north" or something.


- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #298 on Thu 04 Mar 2010 04:52 AM (UTC)
Message
Well, that's not really how hash math works, and I agree that the chances are small, but I guess I don't see the point in adding that risk when it's so easy to reduce the probability by just adding a few characters.

I agree that it would be good that attributes in the volatile section always override any present in the hashed section. This way, if a given attribute is almost always the same, you would leave it in the hashed section, but in those few occasions where it switches you override it in the volatile section.

An example:
Normal description: Fred the Fighter is standing here.
But occasionally: Fred the Fighter is sitting here.
Or: Fred the Fighter is fighting YOU!
etc.
Especially for the fighting one, it's a transient state to begin with, so it might as well be sent along. And who knows, maybe you might want to have even that description change depending on how the fight is going.



By the way, it would be fairly easy, I think, to change the networking loop to not throttle everything at 0.25 seconds. I did that a while ago on my game. There's really no need for the server to sit there idle, so as long as you have time until the next 0.25s tick, you might as well look for and process data requests. A quarter of a second could be somewhat annoying especially when so easily avoided.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,165 posts)  Bio   Forum Administrator
Date Reply #299 on Thu 04 Mar 2010 05:39 AM (UTC)
Message
David Haley said:

Well, that's not really how hash math works, and I agree that the chances are small, but I guess I don't see the point in adding that risk when it's so easy to reduce the probability by just adding a few characters.


How many do you suggest, and on what grounds? I am aware of things like the birthday problem where it only takes about 23 people to have an even chance of a collision of birthdays out of a set of 365 days per year.

I can certainly make it 12 characters which will be 48 bits. Would that be better do you think?

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


928,612 views.

This is page 20, subject is 23 pages long:  [Previous page]  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20 21  22  23  [Next page]

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum


[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.