2

I'm processing a stream of incoming records, for clarity assume they're numbered consecutively 1,2,3....etc.

Most of the time the records are arriving slowly enough for me to process every single record. During busy periods they are arriving too fast to all be processed so I need to drop/ignore a proportion of them.

I've been using a simple bit of (pseudo) code like this.....

if ( n mod x == 0 )
{
  process = true;
}

(where 'n' is the record number). This is pretty simple, if 'x' is 2 and the record is even numbered it gets processed, if it's odd numbered it get's ignored. 50% of records are processed and 50% ignored. If I replace 'x' with 10 then one record in 10 (i.e. 10%) will get processed and 90% will be ignored. Replacing 'x' with 20 will select 5% of records.

This works ok, but only allows the selection of a limited number of percentages..

x=2  -> 50%
x=3  -> 33%
x=4  -> 25%
x=5  -> 20%

How can I re-write my code to select a given percentage of incoming records - say 85%?

although I'm doing this with a powershell script, I'm looking for a language neutral solution.

UPDATE - due to the nature of the data, I'd prefer not to drop the records randomly because this could (in theory) drop a long sequence of consecutive records. I'd prefer to drop/process at a regular rate i.e. process 3 records, drop 1 and repeat. Dropping (say) 20 records in a row could make me miss something important.

  • At a 75% hit rate, your chance of dropping 20 records in a row is infinitesimal. – Philip Kendall May 13 '18 at 18:11
5

The easy way to handle this is something like if (rand() < targetFraction) process = true. Formally, this doesn't guarantee you 85% or whatever, but will asymptotically approach 85% as the number of records increases.

Note that I think you may be solving the wrong problem here - if you know you can handle at maximum N records per second, write code that drops anything above that rate, rather than hard coding a fraction to drop.

  • in principle, both approaches could be combined – adjusting the percentage of sampled records based on the observed rate of incoming records (p = r/max(r, R) where r is the desired sample rate, and R the observed rate). But that's probably overkill. – amon May 13 '18 at 13:21
  • you called it. If the OP cant process 100% what makes them think they can process 85%? – Ewan May 13 '18 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.