Requirements

Functional Requirements:

• Allow employees to propose shift swaps with colleagues via the client application.
• Enable a multi-step approval workflow: employee agreement followed by manager approval.
• Resolve conflicts when multiple employees request to swap the same shift simultaneously using distributed locks or optimistic concurrency.
• Notify users of shift swap status changes in real time via WebSocket with email and SMS fallback channels.

Non-Functional Requirements:

• Assuming 1 million active employees, and each employee sends 2 shift swap requests per day on average, the peak write QPS should be around 50, and the read QPS should be around 200. This is fairly small for a modern distributed system.
• When an employee is already requesting to swap for a shift, the workflow has 24 hours to be approved. Before then, any further request to swap this shift will be rejected.
• We need to store the shift information, associated user, as well as the swapping flow information. Assuming 10 shits per user, each user's each shift information takes 10kb to store. The total storage volume is 10GB, this is very small for a modern database cluster.

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

Here are a few APIs:

For employees to start shift swaps:

POST v1/request_shift_swap {

request_employee_id: UUID,

current_shift_id: UUID,

swap_shift_id: UUID,

swap_employee_id: UUID,

}

For employees to respond to shift swap:

POST v1/employee_respond_shift_swap {

request_employee_id: UUID,

current_shift_id: UUID,

swap_shift_id: UUID,

swap_employee_id: UUID,

is_approve: Boolean

}

For managers to respond to shift swap:

POST v1/manager_respond_shift_swap {

request_employee_id: UUID,

current_shift_id: UUID,

swap_shift_id: UUID,

swap_employee_id: UUID,

is_approve: Boolean

}

For employees to see their current shifts:

GET v1/view_shifts {

current_employee_id: UUID

}

For employees to view recommended shifts for swapping:

GET v1/view_swap_recommendations {

current_employee_id: UUID

}

For employees to authenticate and log in:

POST v1/login {

user_name: String,

company_email: String,

hashed_password: String

}

For notifications, we won't use any APIs. Instead, we will use an event-driven approach.

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

In this system, we have 2 relational databases, that separately stores information about shift and employee themselves. Data models are like:

table employees {

employee_id: UUID,

employee_name: String,

employee_start_date: Date,

employee_title_name: String,

...

}

table shifts {

shift_id: UUID,

shift_employee_id: UUID,

shift_start_time: Timestamp,

shift_end_time: Timestamp,

...

}

For the relational databases, we don't need caching layer, sharding or replicas in this case, since neither the data volume nor the data size is large.

All requests from employee clients are sent to the API gateway before they reach the servers. This way, we can handle authentication and rate limiting. An employee needs to log in with their username and password first before they can make any requests.

1. When an employee wants to view the available shifts, we route a request to the shift service, and queries the shift data table in the relational db for this employee to request swaps.
2. When a user requests to swap to a shift. We do the following: We first read the shift data relational table, as well as the employee db relational table, and get back the information about the shift, the employees to swap. After we get back the metadata we need, we trigger the shift approval workflow. In this flow, we use web sockets to send real-time requests to the relevant employee and the manager, for them to accept the request. If the request isn't accepted within 10 minutes, we trigger the email server and message server, to send reminder emails and text messages to the relevant employee and manager. Once the request is approved by both the relevant employee and manager, we write to the shift data table in the database, to override the employees associated with the relevant shifts, and return as success. If no approvals within 24 hours, we treat the shift swap as failure. We then trigger a cancellation workflow: We notify the employees and manager through websocket about the failing request. We release the distributed locks held by the corresponding shift row. We write the expired requests to analytics database, through message queue. We do a scheduled cleanup of the analytics database for remote events, and we use the logged data to generate reports and metrics.
3. When two employees simultaneously request shift swaps for the same shift, whoever requests first will acquire a distributed lock on the row for the associated shift. Whoever acquires the lock has 24 hours to finish the overall approval process, before the lock is automatically released.
4. Currently, we have 1 million employees and the peak QPS for read is 200 and for write is 50. Even if our employees count is to increase by 5 times (becoming the largest employer in the U.S.), the peak QPS for read will be 1000 and for write will be 250. In this case, we can create database replicas to handle the additional read/write. In our case, we want to make sure we have strong consistency, different replicas should serve the same shift information to different clients, so all writes will need to be synchronously acknowledged by all database replicas. This increases latency but guarantees strong consistency. In case of database replica failure, the remaining replicas will handle the traffic until the failed replica recovers. For even 1000 RPS, it still can easily handled by our database replica, we don't need to build a caching layer.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

In this system, we have 2 relational databases, that separately stores information about shift and employee themselves. Data models are like:

table employees {

employee_id: UUID,

employee_name: String,

employee_start_date: Date,

employee_title_name: String,

...

}

table shifts {

shift_id: UUID,

shift_employee_id: UUID,

shift_start_time: Timestamp,

shift_end_time: Timestamp,

...

}

For the relational databases, we don't need caching layer, sharding or replicas in this case, since neither the data volume nor the data size is large.

All requests from employee clients are sent to the API gateway before they reach the servers. This way, we can handle authentication and rate limiting. An employee needs to log in with their username and password first before they can make any requests.

1. When an employee wants to view the available shifts, we route a request to the shift service, and queries the shift data table in the relational db for this employee to request swaps.
2. When a user requests to swap to a shift. We do the following: We first read the shift data relational table, as well as the employee db relational table, and get back the information about the shift, the employees to swap. After we get back the metadata we need, we trigger the shift approval workflow. In this flow, we use web sockets to send real-time requests to the relevant employee and the manager, for them to accept the request. If the request isn't accepted within 10 minutes, we trigger the email server and message server, to send reminder emails and text messages to the relevant employee and manager. Once the request is approved by both the relevant employee and manager, we write to the shift data table in the database, to override the employees associated with the relevant shifts, and return as success. If no approvals within 24 hours, we treat the shift swap as failure. We then trigger a cancellation workflow: We notify the employees and manager through websocket about the failing request. We release the distributed locks held by the corresponding shift row. We write the expired requests to analytics database, through message queue. We do a scheduled cleanup of the analytics database for remote events, and we use the logged data to generate reports and metrics.
3. When two employees simultaneously request shift swaps for the same shift, whoever requests first will acquire a distributed lock on the row for the associated shift. Whoever acquires the lock has 24 hours to finish the overall approval process, before the lock is automatically released.
4. Currently, we have 1 million employees and the peak QPS for read is 200 and for write is 50. Even if our employees count is to increase by 5 times (becoming the largest employer in the U.S.), the peak QPS for read will be 1000 and for write will be 250. In this case, we can create database replicas to handle the additional read/write. In our case, we want to make sure we have strong consistency, different replicas should serve the same shift information to different clients, so all writes will need to be synchronously acknowledged by all database replicas. This increases latency but guarantees strong consistency. In case of database replica failure, the remaining replicas will handle the traffic until the failed replica recovers. For even 1000 RPS, it still can easily handled by our database replica, we don't need to build a caching layer.