Quadratic runtime complexity for adding constraint templates

[briantkennedy]

While testing config validator, I found that adding all 68 constraint templates from the policy-library takes about 15 seconds total. I added some timers and found that the bulk of this is in adding Constraint Templates which appears to have a runtime complexity of O(n^2). This isn't a huge deal for large analysis jobs, but there's a few places where I could see this becoming an issue:

• it slows down TDD so it would be nice to fix this for people developing new CT/C (Better UX).
• At 68 constraints, the incremental load time is about 350ms. If gatekeeper gets loaded with a lot of templates, I'm not sure what the implications of taking this long will be, but it's probably something to be aware of.
• for realtime FCV, we plan to put FCV into a knative endpoint, so this would mean cold-starts are really costly

[maxsmythe]

@tsandall

The increasing incremental cost is likely due to a larger bulk of Rego needing to be recompiled. Given that constraint templates are meant to be non-interacting, is there any way to eliminate the incremental cost by preserving the work of previous compiles? Maybe caching the artifacts somewhere to improve the cold start as well?

[maxsmythe]

An option for non-referential templates would be to have a separate interpreter per-template.

[tsandall]

@maxsmythe improving the compiler to support incremental updates is possible but would require some work. In short, some of the stages implement checks and rewriting or build data structures that are local to the module/rules in the module whereas others do these things globally (recursion check is one example). The first step would be to categorize the stages in the compiler so we know which ones require global information or perform global updates and which do not. For the global changes that affect data structures, we probably have to update the data structures to support add/remove operations (if they don't already.) In the short term, we should probably benchmark the compile operation and see where the time is spent. If you run opa eval -d x.rego 'data' --instrument you'll get back timers for each of the stages.

[maxsmythe]

Any way to get that debug information from the OPA API?

[tsandall]

Yes, the rego.Instrument option enables it: https://github.com/open-policy-agent/opa/blob/master/rego/rego.go#L785

[tsandall]

I've filed an issue against OPA to improve support for incremental load scenarios. In the meantime, it would be good if the constraint framework could support a bulk load API (e.g., AddTemplates in addition to AddTemplate on the client).

EDIT: One other thing to mention. When I updated to use OPA master with the new parser implementation (which is in v0.19.0-rc1), the load time for the first template went from ~45ms to ~10ms.

[willbeason]

Resolved with #202