Concurrency considerations in LLD - System Design Exercise

Design: Concurrency Management System

Design focuses on concurrency control mechanisms and resource access management. Does not cover network protocols or UI design.

Functional Requirements

FR1: Allow multiple users or processes to access shared resources safely

FR2: Prevent data corruption due to simultaneous updates

FR3: Ensure system remains responsive under concurrent load

FR4: Support locking mechanisms to control access

FR5: Handle deadlocks and race conditions gracefully

Non-Functional Requirements

NFR1: Support up to 1000 concurrent users/processes

NFR2: Response time for resource access requests should be under 200ms

NFR3: System availability target is 99.9% uptime

NFR4: Minimal overhead added by concurrency controls

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Lock manager to grant and release locks

Resource manager to track resource states

Deadlock detection and resolution module

Queue or scheduler for managing waiting requests

Logging for audit and debugging

Design Patterns

Pessimistic locking

Optimistic concurrency control

Two-phase locking

Deadlock detection algorithms

Wait-die and wound-wait schemes

Reference Architecture

  +-------------------+       +-------------------+       +-------------------+
  |   Client/Process  | <---> |   Lock Manager    | <---> | Resource Manager  |
  +-------------------+       +-------------------+       +-------------------+
           |                          |                           |
           |                          |                           |
           |                          v                           |
           |                 +-------------------+               |
           |                 | Deadlock Detector |               |
           |                 +-------------------+               |
           |                          |                           |
           +------------------------------------------------------+

Components

Client/Process

Any programming environment

Requests access to shared resources

Lock Manager

In-memory lock table

Grants and releases locks to control resource access

Resource Manager

Data store or in-memory state

Tracks current state and ownership of resources

Deadlock Detector

Graph-based detection algorithm

Detects cycles in wait-for graph and triggers resolution

Request Flow

1. Client requests access to a resource from Lock Manager

2. Lock Manager checks if resource is free or locked

3. If free, Lock Manager grants lock and updates Resource Manager

4. If locked, Client is queued and waits

5. Deadlock Detector periodically checks for cycles in waiting clients

6. If deadlock detected, Deadlock Detector selects victim and releases locks

7. Client releases lock after work is done, Lock Manager updates Resource Manager

8. Next waiting client is granted lock

Database Schema

Entities: - Resource: id, state, owner_lock_id - Lock: id, resource_id, client_id, lock_type (read/write), status - Client: id, metadata - WaitForGraph: edges representing waiting relationships between clients Relationships: - One Resource can have multiple Locks (shared or exclusive) - Locks belong to one Client - WaitForGraph edges connect Clients waiting for Locks held by others

Scaling Discussion

Bottlenecks

Lock Manager becomes a single point of contention under high concurrency

Deadlock detection overhead increases with number of clients and locks

Resource Manager state updates may slow down with many resources

Queue length grows causing increased wait times

Solutions

Partition Lock Manager by resource groups to distribute load

Use incremental or on-demand deadlock detection to reduce overhead

Cache resource states and batch updates to Resource Manager

Implement priority queues and timeout mechanisms to reduce wait times

Interview Tips

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

Explain why concurrency control is needed to prevent data corruption

Discuss pros and cons of pessimistic vs optimistic locking

Describe how deadlocks occur and how to detect and resolve them

Show understanding of scalability challenges and partitioning

Mention importance of balancing performance and correctness

Practice

1. What is the main purpose of using locks in concurrent systems?

easy

A. To allow unlimited access to shared resources

B. To prevent multiple threads from accessing shared data simultaneously

C. To speed up the execution of a single thread

D. To reduce memory usage in the system

Solution

1. Step 1: Understand concurrency risks

   When multiple threads access shared data at the same time, it can cause errors or inconsistent results.

2. Step 2: Role of locks

   Locks ensure only one thread accesses the shared data at a time, preventing conflicts and data corruption.

3. Final Answer:

   To prevent multiple threads from accessing shared data simultaneously -> Option B

4. Quick Check:

   Locks protect shared data = C [OK]

Hint: Locks protect shared data from simultaneous access [OK]

Common Mistakes:

• Thinking locks speed up single-thread execution
• Believing locks allow unlimited resource access
• Confusing locks with memory optimization

2. Which of the following is the correct way to acquire a lock in a typical low-level design?

easy

A. lock.notify() before accessing shared data

B. lock.release() before accessing shared data

C. lock.wait() after accessing shared data

D. lock.acquire() before accessing shared data

Solution

1. Step 1: Understand lock usage order

   To safely access shared data, a thread must first acquire the lock to block others.

2. Step 2: Correct method to acquire lock

   The method lock.acquire() is used to obtain the lock before accessing shared data.

3. Final Answer:

   lock.acquire() before accessing shared data -> Option D

4. Quick Check:

   Acquire lock first = A [OK]

Hint: Acquire lock before shared data access [OK]

Common Mistakes:

• Releasing lock before access
• Using wait or notify incorrectly
• Confusing acquire with release

3. Consider this pseudocode for two threads incrementing a shared counter without locks:

Thread 1: temp = counter
          temp = temp + 1
          counter = temp

Thread 2: temp = counter
          temp = temp + 1
          counter = temp

What is the possible final value of counter if it starts at 0?

medium

A. 2

B. Any negative number

C. 1

D. 0

Solution

1. Step 1: Analyze concurrent increments without locks

   Both threads read the same initial value 0, increment it to 1, and write back 1, causing one increment to be lost.

2. Step 2: Determine final counter value

   Because of race condition, the counter may only increase once, resulting in final value 1 instead of 2.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Race condition causes lost update = 1 [OK]

Hint: Without locks, increments can overwrite each other [OK]

Common Mistakes:

• Assuming both increments always succeed
• Ignoring race conditions
• Thinking counter can be negative here

4. In the following code snippet, what is the main concurrency issue?

lock.acquire()
shared_data.append(1)
# Missing lock.release()

medium

A. Deadlock due to missing lock release

B. Data race on shared_data

C. Syntax error in lock usage

D. No issue, code is safe

Solution

1. Step 1: Identify missing lock release

   The code acquires a lock but never releases it, so other threads waiting for the lock will block forever.

2. Step 2: Understand deadlock impact

   This causes a deadlock where threads cannot proceed, halting system progress.

3. Final Answer:

   Deadlock due to missing lock release -> Option A

4. Quick Check:

   Missing release causes deadlock = A [OK]

Hint: Always release locks after acquiring [OK]

Common Mistakes:

• Thinking it's a syntax error
• Assuming no issue without release
• Confusing deadlock with data race

5. You design a system where multiple threads read and write a shared cache. To improve performance, you want to allow multiple readers but only one writer at a time. Which concurrency control mechanism fits best?

hard

A. Use a read-write lock allowing concurrent reads but exclusive writes

B. Use a simple mutex lock for all access

C. Use no locks and rely on thread scheduling

D. Use a semaphore with count 1 for all operations

Solution

1. Step 1: Understand concurrency needs for readers and writers

   Multiple readers can safely access shared data simultaneously, but writers need exclusive access to avoid conflicts.

2. Step 2: Choose appropriate lock type

   A read-write lock allows many readers at once but only one writer, balancing concurrency and safety efficiently.

3. Final Answer:

   Use a read-write lock allowing concurrent reads but exclusive writes -> Option A

4. Quick Check:

   Read-write lock fits multiple readers, single writer = B [OK]

Hint: Read-write locks allow many readers, one writer [OK]

Common Mistakes:

• Using simple mutex reduces concurrency
• Ignoring need for exclusive write access
• Relying on no locks causes data races