[clug] access control list search algorithms

Daniel Pittman daniel at rimspace.net
Thu Apr 2 06:57:17 GMT 2009


jm <jeffm at ghostgun.com> writes:
> jm wrote:
>
>> Does anyone know of any algorithms for speeding up searching of access
>> control lists? Is there anything more efficient than a sequential search?
>
> I should elaborate. I'm mucking about with email trying to develop a
> progrom to give finer control over smtp delivery.

Are you sure you want to do that, with all the workload it implies,
instead of using something like Postfix or Exim?

> My ACL is made up of senders and recipients with wildcards thrown in
> for good measure. For example,
>
> index        sender                           recipient                action
> 1              fred at example.org         '*'                             allow
> 2              '*'                                  joe at example.org     deny
> 3             admin at example.org    '*'                               allow

Is this just accept or reject delivery?  Heh.

In answer to your original question, sure there are more efficient ways.
Use a better search algorithm, structure the tests so you can
efficiently locate the applicable rules.  A trie or tree structure might
work, if the memory locality issues don't kill you.

That said, how many records are you talking here?  Are you sure that a
DBMS like sqlite isn't going to do a better job of this, given the
effort that has already been put in?


Also, how many rows are you talking?  Unless it is thousands, and
probably tens of thousands, I would further ask why you are wasting time
worrying about performance there when network and disk delays are going
to absolutely drown the time spent on searching the list with the least
efficient algorithms.

Regards,
        Daniel


More information about the linux mailing list