Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[Theodore Y. Ts'o]

On Thu, Oct 24, 2019 at 06:54:44AM +0000, Xiaohui1 Li 李晓辉 wrote:
> 
> But i also have an idea which can simplify the fast commit patch.
> because we want to fix fsync cost too much time problems on our
> mobile phone without format the whole ext4 partition , and i found
> current fast commit patch can't do this job as it need to
> readjustment the layout of journal area and will destroy phone
> user's data from my opinion .

That's not correct.  The fast commit feature can be added to an
existing ext4 file system.  That's because when the ext4 file system
is mounted (or when e2fsck is run) the contents of the file system
journal (if any) are replayed and then discard.  On a clean shutdown,
the journal is empty to begin with.

Hence, restructuring the journal so that a portion of the space can be
used for fast commits can be done without modifying or otherwise
destroying the data on the pre-existing file system.

> so my simplify idea is that:
> when jbd2 thread begin to commit the current transaction , why not
> divide the commiting work into two sub work ? firstly flush metadata
> generated by fsynced handles to disk, and then append a commit end
> block. and then tell the fsync threads that no need to wait, as
> their metadata has already been flush to disk journal area, the
> fsync work is finished.  and then the second sub work is to
> committing metadata and data generated by left handles in current
> transaction.

The problem, as I stated in my earlier message, is that the handles
that were not involved in the fsync in many cases will have been
started and completed before the changes reflected by the handles
involving the inode to be fsync'ed.  We can't just "separate out the
handles" and commit the ones that are necessary, and then do the rest
in a separate transaction.  The problem is entagled dependencies.  For
example, one of the handles not involved with the fsync may have
modified the inode table or the allocation bitmap that is involved
with the update to the inode to be fsync'ed.  We can't just flush the
metadata blocks involved with the "fsync handles", since they will
include the modifications made by other file systems via "the rest of
the handles."

So no, we can't do what you are suggesting.  If it were that easy, we
would have done it a long time ago.

The reason why you can't separate out some of the handles from others
is referenced in the LWN article, "Soft Updates, Hard Problems"[1].
What you are suggesting is not exactly soft updates, but it suffers
from the same problem, namely that of entangled updates, where the
same block is modified by multiple handles.  If you track all of the
logical dependencies, you could potentially "roll back" in memory
those changes which are not yet committed, and then after commit of
the "fsync hanldes", roll them forward again.  But this is hopelessly
complicated to get right.

[1] https://lwn.net/Articles/339337/

So if you implemented your suggestion, and the system were to crash
between the first and second commit, the file system would be
corrupted, and in the worst case, e2fsck might not be able to recover
the file system, and all of the user's data would be lost.  Of course,
if you are sure that your system will never crash, because the kernel
is bug-free(tm), then you could skip using the journalling altogher.....

						- Ted

P.S.  It's actually a little bit more complicated than that; you also
need to worry about power drops, so the battery needs to be embedded,
so there is no chance the battery will come flying out when the phone
is dropped.  The EC also has to be able to give a low-pattery warning
so that the system can be shut down cleanly before the battery power
goes to zero, and you can't allow the emergency poweroff where the
user pushes and holds the power buton for eight seconds.  The last,
after all, won't be needed because we are making the hopelessly
unrealistic assumption that the kernel is completely, 100%,
bug-free(tm).   :-)

Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[Theodore Y. Ts'o]

On Tue, Oct 29, 2019 at 11:43:54AM +0000, Xiaohui1 Li 李晓辉 wrote:
> > We don't actually have to do this.  Strictly speaking, we only have to
> > write out the specific inode being fsync'ed, or the specific inode for
> > which ext4_nfs_commit_metdata() has been called.  For an fsync()
> > workload, especially one where for example, we might have hundreds of
> > modified inodes, all of which are fc-eligible --- for example, because
> > a kernel build is happening in the background, and a single file which
> > is being fsync'ed --- for example because the programmer has just
> > saved a source file in emacs ---- we only need to include that single
> > inode in the fast commit.  Including *all* of the inodes in the
> > i_fc_list in the fast commit, is wasted effort, especially since the
> > inodes in question will be committed within the next 5 seconds.
> 
> you said only need to include that single inode in the fast commit.
> do you mean that create a fast-commit transaction which only need to
> commit data and metadata of the specific inode ?  but in your last
> email, you says "we can't just separate out some of the handles from
> others in one transation".
> 
> so if we just only include that single inode(ie: being fsync'ed) in
> the fast commit, is it means that in the ext4 traditional way，
> metadata of this single inode being fsync'ed need to be mixed with
> other inodes not being fsync'ed (may doing buffer write) together in
> one transaction to be flushed to disk both together because of
> entagled dependencies you says in your last reply email.
> 
> but when fast-commit patches applied, how the metadata and data of
> this single inode being fsync'ed can be extracted from all files
> metadata changes during one time range ？

Did you read the iJournaling Usenix paper[1] which I referenced
earlier?  It's described in there.

[1] https://www.usenix.org/conference/atc17/technical-sessions/presentation/park

The trick is that we track whether the inode has changes which we
can't represent in the fast commit "logical journal".  In the logical
journal, we record changes since the last full commit, not as the full
physical metadata block, but just bits of the logical metadata that
have changed.  If that inode has changed in ways that we can't
represent in the fast commit journal, then we do a normal full commit.

So we avoid entangled dependencies in two ways .  First of all, we
only journal the logical change.  Hence, if there is a change in
another part of the metadata block (say, another inode in the inode
table) there won't be an issue, since we only update that one inode.
Secondly, if the inode has some entangelements either with other
inodes, or (b) changes in the inode which we can't reflect in the fast
commit log, then fall back to doing a full commit.

So basically, we only deal with the simple, common cases, where it's
easy to log changes to the fast commit log.  Now, those changes are
also logged in the normal physical commit, so once we do a full
commit, all of the entries in the fast commit log are no longer needed
--- the fast commit just contains the small, simple changes since the
last full commit.

Cheers,

						- Ted

答复: [External Mail]Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[Xiaohui1 Li 李晓辉]

thanks to this  iJournaling Usenix paper,

fsync latency-too-long problem because of entangled dependencies and inode' data has to be waited in jbd2 order mode
can be fixed.

entangled dependencies problem is known to us by your kind reply email.
the  problem of file' data wating in jbd2 order mode is also a serious problem which case a long-latency fsync call.

as pointed out in this iJournaling paper, when three conditions turn up at the same time,
1: order mode must be applied, not the writeback mode.
2: The delayed block allocation technique of ext4 must be  applied.
3: backgroud buffer writes are too many.

because the periodic flush disk time caused by delayed block allocation is 30s(a bit too long) in android system,
so when begin to flush data and metadata to disk, the amount of inode data flushed can be so large.
and so because of the default ext4 data mode is order(not the writeback mode), so when fsync is called,
we have to be faced with such a difficult condition which is that have to be waited for so many inode data(not the metadata) flushed to
disk completely in jbd2 thread.

we have no choice as the order mode need to do this work, so the waiting inode-data-flushed-disk time is too long in some extreme conditions.
so it cause the appearance of long-latency fsync call.

thank you for your reply, i will try to fix this problem in my free time.


append some words in ijournal paper which may be help for someone(may be include me) which don't be familiar with why delayed block allocation
will cause long-latency fsync call :

The delayed block allocation technique of ext4 ag-
gravates the CTX problem(appeared in fsync call).

However, if an fsync is called just after
the flush kernel thread invocation, as shown in the ex-
ample in Figure 1(a), the flush thread will allocate data
blocks for dirty pages, and register several modified in-
odes in the running transaction during the delayed block
allocation. Then, the commit operation of the journal
transaction will generate many write requests into stor-
age.

 Shall someone can tell the reason why delayed block allocation technique of ext4 cause  long-latency fsync call with more detail ?
many thanks.

________________________________________
发件人: Theodore Y. Ts'o <tytso@mit.edu>
发送时间: 2019年10月30日 5:35
收件人: Xiaohui1 Li 李晓辉
抄送: linux-ext4@vger.kernel.org; harshadshirwadkar@gmail.com
主题: [External Mail]Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

On Tue, Oct 29, 2019 at 11:43:54AM +0000, Xiaohui1 Li 李晓辉 wrote:
> > We don't actually have to do this.  Strictly speaking, we only have to
> > write out the specific inode being fsync'ed, or the specific inode for
> > which ext4_nfs_commit_metdata() has been called.  For an fsync()
> > workload, especially one where for example, we might have hundreds of
> > modified inodes, all of which are fc-eligible --- for example, because
> > a kernel build is happening in the background, and a single file which
> > is being fsync'ed --- for example because the programmer has just
> > saved a source file in emacs ---- we only need to include that single
> > inode in the fast commit.  Including *all* of the inodes in the
> > i_fc_list in the fast commit, is wasted effort, especially since the
> > inodes in question will be committed within the next 5 seconds.
>
> you said only need to include that single inode in the fast commit.
> do you mean that create a fast-commit transaction which only need to
> commit data and metadata of the specific inode ?  but in your last
> email, you says "we can't just separate out some of the handles from
> others in one transation".
>
> so if we just only include that single inode(ie: being fsync'ed) in
> the fast commit, is it means that in the ext4 traditional way，
> metadata of this single inode being fsync'ed need to be mixed with
> other inodes not being fsync'ed (may doing buffer write) together in
> one transaction to be flushed to disk both together because of
> entagled dependencies you says in your last reply email.
>
> but when fast-commit patches applied, how the metadata and data of
> this single inode being fsync'ed can be extracted from all files
> metadata changes during one time range ？

Did you read the iJournaling Usenix paper[1] which I referenced
earlier?  It's described in there.

[1] https://www.usenix.org/conference/atc17/technical-sessions/presentation/park

The trick is that we track whether the inode has changes which we
can't represent in the fast commit "logical journal".  In the logical
journal, we record changes since the last full commit, not as the full
physical metadata block, but just bits of the logical metadata that
have changed.  If that inode has changed in ways that we can't
represent in the fast commit journal, then we do a normal full commit.

So we avoid entangled dependencies in two ways .  First of all, we
only journal the logical change.  Hence, if there is a change in
another part of the metadata block (say, another inode in the inode
table) there won't be an issue, since we only update that one inode.
Secondly, if the inode has some entangelements either with other
inodes, or (b) changes in the inode which we can't reflect in the fast
commit log, then fall back to doing a full commit.

So basically, we only deal with the simple, common cases, where it's
easy to log changes to the fast commit log.  Now, those changes are
also logged in the normal physical commit, so once we do a full
commit, all of the entries in the fast commit log are no longer needed
--- the fast commit just contains the small, simple changes since the
last full commit.

Cheers,

                                                - Ted
#/******本邮件及其附件含有小米公司的保密信息，仅限于发送给上面地址中列出的个人或群组。禁止任何其他人以任何形式使用（包括但不限于全部或部分地泄露、复制、或散发）本邮件中的信息。如果您错收了本邮件，请您立即电话或邮件通知发件人并删除本邮件！ This e-mail and its attachments contain confidential information from XIAOMI, which is intended only for the person or entity whose address is listed above. Any use of the information contained herein in any way (including, but not limited to, total or partial disclosure, reproduction, or dissemination) by persons other than the intended recipient(s) is prohibited. If you receive this e-mail in error, please notify the sender by phone or email immediately and delete it!******/#

Re: 答复: [External Mail]Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[Theodore Y. Ts'o]

On Wed, Oct 30, 2019 at 04:28:42AM +0000, Xiaohui1 Li 李晓辉 wrote:
> the problem of file' data wating in jbd2 order mode is also a
> serious problem which case a long-latency fsync call.

Yes, this is a separate problem, although note that if the file with a
large amount of data is the file which is being fsync'ed, you have to
write it out at fsync time no matter what.

You could try to write out dirty data earlier (e.g., by decreasing the
30 second writeback window), but there are tradeoffs.  For one thing,
if the file ends up being deleted anyway, it's better not to write out
the data at all.  For another, if we know how big the file is at the
time when we do the writeout, we can do a better job allocating space
for the file, and it improves the file layout by making it more likely
it will be contiguous, or at least mostly contiguous.

Also, files that tend to be fsync'ed a lot tend to be database files
(e.g., SQLite files), and they tend to write small amounts of data and
then fsync them.  So the problem described below happens when there
are unrelated files that happen to be downloaded in parallel.  An
example of this in the Android case mgiht be when the user is
downloading a large video file, such as a movie, to be watched offline
later (such as when they are on a plane).

> as pointed out in this iJournaling paper, when three conditions turn up at the same time,
> 1: order mode must be applied, not the writeback mode.
> 2: The delayed block allocation technique of ext4 must be  applied.
> 3: backgroud buffer writes are too many.

(1) and (2) are the default.  (3) may or may not be a frequent
occurrence, depending on the workload.  In practice though, users
aren't downloading large files all *that* often.

> we have no choice as the order mode need to do this work, so the
> waiting inode-data-flushed-disk time is too long in some extreme
> conditions.  so it cause the appearance of long-latency fsync call.
> 
> thank you for your reply, i will try to fix this problem in my free time.

So there is a solution; it's just a bit tricky to do, and it's not
been a huge enough deal that anyone has allocated time to fix it.

The idea is to allocate space, but not actually update the metadata
blocks at the time when the data blocks are allocated.  Instead, we
reserve them so they won't get allocated for use by another file, and
we note where they are in the extent status cache.  We then issue the
writes of the data block, and only after they are complete, only
*then* do we update the metadata blocks (which then gets updated via
the journal, using either a commit or a fast commit).

This is similar to the dioread_nolock case, where we update the
metadata blocks first, but mark them as unwritten, then we let the
data blocks get written, and only finally do we update the metadata
blocks so they are marked as written (e.g., initialized).  This avoids
the stale data problem as well, but we end up modifying the metadata
blocks twice, and it has resulted other performance problems since in
increases overhead on the i_data_sem lock.  See for example some of
the posts by Liu Bo from Alibaba last year:

If we can allocate space, write the data blocks, and only *then*
update the extent tree metadata blocks, it solves a lot of problems.
We can get rid of the dioread_nolock option; we can get rid of the
data=ordered vs data=writeback distinction; and we can avoid the need
to force data blocks to be written out at commit time.  So it improves
performance, and it will reduce code complexity, making it a win-win
approach.

The problem is that this means significantly changing how we do block
allocation and block reservation, so it's a fairly large and invasive
set of changes.  But it's the right long-term direction, and we'll get
there eventually.

Cheers,

						- Ted

Re: 答复: [External Mail]Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[xiaohui li]

another way which i think can fix this fsync time cost problem may be
that changing ext4 data mode from order to writeback.

when in writeback mode, inode' data has not to be waited in jbd2
thread, so the fsync time cost is also reduced.
meawhile, writeback mode also can guarantee filesystem consistency in
os crash-reboot conditions,
with only one drawback is that it will cause security problems such as
stale data will be seen.

but in android system with file encryption enabled, there is no
security problem as files are all encryped.
but user will see wrong file data in system crash-reboot conditions
with writeback mode enabled.

for example:
-------------
file A has allocate 50 new blocks, and already dirtys page cache
corresponding to these 50 blocks,
and after the medata represent new 50 blocks of this file have been
flushed to journal area, the system crash.
file A's data according to above 50 new blocks has not been to flushed to disk.
after system reboot and finish file system recovery work, file A's
size has bee enlarged with new 50 blocks added.
but data in this file's new 50 blocks is not correct. so it will cheat
user if it is difficult to see this data-not-correct problem.
-------------

and this problem can't fixed by e2fsck full check ,it is not belong to
file system consistency,
so we will insist on using order mode ,not writeback mode.

i will also share my view about that ijournal paper in my next time.

On Wed, Oct 30, 2019 at 10:26 PM Theodore Y. Ts'o <tytso@mit.edu> wrote:
>
> On Wed, Oct 30, 2019 at 04:28:42AM +0000, Xiaohui1 Li 李晓辉 wrote:
> > the problem of file' data wating in jbd2 order mode is also a
> > serious problem which case a long-latency fsync call.
>
> Yes, this is a separate problem, although note that if the file with a
> large amount of data is the file which is being fsync'ed, you have to
> write it out at fsync time no matter what.
>
> You could try to write out dirty data earlier (e.g., by decreasing the
> 30 second writeback window), but there are tradeoffs.  For one thing,
> if the file ends up being deleted anyway, it's better not to write out
> the data at all.  For another, if we know how big the file is at the
> time when we do the writeout, we can do a better job allocating space
> for the file, and it improves the file layout by making it more likely
> it will be contiguous, or at least mostly contiguous.
>
> Also, files that tend to be fsync'ed a lot tend to be database files
> (e.g., SQLite files), and they tend to write small amounts of data and
> then fsync them.  So the problem described below happens when there
> are unrelated files that happen to be downloaded in parallel.  An
> example of this in the Android case mgiht be when the user is
> downloading a large video file, such as a movie, to be watched offline
> later (such as when they are on a plane).
>
> > as pointed out in this iJournaling paper, when three conditions turn up at the same time,
> > 1: order mode must be applied, not the writeback mode.
> > 2: The delayed block allocation technique of ext4 must be  applied.
> > 3: backgroud buffer writes are too many.
>
> (1) and (2) are the default.  (3) may or may not be a frequent
> occurrence, depending on the workload.  In practice though, users
> aren't downloading large files all *that* often.
>
> > we have no choice as the order mode need to do this work, so the
> > waiting inode-data-flushed-disk time is too long in some extreme
> > conditions.  so it cause the appearance of long-latency fsync call.
> >
> > thank you for your reply, i will try to fix this problem in my free time.
>
> So there is a solution; it's just a bit tricky to do, and it's not
> been a huge enough deal that anyone has allocated time to fix it.
>
> The idea is to allocate space, but not actually update the metadata
> blocks at the time when the data blocks are allocated.  Instead, we
> reserve them so they won't get allocated for use by another file, and
> we note where they are in the extent status cache.  We then issue the
> writes of the data block, and only after they are complete, only
> *then* do we update the metadata blocks (which then gets updated via
> the journal, using either a commit or a fast commit).
>
> This is similar to the dioread_nolock case, where we update the
> metadata blocks first, but mark them as unwritten, then we let the
> data blocks get written, and only finally do we update the metadata
> blocks so they are marked as written (e.g., initialized).  This avoids
> the stale data problem as well, but we end up modifying the metadata
> blocks twice, and it has resulted other performance problems since in
> increases overhead on the i_data_sem lock.  See for example some of
> the posts by Liu Bo from Alibaba last year:
>
> If we can allocate space, write the data blocks, and only *then*
> update the extent tree metadata blocks, it solves a lot of problems.
> We can get rid of the dioread_nolock option; we can get rid of the
> data=ordered vs data=writeback distinction; and we can avoid the need
> to force data blocks to be written out at commit time.  So it improves
> performance, and it will reduce code complexity, making it a win-win
> approach.
>
> The problem is that this means significantly changing how we do block
> allocation and block reservation, so it's a fairly large and invasive
> set of changes.  But it's the right long-term direction, and we'll get
> there eventually.
>
> Cheers,
>
>                                                 - Ted

Re: 答复: [External Mail]Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[Theodore Y. Ts'o]

On Mon, Nov 04, 2019 at 09:01:28AM +0800, xiaohui li wrote:
> 
> when in writeback mode, inode' data has not to be waited in jbd2
> thread, so the fsync time cost is also reduced.
> meawhile, writeback mode also can guarantee filesystem consistency in
> os crash-reboot conditions,
> with only one drawback is that it will cause security problems such as
> stale data will be seen.

It's not just stale data; in data=writeback, today if a file gets
deleted, its blocks are immediately eligible to be reused.  If there
is a crash before the transaction is committed, there could be a file
that would have deleted (and perhaps replaced) that doesn't in fact
get deleted, but its data blocks will have been corrupted.

I'm not fond of that particular behavior, and I may look to fix it,
but in general, data=writeback means that data blocks may be corrupted
or contain stale data after a crash --- for blocks that were freshly
created, or for a file that might have been deleted, but except for
the crash which means that the file deletion doesn't actually get
corrupted.

> but in android system with file encryption enabled, there is no
> security problem as files are all encryped.
> but user will see wrong file data in system crash-reboot conditions
> with writeback mode enabled.

If all files are encrypted, then yes, the chances of stale data
causing security issues is significantly reduced.

But see also the case of a file which is deleted immediately before a
crash.  Things are more complex in terms of the data gauarantees after
a crash, which is why data=ordered is the default.

Regards,

					- Ted

Re: 答复: [External Mail]Re: [PATCH v3 09/13] ext4: fast-commit commit path changes

[xiaohui li]

thank you, ted.

I have understood  the whole design and implementation of the ijournal paper.
and i think the fast commit for ext4 may be designed and implemented
according to idea of that ijournal paper,
as that ijournal thought is the best way for resolve the problem of
file's data has to been waited in jbd2 thread with
order mode from my opinion.

according to that paper, ijournal only record and commit the changes
of the fsync'ed file to its own ijournal area,
the changes of whole ext4 filesystem are left to normal journal to process.
and ijournal only happen at the end of the thread which is doing fsync
work. it need not be embedded to jbd2 thread.
and the changes of the fsync'ed file which have been committed by
ijournal will also be committed to normal journal area subsequently.
ijournal won't have side effect on normal journal , these two journal
runs independently.

all of these above designments of ijournal from my viewpoint will
simply the fast commit function developed recently, meanwhile it can
help fast commit function to
achieve its goals.
one of its most important goals which i have to highlight should be
fix ext4 fsync time cost problems because of file's data has to been
waited in jbd2 thread(same as CTX problems pointed in ijournal paper).
what do you think of it ?

I like this ijournal thought. may be i want to do some work on coding
of this fast commit function in my free time.



On Mon, Nov 4, 2019 at 11:22 AM Theodore Y. Ts'o <tytso@mit.edu> wrote:
>
> On Mon, Nov 04, 2019 at 09:01:28AM +0800, xiaohui li wrote:
> >
> > when in writeback mode, inode' data has not to be waited in jbd2
> > thread, so the fsync time cost is also reduced.
> > meawhile, writeback mode also can guarantee filesystem consistency in
> > os crash-reboot conditions,
> > with only one drawback is that it will cause security problems such as
> > stale data will be seen.
>
> It's not just stale data; in data=writeback, today if a file gets
> deleted, its blocks are immediately eligible to be reused.  If there
> is a crash before the transaction is committed, there could be a file
> that would have deleted (and perhaps replaced) that doesn't in fact
> get deleted, but its data blocks will have been corrupted.
>
> I'm not fond of that particular behavior, and I may look to fix it,
> but in general, data=writeback means that data blocks may be corrupted
> or contain stale data after a crash --- for blocks that were freshly
> created, or for a file that might have been deleted, but except for
> the crash which means that the file deletion doesn't actually get
> corrupted.
>
> > but in android system with file encryption enabled, there is no
> > security problem as files are all encryped.
> > but user will see wrong file data in system crash-reboot conditions
> > with writeback mode enabled.
>
> If all files are encrypted, then yes, the chances of stale data
> causing security issues is significantly reduced.
>
> But see also the case of a file which is deleted immediately before a
> crash.  Things are more complex in terms of the data gauarantees after
> a crash, which is why data=ordered is the default.
>
> Regards,
>
>                                         - Ted