Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1575428 > unrolled thread

Re: [PATCH] f2fs: introduce nid cache

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH] f2fs: introduce nid cache Chao Yu <yuchao0@huawei.com> - 2017-02-07 08:30 +0100
    Re: [PATCH] f2fs: introduce nid cache Chao Yu <chao@kernel.org> - 2017-02-08 16:30 +0100
      Re: [PATCH] f2fs: introduce nid cache Jaegeuk Kim <jaegeuk@kernel.org> - 2017-02-09 03:30 +0100
        Re: [PATCH] f2fs: introduce nid cache Chao Yu <yuchao0@huawei.com> - 2017-02-11 07:20 +0100
          Re: [PATCH] f2fs: introduce nid cache Jaegeuk Kim <jaegeuk@kernel.org> - 2017-02-14 01:30 +0100
            Re: [PATCH] f2fs: introduce nid cache Chao Yu <yuchao0@huawei.com> - 2017-02-15 03:30 +0100

#1575428 — Re: [PATCH] f2fs: introduce nid cache

Hi Jaegeuk,

Happy Chinese New Year! :)

On 2017/1/24 12:35, Jaegeuk Kim wrote:
> Hi Chao,
> 
> On 01/22, Chao Yu wrote:
>> In scenario of intensively node allocation, free nids will be ran out
>> soon, then it needs to stop to load free nids by traversing NAT blocks,
>> in worse case, if NAT blocks does not be cached in memory, it generates
>> IOs which slows down our foreground operations.
>>
>> In order to speed up node allocation, in this patch we introduce a new
>> option named "nid cache", when turns on this option, it will load all
>> nat entries in NAT blocks when doing mount, and organize all free nids
>> in a bitmap, for any operations related to free nid, we will query and
>> set the new prebuilded bitmap instead of reading and lookuping NAT
>> blocks, so performance of node allocation can be improved.
>>
> 
> How does this affect mount time and memory consumption?

Sorry for the delay.

Let me figure out some numbers later.

> IMO, if those do not
> raise huge concerns, we would be able to consider just replacing current free
> nid list with this bitmap.

Yup, I agree with you.

Thanks,

[toc] | [next] | [standalone]

#1576649

On 2017/2/7 15:24, Chao Yu wrote:
> Hi Jaegeuk,
> 
> Happy Chinese New Year! :)
> 
> On 2017/1/24 12:35, Jaegeuk Kim wrote:
>> Hi Chao,
>>
>> On 01/22, Chao Yu wrote:
>>> In scenario of intensively node allocation, free nids will be ran out
>>> soon, then it needs to stop to load free nids by traversing NAT blocks,
>>> in worse case, if NAT blocks does not be cached in memory, it generates
>>> IOs which slows down our foreground operations.
>>>
>>> In order to speed up node allocation, in this patch we introduce a new
>>> option named "nid cache", when turns on this option, it will load all
>>> nat entries in NAT blocks when doing mount, and organize all free nids
>>> in a bitmap, for any operations related to free nid, we will query and
>>> set the new prebuilded bitmap instead of reading and lookuping NAT
>>> blocks, so performance of node allocation can be improved.
>>>
>>
>> How does this affect mount time and memory consumption?
> 
> Sorry for the delay.
> 
> Let me figure out some numbers later.

a. mount time

I choose slow device (Kingston 16GB SD card) to see how this option affect mount
time when there is not enough bandwidth in low level,

Before the test, I change readahead window size of NAT pages from FREE_NID_PAGES
* 8 to sbi->blocks_per_seg for better ra performance, so the result is:

time mount -t f2fs -o nid_cache /dev/sde /mnt/f2fs/

before:
real	0m0.204s
user	0m0.004s
sys	0m0.020s

after:
real	0m3.792s
user	0m0.000s
sys	0m0.140s

b. memory consumption

For 16GB size image, there is total 34 NAT pages, so memory footprint is:
34 / 2 * 512 * 455 / 8 = 495040 bytes = 483.4 KB

Increasing of memory footprint is liner with total user valid blocks in image,
and at most it will eat 3900 * 8 * 455 / 8 = 1774500 bytes = 1732.9 KB

Thanks,

> 
>> IMO, if those do not
>> raise huge concerns, we would be able to consider just replacing current free
>> nid list with this bitmap.
> 
> Yup, I agree with you.
> 
> Thanks,
> 

[toc] | [prev] | [next] | [standalone]

#1577267

On 02/08, Chao Yu wrote:
> On 2017/2/7 15:24, Chao Yu wrote:
> > Hi Jaegeuk,
> > 
> > Happy Chinese New Year! :)
> > 
> > On 2017/1/24 12:35, Jaegeuk Kim wrote:
> >> Hi Chao,
> >>
> >> On 01/22, Chao Yu wrote:
> >>> In scenario of intensively node allocation, free nids will be ran out
> >>> soon, then it needs to stop to load free nids by traversing NAT blocks,
> >>> in worse case, if NAT blocks does not be cached in memory, it generates
> >>> IOs which slows down our foreground operations.
> >>>
> >>> In order to speed up node allocation, in this patch we introduce a new
> >>> option named "nid cache", when turns on this option, it will load all
> >>> nat entries in NAT blocks when doing mount, and organize all free nids
> >>> in a bitmap, for any operations related to free nid, we will query and
> >>> set the new prebuilded bitmap instead of reading and lookuping NAT
> >>> blocks, so performance of node allocation can be improved.
> >>>
> >>
> >> How does this affect mount time and memory consumption?
> > 
> > Sorry for the delay.
> > 
> > Let me figure out some numbers later.
> 
> a. mount time
> 
> I choose slow device (Kingston 16GB SD card) to see how this option affect mount
> time when there is not enough bandwidth in low level,
> 
> Before the test, I change readahead window size of NAT pages from FREE_NID_PAGES
> * 8 to sbi->blocks_per_seg for better ra performance, so the result is:
> 
> time mount -t f2fs -o nid_cache /dev/sde /mnt/f2fs/
> 
> before:
> real	0m0.204s
> user	0m0.004s
> sys	0m0.020s
> 
> after:
> real	0m3.792s

Oops, we can't accept this even only for 16GB, right? :(

> user	0m0.000s
> sys	0m0.140s
> 
> b. memory consumption
> 
> For 16GB size image, there is total 34 NAT pages, so memory footprint is:
> 34 / 2 * 512 * 455 / 8 = 495040 bytes = 483.4 KB
> 
> Increasing of memory footprint is liner with total user valid blocks in image,
> and at most it will eat 3900 * 8 * 455 / 8 = 1774500 bytes = 1732.9 KB

How about adding two bitmaps for whole NAT pages and storing the bitmaps in
checkpoint pack, which needs at most two blocks additionally?

1. full-assigned NAT bitmap, where 1 means there is no free nids.
2. empty NAT bitmap, where 1 means whole there-in nids are free.

With these bitmaps, build_free_nids() can scan from 0'th NAT block by:

	if (full-assigned NAT)
		skip;
	else if (empty NAT)
		add_free_nid(all);
	else
		read NAT page and add_free_nid();

The flush_nat_entries() has to change its bitmaps accordingly.

With this approach, I expect we can reuse nids as much as possible while
getting cached NAT pages more effectively.

Thanks,

> 
> Thanks,
> 
> > 
> >> IMO, if those do not
> >> raise huge concerns, we would be able to consider just replacing current free
> >> nid list with this bitmap.
> > 
> > Yup, I agree with you.
> > 
> > Thanks,
> > 

[toc] | [prev] | [next] | [standalone]

#1578938

On 2017/2/9 9:28, Jaegeuk Kim wrote:
> On 02/08, Chao Yu wrote:
>> On 2017/2/7 15:24, Chao Yu wrote:
>>> Hi Jaegeuk,
>>>
>>> Happy Chinese New Year! :)
>>>
>>> On 2017/1/24 12:35, Jaegeuk Kim wrote:
>>>> Hi Chao,
>>>>
>>>> On 01/22, Chao Yu wrote:
>>>>> In scenario of intensively node allocation, free nids will be ran out
>>>>> soon, then it needs to stop to load free nids by traversing NAT blocks,
>>>>> in worse case, if NAT blocks does not be cached in memory, it generates
>>>>> IOs which slows down our foreground operations.
>>>>>
>>>>> In order to speed up node allocation, in this patch we introduce a new
>>>>> option named "nid cache", when turns on this option, it will load all
>>>>> nat entries in NAT blocks when doing mount, and organize all free nids
>>>>> in a bitmap, for any operations related to free nid, we will query and
>>>>> set the new prebuilded bitmap instead of reading and lookuping NAT
>>>>> blocks, so performance of node allocation can be improved.
>>>>>
>>>>
>>>> How does this affect mount time and memory consumption?
>>>
>>> Sorry for the delay.
>>>
>>> Let me figure out some numbers later.
>>
>> a. mount time
>>
>> I choose slow device (Kingston 16GB SD card) to see how this option affect mount
>> time when there is not enough bandwidth in low level,
>>
>> Before the test, I change readahead window size of NAT pages from FREE_NID_PAGES
>> * 8 to sbi->blocks_per_seg for better ra performance, so the result is:
>>
>> time mount -t f2fs -o nid_cache /dev/sde /mnt/f2fs/
>>
>> before:
>> real	0m0.204s
>> user	0m0.004s
>> sys	0m0.020s
>>
>> after:
>> real	0m3.792s
> 
> Oops, we can't accept this even only for 16GB, right? :(

Pengyang Hou help testing this patch in 64GB UFS, the result of mount time is:

Before:	110 ms
After:	770 ms

So these test results shows that we'd better not set nid_cache option by default
in upstream since anyway it slows down mount procedure obviously, but still
users can decide whether use it or not depending on their requirement. e.g.:
a. For readonly case, this option is complete no needed.
b. For in batch node allocation/deletion case, this option is recommended.

> 
>> user	0m0.000s
>> sys	0m0.140s
>>
>> b. memory consumption
>>
>> For 16GB size image, there is total 34 NAT pages, so memory footprint is:
>> 34 / 2 * 512 * 455 / 8 = 495040 bytes = 483.4 KB
>>
>> Increasing of memory footprint is liner with total user valid blocks in image,
>> and at most it will eat 3900 * 8 * 455 / 8 = 1774500 bytes = 1732.9 KB
> 
> How about adding two bitmaps for whole NAT pages and storing the bitmaps in
> checkpoint pack, which needs at most two blocks additionally?
> 
> 1. full-assigned NAT bitmap, where 1 means there is no free nids.
> 2. empty NAT bitmap, where 1 means whole there-in nids are free.
> 
> With these bitmaps, build_free_nids() can scan from 0'th NAT block by:
> 
> 	if (full-assigned NAT)
> 		skip;
> 	else if (empty NAT)
> 		add_free_nid(all);
> 	else
> 		read NAT page and add_free_nid();
> 
> The flush_nat_entries() has to change its bitmaps accordingly.
> 
> With this approach, I expect we can reuse nids as much as possible while
> getting cached NAT pages more effectively.

Good idea! :)

And there is another approach which do not need to change disk layout is:

We can allocate free_nid_bitmap[NAT_BLOCKS_COUNT][455] array, each bitmap
indicates usage of free nids in one NAT block, and we introduce another
nat_block_bitmap[NAT_BLOCKS_COUNT] to indicate each NAT block is loaded or not,
if it is loaded and we can do lookup in free_nid_bitmap correspondingly. So I
expect that we will load one NAT block from disk one time at most, it will:
- not increase mount latency
- after loading NAT blocks from disk, we will build its bitmap inside memory to
reduce lookup time for second time

Thoughts? Which one is preferred?

Thanks,

> 
> Thanks,
> 
>>
>> Thanks,
>>
>>>
>>>> IMO, if those do not
>>>> raise huge concerns, we would be able to consider just replacing current free
>>>> nid list with this bitmap.
>>>
>>> Yup, I agree with you.
>>>
>>> Thanks,
>>>
> 
> .
> 

[toc] | [prev] | [next] | [standalone]

#1580164

On 02/11, Chao Yu wrote:
> On 2017/2/9 9:28, Jaegeuk Kim wrote:
> > On 02/08, Chao Yu wrote:
> >> On 2017/2/7 15:24, Chao Yu wrote:
> >>> Hi Jaegeuk,
> >>>
> >>> Happy Chinese New Year! :)
> >>>
> >>> On 2017/1/24 12:35, Jaegeuk Kim wrote:
> >>>> Hi Chao,
> >>>>
> >>>> On 01/22, Chao Yu wrote:
> >>>>> In scenario of intensively node allocation, free nids will be ran out
> >>>>> soon, then it needs to stop to load free nids by traversing NAT blocks,
> >>>>> in worse case, if NAT blocks does not be cached in memory, it generates
> >>>>> IOs which slows down our foreground operations.
> >>>>>
> >>>>> In order to speed up node allocation, in this patch we introduce a new
> >>>>> option named "nid cache", when turns on this option, it will load all
> >>>>> nat entries in NAT blocks when doing mount, and organize all free nids
> >>>>> in a bitmap, for any operations related to free nid, we will query and
> >>>>> set the new prebuilded bitmap instead of reading and lookuping NAT
> >>>>> blocks, so performance of node allocation can be improved.
> >>>>>
> >>>>
> >>>> How does this affect mount time and memory consumption?
> >>>
> >>> Sorry for the delay.
> >>>
> >>> Let me figure out some numbers later.
> >>
> >> a. mount time
> >>
> >> I choose slow device (Kingston 16GB SD card) to see how this option affect mount
> >> time when there is not enough bandwidth in low level,
> >>
> >> Before the test, I change readahead window size of NAT pages from FREE_NID_PAGES
> >> * 8 to sbi->blocks_per_seg for better ra performance, so the result is:
> >>
> >> time mount -t f2fs -o nid_cache /dev/sde /mnt/f2fs/
> >>
> >> before:
> >> real	0m0.204s
> >> user	0m0.004s
> >> sys	0m0.020s
> >>
> >> after:
> >> real	0m3.792s
> > 
> > Oops, we can't accept this even only for 16GB, right? :(
> 
> Pengyang Hou help testing this patch in 64GB UFS, the result of mount time is:
> 
> Before:	110 ms
> After:	770 ms
> 
> So these test results shows that we'd better not set nid_cache option by default
> in upstream since anyway it slows down mount procedure obviously, but still
> users can decide whether use it or not depending on their requirement. e.g.:
> a. For readonly case, this option is complete no needed.
> b. For in batch node allocation/deletion case, this option is recommended.
> 
> > 
> >> user	0m0.000s
> >> sys	0m0.140s
> >>
> >> b. memory consumption
> >>
> >> For 16GB size image, there is total 34 NAT pages, so memory footprint is:
> >> 34 / 2 * 512 * 455 / 8 = 495040 bytes = 483.4 KB
> >>
> >> Increasing of memory footprint is liner with total user valid blocks in image,
> >> and at most it will eat 3900 * 8 * 455 / 8 = 1774500 bytes = 1732.9 KB
> > 
> > How about adding two bitmaps for whole NAT pages and storing the bitmaps in
> > checkpoint pack, which needs at most two blocks additionally?
> > 
> > 1. full-assigned NAT bitmap, where 1 means there is no free nids.
> > 2. empty NAT bitmap, where 1 means whole there-in nids are free.
> > 
> > With these bitmaps, build_free_nids() can scan from 0'th NAT block by:
> > 
> > 	if (full-assigned NAT)
> > 		skip;
> > 	else if (empty NAT)
> > 		add_free_nid(all);
> > 	else
> > 		read NAT page and add_free_nid();
> > 
> > The flush_nat_entries() has to change its bitmaps accordingly.
> > 
> > With this approach, I expect we can reuse nids as much as possible while
> > getting cached NAT pages more effectively.
> 
> Good idea! :)
> 
> And there is another approach which do not need to change disk layout is:
> 
> We can allocate free_nid_bitmap[NAT_BLOCKS_COUNT][455] array, each bitmap
> indicates usage of free nids in one NAT block, and we introduce another
> nat_block_bitmap[NAT_BLOCKS_COUNT] to indicate each NAT block is loaded or not,
> if it is loaded and we can do lookup in free_nid_bitmap correspondingly. So I
> expect that we will load one NAT block from disk one time at most, it will:
> - not increase mount latency
> - after loading NAT blocks from disk, we will build its bitmap inside memory to
> reduce lookup time for second time

Yup, I think both of them are doable together. Meanwhile, I've written patches
which support the bitmaps for NAT pages and started to test them. Could you
write a patch to introduce free_nid_bitmap[][] as well?

Thanks,

> 
> Thoughts? Which one is preferred?
> 
> Thanks,
> 
> > 
> > Thanks,
> > 
> >>
> >> Thanks,
> >>
> >>>
> >>>> IMO, if those do not
> >>>> raise huge concerns, we would be able to consider just replacing current free
> >>>> nid list with this bitmap.
> >>>
> >>> Yup, I agree with you.
> >>>
> >>> Thanks,
> >>>
> > 
> > .
> > 

[toc] | [prev] | [next] | [standalone]

#1581007

On 2017/2/14 8:25, Jaegeuk Kim wrote:
> On 02/11, Chao Yu wrote:
>> On 2017/2/9 9:28, Jaegeuk Kim wrote:
>>> On 02/08, Chao Yu wrote:
>>>> On 2017/2/7 15:24, Chao Yu wrote:
>>>>> Hi Jaegeuk,
>>>>>
>>>>> Happy Chinese New Year! :)
>>>>>
>>>>> On 2017/1/24 12:35, Jaegeuk Kim wrote:
>>>>>> Hi Chao,
>>>>>>
>>>>>> On 01/22, Chao Yu wrote:
>>>>>>> In scenario of intensively node allocation, free nids will be ran out
>>>>>>> soon, then it needs to stop to load free nids by traversing NAT blocks,
>>>>>>> in worse case, if NAT blocks does not be cached in memory, it generates
>>>>>>> IOs which slows down our foreground operations.
>>>>>>>
>>>>>>> In order to speed up node allocation, in this patch we introduce a new
>>>>>>> option named "nid cache", when turns on this option, it will load all
>>>>>>> nat entries in NAT blocks when doing mount, and organize all free nids
>>>>>>> in a bitmap, for any operations related to free nid, we will query and
>>>>>>> set the new prebuilded bitmap instead of reading and lookuping NAT
>>>>>>> blocks, so performance of node allocation can be improved.
>>>>>>>
>>>>>>
>>>>>> How does this affect mount time and memory consumption?
>>>>>
>>>>> Sorry for the delay.
>>>>>
>>>>> Let me figure out some numbers later.
>>>>
>>>> a. mount time
>>>>
>>>> I choose slow device (Kingston 16GB SD card) to see how this option affect mount
>>>> time when there is not enough bandwidth in low level,
>>>>
>>>> Before the test, I change readahead window size of NAT pages from FREE_NID_PAGES
>>>> * 8 to sbi->blocks_per_seg for better ra performance, so the result is:
>>>>
>>>> time mount -t f2fs -o nid_cache /dev/sde /mnt/f2fs/
>>>>
>>>> before:
>>>> real	0m0.204s
>>>> user	0m0.004s
>>>> sys	0m0.020s
>>>>
>>>> after:
>>>> real	0m3.792s
>>>
>>> Oops, we can't accept this even only for 16GB, right? :(
>>
>> Pengyang Hou help testing this patch in 64GB UFS, the result of mount time is:
>>
>> Before:	110 ms
>> After:	770 ms
>>
>> So these test results shows that we'd better not set nid_cache option by default
>> in upstream since anyway it slows down mount procedure obviously, but still
>> users can decide whether use it or not depending on their requirement. e.g.:
>> a. For readonly case, this option is complete no needed.
>> b. For in batch node allocation/deletion case, this option is recommended.
>>
>>>
>>>> user	0m0.000s
>>>> sys	0m0.140s
>>>>
>>>> b. memory consumption
>>>>
>>>> For 16GB size image, there is total 34 NAT pages, so memory footprint is:
>>>> 34 / 2 * 512 * 455 / 8 = 495040 bytes = 483.4 KB
>>>>
>>>> Increasing of memory footprint is liner with total user valid blocks in image,
>>>> and at most it will eat 3900 * 8 * 455 / 8 = 1774500 bytes = 1732.9 KB
>>>
>>> How about adding two bitmaps for whole NAT pages and storing the bitmaps in
>>> checkpoint pack, which needs at most two blocks additionally?
>>>
>>> 1. full-assigned NAT bitmap, where 1 means there is no free nids.
>>> 2. empty NAT bitmap, where 1 means whole there-in nids are free.
>>>
>>> With these bitmaps, build_free_nids() can scan from 0'th NAT block by:
>>>
>>> 	if (full-assigned NAT)
>>> 		skip;
>>> 	else if (empty NAT)
>>> 		add_free_nid(all);
>>> 	else
>>> 		read NAT page and add_free_nid();
>>>
>>> The flush_nat_entries() has to change its bitmaps accordingly.
>>>
>>> With this approach, I expect we can reuse nids as much as possible while
>>> getting cached NAT pages more effectively.
>>
>> Good idea! :)
>>
>> And there is another approach which do not need to change disk layout is:
>>
>> We can allocate free_nid_bitmap[NAT_BLOCKS_COUNT][455] array, each bitmap
>> indicates usage of free nids in one NAT block, and we introduce another
>> nat_block_bitmap[NAT_BLOCKS_COUNT] to indicate each NAT block is loaded or not,
>> if it is loaded and we can do lookup in free_nid_bitmap correspondingly. So I
>> expect that we will load one NAT block from disk one time at most, it will:
>> - not increase mount latency
>> - after loading NAT blocks from disk, we will build its bitmap inside memory to
>> reduce lookup time for second time
> 
> Yup, I think both of them are doable together. Meanwhile, I've written patches
> which support the bitmaps for NAT pages and started to test them. Could you
> write a patch to introduce free_nid_bitmap[][] as well?

No problem. :)

Thanks,

> 
> Thanks,
> 
>>
>> Thoughts? Which one is preferred?
>>
>> Thanks,
>>
>>>
>>> Thanks,
>>>
>>>>
>>>> Thanks,
>>>>
>>>>>
>>>>>> IMO, if those do not
>>>>>> raise huge concerns, we would be able to consider just replacing current free
>>>>>> nid list with this bitmap.
>>>>>
>>>>> Yup, I agree with you.
>>>>>
>>>>> Thanks,
>>>>>
>>>
>>> .
>>>
> 
> .
> 

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web