Double booking and producer-consumer

Part of the free Low-Level Design course on LogicWiz, in the chapter: Concurrency in LLD. The class-diagram exercises run in the app.

Week 10: The slot that was sold 23 times

"The 6 to 8 pm slot has room for 20 orders. On Saturday we sold it 23 times."

Priya, opening the incident report

A slot is stock with a deadline

SwiftKart lets customers pick a delivery slot: a time window such as 6 to 8 pm. Each slot has a capacity, the number of orders the riders can carry in that window. Here is Arjun's first booking code:

public boolean book(String slotId, String orderId) {
    DeliverySlot slot = slots.get(slotId);
    if (slot.bookedCount() < slot.capacity()) {   // check
        slot.addBooking(orderId);                  // act
        return true;
    }
    return false;
}

You have seen this shape last week. It is check-then-act. On Saturday evening, hundreds of customers booked at once. Four of them passed the check while the slot showed 19 bookings. This is called double booking: selling the same limited place to more people than it holds. Seat booking for cinemas and trains has the same problem. You will meet it again in the problem library.

Arjun's first fix was to put synchronized on book. "Now only one thread books at a time, so we are safe," he said. Priya asked how many servers run the slot service. Twelve. A synchronized lock lives inside one Java process. Twelve processes have twelve separate locks, and they do not know about each other.

So there are two levels to the answer. Inside one process, a Java lock works. Across many servers, the shared database must do the guarding. In a machine-coding round you build one process, so say this out loud and then use a Java lock.

Pessimistic locking: lock first, then decide

Pessimistic locking assumes a conflict is likely. You take a lock before reading, and hold it until you have written. Nobody else can even read the slot to decide in the meantime.

One lock for the whole service would make every booking wait in one line, even for different slots. Use one lock per slot instead:

public class SlotBookingService {
    private final Map<String, DeliverySlot> slots;
    private final ConcurrentHashMap<String, ReentrantLock> locks = new ConcurrentHashMap<>();

    public SlotBookingService(Map<String, DeliverySlot> slots) {
        this.slots = slots;
    }

    public boolean book(String slotId, String orderId) {
        ReentrantLock lock = locks.computeIfAbsent(slotId, id -> new ReentrantLock());
        lock.lock();
        try {
            DeliverySlot slot = slots.get(slotId);
            if (slot.bookedCount() >= slot.capacity()) {
                return false;
            }
            slot.addBooking(orderId);
            return true;
        } finally {
            lock.unlock();
        }
    }
}

computeIfAbsent is atomic, so two threads asking for the lock of slot "S18" always get the same lock object. In a database, the same idea is SELECT ... FOR UPDATE, which locks the slot's row until the transaction ends.

Optimistic locking: check the version when you save

Optimistic locking assumes a conflict is rare. You read without a lock. When you save, you check that nobody changed the record since you read it. Each record carries a version number that goes up by one on every save.

public record DeliverySlot(String id, int capacity, int booked, int version) {
    boolean hasRoom() { return booked < capacity; }
    DeliverySlot withOneMore() { return new DeliverySlot(id, capacity, booked + 1, version + 1); }
}

public interface SlotRepository {
    DeliverySlot find(String slotId);
    boolean saveIfVersion(DeliverySlot updated, int expectedVersion);
}

public class InMemorySlotRepository implements SlotRepository {
    private final ConcurrentHashMap<String, DeliverySlot> slots = new ConcurrentHashMap<>();

    public DeliverySlot find(String slotId) { return slots.get(slotId); }

    public boolean saveIfVersion(DeliverySlot updated, int expectedVersion) {
        DeliverySlot result = slots.computeIfPresent(updated.id(),
            (id, current) -> current.version() == expectedVersion ? updated : current);
        return result == updated;
    }
}

computeIfPresent runs the check and the replace for one key as a single step. If another thread saved first, the version no longer matches, and the save is refused. The service then reads again and retries:

public boolean book(String slotId) {
    for (int attempt = 0; attempt < 3; attempt++) {
        DeliverySlot slot = repo.find(slotId);
        if (!slot.hasRoom()) {
            return false;
        }
        if (repo.saveIfVersion(slot.withOneMore(), slot.version())) {
            return true;
        }
    }
    throw new IllegalStateException("Slot is busy, please try again");
}

In SQL the save becomes UPDATE slot SET booked = booked + 1, version = version + 1 WHERE id = :id AND version = :expected. If it updates zero rows, someone else won. This works across all twelve servers, because the database does the check.

How do you choose?

• Optimistic suits records where conflicts are rare, such as a customer editing their own address. No thread waits.
• Pessimistic suits hot records where conflicts are common, such as the last places in a popular slot. Retrying again and again would waste more time than waiting.

💡 Tip: In an interview, name both and pick one with a reason. "Slots get busy at 6 pm, so I lock per slot" is a strong answer.

Now draw it. Put slot storage behind a SlotRepository interface, give DeliverySlot a version, and add the save that checks it.

Producer-consumer: a queue between threads

After a booking, SwiftKart sends an SMS and a push message. Sending takes about 300 milliseconds. Arjun's checkout thread did it inline, so the customer waited for it.

The fix is the producer-consumer pattern. Producers are threads that create work, here the checkout threads. Consumers are worker threads that do the work. Between them sits a blocking queue: a thread-safe queue where put waits when the queue is full and take waits when it is empty.

flowchart LR
  C1["Checkout thread"] -->|"put"| Q["BlockingQueue, size 1000"]
  C2["Checkout thread"] -->|"put"| Q
  Q -->|"take"| W1["Notification worker"]
  Q -->|"take"| W2["Notification worker"]

private final BlockingQueue<OrderEvent> queue = new ArrayBlockingQueue<>(1000);

// Producer: runs on the checkout thread
public void onBooked(String orderId) throws InterruptedException {
    queue.put(new OrderEvent(orderId, "BOOKED"));   // waits if the queue is full
}

// Consumer: each worker thread runs this loop
public void run() {
    try {
        while (true) {
            OrderEvent event = queue.take();        // waits if the queue is empty
            notifier.send(event);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();         // stop cleanly on shutdown
    }
}

The queue is bounded (it holds at most 1,000 events). If workers fall behind, put makes producers wait instead of filling memory. This is called back pressure. Do not use this pattern when the caller needs the result now: a payment answer cannot wait in a queue.

What to say in the round

Interviewers often ask "what if two customers book the last place at once?" A strong answer has four parts, in this order:

1. Name the race. "Reading the count and adding a booking is check-then-act, so two threads can both see a free place."
2. Fix it in your code. "In this program I lock per slot, inside SlotBookingService, so callers cannot forget."
3. Say what changes with many servers. "In production, a Java lock is not enough. I would use a version check or a row lock in the database."
4. Name the trade-off. "Optimistic is cheaper when conflicts are rare. For a busy slot, I would lock."

If you build the notification queue, start its consumers with an ExecutorService, a Java class that runs a fixed pool of worker threads for you. On shutdown, call shutdownNow. It interrupts the workers, so take throws InterruptedException and each loop ends cleanly. Saying this shows you thought about how the program stops, not only how it starts.

📌 Summary: Double booking is check-then-act on shared capacity. Lock per slot when conflicts are common; use a version check when they are rare. A bounded BlockingQueue hands slow work to workers.

What Arjun learns next

Arjun now has the parts: classes, patterns, diagrams and thread safety. Next week puts them on a clock. Module 11 is the machine-coding round itself: how to spend 90 minutes, what to build first, and what to skip.

Check your understanding

1. SwiftKart runs the slot service on 12 servers. Arjun adds `synchronized` to `book()`. Why can slots still be double booked?
2. Two threads read slot S18 at version 7. Thread 1 saves with "only if version is 7" and succeeds. What happens when thread 2 tries the same save?
3. At 6 pm on Saturday, hundreds of customers book the last few places in the same popular slot. Which choice fits best, and why?
4. Checkout threads `put` notification events into an `ArrayBlockingQueue` of size 1,000. Workers fall behind and the queue fills up. What does the next `put` do?