[Standards] Proposed XMPP Extension: Roster Versioning

[Dave Cridland]

On Thu Mar  6 09:45:17 2008, Richard Dobson wrote:
> 
>> A few hours of testing does not a reliable protocol make. Under  
>> what
>> conditions? Is this a public server that people can test against?
>>   
> No you are correct, but even so the tone of some of the messages on  
> this subject as far as I read them said that it wouldn't work, and  
> under my limited testing it does seem to. I can make it publically  
> accessible if you like and actually want to and will have a go.
> 
> 
You can't rely on testing, sadly; you need to prove that it works.

Timestamps probably do work in most cases, as long as the updates to  
the roster are atomically and sequentially performed on a single  
point, and your implementation is sufficiently slow that timestamps  
are obtained at a maximum frequency lower than their resolution. This  
is simply because then you have a strictly increasing sequence.

However, timestamps don't always work like that even on a single  
machine. It just happens that they usually do. I'm not terribly keen  
on making the specification define a new RFC 2119 entry candidate for  
MUST USUALLY. ;-)

>> "It's a lot more efficient with an int, and everything else is  
>> either
>> worse performance, fails entirely, or else is equivalent  
>> difficulty to
>> an int."
>>   
> What sort of things are these? Im not trying to say im right and  
> he's wrong but id like a more full explanation on the points above  
> and below so I can understand why Dave thinks it will break,  
> because as far as I can see all the problems pointed out so far in  
> this thread can be easily overcome.
> 
> 
If you modify a timestamp value, or for that matter generate it in  
such a way that it's strictly increasing, then everything *will*  
work. But since you can model that trivially as a non-negative  
integer, it's not a problem. But since you can, it's a lot easier to  
simply use an arbitrary strictly increasing integer sequence anyway.


>> "One interesting point is that with an int, there's always  
>> something a
>> client can use to get the entire roster, with versioning turned  
>> on."
>>   
> Yea it can just omit the version attribute.
> 
> 
Then it doesn't get versioning. (BTW, I hate that name - there are no  
versions kept. It's not like a client can ask for a previous version,  
and nor does a server need to keep any previous versions).


>> "Put it this way, since the counter-proposal involved timestamps,  
>> which
>> are known to be broken, I'm pretty sure people will get stuff wrong
>> without it being a MUST."
>>   
> Why are they broken?
> 
> 
See previous messages. They're not strictly increasing, nor are they  
strictly non-decreasing, nor are they even unique.

>> And [3]:
>> 
>> "You can't use timestamps - they're not strictly increasing, for
>> various reasons.
>>   
> Why does it have to be strictly increasing, even if it was a  
> timestamp?
> 
> 
Because you want them to have the property that for any known state,  
the server can produce a delta to the current state. Now, as it  
happens, we allow in this specification for a server to give up and  
provide the complete roster, and given this escape hatch, "unique" is  
sufficient if you wanted to produce a really poor implementation.

However, you do need to ensure it really is unique, and given  
multi-core multi-threading clustered servers, about the simplest way  
is to just use a strictly increasing integer sequence. After all, you  
need some central point to perform atomic updates of the roster,  
right?

Now, if what you have is a sequence which usually goes up, but  
sometimes goes down, and is not unique, then updates can simply be  
lost to a client.


>> Firstly, two roster changes could happen at precisely the same
>> moment. To be fair, by introducing cluster node identifiers, and
>> having a strict strong ordering of them, you could avoid this.
>>   
> Why is it a problem if two updates share the same version  
> identifier? Couldn't they not just become part of a single atomic  
> change?
> 
> 
That's "strictly non-decreasing", and neither "unique" nor "strictly  
increasing".

The problem here is that a roster push only contains one item, so two  
roster pushes would involve the same sequence value. (See rfc3921bis,  
Section 2.1.4)

Given this, you need to ensure that either:

a) There is some way to indicate to the client that it now has all  
roster pushes up to and including the sequence value. (ACAP style, if  
you're wondering, since ACAP also has atomic updates spanning  
multiple notifications). This involves an additional stanza, and if  
it's lost, a client will observe all the previous pushes with the  
same sequence value repeated - as such, it's inherently less  
efficient on dodgy connectivity.

b) You cheat and lower the sequence value included in the roster  
pushes, such that the sequence value the client next produces to  
resynchronize will include all those pushes - effectively using a  
subsequent push as an indicator to the client that all pushes  
relating to previous sequence values have now been received.

(b) is less efficient than (a), which has more failure cases than  
simply using a strictly increasing sequence. (b) will always send the  
client data it already has.


>> Secondly, the clock on a computer can, and surprisingly often does,
>> go backwards. That's a much harder problem to solve.
>>   
> As previously requested could you describe this further or point to  
> some more information on this so I can understand how much of a  
> problem this actually is.
> 
> 
It happens. Really and truly, it happens. How often isn't really the  
point.

What happens is typically this:

1) The machine receives updates from NTP.
2) Typically, it adjusts its clock skew to converge on the real time.
3) But, if the clock is sufficiently wrong, it's simply moved.
4) This might be backwards.

Some machines are also configured to move the clock to an NTP derived  
time on reboot - again, if reboots are sufficiently fast, and the  
clock's offset was sufficiently large, that can cause the clock to  
reverse.

Finally, even with a timestamp that never goes backwards, you need to  
ensure that all members of a clustered setup use the same source, and  
moreover test that the obtained timestamp is higher than any previous  
timestamp obtained, so I just fail to see any advantage, really.


>> Thirdly, in a clustering situation, you'd have to ensure that the
>> time on each cluster node was perfectly synchronized.
>>   
> No they don't as previously pointed out (the database layer could  
> generate all the ids).
> 
> 
Yes, and it can generate integer ids just as well, if not better.


>> So the closest you can do would be a modified timestamp that had
>> additional logic during generation to ensure it never went  
>> backwards,
>> in which case you don't need the cluster identifier anymore, and
>> that's effectively the same as having a strictly increasing integer
>> sequence anyway, so it's easier to just do that. But even if you  
>> did
>> want to use timestamps, just representing them as an integer is
>> pretty trivial. Look at the definition of "modtime" in ACAP (RFC
>> 2244), which defines a strictly increasing modified timestamp
>> represented using digits."
>>   
> Yup exactly so the issue about clocks going backwards can be easily  
> overcome then.
> 
> 
"represented using digits". Feel free to do this if you want. RFC  
2244 section 3.1.1, although you'll need to fix the subsecond  
accuracy, so it's comparable as an int rather than a string. But:

1) I would note that the same guys who designed that essentially  
ported it to IMAP as CONDSTORE, and dropped the entire timestamp  
thing, making it an integer sequence instead. (*NOT* a contiguous  
integer sequence, please note - many of the IMAP CONDSTORE examples  
use ACAP modtime formats)

2) I've written an ACAP server. Getting modtimes right is neither as  
simple, nor as fast, as getting an integer sequence right. And it's  
still a strictly increasing integer sequence. (Although it says  
"strictly ascending"). In fact, I know there are failure cases in my  
code, I just hope they're sufficiently unlikely as to not affect  
anyone. Given that I'm probably the only user of my ACAP server, I'm  
probably safe.

I've got a fondness for doing it this way, as it happens, but I'd  
certainly not mandate it, nor encourage anyone else to do the same.

> Is there any chance we can use BASE64 or something to compress the  
> version identifiers in the roster pushes and whatnot?, just like is  
> done with the hashes in caps? Or do we think its probably not  
> really going to be a problem in the future? Granted as an auto  
> incrementing integer it probably wont be much of an issue unless  
> you have an incredibly busy roster, just trying to plan ahead.

It won't compress them if they're integers until you get over 9999,  
since base64 comes in multiples of four characters. So the best way  
for efficiency for the majority is to ensure you use a compact  
sequence.

FWIW, I'm not convinced that the additional traffic here is worth  
worrying about at all either way.

Dave.
-- 
Dave Cridland - mailto:dave at cridland.net - xmpp:dwd at jabber.org
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade