Tool to help choosing a great # of shards

DIVISORS.md

Tool to help choosing a great # of shards

What is this for?

This tool finds numbers with a high number of divisors. Having a lot of divisors is a property that makes them a great choice as the number of partitions to use for sharding.

It also has the concept of "usable divisors", those that provide an increase greater or equal to some % (20% by default). Rebalancing has some operational costs and risks, so you usually wouldn't want to rebalance to achieve less than 20% increase in capacity. But you can override this % to your liking.

Why is important?

Let's image that you want to shard a DB table, so you can split the load across two instance. If you choose to just create 2 tables, you will face a complex migration down the road. Now that you are sharding is better to plan for the future and choose a high number so we can potentially partition across a lot of servers.

You might chose, for example, to create 250 shards. But 250 is only divisible by 2, 5 10, 25, 50 and 125.

Running this tool it will inform you of the divisors for that number:

$ divisors.py 250
 === 250 ================
6 divisors:
   2   5  10  25  50 125
      +3  +5 +15 +25 +75
     60% 50% 60% 50% 60%
6 usable divisors with increases ≥20%:
   2   5  10  25  50 125
      +3  +5 +15 +25 +75
     60% 50% 60% 50% 60%

This means that if you try to balance those 250 shards equally amond a certain number of servers, you will need to go from 2 to 5 (+60%), from 5 to 10 (+50%), and so on. Each increase is quite a significant bump. Going to intermediate increases will leave some servers with more shards than others, and thus not having the same amount of load on all servers, leading to operational problems.

If instead of 250 you were to choose 240 (that is almost the same as 250), you would get far more options:

$ divisors.py 240
 === 240 ================
18 divisors:
   2   3   4   5   6   8  10  12  15  16  20  24  30  40  48  60  80 120
      +1  +1  +1  +1  +2  +2  +2  +3  +1  +4  +4  +6 +10  +8 +12 +20 +40
     33% 25% 20% 16% 25% 20% 16% 20%  6% 20% 16% 20% 25% 16% 20% 25% 33%
13 usable divisors with increases ≥20%:
   2   3   4   5   8  10  15  20  30  40  60  80 120
      +1  +1  +1  +3  +2  +5  +5 +10 +10 +20 +20 +40
     33% 25% 20% 37% 20% 33% 25% 33% 25% 33% 25% 33%

This number allows you to scale from 2 to 3 servers, then to 4, to 5, to 6... very granular increases of 20-33%, always keeping the servers with an equal share of shards.

Usage:

Usage: divisors.py [OPTIONS] NUMBER_RANGE

Options:
  --min-percent INTEGER
  --help                 Show this message and exit.

The output:

 === 240 ================
18 divisors:  # <-- This is the number of divisors
   2   3   4   5   6   8  10  12  15  16  20  24  30  40  48  60  80 120
 # ^--- This is the list of divisors. 240 can be split by 2, 3, 4...
      +1  +1  +1  +1  +2  +2  +2  +3  +1  +4  +4  +6 +10  +8 +12 +20 +40
 #    ^--- This is the increase over previous, how much each divisor grows
 #         When thinking in sharding, this is how many instances you will
 #         need to add to go to the next shard rebalancing.
     33% 25% 20% 16% 25% 20% 16% 20%  6% 20% 16% 20% 25% 16% 20% 25% 33%
 #    ^--- This is the increase over previous, in % instead of net increase
13 usable divisors with increases ≥20%:  # <-- This is the number of "usable divisors"
   2   3   4   5   8  10  15  20  30  40  60  80 120
 # ^--- The list of usable divisors
      +1  +1  +1  +3  +2  +5  +5 +10 +10 +20 +20 +40
 #    ^--- As before, the increase, but for usable divisors
     33% 25% 20% 37% 20% 33% 25% 33% 25% 33% 25% 33%
 #    ^--- As before, Increse in %, but for usable divisors

The tool can operate in ranges:

$ divisors.py 200-1000
 === 200 ================
10 divisors:
   2   4   5   8  10  20  25  40  50 100
      +2  +1  +3  +2 +10  +5 +15 +10 +50
     50% 20% 37% 20% 50% 20% 37% 20% 50%
10 usable divisors with increases ≥20%:
   2   4   5   8  10  20  25  40  50 100
      +2  +1  +3  +2 +10  +5 +15 +10 +50
     50% 20% 37% 20% 50% 20% 37% 20% 50%
 === 204 ================
10 divisors:
   2   3   4   6  12  17  34  51  68 102
      +1  +1  +2  +6  +5 +17 +17 +17 +34
     33% 25% 33% 50% 29% 50% 33% 25% 33%
10 usable divisors with increases ≥20%:
   2   3   4   6  12  17  34  51  68 102
      +1  +1  +2  +6  +5 +17 +17 +17 +34
     33% 25% 33% 50% 29% 50% 33% 25% 33%
 === 210 ================
14 divisors:
   2   3   5   6   7  10  14  15  21  30  35  42  70 105
      +1  +2  +1  +1  +3  +4  +1  +6  +9  +5  +7 +28 +35
     33% 40% 16% 14% 30% 28%  6% 28% 30% 14% 16% 40% 33%
11 usable divisors with increases ≥20%:
   2   3   5   7  10  14  21  30  42  70 105
      +1  +2  +2  +3  +4  +7  +9 +12 +28 +35
     33% 40% 28% 30% 28% 33% 30% 28% 40% 33%
 === 216 ================
14 divisors:
   2   3   4   6   8   9  12  18  24  27  36  54  72 108
      +1  +1  +2  +2  +1  +3  +6  +6  +3  +9 +18 +18 +36
     33% 25% 33% 25% 11% 25% 33% 25% 11% 25% 33% 25% 33%
12 usable divisors with increases ≥20%:
   2   3   4   6   8  12  18  24  36  54  72 108
      +1  +1  +2  +2  +4  +6  +6 +12 +18 +18 +36
     33% 25% 33% 25% 33% 33% 25% 33% 33% 25% 33%
 === 240 ================
18 divisors:
   2   3   4   5   6   8  10  12  15  16  20  24  30  40  48  60  80 120
      +1  +1  +1  +1  +2  +2  +2  +3  +1  +4  +4  +6 +10  +8 +12 +20 +40
     33% 25% 20% 16% 25% 20% 16% 20%  6% 20% 16% 20% 25% 16% 20% 25% 33%
13 usable divisors with increases ≥20%:
   2   3   4   5   8  10  15  20  30  40  60  80 120
      +1  +1  +1  +3  +2  +5  +5 +10 +10 +20 +20 +40
     33% 25% 20% 37% 20% 33% 25% 33% 25% 33% 25% 33%
 === 336 ================
18 divisors:
   2   3   4   6   7   8  12  14  16  21  24  28  42  48  56  84 112 168
      +1  +1  +2  +1  +1  +4  +2  +2  +5  +3  +4 +14  +6  +8 +28 +28 +56
     33% 25% 33% 14% 12% 33% 14% 12% 23% 12% 14% 33% 12% 14% 33% 25% 33%
14 usable divisors with increases ≥20%:
   2   3   4   6   8  12  16  21  28  42  56  84 112 168
      +1  +1  +2  +2  +4  +4  +5  +7 +14 +14 +28 +28 +56
     33% 25% 33% 25% 33% 25% 23% 25% 33% 25% 33% 25% 33%
 === 360 ================
22 divisors:
   2   3   4   5   6   8   9  10  12  15  18  20  24  30  36  40  45  60  72  90 120 180
      +1  +1  +1  +1  +2  +1  +1  +2  +3  +3  +2  +4  +6  +6  +4  +5 +15 +12 +18 +30 +60
     33% 25% 20% 16% 25% 11% 10% 16% 20% 16% 10% 16% 20% 16% 10% 11% 25% 16% 20% 25% 33%
14 usable divisors with increases ≥20%:
   2   3   4   5   8  10  15  20  30  40  60  90 120 180
      +1  +1  +1  +3  +2  +5  +5 +10 +10 +20 +30 +30 +60
     33% 25% 20% 37% 20% 33% 25% 33% 25% 33% 33% 25% 33%
 === 420 ================
22 divisors:
   2   3   4   5   6   7  10  12  14  15  20  21  28  30  35  42  60  70  84 105 140 210
      +1  +1  +1  +1  +1  +3  +2  +2  +1  +5  +1  +7  +2  +5  +7 +18 +10 +14 +21 +35 +70
     33% 25% 20% 16% 14% 30% 16% 14%  6% 25%  4% 25%  6% 14% 16% 30% 14% 16% 20% 25% 33%
15 usable divisors with increases ≥20%:
   2   3   4   5   7  10  14  20  28  35  60  84 105 140 210
      +1  +1  +1  +2  +3  +4  +6  +8  +7 +25 +24 +21 +35 +70
     33% 25% 20% 28% 30% 28% 30% 28% 20% 41% 28% 20% 25% 33%
 === 480 ================
22 divisors:
   2   3   4   5   6   8  10  12  15  16  20  24  30  32  40  48  60  80  96 120 160 240
      +1  +1  +1  +1  +2  +2  +2  +3  +1  +4  +4  +6  +2  +8  +8 +12 +20 +16 +24 +40 +80
     33% 25% 20% 16% 25% 20% 16% 20%  6% 20% 16% 20%  6% 20% 16% 20% 25% 16% 20% 25% 33%
15 usable divisors with increases ≥20%:
   2   3   4   5   8  10  15  20  30  40  60  80 120 160 240
      +1  +1  +1  +3  +2  +5  +5 +10 +10 +20 +20 +40 +40 +80
     33% 25% 20% 37% 20% 33% 25% 33% 25% 33% 25% 33% 25% 33%
 === 504 ================
22 divisors:
   2   3   4   6   7   8   9  12  14  18  21  24  28  36  42  56  63  72  84 126 168 252
      +1  +1  +2  +1  +1  +1  +3  +2  +4  +3  +3  +4  +8  +6 +14  +7  +9 +12 +42 +42 +84
     33% 25% 33% 14% 12% 11% 25% 14% 22% 14% 12% 14% 22% 14% 25% 11% 12% 14% 33% 25% 33%
14 usable divisors with increases ≥20%:
   2   3   4   6   8  12  18  24  36  56  72 126 168 252
      +1  +1  +2  +2  +4  +6  +6 +12 +20 +16 +54 +42 +84
     33% 25% 33% 25% 33% 33% 25% 33% 35% 22% 42% 25% 33%
 === 540 ================
22 divisors:
   2   3   4   5   6   9  10  12  15  18  20  27  30  36  45  54  60  90 108 135 180 270
      +1  +1  +1  +1  +3  +1  +2  +3  +3  +2  +7  +3  +6  +9  +9  +6 +30 +18 +27 +45 +90
     33% 25% 20% 16% 33% 10% 16% 20% 16% 10% 25% 10% 16% 20% 16% 10% 33% 16% 20% 25% 33%
16 usable divisors with increases ≥20%:
   2   3   4   5   9  12  15  20  27  36  45  60  90 135 180 270
      +1  +1  +1  +4  +3  +3  +5  +7  +9  +9 +15 +30 +45 +45 +90
     33% 25% 20% 44% 25% 20% 25% 25% 25% 20% 25% 33% 33% 25% 33%
 === 600 ================
22 divisors:
   2   3   4   5   6   8  10  12  15  20  24  25  30  40  50  60  75 100 120 150 200 300
      +1  +1  +1  +1  +2  +2  +2  +3  +5  +4  +1  +5 +10 +10 +10 +15 +25 +20 +30 +50+100
     33% 25% 20% 16% 25% 20% 16% 20% 25% 16%  4% 16% 25% 20% 16% 20% 25% 16% 20% 25% 33%
16 usable divisors with increases ≥20%:
   2   3   4   5   8  10  15  20  25  40  50  75 100 150 200 300
      +1  +1  +1  +3  +2  +5  +5  +5 +15 +10 +25 +25 +50 +50+100
     33% 25% 20% 37% 20% 33% 25% 20% 37% 20% 33% 25% 33% 25% 33%
 === 630 ================
22 divisors:
   2   3   5   6   7   9  10  14  15  18  21  30  35  42  45  63  70  90 105 126 210 315
      +1  +2  +1  +1  +2  +1  +4  +1  +3  +3  +9  +5  +7  +3 +18  +7 +20 +15 +21 +84+105
     33% 40% 16% 14% 22% 10% 28%  6% 16% 14% 30% 14% 16%  6% 28% 10% 22% 14% 16% 40% 33%
14 usable divisors with increases ≥20%:
   2   3   5   7   9  14  18  30  42  63  90 126 210 315
      +1  +2  +2  +2  +5  +4 +12 +12 +21 +27 +36 +84+105
     33% 40% 28% 22% 35% 22% 40% 28% 33% 30% 28% 40% 33%
 === 660 ================
22 divisors:
   2   3   4   5   6  10  11  12  15  20  22  30  33  44  55  60  66 110 132 165 220 330
      +1  +1  +1  +1  +4  +1  +1  +3  +5  +2  +8  +3 +11 +11  +5  +6 +44 +22 +33 +55+110
     33% 25% 20% 16% 40%  9%  8% 20% 25%  9% 26%  9% 25% 20%  8%  9% 40% 16% 20% 25% 33%
14 usable divisors with increases ≥20%:
   2   3   4   5  10  15  20  30  44  55 110 165 220 330
      +1  +1  +1  +5  +5  +5 +10 +14 +11 +55 +55 +55+110
     33% 25% 20% 50% 33% 25% 33% 31% 20% 50% 33% 25% 33%
 === 672 ================
22 divisors:
   2   3   4   6   7   8  12  14  16  21  24  28  32  42  48  56  84  96 112 168 224 336
      +1  +1  +2  +1  +1  +4  +2  +2  +5  +3  +4  +4 +10  +6  +8 +28 +12 +16 +56 +56+112
     33% 25% 33% 14% 12% 33% 14% 12% 23% 12% 14% 12% 23% 12% 14% 33% 12% 14% 33% 25% 33%
16 usable divisors with increases ≥20%:
   2   3   4   6   8  12  16  21  28  42  56  84 112 168 224 336
      +1  +1  +2  +2  +4  +4  +5  +7 +14 +14 +28 +28 +56 +56+112
     33% 25% 33% 25% 33% 25% 23% 25% 33% 25% 33% 25% 33% 25% 33%
 === 720 ================
28 divisors:
   2   3   4   5   6   8   9  10  12  15  16  18  20  24  30  36  40  45  48  60  72  80  90 120 144 180 240 360
      +1  +1  +1  +1  +2  +1  +1  +2  +3  +1  +2  +2  +4  +6  +6  +4  +5  +3 +12 +12  +8 +10 +30 +24 +36 +60+120
     33% 25% 20% 16% 25% 11% 10% 16% 20%  6% 11% 10% 16% 20% 16% 10% 11%  6% 20% 16% 10% 11% 25% 16% 20% 25% 33%
16 usable divisors with increases ≥20%:
   2   3   4   5   8  10  15  20  30  40  60  80 120 180 240 360
      +1  +1  +1  +3  +2  +5  +5 +10 +10 +20 +20 +40 +60 +60+120
     33% 25% 20% 37% 20% 33% 25% 33% 25% 33% 25% 33% 33% 25% 33%
 === 840 ================
30 divisors:
   2   3   4   5   6   7   8  10  12  14  15  20  21  24  28  30  35  40  42  56  60  70  84 105 120 140 168 210 280 420
      +1  +1  +1  +1  +1  +1  +2  +2  +2  +1  +5  +1  +3  +4  +2  +5  +5  +2 +14  +4 +10 +14 +21 +15 +20 +28 +42 +70+140
     33% 25% 20% 16% 14% 12% 20% 16% 14%  6% 25%  4% 12% 14%  6% 14% 12%  4% 25%  6% 14% 16% 20% 12% 14% 16% 20% 25% 33%
17 usable divisors with increases ≥20%:
   2   3   4   5   7  10  14  20  28  35  56  70 105 140 210 280 420
      +1  +1  +1  +2  +3  +4  +6  +8  +7 +21 +14 +35 +35 +70 +70+140
     33% 25% 20% 28% 30% 28% 30% 28% 20% 37% 20% 33% 25% 33% 25% 33%

You can override the --min-percent setting (20% by default) that is used to determine which are considered "usable divisors".

divisors.py

#!env python
from typing import List
import click


def print_number_list(
    numbers: List[int], width: int = 4, plus: bool = False, suffix: str = ""
):
    blank = " " * width
    width -= len(suffix)
    if plus:
        formatted = [f"{n:>+{width}}{suffix}" if n > 0 else blank for n in numbers]
    else:
        formatted = [f"{n:>{width}}{suffix}" if n > 0 else blank for n in numbers]
    print("".join(formatted))


def print_increases(result: List[int]) -> None:
    diff = []
    percent = []
    prev = result[0]
    for n in result:
        increase = n - prev
        diff.append(increase)
        percent.append(int(increase * 100 / n))
        prev = n
    print_number_list(diff, plus=True)
    print_number_list(percent, suffix="%")


def filter_usable(result: List[int], min_percent: int) -> List[int]:
    usable = []
    prev = result[0]
    for i, n in enumerate(result):
        increase = n - prev
        if increase * 100 / n >= min_percent or i < 1:
            usable.append(n)
            prev = n
    return usable


def divisors(number: int) -> List[int]:
    result = []
    for n in range(2, number // 2 + 1):
        if number % n == 0:
            result.append(n)
    return result


@click.command()
@click.argument("number_range", nargs=1)
@click.option("--min-percent", type=int, default=20)
def find_divisors(number_range: str, min_percent: int) -> None:
    start, _, end = number_range.partition("-")
    start = int(start)
    if not end:
        end = start
    else:
        end = int(end)
    prev = 0
    for n in range(start, end + 1, 2):
        result = divisors(n)
        if len(result) >= prev:
            print(f" === {n} ================")
            print(f"{len(result)} divisors:")
            print_number_list(result)
            print_increases(result)
            usable = filter_usable(result, min_percent)
            print(f"{len(usable)} usable divisors with increases ≥{min_percent}%:")
            print_number_list(usable)
            print_increases(usable)
            prev = len(result)


if __name__ == "__main__":
    find_divisors()