detecting invalid iterators for a ring buffer

Question

I'm trying to implement a ring buffer (or circular buffer). As with most of these implementations it should be as fast and lightweight as possible but still provide enough safety to be robust enough for production use. This is a difficult balance to strike. In particular I'm faced with the following problem.

I want to use said buffer to store the last n system events. As new events come in the oldest get deleted. Other parts of my software can then access those stored events and process them at their own pace. Some systems might consume events almost as fast as they arrive, others may only check sporadically. Each system would store an iterator into the buffer so that they know where they left off last time they checked. This is no problem as long they check often enough but especially the slower systems may oftentimes find themselves with an old iterator that points to a buffer element that has since been overwritten without a way to detect that.

Is there a good (not too costly) way of checking whether any given iterator is still valid?

Things I came up with so far:

• keep a list of all iterators and store their valid state (rather costly)
• store not only the iterator in the calling systems but also a copy of the pointed-to element in the client of the buffer. On each access, check whether the element is still the same. This can be unreliable. If the element has been overwritten by an identical element it is impossible to check whether it has changed or not. Also, the responsibility of finding a good way to check elements lies with the client, which is not ideal in my mind.

Many ring buffer implementations don't bother with this at all or use a single-read-single-write idiom, where reading is deleting.

Answer 1

Instead of storing values, store (value, sequence_num) pairs. When you push a new value, always make sure that it uses a different sequence_num. You can use a monotonically increasing integer for sequence_num.

Then, the iterator remembers the sequence_num of the element that it was last looking at. If it doesn't match, it's been overwritten.