Split some metadata onto separate device?

Split some metadata onto separate device?

[dexen deVries]

Hi list,

back when I was using XFS, there was an option to put one particular piece of 
metadata -- the journal -- onto separate physical device. The speed-up was 
very significant, especially for operations on lots of files. For example, with 
external journal removing whole kernel source tree on XFS would take less time 
than on ext2 or ext3; with internal it would be much longer than ext2 or 3.

The journal was needed only in case of unclean unmount, as only then it 
contained any information not applied yet; if the unmount was clean, the 
journal contained no important information.

XFS journals only metadata changes, btw.


My question is, would it be feasible to move some part of NILFS2 metadata onto 
separate device for R/W/GC speed-up? 

Perhaps some of metadata could even be considered `recoverable' -- that is, if 
the other device gets broken or lost, the metadata on it could be re-
constructed from content of the main device.


Regards,
-- 
dexen deVries

[[[↓][→]]]

For example, if the first thing in the file is:
   <?kzy irefvba="1.0" rapbqvat="ebg13"?>
an XML parser will recognize that the document is stored in the traditional 
ROT13 encoding.

(( Joe English, http://www.flightlab.com/~joe/sgml/faq-not.txt ))
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[Ryusuke Konishi]

Hi dexen,
On Fri, 3 Jun 2011 12:29:33 +0200, dexen deVries wrote:
> Hi list,
> 
> back when I was using XFS, there was an option to put one particular piece of 
> metadata -- the journal -- onto separate physical device. The speed-up was 
> very significant, especially for operations on lots of files. For example, with 
> external journal removing whole kernel source tree on XFS would take less time 
> than on ext2 or ext3; with internal it would be much longer than ext2 or 3.
> 
> The journal was needed only in case of unclean unmount, as only then it 
> contained any information not applied yet; if the unmount was clean, the 
> journal contained no important information.
> 
> XFS journals only metadata changes, btw.
> 
> 
> My question is, would it be feasible to move some part of NILFS2 metadata onto 
> separate device for R/W/GC speed-up? 
> 
> Perhaps some of metadata could even be considered `recoverable' -- that is, if 
> the other device gets broken or lost, the metadata on it could be re-
> constructed from content of the main device.

NILFS2 is a log-structured filesystem and that means the filesystem
itself is a big journal.  My understanding is using separate journal
device has no merit of performance.

On the other hand, We may be able to speed up the filesystem by
putting DAT (disk address translation) metadata to a separate device.
I mean putting a full copy of the DAT metadata on the sperate device
instead of journal of it.

The DAT is referred to every time an off-cache block is read from the
disk, and is updated every time we overwrite or create some disk
blocks.  Even though the DAT is just a table data, the current NILFS2
uses b-tree for its lookup and writes them in a log like manner.

This is meaningless from engineering perspective and decreasing
performance due to fragmentation.

The same is true of SUFILE and CPFILE metadata, where the former is
keeping matadata of segment usage state, and the latter, checkpoint
list.

Putting original of these metadata on a separate device and journaling
it in the NILFS partition would have performance merits.

But, I think we have other approaches to think about before that with
regard to performance improvement.  For example, applying "extent" to
DAT seems much more effective.


Thanks,
Ryusuke Konishi

> Regards,
> -- 
> dexen deVries
> 
> [[[↓][→]]]
> 
> For example, if the first thing in the file is:
>    <?kzy irefvba="1.0" rapbqvat="ebg13"?>
> an XML parser will recognize that the document is stored in the traditional 
> ROT13 encoding.
> 
> (( Joe English, http://www.flightlab.com/~joe/sgml/faq-not.txt ))
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[dexen deVries]

Hi Ryusuke,


On Friday 03 June 2011 19:26:21 you wrote:
> (...) 
> NILFS2 is a log-structured filesystem and that means the filesystem
> itself is a big journal.  My understanding is using separate journal
> device has no merit of performance.
> 
> On the other hand, We may be able to speed up the filesystem by
> putting DAT (disk address translation) metadata to a separate device.
> I mean putting a full copy of the DAT metadata on the sperate device
> instead of journal of it.

*nods* sounds interesting. Of course changing on-disk format would hurt ;-)


> But, I think we have other approaches to think about before that with
> regard to performance improvement.  For example, applying "extent" to
> DAT seems much more effective.

Currently every block of file gets own entry in DAT, right?


By the way, it seems to me that the in-kernel GC does not attempt to de-
fragment files. Is that the case? If so, would probably mean extents would not 
help very much for fragmented files. Also, on magnetic media, a lot of seeking 
happens in case of fragmented files.


Regards,
-- 
dexen deVries

``One can't proceed from the informal to the formal by formal means.''
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[Ryusuke Konishi]

On Fri, 3 Jun 2011 19:42:28 +0200, dexen deVries wrote:
> Hi Ryusuke,
> 
> 
> On Friday 03 June 2011 19:26:21 you wrote:
> > (...) 
> > NILFS2 is a log-structured filesystem and that means the filesystem
> > itself is a big journal.  My understanding is using separate journal
> > device has no merit of performance.
> > 
> > On the other hand, We may be able to speed up the filesystem by
> > putting DAT (disk address translation) metadata to a separate device.
> > I mean putting a full copy of the DAT metadata on the sperate device
> > instead of journal of it.
> 
> *nods* sounds interesting. Of course changing on-disk format would hurt ;-)
> 
> 
> > But, I think we have other approaches to think about before that with
> > regard to performance improvement.  For example, applying "extent" to
> > DAT seems much more effective.
> 
> Currently every block of file gets own entry in DAT, right?

Exactly.

> By the way, it seems to me that the in-kernel GC does not attempt to
> de- fragment files. Is that the case? If so, would probably mean
> extents would not help very much for fragmented files. Also, on
> magnetic media, a lot of seeking happens in case of fragmented
> files.

Yes, but extents will decrease the amount of metadata, and this has
potential for speed up.

NILFS2 uses 32 bytes metadata per disk block at present.  I guess you
know that the number of DAT blocks are actually indispensable through
analysis using the dumpseg tool.

Regards,
Ryusuke Konishi


> Regards,
> -- 
> dexen deVries
> 
> ``One can't proceed from the informal to the formal by formal means.''
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[Ryusuke Konishi]

On Wed, 08 Jun 2011 21:48:52 +0900 (JST), Ryusuke Konishi wrote:
> On Fri, 3 Jun 2011 19:42:28 +0200, dexen deVries wrote:
> > By the way, it seems to me that the in-kernel GC does not attempt to
> > de- fragment files. Is that the case? If so, would probably mean
> > extents would not help very much for fragmented files. Also, on
> > magnetic media, a lot of seeking happens in case of fragmented
> > files.
> 
> Yes, but extents will decrease the amount of metadata, and this has
> potential for speed up.
> 
> NILFS2 uses 32 bytes metadata per disk block at present.  I guess you
> know that the number of DAT blocks are actually indispensable through
> analysis using the dumpseg tool.

Oh, looks confusing.  I meant the amount of DAT blocks is not
negligible.

Regards,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[dexen deVries]

Hi again,


On Wednesday 08 of June 2011 14:58:03 you wrote:
> On Wed, 08 Jun 2011 21:48:52 +0900 (JST), Ryusuke Konishi wrote:
> > On Fri, 3 Jun 2011 19:42:28 +0200, dexen deVries wrote:
> > > By the way, it seems to me that the in-kernel GC does not attempt to
> > > de- fragment files. Is that the case? If so, would probably mean
> > > extents would not help very much for fragmented files. Also, on
> > > magnetic media, a lot of seeking happens in case of fragmented
> > > files.
> > 
> > Yes, but extents will decrease the amount of metadata, and this has
> > potential for speed up.
> > 
> > NILFS2 uses 32 bytes metadata per disk block at present.  I guess you
> > know that the number of DAT blocks are actually indispensable through
> > analysis using the dumpseg tool.
> 
> Oh, looks confusing.  I meant the amount of DAT blocks is not
> negligible.

Understood ;-)

Anyway, isn't some fragmentation avoidance necessary to profit from extents 
(that we hope we'll use at some point)?
AFAIK, an extent is only good to describe file blocks if they are laid out 
continuous on the block device.


Cheers,
-- 
dexen deVries

[[[↓][→]]]

For example, if the first thing in the file is:
   <?kzy irefvba="1.0" rapbqvat="ebg13"?>
an XML parser will recognize that the document is stored in the traditional 
ROT13 encoding.

(( Joe English, http://www.flightlab.com/~joe/sgml/faq-not.txt ))
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[Ryusuke Konishi]

On Wed, 8 Jun 2011 15:08:37 +0200, dexen deVries wrote:
> Hi again,
> 
> 
> On Wednesday 08 of June 2011 14:58:03 you wrote:
> > On Wed, 08 Jun 2011 21:48:52 +0900 (JST), Ryusuke Konishi wrote:
> > > On Fri, 3 Jun 2011 19:42:28 +0200, dexen deVries wrote:
> > > > By the way, it seems to me that the in-kernel GC does not attempt to
> > > > de- fragment files. Is that the case? If so, would probably mean
> > > > extents would not help very much for fragmented files. Also, on
> > > > magnetic media, a lot of seeking happens in case of fragmented
> > > > files.
> > > 
> > > Yes, but extents will decrease the amount of metadata, and this has
> > > potential for speed up.
> > > 
> > > NILFS2 uses 32 bytes metadata per disk block at present.  I guess you
> > > know that the number of DAT blocks are actually indispensable through
> > > analysis using the dumpseg tool.
> > 
> > Oh, looks confusing.  I meant the amount of DAT blocks is not
> > negligible.
> 
> Understood ;-)
> 
> Anyway, isn't some fragmentation avoidance necessary to profit from extents 
> (that we hope we'll use at some point)?

I guess it doesn't become a big issue unless we do many small random
writes like database.

> AFAIK, an extent is only good to describe file blocks if they are laid out 
> continuous on the block device.

Yep.  And, we know files are enough continuous in most cases.

We use at least 16 bytes per 4 kiro-bytes disk block to point the
block (16KB for 8MB segment); btrees of nilfs2 use an 8 bytes key and
an 8 bytes pointer for a disk block.

In typical case, this can be reduced to 16 bytes per file (16 bytes
for 8MB segment) with the extents.

IMO, 64-bit filesystems have a reasonable reason to adopt extents
though nilfs2 did not apply it.

I guess applying extents to the DAT file is especially effective.


Regards,
Ryusuke Konishi

> Cheers,
> -- 
> dexen deVries
> 
> [[[↓][→]]]
> 
> For example, if the first thing in the file is:
>    <?kzy irefvba="1.0" rapbqvat="ebg13"?>
> an XML parser will recognize that the document is stored in the traditional 
> ROT13 encoding.
> 
> (( Joe English, http://www.flightlab.com/~joe/sgml/faq-not.txt ))
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Split some metadata onto separate device?

[Reinoud Zandijk]

[-- Attachment #1: Type: text/plain, Size: 2526 bytes --]

Hi Dexen, hi Ryusuke,

been a while since i was active on the list or active with NiLFS in general
but the last vacation did remind me why i started working on NiLFS for NetBSD
again! Using FFS, even with logging, UDF or msdosfs just doesn't work well on
Flash media ;)

On Wed, Jun 08, 2011 at 10:49:06PM +0900, Ryusuke Konishi wrote:
> > > > Yes, but extents will decrease the amount of metadata, and this has
> > > > potential for speed up.
> > > > 
> > > > NILFS2 uses 32 bytes metadata per disk block at present.  I guess you
> > > > know that the number of DAT blocks are actually indispensable through
> > > > analysis using the dumpseg tool.
> > > 
> > > Oh, looks confusing.  I meant the amount of DAT blocks is not
> > > negligible.
> > 
> > Understood ;-)
> > 
> > Anyway, isn't some fragmentation avoidance necessary to profit from extents 
> > (that we hope we'll use at some point)?
> 
> I guess it doesn't become a big issue unless we do many small random
> writes like database.
> 
> > AFAIK, an extent is only good to describe file blocks if they are laid out 
> > continuous on the block device.
> 
> Yep.  And, we know files are enough continuous in most cases.
> 
> We use at least 16 bytes per 4 kiro-bytes disk block to point the
> block (16KB for 8MB segment); btrees of nilfs2 use an 8 bytes key and
> an 8 bytes pointer for a disk block.
> 
> In typical case, this can be reduced to 16 bytes per file (16 bytes
> for 8MB segment) with the extents.
> 
> IMO, 64-bit filesystems have a reasonable reason to adopt extents
> though nilfs2 did not apply it.
> 
> I guess applying extents to the DAT file is especially effective.

I've used extents a lot in UDF since its all-extent based, and yes, it CAN be
a lot smaller indeed :) BUT only when files are NOT sparse and NOT fragmented.

Anyway, my sugestion is an intermediate one since it doesn't change the disc
format: on garbage collection, make an extra pass to seek (very) fragmented
extents in the DAT, how much might be a parameter, read it all in and then
relocate/write out a whole (or partial) segment with it. This could also be
done with the CP and SU files although those files are relatively tiny. This
will leave the DAT file in just a few segments when the filesystem has been
garbage collected and (hopefully) most references only within the segment also
easing cachability.

Other files could also be un-sparsified this way but i think the DAT will have
the most benefit and it's relatively easy to do this way.

With regards,
Reinoud


[-- Attachment #2: Type: application/pgp-signature, Size: 487 bytes --]

Re: Split some metadata onto separate device?

[Ryusuke Konishi]

Hi Reinoud,
On Tue, 14 Jun 2011 13:18:52 +0200, Reinoud Zandijk wrote:
> Hi Dexen, hi Ryusuke,
> 
> been a while since i was active on the list or active with NiLFS in general
> but the last vacation did remind me why i started working on NiLFS for NetBSD
> again! Using FFS, even with logging, UDF or msdosfs just doesn't work well on
> Flash media ;)
> 
> On Wed, Jun 08, 2011 at 10:49:06PM +0900, Ryusuke Konishi wrote:
> > > > > Yes, but extents will decrease the amount of metadata, and this has
> > > > > potential for speed up.
> > > > > 
> > > > > NILFS2 uses 32 bytes metadata per disk block at present.  I guess you
> > > > > know that the number of DAT blocks are actually indispensable through
> > > > > analysis using the dumpseg tool.
> > > > 
> > > > Oh, looks confusing.  I meant the amount of DAT blocks is not
> > > > negligible.
> > > 
> > > Understood ;-)
> > > 
> > > Anyway, isn't some fragmentation avoidance necessary to profit from extents 
> > > (that we hope we'll use at some point)?
> > 
> > I guess it doesn't become a big issue unless we do many small random
> > writes like database.
> > 
> > > AFAIK, an extent is only good to describe file blocks if they are laid out 
> > > continuous on the block device.
> > 
> > Yep.  And, we know files are enough continuous in most cases.
> > 
> > We use at least 16 bytes per 4 kiro-bytes disk block to point the
> > block (16KB for 8MB segment); btrees of nilfs2 use an 8 bytes key and
> > an 8 bytes pointer for a disk block.
> > 
> > In typical case, this can be reduced to 16 bytes per file (16 bytes
> > for 8MB segment) with the extents.
> > 
> > IMO, 64-bit filesystems have a reasonable reason to adopt extents
> > though nilfs2 did not apply it.
> > 
> > I guess applying extents to the DAT file is especially effective.

> I've used extents a lot in UDF since its all-extent based, and yes,
> it CAN be a lot smaller indeed :) BUT only when files are NOT sparse
> and NOT fragmented.
> 
> Anyway, my sugestion is an intermediate one since it doesn't change
> the disc format: on garbage collection, make an extra pass to seek
> (very) fragmented extents in the DAT, how much might be a parameter,
> read it all in and then relocate/write out a whole (or partial)
> segment with it. This could also be done with the CP and SU files
> although those files are relatively tiny. This will leave the DAT
> file in just a few segments when the filesystem has been garbage
> collected and (hopefully) most references only within the segment
> also easing cachability.
> 
> Other files could also be un-sparsified this way but i think the DAT
> will have the most benefit and it's relatively easy to do this way.

That's a good point.  Defragmetation on GC is a known technique for
LFS, but defragmentation focusing on the DAT file sounds more
meaningful.

We already have components for that:

One-shot GC routine is now separated as a library from nilfs_cleanerd
(i.e. libnilfsgc), and we can call it even while the cleaner is
running.

Also, we have an ioctl command to get location of disk blocks
composing the DAT file.  (i.e. NILFS_IOCTL_GET_BDESCS).

With these setups, making a defrag tool for DAT seems possible.

The bad news is that the current GC routine cannot leave other blocks
in the same segment untouched; they will be moved along with blocks of
the DAT file.


By the way, I am considering to propose a disk format change to
implement feaures like checkpoint diff, revert without file
duplication, and extended attributes.  (We once posted a patchset on
the checkpoint diff with title "[PATCH 0/9] exprimental API to extract
changes between two checkpoints").

We may enlarge the size of disk inode to 256 bytes from the current
128 byte size in order to store information needed for those
enhancements.

If you have an opinion (or objection) for this, please let me know.


Thanks,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html