Implemented an in-memory, multi-Threaded, LRU caching server supporting time to live (TTL) eviction in December 2017 at Stony Brook University.

Author

All works were solely done by Wonyong Jeong except the base code that is designed under the course CSE320: System Fundamentals II led by Professor Jeniffer Wong-Ma and Professor Eugene Stark.

NOTE: If you are a student in such a class, you should not copy (or copy then modify) this code without permission.

Description

A caching Server supporting Least Recently Used (LRU) replacement and Time To Live (TTL) eviction policy was implemented consisting of both concurrent queue and hashmap through low-level POSIX threads, multi-threading safety, concurrency guarantees, and networking.

Usage

./wyjeong-server [-h] NUM_WORKERS PORT_NUMBER MAX_ENTRIES
-h                 Displays this help menu and returns EXIT_SUCCESS.
NUM_WORKERS        The number of worker threads used to service requests.
PORT_NUMBER        Port number to listen on for incoming connections.
MAX_ENTRIES        The maximum number of entries that can be stored in `wyjeong-server`'s underlying data store.

NOTE wyjeong-server will service a request for any client that connects to it. wyjeong-server will service one request per connection, and will terminate any connection after it has fulfilled and replied to its request.

Concurrent Queue

A concurrent, blocking queue that follows the producers/consumers pattern was implemented. The queue_t struct includes a mutex and a semaphore to implement the producers/consumers pattern.

Operations

Concurrent Hash map

An open-addressed hash map backed by an array that uses linear probing to deal with collisions was implemented. Thus, the map supports the put, get, and remove operations.

Operations

Hash Function

jenkins_one_at_a_time_hash hash function is used and located in utils.c.

uint32_t jenkins_one_at_a_time_hash(map_key_t map_key) {
    const uint8_t* key = map_key.key_base;
    size_t length = map_key.key_len;
    size_t i = 0;
    uint32_t hash = 0;

    while (i != length) {
      hash += key[i++];
      hash += hash << 10;
      hash ^= hash >> 6;
    }

    hash += hash << 3;
    hash ^= hash >> 11;
    hash += hash << 15;
    return hash;
}

This hash function is used by the server to hash keys when inserting, retrieving, and deleting values from the underlying data store.

Caching Server

Many general purpose caching services such as Memcached and Redis have been developed. These caching services can be used by any application and provide a ton of flexibility to the programmers using them.

Similar to them, the concurrent data structures implemented in the previous parts was used to build the server for the general purpose in-memory key-value caching service.

ServerDiagram

The diagram above shows how wyjeong-server handles client requests. On startup wyjeong-server will spawn NUM_WORKERS worker threads for the lifetime of the program, bind a socket to the port specified by PORT_NUMBER, and infinitely listen on the bound socket for incoming connections. Clients will attempt to establish a connection with wyjeong-server which will be accepted in wyjeong-server’s main thread. After accepting the client’s connection wyjeong-server’s main thread adds the accepted socket to a request queue so that a blocked worker thread is unblocked to service the client’s request. Once the worker thread has serviced the request it will send a response to the client, close the connection, and block until it has to service another request.

All client requests access wyjeong-server’s underlying data store in some way. This underlying data store is what wyjeong-server uses to cache values sent to it by clients. The different types of requests and the structure of the requests that wyjeong-server services are determined by the protocol that wyjeong-server adheres to.

Caching Policy

LRU Cache

In order to avoid to violate temporal locality, hash map implementation supports a Least Recently Used (LRU) replacement policy.

TTL Eviction

Modern caching daemons support time to live (TTL) eviction. This means that a key/value pair in the map will be removed after a set amount of time. It can lazily remove nodes when get requests are made for them. Also, the map can treat expired nodes as tombstones when doing linear probing.

Caching Protocol

Protocol for the caching server is implemented over a streaming socket and uses the request-response pattern.

Request Header

typedef struct request_header_t {
    uint8_t request_code;
    uint32_t key_size;
    uint32_t value_size;
} __attribute__((packed)) request_header_t;

request_codes enum in wyjeong-server.h consists of all requests and their corresponding request_code.

typedef enum request_codes {
    PUT = 0x01,
    GET = 0x02,
    EVICT = 0x04,
    CLEAR = 0x08
} request_codes;

Response Header

typedef struct response_header_t {
    uint32_t response_code;
    uint32_t value_size;
} __attribute__((packed)) response_header_t;

response_codes enum in wyjeong-server.h consists of all responses and their corresponding response_code.

typedef enum response_codes {
    OK = 200,
    UNSUPPORTED = 220,
    BAD_REQUEST = 400,
    NOT_FOUND = 404
} response_codes;

Requests Supported

1. Put Request

When a client wants to insert a value into the cache it will connect to the server and send a request message with a request_code of PUT.

The server checks if the key_size and value_size fields in the request_header are valid, and then attempts to read the key and value from the connected socket.

For a PUT request the first key_size bytes after the request_header correspond to the key, and the the next value_size bytes after the key correspond to the value.

If the cache is full, the PUT operation will evict a value from the cache by overwriting the entry in the hash map at the index that the key hashes to.

After the PUT operation has completed the server will send a response message back to the client informing them of the status of their request. The response_code in the header of the response message will be set to OK if the operation was completed successfully, or BAD_REQUEST if an error occurred, and value_size will be set to 0.

2. Get Request

When a client wants to retrieve a value from the cache it will connect to the server and send a request message with a request_code of GET. The server checks if the key_size field in the request_header is valid, and then attempts to read the key from the connected socket.

For a GET request the first key_size bytes after the request_header correspond to the key.

If the value that the client requested exists, the server will send a response message back to the client containing the corresponding value. In the message, the response_code will be set to OK, the value_size will be set to the size of the value in bytes, and the first value_size bytes after the header will be the corresponding value.

If the value that the client requested does not exist, the server will still send a response message back to client. In this scenario the response_code will be set to NOT_FOUND, and value_size will be set to 0.

3. Evict Request

When a client wants to delete a value from the cache it will connect to the server and send a request message with a request_code of EVICT. The server checks if the key_size field in the request_header is valid, and then attempts to read the key from the connected socket.

Once the EVICT operation has completed, regardless of the outcome of this operation, the server will send a response message back to the client with a response_code of OK and value_size of 0.

4. Clear Request

When a client wants to clear all values from the cache it will connect to the server and send a request message with a request code of CLEAR.

Once the CLEAR operation has completed the server will send a response message back to the client with a response_code of OK and value_size of 0.

5. Invalid Request

If a client sends a message to the server, and the request_code is not set to any of the values in the request_codes enum, the server will send a response message back to the client with a response_code of UNSUPPORTED and value_size of 0.

6. Otherwise

The program handles:

Source Code

Source code will be public on my github accout soon.