Thread safety in code

In a machine-coding round (lesson 105), your code often keeps data in memory, such as a cache or a seat map. When it works, the interviewer may ask: "Two requests call this method at the same moment. What goes wrong?" The question tests whether you can see that data can break even when every line is correct.

A weak answer says "Python is safe" or puts a lock on every method without a reason. A strong answer finds the step that another request can interrupt. It protects only that step and says what the protection costs. It also knows where a lock stops helping: when the app runs on more than one server.

At SDE-1 level you should know that two requests can overlap, and that a lock fixes it. At SDE-2 level you should protect a check followed by a change, and avoid deadlock. At SDE-3 level you should choose how much code to lock, and say when to use the database instead (lesson 22).

Think of a small shop with two clerks. A note on the wall says "pens in stock: 1". Clerk A reads the note and sells the pen. Before A changes the note, clerk B reads it, sees 1, and sells the same pen. Each clerk did the right steps. The mix of the steps was wrong. The fix is a rule: only the clerk who holds the key to the cash drawer may read or change the note. The other clerk waits for the key.

A thread is one line of work inside a running program. A web server runs many threads, often one for each request. The computer may pause a thread between any two of its steps and run another thread. Data that more than one thread can reach is shared data, such as a counter, a cache or a seat map in memory. A race condition is a bug where the result depends on which thread runs which step first. It is the lost update of lesson 21 and the gap of lesson 22, but inside the memory of one program.

Here is a counter of page views. The three steps are written out, because the computer does all three.

class ViewCounter:
    def __init__(self):
        self.views = 10

    def add_view(self):
        current = self.views     # step 1: read
        new = current + 1        # step 2: add
        self.views = new         # step 3: write

The line self.views += 1 looks like one step, but the computer also does read, add and write. Two threads can both read the same number. Then both write the same new number, and one view is lost. The bug is rare and depends on timing. A test can pass a thousand times and fail on the sale day.

Fix 1: a lock

A lock lets only one thread at a time run a part of the code. A thread that wants a lock that is taken waits. The code inside is the critical section. In Python, with lock: takes the lock at the start of the block and gives it back at the end, even when an error happens.

import threading

class ViewCounter:
    def __init__(self):
        self.views = 10
        self.lock = threading.Lock()

    def add_view(self):
        with self.lock:
            self.views += 1

Keep the critical section short. While one thread holds the lock, every thread that needs it waits. Never make a slow call inside it, such as a database call or a network call. This is the advice of lesson 22 for database locks, too.

Check, then act

The second common bug is a check followed by a change. It is the same gap as SELECT then UPDATE in lesson 22. The check and the change must sit in the same critical section.

class Stock:
    def __init__(self, units):
        self.units = units
        self.lock = threading.Lock()

    def buy(self):
        with self.lock:
            if self.units > 0:      # check
                self.units -= 1     # act
                return True
            return False

Without the with line, two threads can both see units equal to 1, and both buy.

The same rule holds for many items. To hold seats A1 and A2 together, check both seats and mark both inside one lock. If the check runs outside the lock, another thread can take A2 after your check. Then you hold only one seat. In Java, a synchronized block or a ReentrantLock does the job of with lock:.

Atomic steps

An atomic step is one step that no other thread can interrupt (lesson 22). Some steps are atomic already. The Python documentation lists L.append(x) and D[x] = y as atomic. It lists i = i+1 and D[x] = D[x] + 1 as not atomic. A group of atomic steps is still not atomic as a whole. A check on a dictionary followed by a read is two steps. When you are not sure, use a lock.

Java gives an atomic number, AtomicInteger. Its incrementAndGet() adds 1 in one step, and your code needs no lock. Its compareAndSet(expected, new) sets the number only if it still equals expected, and returns true or false. This is the version check of lesson 22 (optimistic locking). The threading module of Python has no atomic number, so the class below builds one with a lock. Then take_one shows the usual loop: if the compare fails, another thread changed the number, so read again and retry.

class AtomicCounter:
    def __init__(self, value=0):
        self.value = value
        self.lock = threading.Lock()

    def compare_and_set(self, expected, new):
        with self.lock:
            if self.value != expected:
                return False
            self.value = new
            return True

def take_one(counter):
    while True:
        seen = counter.value
        if seen == 0:
            return False
        if counter.compare_and_set(seen, seen - 1):
            return True

Two locks: deadlock and lock order

With two locks, a new bug appears. Thread 1 holds lock A and waits for lock B. Thread 2 holds lock B and waits for lock A. Both wait with no end. This is a deadlock (lesson 22). A database such as Postgres notices it and stops one transaction. A plain Python lock does not notice it. The fix is the same as in lesson 22: every thread takes the locks in the same order. A transfer between two wallets takes the wallet with the lower id first.

class Wallet:
    def __init__(self, wallet_id, balance):
        self.id, self.balance = wallet_id, balance
        self.lock = threading.Lock()

def transfer(src, dst, amount):
    if src is dst:
        raise ValueError("same wallet")
    first, second = sorted((src, dst), key=lambda w: w.id)
    with first.lock:
        with second.lock:
            if src.balance < amount:
                return False
            src.balance -= amount
            dst.balance += amount
            return True

The check src is dst matters: a plain lock makes even its own thread wait if the thread takes it a second time. Python also has threading.RLock, which allows this, but it is better not to take a lock twice.

A safe cache

A cache is shared by all request threads, so it needs the same care. Take the least recently used (LRU) cache of lesson 33. It keeps its keys in an OrderedDict, a dictionary that remembers the order of its keys. Its get looks like a read, but move_to_end puts the key last in that order. So get also changes the cache. Use one lock for every method.

from collections import OrderedDict

class SafeLruCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()
        self.lock = threading.Lock()

    def get(self, key):
        with self.lock:
            if key not in self.items:
                return None
            self.items.move_to_end(key)
            return self.items[key]

    def put(self, key, value):
        with self.lock:
            self.items[key] = value
            self.items.move_to_end(key)
            if len(self.items) > self.capacity:
                self.items.popitem(last=False)

    def get_or_load(self, key, load):
        value = self.get(key)
        if value is None:
            value = load(key)        # slow work: no lock held here
            self.put(key, value)
        return value

get_or_load does the slow load outside the lock. Two threads can both miss and both load. This wastes work but never gives wrong data. Lesson 35 shows how to join such loads into one.

One lock for the whole cache is simple, but under heavy load all threads wait for the same lock. A next step is several smaller caches, each with its own lock. The remainder of the hash of the key, divided by the number of parts, chooses the part.

Share less, and know where a lock stops

The best fix is to share less. A value that nobody changes needs no lock. A thread that works on its own copy needs no lock either. Also, a lock lives inside one program. If the app runs on three servers, there are three programs and three separate locks (lesson 26). Across servers, use the database tools of lesson 22.

A shop server on a sale day. It is one Python program, and each request runs on its own thread. Assumption: all numbers are made up to teach with.

1. The counter (the predict box). Both threads run the three steps of add_view.

The final value is 11. The right value is 10 + 1 + 1 = 12. If thread 1 finishes all three steps before thread 2 starts, the result is 12. So you can see 11 or 12, and 12 is right. With the lock, thread 2 waits at the with line until thread 1 has written 11. Then it reads 11 and writes 12.

2. The last unit. Stock(1). Asha and Ravi both press Buy. Without the lock, both check 1 > 0 and both pass. Asha sets units to 0. Ravi sets it to 0 - 1 = -1. Both are told "bought", so the shop sold one unit too many. With the lock, Ravi waits. When he checks, units is 0, so he is told "sold out".

3. The cost of the lock. Assumption: the critical section of buy takes 0.05 ms.

• At most 1,000 ms / 0.05 ms = 20,000 buys per second can pass through the lock.
• The sale sends 2,000 buys per second. The lock is busy 2,000 x 0.05 ms = 100 ms in each second, which is 10%.
• A developer puts a database call of 20 ms inside the lock. One buy now holds the lock for 20.05 ms. At most 1,000 / 20.05 = 49.9, about 50 buys per second, can pass.
• The sale needs 2,000 / 50 = 40 times more than that. Requests wait in a long line and time out, and the lock is the reason.

4. Two wallets. Asha has id 1 and Rs 1,000. Ravi has id 2 and Rs 500. At the same moment, Asha sends Rs 300 to Ravi, and Ravi sends Rs 200 to Asha. If each thread locks the sender first, thread 1 holds Asha, thread 2 holds Ravi, and each waits for the other. That is a deadlock. With the lower id first, both threads lock Asha first, so one waits for the other. The balances end at Asha 1,000 - 300 + 200 = Rs 900 and Ravi 500 + 300 - 200 = Rs 600. The total is 900 + 600 = 1,500, as before.

5. The cache. A cache of size 2 holds "a" (the oldest) and "b". Thread 1 calls get("a"). Thread 2 calls put("c", ...). Without the lock:

1. Thread 1 checks that "a" is in the cache. It is.
2. Thread 2 adds "c". The cache now has three keys, so it removes the oldest, "a".
3. Thread 1 calls move_to_end("a"). The key is gone, and Python raises a KeyError.

With the lock, thread 2 waits. Thread 1 moves "a" to the end, so the order is b, a. Then thread 2 adds "c" and removes "b". The cache holds a and c, and no error happens.

• A lock solves lost updates and a check followed by a change. It costs waiting. The cost is small when the locked part is short, and it is large when a slow call sits inside. I would change it when the lock is busy most of the time. Then I make the locked part shorter, or split the data and give each part its own lock.
• One lock for everything solves the problem with little code, and two threads cannot wait for each other's lock. It costs speed, because unrelated work waits. Many small locks give more speed but add deadlock risk. I would add them only after I see the wait, and I would always take them in one order.
• A retry loop with compare and set solves waiting. It costs wasted tries when many threads clash. I would use a lock when clashes are common.
• A lock in code solves clashes inside one program. It costs nothing for other servers, because it does not reach them. I would change to a database tool (lesson 22) when the app runs on more than one server.

"Python has a global interpreter lock (GIL), so my code is already thread safe." Standard Python runs one thread at a time and switches only between small steps. But self.views += 1 is several steps. A switch can come between them. The Python documentation lists i = i+1 as not atomic. Since Python 3.13, an optional build can run without the GIL, and then even more steps can overlap.

"I only need a lock around the writes. Reads are harmless." In the LRU cache, get moves a key, so it is also a write. In example 5, an unlocked get crashed because another thread changed the cache between its check and its move.

"I put a lock in my class, so double booking cannot happen." The lock reaches only the threads of one program. Three servers have three locks and share none of them. The database must make the decision (lesson 22).

1. Name three ways to keep shared data safe in code. Give one cost of the lock.
2. The locked part of a cache call takes 0.2 ms. (a) At most how many calls per second can pass through the lock? (b) A developer adds a load of 10 ms inside the lock. Now at most how many? (c) The app gets 800 calls per second. How many times too many is that for (b)?
3. A teammate puts a lock around Stock.buy. The app then runs on 3 servers. Each server loaded Stock(100) from the database at start-up, and the sale has 100 units in total. What can happen, and what do you change?