I have been working on a project for almost a year now, and recently I discovered that there was a significant bottleneck at the stage where IP addresses are generated and handed off to the rest of the system. Python has a great
netaddr package that allows users to convert addresses to/from integers, define CIRDR ranges (eg:
IPNetwork(192.168.1.0/24)), and also do tests such as
if IPAddr(192.168.1.5) in IPNetwork(192.168.1.0/24) (which would evaluate to
True). At high volume however, some performance issues started to creep in rather quickly.
The system structure I had was a single process with the sole job of keeping a shared
multiprocessing.Queue full of IP addresses. Specifically each element on the
Queue was a list of
n IP addresses. Typically this would mean the
Queue had 256 bundles of 1024 addresses at any given time, and needs to support producing these bundles a few thousand times per second. Lets look at a few cases to get a feeling for performace in simple cases:
How fast can we generate IP addresses?
The following code generates a random number between
2.4e9, and converts it to an address using the
Note: I'm running these tests on my desktop computer. Therefore these numbers should be viewed relative to each other, and will change based on the hardware this code is run on.
MAX_IP_INT = 4200000000 N=1000000 for n in range(N): IPAddress(randint(0, MAX_IP_INT))
This can pump out addresses at a rate of: 240k ips/second
Now lets see what happens when we check that the addresses aren't within a CIDR. The following code will generate a random IP in a loop, and only exit when the IP doesn't fall within any of the excluded subnets.
MAX_IP_INT = 4200000000 N=1000000 # Define a list of excluded CIDRs. single_exclude = [ IPNetwork('192.168.0.0/16')] for n in range(N): rnd = random.randint(0, MAX_IP_INT) # Loop until the new IP address is valid. while any([rnd in e for e in single_exclude]): rnd = random.randint(0, MAX_IP_INT) IPAddress(rnd)
Accomodating this constraint immediately decreases the rate to: 106k ips/second!
The following is a plot showing the how long generating 1 million IPs take, as the number of excluded ranges increase.
This plot shows that by adding even a few (random)
/24 CIDRs, the IP generation slows to a complete grind! The outgoing rate on this test was 5k ips/second, or 0.8% the rate of our first test. Sloths move faster than this. The other important thing to note, is that this continues to get worse as you continue to add excluded networks!
Now for the good stuff: How can we improve on this?
The answer is simple. Generate numbers that have no chance of being in the exluded networks!
The algorithm is not very complicated. Instead of generating a number between
4.2e9, use the list of exclusions to create a list of allowed ranges. For simple numbers here pretend our values go from 0 to 20 (instead of 4.2 billion). If our excluded range is
[5,12], the allowed lists would be
[0,4] and [13,20] (Note: this list needs to be sorted in ascending order). Then, calculate the lengths of these allowed regions, and normalize them. This would give two values,
7/11 which will be used as weights. Now we can form a new list with each element having the form of
[start, end, weights], giving:
[ [0,4,0.36], [13,20,0.67] ]. This process should be done during an initialization process, and can take a few seconds. So now, we have a list of start/end indexes, and a value that represents that range's contribution in size relative to others. This is important because if you are generating numbers at random, you should be more likely to choose a number within a large range, than you would a small one. So these weight values can be used as the probability to choose it!
To choose one of these ranges: generate a number between
1.0. Iterate through the (sorted) list of
[start, end, weights], subtracting the weight from your random number each time. Eventually your number will go negative, and when that happens - you've chosen a range to use! For example, if you had weights
[0.25, 0.1, 0.3, 0.35] and you generated the number
0.6 - 0.25 = 0.35. Okay, still above
0, so keep going.
0.35 - 0.1 = 0.25. Still above
0.25 - 0.3= -0.05 -> There it is! So the range selected would be the
[start, end] associated with the
0.3 weight. Now all that is left is to randomly pick an integer between the
end index. Here is a plot illustrating the speed to compare to earlier methods:
Using this new method the preprocessing took
2.9e-3 seconds, and the IP generation was 98k ips/second
Boom! That is all there is to it. So now, instead of generating a number, checking if it's in any one of a series of excluded ranges, and possibly repeating that check several times until an allowed value is produced: You can simply do a little preprocessing and then only even have to generate two values with a bit of simple math!
You can find the full code I used to generate this data, as well as a full ip-generation class here
Thanks for reading!
-- Jason Hopper firstname.lastname@example.org