In this article, I'm trying to explain how to build a Load Balancer from scratch using just C programming language and no other 3rd party libraries at all. I'll be using various techniques here including UNIX socket programming, multi-threading, thread pools and safety, data structures and containerizing. I'll try my best to explain all the concepts!
I took this application as a personal challenge of trying to understand the abstraction behind complex systems and implementing the same with very simple tools and technologies. I restricted myself to use C as the only programming language. The system might seem a bit complex at first, but dividing it into multiple smaller systems will make it easier!
caution
This article will contain some concepts which are not explained from scratch. They include data structures like: Linked List, Circular Linked List, Queue and techniques like: Sockets, Multithreading, Round Robin, File handling, CMake, Docker etc. Beginner-level knowledge on these topics might be considered as a prerequisite!
Load Balancer
A load balancer is an application which sits in front of web applications to distribute and forward incoming traffic to the target web applications efficiently. This is done so that the web severs don't get overwhelmed by a huge amount of requests in a high traffic system.
Also, load balancer help in scaling up systems. By analyzing the memory and CPU signatures of the target web severs, it can help judge whether there's a need to bring up additional instances. Once up, a load balancer can route traffics to the new instances. On the other hand, with regular health checks, it can automatically detect the unhealthy instances and choose not to route traffic to them!
Here I'll build a load balancer that'll follow a simple round-robin algorithm to distribute the traffic. Additionally, there will be passive health checks that will be triggered every 30s. I've also added a priority based target group system to group backend resources by path/routes.
info
This article will give you an idea of how things work under the hood. For actual code, please refer to the GitHub Repository here. I'll suggest opening up the repository while reading this article for better following along. Many places in this article, you'll find just the function signatures or code snippets. For the full code, please refer the repository!
Low level Networking
Let's start by dealing the low level networking problems! Low level networking here means handling HTTP requests by raw UNIX sockets only. This includes working with socket file descriptors, connecting, binding etc. But lets first start with socket!
Sockets
Sockets are used for communication between different processes. Ideally in a client-server situation, socket is the underlying technology used by several protocols to establish connections to send/receive data. Unix sockets are actually file descriptors (unique non-negative integer identifier for a resource) on which we can use functions like recv and send to receive and send data respectively
Structures
I've set up a few structures to handle the socket and address info of the servers:
struct socket_name_info {
char host[INET6_ADDRSTRLEN];
char port[NI_MAXSERV];
};
struct socket_connection {
int socket_fd;
struct sockaddr_in address;
struct socket_name_info socket_name;
};
- The constants
INET6_ADDRSTRLENandNI_MAXSERVdenotes the maximum length of an IPv6 address and the maximum length of a service info sockaddr_inis a structure that deals with internet addresses
Creating the socket_connection object
To create the socket_connection object, we'll need to do the following:
int get_socket(struct socket_connection *server_socket, char *address, unsigned int port) {
/** Code */
}
- Create the socket file descriptor with the
socketfunction. I'm setting the following:domaintoAF_INETfor allowing the socket connection to be on IPv4 protocoltypetoSOCK_STREAMto provided a two-way connection
- Set the socket options to reuse local addresses with the
setsockoptfunction - Set the appropriate host and port options for the
sockaddr_instructure - Get the details of the service for the
socket_name_infostructure usinggetnameinfo - Finally save everything in the
socket_connectionstructure - This function also returns
0if everything goes fine, or else returns a negative number on failure
More functions for networking
Binding
int bind_to_socket(struct socket_connection server_socket) {
/** Code */
}
The socket created in the above step need to be associated with an address. Just creating the socket file descriptor doesn't let us connect to it until and unless, we've an address for it. This is done with the bind() function
Connecting
int connect_to_socket(struct socket_connection server_socket) {
/** Code */
}
connect() is used to connect to the socket to send and receive data. After a successful connection only, we can use other methods on the socket file descriptor to undergo various network operations
Listening
int listen_to_socket(struct socket_connection server_socket, unsigned int backlog) {
/** Code */
}
To accept incoming connections on the socket, we'll need to listen on it. The listen() function does the same job! Listening to the socket comes with a backlog. A backlog is the maximum number till which the queue of pending connections can grow to, in the particular socket we're trying to listen on. The value of backlog depends on the programmer and there is no such preferred value
Convert hostname to IP address
int hostname_to_ip(char *hostname, unsigned int port, char *ip) {
/** Code */
}
Sometimes there's a need to convert the hostname to IP addresses (For example, localhost -> 127.0.0.1), so that we have a consistent style of handling addresses within the system. This function cycles through the list of available addresses and sets the IP. The getaddrinfo() function comes handy in this case
Handling incoming requests
Once we're all set with the low level networking setup, we'll need to start accepting some requests in our Load balancer. To do that, we'll first need to work on the listening server. This is the main load balancer server which will receive all the request. We're not handling the forwarding work yet!
int create_server(struct socket_connection *server_socket, char *host,
unsigned int port, unsigned int backlog) {
/** Code */
}
The above function creates the socket file descriptor, bind an address and then start listening on this socket.
To accept the connections, we'll need to use the accept() function. This function creates a new file descriptor for the connection and returns the same
int accept_incoming_connection(struct socket_connection server_socket) {
/** Code */
}
We'll need to continuously accept the connection, hence we'll need to place the above function in an infinite while loop!
A basic Reverse Proxy
A reverse proxy is an application which routes incoming client requests to backend services. If you look closely, you'll see that a Load Balancer is essentially a high level reverse proxy. Hence, let/s implement a simple reverse proxy to work with our current setup.
To build a reverse proxy, we'll need to forward requests. We're already capturing the requests in the accept_incoming_connection function. We'll now need to read the data from the incoming connection and then create another socket connection to the backend to send the request.
To package all the information of a backend, we'll use the following structure:
struct target_backend {
char name[100]; // name of the backend
char host[INET6_ADDRSTRLEN];
unsigned int port;
int is_healthy; // 0 - unhealthy , 1 - healthy
};
To forward incoming request to a particular target backend, we can use the following code snippet. This is a toned down version of the final code, as we'll fiddling around with this to add more functionality later!
/* Read the client's request */
// new_connection is a socket file descriptor created by accept() call
bytes_read = recv(new_connection, buffer, BUFSIZE - 1, 0);
// selecting a target will be coming up later!
struct target_backend target;
/* Create a target socket */
// creating and connecting to the target. src/server.c
if (connect_to_target(&target_socket, target.host, target.port) < 0) {
return NULL;
}
/* Forward the client's request to the target server */
send(target_socket.socket_fd, buffer, strlen(buffer), 0);
/* Read the response from the target and forward it to the client */
while (
(bytes_read = recv(target_socket.socket_fd, buffer, BUFSIZE - 1, 0))) {
send(new_connection, buffer, bytes_read, 0);
}
/* close sockets */
close(target_socket.socket_fd);
close(new_connection);
Multi-Threading and Request Queue
When a huge number of connections come in, it'll be difficult for the server to keep up with the requests. Threads come at a rescue here. The idea is to enqueue an incoming connection to a simple queue and then dequeue it to process later. If we work towards building a thread safe queue, then multiple each thread can dequeue its own connection and handle them in parallel.
The src/queue.c file illustrates a simple thread safe queue. It works along with a thread pool, which is a set of pre-defined threads. Thread safety is done with the help of a mutex. Also, to improve performance, condition variables are used. It helps to send signals between threads, so that the threads become active only when needed to!
tip
Jacob Sorber has a 3 part video series explaining the above concepts. Do check them out:
When the server starts up, we can initialize the thread pool. The THREAD_POOL_SIZE can be a configurable value depending on the programmer's need!
void init_thread_pool() {
for (int i = 0; i < THREAD_POOL_SIZE; i++) {
pthread_create(&thread_pool[i], NULL, thread_handler, NULL);
}
}
To work with the request queue and threading together, the following functions are used. As you can see, we enqueue the connection on the request queue and then one of the threads from the thread pool picks up the connection and handles the same. This might look like a producer-consumer system too!
void *thread_handler(void *arg) {
while (1) { // do not kill the threads
int *p_new_connection = dequeue_connection();
if (p_new_connection != NULL) {
// we've a waiting connection, so handle it!
handle_connection(p_new_connection); // the actual handling logic goes in here!
}
}
}
// this was the connection loop to handle incoming connection
void connection_loop(struct socket_connection client_socket) {
int new_connection;
while (1) {
/* Accept incoming client connections */
new_connection = accept_incoming_connection(client_socket);
if (new_connection < 0) continue;
int *p_new_connection = (int *)malloc(sizeof(int));
*p_new_connection = new_connection;
enqueue_connection(p_new_connection);
}
}
Round Robin Algorithm with unhealthy targets
Once we're done with handling the requests efficiently, it's time to start working towards our load balancer logic. Round-robin algorithm is one of the common algorithm used to distribute traffic across a set of backend services. It's simple and ridiculously efficient when equally dividing the requests.
However, there can be a situation where certain backend services might be down, and we do not want to route traffic to them. Hence, we'll need to tweak the round-robin algorithm such that it ignores the unhealthy targets. Also, as we're dealing with requests in multiple threads now, it's better to make this algorithm thread safe too!
In the heart of this algorithm, lies a simple Circular Linked List. Circular linked list is like a normal linked list, but the last node is pointed back to the first node. Hence, while iterating a circular link list, it'll never overflow after the last node, but will start back again from the first node. This is actually the logic behind the round-robin algorithm
The follow structure is used for a single node in the round-robin circular linked list:
struct round_robin_node {
struct target_backend backend;
struct round_robin_node *next;
};
Additionally, to maintain the circular linked list, two points are used. The head pointer points to the start of the list while the current pointer points to the currently used target.
Insertion can be done easily. Find the insertion code in the src/round_robin.c file. The interesting part is getting the next target from the circular linked list. In theory, if we move the current pointer to the next one, it should work. However, we need to deal with unhealthy targets too:
struct target_backend get_next_backend(
struct round_robin_node *round_robin_head,
struct round_robin_node **round_robin_current, pthread_mutex_t mutex) {
pthread_mutex_lock(&mutex);
struct round_robin_node *temp = *round_robin_current;
if (temp == NULL) { // first time here, start with the head
temp = round_robin_head;
*round_robin_current = round_robin_head;
} else {
temp = temp->next;
}
// loop back till current
while (temp->next != *round_robin_current) {
if (temp->backend.is_healthy == 1) { // choose only if healthy
*round_robin_current = temp;
pthread_mutex_unlock(&mutex);
return temp->backend; // got a healthy one!
}
temp = temp->next;
}
if (temp->backend.is_healthy == 1) { // choose only if healthy
*round_robin_current = temp;
pthread_mutex_unlock(&mutex);
return temp->backend; // got a healthy one!
} else {
temp = temp->next;
}
pthread_mutex_unlock(&mutex);
return temp->backend;
}
What happens when all the targets are unhealthy? - The load balancer cannot do much here and needs to route traffic to one of the unhealthy ones!
Target Groups with priority
Target groups are a group of targets that are linked to a particular path of the load balancer. Lets say we've the following target groups:
| Target Group Name | Path | Priority | Default? |
|---|---|---|---|
| tg1 | /foo/* | 1 | No |
| tg2 | /bar/* | 2 | No |
| tg3 | /meh/* | 1 | Yes |
Now, if we receive a request with a path /bar/search?q=chocolates, the load balancer will first go through the paths according to the priority and regex match them. Here is how it goes:
- Check tg1 - Fails
- Check tg2 - Passes => Route to this target group
Few things to note here:
- If none of the paths match, then the request is routed to the default route.
- Priorities are descending. In other words: 1 is a higher priority than 2.
- If all the target groups have the same priority, then the priority is decided internally by the insertion index. That means, the target groups inserted first will have an higher priority
- If no default target group is mentioned, then the highest priority target group is used as the default one
Target groups list can be created with Linked Lists and we can smartly handle the priority by sorting the targets groups by priority while inserting them only!
void target_group_list_sorted_insert(struct target_group target_group)
The path matching on the target group list will look like this:
void find_target_group_with_path(char *path, struct target_group **tg) {
pthread_mutex_lock(&target_group_mutex);
struct target_group_list_node *temp = target_groups_head;
struct target_group *default_tg = &target_groups_head->tg;
regex_t path_regex;
int regex_result;
while (temp != NULL) {
// extracting out the default one while iterating the list!
if (temp->tg.is_default == 1) { // found the default!
default_tg = &temp->tg;
}
regcomp(&path_regex, temp->tg.path, 0);
regex_result = regexec(&path_regex, path, 0, NULL, 0);
if (regex_result == 0) {
pthread_mutex_unlock(&target_group_mutex);
*tg = &temp->tg;
return;
}
temp = temp->next;
}
pthread_mutex_unlock(&target_group_mutex);
*tg = default_tg;
}
Additionally, to handle routing from the incoming connection, we can abstract out the routing logic in a separate function while handling the connection:
int handle_routing_target(char *request_buffer, struct target_backend *p_target,
int new_connection) {
/** Code */
}
Passive Health checks
To monitor the health of the target backends, we'll need to run passive health checks. These health checks will run once every 30 seconds. In each run, it'll do a simple HTTP call to the root route of the backend service and check if it returns a 200 status code to make sure it's healthy. If any other status code is returned and/or the HTTP connection fails, then we'll mark the target as unhealthy. This operation is done in a separate thread all together so that it doesn't interfere with the main server thread.
The HTTP call is illustrated in the following function
int health_check_target(struct target_backend target) {
/** Code */
}
The health check thread is set up while the server is initializing, and a health check is also done for the first time before actually listening to incoming requests
Handling special request/response
Health report
While doing the routing in the handle_routing_target function, we can look for some special routes to handle them differently
int handle_routing_target(char *request_buffer, struct target_backend *p_target,
int new_connection) {
/** Code */
// health report
if (strcmp(url, "/__health") == 0) {
logger("[ROUTE] %s => Health Report", url);
handle_health_route(new_connection);
return 1; // already handled
}
/** Code */
}
Here, we're checking whether the incoming rout is /__health and handling it differently. We're not routing the traffic to one of the backend services, but instead sending out a static JSON. The JSON looks like the following:
{
"target_groups": [
{
"path": "/foo/*",
"priority": 1,
"default": true,
"targets": [
{ "name": "serverA", "status": "up" },
{ "name": "serverB", "status": "up" },
{ "name": "serverC", "status": "up" },
{ "name": "serverD", "status": "down" },
{ "name": "serverE", "status": "up" }
]
},
{
"path": "/bar/*",
"priority": 2,
"default": false,
"targets": [
{ "name": "serverF", "status": "up" },
{ "name": "serverG", "status": "up" }
]
}
]
}
503 response
503 status code response can occur when we fail to establish connection to the target backend server. We can look for such errors in the handle_connection function
void *handle_connection(void *p_new_connection) {
/** Code */
/* Create a target socket */
if (connect_to_target(&target_socket, target.host, target.port) < 0) {
handle_503(target_socket, new_connection);
return NULL;
}
/** Code */
}
Here the handle_503 function returns static HTML which says: "Service Unavailable"
Configuration
Configuration File
To create target groups, backends etc., we'll need to do some kind of configuration. Configurations are handled by a configuration file named as: byolb.config
The config file's syntax looks like the following:
tg {
path /foo/*
priority 1
default
target serverA localhost 80
target serverB localhost 5001
target serverC localhost 5002
target serverD localhost 5003
target serverE localhost 5004
}
tg {
path /bar/*
priority 2
target serverF localhost 5010
target serverG localhost 5011
}
To parse the above file, a simple line wise parsing is done and the request data structures (like target groups, backend targets, etc.) are created using the following function. This function is called before the server starts. The file's location can be controlled by the CONFIG_FILE environment variable
void read_config_file() {
/** Code */
}
Environment variables
Reading the environment variables is an easy job ans can be done by the getenv function in C. However, some variables are needed in particular format or types. To parse them correctly and also to assign default values in absence of the environment variables is done in the src/env.c file.
Currently, these are the environment variables allowed:
| Environment variables | Type | Default | Behaviour |
|---|---|---|---|
| HOST | String | localhost | The Host on which the load balancer will run |
| PORT | Integer | 2209 | The Port on which the load balancer will run |
| BACKLOG | Integer | 10 | The amount of listening backlog |
| LOG_ERRORS | Integer | 0 | Wheather to log errors in verbose. Set this to 1 to log |
| CONFIG_FILE | String | /etc/opt/byolb/byolb.config | The absolute path to the configuration file |
Containerizing
Most of the applications you're planning to run on the Cloud uses containers in one or the other way. Though this load balancer is not a production ready application, still I've tried to build this through a simple Dockerfile
caution
I've built the Docker image on a M1 Mac which is ARM based. I've not tested this in other platforms! If you fail to create the docker image on your platform, do open an issue!
FROM ubuntu:focal
ARG DEBIAN_FRONTEND=noninteractive
RUN apt-get update && apt-get install build-essential cmake -y --no-install-recommends
# for debugging!
RUN apt-get install -y iputils-ping curl
WORKDIR /byolb
COPY . .
RUN ./scripts/clean.sh
RUN cmake --build ./build --target clean
RUN cmake --build ./build --target all
RUN mkdir -p /etc/opt/byolb
VOLUME [ "/etc/opt/byolb" ]
ENTRYPOINT [ "./build/src/lb" ]
Explore the docker image in DockerHub
What have we done?
In this article, we've started with the low level networking stuffs and slowly build towards our actual goal - a Load Balancer! We've seen several data structures and have explored techniques and algorithms to build this complex system.
But, as previously mentioned, this Load Balancer is just a hobby project and not a production ready application at all. There are still multiple sectors in which we can improve it - like identifying Denial of Service attacks, auto-scaling, handling non-HTTP protocols, logging, monitoring, etc. There are various industry grade Load Balancers like ngnix, HAProxy, etc. which implements such features!