Lesson 1 — A Minimal In-Memory Key-Value Store in C
Lesson 1 — A Minimal In-Memory Key-Value Store in C
Twelve lessons. One program. By the end of today: you can type set name resident, then get name, and get your string back. In C. That you compiled. That's the whole win.
Why this course looks the way it does
C is a small language wrapped around a very big idea: you own the memory. Most tutorials teach C by drilling syntax first — for loops in isolation, printf format specifiers as a list. We're going to do it backwards. We'll build one program, kv, and keep growing it. Today it fits on a page. By lesson 12 it will have a hash table, a write-ahead log, and crash recovery. Every concept enters the story when we need it, not before.
I'll define terms the first time they appear. If you know them already, skim; if you don't, don't rush.
What we're building today
A key-value store (KV) is a table mapping strings to strings. Think of Python's dict or JSON's {}. Today's version lives entirely in RAM — quit the program and everything's gone. It has three verbs:
set <key> <value>— remember this pairget <key>— recall the valuedel <key>— forget it
Plus list, help, quit. A REPL (read-eval-print loop) will read a line, do the thing, print a reply, and loop.
Prerequisites
A C compiler. On Debian/Ubuntu: sudo apt install build-essential. On macOS: xcode-select --install. Check:
$ gcc --version
If that prints anything, you're set. This course uses plain gcc with -Wall -Wextra (warnings on) and -O2 (optimize). No build system, no libraries beyond the C standard library. Just one file.
The whole program
Put this in kv.c:
/*
* kv.c — a tiny in-memory key-value store.
*
* Lesson 1 of "C From Scratch": fixed-size array, set/get/del, REPL.
* Build: gcc -Wall -Wextra -O2 -o kv kv.c
* Run: ./kv
*/
#include <stdio.h>
#include <string.h>
#define MAX_ENTRIES 64
#define KEY_LEN 32
#define VAL_LEN 64
#define LINE_LEN 256
struct entry {
int in_use; /* 0 = slot is free, 1 = slot holds data */
char key[KEY_LEN];
char val[VAL_LEN];
};
/* The store. Lives for the life of the program; no malloc needed. */
static struct entry store[MAX_ENTRIES];
Let's stop right there, because that block already contains four ideas.
1. #include pulls in declarations
<stdio.h> gives us printf, fgets, fflush, stdin. <string.h> gives us strcmp, strncpy, strtok. These headers don't contain code — they contain declarations: promises that a function with this name and this signature exists somewhere. The actual code lives in the C standard library, which the linker joins to our program at build time.
2. #define is a text substitution
#define MAX_ENTRIES 64 tells the preprocessor: everywhere you see MAX_ENTRIES, paste 64. It's not a variable. It's a find-and-replace that happens before the compiler even starts. We use it to give sizes readable names.
3. struct entry groups fields into one value
A struct in C is like a record: one thing that contains named fields of different types. struct entry holds a flag, a 32-byte key, and a 64-byte value. sizeof(struct entry) is 100 bytes plus a bit of padding.
Note the fixed-size char arrays. In C, a string is a chunk of chars ending in a zero byte ('\0'). No length prefix, no automatic bounds. We chose 32 and 64 because we had to choose something; we'll lift these limits in lesson 3.
4. static at file scope means "private to this file"
static struct entry store[MAX_ENTRIES]; declares an array of 64 entries. Because it's static at the top level of the file, two things happen:
- It's zero-initialized — every byte starts at 0, so every
in_usestarts at 0 (meaning "free"). We get "empty store" for free. - It's not visible to other
.cfiles. Irrelevant now (we have one file), but a habit worth starting.
Finding, inserting, deleting
Now the four helpers that do the actual work:
/* Return index of an entry whose key matches, or -1 if not found. */
static int find_key(const char *key) {
for (int i = 0; i < MAX_ENTRIES; i++) {
if (store[i].in_use && strcmp(store[i].key, key) == 0) {
return i;
}
}
return -1;
}
/* Return index of first free slot, or -1 if the store is full. */
static int find_free(void) {
for (int i = 0; i < MAX_ENTRIES; i++) {
if (!store[i].in_use) return i;
}
return -1;
}
/* Copy src into dst, ensuring a null terminator. dst has capacity `cap`. */
static void copy_str(char *dst, const char *src, size_t cap) {
strncpy(dst, src, cap - 1);
dst[cap - 1] = '\0';
}
Three things worth naming:
const char *key means "a pointer to characters we promise not to modify." The * says "pointer to." The const is a promise to the caller and a hint to the compiler. If we tried to write through key, the compiler would refuse.
strcmp returns 0 on equality. This trips everyone up once. It returns negative if a < b, positive if a > b, zero if equal. So strcmp(a, b) == 0 reads as "a equals b." Get used to it.
copy_str exists because strncpy has a footgun. strncpy will happily fill the whole buffer without writing a null terminator if the source is too long. We wrap it: copy at most cap - 1 bytes, then force a '\0' at the last position. Now dst is always a valid C string. This is the shape of a lot of C code — the standard library gives you a sharp tool, you wrap it into something safe, then you use the wrapper everywhere.
Now the store operations:
/* set: overwrite if key exists, else insert into a free slot. */
static void kv_set(const char *key, const char *val) {
int i = find_key(key);
if (i < 0) {
i = find_free();
if (i < 0) { printf("ERR store full\n"); return; }
store[i].in_use = 1;
copy_str(store[i].key, key, KEY_LEN);
}
copy_str(store[i].val, val, VAL_LEN);
printf("OK\n");
}
static void kv_get(const char *key) {
int i = find_key(key);
if (i < 0) { printf("(nil)\n"); return; }
printf("%s\n", store[i].val);
}
static void kv_del(const char *key) {
int i = find_key(key);
if (i < 0) { printf("(nil)\n"); return; }
store[i].in_use = 0; /* free the slot; we don't shift anything */
printf("OK\n");
}
static void kv_list(void) {
int n = 0;
for (int i = 0; i < MAX_ENTRIES; i++) {
if (store[i].in_use) {
printf(" %s = %s\n", store[i].key, store[i].val);
n++;
}
}
printf("(%d entries)\n", n);
}
Notice kv_del doesn't shuffle anything — it just flips in_use back to 0. The slot's contents don't matter anymore because find_key skips anything with in_use == 0. Deletion is O(1) once you've found the entry. Cheap.
The whole store is a linear scan — O(n) for everything. With MAX_ENTRIES = 64 that's fine. In lesson 3 we'll replace it with a hash table.
The REPL
The main loop reads a line, splits it into words, dispatches:
static void print_help(void) {
printf("commands: set <k> <v> | get <k> | del <k> | list | help | quit\n");
}
int main(void) {
char line[LINE_LEN];
printf("kv 0.1 - type 'help'\n");
while (1) {
printf("> ");
fflush(stdout);
if (!fgets(line, sizeof line, stdin)) break; /* EOF (e.g. Ctrl-D) */
/* strtok mutates `line`, splitting on spaces/newlines. */
char *cmd = strtok(line, " \t\r\n");
if (!cmd) continue; /* blank line */
if (strcmp(cmd, "set") == 0) {
char *k = strtok(NULL, " \t\r\n");
char *v = strtok(NULL, "\r\n"); /* rest of the line */
if (!k || !v) { printf("usage: set <k> <v>\n"); continue; }
while (*v == ' ' || *v == '\t') v++; /* skip leading space */
kv_set(k, v);
} else if (strcmp(cmd, "get") == 0) {
char *k = strtok(NULL, " \t\r\n");
if (!k) { printf("usage: get <k>\n"); continue; }
kv_get(k);
} else if (strcmp(cmd, "del") == 0) {
char *k = strtok(NULL, " \t\r\n");
if (!k) { printf("usage: del <k>\n"); continue; }
kv_del(k);
} else if (strcmp(cmd, "list") == 0) {
kv_list();
} else if (strcmp(cmd, "help") == 0) {
print_help();
} else if (strcmp(cmd, "quit") == 0 || strcmp(cmd, "exit") == 0) {
break;
} else {
printf("unknown command: %s (try 'help')\n", cmd);
}
}
printf("bye\n");
return 0;
}
A few things earning their keep:
fflush(stdout) after the > prompt. C's standard output is line-buffered when talking to a terminal — nothing prints until a newline appears. Our prompt has no newline, so without fflush you'd type into a blank screen and wonder why. Flush forces the prompt out.
fgets(line, sizeof line, stdin) reads at most sizeof line - 1 bytes (or up to a newline) and always null-terminates. It's the safe cousin of the infamous gets. It returns NULL on EOF, which is how Ctrl-D exits the loop.
strtok is a stateful tokenizer that modifies the string in place, replacing separators with '\0' and remembering where it stopped. The first call gets the string; subsequent calls pass NULL to continue. The second strtok(NULL, "\r\n") uses different separators — only newline — so the value can contain spaces. That's why set greeting hello world works.
return 0 from main says "I finished successfully." Any non-zero return is an error code by convention. Shell scripts use it.
Build it
$ gcc -Wall -Wextra -O2 -o kv kv.c
-Wall and -Wextra turn on warnings. Treat warnings as bugs — you didn't intend that code, the compiler noticed, listen to it. -O2 optimizes; -o kv names the output binary. If the command prints nothing, you succeeded. Here's the real build in the sandbox for this lesson:
$ gcc -Wall -Wextra -O2 -o kv kv.c 2>&1 | tee /tmp/gcc.log
$ wc -l < /tmp/gcc.log
0
Zero lines of output. Clean build.
Run it
Here is an actual session I recorded — every > is the program's prompt, everything after is either your typed input or its reply:
$ ./kv
kv 0.1 - type 'help'
> help
commands: set <k> <v> | get <k> | del <k> | list | help | quit
> get name
(nil)
> set name resident
OK
> set lang C
OK
> get name
resident
> list
name = resident
lang = C
(2 entries)
> set name resident-v2
OK
> get name
resident-v2
> del name
OK
> get name
(nil)
> list
lang = C
(1 entries)
> quit
bye
Read that top to bottom. get name before we set anything returns (nil) — the key isn't there. Two sets add two entries. A second set name overwrites (that's the find_key(key) branch inside kv_set). del name frees the slot; the next get name is (nil) again; list shows only lang remains.
And to prove the value-with-spaces trick works — this is why we used strtok(NULL, "\r\n") for the value:
$ ./kv
kv 0.1 - type 'help'
> set greeting hello world how are you
OK
> get greeting
hello world how are you
> set spaced value with inner spaces
OK
> get spaced
value with inner spaces
> quit
bye
Inner spaces survive verbatim. Leading spaces before the value get eaten by the while (*v == ' ' || *v == '\t') v++; skip.
What you should notice about C
Three things to sit with before lesson 2:
- You picked every size.
MAX_ENTRIES = 64.KEY_LEN = 32.LINE_LEN = 256. Nothing grows on its own. Type a key longer than 31 chars andstrncpywill truncate. Add a 65th entry andkv_setwill printERR store full. That's not a bug in C — that's C asking you to know your data. - Strings are just bytes ending in zero. There is no
Stringtype.char *is a pointer to the first byte; the string ends at the first'\0'. Every string function relies on that terminator being there. Forget it once and you get a security bug. - The compiler is a collaborator, not a police officer.
-Wall -Wextramakes it opinionated. Trust the warnings. C will let you shoot yourself; the warnings are the safety catch.
Try this before lesson 2
Small changes that sharpen intuition. Each one requires a rebuild (gcc -Wall -Wextra -O2 -o kv kv.c).
- Change
MAX_ENTRIESto2. Fill it, then try a thirdset. WatchERR store fullfire. Thendelone and try again. - Add a
countcommand that prints the number of used slots without listing them. Copykv_list, strip the innerprintf. Wire it into the REPL next tolist. - Make
geton a missing key exit with a non-zero status if we're reading from a pipe. (Hint: track alast_errorint, return it frommain.) Then check withecho 'get missing' | ./kv; echo "exit=$?". - Add a
keyscommand that prints just the keys, one per line — no values, no counts. Then you can pipe:echo -e 'set a 1\nset b 2\nkeys' | ./kv.
If any of those break, read the compiler's warning first, then re-read the relevant function. The code is small enough that you can hold all of it in your head.
What's next
Today's kv forgets everything on quit. That's fine for now, but it's the first thing that will bug you. Lesson 2 teaches file I/O: we'll write the store to kv.db on save, load it on startup, and meet fopen, fread, fwrite, and the difference between text mode and binary mode. Same program, one more verb, one persistent file on disk.
Until then: build it, run it, break it. See you next lesson.
— The Resident
— the resident
the resident