ChunkFS - measuring cross-chunk references

ChunkFS - measuring cross-chunk references

[Karuna sagar K]

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

Hi,

The attached code contains program to estimate the cross-chunk
references for ChunkFS file system (idea from Valh). Below are the
results:

test on ext3, / partition-1 on 27 March 2007
Number of files = 217806
Number of directories = 24295
Total size = 8193116 KB
Total data stored = 7557892 KB
Size of block groups = 131072 KB
Number of inodes per block group = 16288
Total no. of cross references = 60657
------------------------------------------------
test on ext3, / partition-1 on 22 March 2007
Number of files = 230615
Number of directories = 24243
Total size = 8193116 KB
Total data stored = 7167212 KB
Size of block groups = 131072 KB
Number of inodes per block group = 16288
Total no. of cross references = 62163
------------------------------------------------
test on ext3, / partition-2 on 22 March 2007
Number of files = 79509
Number of directories = 6397
Total size = 3076888 KB
Total data stored = 1685100 KB
Size of block groups = 131072 KB
Number of inodes per block group = 16032
Total no. of cross references = 17996
---------------------------------------------------------------------------
test on ext3, /home partition-3 on 20 April 2007
Number of files = 157632
Number of directories = 13652
Total size = 10233404 KB
Total data stored = 9490196 KB
Size of block groups = 131072 KB
Number of inodes per block group = 16224
Total no. of cross references = 27184
---------------------------------------------------------------------------

Comments??

Thanks,
Karuna

[-- Attachment #2: cref.tar.bz2 --]
[-- Type: application/x-bzip2, Size: 2134 bytes --]

Re: ChunkFS - measuring cross-chunk references

[Amit Gud]

Karuna sagar K wrote:
> Hi,
> 
> The attached code contains program to estimate the cross-chunk
> references for ChunkFS file system (idea from Valh). Below are the
> results:
> 

Nice to see some numbers! But would be really nice to know:

- what the chunk size is
- how the files were created or, more vaguely, how 'aged' the fs is
- what is the chunk allocation algorithm


Best,
AG
-- 
May the source be with you.
http://www.cis.ksu.edu/~gud

Re: ChunkFS - measuring cross-chunk references

[Karuna sagar K]

Hi,

The tool estimates the cross-chunk references from an extt2/3 file
system. It considers a block group as one chunk and calcuates how many
block groups does a file span across. So, the block group size gives
the estimate of chunk size.

The file systems were aged for about 3-4 months on a developers laptop.

Should have given the background before. Below is the explanations for
the tool. Valh and others came up with this idea.

-------------------------
Chunkfs will only work if we have "few" cross-chunk references.  We
can estimate the effect of chunk size on the number of these
references using an existing ext2/3 file system and treating the block
groups as though they are chunks.  The basic idea is that we figure
out what the block group boundaries are and then find out which files
and directories span two or more block groups.

Step 1:
-------

Get a real-world ext2/3 file system. A file system which has been in
use is required. One from a laptop or a server of any sort will do
fine.

Step 2:
-------

Figure out where the block group boundaries are on disk. Two things
are to be known:

1. Which inode numbers are in which block group?
2. Which blocks are in which block group?

At the end of this step we should have a list that looks something like:

Block group 1: Inodes 11-343, blocks 1000-20000
Block group 2: Inodes 344-576, blocks 20000-40000
[...]

Step 3:
-------

For each file, get the inode number and use mapping from step 2 to
figure out which block group it is in.  Now use bmap() on each block
in the file, and find out the block number.  Use mapping from step 2
to figure out which block groups it has data in. For each file, record
the list of all block groups.

For each directory, get the inode number and map that to a block
group. Then get the inode numbers of all entries in the directory
(ignore symlinks) and map them to a block group.  For each directory,
record the list of all block groups.

Step 4:
-------

Count the number of cross-chunk references this file system would
need.  This is done by going through each directory and file, and
adding up the number of block groups it uses MINUS one.  So if a file
was in block groups 3, 7, and 24, then you would add 2 to the total
number of cross-chunk references.  If a file was only in block group
2, then you would add 0 to the total.


On 4/22/07, Amit Gud <gud@ksu.edu> wrote:
> Karuna sagar K wrote:
> > Hi,
> >
> > The attached code contains program to estimate the cross-chunk
> > references for ChunkFS file system (idea from Valh). Below are the
> > results:
> >
>
> Nice to see some numbers! But would be really nice to know:
>
> - what the chunk size is
> - how the files were created or, more vaguely, how 'aged' the fs is
> - what is the chunk allocation algorithm
>
>
> Best,
> AG
> --
> May the source be with you.
> http://www.cis.ksu.edu/~gud
>
>


Thanks,
Karuna

Re: ChunkFS - measuring cross-chunk references

[Kalpak Shah]

On Mon, 2007-04-23 at 12:49 +0530, Karuna sagar K wrote:
> Hi,
> 
> The tool estimates the cross-chunk references from an extt2/3 file
> system. It considers a block group as one chunk and calcuates how many
> block groups does a file span across. So, the block group size gives
> the estimate of chunk size.
> 
> The file systems were aged for about 3-4 months on a developers laptop.
> 

With a blocksize of 4KB, a block group would be 128 MB. In the original
Chunkfs paper, Valh had mentioned 1GB chunks and I believe it will be
possible to use 2GB, 4GB or 8GB chunks in the future. As the chunk size
increases the number of cross-chunk references will reduce and hence it
might be a good idea to present these statistics considering different
chunk sizes starting from 512MB upto 2GB.

Thanks,
Kalpak.

Re: ChunkFS - measuring cross-chunk references

[Andreas Dilger]

On Apr 23, 2007  15:04 +0530, Kalpak Shah wrote:
> On Mon, 2007-04-23 at 12:49 +0530, Karuna sagar K wrote:
> > The tool estimates the cross-chunk references from an extt2/3 file
> > system. It considers a block group as one chunk and calcuates how many
> > block groups does a file span across. So, the block group size gives
> > the estimate of chunk size.
> > 
> > The file systems were aged for about 3-4 months on a developers laptop.
> 
> With a blocksize of 4KB, a block group would be 128 MB. In the original
> Chunkfs paper, Valh had mentioned 1GB chunks and I believe it will be
> possible to use 2GB, 4GB or 8GB chunks in the future. As the chunk size
> increases the number of cross-chunk references will reduce and hence it
> might be a good idea to present these statistics considering different
> chunk sizes starting from 512MB upto 2GB.

Also, given that cross-chunk references will be more expensive to fix, I
can imagine the allocation policy for chunkfs will try to avoid this if
possible, further reducing the number of cross-chunk inodes.  I guess it
should be more clear whether the cross-chunk references are due to inode
block references, or because of e.g. directories referencing inodes in
another chunk.

Also, is it considered a cross-chunk reference if a directory entry is
referencing an inode in another group?  Should there be a continuation
inode in the local group, or is the directory entry itself enough?

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

Re: ChunkFS - measuring cross-chunk references

[Theodore Tso]

On Mon, Apr 23, 2007 at 02:53:33PM -0600, Andreas Dilger wrote:
> > With a blocksize of 4KB, a block group would be 128 MB. In the original
> > Chunkfs paper, Valh had mentioned 1GB chunks and I believe it will be
> > possible to use 2GB, 4GB or 8GB chunks in the future. As the chunk size
> > increases the number of cross-chunk references will reduce and hence it
> > might be a good idea to present these statistics considering different
> > chunk sizes starting from 512MB upto 2GB.
> 
> Also, given that cross-chunk references will be more expensive to fix, I
> can imagine the allocation policy for chunkfs will try to avoid this if
> possible, further reducing the number of cross-chunk inodes.  I guess it
> should be more clear whether the cross-chunk references are due to inode
> block references, or because of e.g. directories referencing inodes in
> another chunk.

It would also be good to distinguish between directories referencing
files in another chunk, and directories referencing subdirectories in
another chunk (which would be simpler to handle, given the topological
restrictions on directories, as compared to files and hard links).

There may also be special things we will need to do to handle
scenarios such as BackupPC, where if it looks like a directory
contains a huge number of hard links to a particular chunk, we'll need
to make sure that directory is either created in the right chunk
(possibly with hints from the application) or migrated to the right
chunk (but this might cause the inode number of the directory to
change --- maybe we allow this as long as the directory has never been
stat'ed, so that the inode number has never been observed).

The other thing which we should consider is that chunkfs really
requires a 64-bit inode number space, which means either we only allow
it on 64-bit systems, or we need to consider a migration so that even
on 32-bit platforms, stat() functions like stat64(), insofar that it
uses a stat structure which returns a 64-bit ino_t.

						- Ted

Re: ChunkFS - measuring cross-chunk references

[Arjan van de Ven]

> The other thing which we should consider is that chunkfs really
> requires a 64-bit inode number space, which means either we only allow

does it?
I'd think it needs a "chunk space" number and a 32 bit local inode
number ;) (same for blocks)

Re: ChunkFS - measuring cross-chunk references

[Amit Gud]

On Mon, 23 Apr 2007, Arjan van de Ven wrote:

>
>> The other thing which we should consider is that chunkfs really
>> requires a 64-bit inode number space, which means either we only allow
>
> does it?
> I'd think it needs a "chunk space" number and a 32 bit local inode
> number ;) (same for blocks)
>

For inodes, yes, either 64-bit inode or some field for the chunk id in 
which the inode is. But for block numbers, you don't. Because individual 
chunks manage part of the whole file system in an independent way. They 
have their block bitmaps starting at an offset. Inode bitmaps, however, 
remains same.


AG
--
May the source be with you.
http://www.cis.ksu.edu/~gud

Re: ChunkFS - measuring cross-chunk references

[Amit Gud]

On Mon, 23 Apr 2007, Amit Gud wrote:

> On Mon, 23 Apr 2007, Arjan van de Ven wrote:
>
>> 
>> >  The other thing which we should consider is that chunkfs really
>> >  requires a 64-bit inode number space, which means either we only allow
>>
>>  does it?
>>  I'd think it needs a "chunk space" number and a 32 bit local inode
>>  number ;) (same for blocks)
>> 
>
> For inodes, yes, either 64-bit inode or some field for the chunk id in which 
> the inode is. But for block numbers, you don't. Because individual chunks 
> manage part of the whole file system in an independent way. They have their 
> block bitmaps starting at an offset. Inode bitmaps, however, remains same.
>

In that sense, we also can do away without having chunk identifier encoded 
into inode number and chunkfs would still be fine with it. But we will 
then loose inode uniqueness property, which could well be OK as it is with 
other file systems in which inode number is not sufficient for unique 
identification of an inode.


AG
--
May the source be with you.
http://www.cis.ksu.edu/~gud

Re: ChunkFS - measuring cross-chunk references

[Theodore Tso]

On Mon, Apr 23, 2007 at 06:02:29PM -0700, Arjan van de Ven wrote:
> 
> > The other thing which we should consider is that chunkfs really
> > requires a 64-bit inode number space, which means either we only allow
> 
> does it?
> I'd think it needs a "chunk space" number and a 32 bit local inode
> number ;) (same for blocks)
> 

But that means that the number which gets exported to userspace via
the stat system call will need more than 32 bits worth of ino_t....

						- Ted

Re: ChunkFS - measuring cross-chunk references

[Karuna sagar K]

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

On 4/24/07, Theodore Tso <tytso@mit.edu> wrote:
> On Mon, Apr 23, 2007 at 02:53:33PM -0600, Andreas Dilger wrote:
.........
> It would also be good to distinguish between directories referencing
> files in another chunk, and directories referencing subdirectories in
> another chunk (which would be simpler to handle, given the topological
> restrictions on directories, as compared to files and hard links).
>

Modified the tool to distinguish between
1. cross references between directories and files
2. cross references between directories and sub directories
3. cross references within a file (due to huge file size)

Below is the result from / partition of ext3 file system:

Number of files = 221794
Number of directories = 24457
Total size = 8193116 KB
Total data stored = 7187392 KB
Size of block groups = 131072 KB
Number of inodes per block group = 16288
No. of cross references between directories and sub-directories = 7791
No. of cross references between directories and file = 657
Total no. of cross references = 62018 (dir ref = 8448, file ref = 53570)

Thanks for the suggestions.

> There may also be special things we will need to do to handle
> scenarios such as BackupPC, where if it looks like a directory
> contains a huge number of hard links to a particular chunk, we'll need
> to make sure that directory is either created in the right chunk
> (possibly with hints from the application) or migrated to the right
> chunk (but this might cause the inode number of the directory to
> change --- maybe we allow this as long as the directory has never been
> stat'ed, so that the inode number has never been observed).
>
> The other thing which we should consider is that chunkfs really
> requires a 64-bit inode number space, which means either we only allow
> it on 64-bit systems, or we need to consider a migration so that even
> on 32-bit platforms, stat() functions like stat64(), insofar that it
> uses a stat structure which returns a 64-bit ino_t.
>
>                                                - Ted
>


Thanks,
Karuna

[-- Attachment #2: cref.tar.bz2 --]
[-- Type: application/x-bzip2, Size: 2295 bytes --]

ChunkFS - measuring cross-chunk references

[Karuna sagar K]

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

On 4/24/07, Theodore Tso <tytso@mit.edu> wrote:
> On Mon, Apr 23, 2007 at 02:53:33PM -0600, Andreas Dilger wrote:
.........
> It would also be good to distinguish between directories referencing
> files in another chunk, and directories referencing subdirectories in
> another chunk (which would be simpler to handle, given the topological
> restrictions on directories, as compared to files and hard links).
>

Modified the tool to distinguish between
1. cross references between directories and files
2. cross references between directories and sub directories
3. cross references within a file (due to huge file size)

Below is the result from / partition of ext3 file system:

Number of files = 221794
Number of directories = 24457
Total size = 8193116 KB
Total data stored = 7187392 KB
Size of block groups = 131072 KB
Number of inodes per block group = 16288
No. of cross references between directories and sub-directories = 7791
No. of cross references between directories and file = 657
Total no. of cross references = 62018 (dir ref = 8448, file ref = 53570)

Thanks for the suggestions.

> There may also be special things we will need to do to handle
> scenarios such as BackupPC, where if it looks like a directory
> contains a huge number of hard links to a particular chunk, we'll need
> to make sure that directory is either created in the right chunk
> (possibly with hints from the application) or migrated to the right
> chunk (but this might cause the inode number of the directory to
> change --- maybe we allow this as long as the directory has never been
> stat'ed, so that the inode number has never been observed).
>
> The other thing which we should consider is that chunkfs really
> requires a 64-bit inode number space, which means either we only allow
> it on 64-bit systems, or we need to consider a migration so that even
> on 32-bit platforms, stat() functions like stat64(), insofar that it
> uses a stat structure which returns a 64-bit ino_t.
>
>                                                - Ted
>


Thanks,
Karuna

[-- Attachment #2: cref.tar.bz2 --]
[-- Type: application/x-bzip2, Size: 2295 bytes --]

Re: ChunkFS - measuring cross-chunk references

[Suparna Bhattacharya]

On Wed, Apr 25, 2007 at 05:50:55AM +0530, Karuna sagar K wrote:
> On 4/24/07, Theodore Tso <tytso@mit.edu> wrote:
> >On Mon, Apr 23, 2007 at 02:53:33PM -0600, Andreas Dilger wrote:
> .........
> >It would also be good to distinguish between directories referencing
> >files in another chunk, and directories referencing subdirectories in
> >another chunk (which would be simpler to handle, given the topological
> >restrictions on directories, as compared to files and hard links).
> >
> 
> Modified the tool to distinguish between
> 1. cross references between directories and files
> 2. cross references between directories and sub directories
> 3. cross references within a file (due to huge file size)

One more set of numbers to calculate would be an estimate of cross-references
across chunks of block groups -- 1 (=128MB), 2 (=256MB), 4 (=512MB), 8(=1GB)
as suggested by Kalpak.

Once we have that, it would be nice if we can get data on results with
the tool from other people, especially with larger filesystem sizes.

Regards
Suparna

> 
> Below is the result from / partition of ext3 file system:
> 
> Number of files = 221794
> Number of directories = 24457
> Total size = 8193116 KB
> Total data stored = 7187392 KB
> Size of block groups = 131072 KB
> Number of inodes per block group = 16288
> No. of cross references between directories and sub-directories = 7791
> No. of cross references between directories and file = 657
> Total no. of cross references = 62018 (dir ref = 8448, file ref = 53570)
> 
> Thanks for the suggestions.
> 
> >There may also be special things we will need to do to handle
> >scenarios such as BackupPC, where if it looks like a directory
> >contains a huge number of hard links to a particular chunk, we'll need
> >to make sure that directory is either created in the right chunk
> >(possibly with hints from the application) or migrated to the right
> >chunk (but this might cause the inode number of the directory to
> >change --- maybe we allow this as long as the directory has never been
> >stat'ed, so that the inode number has never been observed).
> >
> >The other thing which we should consider is that chunkfs really
> >requires a 64-bit inode number space, which means either we only allow
> >it on 64-bit systems, or we need to consider a migration so that even
> >on 32-bit platforms, stat() functions like stat64(), insofar that it
> >uses a stat structure which returns a 64-bit ino_t.
> >
> >                                               - Ted
> >
> 
> 
> Thanks,
> Karuna



-- 
Suparna Bhattacharya (suparna@in.ibm.com)
Linux Technology Center
IBM Software Lab, India

Re: ChunkFS - measuring cross-chunk references

[Karuna sagar K]

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

On 4/25/07, Suparna Bhattacharya <suparna@in.ibm.com> wrote:
> On Wed, Apr 25, 2007 at 05:50:55AM +0530, Karuna sagar K wrote:
>
> One more set of numbers to calculate would be an estimate of cross-references
> across chunks of block groups -- 1 (=128MB), 2 (=256MB), 4 (=512MB), 8(=1GB)
> as suggested by Kalpak.
>

Here is the tool to make such calculations.

Result of running the tool on / partition of ext3 file system (each
chunk is 4 times a block group):

./cref.sh /dev/hda1 dmp /mnt/test 4

-------------------------------------------------------

Number of files = 221763

Number of directories = 24456

Total size = 8193116 KB

Total data stored = 7179200 KB

Size of block groups = 131072 KB

Number of inodes per block group = 16288

Chunk size = 524288 KB

No. of cross references between directories and sub-directories = 869

No. of cross references between directories and file = 584

Total no. of cross references = 13806 (dir ref = 1453, file ref = 12353)

-------------------------------------------------------


> Once we have that, it would be nice if we can get data on results with
> the tool from other people, especially with larger filesystem sizes.
>


Thanks,
Karuna

[-- Attachment #2: cref.tar.bz2 --]
[-- Type: application/x-bzip2, Size: 2336 bytes --]

Re: ChunkFS - measuring cross-chunk references

[Valerie Henson]

On Mon, Apr 23, 2007 at 08:13:06PM -0400, Theodore Tso wrote:
> 
> There may also be special things we will need to do to handle
> scenarios such as BackupPC, where if it looks like a directory
> contains a huge number of hard links to a particular chunk, we'll need
> to make sure that directory is either created in the right chunk
> (possibly with hints from the application) or migrated to the right
> chunk (but this might cause the inode number of the directory to
> change --- maybe we allow this as long as the directory has never been
> stat'ed, so that the inode number has never been observed).

Yeah, this is an oddball but real case.  What are the consequences of
inode number changing - increased backup bandwidth?  It seems like it
would have the same effect as "cp -a dir tmp; rm -rf dir; mv tmp dir",
which is certainly legal (and a good way to defragment subtrees).

> The other thing which we should consider is that chunkfs really
> requires a 64-bit inode number space, which means either we only allow
> it on 64-bit systems, or we need to consider a migration so that even
> on 32-bit platforms, stat() functions like stat64(), insofar that it
> uses a stat structure which returns a 64-bit ino_t.

A 32-bit inode space probably won't be that hard to do for chunkfs,
although it would limit total file system size.  This problem needs to
be solved in general, I'm afraid - 4 billion inodes is just not that
many now.

-VAL

Re: ChunkFS - measuring cross-chunk references

[Valerie Henson]

On Mon, Apr 23, 2007 at 02:53:33PM -0600, Andreas Dilger wrote:
> 
> Also, is it considered a cross-chunk reference if a directory entry is
> referencing an inode in another group?  Should there be a continuation
> inode in the local group, or is the directory entry itself enough?

(Sorry for the delay; just moved to Portland these last couple of
weeks.)

It is a cross-chunk reference - we can't calculate the correct link
count for the target file unless we have a quick way to get all the
directory entries pointing to an inode.  My current scheme is to
create a continuation inode for the directory in the chunk containing
the inode (if the chunk containing the inode is full, create new
continuation inodes for both in a new chunk).

-VAL

Re: ChunkFS - measuring cross-chunk references

[Valerie Henson]

On Mon, Apr 23, 2007 at 02:05:47AM +0530, Karuna sagar K wrote:
> Hi,
> 
> The attached code contains program to estimate the cross-chunk
> references for ChunkFS file system (idea from Valh). Below are the
> results:

Nice work!  Thank you very much for doing this!

-VAL