[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: random access delta streams

From: Branko Èibej <brane_at_xbc.nu>
Date: 2000-11-14 19:05:21 CET

Jim Blandy wrote:

>> It should be possible, i guess. Right now, our delta format doesn't
>> allow such random-access applying of deltas simply because the windows
>> aren't indexed. You'd have to store a window lookup table with the
>> delta in order to convert seek offsets appropriate windows.
>
>
> Yep. Just on the techno-wanking side, I was thinking of a
> hierarchical index: after every tenth window, store a little table of
> pointers to the windows. After every tenth little table, store a
> little table of pointers to little tables of pointers to windows.
> After every tenth... you see what I mean. Then you can start at the
> end of the file and find any window in logarithmic time. That
> procedure always emits balanced trees. Use 100 instead of ten, and
> your tree has 1/100th the number of nodes as your file has windows,
> and is very shallow.

Aha, you're describing a B+tree of delta windows. Talk about a database
of compressed databases. :-)

>> Another question: when do you need random access to old versions?
>> And if you do, wouldn't it make more sense to store them in the
>> clear, anyway, without having to apply a series of deltas every
>> time? That's what any caching scheme will boil down to, anyway.
>
>
> Greg S. asked some mild questions, and I'm inferring from there.
> The thought arose from the intersection of these issues:
> - Subversion wants to use deltas to store multiple versions of files
> in a compact way.
> - Subversion wants to provide a uniform interface for accessing both
> old and new versions of nodes.
> - HTTP or DAV has some way to ask about substrings of files.

Oooh, that's right: HTTP/1.1 let's you pick a file to pieces.

> I have no compelling application in mind; I'm just trying to meet all
> the promises we're making.

Well, personally I think it would be a great feature to have, and I've a
hunch that it could be a huge performance gain in some situations. I've
no feeling about /when/ we'll need it. I suggest you add this to IDEAS,
and we can pull it out of there when the time's right..

-- 
Brane �ibej
    home:   <brane_at_xbc.nu>             http://www.xbc.nu/brane/
    work:   <branko.cibej_at_hermes.si>   http://www.hermes-softlab.com/
     ACM:   <brane_at_acm.org>            http://www.acm.org/
Received on Sat Oct 21 14:36:14 2006

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.