Skip to main content

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [provisioning-dev] Improved update generation/distribution algorithm

This is really interesting too.  What kind of space reduction measurements have you gotten?


Regards,

Dave
----- Original Message -----
From: Stefan Liebig <Stefan.Liebig@xxxxxxxxxxxx>
To: provisioning-dev@xxxxxxxxxxx
Sent: Thursday, April 26, 2007 3:41:50 AM GMT-0800
Subject: Re: [provisioning-dev] Improved update generation/distribution algorithm

I think the approach taken by us (http://wiki.eclipse.org/index.php/GPW_Lightning_Retrospectives#Smartup_software_update) is somehow similar. At least we have the same requirements. Would be nice if we could join our efforts. For that I will give you a brief outline of our mechanism/algorithm.
First our alg. updates resources from V(n) to V(n+delta) with delta>0 in a single step. Resources might be jars, zips, dlls, docs, ...
Since our solution is not (yet) eclipse based we do not have plugin jars like eclipse has. But this is not a general restriction for our mechanism.
 
Our mechanism is based on delta encodings (http://en.wikipedia.org/wiki/Delta_encoding).
In our particular case we have decided to use the xdelta alg. (http://en.wikipedia.org/wiki/Xdelta) which is pretty good usable for many types of data. However, it performs very bad when ´diffing´ compressed data like zips and jars.
Because of that we unpack zips (in memory) into somthing similar to a tar and perfom the ´binary diffing´ on the different version of these ´tars´. The resulting delta (or patch) is then zipped (it really gets smaller!) and send of the wire. ´Applying´ this delta on the ´old´ version creates the ´new´ version of the ´tared´ resource. The resulting version is then converted back into a zip.
For this mechanism to work properly it required that versions of resources can be uniquely identified. For this identification we use a combination of the resource name and the MD5 hash of the resource. The resource name is similar to the artifactId in mavens project.xml, i.e. the name of the resource without any version specific parts in it.
 
The simplified update flow is:
- the client gets somehow the information that a resource should be updated to a newer one
- therefore it asks the update server for the delta between the old and the new version
- the update server generates the delta or has it already generated and cached and sends it back
- the client applies this delta to old version and gets the new version
This happens for all required resources.
 
Our update server is an active server component realized as a servlet. It manages all resources in their different versions. The server is capable of generating deltas in advance and keeping them in a cache for faster response times. If a requested delta is not available it generates them on demand.
In case that a delta is requested for a ´very´ old version of a resource which is no longer available on the server (has been removed by an administrator) the server will respond with a zipped version of the complete resource. Every delta/patch send to the client has a type that tells the client how to handle the ´delta´.
The situation that the server does not have a base (old) version for generating a delta may also be the result of the manipulation of a resource on the client side. The identification for this manipulated resource (resource name + md5 hash) will most likely not reference a resource on the server. This case will also result in returning a complete (zipped) resource.
 
As I already mentioned it seems that Dave and we have similar requirements but we solve them differently. The challenge will be to provide with the new provisioning a base where different mechanisms can be plugged in.
There might also be a generalized delta layer in which Daves and our solution could be plugged in.
 
Comments, questions?

Stefan


Von: provisioning-dev-bounces@xxxxxxxxxxx im Auftrag von David J. Orme
Gesendet: Do 26.04.2007 00:22
An: provisioning-dev@xxxxxxxxxxx
Betreff: [provisioning-dev] Improved update generation/distribution algorithm

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


Back to the top