System requirements

Functional:

• The system should have a convenient and simple user interface.
• The users can swap their shifts with colleagues according to the schedule
• The users can get the history of their successful shift swap.
• The user uses the client application, in which the user can swap shifts with other employees and view the history of previous shift swaps.
• The users have 2 roles: employee and manager. A manager should approve the employee shift swap.
• The shift swap is a multi-step process: employees agree on the shift swap, and their managers should approve it as well.
• The system resolves the conflict if a few employees want to swap the same shift simultaneously.
• The users should be notified in the client application if the shift swap is completed or canceled.

Non-Functional:

• The system guarantees compliance with labor laws and fairness measures to prevent favoritism and unequal shift distribution.
• The system stores the shift history for one year.
• The users can see only the other shifts approved by a manager.
• The system should be reliable and available even under high load.
• The user can make a shift swap up to one week in advance.
• If the client application loses the connection to the backend, the client retries the last operation.
• The client application works on mobile and platforms.

API design

Here's a breakdown of the essential REST

API

User service:

PUT /auth/v1/login - authenticate a user

{

"login": "user1"

"pass_hash": "90AB787887878F"

}

Response: HTTP 200 and JWT token or HTT P 403 if the credentials are invalid.

PUT /auth/v1/logout/ - log out user

{

"login": "user1"

}

Response: HTTP 200 if login and JWT are valid or HTTP 403 if JWT is invalid or absent in HTTP headers.

POST /auth/v1/register - register new user:

{

"name": "user1"

"email": "[email protected]"

"phone": "0283929382829"

"manager_id": "232323323"

}

Response: HTTP 201 and employee_id of the new user or HTTP 403 if the JWT is invalid or absent in HTTP headers.

GET /user/v1/manager/{employee_id}

Response: HTTP 200 and the manager information:

{

'employee_id': "28382329082"

'name': "user1"

'email': "[email protected]"

"phone": "928329329"

'manager_id': "92839238293"

}

Otherwise, HTTP 403 if JWT is absent in the HTTP header or invalid

Employee shift matching service:

PUT /shift_matching/v1/swap/{employee_id}/{srcshift_id}/{target_shift_id} - try to swap the the shift {src_shift_id} with the shift {target_shift_id} for employee {empoloyee_id}

Response: HTTP 200 and

{ "swap_id": "9829389293",

"status": "IN_PROGRESS"|

"APPROVED_BY_OTHER_EMPLOYEE"|"CANCELED"|"COMPLETED",

"createdAt": "01/22/2025:08:09:01"

}

Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

GET /shift_matching/v1/swap/{employee_id}/status/{swap_id} - Response HTTP 200 and the swap status:

{ "swap_id": "1233333"

"status": "IN_PROGRESS" | "COMPELETED"| "APPROVED_BY_EMPLOYEE" | "CANCELED"

"createdAt": "01/10/2025:09:10:23"

}

Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

GET /shift_matching/v1/shift/{employee_id}

Response: HTTP 200 and the shift list:

{

[

'shift_id': "1234444",

'employee_id': '23232323'

'start_time': "01/10/2025:09:10:23",

'end_time': "01/11/2025:09:10:23",

'last_swap_date': "01/11/2025:09:10:23",

'status': 'ACTIVE' | 'PENDING' | 'CANCELED'

]

}

Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

PUT /shift_matching/v1/swap/manager/{manager_id}/approve/{swap_id} - a manager approves the suggested shift if both employees agree.

Response: HTTP 200 or

Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

Employee Shift service:

GET /employee_shift/v1/shift/{employee_id}/shifts?startDate=01/10/2025:09:10:23&endDate=01/10/2025:09:10:23&offset=1&pageSize=10 - Response HTTP 200 and return the list of shifts belonging to the employee:

{ "employee_id":'12223232',

"shifts":[

{ "shift_id" : '2323232'

"startFrom": '01/02/2025:09:10:23',

"endTo": '01/10/2025:09:10:23',

'status': 'ACTIVE' | 'PENDING' | 'CANCELED',

'last_swap_date': '01/10/2025:09:10:23'

} ]

}

Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

POST /employee_shift/v1/shift/{employee_id}

Persist new shift for an employee.

body request:

{ 'shift_id' : '1121212121',

'employee_id': '22323232',

'start_date': '01/02/2025:09:10:23',

'end_date': '01/02/2025:09:10:23',

'status': 'ACTIVE' | 'PENDING' | 'CANCELED',

'last_swap_date': '01/02/2025:09:10:23'

}

Response HTTP 201.Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

PUT /employee_shift/v1/shift/{employee_id}

Update the shift information for an employee.

The body request:

{ 'shift_id' : '1121212121',

'employee_id': '22323232',

'start_date': '01/02/2025:09:10:23',

'end_date': '01/02/2025:09:10:23',

'status': 'ACTIVE' | 'PENDING' | 'CANCELED',

'last_swap_date': '01/02/2025:09:10:23'

}

Response HTTP 200. Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

Notification Service:

Uses the WebSocket to send updates to the client application.

PUT /notification/v1/notify

The request body:

{

'employee_id': '1121221212121',

'message': 'Please confirm the swap',

'url': 'http://blabla.com/callback',

'email': '[email protected]',

'phone': '131232323232',

'expired_at': '01/02/2025:09:10:23'

}

Response: HTTP 200. Otherwise, HTTP 403 if the JWT is invalid or absent in the HTTP headers.

High-level design

Load Balancer and API Gateway (LB)

Load Balancer:

Distributes incoming HTTP requests accross

multiple application services. The LB ensures no single server is overwhelmed and enables horizontal scaling. It also health-checks servers and stops seding traffic to any that are down, and provides DDoS protection and TLS termination, and routes the requests to the right service nodes.

The User service:

• Log in the user and assign them a new JWT.
• Log out the user
• register new user

The Employee shift matching service:

• A shift has the following statuses: active, in progress, and canceled.
• A swap has the following statuses:

"IN_PROGRESS", "COMPLETED", "APPROVED_BY_OTHER_EMPLOYEE", "CANCELED"

• Query the current employee shift swap status.
• Query the possible shifts for an employee can pick to swap. The service provides only the shifts in status 'active ', excluding the race condition for the shift. This list is built using the Hungarian algorithm. The service takes the employee's closest shifts and builds the possible shifts to swap.
• Try to swap shifts with another employee. After the employee can request the shift status with the client application.
• Approve the other employee's proposition to swap shifts by an employee.
• Approve the confirmed by two empoyees shift swap by their manager.
• Send the approved shift swap to the Employee Shift service with Kafka.
• If users want to swap the same shift swap simultaneously, the employee who first sets up the Redis lock with the name being the swap_id, would swap the shift. If the Redis lock expires and the employee who acquired the Redis lock doesn't get the approvals from another employee and manager, then the shift would be available for other employees.
• Use Redis to cache shift information: shift_id,employee_id, shift status and etc.

The Employee shift service:

• Persists a shift's information in Postgres, receiving updates from the Employee shift matching service with Kafka.
• Hold the last 100 swap shifts of an employee and return them to the Employee shift matching service.

The client application:

• Support the mobile and web platform
• Uses long-polling to get the swap statuses from the Employee shift matching service
• Show the possible shifts to swap getting from the Employee shift matching service
• Retry the operation if the client application loses the connection to the backend.

The Kafka:

• event streaming platform to process the shift update events.

The Postgres:

• Hold the user and shift information

The Redis:

• cache the employee shift information

The notification service:

• Notify the employees with SMS, email, and WebSocket that they have to consider or decline the shift swap.
• Utilise the External SMTP/SMS service

The External SMTP/SMS service:

• Reliable sends the email or SMS to the client.

Detailed component design

All the services can be deployed to AWS EKS and would be managed by Kubernetes.

The API Gateway:

Distributes the user requests evenly and hides the API behind the API Gateway, also it routes the request by using the lsito service mesh to build the Microservice architecture. The employee_id may be used as a sharding key to distribute the user request evenly.

The Employee shift matching service:

This is an essential service, and it's used to match the given employee shift. The service prepared the possible shift swap using the Hungarian algorithms and returns the list of shifts to the user. This service returns the swap status update to the client application that uses the Websocket to connect to the Notification service and HTTP to get the shift swap status. The service asks the User service to get employee's manage_id. This service is stateless, and if it's down, this service just reads the necessary information from the Employee Shift service and the client application and puts them into Redis. This service is orchestrated by Kubernetes, which cares about the service health and availability. We can use the Kubernetes autoscaling mechanism to regulate the resources to process the user requests efficiently. It cares if some shift swap is hanging over 1 day; it would be evicted from Redis as outdated.

If the employee proposes the shift swap, this service sends the message to the Notification service to notify other employee and the manager to consider the swap proposal.

The possible shift recommendation to swap:

We use the Hungarian algorithm to build the possible list of shifts to swap for the employee. We represent the shift as nodes and edges as possible swaps. Every swap has a weight that may include shift start date and shift duration, and current time. If the shift is the closer to current time, those edges would have less weights. Also employee can see only the shifts of employees having the same managers. If a swap completes, the service rebuilds the shift recommendation list for the employee. Also, the Employee shift matching service should store the graph information as adjacency list, for instance.

The shift swap flow:

Initially, the shift has an active status. If an employee starts making the new shift swap, shift and new swap are changed the status to in_progress, and nobody can use this shift to swap. If another employee approves the swap, the shift swap status is changed to APPROVED_BY_OTHER_EMPLOYEE, and if the manager approves it, the swap is considered as COMPLETED, and the Employee shift matching service sends the shift update to Kafka. The Employee shift service receives this and updates the new shift information.

The shift swap conflict resolution:

Two or more employees pick the same shift simultaneously, which causes conflicts. The first employee who sets up the lock in Redis with the name being shift_id would swap the shift. The Redis lock would have TTL, and when this lock expires, another employee may swap this shift.

The Hungarian algorithm description:

Use 2D matrix: the rows are employees and the columns are possible shifts the employee can swap. The matrix cells contain the costs, if employee can't swap to the shift, the matrix cell would contain a big number as cost. Other matrix cells contain the cost calculated as 1 / startDate of shift. Such matrices would be calculated for every 2 weeks. If some shift is not accessible, that matrix cell would contain very big number as cost to ignore this shift. Below are the common steps of the algorithm:

1. Row Reduction: Subtract the row min from each row.
2. Column Reduction: Subtract the column min from each column.
3. Cover Zeros: Cover all zeros with the minimum number of lines (K).
   • If K = n, an optimal assignment exists among the zeros. Go to Step 5.
   • If K < n, go to Step 4.
4. Matrix Adjustment:
   • Find the smallest uncovered value.
   • Subtract it from all uncovered elements.
   • Add it to all elements covered by two lines.
   • Go back to Step 3.
5. Final Assignment: Make the assignment by selecting n zeros, one in each row and column

The Redis cluster:

The Redis cluster is isolated from the Employee shift matching service. The Redis cluster is a highly available and fault-tolerant solution. A Redis cluster of multiple nodes. We could use Redis with replication (master-slave) and partitioning (sharding keys across nodes). The are also managed services like AWS ElastiCache. For simplicity, assume we have a few Redis nodes and a consistent hashing or cluster mode to distribute keys.

The client application:

The client application is developed to have a comfortable and simple interface for employees. It shows the possible shifts, requests the swap status from the Employee shift matching service. Also, if the Employee shift service is down, it may resend the last information about the swap shift. The client application connects with the Notification service to get the shift swap notification.

The Notification service:

Connects to the client application to notify the employees in the client application about the shift swap to approve. Hold the network websocket connection information in Redis. The notification service is statefull and would be managed by Kubernetes. It uses the istio to build the consistent hashing by emploee_id to process the request efficiently. It duplicates and sends the notification using email. It connects to The External SMTP/SMS service to send the emails and sms to the employees and managers to consider the shift swap.

The User service:

Handles the login and logout requests. If the user logs in successfully, the User service assigns JWT to authenticate the following user requests to other microservices. This service can register the new user as either an employee or a manager and persists them to Postgres. This service is stateless, and it would be managed by Kubernetes. We would deploy a few instances of the servcie to process the user requests efficently. Postgres may be sharded by emploee_id,where one Postgres instance handles the request for employee_id hash ring as consistent hashing. The key generator could be implemented as an internal library.

Statelessness and Scaling

Because all states is in the storage and cache, the app servers except the Notification service,don't hold any persistent state between requests. Ths means we csn scale out by just adding more servers behind the LB. If one server fails mid-request, the request fails but cleint application can retry and another server handle it.

Autoscaling

We can set up the infrastructure to monitor CPU, memory, or request rate on the app servers and automatically launch more instances during high load. Because of the LB, new instances can start receiving traffic as soon as they're up. Similarly, in low load, some instances can be shut down. This elasticity ensures we handle millions of users at peak, but don't waste resources at off-peak.

External SMTP/SMS service:

The notification service could use the external SMTP cloud service to send notifications about the shift swaps.

Database design

User service:

Uses Postgres to hold the user information because we need to support strong consistency in SQL storage:

The user table:

employee_id : the unique key string 128 bytes

name: string 128 bytes

email: string 256 bytes

role: string 'employee' or 'manager'

manager_id: string 128 bytes

createAt: timestamp 4 bytes

loggedIn: boolean 1 bytes

LastLogin: timestamp 4 bytes

The employee shift service:

Utilizes Postgres to store the shift information.

The shift table:

shift_id: string 128 bytes, the unique key

the employee_id: string 128 bytes

start_date: timestamp

end_date: timestamp

status: byte

The swap_history table:

swap_id: string 128 bytes

src_emploee_id1: string 128 bytes

src_shift_id: string

target_ employee_id: string 128 bytes

target_shift_id: string 128 bytes

swapped_at: timestamp 4 bytes

Capacity estimation:

So it takes 2 kbytes to store all tables, and it takes 80 megabytes for 1 year, it takes 1 gigabyte for 5 years. (We're going to hold one replication copy)

Request flows

Trade offs/Tech choices

Choose to share one swap matrix between all the Employee shift matching service instances, whereas it's better to create a structure to partition that by shift_id between the

Employee shift matching service instances.

Need to invent the mechanism to restore the last swap shift information from the client application if the Employee shift matching service is down and loses the information, now it ignores that moment.

Failure scenarios/bottlenecks

The system would be deployed to AWS EKS and the service container would be orchestrated by Kubernetes.

If client applications request the swap history information frequently it gives the high load to Postgres and it may be cached.

If many employees would request changes of the swap shift intensively, it causes the race condition in Redis, so it's better to shard this process.

Future improvements

we improve this service in future by spending time on choose other object store.