Re: [Gnu-arch-users] Re: RFC: arch protocol, smart server, and tla implementation prototypes

[Tom Lord]

    > From: Chris Gray <address@hidden>

    > >> Orthogonally, you can make a (client + server time) vs (server
    > >> diskspace) tradeoff by caching more or fewer summaries on the
    > >> server, in a hierarchical decomposition. E.g., if a version
    > >> contains 1024 patches (a nice round number ;-), you can have

    > >> summary-0-1024 summary-0-512, summary-512-1024 summary-0-256
    > >> summary-256-512 summary-512-768 summary-768-1024 ...  :

    > >> So depending on how much disk you're willing to burn, you can bound
    > >> the number of deltas sent for a given DELTA command to around
    > >> log2(#patches in version).

    > > You can also implement the caching/composing logic as part of an
    > > archd proxy.  I can imagine more free-form caching, e.g. server gets
    > > the following requests: 0-39, 0-32, 0-50, 0-60 After these, server
    > > retains summary deltas for 0-32, 32-50.  Or is that 0-32, 32-39,
    > > 39-50?  Or what about 0-39, 39-32, 39-50?

    > > This could get baroque pretty easily, but it would allow lots of
    > > room for tuning.

    > I will probably get flamed by some for saying this, but skiplists [1]
    > do a pretty good job of this without any of that bogosity.

What's being described is a dynamically optimized (in response to
demand) generalization of skip-deltas.  A caching/composing-server
would need a heuristic to decide which which deltas to compute and
cache.  The static algorithms typically described for skip-delta
approaches are one possible heuristic --- if you program a
caching/composing-server with that heuristic: you've got classic
skip-deltas.   Other heuristics may be better in practice, or not --
we don't know yet.

Speculatively: most likely other heuristics _would_ be better in
practice, at least where it matters.  If Linus says, for example,
"here is 2.7" -- and many, many people run `update' for the first time
since "here is 2.6" -- then a more dynamic heuristic can optimize all
of those updates perfectly while a static skip-delta approach would
only optimize them perfectly, sometimes, by coincidence.

-t