<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P165-shard-planner/ | updated: 2026-10-19 -->

# P165 Shard planner

Order ids allocated 8 apart, placed on buckets and nodes: id % 16 uses 2 of 16 buckets, a ring moves only the keys a new node takes, and one customer's key makes one node serve more than five times the even share.

EML-P project `projects/shard-planner` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/shard-planner` runs it and `eml project verify projects/shard-planner` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: the-hash-was-uniform-and-the-buckets-were-not (https://efficientnewlanguage.org/cases/545-the-hash-was-uniform-and-the-buckets-were-not/), the-hash-was-stable-and-the-ring-was-not (https://efficientnewlanguage.org/cases/635-the-hash-was-stable-and-the-ring-was-not/), the-shard-key-was-uniform-and-the-traffic-was-not (https://efficientnewlanguage.org/cases/669-the-shard-key-was-uniform-and-the-traffic-was-not/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
5

5
1
5
1025
5
x
5
2
5
1024
6
```

Screen:

```text
== Shard planner ==
1,024 order ids placed on buckets and on nodes: what is even, and what is not.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 0
Pick a number from 1 to 6.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> x
Pick a number from 1 to 6.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 
Cancelled.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 1
Type a whole number from 2 to 1024.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 1025
Type a whole number from 2 to 1024.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> x
Type a whole number from 2 to 1024.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 2
id % 2: 1 of 2 buckets used, the busiest with 1024 ids; gcd(2, 8) is 2, and 2 / 2 is 1.
The top bit of the mixed hash: 2 of 2 used, the busiest with 513.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 1024
id % 1024: 128 of 1024 buckets used, the busiest with 8 ids; gcd(1024, 8) is 8, and 1024 / 8 is 128.
The top 10 bits of the mixed hash: 450 of 1024 used, the busiest with 4.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 6
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
2
3
4
5
24
5
128
5
17
6
```

Screen:

```text
== Shard planner ==
1,024 order ids placed on buckets and on nodes: what is even, and what is not.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 1
1,024 order ids from the allocator, which hands them out in blocks of 8: 1000, 1008, 1016, ... 9184.
Every key gets 20 requests a second, except customer 5000's, which gets 9,200: 31.0% of all 29,660.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 2
Where id % n puts the 1,024 ids, and where the top bits of a mixing hash put them:
  buckets   id % n: used  busiest   mixed: used  busiest
  16                   2      512            16       68
  17                  17       61             -        -
  32                   4      256            32       35
  64                   8      128            64       20
The ids are 8 apart, so id % n reaches only n / gcd(n, 8) of the buckets: a power of two shares the factor 8, and 17 shares none. The ids are not skewed; the bucket count and the allocator share a divisor.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 3
12 nodes, then a 13th:
  placed by id % nodes: 946 of the 1,024 keys change node.
  placed on a ring, 16 points a node: 59 keys change node, every one of them to the new node.
Clients read the node list from a registry every 60 seconds, with jitter: for 120 seconds both rings are in use, half the clients on each on average.
The 59 moved keys get 1,180 requests a second, and the half still on the old ring send theirs to the old owners: 70,800 requests to the wrong node, from the same stable hash.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 4
Keys and requests on each node of the 13-node ring:
  node   keys  requests a second
  n0       84              1,680
  n1       72              1,440
  n2       73              1,460
  n3       88              1,760
  n4      131             11,800
  n5      133              2,660
  n6       89              1,780
  n7       60              1,200
  n8       59              1,180
  n9       59              1,180
  n10      58              1,160
  n11      59              1,180
  n12      59              1,180
Keys per node: 58 to 133. Requests: n4, which holds customer 5000, serves 11,800 a second, 5.2 times the even share of 2,282.
Spreading keys does not spread requests: one key is 31.0% of the traffic, and no placement of keys can split it.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 24
id % 24: 3 of 24 buckets used, the busiest with 342 ids; gcd(24, 8) is 8, and 24 / 8 is 3.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 128
id % 128: 16 of 128 buckets used, the busiest with 64 ids; gcd(128, 8) is 8, and 128 / 8 is 16.
The top 7 bits of the mixed hash: 128 of 128 used, the busiest with 12.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 5
buckets (2 to 1024)> 17
id % 17: 17 of 17 buckets used, the busiest with 61 ids; gcd(17, 8) is 1, and 17 / 1 is 17.

1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit
choice> 6
Bye.
```

## Modules

### main.eml

```eml
# P165 shard planner: 1,024 order ids on buckets and nodes - the keys and
# their traffic, buckets by id % n and by a mixing hash, a 13th node added,
# the load on each node, and a bucket count of your own.
import shards

def plain(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def pad(s, n):
    s => out
    while len(out) < n:
        out + " " => out
    return out

def lpad(s, n):
    s => out
    while len(out) < n:
        " " + out => out
    return out

def digits(t):
    for c in t:
        if c < "0" or c > "9":
            return False
    return len(t) > 0

def commas(n):
    str(n) => s
    "" => out
    0 => k
    len(s) => i
    while i > 0:
        if k == 3:
            "," + out => out
            0 => k
        s[i - 1] + out => out
        k + 1 => k
        i - 1 => i
    return out

def tenths(num, den):
    # num / den as a percent to one place, rounded half-up
    num * 2000 + den => y
    int((y - y % (2 * den)) / (2 * den)) => t
    return str(int((t - t % 10) / 10)) + "." + str(t % 10) + "%"

def total_rate():
    0 => t
    for x in shards.ids():
        t + shards.rate(x) => t
    return t

def spread(counts):
    # [buckets used, the busiest]
    0 => used
    0 => most
    for c in counts:
        if c > 0:
            used + 1 => used
        if c > most:
            c => most
    return [used, most]

def by_mod(n):
    [0] * n => c
    for x in shards.ids():
        c[x % n] + 1 => c[x % n]
    return spread(c)

def by_top(b, n):
    [0] * n => c
    for x in shards.ids():
        shards.top(x, b) => k
        c[k] + 1 => c[k]
    return spread(c)

def log2(n):
    # b with 2^b == n, or -1 if n is not a power of two
    0 => b
    1 => p
    while p < n:
        p * 2 => p
        b + 1 => b
    if p == n:
        return b
    return 0 - 1

def show_keys():
    "1,024 order ids from the allocator, which hands them out in blocks of 8: 1000, 1008, 1016, ... 9184." ^0
    ("Every key gets 20 requests a second, except customer " + str(shards.hot_id()) + "'s, which gets " + commas(shards.rate(shards.hot_id())) + ": " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of all " + commas(total_rate()) + ".") ^0

def show_buckets():
    "Where id % n puts the 1,024 ids, and where the top bits of a mixing hash put them:" ^0
    ("  " + pad("buckets", 9) + lpad("id % n: used", 13) + lpad("busiest", 9) + lpad("mixed: used", 14) + lpad("busiest", 9)) ^0
    for n in [16, 17, 32, 64]:
        by_mod(n) => a
        "  " + pad(str(n), 9) + lpad(str(a[0]), 13) + lpad(str(a[1]), 9) => line
        if log2(n) > 0:
            by_top(log2(n), n) => m
            line + lpad(str(m[0]), 14) + lpad(str(m[1]), 9) => line
        else:
            line + lpad("-", 14) + lpad("-", 9) => line
        line ^0
    "The ids are 8 apart, so id % n reaches only n / gcd(n, 8) of the buckets: a power of two shares the factor 8, and 17 shares none. The ids are not skewed; the bucket count and the allocator share a divisor." ^0

def show_join():
    shards.ring(12) => r12
    shards.ring(13) => r13
    0 => by_mod
    0 => by_ring
    0 => moved_rate
    for x in shards.ids():
        if x % 12 != x % 13:
            by_mod + 1 => by_mod
        if shards.owner(r12, x) != shards.owner(r13, x):
            by_ring + 1 => by_ring
            moved_rate + shards.rate(x) => moved_rate
    "12 nodes, then a 13th:" ^0
    ("  placed by id % nodes: " + str(by_mod) + " of the 1,024 keys change node.") ^0
    ("  placed on a ring, 16 points a node: " + str(by_ring) + " keys change node, every one of them to the new node.") ^0
    "Clients read the node list from a registry every 60 seconds, with jitter: for 120 seconds both rings are in use, half the clients on each on average." ^0
    ("The " + str(by_ring) + " moved keys get " + commas(moved_rate) + " requests a second, and the half still on the old ring send theirs to the old owners: " + commas(moved_rate * 60) + " requests to the wrong node, from the same stable hash.") ^0

def show_load():
    shards.ring(13) => r
    [0] * 13 => keys
    [0] * 13 => reqs
    for x in shards.ids():
        shards.owner(r, x) => n
        keys[n] + 1 => keys[n]
        reqs[n] + shards.rate(x) => reqs[n]
    "Keys and requests on each node of the 13-node ring:" ^0
    ("  " + pad("node", 6) + lpad("keys", 5) + lpad("requests a second", 19)) ^0
    0 => k
    while k < 13:
        ("  " + pad("n" + str(k), 6) + lpad(str(keys[k]), 5) + lpad(commas(reqs[k]), 19)) ^0
        k + 1 => k
    spread(keys) => s
    1024 => least
    0 => hot
    0 => k
    while k < 13:
        if keys[k] < least:
            keys[k] => least
        if reqs[k] > reqs[hot]:
            k => hot
        k + 1 => k
    total_rate() * 2 + 13 => y
    int((y - y % 26) / 26) => even
    reqs[hot] * 130 * 2 + total_rate() => z
    int((z - z % (2 * total_rate())) / (2 * total_rate())) => times
    ("Keys per node: " + str(least) + " to " + str(s[1]) + ". Requests: n" + str(hot) + ", which holds customer " + str(shards.hot_id()) + ", serves " + commas(reqs[hot]) + " a second, " + str(int((times - times % 10) / 10)) + "." + str(times % 10) + " times the even share of " + commas(even) + ".") ^0
    ("Spreading keys does not spread requests: one key is " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of the traffic, and no placement of keys can split it.") ^0

def own():
    plain(input("buckets (2 to 1024)> ")) => t
    if t == "":
        "Cancelled." ^0
        return
    if len(t) > 4 or not digits(t) or int(t) < 2 or int(t) > 1024:
        "Type a whole number from 2 to 1024." ^0
        return
    int(t) => n
    by_mod(n) => a
    ("id % " + str(n) + ": " + str(a[0]) + " of " + str(n) + " buckets used, the busiest with " + str(a[1]) + " ids; gcd(" + str(n) + ", 8) is " + str(shards.gcd(n, 8)) + ", and " + str(n) + " / " + str(shards.gcd(n, 8)) + " is " + str(int(n / shards.gcd(n, 8))) + ".") ^0
    if log2(n) > 0:
        by_top(log2(n), n) => m
        "The top " + str(log2(n)) + " bits" => unit
        if log2(n) == 1:
            "The top bit" => unit
        (unit + " of the mixed hash: " + str(m[0]) + " of " + str(n) + " used, the busiest with " + str(m[1]) + ".") ^0

"== Shard planner ==" ^0
"1,024 order ids placed on buckets and on nodes: what is even, and what is not." ^0
True => running
while running:
    "" ^0
    "1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit" ^0
    plain(input("choice> ")) => choice
    if choice == "1":
        show_keys()
    elif choice == "2":
        show_buckets()
    elif choice == "3":
        show_join()
    elif choice == "4":
        show_load()
    elif choice == "5":
        own()
    elif choice == "6":
        False => running
    else:
        "Pick a number from 1 to 6." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import shards

def plain(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def pad(s, n):
    out = s
    while len(out) < n:
        out = out + " "
    return out

def lpad(s, n):
    out = s
    while len(out) < n:
        out = " " + out
    return out

def digits(t):
    for c in t:
        if c < "0" or c > "9":
            return False
    return len(t) > 0

def commas(n):
    s = str(n)
    out = ""
    k = 0
    i = len(s)
    while i > 0:
        if k == 3:
            out = "," + out
            k = 0
        out = s[i - 1] + out
        k = k + 1
        i = i - 1
    return out

def tenths(num, den):
    y = num * 2000 + den
    t = int((y - y % (2 * den)) / (2 * den))
    return str(int((t - t % 10) / 10)) + "." + str(t % 10) + "%"

def total_rate():
    t = 0
    for x in shards.ids():
        t = t + shards.rate(x)
    return t

def spread(counts):
    used = 0
    most = 0
    for c in counts:
        if c > 0:
            used = used + 1
        if c > most:
            most = c
    return [used, most]

def by_mod(n):
    c = [0] * n
    for x in shards.ids():
        c[x % n] = c[x % n] + 1
    return spread(c)

def by_top(b, n):
    c = [0] * n
    for x in shards.ids():
        k = shards.top(x, b)
        c[k] = c[k] + 1
    return spread(c)

def log2(n):
    b = 0
    p = 1
    while p < n:
        p = p * 2
        b = b + 1
    if p == n:
        return b
    return 0 - 1

def show_keys():
    print("1,024 order ids from the allocator, which hands them out in blocks of 8: 1000, 1008, 1016, ... 9184.")
    print("Every key gets 20 requests a second, except customer " + str(shards.hot_id()) + "'s, which gets " + commas(shards.rate(shards.hot_id())) + ": " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of all " + commas(total_rate()) + ".")

def show_buckets():
    print("Where id % n puts the 1,024 ids, and where the top bits of a mixing hash put them:")
    print("  " + pad("buckets", 9) + lpad("id % n: used", 13) + lpad("busiest", 9) + lpad("mixed: used", 14) + lpad("busiest", 9))
    for n in [16, 17, 32, 64]:
        a = by_mod(n)
        line = "  " + pad(str(n), 9) + lpad(str(a[0]), 13) + lpad(str(a[1]), 9)
        if log2(n) > 0:
            m = by_top(log2(n), n)
            line = line + lpad(str(m[0]), 14) + lpad(str(m[1]), 9)
        else:
            line = line + lpad("-", 14) + lpad("-", 9)
        print(line)
    print("The ids are 8 apart, so id % n reaches only n / gcd(n, 8) of the buckets: a power of two shares the factor 8, and 17 shares none. The ids are not skewed; the bucket count and the allocator share a divisor.")

def show_join():
    r12 = shards.ring(12)
    r13 = shards.ring(13)
    by_mod = 0
    by_ring = 0
    moved_rate = 0
    for x in shards.ids():
        if x % 12 != x % 13:
            by_mod = by_mod + 1
        if shards.owner(r12, x) != shards.owner(r13, x):
            by_ring = by_ring + 1
            moved_rate = moved_rate + shards.rate(x)
    print("12 nodes, then a 13th:")
    print("  placed by id % nodes: " + str(by_mod) + " of the 1,024 keys change node.")
    print("  placed on a ring, 16 points a node: " + str(by_ring) + " keys change node, every one of them to the new node.")
    print("Clients read the node list from a registry every 60 seconds, with jitter: for 120 seconds both rings are in use, half the clients on each on average.")
    print("The " + str(by_ring) + " moved keys get " + commas(moved_rate) + " requests a second, and the half still on the old ring send theirs to the old owners: " + commas(moved_rate * 60) + " requests to the wrong node, from the same stable hash.")

def show_load():
    r = shards.ring(13)
    keys = [0] * 13
    reqs = [0] * 13
    for x in shards.ids():
        n = shards.owner(r, x)
        keys[n] = keys[n] + 1
        reqs[n] = reqs[n] + shards.rate(x)
    print("Keys and requests on each node of the 13-node ring:")
    print("  " + pad("node", 6) + lpad("keys", 5) + lpad("requests a second", 19))
    k = 0
    while k < 13:
        print("  " + pad("n" + str(k), 6) + lpad(str(keys[k]), 5) + lpad(commas(reqs[k]), 19))
        k = k + 1
    s = spread(keys)
    least = 1024
    hot = 0
    k = 0
    while k < 13:
        if keys[k] < least:
            least = keys[k]
        if reqs[k] > reqs[hot]:
            hot = k
        k = k + 1
    y = total_rate() * 2 + 13
    even = int((y - y % 26) / 26)
    z = reqs[hot] * 130 * 2 + total_rate()
    times = int((z - z % (2 * total_rate())) / (2 * total_rate()))
    print("Keys per node: " + str(least) + " to " + str(s[1]) + ". Requests: n" + str(hot) + ", which holds customer " + str(shards.hot_id()) + ", serves " + commas(reqs[hot]) + " a second, " + str(int((times - times % 10) / 10)) + "." + str(times % 10) + " times the even share of " + commas(even) + ".")
    print("Spreading keys does not spread requests: one key is " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of the traffic, and no placement of keys can split it.")

def own():
    t = plain(input("buckets (2 to 1024)> "))
    if t == "":
        print("Cancelled.")
        return
    if len(t) > 4 or not digits(t) or int(t) < 2 or int(t) > 1024:
        print("Type a whole number from 2 to 1024.")
        return
    n = int(t)
    a = by_mod(n)
    print("id % " + str(n) + ": " + str(a[0]) + " of " + str(n) + " buckets used, the busiest with " + str(a[1]) + " ids; gcd(" + str(n) + ", 8) is " + str(shards.gcd(n, 8)) + ", and " + str(n) + " / " + str(shards.gcd(n, 8)) + " is " + str(int(n / shards.gcd(n, 8))) + ".")
    if log2(n) > 0:
        m = by_top(log2(n), n)
        unit = "The top " + str(log2(n)) + " bits"
        if log2(n) == 1:
            unit = "The top bit"
        print(unit + " of the mixed hash: " + str(m[0]) + " of " + str(n) + " used, the busiest with " + str(m[1]) + ".")

print("== Shard planner ==")
print("1,024 order ids placed on buckets and on nodes: what is even, and what is not.")
running = True
while running:
    print("")
    print("1) the keys  2) buckets  3) a 13th node  4) load per node  5) a bucket count of your own  6) quit")
    choice = plain(input("choice> "))
    if choice == "1":
        show_keys()
    elif choice == "2":
        show_buckets()
    elif choice == "3":
        show_join()
    elif choice == "4":
        show_load()
    elif choice == "5":
        own()
    elif choice == "6":
        running = False
    else:
        print("Pick a number from 1 to 6.")
print("Bye.")
```

### shards.eml

```eml
# P165 shard planner - 1,024 order ids placed on buckets and nodes. As in
# the corpus case the-hash-was-uniform-and-the-buckets-were-not, the ids
# come from an allocator that hands them out 8 apart, and id % n reaches
# only the buckets that 8 can: a power of two shares its factor. As in
# the-hash-was-stable-and-the-ring-was-not, a ring moves only the keys the
# new node takes, and while clients hold two node lists, the same stable
# hash names two owners. And as in
# the-shard-key-was-uniform-and-the-traffic-was-not, keys spread evenly and
# requests do not.

def ids():
    # 1000, 1008, 1016, ... - 1,024 of them
    [0] * 1024 => out
    0 => k
    while k < 1024:
        1000 + 8 * k => out[k]
        k + 1 => k
    return out

def hot_id():
    return 5000

def rate(x):
    # requests a second for key x
    if x == hot_id():
        return 9200
    return 20

def mix(x):
    # a multiplicative hash onto 0 .. 2^32 - 1 (x below 3,000,000)
    return (x * 2654435761) % 4294967296

def top(x, b):
    # bucket of x among 2^b: the top b bits of its mixed hash
    1 => d
    0 => k
    while k < 32 - b:
        d * 2 => d
        k + 1 => k
    mix(x) => h
    return int((h - h % d) / d)

def ring(nodes):
    # [position, node] for 16 points a node, sorted by position
    [] => pts
    0 => n
    while n < nodes:
        0 => v
        while v < 16:
            pts + [[mix(100000 + n * 100 + v), n]] => pts
            v + 1 => v
        n + 1 => n
    1 => i
    while i < len(pts):
        pts[i] => p
        i - 1 => j
        while j >= 0 and pts[j][0] > p[0]:
            pts[j] => pts[j + 1]
            j - 1 => j
        p => pts[j + 1]
        i + 1 => i
    return pts

def owner(pts, x):
    # the node of the first point at or after x's position, round the ring
    mix(x) => h
    0 => lo
    len(pts) => hi
    while lo < hi:
        int((lo + hi - (lo + hi) % 2) / 2) => mid
        if pts[mid][0] < h:
            mid + 1 => lo
        else:
            mid => hi
    if lo == len(pts):
        return pts[0][1]
    return pts[lo][1]

def gcd(a, b):
    while b > 0:
        a % b => r
        b => a
        r => b
    return a
```

Python projection of shards.eml:

```python
def ids():
    out = [0] * 1024
    k = 0
    while k < 1024:
        out[k] = 1000 + 8 * k
        k = k + 1
    return out

def hot_id():
    return 5000

def rate(x):
    if x == hot_id():
        return 9200
    return 20

def mix(x):
    return x * 2654435761 % 4294967296

def top(x, b):
    d = 1
    k = 0
    while k < 32 - b:
        d = d * 2
        k = k + 1
    h = mix(x)
    return int((h - h % d) / d)

def ring(nodes):
    pts = []
    n = 0
    while n < nodes:
        v = 0
        while v < 16:
            pts = pts + [[mix(100000 + n * 100 + v), n]]
            v = v + 1
        n = n + 1
    i = 1
    while i < len(pts):
        p = pts[i]
        j = i - 1
        while j >= 0 and pts[j][0] > p[0]:
            pts[j + 1] = pts[j]
            j = j - 1
        pts[j + 1] = p
        i = i + 1
    return pts

def owner(pts, x):
    h = mix(x)
    lo = 0
    hi = len(pts)
    while lo < hi:
        mid = int((lo + hi - (lo + hi) % 2) / 2)
        if pts[mid][0] < h:
            lo = mid + 1
        else:
            hi = mid
    if lo == len(pts):
        return pts[0][1]
    return pts[lo][1]

def gcd(a, b):
    while b > 0:
        r = a % b
        a = b
        b = r
    return a
```

## README

# P165 - Shard planner

1,024 order ids placed on buckets and on nodes: what comes out even, and
what does not.

- `main.eml` - the menu, the keys and their traffic, buckets by id % n and
  by a mixing hash, a 13th node, the load on each node, and a bucket count
  of your own
- `shards.eml` - the ids and their request rates, a multiplicative mixing
  hash, a ring with 16 points a node, and finding a key's owner on it

How each part works:

- The allocator hands out ids in blocks of 8: 1000, 1008, ... 9184. Every
  key gets 20 requests a second except customer 5000's, which gets 9,200,
  31.0% of all 29,660.
- As in the corpus case `the-hash-was-uniform-and-the-buckets-were-not`,
  id % n reaches only n / gcd(n, 8) buckets: 2 of 16, 4 of 32, 8 of 64,
  and all 17 of 17. The ids are not skewed; they share a factor with a
  power-of-two bucket count. The top bits of a mixing hash use all 16, 32
  and 64.
- As in `the-hash-was-stable-and-the-ring-was-not`, adding a 13th node moves
  946 of the 1,024 keys when they are placed by id % nodes, and 59 on the
  ring, every one of them to the new node. For the 120 seconds both node
  lists are in use, the half of the clients still on the old one send the
  moved keys' 1,180 requests a second to the old owners: 70,800 requests
  to the wrong node, from the same stable hash.
- As in `the-shard-key-was-uniform-and-the-traffic-was-not`, keys per node
  run from 58 to 133, while the node holding customer 5000 serves 11,800
  requests a second, 5.2 times the even share: no placement of keys can
  split one key.

What is checked: menu choices 1 to 6; a bucket count from 2 to 1024. An
empty answer cancels.

Sessions: `sessions/basic.in` gives:
- the keys, the buckets, the 13th node and the load per node;
- bucket counts of 24, 128 and 17.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- bucket counts: a cancel, 1, 1025 and x;
- bucket counts of 2 and 1024.

Built on the verified corpus cases `the-hash-was-uniform-and-the-buckets-were-not`
(ids allocated 8 apart in a power-of-two table),
`the-hash-was-stable-and-the-ring-was-not` (a node added to a consistent
hashing ring while clients hold different member lists) and
`the-shard-key-was-uniform-and-the-traffic-was-not` (keys even across 64
shards, and one key with 31 percent of the requests).