[tahoe-dev] version advertisement and negotiation

[Brian Warner]

Zooko and I have spent an afternoon or two talking about what would be
the best way to handle version negotiation. The basic model is that a
server advertises something about itself, and later a client must
decide how to talk to that server based upon the advertisement.
Reducing round trips is nice, and being able to reduce our dependence
on connections is nice too. So if the client can figure out what to say
ahead of time (instead of trying something and then falling back to
something else if an error occurs), that's slightly preferable.

There are a lot of ways to approach this issue, and I wish somebody had
published a book on what the relative merits are for each. I'm vaguely aware
of the techniques used by a handful of existing systems (ssh, HTTP, things
like that), and I've implemented one or two myself (foolscap, the buildbot
slave-commands protocol), each with their share of flaws. The biggest problem
with this field is that most of the important questions don't come up until
well after the protocol has been defined. Dealing with old versions isn't
important until you create a new version to replace it :).


= Proposed Design =

The scheme that Zooko and I have mostly settled upon is as follows:

 * the documentation defines a series of "Protocol Versions". Each has a
   number (a small integer). This document defines exactly what that protocol
   means: "a server which claims to support version 2 shall accept messages
   X, Y, and Z, with the following meanings and limitations:..". This
   document may be refined and updated over time, particularly as limitations
   are discovered in existing versions, but in general, once a protocol
   version is allocated, it is not changed. The document may also define
   protocols that have not been implemented yet, to enable clients to take
   advantage of new features that become available in the future.

 * the server advertises a set of protocol versions that it provides. Each
   separate service exports a different set: in Tahoe, the "storage" service
   might advertise support for v1 and v2, whereas the "helper" service would
   advertise a completely unrelated set of versions. The supported set is
   expected to be fairly small, because new protocol versions are not created
   casually. It also advertises a fast-changing not-well-documented
   application version number, taken from the revision control system.

 * the client behavior depends upon the server advertisement. The logic will
   look like this:

     if 3 in server_supported_versions:
          speak_three()
     elif 2 in server_supported_versions:
          fallback_to_two():
     else:
          raise CannotUseThisServer()

   The client might also just switch to using a different server instead of
   raising an exception.

 * the application version is published as a hedge against behavioral changes
   (probably bugfixes) that weren't recognized as warranting a new protocol
   version. If necessary, the client will use it as follows:

    def speak_three():
        if server_application_version < "1.2.0r1234":
            workaround_old_bug()
        do_operation()


We currently have two use cases: things in Tahoe that need versioning because
we've already identified changes that were made or need to be made; changes
which clients may want to be aware of.

The first is the storage protocol, specifically the allocate_buckets call
that is used to upload shares of immutable files. The current container
format uses a 4-byte field for the share size, which imposes roughly a 4GiB
limit on the share size, which translates into about a 12GiB limit on the
size of an uploaded file (see ticket #346 for details). We're in the process
of fixing this, but the result will be three distinct versions of the storage
server:

 server A: uploading a large share will result in silent corruption (the
 large share size will wrap when it is written to the 4-byte field, so
 subsequent downloads will fail)

 server B: uploading a large share will result in an exception, as the server
 does a precondition(size < 2**32) before writing the share size to disk.

 server C: uploading a large share will succeed, using a new container format
 with 8-byte size fields.

Now, from the point of view of an updated client (one which knows about all
of these versions), what should the client do?:

 server A: don't send large shares: use a different server instead, or raise
 an exception if there are not enough large-share-capable servers available

 server B: don't send the large share, but if you do, you'll get an
 exception, so at least we won't get silent corruption.

 server C: go ahead and send the large share

So the client doesn't really need to distinguish between A and B, just
between (A,B) and (C).

We also want to make sure that old clients keep working. Specifically, we
don't want an existing client to refuse to use server C just because the
server looks too new.

In this case, we'd define the following protocol versions:

 * protocol 1: share size is limited to 2**32-1
 * protocol 2: just like protocol 1, but share size is limited to 2**64-1

We'd declare that both server A and server B support protocol 1. Server C
would announce support for both protocols 1 and 2. (in fact, since we haven't
added this version-publishing code yet, we'd write the client to interpret a
"no versions advertised" condition as meaning "supports only protocol 1").


The second use case is the Introducer protocol. We're slowly moving to signed
announcements (ticket #466). The new introducer protocol is quite different
than the old one. In this specific case, we're embedding version numbers in
the foolscap method names (since we're constrained to make the existing
introducer.furl keep working), but the principles are the same.

 server A: accepts only unsigned announcements
 server B: accepts both signed and unsigned announcements
 server C: accepts only signed announcements

A client which can only produce unsigned announcements can use (A,B), but not
(C). A client which can produce both can use all three. A client which
produces only signed announcements can only use (B,C).

For this one, we'd define the obvious protocol versions:

 * protocol 1: unsigned announcements
 * protocol 2: signed announcements

And of course A advertises 1, B advertises 1+2, C advertises 2. Clients use
protocol 2 if they can, else fall back to protocol 1 if they can, else fail.

= Temporary Development Protocols =

The #466 signed-announcements work exposes another wrinkle: sometimes we'll
have a protocol that isn't finished yet, one that we need to be able to test
out, but that we don't want to commit to supporting forever. The signed
announcement format uses pycryptopp EC-DSA signatures, which are in flux
right now (the next release of pycryptopp will change the serialization
format, so public keys exported by the old version will not work with the new
one).

For this, we'd define three protocol versions:

 * protocol 1: unsigned announcements
 * protocol 2 (temp): signed announcements, using old pycryptopp serialization
 * protocol 3: signed announcements, using new pycryptopp serialization

The first version of the server that supports #466 announcements would
advertise that it supports protocols (1,2), and it would also have a
versioned dependency on pycryptopp that excludes the newer version. The
finished version of the server would advertise support for protocols(1,3),
and would depend upon the newer version of pycryptopp.

During development, the client would attempt to use protocol 2, and fall back
to protocol 1. Once the pycryptopp release is done, the client would be
changed to attempt protocol 3, then fall back to protocol 1.

This would let us run tests against a combination of (1) and (1,2) systems,
and then deploy a combination of (1) and (1,3) systems, while not requiring
us to support the old pycryptopp serialization forever. Of course, we'd
prefer to not make a release with the protocol-2 code, since that would cause
upgrade headaches for anyone who deployed it. But even if we did, there
wouldn't be any confusion at the protocol level.

= Issues =

Zooko pointed out that it's a bit weird to classify the 2**32-1 share-size
limitation as a feature rather than a bug, by indicating it with a separate
protocol version. We could, if we wanted to, use the application-version
string to make this distinction: in this approach, there would be a single
protocol version, supported by all servers, but the client would need to
distinguish between e.g. appversion<1234 and appversion>=1234, by not using
old servers for large shares.

However, the advantage of protocol versions is that they can be pre-allocated
and defined before any code is actually available to implement them. So, we
could define protocol versions 1 and 2 as above (differing only in their
share-size limitations), and write client code that would distinguish between
the two (by only sending large shares to servers which support protocol 2),
and then ship that. Later, in some future release, we could actually
implement protocol 2 in the server side, and all existing clients would
automatically be able to take advantage of the new server capabilities.

If this distinction were made by examining the appversion string instead,
we'd be severely constrained: either we'd have to commit to lifting the size
restriction in a specific release (and not taking advantage of the fix in
anything before that release, including development versions), or clients
wouldn't be able to take advantage of the new feature until we'd fixed the
server, made a release, and updated all the clients.


= Greetings, All-Knowing Clients From The Omniscient Future! =

We're trying to figure out a good, clean way of looking at all of this. One
perspective is to think about the full spectrum of clients, from the ancient
past to the unknowable future. The future client has complete knowledge of
all server versions: all the bugs, all the protocol changes, so (given enough
code) it can make arbitrarily exact compensation for any given server. The
not-so-future client knows less: it might know about the servers that came
before it, depending upon how quick the developers are (some bugs might not
become apparent for a long time). The older clients probably know very little
about servers that are newer than them, except for changes that can be
anticipated ahead of time (like the lifting of the 2**32-1 share size limit,
above).

The version-advertising mechanism is a way for the server to provide some
information to the client, through a one-way channel. This might be
information travelling from the future to the past: (FUTURE SERVER: "I
support protocol version 1. I handle others too, but you're too old to know
about them". OLDER CLIENT: "Ok, be all mysterious, I'll just use v1"). It
might travel from the past to the future (OLDER SERVER: "I support v1". NEWER
CLIENT: "sigh, I'd prefer v3, but I'll fall back to v1 if I must").

There are other approaches: the client could send a version number along with
the request ("This is a v1 request, interpret it if you can"), but then it's
a bigger impact to we drop older support in newer servers, since there's less
opportunity for fallback (or at least it would require more roundtrips). The
two sides could compare supported-version sets and find the highest point of
intersection, but that's more applicable to interactive connection-oriented
protocols in which both sides need to agree on a common long-term protocol to
use: this is what Foolscap does.

= Compression =

Our design sends the set of supported versions as a set: one or more
integers. If we didn't have things like the "Temporary Development Protocols"
issue to deal with, we could compress this set into a range: a pair of
integers, with the implicit claim that all integers in between are also
supported. Using a set provides a certain amount of pressure against creating
new versions casually: it would be a bit embarrasing for the service
announcement to include thousands of consecutive supported versions.
Hopefully we'll try to change the protocol infrequently, resulting in fewer
versions and smaller sets to advertise. In addition, fewer protocol versions
means fewer combinations to think about in the compatibility matrix (client X
will work with server Y, etc).


So, thoughts? How have folks dealt with these sorts of issues in the past?
What techniques worked well for you?

cheers,
 -Brian