Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-19
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 ownplacement.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (29 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (13 lines)
1
2
3
A
3
b
4
5
6
4 4 4
6
10 2
7
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (placement.py)
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)