Delayed Extent Tree and Extent Lock Tree

Delayed Extent Tree and Extent Lock Tree

[Allison Henderson]

Hi Yongqiang,

I've have been working on an extent lock implementation that uses an 
rbtree to keep track of locked extents, and I think I will probably end 
up with a something similar to the tree that you've already set up for 
delayed extents.  So I wanted to send a note out to see what folks would 
think about the idea of merging the two solutions.

If we did this, the tree would get a little more complex in that it 
would have to keep track of more than just delayed extents. It would 
have to keep track of all extents and the processes that are waiting on 
them.  So I guess it would kind of turn into an extent status tree.  I 
also realize that some folks wanted to see range locks go into /lib as 
general purpose code so that other filesystems or kernel code could use 
it too, but the advantage to this approach would be one less tree for 
ext4 to keep track of.  Any thoughts?

Allison Henderson

Re: Delayed Extent Tree and Extent Lock Tree

[Tao Ma]

Hi Allison,
On 02/01/2012 06:33 AM, Allison Henderson wrote:
> Hi Yongqiang,
> 
> I've have been working on an extent lock implementation that uses an
> rbtree to keep track of locked extents, and I think I will probably end
> up with a something similar to the tree that you've already set up for
> delayed extents.  So I wanted to send a note out to see what folks would
> think about the idea of merging the two solutions.
> 
> If we did this, the tree would get a little more complex in that it
> would have to keep track of more than just delayed extents. It would
> have to keep track of all extents and the processes that are waiting on
> them.  So I guess it would kind of turn into an extent status tree.  I
> also realize that some folks wanted to see range locks go into /lib as
> general purpose code so that other filesystems or kernel code could use
> it too, but the advantage to this approach would be one less tree for
> ext4 to keep track of.  Any thoughts?
We (Taobao) are very interested in this stuff and it should benefit
several of our workload(It is on our todo list for a long time). I guess
Yongqiang's solution is a little bit limited to the only delayed extent
case, and your new solution at least has 2 more benefits:
1. improve the direct i/o read/write
2. speed up the extent search since now we only cache one in
ei_cached_extent.

So please go ahead with your new solution. btw, do you have any timeline
for it? We are glad to provide any help if needed.

Thanks
Tao

Re: Delayed Extent Tree and Extent Lock Tree

[Andreas Dilger]

On 2012-02-01, at 12:26 AM, Tao Ma wrote:
> On 02/01/2012 06:33 AM, Allison Henderson wrote:
>> Hi Yongqiang,
>> 
>> I've have been working on an extent lock implementation that uses an
>> rbtree to keep track of locked extents, and I think I will probably end
>> up with a something similar to the tree that you've already set up for
>> delayed extents.  So I wanted to send a note out to see what folks would
>> think about the idea of merging the two solutions.
>> 
>> If we did this, the tree would get a little more complex in that it
>> would have to keep track of more than just delayed extents. It would
>> have to keep track of all extents and the processes that are waiting on
>> them.  So I guess it would kind of turn into an extent status tree.  I
>> also realize that some folks wanted to see range locks go into /lib as
>> general purpose code so that other filesystems or kernel code could use
>> it too, but the advantage to this approach would be one less tree for
>> ext4 to keep track of.  Any thoughts?
> 
> We (Taobao) are very interested in this stuff and it should benefit
> several of our workload(It is on our todo list for a long time). I guess
> Yongqiang's solution is a little bit limited to the only delayed extent
> case, and your new solution at least has 2 more benefits:
> 1. improve the direct i/o read/write
> 2. speed up the extent search since now we only cache one in
> ei_cached_extent.

Another related usage is to use a tree to track free extents in the
block allocation bitmaps.  We already have a thread starting at mount
time to do itable_init, and it would be possible to have that same
thread read block bitmaps from disk and generate a free extents tree.

That would allow much faster extent allocation without changing the
on-disk format.

Cheers, Andreas

Re: Delayed Extent Tree and Extent Lock Tree

[Allison Henderson]

On 02/01/2012 12:26 AM, Tao Ma wrote:
> Hi Allison,
> On 02/01/2012 06:33 AM, Allison Henderson wrote:
>> Hi Yongqiang,
>>
>> I've have been working on an extent lock implementation that uses an
>> rbtree to keep track of locked extents, and I think I will probably end
>> up with a something similar to the tree that you've already set up for
>> delayed extents.  So I wanted to send a note out to see what folks would
>> think about the idea of merging the two solutions.
>>
>> If we did this, the tree would get a little more complex in that it
>> would have to keep track of more than just delayed extents. It would
>> have to keep track of all extents and the processes that are waiting on
>> them.  So I guess it would kind of turn into an extent status tree.  I
>> also realize that some folks wanted to see range locks go into /lib as
>> general purpose code so that other filesystems or kernel code could use
>> it too, but the advantage to this approach would be one less tree for
>> ext4 to keep track of.  Any thoughts?
> We (Taobao) are very interested in this stuff and it should benefit
> several of our workload(It is on our todo list for a long time). I guess
> Yongqiang's solution is a little bit limited to the only delayed extent
> case, and your new solution at least has 2 more benefits:
> 1. improve the direct i/o read/write
> 2. speed up the extent search since now we only cache one in
> ei_cached_extent.
>
> So please go ahead with your new solution. btw, do you have any timeline
> for it? We are glad to provide any help if needed.
>
> Thanks
> Tao
>

Thx all for the feed back, it sounds like there will be a lot of 
benefits to extending Yongqiang's delayed extent tree, so I will work on 
a solution based on that patch set.  Unfortunately though, I cannot give 
a time frame for this work item at the moment.  There are currently some 
other business needs that may take priority over this one, and until 
those have been decided, I cannot make any promises at this point in 
time.  But I will work as quickly as I can with it since it is currently 
on my plate, and I will keep folks updated.  At the moment, feed back 
and guidance is most helpful to me.  Also, since the delayed extent 
solution is now a dependency for my solution, anything to help get that 
reviewed and merged would help me too.  Yongqiang, does the set still 
need review?  I think I recall Ted saying it was still on his list of 
things to look at.  Im sure I will give it some good exercise here too. 
  Thx all for your help!  :)

Allison Henderson

Re: Delayed Extent Tree and Extent Lock Tree

[Yongqiang Yang]

On Thu, Feb 2, 2012 at 6:04 AM, Allison Henderson
<achender@linux.vnet.ibm.com> wrote:
> On 02/01/2012 12:26 AM, Tao Ma wrote:
>>
>> Hi Allison,
>> On 02/01/2012 06:33 AM, Allison Henderson wrote:
>>>
>>> Hi Yongqiang,
>>>
>>> I've have been working on an extent lock implementation that uses an
>>> rbtree to keep track of locked extents, and I think I will probably end
>>> up with a something similar to the tree that you've already set up for
>>> delayed extents.  So I wanted to send a note out to see what folks would
>>> think about the idea of merging the two solutions.
>>>
>>> If we did this, the tree would get a little more complex in that it
>>> would have to keep track of more than just delayed extents. It would
>>> have to keep track of all extents and the processes that are waiting on
>>> them.  So I guess it would kind of turn into an extent status tree.  I
>>> also realize that some folks wanted to see range locks go into /lib as
>>> general purpose code so that other filesystems or kernel code could use
>>> it too, but the advantage to this approach would be one less tree for
>>> ext4 to keep track of.  Any thoughts?
>>
>> We (Taobao) are very interested in this stuff and it should benefit
>> several of our workload(It is on our todo list for a long time). I guess
>> Yongqiang's solution is a little bit limited to the only delayed extent
>> case, and your new solution at least has 2 more benefits:
>> 1. improve the direct i/o read/write
>> 2. speed up the extent search since now we only cache one in
>> ei_cached_extent.
>>
>> So please go ahead with your new solution. btw, do you have any timeline
>> for it? We are glad to provide any help if needed.
>>
>> Thanks
>> Tao
>>
>
> Thx all for the feed back, it sounds like there will be a lot of benefits to
> extending Yongqiang's delayed extent tree, so I will work on a solution
> based on that patch set.  Unfortunately though, I cannot give a time frame
> for this work item at the moment.  There are currently some other business
> needs that may take priority over this one, and until those have been
> decided, I cannot make any promises at this point in time.  But I will work
> as quickly as I can with it since it is currently on my plate, and I will
> keep folks updated.  At the moment, feed back and guidance is most helpful
> to me.  Also, since the delayed extent solution is now a dependency for my
> solution, anything to help get that reviewed and merged would help me too.
>  Yongqiang, does the set still need review?  I think I recall Ted saying it
It passed xfstests last year and I think you can go ahead on the set.
 It seems that your changes are a lot, so maybe we can merge the whole
set until your work is done.  At least, your work and the merging work
can be undertaken concurrently.

If you need any help,  I am available.

Yongqiang.
> was still on his list of things to look at.  Im sure I will give it some
> good exercise here too.  Thx all for your help!  :)
>
> Allison Henderson
>



-- 
Best Wishes
Yongqiang Yang
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html