Master

Designing shared state

Shared state is the part of a program that has to be designed twice. Once for one task, and once for the order tasks can arrive in.

What you will see

About 2 min of reading

Try It

Check the state design.

Keys counted.

results = {} results["a"] = 1 results["b"] = 2 print(len(results))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Counter exact.

import threading lock = threading.Lock() count = 0 def bump(): global count with lock: count = count + 1 for _ in range(3): bump() print(count)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Merge sized.

parts = [{"a": 1}, {"b": 2}] merged = {} for p in parts: merged.update(p) print(len(merged))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Writers named.

owners = ["task-a", "task-b"] print(len(set(owners)))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Each task owns its cells, tasks return their own data, one merge combines the parts, and a cell with two writers gets a lock.

1 each task owns cells

↓

2 tasks return their data

↓

3 one merge combines it

↓

4 a shared cell gets a lock

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

results = {} sets nothing on screen

results["a"] = 1 sets nothing on screen

results["b"] = 2 sets nothing on screen

print(len(results)) 2

Why this works

One writer per cell

Design the state so each cell has one writer. Then a race needs two writers and the design has none.

Merge beats share

A merge at the end is a serial step over small data. It is cheaper to read than a shared cell with a lock around every touch.

Examples

A value with an owner

results = {}
results["a"] = 1
print(len(results))

A dict written by one key per task has no window between two writers. Different keys cannot lose each other.

A counter instead

import threading

lock = threading.Lock()
count = 0

def bump():
    global count
    with lock:
        count = count + 1

for _ in range(3):
    bump()
print(count)

A single counter needs a lock because every writer touches the same slot. That is the cost of one shared cell.

A merge at the end

parts = [{"a": 1}, {"b": 2}]
merged = {}
for p in parts:
    merged.update(p)
print(len(merged))

Each task returns its own small map and one merge combines them. No task reads another task state.

A cell read later

shared = {"ready": False}
shared["ready"] = True
print(shared["ready"])

A flag one task writes and another reads needs a stated order. Without it, the reader can see the old value.

Immutable is easier

point = (1, 2)
shifted = (point[0] + 1, point[1])
print(shifted)

A value nobody writes is a value nobody can race on. Return new data instead of editing a shared object.

Name the writers

owners = ["task-a", "task-b"]
print(len(set(owners)))

Write down who writes each field. A field with two names beside it is the field that needs a lock or a merge.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Where the boundary sits

Previous Lesson

Where the boundary sits

Next Lesson

A small concurrent tool

A small concurrent tool →