Loading...
Scale Requirements
GET /problems?start={start}&end={end}
Get problems in a range. If start and end are not provided, get all problems with default page size.
Response Body:
{
problems: [
{
id: string,
title: string,
difficulty: string
}
]
}
GET /problems/{problem_id}
Get problem details, including description, constraints, examples, and starter code.
Response Body:
{
id: string
title: string
difficulty: string
description: string
constraints: string
examples: [{
input: string
output: string
}]
starter_code: {
language: string
code: string
}
}
POST /problems/{problem_id}/submission
Submit code for a problem and get results.
Response Body:
{
status: success | fail
test_cases: [
{ status: success | fail | timeout }
]
}
GET /contests/{contest_id}/leaderboard
Get leaderboard for a contest.
Response Body:
{
ranking: [
{ user_id: string, score: number }
]
}
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
Users should be able to view problem descriptions, examples, constraints, and browse a list of problems.
The design for viewing problems uses a standard three-tier architecture:
Client: Frontend application sending HTTP GET requests
Problems Service: Backend service with endpoints:
Database: Stores problem data (id, title, description, difficulty, examples, constraints)
This simple setup efficiently handles problem viewing requests while maintaining separation of concerns.
Users should be able to solve coding questions by submitting their solution code and running it against built-in test cases to get results. To design the code evaluation flow for our LeetCode-like platform, we need to consider the high concurrency requirement of 10,000 users participating in contests simultaneously, each submitting solutions about 20 times on average. We use a Code Evaluation Service as the entry point for code submissions. This service will be responsible for receiving code from users and initiating the evaluation process. However, to handle the high volume of submissions efficiently and securely, we introduce a Message Queue as a buffer between the submission process and the actual code execution. Note that most system design questions requires microservices. For a simpler problem like this, we can use a single service to handle both problem service and code evaluation. However, code submission can be compute heavy and we do not want to bring down the entire service when handling a large number of submissions. Therefore, we opt to separate the two services.
When a user submits a solution, the Code Evaluation Service pushes a message containing the submission details (user ID, problem ID, and code) to the Message Queue. This decouples the submission process from the execution process, allowing us to handle traffic spikes more effectively.
On the other side of the Message Queue, we have multiple Code Execution Workers. These workers continuously poll the queue for new submissions. When they receive a message, they fetch the necessary test cases from the Problems database, execute the code in a sandboxed environment, and record the results.
We will choose Container (Docker) as execution environment. To ensure security and isolation, each submission runs in a separate container, preventing malicious code from affecting our system or other users' submissions. We can use technologies like Docker for this purpose.
After execution, the results (including whether the code passed all test cases, execution time, and memory usage) are saved in the Submissions table.
This design allows us to scale horizontally by adding more Code Execution Workers as needed to handle increased load during peak times or popular contests. The use of a Message Queue also provides a level of fault tolerance - if a Code Execution Worker fails, the message remains in the queue and can be picked up by another worker.
User can participate in coding contest. The contest is a timed event with a fixed duration of 2 hours consisting of four questions. The score is calculated based on the number of questions solved and the time taken to solve them. The results will be displayed in real time. The leaderboard will show the top 50 users with their usernames and scores.
A contest itself is bascially four problems with a time window. Running the contest itself is straightforward. We can use a centralized service to manage the contest, Contest Service. After a user submits a solution, it's graded by the Code Evaluation Service as described in the previous section. The results are then sent to the Contest Service to record the user's score in the database.
The key decision here is where to store the contest data, user's score, and the leaderboard. We need real time updates for the leaderboard and data changes frequently. We can use an in-memory database like Redis to store the leaderboard. Redis is a fast, in-memory database that is well suited for high performance, real time data processing. Check the deep dive below for more details on how the leaderboard is implemented.
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
The Code Evaluation Service decides if a submission is correct by comparing the output of the code with the expected output.
Here's an example of how this works:
Requirement:
User submitted code:
def add(a, b):
return a + b
Test case files:
test_case_1.in
2, 3
test_case_1_expected_output.out
5
test_case_1.out
5
The Code Evaluation Service will run the code with the input and get an output file test_case_1.out. It will then compare test_case_1.out with test_case_1_expected_output.out. If they are the same, the submission is marked as correct. Otherwise, it's marked as incorrect.
If the code fails to execute, the submission is marked as failed. If the code execution time exceeds the time limit, the submission is marked as timeout.
Running the code in a sandboxed environment like a container already provides a measure of security and isolation. We can further enhance security by limiting the resources that each code execution can use, such as CPU, memory, and disk I/O. We can also use technologies like seccomp to further limit the system calls that the code can make.
To be specific, to prevent malicious code from affecting other users' submissions, we can use the following techniques:
Resource Limitation: Limit the resources that each code execution can use, such as CPU, memory, and disk I/O.
Time Limitation: Limit the execution time of each code execution.
System Call Limitation: Use technologies like seccomp to limit the system calls that the code can make.
User Isolation: Run each user's code in a separate container.
Network Isolation: Limit the network access of each code execution.
File System Isolation: Limit the file system access of each code execution.
Here's sample command while running docker run ...:
--cpus="0.5" --memory="512M" --cap-drop="ALL" --security-opt="seccomp=unconfined" --network="none" --read-only
This limits the code execution to use at most 0.5 CPU, 512 MB of memory, and disable all capabilities.