[Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty

[Patrick Donnelly <batrick@...>]

Hi Robert Paprocki,

(Sorry I didn't get your email. So lua-l gets to be the transition medium :)

Here is a messy proof-of-concept for handling IP addresses matching a
set of CIDRs at large scale. As we talked about, it works by
constructing a tree of CIDRs as an array and matching IP addresses
against it. (Note: the array is static size and holds the entire 32bit
ip address space as a 2GB array. However, this malloc'd memory is
mostly unused and due to memory overcommit in Linux, the actual memory
of your RSS is much less.)

I was able to achieve the following numbers for insertion (which
includes significant time spent creating IP addresses via
math.random):

pdonnell@icewind ~/Downloads/LuaJIT-2.1.0-beta3/src$ ./luajit  ~/cidr-match.lua
CIDRs inserted per second (100000): 986747
IPv4 addr searched per second (100000): 838272
CIDRs inserted per second (1e+06): 2723912
IPv4 addr searched per second (1e+06): 2027817
CIDRs inserted per second (1e+07): 2589888
IPv4 addr searched per second (1e+07): 1621741

pdonnell@icewind ~/Downloads/LuaJIT-2.1.0-beta3/src$ luajit  ~/cidr-match.lua
CIDRs inserted per second (100000): 278164
IPv4 addr searched per second (100000): 154175
CIDRs inserted per second (1e+06): 336277
IPv4 addr searched per second (1e+06): 193654
CIDRs inserted per second (1e+07): 223287
IPv4 addr searched per second (1e+07): 117337

(For some reason, luajit 2.0 -- the second run above -- is much slower
than 2.1.)

Here's the memory usage with 1 million CIDRs:

$ ./luajit  ~/cidr-match.lua
VmPeak:  2109684 kB
VmSize:  2109684 kB
VmLck:         0 kB
VmPin:         0 kB
VmHWM:    683128 kB
VmRSS:    683128 kB
VmData:  2097480 kB
VmStk:       132 kB
VmExe:       480 kB
VmLib:      3364 kB
VmPTE:      1384 kB
VmPMD:        28 kB
VmSwap:        0 kB

Note the important bit there VmRSS which indicates it's actually using
680MB for 1 million CIDRs... so not quite that small :). Memory use
for normal use-cases may be very different.

The code is rough and doesn't handle network byte order correctly but
that should be easy enough to fix. Exercise for the reader and all
that.

Thanks for the fun programming challenge and thanks to Kong for
hosting the Lua workshop!

-- 
Patrick Donnelly

Attachment: cidr-match.lua
Description: Binary data