Ring Buffers

Added on January 3, 2017 and completed 0 times.

One particularly desirable property for systems we design is that they consume a predictable quantity of resources. In this day and age, it is still common for engineers to be woken from their sweet dreams by an alert informing them logs have suddenly consumed the majority of the disk space on one of their servers.

In the fight for predictability, ring buffers are an interesting data structure which allow us to use a fixed amount of memory, and which are frequently used for storing time series data. In short, a ring buffer is a datastructure which wraps around when it reaches its end, always maintaining a fixed size, and prefers to overwrite earlier data instead of extending itself.

Let's imagine we are relying on ring buffer to store `n`, number of requests over each second to one of our services for the last `k` seconds, and each second we write a number of requests. There are two operations we an perform:

write(n, t) will add a new entry for the number of requests at time `t`. This operation should never fail. If the buffer is full, then it should loop around the buffer.

read(t) should return the number of requests per second at time `t`, and should return -1 if a value is not stored for for time `t`, (for example, if that time is too far in the past and has already been lost).

Taking a simple case, a program would take these inputs over stdin:

Input
10
r 0
w 10 1
w 5 2
r 1
r 2
r 3
Output
# no output, this is 'k', the size of buffer
0 -1
# no output
# no output
1 20
2 5
3 -1

Then getting a bit trickier, consider this:

Input
w 4 8
r 3
r 4
Output
# no output
3 0
4 8

Although you never wrote a value for t=3, because you wrote a value at a later point in time, you know that there was no traffic until that point (in this problem, where we are operating in a world without race conditions)! Pushing your implementation a bit further, taking this input:

Input
10
r 0
r 10
r 100
w 1 3
w 2 5
w 3 7
r 2
r 4
w 10 11
r 5
r 9
r 10
r 1
w 11 13
r 11
r 1
w 50 17
r 11
r 49
r 50
Output
# no input
0 -1
10 -1
100 -1
# no input
# no input
# no input
2 5
4 -1
# no input
5 0
9 0
10 11
1 3
# no input
11 11
1 -1
# no input
11 -1
49 0
50 17

If your implementation worked correctly, then you're definitely ready to validate your solution!

You'll need to log in to submit solutions.

Related papers
Name Year Topic Rating
I've been writing ring buffers wrong all these years 2016 Ring Buffers ★★★
Using Ring Buffer Logging to Help Find Bugs 2000 Ring Buffers ★★★