SwadhyAI Notes

All Low-Level Design notes

Concurrency · LLD

Concurrent collections

Tickets live in a HashMap by id. Gate A puts T-1. Gate B puts T-2. Under the hood the map resizes, a bucket is half-copied, and a lookup can hang or a ticket can vanish. You did not race occupy this time; you raced the dictionary. HashMap never promised safe concurrent writers.

A fixes single get and put. It does not fix a like “if free then occupy.” That is still two calls unless you use the map’s one-step API.

Pick for the job

  1. 1. Map index. ConcurrentHashMap with or , not containsKey then put.
  2. 2. Work queue. put/take already wait; bound the capacity.
  3. 3. Rare listeners. at startup, never a hot free-spot board.

Safe single ops, unsafe stories

The real question is: is the collection itself what we share, and is get-then-put still two steps? If many threads only need a map, a queue, or a list, start with a concurrent type instead of locking a HashMap by habit. Then ask whether your action is one method or a compound action.

ConcurrentHashMap

Ticket index, session table, idempotency keys. Use putIfAbsent and replace, not containsKey then put.

BlockingQueue

Work queue. put / take already waits. Bound it. This is producer-consumer as a type.

CopyOnWrite list

Rare writes: listeners at startup. Not occupancy. Not a hot board of free spots.

The map’s occupy, and the race on the value

Two gates must not both insert the same TicketId. is that sentence; the return value is the fail path. A concurrent map of spots still does not make ParkingLot thread-safe: occupy is a transition on the spot. Use , CAS on the value, or a lock around the compound.

java
class TicketIndex {
  private final ConcurrentHashMap<TicketId, Ticket> byId =
      new ConcurrentHashMap<>();

  boolean putNew(Ticket ticket) {
    Ticket already = byId.putIfAbsent(ticket.id(), ticket);
    return already == null;          // false: two gates, same id
  }
}
java
ConcurrentHashMap<Integer, SpotStatus> board = new ConcurrentHashMap<>();
board.put(101, SpotStatus.FREE);

// Both gates: two tickets again:
if (board.get(101) == SpotStatus.FREE) {
  board.put(101, SpotStatus.OCCUPIED);
}

// One step:
board.replace(101, SpotStatus.FREE, SpotStatus.OCCUPIED);

If the map holds a mutable ParkingSpot, replace on an enum is the wrong layer. Hold the spot object, make tryOccupy atomic on the spot, and let the map be a directory. compute is for “create or update this entry as one map step” (counters, sets of ids), not for walking twenty spots.

java
// Directory, not the race:
ConcurrentHashMap<Integer, ParkingSpot> byNumber = ...;
ParkingSpot s = byNumber.get(101);
if (s != null && s.tryOccupy()) return s;

// Compound on the entry itself (idempotency counter, not occupancy):
hits.compute(key, (k, n) -> n == null ? 1 : n + 1);

When CopyOnWrite is the wrong board

After the map story, name the list type people reach for too early. copies the array on every write. Reads are cheap. That fits observers at startup, not free spots that change every park.

java
private final CopyOnWriteArrayList<LotListener> listeners =
    new CopyOnWriteArrayList<>();

void addListener(LotListener l) { listeners.add(l); }   // rare

void fireParked(ParkedEvent e) {
  for (LotListener l : listeners) l.onParked(e);        // snapshot iteration
}

// Not this: CopyOnWriteArrayList<ParkingSpot> freeSpots;

Dictionary lies, iteration, and HashMap under writers

A ConcurrentHashMap of ParkingSpot by number is a directory: find 101 fast. The board (is 101 free) lives on the spot. Mixing them into Map of SpotStatus plus get/put is how people “use CHM” and still double-ticket. putIfAbsent is for “this id must be born once,” a dictionary race, not an occupancy race.

HashMap under two writers: a resize can corrupt a bucket chain. Modern JDKs fail more loudly, but the contract never promised concurrent writes. ConcurrentHashMap’s contract is concurrent single operations; your compound story is still yours. ConcurrentLinkedQueue is unbounded and does not back-pressure; a bounded does.

Iteration is a compound action too. for (Ticket t : map.values()) during concurrent puts is weakly consistent: you may miss a new ticket. Fine for “list open tickets,” not for “sum money then clear.” Snapshot keys first or confine the map. synchronizedList iteration still needs the list locked for the whole for-loop.

compute that calls occupy inside the map’s function can deadlock if occupy locks something the caller already holds. Keep compute tiny. A CHM of mutable lists as values: the map will not protect list.add.

I used ConcurrentHashMap. Am I done?

The map’s get and put are safe. Your “if free then occupy” is still two calls. Use replace or putIfAbsent, or CAS on the spot object the map holds. The collection is the dictionary, not the occupancy arrow.

Why not Collections.synchronizedList?

It locks each call. Iteration still needs an external lock or you race. Compound get-then-add still races. Prefer a concurrent type that matches the operation, or one lock around the real critical section.

Why CopyOnWrite for observers?

Iteration sees a snapshot. A listener can unsubscribe without ConcurrentModificationException. Writes are rare. Occupancy is not rare; do not copy the lot on every park.

Is map.size() exact under concurrency?

Treat size as an estimate. Do not use “if size < cap then put” as a bound. The bound belongs in putIfAbsent against a known key, a semaphore, or the allocator’s own count under confinement.

Wrap-up

You have the types, the one-step APIs, and the directory-versus-board split. Use these mistakes and exercises to check the ideas stuck.

Common mistakes

ConcurrentHashMap therefore I am done

The map’s get and put are safe. Your “if free then occupy” is still two calls; use replace or putIfAbsent.

CopyOnWrite for a hot board

Copying the whole spot list on every occupy is a tax you cannot pay at the gate.

Locking a HashMap by habit

For a ticket dictionary, ConcurrentHashMap plus putIfAbsent fits; synchronized HashMap still leaves compound actions as two steps unless you lock both.

Exercises

  1. Idempotency key map: two retries of pay(). Which ConcurrentHashMap method records “first wins”?
  2. board.get(101) == FREE then board.put OCCUPIED. Rewrite with replace. What does false mean for the loser gate?
  3. You stored free spots in CopyOnWriteArrayList. Estimate the copy cost at 400 spots and 2 parks per second. What type belongs instead?
  4. for (Ticket t : chm.values()) then sum fees and clear. Why is that not one map operation, and what would you confine or snapshot instead?

Key takeaway

Use a concurrent collection when the collection is the shared state. Single ops are safe; get-then-put is still a race. putIfAbsent and replace are the map’s occupy. CopyOnWrite is for rare writes. Occupancy still lives on the spot.