lkml.org 
[lkml]   [2000]   [Aug]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Subject[fsdevel] Tailmerging - first results
Date
I'd normally post this to linux-fsdevel, but the list isn't up yet, so...

I now have part of my experimental tailmerging extension for Ext2 working - enough to
measure the expected disk space savings. I'm currently doing a full pass through the
entire filesystem at mount time, merging as many file tails as I can with a simple,
first-fit algorithm.

The current algorithm is:

For each inode with a partly filled tail:
Search back through the list of partly filled merge rings
Is there a merge ring with enough space to hold this file's tail?
If so, merge this file into the ring and reduce the ring's space
If not, add this file to the list of partly filled merge rings
If the list has reached maximal size, drop the oldest ring

What is surprising is how well this simple-minded algorithm works. I tested it on
two source trees: the Linux kernel and Mozilla. Here are the results:

# Install experimental tailmerging version of Ext2
insmod tme2
# Use kernel source for tailmerge test
cd /x && tar -xzf /zoo/linux-2.4.0-test6.tar.gz && cd / && umount /x
# Remount and perform full-filesystem tailmerge pass
mount -t tme2 -o tails=merge /x
Aug 21 11:27:09 gimli kernel: Tailmerging enabled!
Aug 21 11:27:09 gimli kernel: Average tail usage was 1768 of 4096 bytes (43%)
Aug 21 11:27:09 gimli kernel: Average tail usage now 3727 of 4096 bytes (91%)
Aug 21 11:27:09 gimli kernel: Freed 3978 of 26861 blocks (14%)

# Install experimental tailmerging version of Ext2
insmod tme2
# Use mozilla source for tailmerge test
cd /x && tar -xzf /zoo/mozilla-source.tar.gz && cd / && umount /x
# Remount and perform full-filesystem tailmerge pass
mount -t tme2 -o tails=merge /x
Aug 21 12:19:57 gimli kernel: Tailmerging enabled!
Aug 21 12:19:57 gimli kernel: Average tail usage was 1182 of 4096 bytes (28%)
Aug 21 12:19:57 gimli kernel: Average tail usage now 3787 of 4096 bytes (92%)
Aug 21 12:19:57 gimli kernel: Freed 16490 of 53341 blocks (30%)

The bottom line is 14% space savings for the Linux source tree and 30% for Mozilla.
Average utilization of the (merged) tail blocks increases from 28% to 92% for
Mozilla.

No doubt a more sophistated algorithm could achieve even better packing but 92% usage
is already pretty good. (For anyone who cares, I seem to recall that this kind of
optimization problem falls into the np-complete class, IOW, no optimal result
computable in polynomial time.)

This is still far from being useable. The current code just computes the merging
arrangement; it doesn't actually change the filesystem. Reading and writing to the
merged files is not implemented yet, although it has been designed. The incremental
version of the tail merging algorithm still has to be designed and implemented.

More details are available in the linux-fsdevel archives:
http://web.gnu.walfield.org/mail-archive/linux-fsdevel/2000-July/0142.html

--
Daniel
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 12:37    [W:0.017 / U:5.500 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site