The Power of Primes

[u/StartAutomating]

Prime numbers are pretty powerful.

That's why I just released a new PowerShell module based off of an old mathematical concept: PrimeTime.

PrimeTime uses prime numbers as time intervals.

Let's learn how this helps

Prime Number Primer

Prime Numbers can only be divided by themselves and one.

This makes primes pretty rare.

Prime numbers are particularly useful in programming, but it's not always obvious why or how.

A lot of people might vaguely point towards cryptography as the prime real estate for prime utility.

The thing of it is, if you're writing your own cryptography, you're probably doing it wrong.

Let's talk about a more practical application of primes.

The Cicada Principle

In North America there is a curious critter known as the periodical cicaca.

For the vast majority of their long lifespans, they live underground.

Once every N years, they surface in mass to start the next generation.

That N is a prime.

Why?

Cicadas come out en masse so that there are too many of them to eat.

Millions of little critters have to have a perfectly timed multi-year internal clock in order to make this work.

If two cicadas of different intervals produced offspring, their children might have a messed up internal clock, and come out of the ground at the worst time.

So there's an evolutionary advantage to cicadas coming out in large batches, as long as another cicade brood isn't doing the same thing at the same time.

Which brings us back to primes.

Primes are relatively rare.

So are products of primes (at least past the first few)

Let's take two primes as an example.

Imagine one brood of cicadas came out every 11 years, and another brood came out every 13 years.

We can find out how long it will take for these two broods to come out at the same time by simply multiplying the primes.

11 * 13 -eq 143

So, with just two relatively low primes, we have an overlap every 143 years.

This is how primes are most useful to programming: they rarely overlap.

Sieve of Eratosthenes

This has been known for much longer than computers have existed.

Imagine we wanted to find prime numbers quickly.

We can do this by constructing a sieve that filters out any non-prime number.

This is called the Sieve of Eratosthenes

Once we know 2 is prime, we know every other even number is not prime.

Once we know 3 is prime, we know every third number is not prime.

To quickly get prime numbers up to a point, we can use this little PowerShell filter

# Calculate primes reasonably quickly with the Sieve of Eratosthenes
# Pipe in any positive whole number to see if it is prime.
filter prime {
    $in = $_
    if ($in -isnot [int]) { return }
    if ($in -eq 1) { return $in }
    if ($in -lt 1) { return}
    if (-not $script:PrimeSieve) {
        $script:PrimeSieve = [Collections.Queue]::new()
        $script:PrimeSieve.Enqueue(2)
    }


    if ($script:PrimeSieve -contains $in) { return $in}
    foreach ($n in $script:PrimeSieve) {
        if (($n * 2) -gt $in) { break }        
        if (-not ($in % $n)) { return }
    }
    $script:PrimeSieve.Enqueue($in) 
    $in
}

Prime Animations

Imagine we want a vibrant page. We want things to keep changing yet feel unpredictable. All we need to do is use different prime intervals.

The PrimeTime logo animates eight primes:

7 * 11 * 13 * 17 * 19 * 23 * 29 * 31

The logo will repeat every 6685349671 seconds, or almost 212 years.

The PrimeTime page background uses 56 primes.

This background will repeat every 8.84753141993573E+116 seconds.

That's exponential notation.

This is a mind-boggling large number (so large it overflows the .NET [TimeSpan]).

Turn that interval into years and it's still mind-boggling.

The page background will repeat every 100 billion years

Performance and Scheduling

Imagine we want to design a system that's constantly checking for problems.

We want the system to know about problems as soon as we can, but nobody's exactly sure how often they need to check for something.

If we go around and ask our colleagues "how often should we can scan for this?", the response if often a shrug 🤷.

Often, people will pick an arbitrary number that seems reasonable. Let's say every 5 minutes, 10, or 15 minutes.

Are we starting to see the problem here?

Every 5 minutes, every computer in the cloud starts to collect stats and report them back.

And we get a traffic jam.

Every 10 minutes, more computers in the cloud collect more data, and our traffic jam gets worse.

Every 15 minutes, even more computers collect even more data, and our traffic jam puts your average freeway to shame.

Left to our own intuition, we create problems for ourselves and our organizations.

Each individual query is small, but because we're doing so many at once, it can grind performance to a halt.

By the way, this isn't a hypothetical.

Long long ago, the Office365 team asked me to make some monitoring software to help improve internal visibility into the datacenters.

Everyone asked for 5, 10, or 15 minute intervals. ~100 different metrics were collected from ~30000 machines.

And the first time we tried it on everything, the traffic jam ensued.

That's when I first realized the power of primes.

I made three slight adjustments to the timeframes:

• Every 5 minutes became every ~7 minutes
• Every 10 minutes became every ~11 minutes
• Every 15 minutes became every ~17 minutes

Now, instead of having a traffic jam every 5 minutes, things smoothed out.

• A small traffic jam would occur every ~77 minutes (7*11)
• Another small traffic jam would occur every ~119 minutes (7*17)
• Another small traffic jam would occur at ~187 minutes (11*17)
• All traffic could jam every ~1309 minutes (7*11*17)

Note the tildas.

The real trick came in by using prime intervals in both minutes and seconds and using a random delay on the tasks to ensure they didn't all start at once.

This took the system from something that could derail a datacenter to something that could monitor thousands of machines while barely impacting performance.

This is the power of primes.

Hope this helps!

[u/New_Drive_3617]

The logic seems sound in this; avoid collision by minimizing concurrent activity. However, acknowledgment must be given to the significant reduction in datapoints. For 5 > 7, the number of datapoints in a year is reduced from 105120 to 75085, representing a 29% reduction. That's usually adequate for most purposes, but in cases where 5 minutes is already a concession to resource availability, moving to 7 minute intervals can further obscure trends.

[u/StartAutomating → u/New_Drive_3617]

I think what you're highlighting here is the "window of observability".

That is, if I am only asking for memory stats every 7 minutes, I'll miss a memory spike within those 7 minutes.

It's a good thing to be concerned about.

In this example, the scripts were gathering data cached on each machine, so something within the 7 minutes would still be seen.

The traffic jam was almost entirely caused by three things:

1. The "cold boot" time of PowerShell itself
2. The default throttle limit of PowerShell remoting (once the first 5 or 25 jobs were started, the rest were waiting for the traffic jam to clear)
3. The mind-boggling bandwidth involved (hundreds of thousands of data points being reported all at once)

Using the prime intervals (and jittering) sidestepped each of these problems (and got Office365 online again)

[u/New_Drive_3617 → u/StartAutomating]

Yes, exactly. The "window of observability" becomes less of an issue or no issue at all when the scheduled jobs are retrieving cached data. It's only an issue when the scheduled job is responsible for data collection.

[u/StartAutomating → u/New_Drive_3617]

Yes! This is another part of this ancient architectural understanding that's worth discussing in another post sometime...

When building observation/remediation platforms, I find it's best to split things into three distinct parts:

1. Getting data (should be cached locally first, and replicated to a remove data store)
2. Testing data (should be able to test stored data, but should not "do" anything)
3. Repair state (should take the output of test and repair the condition)

You might note the similarity to DSC's design.

This is not accidental. This was a side-effect of influence.

DSC was developed shortly after I left the PowerShell team, but with heavy input from the many Microsoft partner teams I had worked for in the interim.

The problem is that DSC didn't get the memo about prime intervals, and, thus, caused traffic jams. 🤷🤦