Java & AI: What Developers Need to Know

Java LLD: High-Concurrency Ticket Booking System (BookMyShow)

Designing BookMyShow is a classic LLD interview favorite because it tests your ability to handle high concurrency without sacrificing data consistency. If you cannot explain how to prevent two users from booking the exact same seat simultaneously under heavy load, your system design interview is over.

The Mistake Most Candidates Make

• Global Database Locks: Using heavy database-level row locks (SELECT ... FOR UPDATE) which drastically reduces throughput during peak ticket sales.
• Linear Seat Scanning: Utilizing basic arrays or lists to search for contiguous seat allocations, resulting in slow $O(N)$ query times.
• Naïve Synchronization: Synchronizing the entire booking method block, which bottlenecks the entire system and prevents concurrent bookings across different theaters.

The Right Approach

• Core mental model: Isolate seat contention per show using in-memory semaphores, while managing contiguous seat boundaries using an Interval Tree.
• Key entities/classes: Show, Seat, ShowSeatManager, IntervalTree, Booking.
• Why it beats the naive approach: It localizes lock contention to individual shows instead of the entire database, enabling millions of concurrent users to book different shows simultaneously.

Shameless plug: javalld.com has full LLD implementations with step-by-step execution traces — free to use while prepping.

The Key Insight (Code)

public class ShowSeatManager {
    private final Semaphore showLock = new Semaphore(1); // Isolate lock per show
    private final IntervalTree bookedSeats = new IntervalTree(); 

    public boolean reserveSeats(int start, int end) {
        if (!showLock.tryAcquire()) return false; // Fail fast under heavy load
        try {
            if (bookedSeats.hasOverlap(start, end)) {
                return false; // Already booked
            }
            bookedSeats.insert(start, end);
            return true;
        } finally {
            showLock.release();
        }
    }
}

Key Takeaways

• Thread Confinement via Semaphores: Use a dedicated Semaphore per show to localize concurrency, ensuring that high demand for a blockbuster movie doesn't block bookings for other shows.
• Interval Tree for Range Queries: Optimize contiguous seat selection; checking if a range of seats (e.g., seats 10 to 15) is available drops from $O(N)$ to $O(\log N)$ complexity.
• Optimistic Locking Safety Net: Pair your in-memory locks with database optimistic locking (@Version) as a final line of defense to guarantee zero double-bookings.

Full working implementation with execution trace available at https://javalld.com/problems/bookmyshow

---JSON
{
"title": "Java LLD: High-Concurrency Ticket Booking System (BookMyShow)",
"tags": ["java", "design", "concurrency", "systemdesign"]
}
---END---