[Standards] Proposed XMPP Extension: Roster Versioning
dave at cridland.net
Thu Mar 6 11:55:40 UTC 2008
On Thu Mar 6 09:45:17 2008, Richard Dobson wrote:
>> A few hours of testing does not a reliable protocol make. Under
>> 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
>> 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
> 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,
>> 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 :
>> "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
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,
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
That's "strictly non-decreasing", and neither "unique" nor "strictly
The problem here is that a roster push only contains one item, so two
roster pushes would involve the same sequence value. (See rfc3921bis,
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
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
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
>> 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
>> 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
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
FWIW, I'm not convinced that the additional traffic here is worth
worrying about at all either way.
Dave Cridland - mailto:dave at cridland.net - xmpp:dwd at jabber.org
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade
More information about the Standards