git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: space compression (again)

From
MUMartin Uecker <muecker@gmx.de>
Date
Apr 16, 2005, 17:37 UTC
Message-ID
<20050416173702.GA12605@macavity>
In-Reply-To
<Pine.LNX.4.61.0504161101470.29343@cag.csail.mit.edu>
On Sat, Apr 16, 2005 at 11:11:00AM -0400, C. Scott Ananian wrote:
Show 16 quoted lines
> On Sat, 16 Apr 2005, Martin Uecker wrote:
> 
> >The right thing (TM) is to switch from SHA1 of compressed
> >content for the complete monolithic file to a merkle hash tree
> >of the uncompressed content. This would make the hash
> >independent of the actual storage method (chunked or not).
> 
> It would certainly be nice to change to a hash of the uncompressed 
> content, rather than a hash of the compressed content, but it's not 
> strictly necessary, since files are fetched all at once: there's not 'read 
> subrange' operation on blobs.
> 
> I assume 'merkle hash tree' is talking about:
>   http://www.open-content.net/specs/draft-jchapweske-thex-02.html
> ..which is very interesting, but not quite what I was thinking.
> The merkle hash approach seems to require fixed chunk boundaries.

I don't know what is written there, but I don't consider fixed chunk boundaries part of the definition.

> The rsync approach does not use fixed chunk boundaries; this is necessary 
> to ensure good storage reuse for the expected case (ie; inserting a single 
> line at the start or in the middle of the file, which changes all the 
> chunk boundaries).

Yes. The chunk boundaries should be determined deterministically from local properties of the data. Use a rolling checksum over some small window and split the file it it hits a special value (0). This is what the rsyncable patch to zlib does.

> Further, in the absence of subrange reads on blobs, it's not entirely 
> clear what using a merkle hash would buy you.

The whole design of git is a hash tree. If you extend this tree structure into files you end up with merkle hash trees. Everything else is just more complicated.

Martin
 
-- 
One night, when little Giana from Milano was fast asleep,
she had a strange dream.
Previous: C. Scott AnanianNext: Martin Uecker
Message 8 of 10 in “space compression (again)”
  1. C. Scott AnanianApr 15, 2005
  2. Linus TorvaldsApr 15, 2005
  3. C. Scott AnanianApr 15, 2005
  4. Derek FawcusApr 15, 2005
  5. Linus TorvaldsApr 15, 2005
  6. Martin UeckerApr 16, 2005
  7. C. Scott AnanianApr 16, 2005
  8. Martin UeckerApr 16, 2005
  9. Martin UeckerApr 19, 2005
  10. Derek FawcusApr 15, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.