Booking conflict resolution in LLD - System Design Exercise

Design: Booking Conflict Resolution System

Design focuses on booking conflict detection and resolution logic, API design, and data model. User interface and payment integration are out of scope.

Functional Requirements

FR1: Allow users to create bookings for resources (e.g., rooms, equipment) with start and end times

FR2: Prevent overlapping bookings for the same resource

FR3: Support concurrent booking requests without conflicts

FR4: Provide immediate feedback if a booking conflicts with existing bookings

FR5: Allow users to view existing bookings for a resource

FR6: Support cancellation and modification of bookings

Non-Functional Requirements

NFR1: Handle up to 1000 concurrent booking requests

NFR2: API response time p99 under 200ms for booking creation

NFR3: System availability 99.9% uptime

NFR4: Data consistency to prevent double bookings

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

API server to handle booking requests

Database to store bookings and resource info

Locking or transaction mechanism to prevent conflicts

Cache layer for quick availability checks

Notification system for booking confirmations or conflicts

Design Patterns

Optimistic concurrency control

Pessimistic locking

Time interval tree or range index for conflict detection

Eventual consistency with conflict resolution

Retry mechanism for failed booking attempts

Reference Architecture

Client
  |
  v
API Server (REST)
  |
  v
Booking Service --- Cache (Redis) 
  |
  v
Database (PostgreSQL)

Legend:
- Client sends booking requests
- API Server validates and forwards to Booking Service
- Booking Service checks cache and database for conflicts
- Uses transactions to ensure no overlapping bookings
- Cache updated after successful booking

Components

API Server

Node.js/Express or similar

Receive booking requests, validate input, and forward to booking service

Booking Service

Backend service in any language (e.g., Python, Java)

Core logic for conflict detection, booking creation, cancellation, and modification

Cache

Redis

Store recent booking intervals per resource for fast conflict checks

Database

PostgreSQL

Persist booking data with transaction support to ensure consistency

Request Flow

1. Client sends booking request with resource ID, start time, and end time to API Server

2. API Server validates request format and authentication

3. API Server forwards request to Booking Service

4. Booking Service queries Redis cache for existing bookings of the resource in the requested time range

5. If cache miss or uncertain, Booking Service queries PostgreSQL database for overlapping bookings

6. If no conflicts found, Booking Service starts a database transaction

7. Booking Service inserts new booking record and commits transaction

8. Booking Service updates Redis cache with new booking interval

9. Booking Service returns success response to API Server

10. API Server sends confirmation to client

11. If conflict detected, Booking Service returns conflict error to API Server

12. API Server informs client about booking conflict

Database Schema

Entities: - Resource (resource_id PK, name, type, description) - Booking (booking_id PK, resource_id FK, user_id FK, start_time, end_time, status) Relationships: - Resource 1:N Booking (one resource can have many bookings) Constraints: - Booking time intervals must not overlap for the same resource - Use database transaction isolation (e.g., SERIALIZABLE or explicit locking) to enforce this

Scaling Discussion

Bottlenecks

Database write contention when many concurrent bookings target the same resource

Cache consistency issues leading to stale availability data

API server overload with high request volume

Latency increase due to complex conflict detection queries

Solutions

Partition bookings by resource to reduce contention; use row-level locking or optimistic concurrency control

Implement cache invalidation or update strategies after booking changes to keep cache fresh

Scale API servers horizontally behind load balancers

Use efficient range indexing (e.g., GiST indexes in PostgreSQL) to speed up conflict queries

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing components and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing

Emphasize importance of preventing overlapping bookings to maintain data integrity

Discuss trade-offs between optimistic and pessimistic concurrency control

Explain how caching improves performance but requires careful consistency management

Highlight use of database transactions and indexing for conflict detection

Mention scaling strategies to handle concurrent booking requests

Practice

1. What is the primary goal of booking conflict resolution in a system?

easy

A. To ignore booking times and accept all requests

B. To allow multiple bookings at the same time for efficiency

C. To delete all previous bookings automatically

D. To prevent overlapping reservations for the same resource

Solution

1. Step 1: Understand booking conflict concept

   Booking conflict resolution ensures no two bookings overlap for the same resource.

2. Step 2: Identify the goal of conflict resolution

   The goal is to prevent double-booking by checking time overlaps and rejecting or adjusting conflicting bookings.

3. Final Answer:

   To prevent overlapping reservations for the same resource -> Option D

4. Quick Check:

   Conflict resolution = prevent overlaps [OK]

Hint: Conflict resolution means no double bookings allowed [OK]

Common Mistakes:

• Thinking multiple bookings at same time are allowed
• Assuming conflict resolution deletes bookings
• Ignoring time overlaps in bookings

2. Which of the following code snippets correctly checks if two time intervals (start1, end1) and (start2, end2) overlap?

easy

A. if start1 < end2 and start2 < end1: overlap

B. if start1 > end2 or start2 > end1: overlap

C. if end1 <= start2 or end2 <= start1: no overlap

D. if start1 == end2 or start2 == end1: overlap

Solution

1. Step 1: Understand time interval overlap condition

   Two intervals overlap if one starts before the other ends and vice versa.

2. Step 2: Match condition to code

   Condition start1 < end2 and start2 < end1 correctly detects overlap.

3. Final Answer:

   if start1 < end2 and start2 < end1: overlap -> Option A

4. Quick Check:

   Overlap check = start1 < end2 and start2 < end1 [OK]

Hint: Overlap if intervals cross each other in time [OK]

Common Mistakes:

• Using <= instead of < causing false negatives
• Confusing no overlap with overlap conditions
• Checking equality as overlap incorrectly

3. Given existing bookings: [(10, 12), (14, 16), (18, 20)], what will be the result of checking a new booking (12, 14) for conflict using the overlap condition start1 < end2 and start2 < end1?

medium

A. Conflict with (10, 12)

B. Conflict with (14, 16)

C. No conflict

D. Conflict with all existing bookings

Solution

1. Step 1: Check overlap with each existing booking

   Check (12,14) against (10,12): 12 < 12 is false, no overlap. Against (14,16): 12 < 16 true, 14 < 14 false, no overlap. Against (18,20): no overlap.

2. Step 2: Determine conflict result

   No overlaps found with any existing booking intervals.

3. Final Answer:

   No conflict -> Option C

4. Quick Check:

   New booking fits between existing without overlap [OK]

Hint: Check each existing booking for overlap carefully [OK]

Common Mistakes:

• Assuming touching intervals overlap
• Ignoring strict less than condition
• Confusing start and end times

4. Identify the bug in this booking conflict check code snippet:

def is_conflict(new_start, new_end, existing_bookings):
    for start, end in existing_bookings:
        if new_start <= end and new_end >= start:
            return True
    return False

medium

A. The condition incorrectly uses <= and >= causing false conflicts

B. The condition allows bookings that end exactly when another starts

C. The function does not return anything

D. The loop does not iterate over bookings

Solution

1. Step 1: Analyze the overlap condition

   Condition new_start <= end and new_end >= start includes cases where bookings just touch at edges, causing false conflicts.

2. Step 2: Correct condition for strict overlap

   Use new_start < end and new_end > start to detect true overlaps only.

3. Final Answer:

   The condition incorrectly uses <= and >= causing false conflicts -> Option A

4. Quick Check:

   Use strict inequalities for overlap [OK]

Hint: Use < and >, not <= or >= for overlap checks [OK]

Common Mistakes:

• Using inclusive operators causing false positives
• Forgetting to return a boolean
• Not iterating over all bookings

5. You are designing a booking system for meeting rooms. To handle conflict resolution at scale, which approach is best to ensure no overlapping bookings and high performance?

hard

A. Use a centralized lock on the entire booking database for each new booking

B. Check for conflicts by querying only relevant time slots and use optimistic concurrency control

C. Allow all bookings and resolve conflicts manually later

D. Store bookings without timestamps and rely on user honesty

Solution

1. Step 1: Understand scalability and conflict resolution needs

   Centralized locking (Use a centralized lock on the entire booking database for each new booking) causes bottlenecks; manual or no checks (Options C, D) cause errors.

2. Step 2: Choose efficient conflict detection method

   Querying only relevant time slots reduces load; optimistic concurrency control handles race conditions efficiently.

3. Final Answer:

   Check for conflicts by querying only relevant time slots and use optimistic concurrency control -> Option B

4. Quick Check:

   Efficient conflict check + concurrency control = scalable solution [OK]

Hint: Query relevant slots + optimistic control for scalable conflict resolution [OK]

Common Mistakes:

• Using global locks causing slowdowns
• Ignoring concurrency issues
• Not filtering bookings by time before checking