Re: [PATCH] Clustering indirect blocks in Ext3

!MAILaRCHIVE_VOTE_RePLACE
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]
To: Theodore Tso <tytso@...>, Andrew Morton <akpm@...>, Abhishek Rai <abhishekrai@...>, Andreas Dilger <adilger@...>, <linux-kernel@...>, Ken Chen <kenchen@...>, Mike Waychison <mikew@...>
Date: Friday, November 16, 2007 - 8:25 pm

Thanks for the great feedback.

On Nov 16, 2007 1:11 PM, Theodore Tso <tytso@mit.edu> wrote:

When we fallback to old-style allocation, new blocks get allocated next
to the goal and are thus co-located with the corresponding data blocks.


Ideally, this is how things should be done, but I feel in practice, it
will make little difference. To summarize, the difference between
my approach and above approach is that when out of free blocks in a
block group while allocating indirect block, the above approach repeats
the same allocation algorithm in the next block group, while I fully
fall back to old-style allocation meaning the indirect block gets
co-located with the data block in the next block group with a free
block. In practice, this will make a difference only for one indirect
block as from next request onwards the goal will be updated to the new
group making the behavior like what you propose. Still, I think your
suggestion is cleaner and I'll change to that.


Makes sense, will do.


We initially avoided making metaclustering a superblock tunable as we
didn't want to make any changes to the on-disk format as then ext4
extents are also a good option. If metaclustering gains acceptance
it might make sense to make it a superblock tunable. However, I would
avoid putting metacluster size into the superblock for the following
reason. Ideally, we should not have to bother about finding the sweet
spot of metacluster size as
(1) a given file system can be used for storing different kinds
of files at different times and it would be a pain to tune it every now
and then, and
(2) it opens the possibility of doubting metcluster size for unrelated
ext3/fsck performance anomalies.
The user should be able to just enable metaclustering and ext3 should
take care of the rest as best as it can. That said, some type of coarse
metaclustering advice can definitely be stored in the superblock.

Allow me to propose a solution that will most likely address the above
issue and please ignore its complexity for a moment. Instead of a two
level partitioning in the block space between data blocks and
metacluster blocks, have a 3 or 4 level partitioning. E.g., a block
group with 'd' blocks can have d/32 blocks in metacluster level 1,
d/64 blocks in metacluster level 2, and d/128 blocks in metacluster
level 3 (define level 0 has having the remaining blocks = d - d/32 -
d/64 - d/128). Data block allocation starts looking for a free block
starting from the lowest possible level. If it is unable to find any
free blocks at that level in all block groups, it moves up a level and
so on. Indirect block allocation proceeds in the opposite direction
starting from higher levels. This approach has several benefits:

In traditional metaclustering, once we run out of metacluster blocks
or data blocks, all bets are off. This forces us to keep small
metaclusters in order to avoid this situation altogether. But with small
metaclusters, we cannot optimize indirect block allocation on file
systems with many small files (>48KB).There is only one glitch in
implementing this. If a block group doesn't have any free blocks at a
given level, we should be able to find that out quickly instead of
having to scan its entire bitmap. gdp->bg_free_blocks_count is not good
enough for this.

Thanks,
Abhishek
-
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]

Messages in current thread:
[PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Fri Nov 16, 1:02 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Andrew Morton, (Fri Nov 16, 3:02 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Fri Nov 16, 6:27 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Theodore Tso, (Fri Nov 16, 5:11 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Fri Nov 16, 8:25 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Theodore Tso, (Fri Nov 16, 10:58 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Fri Dec 21, 10:15 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Thu Jan 10, 5:17 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Daniel Phillips, (Fri Jan 11, 1:05 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Andrew Morton, (Fri Jan 11, 8:04 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Daniel Phillips, (Sat Jan 12, 2:05 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Sun Jan 13, 1:06 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Sat Nov 17, 4:58 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Andreas Dilger, (Fri Nov 16, 7:28 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Matt Mackall, (Fri Nov 16, 3:37 am)
Re: [PATCH] Clustering indirect blocks in Ext3, Abhishek Rai, (Sun Nov 18, 11:52 am)
Re: [PATCH] Clustering indirect blocks in Ext3, John Stoffel, (Tue Nov 20, 4:25 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Matt Mackall, (Sun Nov 18, 4:47 pm)
Re: [PATCH] Clustering indirect blocks in Ext3, Kyungmin Park, (Mon Nov 19, 6:34 am)