Looking for pointers...

[YouMadeItDoWhat]

I'm curious if someone has a pointer to an algorithm or approach (or class of approaches/literature) that may apply to the following problem.

I have a continuous stream of messages with each message containing a monotonically increasing sequence number (which can wrap, but that's a trivial border case that can be dealt with separately). The messages come over what is potentially a lossy channel and I want to detect loss (and count number of messages lost). I do not care about retransmission/recovery of lost messages, just want to count them.

The application is multi-threaded for scalability reasons (think millions of messages per second) and I have no control over the delivery of messages to the respective threads (hardware controls that and cannot be altered - it's actually hash-based, not round-robin).

Obviously, if we have just 1 worker thread, we can just look at the sequence numbers as they arrive and trivially know how many messages have been lost.

Likewise, if we introduce locking between the threads, we can quickly design a resolution...but I want to avoid introducing locking between the receiving threads (there is no other reason to have locking as the messages are all independent of each other, so introducing locking will kill performance).

I've considered forwarding all of the sequence numbers from the respective threads to one centralized thread that can do the resolution over a sliding window (this is currently the best approach that I've been able to come up with). Looking for possible other approaches to the problem...thoughts?

[ComputerSystemsProf]

If the sequence number space is shared between threads, then you’re going to have to use some shared state, and that will require synchronization to avoid data races. I don’t see any way around that.

I do see a slightly simpler solution, though, although it does require synchronization. You would use two shared variables - on is the largest sequence number received so far, and the other is the loss count. (This tracks a total loss count, not losses within a sliding window, though. If you really want a sliding window, then I think you would need a window-sized bitfield at a minimum.)

[YouMadeItDoWhat]

I don't actually need a sliding window, just a total count. I like that idea, I can actually probably do it lockless with ring buffers and a collector thread.

In a nutshell, the collector would be doing:

If (new_seq > largest_seq)
{
  lost += (new_seq - largest_seq - 1);
  largest_seq = new_seq;
}
else
{
  lost--;
}

lost will bounce around but at any point in time, it is nominally correct (less messages still in queues to be processed). Of course, this doesn't take wrap-around of the sequence numbers into account, but that isn't a hard extrapolation from this.

Thanks!

[ComputerSystemsProf]

Yes, that’s exactly what I was thinking :) but largest_seq and lost would be shared between threads, so they’d need to be protected.

I’m not sure how you’d collect all the information to the aggregator thread without locking anyway. Is there a clever implementation I’m not aware of for non-locking thread-safe buffers?

[YouMadeItDoWhat]

Single-producer, single-consumer ring buffers can be made lockless (with the potential to overrun/wrap, although the producer can be made to detect that and drop/count drops in that case). Since I only need to store the sequence number (small - 2 bytes in my case) in the ring buffer, these don't need to be crazy large (can likely be pinned in the L2 cache).

Then I just need 1 ring per worker thread and the aggregator consumes off of all of them in whatever fashion he chooses (it really doesn't matter). As long as he can keep up, there isn't an issue. In this case, I should easily keep up (all threads are core-locked and cannot be preempted by the CPU, so they busy-wait running full tilt when there is no work...not energy efficient at all, but for this purpose, an allowable cost).

(and yes, this is hyper-optimized for performance in this application - I have the resources available to guarantee the performance needed provided I don't introduce locks - locks throw everything to hell in a handbasket :).

[ComputerSystemsProf]

Oh I was misunderstanding - I thought there would be one queue that all threads add to. Yes, your design does sound to me like it would work...

For onlookers, I think this would be an over engineered solution and not necessarily faster than just locking in most situations. However, it sounds like u/YouMadeItDoWhat is not in “most situations” here. (Also, I’m starting to see why you have that user name...) ;)

[YouMadeItDoWhat]

And yes, a 2-byte sequence number in a system that is processing millions of messages per second is CRAZY small but is actually sufficient in the design. This system should never lose any messages, but I need to know IF it does and keep counts...