I was recently doing an assignment for a job interview, which asked to create a simple key value database with 4 command line operations:
- create key value: Adds a key value pair/updates an existing key
- get key: Prints the value corresponding to key, if it exists
- del key: Deletes a key value pair
- ts key: Returns the timestamps a key was first set and last set
It was to be written in C with no external database libraries. I successfully implemented it (although it took longer than recommended- hadn't worked with C strings for a while). However, I did not progress to the next step of the application process.
What ways can I improve? Even some general tips would be great. I've only been programming for a year and a half (undergraduate was in mathematics), so I am aware that the code is probably packed with bad conventions etc.
General Idea
The general idea of my implementation was to have an index binary file which would provide file offsets for each key index (first two letters of key) to allow fast lookup. Another binary file would store the key value pairs and any timestamps etc contiguously to save memory.
To set, the key is added to the index file. This calculated offset then gives the offset at which the key should be added/updated. The data file is then rewritten to include the new key/updated key. The rewriting is expensive, but if the database was large you could implement multiple data files pointed to by the index file. Plus I wasn;t sure how you'd get around rewriting the files for .bin/.txt files.
To get, the index file is used to calculate the file offset. The key is then searched for using this offset and the corresponding value (if there is one) is returned.
main.c
/**
* @brief Main function for implementing IO for the database.
* Database is a binary file, with an index file to make getting values faster.
* Binary file is quicker to write and read to. Data is stored dynamically and contiguously so memory footprint is small.
* All values are stored in alphabetical order in both index.bin and data.bin. This implementation is scalable. If database
* will be large, can extend implementation to have multiple data files holding different alphabetical ranges.
* These will be pointed to by the index file.
* @date 24-10-2023
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/file.h>
#include <semaphore.h>
#include "definitions.h"
#include "index.h"
#include "set.h"
#include "get.h"
int main(int argc, char* argv[]){
sem_t mutex;
if (sem_init(&mutex, 0, 1) != 0) {
perror("sem_init");
return -1;
}
// Open files if they exist, else create them
FILE* index = fopen("index.bin", "r");
if (index == NULL) index = fopen("index.bin", "w+");
FILE* data = fopen("data.bin", "r");
if (data == NULL) data = fopen("data.bin", "w+");
if (index == NULL){
perror("Error opening index.bin\n");
return -1;
}
if (data == NULL){
perror("Error opening data.bin\n");
return -1;
}
char command[10];
strncpy(command, argv[1], 10);
if (strcmp(command, "set") == 0){
if (argc != 4){
printf("Incorrect numer of arguments entered\nUsage: ./test set key value\n");
fclose(data); fclose(index);
return 0;
}
// Begin by initialising a Pair struct
Pair* entry = malloc(sizeof(Pair));
entry -> keySize = strlen(argv[2]) + 1;
if (entry -> keySize > MAX_KEY_SIZE){
fprintf(stderr, "Entered key is too long. To adjust maximum key size, please edit #define in utility.h\n");
fclose(data); fclose(index);
return -1;
}
entry -> valueSize = strlen(argv[3]) + 1;
if (entry -> valueSize > MAX_VALUE_SIZE){
fprintf(stderr, "Entered value is too long. To adjust maximum value size, please edit #define in utility.h\n");
fclose(data); fclose(index);
return -1;
}
time(&(entry -> firstSet));
time(&(entry -> lastSet));
// Use semaphores to ensure exclusive write access
sem_wait(&mutex);
set(data, index, argv[2], argv[3], entry, 0);
sem_post(&mutex);
free(entry);
}
else if (strcmp(command, "get") == 0){
if (argc != 3){
printf("Incorrect number of arguments entered.\nUsage: ./test get key\n");
fclose(data); fclose(index);
return -1;
}
// Don't need any semaphores here - writing processes write to a temp file then rename so no issues with reading
get(data, index, argv[2], 0);
}
else if (strcmp(command, "ts") == 0){
if (argc != 3){
printf("Incorrect number of arguments entered.\nUsage: ./test ts key\n");
fclose(data); fclose(index);
return -1;
}
// Don't need any semaphores here - writing processes write to a temp file then rename so no issues with reading
get(data, index, argv[2], 1);
}
else if (strcmp(command, "del") == 0){
if (argc != 3){
printf("Incorrect number of arguments entered.\nUsage: ./test del key\n");
fclose(data); fclose(index);
return -1;
}
char value[] = "null";
Pair* entry = malloc(sizeof(Pair));
// Use semaphores to ensure exclusive write
sem_wait(&mutex);
set(data, index, argv[2], value, entry, 1);
sem_post(&mutex);
free(entry);
}
else if (strcmp(command, "help") == 0){
printf("Usage:\n");
printf("./kvdb set key value\tSets a key value pair in the database\n");
printf("./kvdb get key\t\tGets the value correspoding to the entered key from the database\n");
printf("./kvdb ts key\t\tReturns the timestamp that this key was first and last set.\n");
printf("./kvdb del key\t\tDeletes a key value pair from the database\n");
}
else{
printf("Unknown command entered. For help type ./kvdb help\n");
}
sem_destroy(&mutex);
fclose(index);
fclose(data);
return 0;
}
set.h
#ifndef SET_H_
#define SET_H_
int writePair(FILE* data, char* key, char* value, Pair* kv);
int addToData(FILE* data, char* key, char* value, Pair* entry, long int* difference, int mode);
int set(FILE* data, FILE* index, char* key, char* value, Pair* entry, int mode);
#endif
set.c
/**
* @brief File containing function definitions for setting/deleting lines to/from the database
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "definitions.h"
#include "index.h"
/**
* @brief Simple function to write a KV entry to file
* @param[in] data Pointer to data file
* @param[in] key String containing key
* @param[in] value String containing value
* @param[in] kv Pair object containing sizes of key and value as well as time first set and time last set
*/
int writePair(FILE* data, char* key, char* value, Pair* kv){
if(fwrite(&(kv -> keySize), sizeof(size_t), 1, data) != 1) perror("ERROR: Failed writing key size\n");
if(fwrite(&(kv -> valueSize), sizeof(size_t), 1, data) != 1) perror("ERROR: Failed writing value size\n");
fwrite(key, 1, (kv -> keySize), data);
fwrite(value, 1, (kv -> valueSize) , data);
if(fwrite(&(kv -> firstSet), sizeof(time_t), 1, data) != 1) perror("ERROR: Failed writing firstSet\n");
if(fwrite(&(kv -> lastSet), sizeof(time_t), 1, data) != 1) perror("ERROR: Failed writing lastSet\n");
return 0;
}
/**
* @brief Function to write a new entry into the data file in the correct alphabetical position.
* @param[in] data Pointer to data file
* @param[in] key String containing key to be added
* @param[in] value String containing value to be added
* @param[in] entry Pair object containing sizes of key and value and times key was first set and last set
* @param[in] mode Determines if a key is being added with set or deleted with del
* @param[out] difference Contains, if the key is new, the size of the entry in bytes. If key exists and is being updated,
* contains the difference in size between the old and new value. If key is being deleted, contains
* the size of the deleted chunk
*/
int addToData(FILE* data, char* key, char* value, Pair* entry, long int* difference, int mode){
// Check if this is first value to be added
rewind(data);
// Open temp file
FILE* tempData = fopen("tempData.bin", "w") ;
if(tempData == NULL) printf("Error opening tempData.bin\n");
Pair* read = malloc(sizeof(Pair));
char* readKey = malloc(MAX_KEY_SIZE);
char* readValue = malloc(MAX_VALUE_SIZE);
// Pair struct to hold read in entries
if (fread(&(read -> keySize), sizeof(size_t), 1, data) == 0){
writePair(tempData, key, value, entry);
}
else{
rewind(data);
int updated = 0;
while(fread(&(read -> keySize), sizeof(size_t), 1, data) == 1){
// Read in current KV entry from data file
fread(&(read -> valueSize), sizeof(size_t), 1, data);
readKey = realloc(readKey, read -> keySize);
readValue = realloc(readValue, read -> valueSize);
fread(readKey, 1, (read -> keySize), data);
fread(readValue, 1, (read -> valueSize), data);
readKey[(read -> keySize)-1] = '\0'; readValue[(read -> valueSize)-1] = '\0';
if (fread(&(read -> firstSet), sizeof(time_t), 1, data) == 0) printf("firstSet not read in correctly\n");
if (fread(&(read -> lastSet), sizeof(time_t), 1, data) == 0) printf("lastSet not read in correctly\n");
// If the key already exists i.e. readKey == key, update and skip writing
if (strcmp(key, readKey) == 0){
if (mode == 0){
entry -> firstSet = read -> firstSet; // Update first write
// Difference in size of new key value pair
*difference = ((entry -> keySize) + (entry -> valueSize)) - ((read -> keySize) + (read -> valueSize));
writePair(tempData, key, value, entry);
}
else if (mode == 1){
// If deleting key, set difference to be minus the size of the deleted entry
*difference = -((read -> keySize) + (read -> valueSize) + 2*sizeof(size_t) + 2*sizeof(time_t));
}
updated = 1;
continue; // Replace line - don't write current line
}
// If the key didn't exist (we've passed where it should be in file), no updates required and don't skip writing
else if (compareString(key, readKey) == 1 && updated == 0 && mode == 0){
writePair(tempData, key, value, entry); // Don't replace line
updated = 1;
}
// Write read entry to new temp file
writePair(tempData, readKey, readValue, read);
}
// If not updated by the end of the file, add the entry to the end of file
if (updated == 0 && mode == 0){
writePair(tempData, key, value, entry);
}
else if (updated == 0 && mode == 1){
printf("Key not found\n");
}
}
// Free dynamically allocated memory
free(readValue);
free(readKey);
free(read);
// Now close files, delete old file and rename new file
fclose(tempData);
remove("data.bin");
rename("tempData.bin", "data.bin");
data = fopen("data.bin", "r");
return 0;
}
/**
* @brief Function to set a new key, update an old key or delete a key from the database. Handles updates to both index and data files
* @param[in] data Pointer to file containing data
* @param[in] index Pointer to file containing index
* @param[in] key String containing key to be added/updated/deleted
* @param[in] value If key to be added/updated, contains corresponding value. If key is to be deleted, contains "null"
* @param[in] entry Holds other relevant variables; key size, value size and times key was first and last set
* @param[in] mode Determines if key is to be added/updated (mode = 0) or deleted (mode = 1)
*/
int set(FILE* data, FILE* index, char* key, char* value, Pair* entry, int mode){
size_t keySize = entry -> keySize; // Extract values from struct
size_t valueSize = entry -> valueSize;
long int difference = 2*sizeof(size_t) + 2*sizeof(time_t) + keySize + valueSize; // Initialise difference to be size of new KV entry
addToData(data, key, value, entry, &difference, mode); // Insert this line in data file and update difference var
addIndexLine(index, key, difference); // Update index.bin to account for this new/updated/deleted key
return 0;
}
get.h
#ifndef GET_H_
#define GET_H_
#include <stdlib.h>
#include <stdio.h>
void printTime(time_t time);
int get(FILE* data, FILE* index, char* key, int mode);
#endif
get.c
/**
* @brief File containing functions to get KV pair/timestamp given the key
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "definitions.h"
#include "index.h"
/**
* @brief Small function to print time in the required format to stdout
* @param[in] time Time object containing seconds since 1/1/1970
*/
void printTime(time_t time){
char buf[50];
struct tm *ts = localtime(&time);
strftime(buf, 50, "%Y-%m-%d %H:%M:%S", ts);
printf("%s", buf);
}
/**
* @brief Function that uses the index and file offsets in the index.bin file to quickly retrieve KV pairs.
* @param[in] data Pointer to file containing data
* @param[in] index Pointer to file holding index
* @param[in] mode Whether get function should return KV or timestamp. mode == 0 => KV pair, mode == 1 => timestamp
* @return Returns 1 if key is found, 0 otherwise.
*/
int get(FILE* data, FILE* index, char* key, int mode){
// First get index of key, if it exists
long int startCount, endCount;
int exists = getDataIndex(index, key, &startCount, &endCount);
if (exists==0){
printf("Key not found\n");
return -1;
}
// Seek the starting offset given by the index file
fseek(data, startCount, SEEK_SET);
size_t readKeySize = 0; size_t readValueSize = 0;
time_t firstSet, lastSet;
// While within bounds given by index file, search for the key
while(fread(&readKeySize, sizeof(size_t), 1, data) != 0 && ftell(data) <= endCount){
fread(&readValueSize, sizeof(size_t), 1, data);
// Use dynamically allocated memory due to variable array length
char* readKey = malloc(readKeySize);
char* readValue = malloc(readValueSize);
fread(readKey, 1, readKeySize, data);
fread(readValue, 1, readValueSize, data);
readKey[readKeySize-1] = '\0'; readValue[readValueSize-1] = '\0';
fread(&firstSet, sizeof(time_t), 1, data);
fread(&lastSet, sizeof(time_t), 1, data);
// If keys match, return either the KV pair or the timestamp
if (strcmp(key, readKey) == 0){
if (mode == 0)
printf("Key: %s, value %s\n", key, readValue);
else if (mode == 1){
printf("Time first set:\t");
printTime(firstSet);
printf("\nTime last set:\t");
printTime(lastSet);
printf("\n");
}
return 1;
}
free(readKey);
free(readValue);
}
printf("Key not found\n");
return 0;
}
index.h
#ifndef INDEX_C_
#define INDEX_C_
#include <stdio.h>
int compareString(char* a, char* b);
void writeEntry(FILE* tempIndex, char* keyStart, size_t dataCount);
int addIndexLine(FILE* index, char *key, long int pairSize);
size_t getDataIndex(FILE* index, char *key, long int* startCount, long int* endCount);
#endif
index.c
/**
* @brief Function definitions for creating an ordered index of key starts, and their accompanying file offsets in the data.bin file
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
* @brief Compares the first two letters of two entered strings. Return is based on which string comes first when
* ordered alphabetically
* @param[in] a Pointer to the beginning of the first string
* @param[in] b Pointer to the beginning of the second string
* @return Returns 0 if start of strings are equal, 1 if the first string is smaller and 2 if the first string is larger
*/
int compareString(char* a, char* b){
char aStart[3]; char bStart[3];
strncpy(aStart, a, 2);
strncpy(bStart, b, 2);
aStart[2] = '\0'; bStart[2] = '\0';
if (strcmp(aStart, bStart) == 0)
return 0;
else if (a[0]<b[0])
return 1;
else if (a[0] == b[0] && a[1] < b[1] && strlen(a) >= 2 && strlen(b) >= 2)
return 1;
return 2;
}
/**
* @brief Small function to write entries to index.bin
* @param[in] tempIndex Pointer to the new index file that is being written to
* @param[in] keyStart Pointer to char array holding the null terminated start of the key.
* @param[in] dataCount Number of bytes written to the file after this entry is written
*/
void writeEntry(FILE* tempIndex, char* keyStart, size_t dataCount){
if (fwrite(keyStart, 1, 2, tempIndex) != 2)
fprintf(stderr, "Error writing key start %s to index file\n", keyStart);
if (fwrite(&dataCount, sizeof(size_t), 1, tempIndex) != 1)
fprintf(stderr, "Error writing dataCount for key start %s to index file\n", keyStart);
}
/**
* @brief This function updates the index.bin file when "set" or "del" commands are called. It handles a
* number of different cases:
* - set: New key index (i.e. Key with unique two letter start): Creates new entry in index.bin with
* the index and the file offset at which the key ends.
* - set: Existing key index: Updates the offset of the existing index to account for another KV pair
* being stored at this index.
* - del: Non existant key: Prints "Key not found"
* - del: Index corresponding to >1 KV pair: Updates the offset to remove element corresponding to entered key
* - del: Index corresponding to 1 KV pair: Deletes this index record from index.bin
* @param[in] index Pointer to index file
* @param[in] key String containing key
* @param[in] pairSize Contains one of the following (measures in bytes) depending on context:
* - Size of new KV pair.
* - Difference in size between new and old KV pairs (they have same key)
* - Size of deleted entry (will be negative)
*/
int addIndexLine(FILE* index, char *key, long int pairSize){
rewind(index);
FILE* tempIndex = fopen("tempIndex.bin", "w");
char ind[3];
char keyStart[3];
strncpy(keyStart, key, 2);
keyStart[2] = '\0';
int found = 0;
size_t dataCount = 0;
size_t prevDataCount = 0;
// If file is new or wrong format encountered, add as first line
if (fread(ind, 1, 2, index) == 0){
dataCount += pairSize;
writeEntry(tempIndex, keyStart, dataCount);
}
else{
rewind(index);
while(fread(ind, 1, 2, index) != 0){
ind[2] = '\0';
fread(&dataCount, sizeof(size_t), 1, index);
// If correct posiiton already found, increase offset and continue to writing
if (found != 0) dataCount += pairSize;
// Else, check if this is the correct position
else {
int result = compareString(keyStart, ind);
// If strings are equal, increase the count for the next string
if (result == 0){
dataCount += pairSize;
found = 1;
if (prevDataCount == dataCount){
// In this case, the key has no bytes associated with it in data file i.e. it is deleted
continue;
}
}
// If key is less, must update this data count to be prevDataCount + pairSize and update next dataCount
else if (result == 1){
size_t thisCount = prevDataCount + pairSize; // Update the new entry's count
dataCount = thisCount + (dataCount - prevDataCount); // Update next
writeEntry(tempIndex, keyStart, thisCount);
found = 1;
}
prevDataCount = dataCount;
}
// Now write back to file
writeEntry(tempIndex, ind, dataCount);
}
// If adding to end of file, must update dataCount accordingly
if (found == 0){
dataCount += pairSize;
writeEntry(tempIndex, keyStart, dataCount);
}
}
// fclose(index);
fclose(tempIndex);
remove("index.bin");
rename("tempIndex.bin", "index.bin");
index = fopen("index.bin", "r");
return 0;
}
/**
* @brief Function to obtain a file offset range that contains a particular key. This can be used to rapidly obtain
* keys in the data file.
* @param[in] index Pointer to index.bin file.
* @param[in] key Pointer to string containing key.
* @param[out] startCount On return, holds the start file offset in bytes, where the key is located within [startCount, endCount]
* @param[out] endCount On return, holds the end file offset in bytes.
*/
size_t getDataIndex(FILE* index, char *key, long int* startCount, long int* endCount){
rewind(index);
char ind[3];
char keyStart[3];
strncpy(keyStart, key, 2);
keyStart[2] = '\0';
// Initialise to 0 in case file is empty
*startCount = 0;
*endCount = 0;
size_t dataCount = 0;
// Read through to find the correct key start (if there is one) and return it's accompanying file offset range
while(fread(ind, 1, 2, index) != 0){
ind[2] = '\0';
int result = compareString(keyStart, ind);
fread(&dataCount, sizeof(size_t), 1, index);
if (result == 0){
*endCount = dataCount;
return 1;
}
else if (result == 1){
*endCount = *startCount;
return 0;
}
*startCount = dataCount;
}
*endCount = *startCount;
rewind(index);
return 0;
}
char command[10]; strncpy(command, argv[1], 10); if (strcmp(command, "set") ...Withargv[1]as"1234567890",commandis not a string as it lacks a null character. Thenstrcmp(command, ...is UB. \$\endgroup\$