Storing Large Flat Namespaces

Hello,

I'm investigating the possibility of using Git to store a large flat namespace. As an example, imagine a single directory containing thousands or millions of files, each named using a 16-byte guid, evenly distributed.

I'm aware that the Git object model makes various trade-offs, typically in favor of managing source-tree layouts - which it does extremely well. However, perhaps it is possible to carry some of Git's features as a content revision tracker over to other storage applications?

Currently, tree objects for large flat directories are quite large. Doing a git-init, git-add, git-push on a flat directory with 10,000 files creates a tree object that is 24 kilobytes compressed. Any change to a single file would create a whole new tree object, 24 kilobytes every time.

The obvious thought is to "virtualize" or "tree-ify" the namespace, similar to how Git stores its own loose objects. (Is there a proper name for this technique?)

This archive thread touches on that idea:

   http://kerneltrap.org/mailarchive/git/2006/2/8/200585

In particular (quoting Linus):

   "Final note: this means, for example, that git is relatively bad at
tracking a "hashed" nested file directory (like the one git itself
uses), because new files will end up randomly appearing in every
directory, and no directory is ever "stable".

I wonder how bad it is, so I did some calculations. What if Git could "virtualize" the namespace when going from the working directory to the object store, without the user ever realizing it. In other words, Git would insert "fake" tree nodes to split apart large directories. This leaves the question of how useful a working directory with a million loose files is, but pretend for a moment that I have a Git frontend that doesn't do full check-outs to a file system but allows a user to grab single objects from the object store straight into memory.

Ok, this is all back-of-the-napkin:

   H = sizeof(hash) = 20 bytes.
   G = sizeof(name) =  16 bytes.

   N = number of assets = let's say one million (hypothetical)

That means the theoretical minimum size of a tree object (without virtualization) is:

  (H + G) * N = 36 megabytes

If we virtualize, using these parameters:

   B = number of bits we chop from the head of the filename, to create
the tree prefix (i.e., internal nodes)
   D = depth of virtualization (number of internal nodes we need to
traverse before we hit a bucket)

   (...in git's loose object store, B equals 8 and D equals 1.)

We get the following formulas:

                      2^(B*D)  = number of buckets (leaf tree objects)
                N / (2^(B*D)) = number of files per bucket
   (H+G) *  N / (2^(B*D)) = size of a bucket

     2^B * H = size of an internal node

The storage overhead of a single file commit then becomes the size of a new bucket plus the size of the internal nodes back to the root. I.e.,

    (D * (2^B) * H)     +     (H+G) * N / (2^(B*D))

The other interesting parameter is the total number of objects involved in just virtualization overhead. For simplicity's sake, the number of leaf objects is a good metric.

For different values of B and D, this leads to the following overhead on a million-file directory.

    B = 0, D = 0 (how git treats large flat directories today)
        number of buckets: 1
        single change commit overhead: 36 megabyte

    B = 8, D = 1:
        number of buckets: 256
        single change commit overhead: 145736 bytes

    B = 8, D = 1:
        number of buckets: 65536
        single change commit overhead: 10780 bytes

    B = 3, D = 4:
        number of buckets: 4096
        single change commit overhead: 9424 bytes

Ultimately, the trade-off is between how may objects are involved in the tree-ification, how many lookups need to be done to get an object, and the storage overhead of commits.

The more I think about it, the less certain I am this kind of data-structure is suitable for my application. I guess Linus's quote at the top summed it up.

I'm wondering if anybody else has put any thought into this kind of thing, and has suggestions for alternate data structures that could enable Git to store large flat namespaces.

Thoughts are welcome. Or am I out to lunch?

Thanks,

Jaap Suter - http://jaapsuter.com

I realize that an obvious suggestion may be to figure out if there is a way to leverage the internal structure of the files to create a more Git-friendly tree layout.

Unfortunately the internal structure is largely opaque to me, and highly dynamic.

Thanks,

Jaap

On Sun, 7 Sep 2008, Jaap Suter wrote:

Sure. But as soon as you repack that repository, there will be only one 24-kilobyte tree object for the latest revision and older revisions will have their tree object stored as a delta against the latest one, which should be merely the size of the changed entry only.

As to the idea of splitting a large flat directory namespace into sub-trees... that would only help in the commit case which isn't that interesting since commits are done much less frequent than, say, directory walking. In the later case, you might end up inflating less object data for files at the beginning of the directory but more for files towards the end, which on average won't be a gain. And in all cases you're looking up more objects. And, to benefit from any advantage left if any, you'd need to do significant surgery in the tree walking code, otherwise simply reconstructing the current object format from subtree objects won't bring any advantage over the current packed format using deltas.

The pack V4 should in theory be much better with large directories since the design of its tree object representation would allow walking partial tree by recursively following deltas making a complete tree walk almost linear in terms of processing and data touched. But that too requires a major surgery of the tree walking code (the main reason holding me back from rushing into any pack v4 work at the moment). But pack v4 won't change anything in the commit case -- you would still have to repack in order to benefit from it.

Nicolas