Designing and building LeetCode - Part I

Introduction

Around September 2024 I built a LeetCode alternative. My plan was to create better, more practical problems/challenges and launch it as a small product.

It had a promising start, but eventually I shut it down because it had 0 paying customers, and the system was a bit too complex to maintain it as a free app.

At least now, I can share how it works because it has some interesting stuff:

• Remote code execution

• Docker container pooling

• Asserting user submissions

If you don’t know LeetCode, it’s a code running platform. You’re presented with a programming challenge, you write your solution, you submit the code, LeetCode executes it, asserts the results and shows it to you.

Get the book

This is going to be a 3-part series in the next 3 weeks.

I also put together a 72-page book, that contains more knowledge and the whole 13k line codebase to the project.

• High-level design

• Docker inside Docker

• Container pools

• Code execution

• Asserting test cases

• Init and tear down tasks for containers

• Package oriented design

• How to navigate the source code

High level design

From the perspective of system design it’s very simple:

Of course, this probably won’t handle LeetCode-size load but this is not the goal of the article. The goal is to understand code execution and everything that comes with it.

When a user submits code it’s pushed onto a queue. Executors will pick up these tasks and execute the code.

I built the entire system as a monolith, because it was a solo project for 0 paying customers. But if I were LeetCode, executor would be a completely different service and repo. And the API would be only a simple API that accepts submissions and enqueues them, etc.

Docker containers

This project needs to execute user submitted code, so it’s very important that everything happens in an isolated docker container. Each submission should have its own container. But the system itself runs in a docker container. It means we need to run a docker container inside a docker container.

There are two main ways to do this:

• Docker-in-Docker (DinD)

• Docker-outside-of-Docker (DooD)

DooD means mounting the host's docker socket into the container.

It looks like this:

docker run -v /var/run/docker.sock:/var/run/docker.sock docker

Now you a container that can run docker commands using the docker socket on the host machine.

It’s a lightweight solution but it has a big disadvantage. Containers are less isolated because they use the docker socket from the host machine. It’s a potential security risk. Unfortunately, I’m not great with security so this option is out.

DinD means running a full docker daemon inside a Docker container. It requires a special docker image labaled as docker:dind:

# This stage is just a standard Go build
FROM golang:1.23-alpine AS builder
WORKDIR /app
COPY ./api/go.mod ./api/go.sum ./
RUN go mod download
COPY ./api .
RUN CGO_ENABLED=0 GOOS=linux go build -a -installsuffix cgo -o reelcode-worker ./cmd/worker/worker.go

# This is the docker-in-docker part
FROM docker:dind
RUN apk add --no-cache ca-certificates
COPY --from=builder /app/reelcode-worker /usr/local/bin/reelcode-worker
COPY ./deployment/bin/entrypoint.sh /usr/local/bin/
RUN chmod +x /usr/local/bin/entrypoint.sh
ENTRYPOINT ["entrypoint.sh"]
CMD ["reelcode-worker"]

As you can see, everything is the same as if it’s in a normal Dockerfile:

• The builder stage builds a binary from the source code

• The second stage starts the binary but using docker:dind as the starting point

Docker is kind of weird, because it’s easy, until it’s not.

The “until it’s not” part came after three or four minutes.

When I ran this image in a compose stack I got all kinds of error messages that said docker is not able to start. Containers were exiting. I was clueless and after few hours I decided to add this entrypoint script:

#!/bin/sh
set -e

dockerd-entrypoint.sh &

# Waiting for Docker with a maximum of 10 attempts
attempts=0
max_attempts=10

while ! docker info >/dev/null 2>&1; do
    attempts=$((attempts + 1))
    if [ $attempts -ge $max_attempts ]; then
        echo "Docker did not start within $max_attempts attempts. Exiting."
        exit 1
    fi
    echo "Waiting for Docker to start... (Attempt $attempts/$max_attempts)"
    sleep 1
done

exec "$@"

The loop runs 10 times checking if docker is available. If not, it sleeps for 1 second.

This fixed the issues but still to this day, I have no idea why this script was needed.

So dind started working but then I got other error messages saying that too many processes were running and I exceeded some kind of limit.

Turns out docker has a PID (process ID) limit so you cannot just start 10,000 processes in a container. Fortunately, the fix is easy:

worker:
  image: registry.digitalocean.com/reelcode/worker:${IMAGE_TAG}
  pids_limit: -1

-1 means unlimited, but of course, you can use any number you want.

So now docker can be used inside of a docker container. It means I can pull images, run containers, execute commands.

Container pooling

One of the first problems we need to solve is spinning up containers for user submissions.

That comes with two challenges:

• Docker images (for different languages) should be pre-pulled in the dind containers

• Containers should be pre-created in the dind containers

Pulling a docker image takes 10+ seconds so we obviously need to do it at startup time when the system is started/restarted.

Not just pulling images, but creating containers on-the-fly from those images takes a little bit too long too. There were instances when it took multiple seconds just to start executing code. Under load docker can be quite resource intensive since it involves lots of I/O operations (copying files, mounting stuff) so it consumes lots of memory and CPU. (Unfortunately, I didn’t benchmark the performance back then so I don’t have exact numbers, and now the system is too big to refactor and try it out. But please believe me, it was considerable slower with just 10 concurrent user on a smaller server.)

To solve these problem we can introduce a container pool into the system. It’s very similar to a connection pool which is used everywhere in software engineering (for example, database systems, web servers, operating systems).

A container pool is an object that maintains a list of ready-to-use docker containers for all available languages. It has a hash map that looks like this:

{
  "php": ["cc5564edfe81", "427f77e406d7"],
  "golang": ["933aaaf9f7df", "906700cb8e7f"]
}

This means, there is a container with the ID of cc5564edfe81 that runs the official PHP image so it vcan be used to run PHP submissions.

This hash map should be pre-populated at startup time. So pre-pulling images and pre-creating containers is a responsibility of the container pool.

The container pool should provide afunction that returns a container ID for a specific language:

func Get(language string) (string, error)

(If you’re not familiar with Golang, please don’t get hung up the small details, you can still understand 99.86% of this article. The (string, error) return value means the function either returns a string or an error. Instead of throwing an Exception, Golang treats errors as values.)

Each container can be used by only one user at a time, so when it is retrieved it should be temporarily removed from the hashmap:

pool.Get("php")

{
  "php": ["427f77e406d7"], // one ID is removed
  "golang": ["933aaaf9f7df", "906700cb8e7f"]
}

Obviously, we can only pre-create a finite number of containers. In this example, two for each language. So after a time, this will happen:

pool.Get("php")

{
  "php": [], // there's no more available PHP container
  "golang": ["933aaaf9f7df", "906700cb8e7f"]
}

In this case, if another request comes in for a PHP container, the pool should create a new container on-the-fly. Yeah, it’s gonna be slower, but we can still serve the user.

Once a request is served, the container should be pushed back to the pool. For that, there’s another function:

func PushBack(language string, ID string) error

This is the fundamental concept of every connection pool as well.

Get the book

This is going to be a 3-part series in the next 3 weeks.

I also put together a 72-page book, that contains more knowledge and the whole 13k line codebase to the project.

• High-level design

• Docker inside Docker

• Container pools

• Code execution

• Asserting test cases

• Init and tear down tasks for containers

• Package oriented design

• How to navigate the source code

Retrieving containers

So let’s write a container pool.