David Wright wrote:
> Quoting Kushal Kumaran:
> > Bob Proulx writes:
> > > If a directory became full it was easy to extend it
> > > by writing the array longer.  But if an early entry in the array was
> > > deleted the system would zero it out rather than move each and every
> > > entry in the file system down a slot.  (I always wondered why they
> > > didn't simply take the *last* entry and move it down to the deleted
> > > entry and simply keep the array always compacted.  I wonder.  But they
> > > didn't do it that way.)
>
> I think the reason for this is that the entries have different lengths
> corresponding to the filenamelength, so you'd have to search for a slot
> small enough. Were this slot not the last entry, then keep repeating...
> I think I can see a pathological end-case here.

But for many years filename slots in directories were of fixed sizes
and yet they still did not move entries around.  They just renamed
them in place.  There wouldn't have been a pathological case in the
old fixed length slots.  I have forgotten how the longer BSD namestyle
slots work.  It might be pathological there.  But those came later.
However that might contribute weight into why it isn't typically done.

> Once you have trees, I'm out of my depth. But I read that trees have
> to be balanced, which may mean a whole new set of algorithms for
> pruning them.

I have worked extensively with trees in memory.  Not so much with
B-trees on disk.  But in both cases there is a big difference between
insertion and deletion.  I should go back and refresh my memory on the
code but I am going to take a risk and just blurt this out anyway.
Rebalancing trees after insertion is always a relatively localized
operation.  AVL trees do it by brute force and there are various
techniques such as 2-3-4 trees and Red-Black that are clever
alternative models.  Basically you prevent the tree from being
pathologically unbalanced and can then always tolerate a little
imbalance so the rotations needed are smaller.

Rebalancing trees after deletion on the other hand is completely
different from rebalancing after insertion.  A deletion may cause a
large rebalancing of a large portion of the tree.  In memory it
probably won't ever get really bad.  Also deletions tend to be less
frequent than insertions for a program using an in memory data
structure.  But for a large B-tree on disk (which I haven't
implemented myself yet) I could imagine it requiring a significant
number of disk operations.  For a directory the number of deletions is
on average the same as insertions.  Deletions are just as common as
insertions.  Marking them empty is likely a significant savings.  It
is only the "industrial strength" file systems such as xfs (and
probably jfs and others) that go the extra code to clean up and
actually delete the entries.

> which may mean a whole new set of algorithms for pruning them.

I wanted to emphasize this.  Yes.  Insertion is easier than deletion.
Deletion requires a significant amount of additional code to handle
properly.  In text books deletion is often left as an exercise to the
reader.  Why?  Because its much harder and less often required.  The
author won't have wanted to delve that deeply into that case.

And as additional commentary when it is in memory for a program if
there is a bug in deletion you can restart the program.  When it is a
file system structure then you would probably lose file data and
require an extensive fsck to repair.  That is much more painful.  I
don't fault file system authors for not implementing deletion to the
same level since it is riskier during development until you get to
that "bug free state".  (Does any software ever truly get there?)

> > Moving entries around breaks ongoing readdir operations.  If a readdir
> > has gone past the file being removed, and you moved the last entry
> > there, the entry being moved would be missed, despite *it* not being the
> > entry added or removed.

I think Kushal is exactly correct.  I had wondered about it but after
the above reasoning I think that completely explains it.  Thank you
Kushal for this rationale.

> I don't think this matters. There's no guarantee that another process
> isn't writing to that directory while you are working your way along
> the entries.

True.  If this is part of a process and becomes a critical section
then the entire process should semaphore access to it.  A typical Unix
way would be to write a daemon to access it and all other processes go
through that daemon which has the same effect of a semaphore simply
because there is now only one process accessing the resource.  This is
effectively the way databases operate.

> This whole discussion touches on one of the facts of life: people
> generally design things for extending, not for contracting. Ability to
> extend a design is an important criterion in its success. In the field
> of computers this is often coupled with backwards compatibility, so you
> can keep the old design going.

Agreed.  I think this comment is very insightful.

Thanks for all of the awesome test cases and data.  Really good stuff!

Bob

Attachment: signature.asc
Description: Digital signature

Reply via email to