RFC: Removal of hash table for Linear RAID

RFC: Removal of hash table for Linear RAID

[SandeepKsinha]

Hi all,

I suggest the removal of the hashing table and various other members
associated with it from the struct linear_private_data, which are used
majorly for faster searching of devices.

struct linear_private_data
  {
          struct linear_private_data *prev;       /* earlier version */
-          dev_info_t              **hash_table;
-          sector_t                spacing;
          sector_t                array_sectors;
-          int                     sector_shift;   /* shift before dividing
-                                                  * by spacing
-                                                   */
          dev_info_t              disks[0];
  };



The reason for the same being that use of sector_div, spacing and
sector_shift involves lots of computations, which can be easily
avoided and we can achieve the same in a simpler way.

Also, in an environment where we hold a restriction to have a maximum
of 27 devices. I believe that a linear search would be faster or
atleast equal in time, if you take into consider the (time taken for
computations + search) while using the hash table as well.

Other than making the code simpler, IMO, this should also help shrink
the struct linear_private_data which might further help caching as
well.

Another enhancement to this can be to add a new member "nr_devices" (
number of devices ) to struct linear_private_data and use the same to
perform a binary search for the lokkup, as we know the sectors would
always be increasing as per we move ahead with devices.

Something like,

struct linear_private_data
  {
          struct linear_private_data *prev;       /* earlier version */
          sector_t                array_sectors;
          int                        nr_devices;
          dev_info_t              disks[0];
  };


And accordingly, which_dev( ) can use the same to make the search
faster and better.


Comments/suggestions please.

-- 
Regards,
Sandeep.





 	
“To learn is to change. Education is a process that changes the learner.”
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: RFC: Removal of hash table for Linear RAID

[Neil Brown]

On Sunday May 17, sandeepksinha@gmail.com wrote:
> Hi all,
> 
> I suggest the removal of the hashing table and various other members
> associated with it from the struct linear_private_data, which are used
> majorly for faster searching of devices.
> 
> struct linear_private_data
>   {
>           struct linear_private_data *prev;       /* earlier version */
> -          dev_info_t              **hash_table;
> -          sector_t                spacing;
>           sector_t                array_sectors;
> -          int                     sector_shift;   /* shift before dividing
> -                                                  * by spacing
> -                                                   */
>           dev_info_t              disks[0];
>   };
> 

I'm in two minds about this...

One the one hand, the simplification is good, just like it was for
raid0.

However the argument that we used for raid0 does not apply exactly to
linear.

For raid0, we observed that the list we would need to search would
never be longer than the number of devices, and would usually be
shorter, often just one entry (when all devices are the same size).
Optimising for an array with lots of different sized drives didn't
seem to be sensible.

However with linear, the list that needs to be searched is always
exactly the same length as the number of devices, even if they are all
the same size.

So I feel that I would still like something the accelerate the search
a bit.
Some options that have occur to me are:
  - do a binary search.  I have read that this can be slower than a
     linear search for very short lists, but if the code turns out to
     be really really simple, that might be a good option.
  - fixed size hash table with power-of-2 spacing.  It might be that
     lots of the current complexity can disappear if we just make the
     table a bit simpler - choose a size that allows shifts instead of
     divides, or something like that.

> 
> 
> The reason for the same being that use of sector_div, spacing and
> sector_shift involves lots of computations, which can be easily
> avoided and we can achieve the same in a simpler way.
> 
> Also, in an environment where we hold a restriction to have a maximum
> of 27 devices. I believe that a linear search would be faster or
> atleast equal in time, if you take into consider the (time taken for
> computations + search) while using the hash table as well.

The limit of 27 devices per array only applies with v0.90 metadata
with v1.x, you can have many more, certainly hundreds.  Whether anyone
would want to is a separate question.

> 
> Other than making the code simpler, IMO, this should also help shrink
> the struct linear_private_data which might further help caching as
> well.

It is really the data structures which a duplicated as in an array
that benefit from shrinking.  So making dev_info smaller might help.
Making linear_private_data smaller isn't likely to make an important
difference.
The important thing is keeping related data close together.  By
shrinking the members of an array, we bring the start and end closer
together, which is a good thing.

Removing num_sectors from dev_info would be a good idea.

> 
> Another enhancement to this can be to add a new member "nr_devices" (
> number of devices ) to struct linear_private_data and use the same to
> perform a binary search for the lokkup, as we know the sectors would
> always be increasing as per we move ahead with devices.
> 
> Something like,
> 
> struct linear_private_data
>   {
>           struct linear_private_data *prev;       /* earlier version */
>           sector_t                array_sectors;
>           int                        nr_devices;
>           dev_info_t              disks[0];
>   };
> 
> 
> And accordingly, which_dev( ) can use the same to make the search
> faster and better.

Yes, that is certainly worth a try.

NeilBrown

Re: RFC: Removal of hash table for Linear RAID

[SandeepKsinha]

Hi Neil,

On Sun, May 17, 2009 at 12:37 PM, Neil Brown <neilb@suse.de> wrote:
> On Sunday May 17, sandeepksinha@gmail.com wrote:
>> Hi all,
>>
>> I suggest the removal of the hashing table and various other members
>> associated with it from the struct linear_private_data, which are used
>> majorly for faster searching of devices.
>>
>> struct linear_private_data
>>   {
>>           struct linear_private_data *prev;       /* earlier version */
>> -          dev_info_t              **hash_table;
>> -          sector_t                spacing;
>>           sector_t                array_sectors;
>> -          int                     sector_shift;   /* shift before dividing
>> -                                                  * by spacing
>> -                                                   */
>>           dev_info_t              disks[0];
>>   };
>>
>
> I'm in two minds about this...
>
> One the one hand, the simplification is good, just like it was for
> raid0.
>
> However the argument that we used for raid0 does not apply exactly to
> linear.
>
> For raid0, we observed that the list we would need to search would
> never be longer than the number of devices, and would usually be
> shorter, often just one entry (when all devices are the same size).
> Optimising for an array with lots of different sized drives didn't
> seem to be sensible.
>
> However with linear, the list that needs to be searched is always
> exactly the same length as the number of devices, even if they are all
> the same size.
>
> So I feel that I would still like something the accelerate the search
> a bit.
> Some options that have occur to me are:
>  - do a binary search.  I have read that this can be slower than a
>     linear search for very short lists, but if the code turns out to
>     be really really simple, that might be a good option.

In my opinion I think this would be simpler and much faster in most of
the cases.
It might be slower for some on the cases as you mentioned but those
will be rare.
Also, looking at the aspects of linear raid, I have seen potential
users having linear raid aggregates with large number of disks,
mostly.

However, as far as the code simplicity is concerned, it surely be. I
will try to send the diff once I am done with the initial testing of
it.

>  - fixed size hash table with power-of-2 spacing.  It might be that
>     lots of the current complexity can disappear if we just make the
>     table a bit simpler - choose a size that allows shifts instead of
>     divides, or something like that.
>

If I am getting you right, a fixed sized table would again put some
kind of limitations. Someway or the other.
Also, choosing a size may be easy and be optimal for one but will that
be optimal for both equal and non-equal sized disks.
So, I would suggest to go with the binary search method.


If you don't mind, can you elaborate a bit more on what exactly you
are suggesting?


.
>>
>>
>> The reason for the same being that use of sector_div, spacing and
>> sector_shift involves lots of computations, which can be easily
>> avoided and we can achieve the same in a simpler way.
>>
>> Also, in an environment where we hold a restriction to have a maximum
>> of 27 devices. I believe that a linear search would be faster or
>> atleast equal in time, if you take into consider the (time taken for
>> computations + search) while using the hash table as well.
>
> The limit of 27 devices per array only applies with v0.90 metadata
> with v1.x, you can have many more, certainly hundreds.  Whether anyone
> would want to is a separate question.
>

Thanks I wasn't aware of this.

>>
>> Other than making the code simpler, IMO, this should also help shrink
>> the struct linear_private_data which might further help caching as
>> well.
>
> It is really the data structures which a duplicated as in an array
> that benefit from shrinking.  So making dev_info smaller might help.
> Making linear_private_data smaller isn't likely to make an important
> difference.
> The important thing is keeping related data close together.  By
> shrinking the members of an array, we bring the start and end closer
> together, which is a good thing.
>
> Removing num_sectors from dev_info would be a good idea.
>

Yes, we can certainly do that and replace num_sectors uses with
conf->rdev->sectors.
num_sectors actually is redundant as we already keep this information in rdev.

Is this assumption right?

>>
>> Another enhancement to this can be to add a new member "nr_devices" (
>> number of devices ) to struct linear_private_data and use the same to
>> perform a binary search for the lokkup, as we know the sectors would
>> always be increasing as per we move ahead with devices.
>>
>> Something like,
>>
>> struct linear_private_data
>>   {
>>           struct linear_private_data *prev;       /* earlier version */
>>           sector_t                array_sectors;
>>           int                        nr_devices;
>>           dev_info_t              disks[0];
>>   };
>>
>>
>> And accordingly, which_dev( ) can use the same to make the search
>> faster and better.
>
> Yes, that is certainly worth a try.
>

Also, after thinking more on this, I feel we already have
mdded->raid_disks, which will be equal to the number of devices on the
linear array.
So, do you still suggest adding something like nr_devices.

As of now, this would only be required in which_dev( ), if we go with
binary search. One instance.
Can we not make use of mddev->raid_disks for this particular instance?

> NeilBrown
> --
> To unsubscribe from this list: send the line "unsubscribe linux-raid" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

-- 
Regards,
Sandeep.





 	
“To learn is to change. Education is a process that changes the learner.”
--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html