linux-ext4 - [LSF/MM ATTEND] Generic defragmentation strategies

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:	Tue, 13 Jan 2015 15:24:42 +0300
From:	Dmitry Monakhov <dmonakhov@...nvz.org>
To:	lsf-pc@...ts.linux-foundation.org
CC:	linux-fsdevel@...r.kernel.org,
	ext4 development <linux-ext4@...r.kernel.org>,
	Jan Kara <jack@...e.cz>, Theodore Ts'o <tytso@....edu>,
	Dave Chinner <david@...morbit.com>,
	Christoph Hellwig <hch@...radead.org>
Subject: [LSF/MM ATTEND] Generic defragmentation strategies

I would like to submit a topic about generic defragmentation strategies.

FS fragmentation is long standing and well known problem, there are
a lot of studies about single file fragmentation, for this case
terms are well defined and most file systems have effective tools for
that issue (e4defrag(8), xfs_fsr(8)). But fragmentation of a directory
lacks of good researches, even the term 'fragmentation of a directory'
is not a well defined statement.

This issue has much in common with filesystem aging. Most filesystems
try to minimize aging issues on block allocator level, but can not avoid
it completely. Sooner or later aging effect becomes significant and can
not be neglected. Generic filesystem lacks of useful utilities which can
fix this issues once it happens. At the same time this issue greatly
affects many use-cases, especially the ones where consumed space matters:
 - Thin-Provision storage containers (LVM, qcow2, ploop, etc)
 - Thin-Provision environments (qemu/kvm, Docker, VMware, OpenVZ, LXC, etc)
 - Cloud storage solutions (Mail, News, Photo-collection, etc)
 - Non fully-random access devices (SMR, etc)

OpenVZ team has done research [fn:1] which allowed to implement online
defragmetation utility e4defrag2 [fn:2] for EXT4 which support various
defragment strategies for IntA and InetEr fragmenration issues (used
terminology from [fn:3]). We found that using this strategies it's possible
to fix issues caused by fs aging which allows both optimize IO
performance and improve space usage efficiency.

Core kernel API has been already merged [fn:4], but user-space implementation
requires a number of hacks around block allocator (~700 LOC or 30% of total code).

We would like to present our findings and discuss future evolution of kernel API
we need to make userspace-tools more efficient. The talk is not EXT4 specific,
We want to discuss generic fine grain block allocator interface which can provide
advantages for many existing filesystems.

Previous works: [fn:3] [fn:5]

*Other discussion I would like to visit*
 - nvram/mutli-queue related performance bottleneck for existing
   filesystems (mq flush optimization)
 - SMR related topics
 - Various Thin-Provision topics
 - Block/FS layer replication/deduplication topics
 - Range locking (topic from Jan Kara)
 - EXT4 related issues: datachecksumming, performance, block allocator.

* Footnotes

[fn:1] http://lists.openwall.net/linux-ext4/2014/04/28/3

[fn:2] https://github.com/dmonakhov/e2fsprogs/tree/e4defrag2

[fn:3] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.3450

[fn:4] http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/fs/ext4/move_extent.c?id=fcf6b1b729bcd23f2b49a84fb33ffbb44712ee6a

[fn:5] https://events.linuxfoundation.org/slides/2010/linuxcon_japan/linuxcon_jp2010_fujita.pdf

Download attachment "signature.asc" of type "application/pgp-signature" (473 bytes)