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:[EMAIL PROTECTED] - xmpp:[EMAIL PROTECTED]
- acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
- http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade
