Concurrency · LLD
Optimistic vs pessimistic concurrency
Optimistic concurrency means try, and retry if someone else won. Pessimistic concurrency means wait on a lock until you can proceed. Example: two cars arrive at two gates and both want spot 101. Pessimistic: they form a line — one gate holds the lock until it has marked a spot; the other waits. Optimistic: both try 101; one succeeds; the loser is told “taken” and tries 102.
On the optimistic path, nobody waited. One attempt failed cleanly and retried another spot. Explain that conflict story before you name ReentrantLock or compareAndSet.
The real question
Should the other gate wait, or try and fail cleanly?
Conflict story
Two paths from the same fork
Pessimistic
The other gate . It never saw 101 as free while you held the key.
Optimistic
needs a . The loser must another rectangle or say the lot is full.
When each story fits
A parking spot is a natural optimistic story. compareAndSet from FREE to OCCUPIED. One gate wins. The other picks another spot. A booking seat is the same story. A ledger that must apply two entries together may prefer a lock around the whole transfer, because a failed half is worse than a short wait.
Lean optimistic
- Collisions are rare, or the loser has another object to try.
- The change is one field or one version number.
- Undo is cheap: just do not park on 101.
Lean pessimistic
- are likely (one compact row, Saturday).
- Several fields must change together; a half is corrupt.
- You would rather wait a blink than retry a messy undo.
Optimistic: try, then pick another
The loop is the fail path. tryOccupy returning false is not an error log. It is “this rectangle is gone; keep walking.”
boolean tryOccupy() {
return status.compareAndSet(SpotStatus.FREE, SpotStatus.OCCUPIED);
}
ParkingSpot allocate(List<ParkingSpot> spots, Vehicle v) {
for (ParkingSpot s : spots) {
if (s.fits(v) && s.tryOccupy()) return s;
}
throw new LotFullException();
}Pessimistic: wait, then occupy
The lock makes pick-and-occupy one critical section. Two gates cannot both choose 101 before either marks it. Hold the lock only for that decision. Print the ticket outside.
ParkingSpot allocate(List<ParkingSpot> spots, Vehicle v) {
synchronized (spots) {
for (ParkingSpot s : spots) {
if (s.fits(v) && s.isFree()) {
s.occupy();
return s;
}
}
}
throw new LotFullException();
}only works if the lock matches the race. Locking the whole lot while you print a receipt makes Saturday evening into a single-file queue. That granularity belongs on the locks page; here the point is wait versus try-and-fail.
Interview: say the conflict, then the tool
Good signposting
“Collisions on one spot are possible but the loser can take 102, so I will CAS occupy and loop. If we must debit two accounts together I would lock the transfer instead.”
Common slip
Starting with ReentrantLock because it sounds grown-up, or CAS-ing and ignoring the boolean so both gates “succeed.”
Versioned seats, same fork
A movie hall often stores a version on the seat: hold if version is still 7, write 8. That is optimistic with a number instead of an enum. Two counters collide; one version wins; the other refreshes and tries another seat. Pessimistic would lock the row. If the hall is mostly empty, versions win. If one blockbuster row is a stampede, a short lock on that row may beat a retry storm.
boolean tryHold(int expectedVersion) {
return version.compareAndSet(expectedVersion, expectedVersion + 1);
}
// Loser: reload version, pick another seat, or tell the UI “taken.”
// Cap retries. Two gates livelocking on H12 is not optimism; it is a missing fail path.Livelock is the optimistic failure mode: both keep retrying the same hot spot. Bound the loop. After N misses, LotFull or “try another type.” Pessimistic’s failure mode is a long wait or deadlock if you nest. Pick the failure you can explain.
Common mistakes
Optimistic with no loser path
compareAndSet that you do not check is an occupy you pretend succeeded. The loser must retry another spot or tell the driver the lot is full.
A giant lock to be safe
If collisions are rare, making every gate wait on the whole lot buys simplicity and spends Saturday throughput. Match the lock to the conflict.
Retrying a half-done ledger
Optimistic on one account and then the other can leave a debit without a credit. Prefer one lock around the transfer, or a single atomic booking record.
ABA, in parking English
Gate A reads FREE, stalls. Gate B occupies, then a car exits, 101 is FREE again. Gate A’s CAS FREE → OCCUPIED succeeds. That may be fine: 101 is free, A parks. It is not fine if A’s CAS meant “this is still the same stay I looked at.” Then you need a version that only goes up, or a ticket id on the spot. In most parking LLD, occupying a spot that became free again is correct. In a compare-and-swap of a recycled pointer, ABA is a real bug. Mention it if they ask why versions exist; do not derail occupy.
Inventory that decrements then restocks can fool a CAS that only checks “quantity is still 1.” A version or a reservation id is the extra expected field. Optimistic still needs the right expected.
Exercises
- One compact spot left, two gates, optimistic CAS. What does the loser return to the driver?
- A cache get that must move a node and maybe evict. Why might you lock the cache instead of CAS-ing the node alone?
- You chose pessimistic on the whole ParkingLot including SMS. What did you serialize that is not a collision?
Read next
Where try-and-fail still hurts
Optimistic CAS on a hot last compact spot with no retry cap can livelock two gates. Pessimistic locking on the entire service starves SMS. Mixing both on the same occupy — CAS then also synchronized (lot) — pays twice and explains nothing. Pick one approach per shared fact.
Takeaway
Wait, or try and fail. Optimistic needs a loser path. Pessimistic needs a small lock. Say the collision story in the interview, then pick CAS or a monitor. Do not start with the class name.