Investigate performance improvement for CIDR match against long prefix array

[nischalsheth]

Expected/Desired Behavior

Logarithmic increase in time w.r.t. length of prefix array when performing longest prefix match (LPM) of an IPv4 address against a list of arbitrary IPv4 prefixes.

Actual Behavior

Linear increase in time.

Steps to Reproduce the Problem

1. Define a prefix array as prefixes := ["10.1.1.0/24", "10.1.2.0/24", "10.1.3.0/24", ...]
2. Use something like net.cidr_contains(prefixes[_], input.address) using an address that matches the last prefix in above array
3. Observe linear increase in time w.r.t. length of prefixes

Additional Info

https://openpolicyagent.slack.com/archives/C1H19LW4F/p1569731663252900

[tsandall]

@nischalsheth thanks for filing this.

If the prefixes are known at load time and the policy was partially evaluated we could unroll the net.cidr_contains(prefixes[_], input.address) expression into a set of expressions like:

# query 1
net.cidr_contains("10.1.1.0/24", input.address)
...other statements...

# query 2
net.cidr_contains("10.1.2.0/24", input.address)
...other statements...

# query 3
net.cidr_contains("10.1.3.0/24", input.address)
...other statements...

# etc.

At this point the rule indexer could build a trie out of the CIDRs and support traversal/lookup for the contains check. We do something similar for equality and glob.match expressions though those are a bit different because the index traversal just involves a simple lookup at each node in the index (whereas for this we would have to traverse the trie of CIDRs.)

Another option would be to add a different built-in that accepts a set of prefixes as input, e.g., net.cidr_contains_any(prefixes, input.address). If we had this built-in function and support for caching built-in state across queries we could implement this entirely inside the evaluator. We've begun thinking about caching built-in state across queries in the context of http.send (#1753).

[kmcquade]

We could really use this as well.

[nischalsheth]

@tsandall Thanks for sharing your thoughts. In the second option, would the trie get built when the first query is evaluated?

[tsandall]

@nischalsheth that's what I had in mind. It might be necessary to provide a hint to the built-in to identify the index (in case cidr_contains_any was called with different sets of prefixes). It could be beneficial to build the index offline but just caching it as part of eval is probably the simplest in terms of implementation and API (IMO).

[nischalsheth]

@tsandall

Can you consider the gist of the suggestion below and share your thoughts?

Caveat - I am not a language designer.

Would it be possible to add a new flavor of map objects which have a "collection type" encoded using a special key? The remaining (key, value) pairs in the map would be type-dependent. Such map objects would be aware of the type of collection and hence can maintain/update additional state to perform faster matches lookup/match using built-in functions that accept pre-defined object types.

In case of the prefix match problem, a map object would have "collection_type" set to "ip_prefixes" or somesuch and would additionally contain a "prefix_list" key whose value would be a set of actual prefix strings. The back end would build/update a trie based on the prefix list.

Each "collection type" would need it's own back-end support and set of built-ins.

[tsandall]

The types in Rego are not extensible today and we don't have any kind of macro system that would you introduce your own types. Adding a new kind of type is a fair amount of work because it means updating everything (i.e., parse, compile, eval, static analysis, etc.)

That said, the object implementation is behind an interface, so in theory, if you constructed the these special objects programmatically it could work.

Essentially you'd have to construct the AST yourself and merge w/ any parsed ASTs before compiling and evaluating. Alternatively, if we added hooks to override object construction when values are read out of storage, you could do it that way (e.g., when a value is read from the in-memory store at path /a/b/c use the special object constructor.)

[nischalsheth]

Thanks for explaining. IMO, the pragmatic solution is to go with the second option you suggested i.e. add a new built-in and cache state across queries.

[skjindal93]

Is the enhancement planned to be added in OPA in near future?

[tsandall]

@skjindal93 no, we don't have any near-term plans to implement this optimization. If there are any folks out there who would be interested in implementing it, feel free to post here. We now have support for inter-query caching in builtins so the alternative I mentioned above would not be too difficult to implement.

[stale]

This issue has been automatically marked as inactive because it has not had any activity in the last 30 days.