CS647 Assignment 3 (tinylog):  Add a simple write-ahead log to recover from failures

The goal of this assignment is to write a simple library that provides a write-ahead log that stores all kv pairs in the order they arrive to the store. 

(a) Flush each kv pair to the log as it arrives and before returning to the user. 

(b) After you flush the KV pairs, start updating the store and its metadata (index, allocator).

(c) From time to time, persist (checkpoint) the metadata to the device. You can do this only at the end, but it is more realistic to do it periodically (in smaller or larger intervals). Here, you need to consider what happens if a failure occurs during this checkpoint.

(d) From time to time, clean (truncate) the log at a point where you know all kv pairs are safely stored in the kv store AND the kv store metadata are correct and uptodate on the device. 

(e) When starting after a failure (crash), read the kv store metadata and then replay the rest of the kv pairs from the WAL. This should result in a consistent kv store that contains all kv pairs that  have been acknowledged to the clients. 

Try your recovery mechanism with "kill -9" to a program using the store.

Extra credit: Replace flushing kv pairs to the log with a group flush mechanism that buffers in memory kv pairs before flushing.

The assignment:

1. The library

Implement a tinylog library on top of tinyindex that implements a write-ahead log. For tinylog you can use an API, such as:

void append(char *key, char *value); //Appends key, value in the log

void checkpoint_metadata(void *); // checkpoints all metadata of the kv store

int truncate(); //Truncates the existing log, return 1 on success 0 on failure

tinyindex replay(); Returns a tinyindex if there are valid entries in the write-ahead log

Note! To simplify your implementation when opening the WAL file use the following flags O_DIRECT | O_SYNC | O_APPEND. This results in atomic writes to the file, meaning that for each write to the file which does not complete (e.g. due to failure), it will not be visible when reopening the file.

2. Driver program

Use YCSB (or similar) to call tinylog and measure throughput and latency for different patterns, IO sizes, number of threads, number of asynchronous IOs. Run a set of numbers for a ramdisk/HDD/SSD.

Submission 

Turn in (by mail to h y 6 4 7 @ c s d . u o c . g r) a tar file that contains your solutions and a README file stating assumptions or special features.

___________________________________________________________________________________________________________________________________
(c) Copyright University of Crete, Greece, Last Modified: 10-Oct-2022