WA> Not a tree, but Berstein's CDB has an exceedingly simple
WA> layout, and it might be a good start:
WA>
WA> http://cr.yp.to/cdb.html
WA>
WA> There's ample documentation.

Actually, the Bernstein approach to this would be to not reinvent the
filesystem. The filesystem is quite capable of holding three parts of
a web page to be concatenated together, in three files. The rename()
system call provides atomic update semantics for individual parts, if
one requires those. And directories provide indexing.

Witness the operation of the Maildir mailbox format.

On Oct 24, 9:12 am, J de Boyne Pollard <j.deboynepoll... (AT) tesco (DOT) net>
wrote:

Give that man a cigar.

DS

J de Boyne Pollard <j.deboynepollard (AT) tesco (DOT) net> wrote:
I agree. I'm guilty of not paying sufficient attention to the OP's request.
But also I've given up on this fight. I've been railing against gratuitous
use of SQL databases and other useless data obsfucations for years, but
often you just get some micro-benchmark thrown back in your face; eventually
you just get worn down.

You haven't met the developer of UW-IMAP, yet, have you? Watch out for
useless micro-benchmarks.

William Ahern <william (AT) wilbur (DOT) 25thandClement.com> writes:

[...]

The 'developer of UW-IMAP' never provided a 'micro-benchmark' but just
stated that he doesn't like maildir, because it has an enormously
larger amount of system calls than other mail access schemes.

To put this into contemporary language: It will scale extremly bad and
a sufficiently large installation would be better off using some
database format that provides indexing et. al. without resorting to
the kernel file-system support code for this. 'Sufficiently large'
here depends on the actual kernel being used and on the machine in runs
on.

BTW, have you bothered to determine how many users UWash supported,
using what kernel running on which hardware by the time this quite old
statement was actually written, and to prove that it was really
useless back then?

Rainer Weikusat <rweikusat (AT) mssgmbh (DOT) com> wrote:
11 December 2006

http://www.washington.edu/imap/docum...rmats.txt.html

I never said that Maildir or any other simplistic scheme using files and
directories as storage was the best, most efficienct way of doing things.
I've written my own share of file-backed hash and tree implementations which
blew away existing general-purpose software/mechanisms. But my comment
comports with the above "analysis", IMHO.

It's also a fair assessment, I think, so say that it's a major pain that
UW-IMAP doesn't support Maildir, and that a disinterested third party, with
full view of all the other Unix software which supports Maildir (mutt, etc),
would agree that the reticence is a bit puzzling. On _my_ system Maildir,
with 20+ users, has proven far superior to mbox. But, for various reasons, I
stick with UW-IMAP and mbox (for non-shell users), notwithstanding that the
users who insist on keeping 10MB attachments in their folders continue to
whine incessantly.

William Ahern <william (AT) wilbur (DOT) 25thandClement.com> writes:
As can be verified (at least now, 2007-10-25 19:14:00 CEST) by taking
a look into the old directory of the imap ftp server, this file
appeared in the imap-4.6 distribution, originally dated

[rw@fever]/tmp/imap-4.6/docs $ls -l formats.txt
-rw-r--r-- 1 rw rw 8673 1999-06-06 05:35 formats.txt

[...]

Quoting from the file elleselled above:

There's a general reason why file/message formats are a bad idea.
Just about every filesystem in existance serializes file creation and
deletions because these manipulate the free space map. _This turns out
to be an enormous problem when you start creating/deleting more than a
few messages per second;_

And '20+ users' is certainly within the range of (at most) 'creating a
few messages per second'.

Rainer Weikusat <rweikusat (AT) mssgmbh (DOT) com> wrote:
Point being? It's no excuse for continued reliance on specious analysis.

Is the problem less than or greater than the problem of users keeping large
attachments?

JdeBP> Actually, the Bernstein approach to this would be to not
JdeBP> reinvent the filesystem. The filesystem is quite capable
JdeBP> of holding three parts of a web page to be concatenated
JdeBP> together, in three files. The rename() system call provides
JdeBP> atomic update semantics for individual parts, if one
JdeBP> requires those. And directories provide indexing.

WA> I agree. I'm guilty of not paying sufficient attention to the
OP's
WA> request. But also I've given up on this fight. I've been railing
WA> against gratuitous use of SQL databases and other useless
WA> data obsfucations for years, but often you just get some
WA> micro-benchmark thrown back in your face; eventually you
WA> just get worn down.

JdeBP> Witness the operation of the Maildir mailbox format.

WA> You haven't met the developer of UW-IMAP, yet, have you?
WA> Watch out for useless micro-benchmarks.

RW> The 'developer of UW-IMAP' never provided a 'micro-
benchmark' [...]

True. However several benchmarks _were_ produced in response. Here
are some: <URL:http://courier-mta.org./mbox-vs-maildir/> <URL:http://
people.redhat.com./rkeech/maildir-migration.txt> <URL:http://
www.decisionsoft.com./pdw/mailbench.html>

(And although I haven't physically met M. Crispin, I've been around
for a long time, and I do know who he is. I cited him in one of my
FGAs back in 2004.)

WA> The maildir analysis is specious because it assumes usage
WA> patterns that are far from universal, and in fact may be becoming
WA> less common. And it was specious back then as now because it
WA> made a universal statement based on a set of localized conditions
WA> and metrics, which even _then_ were suspect.

M. Weikusat may not comprehend what you are saying, but I do.
However, I think that you are being unjust. M. Crispin _didn't_
overgeneralize from one set of data. His analysis was a deductive
one, not an inductive one. The flaw that people pointed out was not
overgeneralization, but the erroneous axiomatic assumption that all
filesystems behaved in a certain way, from which the deductions were
then made.

WA> That maildir suffered dismal performance for the usage patterns
WA> of interest to the developers at the time they made their
analysis,
WA> I don't doubt. But the totality of the argument against maildir
rose
WA> to more a general level [of] argumentation. There arose a more
WA> general dispute in the IMAP community.

I remember.

WA> Thus, my point about people using "micro-benchmarks" to shoot
WA> down simple solutions. Often people generalize to the extreme,
WA> and unless one has solid data about a specific operating
condition,
WA> *and* that the specific operating condition will actually be the
WA> normal condition (which is a much harder task), then such a
WA> person has failed their burden of proof. All else equal, in
WA> engineering the rule of thumb is to assume the simpler
WA> solution, layered on established mechanism, to be superior.

It's true that people generalize. But often in my experience lack of
context and lack of knowledge play a part, too. For example: There
was a discussion in alt.folklore.computers last month where one poster
was reluctant to run xyr own example program, on the grounds that it
would create over 17,000 files in a single directory. (To some of us,
that's simply a medium-sized news spool directory.) The worry about
creating that number of files all too often stems from a vague
knowledge that it is bad, gleaned thirdhand as received wisdom based
upon sources that were talking about the FAT filesystem format. It's
not necessarily that people are generalizing from FAT to everything
else. It is sometimes that they don't know that (a) the books and
articles that they may have read were only talking about FAT, because
those books and articles were written at a time and for an audience
where FAT was the only format available and so the fact that FAT was
the filesystem format was implicit and often unstated; or that (b)
other filesystems formats don't have this problem because they don't
have linear directory organizations like FAT does, and that the
problem is fomat-specific. They lack the context to realize that the
old article talking about how bad large directory sizes were was
written from the viewpoint of someone who only had the option of FAT,
and they lack the knowledge of filesystem design to know that not all
filesytem formats are the same in this regard.