Load Balancing Algorithm doesn't consider weight of nodes

[prostko]

It seems that this is the current algorithm used to assign specs to nodes:
Round Robin

1. sorts the spec list by execution time (weight)
2. iterates over the spec list and assigns each of the nodes the current spec by index

---

This can be optimized by:
Least Connections Algorithm

1. sorting the spec list by execution time (weight)
2. iterating over the spec list and for each of the specs:

• Finding the current lightest node
• assigning the current spec to lightest node
• adding the weight of the current spec to the weight of the lightest node

This way the nodes will be more balanced.

[prostko]

Also, thanks a lot! Love the project!

More than happy to submit a PR if this is interesting

[ArturT]

Hi @prostko

Sounds like an interesting idea.

If you would like to work on this you can take a look at
Knapsack::Distributors::ReportDistributor takes care of sorting test files with known time execution (test files in JSON report).
https://github.com/ArturT/knapsack/blob/387181ed7a459557770514c676771eff27dc3e1f/lib/knapsack/allocator.rb#L8
https://github.com/ArturT/knapsack/blob/387181ed7a459557770514c676771eff27dc3e1f/lib/knapsack/distributors/report_distributor.rb#L3

Knapsack::Distributors::LeftoverDistributor takes care of test files with unknown time execution (for instance someone added a new test file and it is not yet in JSON report - this file is called leftover).

List of test files for a given node index from ReportDistributor + LeftoverDistributor are passed to RSpec as allocator.stringify_node_tests
https://github.com/ArturT/knapsack/blob/387181ed7a459557770514c676771eff27dc3e1f/lib/knapsack/runners/rspec_runner.rb#L15 (it looks similar for other runners like cucumber, minitest, etc)

dynamic tests split

A bit similar idea to Least Connections Algorithm you can find in Knapsack Pro Queue Mode that will dynamically split tests between parallel nodes. This way you solve problems when nodes start at a different times or test files have random execution time.

You can check this article https://docs.knapsackpro.com/2020/how-to-speed-up-ruby-and-javascript-tests-with-ci-parallelisation

[ArturT]

I'm closing this issue because #99 was merged.