Gemini, built by Google! October 2026
The goal of this project is to design and implement a key-value store accessed by a REST-style API using UDP datagrams.
When truth is a forward-moving clock ...
NAME
skv-client, skv-server
SYNOPSIS
skv-client [-v|-vv] host:port [-|request]
skv-server [-v|-vv|-L] port
DESCRIPTION
skv-server listens on port _port_ and responds to REST requests:
GET key
PUT key value
DEL key
IPUT key if-val value
svi-client and sends requests to _host_ on port _port_ and prints the response.
ARGUMENTS
The server listens on port _port_.
The client sends the request to the colon (:) delimited host and port.
If the request argument is a dash (-) requests are read sequentially from standard input,
one per line.
OPTIONS
-L do not loop - server responds to one request and exits
-v verbose (can be repeated)
BUGS
Due to lost packets, IPUT might be complicated to use.
LAST UPDATE
18 October 2026
A key-value store is a database of string pairs. The first element is the key, and the second is the value. A value is retrieved by its key. Key-value pairs can be inserted, updated, and deleted.
When a database is accessed by multiple clients, it becomes difficult to define its exact state at any given time. One solution is to represent the database as a time-ordered log of its changes. The state of the database can then be determined by replaying the log. A longer log represents a later state, and two logs will agree on their shared (older) portion.
To implement this, the key-value pairs will be stored in an append-only linked list, with new pairs added to the front of the list. The entire history is retained. To access a key, the list is scanned from front to back, stopping at the first matching key.
Deletion is accomplished but adding the key with a special value, called a tombstone. In our implementation, the tombstone is a empty string for the value. This gives two internal representations of a non-existant key: either no pair has the key or there is a pair with the key and its most recent value is the empty string. However the external semantics will be that a missing key from the store, regardless of the internal representation.
To accommodate a possible later project in which the datastore is stored in a file, each key-value pair is represented as a single memory array containing two consecutive null-terminated strings:
+-------+----+--------+----+
--->| key | \0 | value | \0 |
+-------+----+--------+----+
The entire datastore can be written to a file as a concatenation of these records,
without additional separators or per-record headers.
A Sorted String Table (SST) is a sequence of such records ordered lexicographically by key. An SST is an immutable snapshot of the database at a particular point in time, supporting efficient key lookup.
For this project, however, the datastore is represented simply as a linked list of these records, in update order. The SST format is a design consideration for a possible future extension, not part of the current implementation.
Update of the store is by a REST-style interface. REST stands for Representational State Transfer. It is an architectural style for designing networked services, introduced by Roy Fielding in his 2000 doctoral dissertation. The central idea is that a service exposes resources identified by names or URIs, and clients interact with those resources through a uniform interface. The client will send the server a string formated as,
OPERATION KEY [KEY2] [VALUE]and receive a response,
[OK|ERR] [VALUE|text]The string is in a UDP packet and there is no end-of-text character. For instance, no '\0' byte. Use the packet length for the length of the string.
| Operation | Arguments | Description |
|---|---|---|
GET |
key |
Retrieves the value associated with the key. Returns ERR if key not found. |
PUT |
key value |
Creates a new key-value pair or replaces the value associated with an existing key. |
DEL |
key |
Deletes the key-value pair identified by the key from the datastore. Returns ERR if key not found. |
IPUT |
key if-val value |
Atomically replaces the value associated with an existing key with value,
but only if the current value equals if-val.
The token if-val is restricted to key format.
Returns NO if the key is found but value does not match if-val.
Returns ERR if key not found. |
The keys and values have formats defined by the functions check_allowed_keys() and check_allowed_values(), see the template code.
| Response | Operation | Description |
|---|---|---|
OK |
PUT DEL IPUT |
The operation completed successfully. |
OK value |
GET |
The requested key was found; value is its associated value. |
NO |
IPUT |
The IPUT operation did not update the key. |
ERR message |
GET PUT DEL IPUT |
The operation failed; message explains the error. |
The standard networking protocol suite of the Internet is called TCP/IP. Although it is not named in the title, this suite also includes UDP, which provides best-effort packet delivery.
A UDP packet is addressed to a destination host and port. The host is identified by an IP address, and the port identifies the receiving application endpoint on that host.
Every IP packet also carries a source host and port. A reply is sent to that source address and port.
The programmer's interface to the TCP/IP network is through the socket software abstraction. A socket is created, and messages are sent and received through it. A server binds a socket to a particular port, so that messages arriving at that port can be delivered to the server's socket. This also establishes the well-known destination for clients seeking service from the server.
The client initiates a packet exchange by sending a packet to the server's host and well-known port. The packet includes the client's source IP address and port, allowing the server to send its response to the correct destination. The client's port is therefore usually assigned automatically by the operating system, without the programmer having to manage it.
There are many details involved in using sockets. The FooSocket library has therefore been provided to reduce the work to a few simple calls. A FooSocket contains a socket and associated context. For instance, socket_recvfrom() records the source address of the received packet, and the next call to socket_replyto() uses that address as the destination of the reply.
NAME
create_foo_socket, socket_sendto, socket_recvfrom,
socket_replyto, create_session_socket
SYNOPSIS
#include "foo-socket.h"
struct FooSocket *
create_foo_socket(int port) ;
int
socket_sendto(struct FooSocket * foo_sock, char * host, int port, char * message, int msg_len) ;
int
socket_recvfrom( struct FooSocket * foo_sock, char * buf, int buf_len, int time_out) ;
int
socket_replyto(struct FooSocket * foo_sock, char * message, int buf_len) ;
struct FooSocket *
create_session_socket(struct FooSocket * sock_listen) ;
DESCRIPTION
The create_foo_socket returns a struct FooSocket * representing a newly
opened socket. If a non-zero port is given, the socket is bound to that port.
Else the socket is bound to an ephemeral port.
The socket_sendto sends the message on the foo_socket to host:port.
The socket_recvfrom receives into buf from the foo_socket up to buf_len bytes,
returning the number of bytes received. The foo_socket binds to the packet
source for the purpose of socket_replyto. If time_out is 0, there is no
timeout on the socket. Else it is the postive seconds to time out.
On timeout, return -1.
The socket_replyto sends the message in reply to the sender of the previous
socket_recv_from.
The create_session_socket returns a new foo_socket, a clone of the foo_sock
bound to a sender after a socket_recvfrom.
BUGS
LAST UPDATE
01 February 2026
The socket interface is designed for network communication between machines. However, it can also be used for communication between processes on the same machine. In this case, the source and destination are identified by localhost with IP address 127.0.0.1. You can develop and test your code using localhost.
The aim of this project is to make your service accessible over the Internet. To do this, you will use your AWS account to create an EC2 instance and run your code on that instance. In doing so, you will need to learn:
A useful tool for network development is the Unix program tcpdump. It observes network traffic and displays the packets it captures. You can apply filters to focus on particular traffic. For this project, the filter selects UDP traffic to or from the port we are using (3333 by default).
A Makefile target provides an example of how to run tcpdump. Its arguments vary by platform, so you may need to modify the target for your system. Similar information is also available in the verbose output of the FooSocket code.
The tcpdump however shows almost the entire packet — including the IP headers and the UDP headers. Points of interest,
Client Server Linked-list
-------------------------------------------------------------------
PUT a one apple ->
<- OK -->[a|one apple]
PUT a two apples ->
<- OK -->[a|two apples]-->[a|one apple]
GET a ->
<- OK two apples -->[a|two apples]-->[a|one apple]
DEL a ->
<- OK -->[a|NULL]-->[a|two apples]-->[a|one apple]
GET a ->
<- ERR key not found
TCPDUMP
01:54:09.986148 IP 127.0.0.1.52750 > 127.0.0.1.3333: UDP, length 15
0x0000: 4500 002b e3d3 0000 4011 0000 7f00 0001 E..+....@.......
0x0010: 7f00 0001 ce0e 0d05 0017 fe2a 5055 5420 ...........*PUT.
0x0020: 6120 6f6e 6520 6170 706c 65 a.one.apple
01:54:09.986298 IP 127.0.0.1.3333 > 127.0.0.1.52750: UDP, length 2
0x0000: 4500 001e 92fb 0000 4011 0000 7f00 0001 E.......@.......
0x0010: 7f00 0001 0d05 ce0e 000a fe1d 4f4b ............OK
01:54:09.986507 IP 127.0.0.1.52750 > 127.0.0.1.3333: UDP, length 16
0x0000: 4500 002c e564 0000 4011 0000 7f00 0001 E..,.d..@.......
0x0010: 7f00 0001 ce0e 0d05 0018 fe2b 5055 5420 ...........+PUT.
0x0020: 6120 7477 6f20 6170 706c 6573 a.two.apples
01:54:09.986574 IP 127.0.0.1.3333 > 127.0.0.1.52750: UDP, length 2
0x0000: 4500 001e 4402 0000 4011 0000 7f00 0001 E...D...@.......
0x0010: 7f00 0001 0d05 ce0e 000a fe1d 4f4b ............OK
01:54:09.986772 IP 127.0.0.1.52750 > 127.0.0.1.3333: UDP, length 5
0x0000: 4500 0021 8762 0000 4011 0000 7f00 0001 E..!.b..@.......
0x0010: 7f00 0001 ce0e 0d05 000d fe20 4745 5420 ............GET.
0x0020: 61 a
01:54:09.986825 IP 127.0.0.1.3333 > 127.0.0.1.52750: UDP, length 13
0x0000: 4500 0029 8ff8 0000 4011 0000 7f00 0001 E..)....@.......
0x0010: 7f00 0001 0d05 ce0e 0015 fe28 4f4b 2074 ...........(OK.t
0x0020: 776f 2061 7070 6c65 73 wo.apples
01:54:09.987041 IP 127.0.0.1.52750 > 127.0.0.1.3333: UDP, length 5
0x0000: 4500 0021 18e2 0000 4011 0000 7f00 0001 E..!....@.......
0x0010: 7f00 0001 ce0e 0d05 000d fe20 4445 4c20 ............DEL.
0x0020: 61 a
01:54:09.987094 IP 127.0.0.1.3333 > 127.0.0.1.52750: UDP, length 2
0x0000: 4500 001e 8595 0000 4011 0000 7f00 0001 E.......@.......
0x0010: 7f00 0001 0d05 ce0e 000a fe1d 4f4b ............OK
01:54:09.987255 IP 127.0.0.1.52750 > 127.0.0.1.3333: UDP, length 5
0x0000: 4500 0021 7ea5 0000 4011 0000 7f00 0001 E..!~...@.......
0x0010: 7f00 0001 ce0e 0d05 000d fe20 4745 5420 ............GET.
0x0020: 61 a
01:54:09.987315 IP 127.0.0.1.3333 > 127.0.0.1.52750: UDP, length 17
0x0000: 4500 002d b867 0000 4011 0000 7f00 0001 E..-.g..@.......
0x0010: 7f00 0001 0d05 ce0e 0019 fe2c 4552 5220 ...........,ERR.
0x0020: 6b65 7920 6e6f 7420 666f 756e 64 key.not.found
author: burton rosenberg
created: 14 oct 2026
update: 21 oct 2026