10. Faults

Goal

Keep the rumor spreading when nodes crash and messages are lost.

New in this chapter

otherwise after a block form continuation spec/02 §2.1
[b: block] form pattern-block spec/03 §3.5
run block form run-block spec/03 §3.5
[b: block] type block spec/04 §4.2
disk.Write package std/disk std/README.md § std/disk

Steps

Everything so far worked because nothing broke. Real nodes crash and come back, and real networks lose messages. This chapter takes the rumor package of chapter 9 and makes it survive. First we need a place for what must outlive a crash.

When a node restarts, every field goes back to its initial value. What a node writes to its disk stays. std/disk has two phrases: disk.Write value at "key" on n stores a value, and disk.Read "key" on n or default reads it back, or gives default when nothing is stored. Both name the node, which must be the one running the code.

The code has to use it at the right moment: define [n: Node] start runs when a node is created, and again after every restart, so that is where a node reloads what it kept. In step 1 a node writes the rumor when it learns it and reloads it in start. Peers have to be on disk too, or a restarted node would have nobody to talk to, so Connect now sends each node a Join record to store them. The demo crashes n3 at 2s and restarts it, with sim.Restart, at 3s:

Step 1

# package main
use example.com/tutorial/rumor
use std/sim

define main
  sim.Seed 4
  set nodes to (sim.Cluster of 6 running rumor)
  rumor.Connect nodes
  deliver (message rumor.Rumor with Text "The leader is n1") to (item 0 of nodes)
  after 2s
    sim.Crash (item 2 of nodes)
  after 3s
    sim.Restart (item 2 of nodes)

# package rumor
use std/disk
use std/lists
use std/net
use std/random
use std/sim

Rumor has
  set Text to ""

Join has
  set Peers to {}

Node has
  set Peers to {}
  set Known to ""

# Every node in the list is told about all the others
define Connect [ns: list of Node]
  each n in ns
    deliver (message Join with Peers (lists.Without n from ns)) to n

# Tell one random peer, then maybe again after a random pause
define [n: Node] Tell
  net.Send (message Rumor with Text n.Known) from n to (random.Pick n.Peers)
  after (random.TimeBetween 200ms and 600ms)
    if (random.Chance 0.7)
      n.Tell

# Believe a rumor the first time it is heard, keep it on disk, and start telling it
define [n: Node] Learn [t: text]
  if (n.Known is "")
    set n.Known to t
    disk.Write t at "known" on n
    n.Tell

# After a restart the fields are fresh, but the disk remembers
define [n: Node] start
  set n.Peers to (disk.Read "peers" on n or {})
  set n.Known to (disk.Read "known" on n or "")
  if (n.Known is not "")
    n.Tell

# Peers are kept on disk too
when [n: Node] (sim.Delivered Join)
  set n.Peers to Join.Peers
  disk.Write n.Peers at "peers" on n

when [n: Node] (sim.Delivered Rumor)
  n.Learn Rumor.Text

when [n: Node] (net.Received Rumor from sender)
  n.Learn Rumor.Text

Look at n3 in the summary after the restart: the fields were reset, then start read the disk and the node knew the rumor again. In chapter 9 some nodes never heard it at all, because nodes told a fixed number of times at random. Real systems confirm. Step 2 adds an acknowledgement: a node that receives the rumor answers with an Ack, and the teller keeps a list Acked of peers that answered. It tells only peers that are still Pending, and keeps going until there are none:

Step 2

# package rumor
use std/disk
use std/lists
use std/net
use std/random
use std/sim

Rumor has
  set Text to ""

Ack has
  set Text to ""

Join has
  set Peers to {}

Node has
  set Peers to {}
  set Known to ""
  set Acked to {}

# Every node in the list is told about all the others
define Connect [ns: list of Node]
  each n in ns
    deliver (message Join with Peers (lists.Without n from ns)) to n

# The peers that have not confirmed the rumor yet
define [n: Node] Pending
  set rest to {}
  each p in n.Peers
    if (p is not in n.Acked)
      set rest to (lists.Append p to rest)
  result rest

# Tell one random peer that has not confirmed, again and again until all have
define [n: Node] Tell
  set open to n.Pending
  if ((lists.Size open) more than 0)
    net.Send (message Rumor with Text n.Known) from n to (random.Pick open)
    after (random.TimeBetween 200ms and 600ms)
      n.Tell

# Believe a rumor the first time it is heard, keep it on disk, and start telling it
define [n: Node] Learn [t: text]
  if (n.Known is "")
    set n.Known to t
    disk.Write t at "known" on n
    n.Tell

# After a restart the fields are fresh, but the disk remembers
define [n: Node] start
  set n.Peers to (disk.Read "peers" on n or {})
  set n.Known to (disk.Read "known" on n or "")
  if (n.Known is not "")
    n.Tell

# Peers are kept on disk too
when [n: Node] (sim.Delivered Join)
  set n.Peers to Join.Peers
  disk.Write n.Peers at "peers" on n

when [n: Node] (sim.Delivered Rumor)
  n.Learn Rumor.Text

# Confirm every telling, even of a rumor already known
when [n: Node] (net.Received Rumor from sender)
  n.Learn Rumor.Text
  net.Send (message Ack with Text Rumor.Text) from n to sender

when [n: Node] (net.Received Ack from sender)
  if (sender is not in n.Acked)
    set n.Acked to (lists.Append sender to n.Acked)

Now every node ends up knowing the rumor, even with seed 4. Next we break the network. net.Loss 0.3 makes the network lose 30% of all messages, at random. A lost rumor is never acknowledged, so the teller should try again, a few times, and then give up for now. "Try this, and if it does not work in time, do that" is a pattern we will want in many places, so we make it a phrase, with a new kind of hole.

A hole of type block is filled with an indented block of statements instead of an item. Block holes come last, after at least one word or inline hole. After a block hole come pairs of one word and one more block hole. The word starts a continuation line: a line with a single word and a block, right after the block before it, at the same indentation. You know one, else; ours is otherwise. In the definition, the name of a block hole used as a statement runs the block: b runs the first, c the second. Look at the definition of Retry: it runs b, waits 300ms, and if the peer has still not answered it calls itself with the same two blocks until the tries are used up, then runs c.

The call reads like a sentence: n.Retry 3 times for peer, a block that sends, otherwise, a block that counts the failure:

Step 3

# package main
use example.com/tutorial/rumor
use std/net
use std/sim

define main
  sim.Seed 4
  net.Loss 0.3
  set nodes to (sim.Cluster of 6 running rumor)
  rumor.Connect nodes
  deliver (message rumor.Rumor with Text "The leader is n1") to (item 0 of nodes)
  after 2s
    sim.Crash (item 2 of nodes)
  after 3s
    sim.Restart (item 2 of nodes)

# package rumor
use std/disk
use std/lists
use std/net
use std/random
use std/sim

Rumor has
  set Text to ""

Ack has
  set Text to ""

Join has
  set Peers to {}

Node has
  set Peers to {}
  set Known to ""
  set Acked to {}
  set GaveUp to 0

# Every node in the list is told about all the others
define Connect [ns: list of Node]
  each n in ns
    deliver (message Join with Peers (lists.Without n from ns)) to n

# The peers that have not confirmed the rumor yet
define [n: Node] Pending
  set rest to {}
  each p in n.Peers
    if (p is not in n.Acked)
      set rest to (lists.Append p to rest)
  result rest

# Run b now. If p has not confirmed 300ms later, run it again, up to k times in all, then run c
define [n: Node] Retry [k: number] times for [p: node] [b: block] otherwise [c: block]
  b
  after 300ms
    if (p is not in n.Acked)
      if (k more than 1)
        n.Retry (k minus 1) times for p
          b
        otherwise
          c
      else
        c

# Tell one random peer that has not confirmed, and again until all have
define [n: Node] Tell
  set open to n.Pending
  if ((lists.Size open) more than 0)
    set peer to (random.Pick open)
    n.Retry 3 times for peer
      net.Send (message Rumor with Text n.Known) from n to peer
    otherwise
      set n.GaveUp to (n.GaveUp plus 1)
    after (random.TimeBetween 200ms and 600ms)
      n.Tell

# Believe a rumor the first time it is heard, keep it on disk, and start telling it
define [n: Node] Learn [t: text]
  if (n.Known is "")
    set n.Known to t
    disk.Write t at "known" on n
    n.Tell

# After a restart the fields are fresh, but the disk remembers
define [n: Node] start
  set n.Peers to (disk.Read "peers" on n or {})
  set n.Known to (disk.Read "known" on n or "")
  if (n.Known is not "")
    n.Tell

# Peers are kept on disk too
when [n: Node] (sim.Delivered Join)
  set n.Peers to Join.Peers
  disk.Write n.Peers at "peers" on n

when [n: Node] (sim.Delivered Rumor)
  n.Learn Rumor.Text

# Confirm every telling, even of a rumor already known
when [n: Node] (net.Received Rumor from sender)
  n.Learn Rumor.Text
  net.Send (message Ack with Text Rumor.Text) from n to sender

when [n: Node] (net.Received Ack from sender)
  if (sender is not in n.Acked)
    set n.Acked to (lists.Append sender to n.Acked)

The two blocks run in the caller's context and see its names, n and peer, as they were when Retry was called. They hold copies, so they cannot set a local of the caller; that is why the failure is recorded in a node field, GaveUp.

Last, the faults you aim. net.Partition left from right cuts every link between two groups of nodes until net.Heal. net.DropNext "Rumor" from a to b drops the next message of that record type on that link. Step 4 drops the first rumor from n1 to n2 and splits the cluster for almost three seconds:

Step 4

# package main
use example.com/tutorial/rumor
use std/net
use std/sim

define main
  sim.Seed 4
  set nodes to (sim.Cluster of 6 running rumor)
  set left to {(item 0 of nodes), (item 1 of nodes), (item 2 of nodes)}
  set right to {(item 3 of nodes), (item 4 of nodes), (item 5 of nodes)}
  rumor.Connect nodes
  deliver (message rumor.Rumor with Text "The leader is n1") to (item 0 of nodes)
  net.DropNext "Rumor" from (item 0 of nodes) to (item 1 of nodes)
  after 300ms
    net.Partition left from right
  after 3s
    net.Heal

What to watch

In step 1, n3 greys out at 2s and returns at 3s with the rumor already in its card. In step 3, some messages fade halfway: those are the lost ones; a card retells the same peer a moment later. In step 4 the rumor stays on the left side of the split. The right-hand nodes are retried and given up on, again and again, and as soon as the network heals the rumor crosses and the run ends. The retry never stops by itself: it is the Pending list that ends it.

Why it looks like this

A block hole is filled by an indented block, so it cannot come in the middle of a pattern: after it only pairs of a word and a block may follow, and before it a word or an inline hole must stand. This pattern breaks both rules:

rumor/rumor.synod:50:24: error[bad-pattern]: a word or hole must stand between the head and the first block hole
   |
50 | define [n: Node] Twice [b: block] for [p: node]
   |                        ^^^^^^^^^^

rumor/rumor.synod:50:39: error[bad-pattern]: block holes come last
   |
50 | define [n: Node] Twice [b: block] for [p: node]
   |                        ----------     ^^^^^^^^^
   |                        |
   |                        the last block hole is here

Error bad-pattern

synod check says error[bad-pattern]. The same rules make every call unambiguous, because the compiler always knows where a block begins and which word starts the next one.

Exercises

In step 3 change net.Loss 0.3 to 0.6. What changes?

Expected

More messages are lost, more nodes give up, and GaveUp counts grow. The rumor still arrives, because the telling goes on until every peer acknowledges.

In step 1, restart n3 at 2500ms instead of 3s. Does anything change in what it knows?

Expected

No. The disk does not depend on when the node comes back.

Crash a node forever in step 4 (remove its restart, add sim.Crash). Why does the run now last ten minutes?

Expected

The others keep telling a peer that never answers. With a node down for good nothing empties the queue, so add sim.StopAt to end the run.