CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Rate and time (20 minutes)

A run of 5,000 records takes 0.689 s. Find the records per second and the microseconds per record.

Done when: 7,257 records per second (7,262 in the measured line, from a rounded time) and 137.8 microseconds.

Hint

records per second is 5,000 divided by the time. Per record is the reverse.

Easy 2: Writes per record (20 minutes)

A run causes 15,002 device writes for 5,000 records, each with its own fsync. How many device writes does one record cause?

Done when: 3.0.

Hint

divide the device writes by the records.

Easy 3: Speed-up (20 minutes)

The run with an fsync every record takes 0.689 s and the run with every 100 takes 0.059 s. Find the speed-up.

Done when: 11.7.

Hint

divide the two times.

Medium

Medium 1: The fixed cost (45 minutes)

A run without fsync takes 0.034 s and a run with 5,000 calls takes 0.689 s. Find the cost of one fsync, and predict the time with 500 calls.

Done when: 131 microseconds, and a prediction of 0.034 + 500 x 0.000131 = 0.0995 s, compared with the measured 0.108 s.

Hint

subtract the two times and divide by the number of calls.

Medium 2: Loss limit (45 minutes)

A service may lose at most 1 MiB of acknowledged data in a crash and records are 4 KiB. What is the largest group size, and what rate does the table of section 4 suggest?

Done when: a group of 256 records, which loses at most 255 records (1,020 KiB), and a rate above 84,963 records per second.

Hint

1 MiB / 4 KiB = 256 records. A sync every 100 loses at most 99.

Medium 3: Run it (45 minutes)

Compile and run the program of section 2 on your machine, giving a file path on the disk you want to test and the disk's name from /proc/diskstats. Make a table like the one in section 4.

Done when: four rows of your own with the device writes, and a sentence on how many writes you saw for each fsync.

Hint

the disk name is the third column of /proc/diskstats, for example sda or nvme0n1.

Hard

Hard 1: Time-based group commit (90 minutes)

Change the program so that it syncs when 5 ms have passed since the last sync, instead of after a count. Report the rate, and the largest number of records that were unsynced at any time.

Done when: a rate, a maximum count of unsynced records, and a sentence that says that the loss is now limited in time, not in count.

Hint

check clock_gettime after each write and sync if 5 ms have gone.

Hard 2: Two writers (90 minutes)

Run two copies of the program at once, on two different files, with fsync every record. Report the rate of each and the total, and say whether the sync cost adds up or overlaps.

Done when: two rates and a total, compared with the single-writer rate, with a sentence on whether the total is about double.

Hint

use two shell jobs with different file names.

Hard 3: The spinning disk (90 minutes)

Using the model of page 1 for a 7,200 RPM disk, 9 ms seek and 100 MB/s, estimate the cost of one fsync of one 4 KiB record that needs three writes to different places. State your assumptions, and find the time for 5,000 records with a sync every record and every 100.

Done when: a written assumption list, a time for each case, and a comparison with the 0.689 s and 0.059 s measured here, with a sentence on which fixed cost dominates.

Hint

one write needs about one seek and half a turn (13.2 ms in the page 1 model) unless the writes are neighbours.