Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

[Changman Lee <cm224.lee@samsung.com>]

Hi Chao,

On Sun, Jan 04, 2015 at 11:19:28AM +0800, Chao Yu wrote:
> Hi Changman,
> 
> Sorry for replying late!
> 
> > -----Original Message-----
> > From: Changman Lee [mailto:cm224.lee@samsung.com]
> > Sent: Tuesday, December 30, 2014 8:32 AM
> > To: Jaegeuk Kim
> > Cc: Chao Yu; linux-f2fs-devel@lists.sourceforge.net; linux-kernel@vger.kernel.org
> > Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree
> > 
> > Hi all,
> > 
> > On Mon, Dec 29, 2014 at 01:23:00PM -0800, Jaegeuk Kim wrote:
> > > Hi Chao,
> > >
> > > On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:
> > >
> > > [snip]
> > >
> > > Nice draft. :)
> > >
> > > >
> > > > Please see the draft below.
> > > >
> > > > 1) Extent management:
> > > > If we use global management that managing all extents which are from different
> > > > inodes in sbi, we will face with serious lock contention when we access these
> > > > extents belong to different inodes concurrently, the loss may outweights the
> > > > gain.
> > >
> > > Agreed.
> > >
> > > > So we choose a local management for extent which means all extents are
> > > > managed by inode itself to avoid above lock contention. Addtionlly, we manage
> > > > all extents globally by linking all inode into a global lru list for extent
> > > > cache shrinker.
> > > > Approach:
> > > > 	a) build extent tree/rwlock/lru list/extent count in each inode.
> > > > 		*extent tree: link all extent in rb-tree;
> > > > 		*rwlock: protect fields when accessing extent cache concurrently;
> > > > 		*lru list: sort all extents in accessing time order;
> > > > 		*extent count: record total count of extents in cache.
> > > > 	b) use lru shrink list in sbi to manage all inode which cached extents.
> > > > 		*inode will be added or repostioned in this global list whenever
> > > > 		extent is being access in this inode.
> > > > 		*use spinlock to protect this shrink list.
> > >
> > > 1. How about adding a data structure with inode number instead of referring
> > > inode pointer?
> > >
> > > 2. How about managing extent entries globally and setting an upper bound to
> > > the number of extent entries instead of limiting them per each inode?
> > > (The rb-tree will handle many extents per inode.)
> > >
> > > 3. It needs to set a minimum length for the candidate of extent cache.
> > >  (e.g., 64)
> > >
> > 
> > Agreed.
> > 
> > > So, for example,
> > > struct ino_entry_for_extents {
> > > 	inode number;
> > > 	rb_tree for extent_entry objects;
> > > 	rwlock;
> > > };
> > >
> > > struct extent_entry {
> > > 	blkaddr, len;
> > > 	list_head *;
> > > };
> > >
> > > Something like this.
> > >
> > > [A, B, C, ... are extent entry]
> > >
> > > The sbi has
> > > 1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
> > > 2. radix_tree:  ino_entry_for_extents (#10) has D, B in rb-tree
> > >               ` ino_entry_for_extents (#11) has A, C in rb-tree
> > >               ` ino_entry_for_extents (#12) has F    in rb-tree
> > >               ` ino_entry_for_extents (#13) has G, E in rb-tree
> > >
> > > In f2fs_update_extent_cache and __get_data_block for #10,
> > >   ino_entry_for_extents (#10) was founded and updated D or B.
> > >   Then, updated entries are moved to MRU.
> > >
> > > In f2fs_evict_inode for #11, A and C are moved to LRU.
> > > But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11)
> > > should be released.
> > >
> > > In f2fs_balance_fs_bg, some LRU extents are released according to the amount
> > > of consumed memory. Then, it frees any ino_entry_for_extents having no extent.
> > >
> > > IMO, we don't need to consider readahead for this, since get_data_block will
> > > be called by VFS readahead.
> > >
> > > Furthermore, we need to think about whether LRU is really best or not.
> > > IMO, the extent cache aims to improve second access speed, rather than initial
> > > cold misses. So, maybe MRU or another algorithms would be better.
> > >
> > 
> > Right. It's very comflicated to judge which is better.
> > In read or write path, extents could be made every time. At that time, we should
> > decide which extent evicts instead of new extents if we set upper bound.
> > In update, one extent could be seperated into 3. It requires 3 insertion and 1 deletion.
> > So if update happends frequently, we could give up extent management for some ranges.
> > And we need to bring ideas from vm managemnt. For example,
> > active/inactive list and second chance to promotion, or batch work for insertion/deletion
> > 
> > I thought suddenly 'Simple is best'.
> > Let's think about better ideas together.
> 
> Yeah, how about using an opposite way to the way of page cache manager?
> 
> for example:
> node page A,B,C,D is in page cache;
> extent a,b,c,d is in extent cache;
> extent a is built from page A, ..., d is built from page D.
> page cache: LRU A -> B -> C -> D MRU
> extent cache: LRU a -> b -> c -> d MRU
> 
> If we use
> 1) the same way LRU, cache pair A-a, B-b, ... may be reclaimed in the same time as OOM.
> 2) the opposite way, maybe A,B in page cache and d,c in extent cache will be reclaimed,
> but we still can hit whole cache in combination of page cache and extent cache.
> 
> So by the way '2)' we can increase the total coverage area of page cache + extent cache.

Good idea. :)
If we decide which one is better between global lru and per inode lru,
it's expected that f2fs read performance will be more improved.
I'll wait your patch.

Thanks,

> 
> > 
> > > Thanks,
> > >
> > > >
> > > > 2) Limitation:
> > > > In one inode, as we split or add extent in extent cache when read/write, extent
> > > > number will enlarge, so memory and CPU overhead will increase.
> > > > In order to control the overhead of memory and CPU, we try to set a upper bound
> > > > number to limit total extent number in each inode, This number is global
> > > > configuration which is visable to all inode. This number will be exported to
> > > > sysfs for configuring according to requirement of user. By default, designed
> > > > number is 8.
> > > >
> > 
> > Chao,
> > It's better which # of extent are controlled globally rather than limit extents
> > per inode as Jaegeuk said to reduce extent management overhead.
> 
> It's OK.
> 
> > 
> > > > 3) Shrinker:
> > > > There are two shrink paths:
> > > > 	a) one is triggered when extent count has exceed the upper bound of
> > > > 	inode's extent cache. We will try to release extent(s) from head of
> > > > 	inode's inner extent lru list until extent count is equal to upper bound.
> > > > 	This operation could be in f2fs_update_extent_cache().
> > > > 	b) the other one is triggered when memory util exceed threshold, we try
> > > > 	get inode from head of global lru list(s), and release extent(s) with
> > > > 	fixed number (by default: 64 extents) in inode one by one.
> > > > 	This operation could be in f2fs_balance_fs_bg().
> > > >
> > 
> > Let's consider to use register_shrinker which is called by vm when
> > memory pressure happens.
> 
> Great, thanks for your reminding! :-)
> 
> Thanks,
> Yu
> 
> > 
> > > > 4) Revalidation:
> > > > In ->evict(), extent cache will be released, in order to reuse extent cache
> > > > of inode when reopen for high hit ratio, a proper way is to add cached extent
> > > > tree into a hash table (could be radix tree), revalidate extent tree and recover
> > > > it to inode when reopen.
> > > > Besides, a global lru list is needed here for shrinker.
> > > >
> > > > 5) Readahead:
> > > > Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency
> > > > path. Note, ra can affect lock contention for both ->rwlock in extent cache and
> > > > ->lock of global shrink list.
> > > >