LKML Archive on
help / color / mirror / Atom feed
From: "Jörn Engel" <>
To: Bill Davidsen <>
Cc: Juan Piernas Canovas <>,
	Jan Engelhardt <>,
	sfaibish <>,
	kernel list <>
Subject: Re: [ANNOUNCE] DualFS: File System with Meta-data and Data Separation
Date: Sat, 17 Feb 2007 18:36:46 +0000	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

On Sat, 17 February 2007 13:10:23 -0500, Bill Davidsen wrote:
> >  
> I missed that. Which corner case did you find triggers this in DualFS?

This is not specific to DualFS, it applies to any log-structured

Garbage collection always needs at least one spare segment to collect
valid data into.  Regular writes may require additional free segments,
so GC has to kick in and free those when space is getting tight.  (1)

GC frees segments by writing all valid data in it into the spare
segment.  If there is remaining space in the spare segment, GC can move
more data from further segment.  Nice and simple.

The requirement is that GC *always* frees more segments than it uses up
doing so.  If that requirement is not fulfilled, GC will simply use up
its last spare segment without freeing a new one.  We have a deadlock.

Now imagine your filesystem is 90% full and all data is spread perfectly
across all segments.  The best segment you could pick for GC is 90%
full.  One would imagine that GC would only need to copy those 90% into
a spare segment and have freed 100%, making overall progress.

But more log-structured filesystems maintain a tree of some sorts on the
medium.  If you move data elsewhere, you also need to update the
indirect block pointing to it.  So that has to get written as well.  If
you have doubly or triply indirect blocks, those need to get written.
So you can end up writing 180% or more to free 100%.  Deadlock.

And if you read the documentation of the original Sprite LFS or any
other of the newer log-structured filesystems, you usually won't see a
solution to this problem, or even an acknowledgement that the problem
exists in the first place.  But there is no shortage of log-structured
filesystem projects that were abandoned years ago and have "cleaner" or
"garbage collector" as their top item on the todo-list.  Coincidence?

(1) GC may also kick in earlier, but that is just an optimization and
doesn't change the worst case, so that bit is irrelevant here.

Btw, the deadlock problem is solvable and I definitely don't want to
discourage further work in this area.  DualFS does look interesting.
But my solution for this problem will likely eat up all the performance
DualFS has gained and more, as it isn't aimed at hard disks.  So someone
has to come up with a different idea.


To recognize individual spam features you have to try to get into the
mind of the spammer, and frankly I want to spend as little time inside
the minds of spammers as possible.
-- Paul Graham

  reply	other threads:[~2007-02-17 18:40 UTC|newest]

Thread overview: 39+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <>
2007-02-14 21:10 ` sfaibish
2007-02-14 21:57   ` Jan Engelhardt
2007-02-15 18:38     ` Juan Piernas Canovas
2007-02-15 20:09       ` Jörn Engel
2007-02-15 22:59         ` Juan Piernas Canovas
2007-02-16  9:13           ` Jörn Engel
2007-02-16 11:05             ` Benny Amorsen
2007-02-16 23:47             ` Bill Davidsen
2007-02-17 15:11               ` Jörn Engel
2007-02-17 18:10                 ` Bill Davidsen
2007-02-17 18:36                   ` Jörn Engel [this message]
2007-02-17 20:47                     ` Sorin Faibish
2007-02-18  5:59                       ` Jörn Engel
2007-02-18 12:46                         ` Jörn Engel
2007-02-19 23:57                         ` Juan Piernas Canovas
2007-02-20  0:10                           ` Bron Gondwana
2007-02-20  0:30                           ` Jörn Engel
2007-02-21  4:36                             ` Juan Piernas Canovas
2007-02-21 12:37                               ` Jörn Engel
2007-02-21 18:31                                 ` Juan Piernas Canovas
2007-02-21 19:25                                   ` Jörn Engel
2007-02-22  4:30                                     ` Juan Piernas Canovas
2007-02-22 16:25                                       ` Jörn Engel
2007-02-22 19:57                                         ` Juan Piernas Canovas
2007-02-23 13:26                                           ` Jörn Engel
2007-02-24 22:35                                             ` Sorin Faibish
2007-02-25  2:41                                             ` Juan Piernas Canovas
2007-02-25 12:01                                               ` Jörn Engel
2007-02-26  3:48                                                 ` Juan Piernas Canovas
2007-02-20 20:43                           ` Bill Davidsen
2007-02-15 20:38       ` Andi Kleen
2007-02-15 19:46         ` Jan Engelhardt
2007-02-16  1:43           ` sfaibish
2007-02-15 21:09         ` Juan Piernas Canovas
2007-02-15 23:57           ` Andi Kleen
2007-02-16  4:57             ` Juan Piernas Canovas
2007-02-26 11:49   ` Yakov Lerner
2007-02-26 13:08     ` Matthias Schniedermeyer
2007-02-26 13:24     ` Sorin Faibish

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \ \ \
    --subject='Re: [ANNOUNCE] DualFS: File System with Meta-data and Data Separation' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).