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

Re: Revised Proposal: Improved locking implementation for fsfs

From: Branko Čibej <brane_at_xbc.nu>
Date: 2005-01-06 03:00:27 CET

Brian W. Fitzpatrick wrote:

>On Tue, 2005-01-04 at 15:17, Mark Benedetto King wrote:
>>On Tue, Jan 04, 2005 at 02:49:00PM -0600, Brian W. Fitzpatrick wrote:
>>>If the node is a directory, the second through n lines will contain a
>>>serialized hash of entries, where the hash key is the name of the child
>>>component, and the corresponding value is the integer of the filename
>>>where the node's lock is stored.
>>If we consider this data element to be a (somehow delimited) list of
>>integers, then we can try to limit the size of the individual dirent
>>files, which should avoid quadratic I/O behaviour (relevant when
>>locking many files in the same directory).
>Can you explain this in more detail please? I don't understand what
>you're saying.
    foo -> 1001
    bar -> 1002
    baz -> 1003

trivially maps to

    (foo, bar, baz) -> [1001..1003]

In short, you can compact sequential lists of numbers. The trouble is,
of course, that the delimiters are all different, so you can't compress
those as in the case of a "normal" list of integers, where, e.g.,




Now if we assume that, on average, the length of a file name is about
the same as the lenght of a decimally-encoded integer, and you locked
all the files in a directory, you'd save around 50% space by compressing
the list into a number range. That may seem like a lot, but it's still
only a constant factor that vanishes in the noise when the quadratic
component begins to make itself felt. Then there's the fact that opening
a file is usually more expensive than reading data from it once it's open.

In short, you avoid quadratic I/O behaviour here in exactly the same way
as we did in the WC -- by caching the entries files. I'm not sure if
this is a valid thing to do in the face of possibly multi-process access
to the FS, though.

-- Brane

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Thu Jan 6 03:01:47 2005

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.