[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [provisioning-dev] Improved update generation/distribution algorithm
A few thoughts...

David J. Orme wrote:
- Is the size of the update site ever an issue?

For us, no. We use a separate physical build server and update site server. For a project like Eclipse, this is a good question, since an algorithm like this would be required to eventually keep terabytes of information around in order to generate diffs.
For those of us who maintain large update sites and can't afford terabytes of disk space, the answer is yes, the size of the update site is an issue to consider :)

- With a server that could run code, have you considered the generation of
the deltas on the fly given what the client has?

Two considerations:
a) big update sites with lots of traffic can potentially require massive server resources to generate deltas on-the-fly.
b) deltas on-the-fly means we can't use the free bandwidth provided by mirror sites. Although sending deltas likely translates to a much smaller transfer than what we send out now, static "dumb http" mirrors also allow users to pick a server geographically close to them instead of one set of servers in one physical location.

Thanks,

Denis

- How do you see that fit with the concept of artifact repository developed
in equinox and our attempt to use a mirroring metaphor instead of download?

This is a way to mirror new versions of plugins between repositories using minimal bandwidth with reasonable assurances of correctness.


ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â "David J. Orme" Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
      <djo@coconut-palm                      Â
ÂÂ Â Â Â Â Â -software.com> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â To
      Sent by:         Âprovisioning-dev@xxxxxxxxxxx    Â
ÂÂ Â Â Â Â Â provisioning-dev- Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âcc
      bounces@xxxxxxxxx                      Â
      rg                          ÂSubject
ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â [provisioning-dev] Improved update Â
ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â generation/distribution algorithm Â
ÂÂ Â Â Â Â Â 04/25/2007 06:22 Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â PM Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
      Please respond to                      Â
       Â"Developer                        Â
      Âdiscussions for                       Â
       provisioning                        Â
        \(Update                         Â
ÂÂ Â Â Â Â Â Â Â Manager\) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â Â initiatives" Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
      <provisioning-dev                      Â
ÂÂ Â Â Â Â Â Â @eclipse.org> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â
ÂÂ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â




The current feature-based update sites can get huge quickly when small
numbers of changes are scattered across a large number of features. ÂThis
kind of situation happens easily when releasing a dot-level or a patchlevel
upgrade--ie: 1.0.0 to 1.0.1--where lots of small bugs are fixed.

The purpose of this email is to open a dialog and to outline our solution.
Apologies in advance for those who are less comfortable with expressing
algorithms in formal math. ÂTime constraints have dictated communication
using the most compact and efficient means possible.

The algorithm we developed worked as follows:

The build server maintains copies of all production versions of the
application. ÂIn the general case, then, we need an algorithm to upgrade a
given user from a version V(n) to a version V(n+delta) where delta is the
number of versions that have elapsed since the user last upgraded. ÂWe want
this algorithm to have the following properties:
ÂÂ Â ÂSend a minimal number of bits across the wire
ÂÂ Â ÂBe as simple as possible
ÂÂ Â ÂBe verifiably correct. ÂWe couldn't afford to have 40k-70k of broken
ÂÂ Â Âclients if the algorithm malfunctioned.
ÂÂ Â ÂRelated to the previous: Have safeguards built-in so that if a bad
ÂÂ Â Âupdate site is ever generated, the whole thing fails fast--before
ÂÂ Â Â*any* bits are ever sent to clients.
You will notice some conflicts in the requirements above. ÂIn particular,
the requirement to send the fewest number of bits over the wire conflicts
with the requirements to be as simple as possible and to be verifiably
correct. ÂThe result was that our algorithm sacrifices some efficiency in
the number of bits it sends over the wire in order to be simpler and more
verifiably correct.

The result: In our application, going from version 1.0.0 to version 1.0.1
using update site features resulted in about a 10 meg download. ÂAfter
applying our algorithm, the download size shrunk to about 3 megs. ÂThis is
still large for some of our users who utilize a dial-up connection, but it
is doable, whereas the 10 meg download would simply be prohibitive.

Here is the algorithm:

First, we simplify the problem. ÂInstead of upgrading users from an
arbitrary version V(n) to V(n+delta), we only upgrade them from V(n) to
V(n+1). ÂGoing to V(n+delta) is simply an iteration of the algorithm over
delta steps. ÂThis simplification works fine for our user population. ÂIf
it would be acceptable for the general Eclipse population is an open
question.

Second, we notice that sending JAR'd plugins is very expensive. ÂSuppose
only two classes in a large plugin change: the whole plugin must still be
shipped.

Our algorithm then is simple. ÂWe dynamically generate a function F where
F(P(V(n))) = P(V(n+1)). ÂF is really just a zipped collection of files that
encodes just the files that changed between the two plugin versions.

This is accomplished using the following algorithm. ÂFor a given plugin P
in two versions V(n) and V(n+1):
ÂÂ 1. Unpack P(V(n)) and P(V(n+1)) into temporary directories.
ÂÂ 2. For files that correspond to each other in the two plugins, MD5 hash
ÂÂ Â Âthem, and if the hashes are different, put the file from P(V(n+1))
ÂÂ Â Âinto F.
ÂÂ 3. Include new files from P(V(n+1)) in F.
ÂÂ 4. Create a text file manifest listing files in P(V(n)) that are no
ÂÂ Â Âlonger included in P(V(n+1)) and include that text file in F.
ÂÂ 5. Package all of the files in F in a zip file.
I believe that the algorithm for applying this function F to P(V(n)) to get
a P(V(n+1)) is self-evident.

This approach has advantages over binary-diffing the two plugin jars
P(V(n)) and P(V(n+1)): If the order of the files contained in the plugin
changes between versions, a naive binary diff algorithm will not achieve
nearly the same amount of "compression" that we achieve.

So we have described a simple algorithm that is able to dramatically reduce
download bandwidth requirements over using update sites. ÂHowever, we have
not described how we achieved the "fail-fast" requirement. ÂIf a flawed
update site is ever generated, we want to detect this automatically at
build time rather than after 50,000 clients have already downloaded it and
broken their installs.

Here is the algorithm we use:

After a build has completed, we have the following artifacts on our build
server:

P(V(n)) - the old version
P(V(n+1)) - the original new version generated by PDEBuild
F - the function (basically an intelligent binary diff) we generated that
we can apply to P(V(n)) to get P(V(n+1))

The approach we take to validate F is the following:
ÂÂ 1. Apply F to P(V(n)) on the build server using the same code that is
ÂÂ Â Ârunning on the clients.
ÂÂ 2. Let's call the result of applying F to P(V(n)), P(V(n+1))' Â(notice
ÂÂ Â Âthe prime there). ÂSo formally, F(P(V(n))) = P(V(n+1))'
ÂÂ 3. We need to prove that P(V(n+1))' is the same as P(V(n+1)), the
ÂÂ Â Âversion originally generated by PDEBuild.
ÂÂ 4. To do this, we simply unpack P(V(n+1))' and P(V(n+1)) into temporary
ÂÂ Â Âdirectories and perform an MD5 hash on all files, making sure that
ÂÂ Â Âall files present in one are also present in the other and that their
ÂÂ Â Âhashes are equal.
ÂÂ 5. If applying F to P(V(n)) on the build server using the same code as
ÂÂ Â Âis running on the clients produces a P(V(n+1))' identical to
ÂÂ Â ÂP(V(n+1)) on the server, then it should work on the clients as well.
In our implementation, all update site building on the build server was
done in Ruby. ÂThe effort to implement the server side of this algorithm in
Ruby was about three days. ÂThe effort to implement the client-side (fully
unit-tested, pair-programmed, one pair programming team working on it
full-time) in Java was about a month. ÂThis was due to the hassle of
working with Java input and output streams. ÂHowever, the result was that
the Java code worked entirely in memory, piping input streams into output
streams and so on until only the final results were written to disk. ÂThus,
the Java solution would be immune to breakage resulting from something on
the file system being changed in a way we did not expect.

Let me know if you have any questions.


Regards,

Dave Orme
_______________________________________________
provisioning-dev mailing list
provisioning-dev@xxxxxxxxxxx
https://dev.eclipse.org/mailman/listinfo/provisioning-dev


_______________________________________________
provisioning-dev mailing list
provisioning-dev@xxxxxxxxxxx
https://dev.eclipse.org/mailman/listinfo/provisioning-dev

_______________________________________________
provisioning-dev mailing list
provisioning-dev@xxxxxxxxxxx
https://dev.eclipse.org/mailman/listinfo/provisioning-dev
  

-- 
Denis Roy
Manager, IT Infrastructure
Eclipse Foundation, Inc.  --  http://www.eclipse.org/
Office: 613.224.9461 x224 (Eastern time)
Cell: 819.210.6481
denis.roy@xxxxxxxxxxx