[erlang-questions] IP search optimization

[Michael Wright]

I think routers generally use radix trees, and it's certainly important for
them to be able to do lookups quickly. Some also have specialised hardware
to assist, but I guess you can't have everything!

Regarding your desire to use an ETS table for the inheritance, I obviously
don't know your exact use case, but I personally feel it's more important
to use the correct/optimal storage solution. My reasoning is:

  1. Obviously it will perform best.
  2. If then you crash, well, fail early is the Erlang way, and hopefully
this would lead to a more rapid development of a relatively stable solution.
  3. If there is a flaw in your persistent data that caused the crash, you
won't persist the flaw and crash again.
  4. If it's worth it, you could back up your prefixes in a separate
process (or ETS table) anyway.

If you backed up your prefixes (point 4) you can reconstruct your radix
tree from the backup in the event of a failure. Not perhaps as quick as not
having to... but probably not really very expensive unless you really crash
very often. Typically routers would do this anyway because they learn
routes from various sources and maintain databases for each of those
sources and/or each protocol, and then the actual routing table used to
make routing decisions is essentially separate, and can be optimised
separately. Your use case might be quite different but you could still
adopt the idea artificially.

Another thing to consider is that you could implement a 'route cache' on
top of whatever solution you choose (every time you have to search your
radix/ETS stuff the result in a cache, the cache being a map of IP to
prefix). This will make most of your lookup speeds very quick and largely
constant because they'll be a hash lookup, ASSUMING your use case is such
that you get a good cache hit rate. There is additional work to be done of
course, you have to garbage collect your cache, you have to invalidate all
or some of it when you update your prefix list (unless the lag is
acceptable in which case just wait for garbage collection), and you must
give very careful consideration to the possibility of dos attacks causing
you to build huge caches. This obviously depends on the details of your use
case, as does the likelihood of a good cache hit rate.

M.

On Fri, Nov 20, 2015 at 5:01 PM, Sid Muller <sid5@REDACTED> wrote:

> > 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 (31.24.171.44) 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]
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151125/f7e50698/attachment.htm>