CSE 40771 - Distributed Systems - Spring 2026
In this assignment, you will convert your (previously) in-memory hashtable into a persistent storage service by making use of the checkpointing-and-logging approach discussed in class. Again, you will measure the performance of the operations, and evaluate the cost of persistent storage against memory.
There are two major problems to address in this assignment, and we will now see a distinction between data and metadata. The file data, or its actual contents, will need to be stored on the server’s disk rather than in the hash table. The file metadata will remain in the hash table, but we need to provide a mechanism for it to be recovered if the server experiences a failure.
Use your prior assignment submission as the starting point,
and continue with the same general code organization as before.
It’s OK to add additional files and classes to the project, as long
as the server main program is still called HashTableServer.py and
the test programs are called TestXYZ.py
In the last assignment you may have forseen the issue that we are storing file data in our hash table. If we wanted to store a substantial amount of data we would quickly fill the server’s memory. Your client program has the ability on a lookup to write the retrieved file to the disk. You will need to give your server the same functionality when a file is inserted into the table.
With the files or previous hash table “values” stored on disk, we no longer need to keep the file data in memory. We still need to be able to identify the files from their keys, or filenames. Thus, your new hash table values should at a minimum be the path to the file on disk. You may find it convenient to create a class or struct for metadata which contains the path and other attributes such as file size.
DO NOT allow the client to insert files to arbitrary paths on your server. Designate a data directory for your server on startup. Store files inserted by clients only this directory. When a file is inserted into the hash table you must name it yourself, either sanitizing the name of the key, or even better, creating a random name to avoid conflicts.
An online storage service must write data to a persistent location (such as disk or non-volatile memory) so that it does not lose information when the server software or hardware crashes. In a production system, a server would ordinarily pass data to a database server to store it safely, but that’s just passing the buck – the database server now has the same problem of storing data persistently. Let’s solve it ourselves directly.
There are two very simple approaches that don’t scale very well. One approach would be to just write out the entire state of the hash table to a file whenever any element of the table changes. That could work (if we are careful to commit atomically) but would become very expensive as the hash table grows. An alternate approach would be to write the contents of each key and value into a separate file, and just update each individual file as it changes, atomically committing the file on each change. Again, this could work, but would be very expensive if the table grows to millions of entries. Each file in a filesystem requires an inode, a directory entry, and at least one data block (typically 4KB), which would become very inefficient at large scales.
A common solution is to strike a balance between the two approaches by using two data structures stored in separate files: a checkpoint and a transaction log.
A checkpoint file (table.ckpt) is a direct representation of the state of the server at some
(current or previous) point in time. In this case, it is a direct dump of the state of the hash
table: all the keys and their corresponding values. (For this project, the exact representation
of the checkpoint file is up to your discretion.)
A transaction log (table.txn) captures the sequential list of updates applied to a server,
since the last checkpoint file was written. The log is structured as a sequence of events that
completely and accurately describe each individual change. It is common for each log entry to include
additional metadata – the time of change, the user making the change, the previous value, etc –
so that it is possible to “audit” prior events and reconstruct the history of the data store.
(For this project, the exact representation of the transaction log is up to your discretion.)
Together, the checkpoint and transaction log describe the current state of the hash table. To obtain the current state of the system, the server need only load the checkpoint file in its entirety, and then read the transaction log, “playing back” each entry as a series of modifications to the table in memory. Once all entries are played back, the most up-to-date state of the hash table is present in memory.
Ideally at this point we would consider the server to be recovered, but depending on the time and nature of the failure we may have a disagreement between the contents of the hash table and the data stored on disk. Once the hash table is rebuilt from the checkpoint and transaction log, make sure each file described in the hash table is actually present on the disk. It is also a good idea to verify the file contents by checking the size, or previously computed crc, checksum, or hash.
For this assignment, you will modify your server to store file data on the disk and the hash table data persistently
using a checkpoint file and transaction log. Please call your checkpoint file table.ckpt and
your transaction log table.txn, and proceed as follows:
The server should maintain a hash table in memory, as before. For each operation
that does not modify the table, it can simply service the request from memory/disk.
But, for each modification made to the table, the server must add an entry
to the transaction log before modifying the table in memory. (Don’t forget to flush and sync to ensure that data is written to disk.)
If the transaction log ever becomes too large, then the server must compact the log by writing out a new complete checkpoint file, and deleting the old checkpoint and transaction log. This compaction must be done atomically so that, if interrupted, no data is lost.
On startup, the server should read the checkpoint file into memory, then open the transaction log and “play back” all entries in the log, modifying the hash table in memory as it goes.
Either while rebuilding the hash table, or immediately after, check that each value in the table references a real file on disk, with some method other than simply comparing the name.
At this point the server is “caught up” and can continue normal operations. (And, if no checkpoint and transaction log are present, it should assume that this is a “fresh start” and create files as appropriate.)
From the end user’s perspective, there should be no change in how the server and client are deployed: both clients and servers are run in the same way as before. In fact, you may not need to change the client code at all unless you need to modify the format of your messages.
To stop the server, simply use kill or Control-C to stop the process.
If you have designed your checkpoint and transaction log correctly, then
you should be able to simply restart the server, and observe that the state
of the hash table is recovered. This mode of operation is known as “crash only” design:
the server has no notion of a “clean shutdown” and is always using/testing its capability
of recovering from a crash.
** For this assignment, your server should compact when the transaction log has more than 100 entries. That’s artificially small, but will make it easy to test and observe that compaction is working. **
Continue to use the two test programs from the prior assignment:
TestBasics.py should exercise all of the RPC operations to test correctness, as before.
TestPerf.py should time the throughput of all operations in four stages, as before.
And create a third test program:
TestOutliers.py should perform a large number of insert and remove pairs, sufficient to force the server to compress the transaction log multiple times. Time each individual operation and keep track of the fastest and slowest instance of each.Please review the general instructions for submitting assignments.
Turn in all of your source code, along with a lab report titled REPORT that describes the following in detail:
TestPerfTestOutliers