cidr table as partricia/radix trie

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

cidr table as partricia/radix trie

Jay Deiman
Hello all,

I was just reading the cidr_table(5) man page and I have a few questions.

First I noticed that this is a "first match" scenario based on the
ordering in the file.  Is this file (in memory) then traversed in a
linear order?

Has there ever been any discussion around implementing the cidr table as
a patricia/radix trie instead?  Perhaps implementing a new table type
that uses a "most specific match" scenario instead of "first match"?
Although, you could still retain the first match scenario by storing the
rule's line number index as part of the leaf node data and traversing
the trie to find the lowest index.  This would probably not be the
fastest method on small files, but if large files are being linearly
traversed, it would be much faster.  A separate table specification
would probably make the most sense so as not to break current setups.

I'm definitely interested in any technical reasons why a patricia/radix
trie is *not* currently implemented.  Contrary to that, would anyone
else be interested in this as a feature request?

As always, thanks for all the hard work everyone puts into Postfix.  It
is greatly appreciated.

Jay Deiman

--
Jay Deiman

\033:wq!
Reply | Threaded
Open this post in threaded view
|

Re: cidr table as partricia/radix trie

Wietse Venema
Jay Deiman:
> Hello all,
>
> I was just reading the cidr_table(5) man page and I have a few questions.
>
> First I noticed that this is a "first match" scenario based on the
> ordering in the file.  Is this file (in memory) then traversed in a
> linear order?

Just like regexps, Postfix stores CIDR networks and masks in memory,
and searches them in the exact order as specified. The strict order
is intentional, as this allows people to make exceptions (!192.168.1.1,
192.168.1.0/24).  (hash maps don't have a specific order, and there
Postfix will search for the more specific entry first).

Generally, Postfix uses the simplest possible implementation AND
the simplest possible user interface, until either is found to be
problematic. The software may be free, my time is not. I don't know
how realistic it is to expect that people will map a substantial
portion of the internet with a Postfix CIDR map.

Other options have not been considered, and everyone is welcome to
draft a design document (user interface and behavior) that argues
a better interface/implementation.

        Wietse

> Has there ever been any discussion around implementing the cidr table as
> a patricia/radix trie instead?  Perhaps implementing a new table type
> that uses a "most specific match" scenario instead of "first match"?
> Although, you could still retain the first match scenario by storing the
> rule's line number index as part of the leaf node data and traversing
> the trie to find the lowest index.  This would probably not be the
> fastest method on small files, but if large files are being linearly
> traversed, it would be much faster.  A separate table specification
> would probably make the most sense so as not to break current setups.
>
> I'm definitely interested in any technical reasons why a patricia/radix
> trie is *not* currently implemented.  Contrary to that, would anyone
> else be interested in this as a feature request?
>
> As always, thanks for all the hard work everyone puts into Postfix.  It
> is greatly appreciated.
>
> Jay Deiman
>
> --
> Jay Deiman
>
> \033:wq!
>
>