From: Jon Smirl <jonsmirl@...>
Date: 2006-08-13T23:57:04+09:00
Subject: Re: Looking for a Fast Persistent Store

On 8/13/06, Francis Cianfrocca <garbagecat10@gmail.com> wrote:
> On 8/12/06, Bill Kelly <billk@cts.com> wrote:
> > Hi,
> >
> > What is being measured?  Access time for files that already exist?
> > Creation of new files?  Scanning the directory structure for a list
> > of existing files?
> >
> > At a prior gig, we used to split a couple hundred thousand
> > encyclopedia articles up as 12/34/56.xxx sort of format.  It worked
> > adequately for our needs--our batch-oriented processing was expected
> > to run overnight anyway--but my impression was that as long as the
> > filename was known, accessing file 12/34/56.xxx seemed quick,
> > whereas directory scans to enumerate the existing filenames were
> > pretty slow.
> >
>
> I wanted to put a rough lower bound on the performance of the
> approach, just to decide if it's worth pursuing at all. (Kirk
> obviously thinks it is, but I don't know if the class of applications
> that interests him is anything like the class that interests me.) So I
> measured creation of 1k files and re-writing of 1k files. (The prior
> case involves creating an inode and data pages, the second involves
> touching an inode and creating data pages.) I didn't test reads of the
> files (which would involve touching an inode) because I didn't feel
> like optimizing the test (by remounting my filesystem with the
> inode-touch for last-access turned off). The test box was a
> medium-powered Linux workstation with a 2.6 kernel, a single SATA
> drive, and ext3 filesystems.

You are rebuilding many of the features of git.
http://git.or.cz/index.html

Git is the SCM designed by Linus to replaces Bitkeeper. C source code
is freely available.

The git file store hashes files into an array of 255 directories and
keeps them initially as small files. Later on you can run a pass which
transparently converts them into single file packs. A pack may have
many thousand files that can be accessed via their hash name. Packs
recover the space lost to block fragmentation. Git directory objects
are used to map hash names to human readable strings.

When packs are created there is code that searches for similarities
between files in the pack. If similar files are found they are stored
as deltas from the original file. All objects stored in the system,
files or packs, are zlib compressed.

It wouldn't be a lot of trouble to take the indexing code out of
cLucene and adjust it to use the git file store.

Transactions are achieved by first adding all of your files to the
file store, then a single 'commit' makes them become visible.  If you
never do the commit there are tools for pruning dangling objects out
of the db. But the dangling objects aren't visible so it's just a
cleanup step.

Git is an archival system, objects in the database can not be changed,
they can only be superseded by a later version. Cryptographic hashes
will immediately detect if something in the db has been altered.

I have multi gigabyte git files stores containing millions of objects.
Performance is pretty constant until your working set won't fit into
memory. The killer feature of these file stores is support for
distributed replication with multiple people adding objects to their
distributed copies.

-- 
Jon Smirl
jonsmirl@gmail.com