Re: [RFC] Tree fragmentation and prefetching

[Arne Jansen <sensille@gmx.net>]

On 24.03.2011 02:38, Miao Xie wrote:
> On wed, 23 Mar 2011 21:28:25 +0100, Arne Jansen wrote:
>> On 23.03.2011 20:26, Andrey Kuzmin wrote:
>>> On Wed, Mar 23, 2011 at 4:06 PM, Arne Jansen<sensille@gmx.net>  wrote:
>>>> The main idea is to load the tree (or parts of it) top-down, order the
>>>> needed blocks and distribute it over all disks.
>>>> To keep you interested, some results first.
>>>>
>>>> a) by tree enumeration with reada=2
>>>>    reading extent tree: 242s
>>>>    reading csum tree: 140s
>>>>    reading both trees: 324s
>>>>
>>>> b) prefetch prototype
>>>>    reading extent tree: 23.5s
>>>>    reading csum tree: 20.4s
>>>>    reading both trees: 25.7s
>>>
>>> 10x speed-up looks indeed impressive. Just for me to be sure, did I
>>> get you right in that you attribute this effect specifically to
>>> enumerating tree leaves in key address vs. disk addresses when these
>>> two are not aligned?
>>
>> Yes. Leaves and the intermediate nodes tend to be quite scattered
>> around the disk with respect to their logical order.
>> Reading them in logical (ascending/descending) order require lots
>> of seeks.
> 
> I'm also dealing with tree fragmentation problem, I try to store the leaves
> which have the same parent closely.

That's good to hear. Do you have already anything I can repeat the test
with?

-Arne

> 
> Regards
> Miao
>