[Verse-dev] [Verse-dev]understanding event collapse

[Eskil Steenberg]

Hi

This has turned out to be an issue that is hard to shake, and I have 
perhaps been too quick to dismiss proposed changes with out properly 
explaining how this works. (i think i have written something like this 
in the past but anyway....)

The basis of this system is that UDP network packets can arrive out of 
order. or get lost (if a packet gets lost it will be resent and hence 
out of order, so in this mail i will only refer to this as out of order.)

if we now consider us sending thees 2 commands:

verse_send_g_layer_create
verse_send_b_init_dimensions

if thees two commands arrive out of order it doesnt matter because the 
deal with two different parts of the data set that can be updated 
independently.

However, what if the two commands are the same commands? lets imagine 
that we send the following two commands:

verse_send_b_init_dimensions(1, 128, 128, 1);
verse_send_b_init_dimensions(2, 256, 256, 1);

if thees two commands arrive out of order it doesnt matter either 
because even if they use the same command they deal with two different 
nodes. The problem comes when you have two commands that deals with the 
same data:

verse_send_b_init_dimensions(2, 128, 128, 1);
verse_send_b_init_dimensions(2, 256, 256, 1);

Now this would be parsed as the bitmap should have a size of 128*128*1 
and then it is changed to 256*256*1. If the two arrive out of order 
there will be a problem, because the node will first be 256*256*1 and 
then 128*128*1. In other word we would get the wrong result and the two 
sides would be out of sync.

As far as i know there is only 2 ways of solving this, the first and 
obvious one is to wait for both commands and the re-order them before 
parsing them. This is what TCP does and it works fine for file transfer. 
The problem with this is that you have to wait for the later packet 
before you can parse any of the data that should have came after it, so 
it creates a lock up. (the most common reason for out of order packets 
are packet re-send so the round trip to request a re-send and then get 
it can be quite long) 

In verse this problem had to be solved in a different way for 
performance reasons. Here is how we do it:

If we take a closer look at the commands used in the earlier examples we 
see that we can divide each command in to two parts, address and data:

Address: verse_send_b_init_dimensions(VNodeID node_id,
data: uint16 width, uint16 height, uint16 depth);

Any two commands with the same address will over write each others data. 
therefore we define the address and data block of all commands. (you can 
actually see the definitions of the commands in the v_cmd_def_ files in 
verse, wherever the enum VCGP_END_ADDRESS is used)

We can now quickly take any two commands and compare their address to 
see if they over write each other. So how do we use this to fix the out 
of order problem? well if we send:

verse_send_b_init_dimensions(2, 128, 128, 1);
verse_send_b_init_dimensions(2, 256, 256, 1);

and they arrive in the wrong order and the sender is asked to re-send 
the first command. The sender can then simply look in to its history and 
see that the second command over writes the first one. so it ends up 
ignoring the resend request to avoid delivering the two out of order. So 
all the receiver will only get is:

verse_send_b_init_dimensions(2, 256, 256, 1);

clear?

It gets a little more complicated. Lets take a look at thees two commands:

verse_send_g_layer_create(2, 3, "heat", VN_G_LAYER_VERTEX_REAL, 0, 0);
verse_send_g_layer_destroy(2, 3);

If you think about it the two functions have the same address (they both 
deal with node 2 layer 3), but they are not the same API call. That is 
true, but they are the same command in the network! internally in the 
spec the verse_send_g_layer_destroy is called an "Alias" of 
verse_send_g_layer_create. so lets see what this means. lets say we send 
these three commands.

verse_send_g_layer_create(2, 3, "heat", VN_G_LAYER_VERTEX_REAL, 0, 0);
verse_send_g_layer_destroy(2, 3);
verse_send_g_layer_create(2, 3, "cold", VN_G_LAYER_POLYGON_FACE_REAL, 0, 0);

they would set one layer, then destroy it and then re set it. but lets 
say this came out of order:

verse_send_g_layer_create(2, 3, "heat", VN_G_LAYER_VERTEX_REAL, 0, 0);
verse_send_g_layer_create(2, 3, "cold", VN_G_LAYER_POLYGON_FACE_REAL, 0, 0);
verse_send_g_layer_destroy(2, 3);

then the network protocol would remove the last call to get the correct 
output:

verse_send_g_layer_create(2, 3, "heat", VN_G_LAYER_VERTEX_REAL, 0, 0);
verse_send_g_layer_create(2, 3, "cold", VN_G_LAYER_POLYGON_FACE_REAL, 0, 0);

This means that the last command received rules disregarding what came 
before. a  callback has to be ready to change the state disregarding of 
what was before. if the client is asked to create a layer where there 
already is a layer, it has to overwrite the current state. you would get 
the exact same state if you only sent:

verse_send_g_layer_create(2, 3, "cold", VN_G_LAYER_POLYGON_FACE_REAL, 0, 0);

In this text i have used commands that you may not use too often as 
examples, but this system is in place for 90% of the API (the exceptions 
are mostly connection commands)

Now it becomes obvious why verse thinks that:

verse_send_g_layer_create(2, -1, "heat", VN_G_LAYER_VERTEX_REAL, 0, 0);
verse_send_g_layer_create(2, -1, "cold", VN_G_LAYER_POLYGON_FACE_REAL, 
0, 0);
verse_send_g_layer_create(2, -1, "moist", 
VN_G_LAYER_POLYGON_CORNER_REAL, 0, 0);

is the same as:

verse_send_g_layer_create(2, -1, "moist", 
VN_G_LAYER_POLYGON_CORNER_REAL, 0, 0);

I have been contemplating how to fix the illegal id problem, to make it 
side step the event compression as emil suggested, but this doesnt 
change the basic idea of one address per data, and that any command over 
writes all previous state disregarding of what was before. If we break 
that we break everything.

There are some things that you have to think about when you code verse 
that is in its very nature. when verse was designed we did not just take 
in to account usability, there where many factors. such as  performance. 
Verse is and was designed to be a low level API, and that means that you 
sacrifice ease of use for performance and control. I dont mind this 
because i know the a higher level API can be implemented on top of  
verse that fixes that.

Every one who writes apps for verse at some point or an other wants to 
change the API (me included, for every app Ive written)  This is why I 
have implemented Enough and other tools so that i more easely can do 
what i want whit verse. You are free to use my higher level API too, but 
to force people to use it just wrong. Purple is an example of an app 
that doesnt fit very well with how Enough was written so Emil is free 
not to us it and that is a good thing.

E