Optimise logic to add BDs to a RaidGroup in a CSPC to maximise successful pool provisions

[vharsh]

As of now, the minimum number of Blockdevices get added into a single RAIDgroup.

TODO: ~Consider storage sizes for creating a pool~.

Implementation to minimize disk losses

• For stripe, there can be only one Raid-Group(in a CSPI) where all the disks exist and they can be of any sizes
• For Mirror, RaidZ, RaidZ2 the BD sizes must be the same in a single CSPI.RaidGroup( same size exact to the number of bytes, one byte off and the CSPC will not provision because of a ZFS error)

How the BD selection works for non-stripe pools?

Tl; dr summary

1. Filter BDs by minimumSize, Unclaimed+Active states
2. Sort them by increasing order of size
3. Assume, minimum device-level replication for mirror, raidZ, Raidz2(i.e. they'll always have 2, 3 and 6 devices per-RAIDgroup)
4. Select disks from the list^ of disks available in the node

Step-4 in detail

1. Have a sorted slice of BDs

2. Convert the slice of BDs into a singly-linked-list

3. Run a two-pointer algorithm similar to Sliding Window, the first pointer(i.e. curr) will point to the start of the window and the second pointer(i.e. ahead) will point to the end of the window, including both the boundaries, they'd always have 1, 2, 3, 6 boxes in their bounds.

4. If the sizes of the BD pointed by the curr BD and the ahead BD are same, we can confirm that the n elements between them are of the same size, where n ∀ n ∈ {0, 1, 2..} NOTE: If the curr & ahead point to the same BD node, the single BD is selected

5. We can get rid of those BD nodes by keeping track of the prev pointer to the BD pointed to by the curr BD

   • the edge cases around selection of the first BD is handled by prefixing a dummy useless node in the Select(...) method which is never shared with the caller in any of the edge cases

6. If a chosen minimum number of same sized BDs aren't found between the two pointers, we can confirm that a specific node doesn't have enough BDs for that RaidGroup in a particular pool-instance and promptly throw an error

Future possible enhancements

• Add a feature flag for omitting HDDs, sparse-files, selecting only HDDs, etc by just modifying filterCStorCompatibleBDs function
• Add some automatically fuzz-ed unit tests to further harden the logic

Co-Authored-by: Sai Chaithanya (@mittachaitu) sai.chaithanya@mayadata.io Signed-off-by: Harsh Vardhan (@vharsh) harsh.vardhan@mayadata.io

[codecov-commenter]

Codecov Report

Merging #136 (acc1801) into develop (c55d1b6) will increase coverage by 1.61%. The diff coverage is 85.27%.

@@             Coverage Diff             @@
##           develop     #136      +/-   ##
===========================================
+ Coverage    68.35%   69.96%   +1.61%     
===========================================
  Files           25       26       +1     
  Lines         2051     2151     +100     
===========================================
+ Hits          1402     1505     +103     
+ Misses         634      630       -4     
- Partials        15       16       +1     

Impacted Files	Coverage Δ
pkg/generate/cspc.go	80.93% <73.23%> (+6.36%)	:arrow_up:
pkg/generate/sort.go	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update c55d1b6...acc1801. Read the comment docs.

[vharsh]

Makes sense, I’ll have to change how unit tests check them internally, but this seems doable.

On Fri, 24 Dec 2021 at 1:17 PM, sai chaithanya @.***> wrote:

@.**** approved this pull request.

LGTM

In pkg/generate/sort.go https://github.com/openebs/openebsctl/pull/136#discussion_r774914482:

@@ -0,0 +1,86 @@ +package generate + +import (

• "fmt"
• "github.com/openebs/api/v2/pkg/apis/openebs.io/v1alpha1"
• "k8s.io/apimachinery/pkg/api/resource" +)

• +// DeviceList is a LinkedList of BlockDevices +type DeviceList struct {

• item v1alpha1.BlockDevice

nit: If we made it as pointer copying of things will be reduced to great extent as compared to struct copy

— Reply to this email directly, view it on GitHub https://github.com/openebs/openebsctl/pull/136#pullrequestreview-839789164, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACG7P4XKZYHES6UYJTURNB3USQQQ5ANCNFSM5JEF3M7Q . You are receiving this because you were mentioned.Message ID: @.***>

[mittachaitu]

Makes sense, I’ll have to change how unit tests check them internally, but this seems doable. … On Fri, 24 Dec 2021 at 1:17 PM, sai chaithanya @.> wrote: @*.*** approved this pull request. LGTM ------------------------------ In pkg/generate/sort.go <#136 (comment)>: > @@ -0,0 +1,86 @@ +package generate + +import ( + "fmt" + + "github.com/openebs/api/v2/pkg/apis/openebs.io/v1alpha1" + "k8s.io/apimachinery/pkg/api/resource" +) + +// DeviceList is a LinkedList of BlockDevices +type DeviceList struct { + item v1alpha1.BlockDevice nit: If we made it as pointer copying of things will be reduced to great extent as compared to struct copy — Reply to this email directly, view it on GitHub <#136 (review)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACG7P4XKZYHES6UYJTURNB3USQQQ5ANCNFSM5JEF3M7Q . You are receiving this because you were mentioned.Message ID: @.>

reflect.DeepEqual should work

[vharsh]

reflect.DeepEqual should work

Yes, it did, made some minor changes in the unit test data. It likely also improved performance numbers.

[vharsh]

Before:

BenchmarkSelect
BenchmarkSelect/six_node_LinkedList,_two_BD_required_of_6G
BenchmarkSelect/six_node_LinkedList,_two_BD_required_of_6G-8              282495          4133 ns/op
BenchmarkSelect/six_node_LinkedList_with_unsorted_BD_sizes,_two_BD_required_of_1G
BenchmarkSelect/six_node_LinkedList_with_unsorted_BD_sizes,_two_BD_required_of_1G-8               232467          5830 ns/op
PASS

After:

cpu: AMD Ryzen 7 4700U with Radeon Graphics         
BenchmarkSelect/six_node_LinkedList,_two_BD_required_of_6G-8              414178          3910 ns/op         848 B/op         15 allocs/op
BenchmarkSelect/six_node_LinkedList_with_unsorted_BD_sizes,_two_BD_required_of_1G-8               282440          5336 ns/op         944 B/op         23 allocs/op
PASS
ok      github.com/openebs/openebsctl/pkg/generate  3.279s