<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P166-replica-placement/ | updated: 2026-10-19 -->

# P166 Replica placement

Three replicas a shard on racks of 6, 3 and 3 nodes, by distinct nodes or by distinct racks: a check that counts nodes while failures arrive by rack, uneven loads, and a shared service no replica count moves.

EML-P project `projects/replica-placement` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/replica-placement` runs it and `eml project verify projects/replica-placement` 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-quorum-was-three-and-two-shared-a-rack (https://efficientnewlanguage.org/cases/621-the-quorum-was-three-and-two-shared-a-rack/), three-copies-and-two-places-to-lose-them (https://efficientnewlanguage.org/cases/551-three-copies-and-two-places-to-lose-them/), the-redundancy-shared-a-dependency (https://efficientnewlanguage.org/cases/577-the-redundancy-shared-a-dependency/).

## Sessions

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

Input:

```text
0
x
3

3
D
3
x
6

6
6
6
6 3 3 3 3 3 3
6
0 3 3
6
21 3
6
1 1
6
6,3,3
6
6 3 x
6
100 3
6
1 1 1
7
```

Screen:

```text
== Replica placement ==
Three replicas a shard, two needed to serve, on racks of different sizes.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 0
Pick a number from 1 to 7.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> x
Pick a number from 1 to 7.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 3
which rack (A, B or C)> 
Cancelled.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 3
which rack (A, B or C)> D
Type A, B or C.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 3
which rack (A, B or C)> x
Type A, B or C.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 
Cancelled.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 6
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 6 3 3 3 3 3 3
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 0 3 3
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 21 3
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 1 1
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 6,3,3
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 6 3 x
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 100 3
Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 1 1 1
3 nodes in racks A, B and C: rule 1 allows 1 triple, 0 (0.0%) with two or more in one rack; rack A down leaves 0 (0.0%) without quorum.
Rule 2 allows 1, and one rack down never takes a quorum; every node holds 100.0% of the shards.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 7
Bye.
```

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

Input:

```text
1
2
3
A
3
b
4
5
6
4 4 4
6
10 2
7
```

Screen:

```text
== Replica placement ==
Three replicas a shard, two needed to serve, on racks of different sizes.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 1
Racks A, B and C with 6, 3 and 3 nodes: 12 nodes. Every shard has 3 replicas and needs 2 to serve.
Rule 1, distinct nodes: no two replicas of a shard on one node. Rule 2, distinct racks: one replica in each of three racks.
A shard is equally likely to land on any node triple its rule allows.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 2
Rule 1 allows 220 node triples, and the placement check passes on every one.
  166 of them (75.5%) put two or more replicas in one rack: 110 in A, 28 in B, 28 in C.
Rule 2 allows 54 triples, and none puts two in one rack.
The check counts nodes; failures arrive by rack.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 3
which rack (A, B or C)> A
Rack A down, 6 nodes:
  rule 1: of 220 triples, 20 untouched, 90 left with 2, 90 left with 1 and no quorum, 20 left with none: 50.0% cannot serve.
  rule 2: of 54 triples, 0 untouched and 54 left with 2: every shard still serves.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 3
which rack (A, B or C)> b
Rack B down, 3 nodes:
  rule 1: of 220 triples, 84 untouched, 108 left with 2, 27 left with 1 and no quorum, 1 left with none: 12.7% cannot serve.
  rule 2: of 54 triples, 0 untouched and 54 left with 2: every shard still serves.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 4
Replicas a node holds, as a share of the shards: rule 1, every node 25.0% (3 of 12).
Rule 2: a node in A 16.7%, in B 33.3%, in C 33.3%. The small racks' nodes carry twice as much: every shard puts one replica in each rack, and 3 nodes share what 6 share in A.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 5
Each rack is down 1 in 1000 of the time, on its own; every rack reads its configuration from one service, down 5 in 1000.
  minutes a year a shard cannot serve      racks alone  with the service
  one replica in each rack                        1.58          2,629.57
  two of the replicas in one rack               525.60          3,150.97
A replica in a third rack cuts the rack term from 525.60 minutes to 1.58. The service is not a rack, and no number of replicas moves its 2,628 minutes.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 4 4 4
12 nodes in racks A, B and C: rule 1 allows 220 triples, 156 (70.9%) with two or more in one rack; rack A down leaves 52 (23.6%) without quorum.
Rule 2 allows 64, and one rack down never takes a quorum; every node holds 25.0% of the shards.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 6
nodes in each rack, e.g. 6 3 3> 10 2
12 nodes in racks A and B: rule 1 allows 220 triples, 220 (100.0%) with two or more in one rack; rack A down leaves 210 (95.5%) without quorum.
Rule 2 needs three racks.

1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit
choice> 7
Bye.
```

## Modules

### main.eml

```eml
# P166 replica placement: three replicas a shard on racks of 6, 3 and 3
# nodes, placed by distinct nodes or by distinct racks - the placements, a
# rack down, the load per node, availability, and a cluster of your own.
import placement

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 pct(a, b):
    # a of b as a percent to one place, half-up
    a * 2000 + b => y
    int((y - y % (2 * b)) / (2 * b)) => t
    return str(int((t - t % 10) / 10)) + "." + str(t % 10) + "%"

def minutes(parts):
    placement.minutes_hundredths(parts) => h
    h % 100 => c
    if c < 10:
        return commas(int((h - c) / 100)) + ".0" + str(c)
    return commas(int((h - c) / 100)) + "." + str(c)

def names(rs):
    "" => out
    0 => i
    while i < len(rs):
        if i > 0 and i == len(rs) - 1:
            out + " and " => out
        elif i > 0:
            out + ", " => out
        out + rs[i][0] => out
        i + 1 => i
    return out

def show_cluster():
    placement.racks() => rs
    ("Racks A, B and C with 6, 3 and 3 nodes: " + str(placement.nodes(rs)) + " nodes. Every shard has 3 replicas and needs 2 to serve.") ^0
    "Rule 1, distinct nodes: no two replicas of a shard on one node. Rule 2, distinct racks: one replica in each of three racks." ^0
    "A shard is equally likely to land on any node triple its rule allows." ^0

def show_placements():
    placement.racks() => rs
    placement.node_triples(rs) => t
    placement.two_in_one(rs) => e
    "" => each
    0 => x
    while x < len(rs):
        placement.lose_nodes(rs, x) => l
        if each != "":
            each + ", " => each
        each + str(l[1] + l[2]) + " in " + rs[x][0] => each
        x + 1 => x
    ("Rule 1 allows " + str(t) + " node triples, and the placement check passes on every one.") ^0
    ("  " + str(e) + " of them (" + pct(e, t) + ") put two or more replicas in one rack: " + each + ".") ^0
    ("Rule 2 allows " + str(placement.rack_triples(rs)) + " triples, and none puts two in one rack.") ^0
    "The check counts nodes; failures arrive by rack." ^0

def rack_down(rs, x):
    placement.node_triples(rs) => t
    placement.lose_nodes(rs, x) => l
    t - l[0] - l[1] - l[2] => untouched
    ("  rule 1: of " + str(t) + " triples, " + str(untouched) + " untouched, " + str(l[0]) + " left with 2, " + str(l[1]) + " left with 1 and no quorum, " + str(l[2]) + " left with none: " + pct(l[1] + l[2], t) + " cannot serve.") ^0
    if len(rs) >= 3:
        placement.rack_triples(rs) => r
        placement.lose_racks(rs, x) => k
        ("  rule 2: of " + str(r) + " triples, " + str(r - k) + " untouched and " + str(k) + " left with 2: every shard still serves.") ^0

def show_rack():
    placement.racks() => rs
    plain(input("which rack (A, B or C)> ")) => t
    if t == "":
        "Cancelled." ^0
        return
    0 - 1 => x
    0 => i
    for r in rs:
        if t == r[0] or t == ["a", "b", "c"][i]:
            i => x
        i + 1 => i
    if x < 0:
        "Type A, B or C." ^0
        return
    ("Rack " + rs[x][0] + " down, " + str(rs[x][1]) + " nodes:") ^0
    rack_down(rs, x)

def loads(rs):
    # [least, most] share of shards a node holds under rule 2, as [triples, of]
    placement.rack_triples(rs) => r
    0 - 1 => lo
    0 => hi
    0 => x
    while x < len(rs):
        placement.per_node_racks(rs, x) => k
        if lo < 0 or k < lo:
            k => lo
        if k > hi:
            k => hi
        x + 1 => x
    return [lo, hi, r]

def show_load():
    placement.racks() => rs
    placement.nodes(rs) => n
    ("Replicas a node holds, as a share of the shards: rule 1, every node " + pct(3, n) + " (3 of " + str(n) + ").") ^0
    "" => each
    0 => x
    while x < len(rs):
        if each != "":
            each + ", " => each
        each + "in " + rs[x][0] + " " + pct(placement.per_node_racks(rs, x), placement.rack_triples(rs)) => each
        x + 1 => x
    ("Rule 2: a node " + each + ". The small racks' nodes carry twice as much: every shard puts one replica in each rack, and 3 nodes share what 6 share in A.") ^0

def show_availability():
    "Each rack is down 1 in 1000 of the time, on its own; every rack reads its configuration from one service, down 5 in 1000." ^0
    ("  " + pad("minutes a year a shard cannot serve", 40) + lpad("racks alone", 12) + lpad("with the service", 18)) ^0
    ("  " + pad("one replica in each rack", 40) + lpad(minutes(placement.down_parts(False, False)), 12) + lpad(minutes(placement.down_parts(False, True)), 18)) ^0
    ("  " + pad("two of the replicas in one rack", 40) + lpad(minutes(placement.down_parts(True, False)), 12) + lpad(minutes(placement.down_parts(True, True)), 18)) ^0
    "A replica in a third rack cuts the rack term from 525.60 minutes to 1.58. The service is not a rack, and no number of replicas moves its 2,628 minutes." ^0

def sizes(t):
    # the numbers in t, separated by spaces; [] if anything else is there
    [] => out
    "" => cur
    for c in t + " ":
        if c == " ":
            if cur != "":
                if len(cur) > 2:
                    return []
                out + [int(cur)] => out
                "" => cur
        elif c < "0" or c > "9":
            return []
        else:
            cur + c => cur
    return out

def own():
    plain(input("nodes in each rack, e.g. 6 3 3> ")) => t
    if t == "":
        "Cancelled." ^0
        return
    sizes(t) => ns
    True => ok
    if len(ns) < 2 or len(ns) > 6:
        False => ok
    0 => total
    for v in ns:
        total + v => total
        if v < 1 or v > 20:
            False => ok
    if not ok or total < 3:
        "Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all." ^0
        return
    [] => rs
    0 => i
    for v in ns:
        rs + [[["A", "B", "C", "D", "E", "F"][i], v]] => rs
        i + 1 => i
    placement.node_triples(rs) => tr
    placement.two_in_one(rs) => e
    0 => worst
    0 => x
    while x < len(rs):
        placement.lose_nodes(rs, x) => l
        placement.lose_nodes(rs, worst) => w
        if l[1] + l[2] > w[1] + w[2]:
            x => worst
        x + 1 => x
    placement.lose_nodes(rs, worst) => w
    " triples" => word
    if tr == 1:
        " triple" => word
    (str(total) + " nodes in racks " + names(rs) + ": rule 1 allows " + commas(tr) + word + ", " + commas(e) + " (" + pct(e, tr) + ") with two or more in one rack; rack " + rs[worst][0] + " down leaves " + commas(w[1] + w[2]) + " (" + pct(w[1] + w[2], tr) + ") without quorum.") ^0
    if len(rs) < 3:
        "Rule 2 needs three racks." ^0
        return
    loads(rs) => ld
    if ld[0] == ld[1]:
        ("Rule 2 allows " + commas(ld[2]) + ", and one rack down never takes a quorum; every node holds " + pct(ld[0], ld[2]) + " of the shards.") ^0
    else:
        ("Rule 2 allows " + commas(ld[2]) + ", and one rack down never takes a quorum; a node holds " + pct(ld[0], ld[2]) + " to " + pct(ld[1], ld[2]) + " of the shards.") ^0

"== Replica placement ==" ^0
"Three replicas a shard, two needed to serve, on racks of different sizes." ^0
True => running
while running:
    "" ^0
    "1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit" ^0
    plain(input("choice> ")) => choice
    if choice == "1":
        show_cluster()
    elif choice == "2":
        show_placements()
    elif choice == "3":
        show_rack()
    elif choice == "4":
        show_load()
    elif choice == "5":
        show_availability()
    elif choice == "6":
        own()
    elif choice == "7":
        False => running
    else:
        "Pick a number from 1 to 7." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import placement

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 pct(a, b):
    y = a * 2000 + b
    t = int((y - y % (2 * b)) / (2 * b))
    return str(int((t - t % 10) / 10)) + "." + str(t % 10) + "%"

def minutes(parts):
    h = placement.minutes_hundredths(parts)
    c = h % 100
    if c < 10:
        return commas(int((h - c) / 100)) + ".0" + str(c)
    return commas(int((h - c) / 100)) + "." + str(c)

def names(rs):
    out = ""
    i = 0
    while i < len(rs):
        if i > 0 and i == len(rs) - 1:
            out = out + " and "
        elif i > 0:
            out = out + ", "
        out = out + rs[i][0]
        i = i + 1
    return out

def show_cluster():
    rs = placement.racks()
    print("Racks A, B and C with 6, 3 and 3 nodes: " + str(placement.nodes(rs)) + " nodes. Every shard has 3 replicas and needs 2 to serve.")
    print("Rule 1, distinct nodes: no two replicas of a shard on one node. Rule 2, distinct racks: one replica in each of three racks.")
    print("A shard is equally likely to land on any node triple its rule allows.")

def show_placements():
    rs = placement.racks()
    t = placement.node_triples(rs)
    e = placement.two_in_one(rs)
    each = ""
    x = 0
    while x < len(rs):
        l = placement.lose_nodes(rs, x)
        if each != "":
            each = each + ", "
        each = each + str(l[1] + l[2]) + " in " + rs[x][0]
        x = x + 1
    print("Rule 1 allows " + str(t) + " node triples, and the placement check passes on every one.")
    print("  " + str(e) + " of them (" + pct(e, t) + ") put two or more replicas in one rack: " + each + ".")
    print("Rule 2 allows " + str(placement.rack_triples(rs)) + " triples, and none puts two in one rack.")
    print("The check counts nodes; failures arrive by rack.")

def rack_down(rs, x):
    t = placement.node_triples(rs)
    l = placement.lose_nodes(rs, x)
    untouched = t - l[0] - l[1] - l[2]
    print("  rule 1: of " + str(t) + " triples, " + str(untouched) + " untouched, " + str(l[0]) + " left with 2, " + str(l[1]) + " left with 1 and no quorum, " + str(l[2]) + " left with none: " + pct(l[1] + l[2], t) + " cannot serve.")
    if len(rs) >= 3:
        r = placement.rack_triples(rs)
        k = placement.lose_racks(rs, x)
        print("  rule 2: of " + str(r) + " triples, " + str(r - k) + " untouched and " + str(k) + " left with 2: every shard still serves.")

def show_rack():
    rs = placement.racks()
    t = plain(input("which rack (A, B or C)> "))
    if t == "":
        print("Cancelled.")
        return
    x = 0 - 1
    i = 0
    for r in rs:
        if t == r[0] or t == ["a", "b", "c"][i]:
            x = i
        i = i + 1
    if x < 0:
        print("Type A, B or C.")
        return
    print("Rack " + rs[x][0] + " down, " + str(rs[x][1]) + " nodes:")
    rack_down(rs, x)

def loads(rs):
    r = placement.rack_triples(rs)
    lo = 0 - 1
    hi = 0
    x = 0
    while x < len(rs):
        k = placement.per_node_racks(rs, x)
        if lo < 0 or k < lo:
            lo = k
        if k > hi:
            hi = k
        x = x + 1
    return [lo, hi, r]

def show_load():
    rs = placement.racks()
    n = placement.nodes(rs)
    print("Replicas a node holds, as a share of the shards: rule 1, every node " + pct(3, n) + " (3 of " + str(n) + ").")
    each = ""
    x = 0
    while x < len(rs):
        if each != "":
            each = each + ", "
        each = each + "in " + rs[x][0] + " " + pct(placement.per_node_racks(rs, x), placement.rack_triples(rs))
        x = x + 1
    print("Rule 2: a node " + each + ". The small racks' nodes carry twice as much: every shard puts one replica in each rack, and 3 nodes share what 6 share in A.")

def show_availability():
    print("Each rack is down 1 in 1000 of the time, on its own; every rack reads its configuration from one service, down 5 in 1000.")
    print("  " + pad("minutes a year a shard cannot serve", 40) + lpad("racks alone", 12) + lpad("with the service", 18))
    print("  " + pad("one replica in each rack", 40) + lpad(minutes(placement.down_parts(False, False)), 12) + lpad(minutes(placement.down_parts(False, True)), 18))
    print("  " + pad("two of the replicas in one rack", 40) + lpad(minutes(placement.down_parts(True, False)), 12) + lpad(minutes(placement.down_parts(True, True)), 18))
    print("A replica in a third rack cuts the rack term from 525.60 minutes to 1.58. The service is not a rack, and no number of replicas moves its 2,628 minutes.")

def sizes(t):
    out = []
    cur = ""
    for c in t + " ":
        if c == " ":
            if cur != "":
                if len(cur) > 2:
                    return []
                out = out + [int(cur)]
                cur = ""
        elif c < "0" or c > "9":
            return []
        else:
            cur = cur + c
    return out

def own():
    t = plain(input("nodes in each rack, e.g. 6 3 3> "))
    if t == "":
        print("Cancelled.")
        return
    ns = sizes(t)
    ok = True
    if len(ns) < 2 or len(ns) > 6:
        ok = False
    total = 0
    for v in ns:
        total = total + v
        if v < 1 or v > 20:
            ok = False
    if not ok or total < 3:
        print("Type 2 to 6 rack sizes from 1 to 20, at least 3 nodes in all.")
        return
    rs = []
    i = 0
    for v in ns:
        rs = rs + [[["A", "B", "C", "D", "E", "F"][i], v]]
        i = i + 1
    tr = placement.node_triples(rs)
    e = placement.two_in_one(rs)
    worst = 0
    x = 0
    while x < len(rs):
        l = placement.lose_nodes(rs, x)
        w = placement.lose_nodes(rs, worst)
        if l[1] + l[2] > w[1] + w[2]:
            worst = x
        x = x + 1
    w = placement.lose_nodes(rs, worst)
    word = " triples"
    if tr == 1:
        word = " triple"
    print(str(total) + " nodes in racks " + names(rs) + ": rule 1 allows " + commas(tr) + word + ", " + commas(e) + " (" + pct(e, tr) + ") with two or more in one rack; rack " + rs[worst][0] + " down leaves " + commas(w[1] + w[2]) + " (" + pct(w[1] + w[2], tr) + ") without quorum.")
    if len(rs) < 3:
        print("Rule 2 needs three racks.")
        return
    ld = loads(rs)
    if ld[0] == ld[1]:
        print("Rule 2 allows " + commas(ld[2]) + ", and one rack down never takes a quorum; every node holds " + pct(ld[0], ld[2]) + " of the shards.")
    else:
        print("Rule 2 allows " + commas(ld[2]) + ", and one rack down never takes a quorum; a node holds " + pct(ld[0], ld[2]) + " to " + pct(ld[1], ld[2]) + " of the shards.")

print("== Replica placement ==")
print("Three replicas a shard, two needed to serve, on racks of different sizes.")
running = True
while running:
    print("")
    print("1) the cluster  2) placements  3) a rack down  4) load per node  5) availability  6) a cluster of your own  7) quit")
    choice = plain(input("choice> "))
    if choice == "1":
        show_cluster()
    elif choice == "2":
        show_placements()
    elif choice == "3":
        show_rack()
    elif choice == "4":
        show_load()
    elif choice == "5":
        show_availability()
    elif choice == "6":
        own()
    elif choice == "7":
        running = False
    else:
        print("Pick a number from 1 to 7.")
print("Bye.")
```

### placement.eml

```eml
# P166 replica placement - three replicas a shard, two needed to serve, on
# racks of different sizes, under two rules: any three distinct nodes, or
# one replica in each of three racks. Every count is over all the node
# triples a rule allows, each equally likely. As in the corpus case
# the-quorum-was-three-and-two-shared-a-rack, the distinct-nodes rule passes
# its check while failures arrive by rack. As in
# three-copies-and-two-places-to-lose-them, three copies are three chances
# only when they are in three places, and spreading by rack loads the small
# racks' nodes harder. And as in the-redundancy-shared-a-dependency,
# independent racks multiply, and a service they all share does not.

def racks():
    # [name, nodes]
    return [["A", 6], ["B", 3], ["C", 3]]

def choose(n, k):
    if k < 0 or k > n:
        return 0
    1 => r
    1 => i
    while i <= k:
        int(r * (n - k + i) / i) => r
        i + 1 => i
    return r

def nodes(rs):
    0 => t
    for r in rs:
        t + r[1] => t
    return t

def node_triples(rs):
    return choose(nodes(rs), 3)

def rack_triples(rs):
    # node triples with one node in each of three racks
    0 => t
    len(rs) => k
    0 => a
    while a < k:
        a + 1 => b
        while b < k:
            b + 1 => c
            while c < k:
                t + rs[a][1] * rs[b][1] * rs[c][1] => t
                c + 1 => c
            b + 1 => b
        a + 1 => a
    return t

def others(rs, x):
    # pairs of nodes from two different racks, neither of them rack x
    0 => t
    len(rs) => k
    0 => a
    while a < k:
        a + 1 => b
        while b < k:
            if a != x and b != x:
                t + rs[a][1] * rs[b][1] => t
            b + 1 => b
        a + 1 => a
    return t

def lose_nodes(rs, x):
    # node triples, under any three distinct nodes, that rack x's failure
    # leaves with [2 replicas, 1 (no quorum), 0]
    rs[x][1] => n
    nodes(rs) - n => rest
    return [n * choose(rest, 2), choose(n, 2) * rest, choose(n, 3)]

def lose_racks(rs, x):
    # one-in-each-rack triples that rack x's failure leaves with 2 replicas
    return rs[x][1] * others(rs, x)

def two_in_one(rs):
    # node triples with two or three replicas in one rack
    0 => t
    0 => x
    while x < len(rs):
        lose_nodes(rs, x) => l
        t + l[1] + l[2] => t
        x + 1 => x
    return t

def per_node_racks(rs, x):
    # one-in-each-rack triples that hold a given node of rack x
    return others(rs, x)

def down_parts(two_in_one, shared):
    # per 10^12, the chance a shard cannot serve, each rack down 1 in 1000
    # independently. One replica a rack: two of the three racks down. Two
    # in one rack: that rack down. With shared, the configuration service
    # every rack reads, down 5 in 1000, as well.
    3 * 999 + 1 => p
    if two_in_one:
        1000000 => p
    if not shared:
        return p * 1000
    return 1000000000000 - (1000000000 - p) * 995

def minutes_hundredths(parts):
    # minutes a year for a chance of parts per 10^12, in hundredths, half-up
    parts * 5256 + 50000000 => y
    return int((y - y % 100000000) / 100000000)
```

Python projection of placement.eml:

```python
def racks():
    return [["A", 6], ["B", 3], ["C", 3]]

def choose(n, k):
    if k < 0 or k > n:
        return 0
    r = 1
    i = 1
    while i <= k:
        r = int(r * (n - k + i) / i)
        i = i + 1
    return r

def nodes(rs):
    t = 0
    for r in rs:
        t = t + r[1]
    return t

def node_triples(rs):
    return choose(nodes(rs), 3)

def rack_triples(rs):
    t = 0
    k = len(rs)
    a = 0
    while a < k:
        b = a + 1
        while b < k:
            c = b + 1
            while c < k:
                t = t + rs[a][1] * rs[b][1] * rs[c][1]
                c = c + 1
            b = b + 1
        a = a + 1
    return t

def others(rs, x):
    t = 0
    k = len(rs)
    a = 0
    while a < k:
        b = a + 1
        while b < k:
            if a != x and b != x:
                t = t + rs[a][1] * rs[b][1]
            b = b + 1
        a = a + 1
    return t

def lose_nodes(rs, x):
    n = rs[x][1]
    rest = nodes(rs) - n
    return [n * choose(rest, 2), choose(n, 2) * rest, choose(n, 3)]

def lose_racks(rs, x):
    return rs[x][1] * others(rs, x)

def two_in_one(rs):
    t = 0
    x = 0
    while x < len(rs):
        l = lose_nodes(rs, x)
        t = t + l[1] + l[2]
        x = x + 1
    return t

def per_node_racks(rs, x):
    return others(rs, x)

def down_parts(two_in_one, shared):
    p = 3 * 999 + 1
    if two_in_one:
        p = 1000000
    if not shared:
        return p * 1000
    return 1000000000000 - (1000000000 - p) * 995

def minutes_hundredths(parts):
    y = parts * 5256 + 50000000
    return int((y - y % 100000000) / 100000000)
```

## README

# P166 - Replica placement

Three replicas a shard, two needed to serve, on racks of 6, 3 and 3
nodes: placed on any three distinct nodes, or one in each of three racks.

- `main.eml` - the menu, the cluster, the placements, a rack down, the
  load per node, availability, and a cluster of your own
- `placement.eml` - the racks, the node triples each rule allows, what a
  rack's failure leaves, and the minutes a year a shard cannot serve

How each part works:

- A shard is equally likely to land on any node triple its rule allows, so
  every figure is an exact count over those triples.
- As in the corpus case `the-quorum-was-three-and-two-shared-a-rack`, the
  distinct-nodes rule allows 220 triples and its check passes on all of
  them, and 166 (75.5%) put two or more replicas in one rack. With rack A
  down, 50.0% of them cannot serve; rack B takes 12.7%. One replica in each
  of three racks: no single rack takes a quorum.
- As in `three-copies-and-two-places-to-lose-them`, three copies are three
  chances only in three places, and the racks are not the same size:
  spreading by rack puts 16.7% of the shards on each node of A and 33.3%
  on each node of B and C, where distinct nodes put 25.0% on every node.
- As in `the-redundancy-shared-a-dependency`, each rack is down 1 in 1000
  of the time on its own, and every rack reads one configuration service,
  down 5 in 1000. One replica in each rack cannot serve for 1.58 minutes a
  year from the racks, 2,629.57 with the service; two in one rack, 525.60
  and 3,150.97. The service's 2,628 minutes are not touched by any number
  of replicas.

What is checked: menu choices 1 to 7; a rack A, B or C (in capitals or
not); 2 to 6 rack sizes from 1 to 20, separated by spaces, at least 3
nodes in all. An empty answer cancels.

Sessions: `sessions/basic.in` gives:
- the cluster, the placements, racks A and B down, the load and the
  availability;
- clusters of 4 4 4 (an even load under rule 2) and 10 2 (no third rack).

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- racks: a cancel, D and x;
- clusters: a cancel, one rack, seven racks, a rack of 0 and one of 21, 1 1,
  6,3,3, a letter and 100 3;
- the smallest cluster, 1 1 1.

Built on the verified corpus cases `the-quorum-was-three-and-two-shared-a-rack`
(three replicas on distinct nodes, two of them in one rack),
`three-copies-and-two-places-to-lose-them` (replicas spread by node over
racks of 12, 4 and 4 nodes) and `the-redundancy-shared-a-dependency` (three
zones at 99.9 percent and one certificate authority they all use).