[erlang-questions] IP search optimization
Fri Nov 20 18:01:50 CET 2015
> Sent: Thursday, November 19, 2015 at 9:05 AM
> From: "Alexandre Snarskii" <snar@REDACTED>
> To: "Sid Muller" <sid5@REDACTED>
> Cc: erlang-questions <erlang-questions@REDACTED>
> Subject: Re: [erlang-questions] IP search optimization
> > And then I want to check if an IP (18.104.22.168) belongs to any
> > network address in the ets table (the table can get pretty large).
> Looks more like a task for radix trees...
Hmm, good point although with ets if my owner process gets killed I inherit the ets and no data is lost. Not sure how that cold be done with a radix tree.
> The best you can achieve with ets is:
> on insert: make sure that inserted networks are normalized (do not have
> any bits set after prefix length).
> on lookup:
> 1. start with masklen of 32
> 2. normalize address to current masklen
> 3. lookup for address/masklen record, return if found
> 4. if current masklen is zero - return 'not_found'
> 5. decrease masklen and repeat from step two.
There are a few faster methods:
1. Have a pre-scanned list of /CIDR [21, 20...], there are usually about 10. But this still traverses the table 10 times in worst case.
2. Traverse the table with ets:lookup(ets:next(), this has the advantage over #1 as it's much faster in most cases.
3. ets:select(MatchSpec), this is probably the fastest solution because it should traverse the table only once. But right now I'm having a bit of a problem with my select statement... see other email [bitstring select]
More information about the erlang-questions