Re: Documenting the crash consistency guarantees of file systems

Re: Documenting the crash consistency guarantees of file systems

[Amir Goldstein]

[CC: linux-fsdevel,linux-doc]

On Sat, Feb 9, 2019 at 12:47 AM Jayashree Mohan <jayashree2912@gmail.com> wrote:
>
> Hi all,
>
> We all understand that providing strong crash consistency guarantees
> while not impacting performance, can be tricky. While you strive to
> achieve that, it is worth documenting the expected/current guarantees
> provided by each file system so that users can report buggy behaviors
> and stop pursuing potential dead ends.
>
> In the course of developing our crash-consistency testing tool:
> CrashMonkey, we've had several interesting discussions with
> file-system developers regarding the guarantees provided by
> file-system operations. For example, the crash-consistency guarantees
> of symlink does not ensure that the symlink-ed file survives a crash,
> even if it was persisted explicitly before the crash. This is because,
> unlike hard links, symlinks are not regular files and it is not
> possible to directly open them to fsync() [1].
>
> Similarly, most file systems today provide guarantees more
> than what the POSIX expects; however, these are not formally
> documented. For example, in btrfs, fsync() of any file should be
> enough to persist that file in its current directory; it does
> not require that its parent directory be explicitly persisted [2].
> f2fs on the other hand, offers multiple fsync() modes like
> FSYNC_MODE_STRICT, FSYNC_MODE_POSIX etc, each with different
> guarantees. As a user, we are unaware of these differences in
> guarantees each file system has to offer.
>
> More recently, there was a bug report which stated that chmod'ed
> permissions on special files were not persisted upon fsync() [3].
> While Ted explained that special files don't have a fsync() function
> defined, thereby making it a no-op, we believe such information is
> crucial and worth documenting.
>
> In this context, how about adding a new file to the Linux kernel
> documentation, for example,
> linux/Documentation/filesystems/crash-consistency-guarantees.txt,
> where developers or users could contribute their knowledge on such
> special cases where persistence guarantees are not applicable, or the
> extent of crash-guarantees each file system provides? If this sounds
> good, we will be happy to send out a patch detailing the information
> we gathered about each file-system's guarantees while testing them
> with CrashMonkey. This would serve as a one-stop destination for all
> information related to crash-consistency guarantees and encourage any
> future conversations pertaining to crash consistency to be documented
> here.
>
> [1] https://www.spinics.net/lists/linux-btrfs/msg76835.html
> [2] https://www.spinics.net/lists/linux-btrfs/msg77340.html
> [3] https://bugzilla.kernel.org/show_bug.cgi?id=202485
>
>

Hi Jayashree,

I think we would be fools to decline an offer for better documentation ;)
Your project has certainly collected some valuable inputs.
The most valuable outcome IMO, besides finding bugs obviously,
is the xfstests that you submitted and working on - ain't nothing like
documentation that checks the code...

But when approaching a task of documenting existing behavior
there are some challenges:
- Behavior may change and documentation may become stale
- Filesystem maintainers may not be happy about committing
  to specific behavior by documenting it

If I were you, I would start with documenting:
1. Existing user space APIs for making changes durable and what
    they guaranty in POSIX vs. Linux (e.g. fsync of symlink)
2. "strictly ordered metadata" - according to Google, Dave Chinner
    was the first to coin this term and claim that ext4, xfs, btrfs all
    abide to those semantics. I think it would be great to have a
    document that describes those semantics, so that we can refer
    people to the doc when trying to explain some crash behavior
    or performance issue that is a by product of these semantics.
3. More tricky would be to find and document behavior that is set in
    stone by applications that grew to expect it despite no guaranty.
    A concrete example is the order guaranties between data and
    metadata operations [1]. I honestly don't know if and what could
    be documented in that regard.

Thanks,
Amir.

[1] https://thunk.org/tytso/blog/2009/03/12/delayed-allocation-and-the-zero-length-file-problem/

Re: Documenting the crash consistency guarantees of file systems

[Jayashree Mohan]

Hi Amir!

Thanks for putting across your thoughts on this. Your suggestions
definitely make sense, and we'll compile these information and submit
a patch for review.

When it comes to strictly ordered metadata consistency, to the best of
our knowledge only xfs claims to provide it explicitly. In ext4,
delayed allocation and fsync of a file not persisting all its hard
links[1] are examples of violation to the strictly ordered metadata
consistency right? And for btrfs, they don't seem to explicit about
providing such semantics. Look at this thread[2] for example, owing to
the lack of specification, btrfs does not commit to providing such
guarantees.

Thanks,
Jayashree

[1] https://www.spinics.net/lists/linux-btrfs/msg77340.html
[2] https://www.spinics.net/lists/linux-btrfs/msg76957.html

Re: Documenting the crash consistency guarantees of file systems

[Amir Goldstein]

On Wed, Feb 13, 2019 at 7:06 PM Jayashree Mohan <jaya@cs.utexas.edu> wrote:
>
> Hi Amir!
>
> Thanks for putting across your thoughts on this. Your suggestions
> definitely make sense, and we'll compile these information and submit
> a patch for review.
>
> When it comes to strictly ordered metadata consistency, to the best of
> our knowledge only xfs claims to provide it explicitly. In ext4,
> delayed allocation and fsync of a file not persisting all its hard
> links[1] are examples of violation to the strictly ordered metadata
> consistency right?

No, I don't think they are.
At least that is not how understand what Ted wrote.

> And for btrfs, they don't seem to explicit about
> providing such semantics. Look at this thread[2] for example, owing to
> the lack of specification, btrfs does not commit to providing such
> guarantees.

The discussion is not about ordered metadata, is it about what
fsync(file) should do. They are related if we decide that fsync(file)
should persist nlink, but I think all fs maintainers are in agreement
that it doesn't matter and btrfs choice is as valid as ext4/xfs choice.

That said, I don't know if btrfs does strictly ordered metadata or not.
Order metadata means if user does op A then op B, you should not be
able to see consequence of op B after crash without seeing the
consequence of op A.

Can you give a counter example for btrfs? for ext4?

The different fsync() guaranties in different filesystems confuse you
because if you expect fsync() to persist op B, then you expect op A
to persist as well, but it may be the former (fsync) expectation that is
failing and not the latter (ordered).

Thanks,
Amir.

>
> [1] https://www.spinics.net/lists/linux-btrfs/msg77340.html
> [2] https://www.spinics.net/lists/linux-btrfs/msg76957.html

Re: Documenting the crash consistency guarantees of file systems

[Vijay Chidambaram]

On Wed, Feb 13, 2019 at 12:22 PM Amir Goldstein <amir73il@gmail.com> wrote:
>
> On Wed, Feb 13, 2019 at 7:06 PM Jayashree Mohan <jaya@cs.utexas.edu> wrote:
> >
> > Hi Amir!
> >
> > Thanks for putting across your thoughts on this. Your suggestions
> > definitely make sense, and we'll compile these information and submit
> > a patch for review.
> >
> > When it comes to strictly ordered metadata consistency, to the best of
> > our knowledge only xfs claims to provide it explicitly. In ext4,
> > delayed allocation and fsync of a file not persisting all its hard
> > links[1] are examples of violation to the strictly ordered metadata
> > consistency right?
>
> No, I don't think they are.
> At least that is not how understand what Ted wrote.
>
> > And for btrfs, they don't seem to explicit about
> > providing such semantics. Look at this thread[2] for example, owing to
> > the lack of specification, btrfs does not commit to providing such
> > guarantees.
>
> The discussion is not about ordered metadata, is it about what
> fsync(file) should do. They are related if we decide that fsync(file)
> should persist nlink, but I think all fs maintainers are in agreement
> that it doesn't matter and btrfs choice is as valid as ext4/xfs choice.
>
> That said, I don't know if btrfs does strictly ordered metadata or not.
> Order metadata means if user does op A then op B, you should not be
> able to see consequence of op B after crash without seeing the
> consequence of op A.
>
> Can you give a counter example for btrfs? for ext4?

My understanding of strictly ordered metadata is that if op A precedes
op B in program order (in-memory execution), then op A should precede
op B in persistence order. As you say, one should not observe op B on
storage without op A. Note that we don't say anything about whether
fsync was called on op A or op B.

I remember this old conversation from our ALICE work that btrfs does
not persist things in order:
https://www.spinics.net/lists/linux-btrfs/msg32215.html

If you do the following:

create file foo
write to file foo
rename bar to baz
CRASH

and then you see baz but not foo on storage, that is a violation of
strictly ordered semantics. ext4 violates this due to delayed
allocation. So it does not provide strictly ordered metadata?

AFAIK, any file system which persists things out of order to increase
performance does not provide strictly ordered metadata semantics.
These semantics seem to indicate a total ordering among all
operations, and an fsync should persist all previous operations (as
ext3 used to do).

Note that Jayashree and I aren't arguing file systems should provide
this semantics, merely that ext4 and btrfs violate it at certain
points.

Re: Documenting the crash consistency guarantees of file systems

[Amir Goldstein]

On Wed, Feb 13, 2019 at 8:35 PM Vijay Chidambaram <vijay@cs.utexas.edu> wrote:
>
> On Wed, Feb 13, 2019 at 12:22 PM Amir Goldstein <amir73il@gmail.com> wrote:
> >
> > On Wed, Feb 13, 2019 at 7:06 PM Jayashree Mohan <jaya@cs.utexas.edu> wrote:
> > >
> > > Hi Amir!
> > >
> > > Thanks for putting across your thoughts on this. Your suggestions
> > > definitely make sense, and we'll compile these information and submit
> > > a patch for review.
> > >
> > > When it comes to strictly ordered metadata consistency, to the best of
> > > our knowledge only xfs claims to provide it explicitly. In ext4,
> > > delayed allocation and fsync of a file not persisting all its hard
> > > links[1] are examples of violation to the strictly ordered metadata
> > > consistency right?
> >
> > No, I don't think they are.
> > At least that is not how understand what Ted wrote.
> >
> > > And for btrfs, they don't seem to explicit about
> > > providing such semantics. Look at this thread[2] for example, owing to
> > > the lack of specification, btrfs does not commit to providing such
> > > guarantees.
> >
> > The discussion is not about ordered metadata, is it about what
> > fsync(file) should do. They are related if we decide that fsync(file)
> > should persist nlink, but I think all fs maintainers are in agreement
> > that it doesn't matter and btrfs choice is as valid as ext4/xfs choice.
> >
> > That said, I don't know if btrfs does strictly ordered metadata or not.
> > Order metadata means if user does op A then op B, you should not be
> > able to see consequence of op B after crash without seeing the
> > consequence of op A.
> >
> > Can you give a counter example for btrfs? for ext4?
>
> My understanding of strictly ordered metadata is that if op A precedes
> op B in program order (in-memory execution), then op A should precede
> op B in persistence order. As you say, one should not observe op B on
> storage without op A. Note that we don't say anything about whether
> fsync was called on op A or op B.
>
> I remember this old conversation from our ALICE work that btrfs does
> not persist things in order:
> https://www.spinics.net/lists/linux-btrfs/msg32215.html
>

Yap that seems to break strict ordering.

> If you do the following:
>
> create file foo
> write to file foo
> rename bar to baz
> CRASH
>
> and then you see baz but not foo on storage, that is a violation of
> strictly ordered semantics. ext4 violates this due to delayed
> allocation. So it does not provide strictly ordered metadata?
>

You are saying that you do not see foo dir entry on storage
or that you do not see foo data on storage. Two completely different
things. metadata ordering is not about data and delayed allocation
is mostly about data.

There are metadata changes that are implied by data changes
(mtime,ctime,size), but those are also deferred along with delayed
allocation.

So we need to rephrase/clarify.
I intentionally use the language "op A" and "op B" and I meant
that the rule only apply to "metadata ops" - now this is a term that
may be hard to define. Different filesystems may have different
views on what qualifies as a "metadata op".
No one will probably argue that rename() is not a metadata op,
but truncate/punch/clone, there may be some wiggle room for
interpretation (and that statement is likely to draw flames).

> AFAIK, any file system which persists things out of order to increase
> performance does not provide strictly ordered metadata semantics.
> These semantics seem to indicate a total ordering among all
> operations, and an fsync should persist all previous operations (as
> ext3 used to do).
>

fsync in xfs does not persist all previous operations.
It knows which is the last transaction where target inode was changed
and it only needs to flush transactions up this this one.

Thanks,
Amir.

Re: Documenting the crash consistency guarantees of file systems

[Dave Chinner]

On Wed, Feb 13, 2019 at 12:35:16PM -0600, Vijay Chidambaram wrote:
> On Wed, Feb 13, 2019 at 12:22 PM Amir Goldstein <amir73il@gmail.com> wrote:
> > On Wed, Feb 13, 2019 at 7:06 PM Jayashree Mohan <jaya@cs.utexas.edu> wrote:
> AFAIK, any file system which persists things out of order to increase
> performance does not provide strictly ordered metadata semantics.

Define "things", please.

And while you are there, define "persist", please.

XFS can "persist" "things" out of order because it has a multi-phase
checkpointing subsystem and we can't control IO ordering during
concurrent checkpoint writeout. The out of order checkpoints don't
get put back in order until recovery is run - it reorders everything
that is in the journal into correct sequence order before it starts
recovery.

IOWs, the assertion that we must "persist" things in strict order to
maintain ordered metadata semantics is incorrect. /Replay/ of the
changes being recovered must be done in order, but that does not
require them to be persisted to stable storage in strict order.

> These semantics seem to indicate a total ordering among all
> operations, and an fsync should persist all previous operations (as
> ext3 used to do).

No, absolutely not.

You're talking about /globally ordered metadata/. This was the
Achille's Heel of ext3, resulting in fsync being indistinguishable
from sync and hence being horrifically slow. This caused a
generation of linux application developers to avoid using fsync and
causing users (and fs developers who got blamed for losing data)
endless amounts of pain when files went missing after crashes.
Hindsight teaches us that ext3's behaviour was a horrible mistake
and not one we want to repeat.

Strictly ordered metadata only requires persisting all the previous
dependent modifications to the objects we need to persist.
i.e. if you fsync an inode we just allocated, then we also have to
persist the changes in the same transaction and then all the
previous changes that are dependent on that set of objects, and so
one all the way back to objects being clean on disk. If we crash,
we can then rebuild all of the information the user persisted
correctly.

There is no requirement for any other newly created inode elsewhere
in the filesystem to be present after fsync of the first file.
Indepdnent file creation will only be persisted by the fsync if
there is a shared object modification dependency between those two
files elsewhere in metadata. e.g. they are both in the same inode
cluster so share an inode btree block modification that marks them
as used, hence if one it persisted, the btree block is persisted,
and hence the other inode and all it's dependencies need to be
persisted as well.

That dependency tree is the "strict ordering" we talk about. At
times it can look like "globally ordered metadata", but for
indepedent changes it will only result in the small number of
dependencies being persisted and not the entire filesystem (as per
ext3).

> Note that Jayashree and I aren't arguing file systems should provide
> this semantics, merely that ext4 and btrfs violate it at certain
> points.

As does XFS.

http://xfs.org/index.php/XFS_FAQ#Q:_Why_do_I_see_binary_NULLS_in_some_files_after_recovery_when_I_unplugged_the_power.3F

ext4 inherited all it's delalloc vs metadata ordering issues from
XFS as ext4 really just copied the XFS design without understanding
all the problems it had. Then when users started reporting problems
the problems we'd fixed with XFS they copied a number of the
mitigations from XFS as well....


-- 
Dave Chinner
david@fromorbit.com

Re: Documenting the crash consistency guarantees of file systems

[Vijay Chidambaram]

On Wed, Feb 13, 2019 at 7:47 PM Dave Chinner <david@fromorbit.com> wrote:
>
> On Wed, Feb 13, 2019 at 12:35:16PM -0600, Vijay Chidambaram wrote:
> > On Wed, Feb 13, 2019 at 12:22 PM Amir Goldstein <amir73il@gmail.com> wrote:
> > > On Wed, Feb 13, 2019 at 7:06 PM Jayashree Mohan <jaya@cs.utexas.edu> wrote:
> > AFAIK, any file system which persists things out of order to increase
> > performance does not provide strictly ordered metadata semantics.
>
> Define "things", please.
>
> And while you are there, define "persist", please.
>
> XFS can "persist" "things" out of order because it has a multi-phase
> checkpointing subsystem and we can't control IO ordering during
> concurrent checkpoint writeout. The out of order checkpoints don't
> get put back in order until recovery is run - it reorders everything
> that is in the journal into correct sequence order before it starts
> recovery.
>
> IOWs, the assertion that we must "persist" things in strict order to
> maintain ordered metadata semantics is incorrect. /Replay/ of the
> changes being recovered must be done in order, but that does not
> require them to be persisted to stable storage in strict order.

Yes, I wasn't precise about this. I agree the behavior depends on what
the user can observe after recovery, not the order in which it is
persisted.

>
> > These semantics seem to indicate a total ordering among all
> > operations, and an fsync should persist all previous operations (as
> > ext3 used to do).
>
> No, absolutely not.
>
> You're talking about /globally ordered metadata/. This was the
> Achille's Heel of ext3, resulting in fsync being indistinguishable
> from sync and hence being horrifically slow. This caused a
> generation of linux application developers to avoid using fsync and
> causing users (and fs developers who got blamed for losing data)
> endless amounts of pain when files went missing after crashes.
> Hindsight teaches us that ext3's behaviour was a horrible mistake
> and not one we want to repeat.
>
> Strictly ordered metadata only requires persisting all the previous
> dependent modifications to the objects we need to persist.
> i.e. if you fsync an inode we just allocated, then we also have to
> persist the changes in the same transaction and then all the
> previous changes that are dependent on that set of objects, and so
> one all the way back to objects being clean on disk. If we crash,
> we can then rebuild all of the information the user persisted
> correctly.
>
> There is no requirement for any other newly created inode elsewhere
> in the filesystem to be present after fsync of the first file.
> Indepdnent file creation will only be persisted by the fsync if
> there is a shared object modification dependency between those two
> files elsewhere in metadata. e.g. they are both in the same inode
> cluster so share an inode btree block modification that marks them
> as used, hence if one it persisted, the btree block is persisted,
> and hence the other inode and all it's dependencies need to be
> persisted as well.
>
> That dependency tree is the "strict ordering" we talk about. At
> times it can look like "globally ordered metadata", but for
> indepedent changes it will only result in the small number of
> dependencies being persisted and not the entire filesystem (as per
> ext3).

Thanks, I understand "strictly ordered metadata operations" much
better now. So we can define it this way:

If op1 precedes op2 in program order (in-memory execution order), and
op1 and op2 share a dependency, then op2 must not be observed by a
user after recovery without op1.

The unsatisfying part about this definition is that "share a
dependency" is vague, and seems to depend on the internal file-system
implementation. I would like it if it was defined in terms of things a
user can observe: op1 and op2 are on the same file, or files in the
same directory, etc.

With this definition of "strictly ordered metadata operations" (SOMO),
does ext4, XFS, and btrfs achieve it? I don't think btrfs does, but
I'm not sure about XFS and ext4. I don't think delayed allocation
violates SOMO per se.

> > Note that Jayashree and I aren't arguing file systems should provide
> > this semantics, merely that ext4 and btrfs violate it at certain
> > points.
>
> As does XFS.
>
> http://xfs.org/index.php/XFS_FAQ#Q:_Why_do_I_see_binary_NULLS_in_some_files_after_recovery_when_I_unplugged_the_power.3F
>
> ext4 inherited all it's delalloc vs metadata ordering issues from
> XFS as ext4 really just copied the XFS design without understanding
> all the problems it had. Then when users started reporting problems
> the problems we'd fixed with XFS they copied a number of the
> mitigations from XFS as well....

I'm aware of the history here. It was interesting to see ext4 run into
the same issues XFS ran into earlier, and then implement the same
work-arounds.