Optimizing OPA performance: From arrays to objects

Note: This post focuses on one aspect of performance tuning Rego policies and datasets evaluated by OPA—arrays vs. objects. The Rego Style Guide and Regal Rego linter are very helpful resources for learning Rego best practices and avoiding code smells in Rego policies. There is also the OPA performance tuning documentation.

In 2018, I started using open policy agent (OPA) as a solution for controlling and preventing unwanted behaviors in our Kubernetes Clusters. OPA, along with Kubernetes Dynamic Admission Control, provided a means to build preventive controls. Since then, I have worked with several PaC solutions. I have always stayed close to the OPA tool set because of how well it supports multiple use cases.

OPA is domain agnostic and can be used with virtually any use case, as long as you supply the correct data and policies. To that end, OPA use cases have expanded throughout several technical disciplines, such as cloud-native computing and software supply chain management.

OPA enables us to unify PaC solutions across multiple use cases and systems, using the same languages and tools. However, there is always room for improvement and performance engineering policies and the execution thereof. In addition, optimizing data that policies evaluate and mutate should be part of our focus when we deliver OPA-based solutions.

Recently I was asked to help with OPA performance issues. I made several recommendations, but I overlooked one simple and glaring issue: the poor performing policy was processing a large data set using nested-arrays, instead of the best practice of using keyed-objects. Later, something was bothering me about my interaction and I realized that while I gave decent architectural level advice, I completely missed the best engineering advice. Rego policies and data should be optimized just like other algorithms and relative data, and part of that optimization is using the correct data structures.

Rego (pronounced RAY-GO) is OPA’s domain-agnostic query language that makes assertions on data stored in and submitted to OPA. Domain-agnostic means that Rego is wide open; it wasn’t written for a specific domain or use case. In fact, OPA doesn’t know anything about your use case until you give it policies and data needed to evaluate required decisions.

Rego works on JSON. While you can send YAML to OPA, it will be parsed into JSON before it’s evaluated by Rego. And as it turns out, Rego executes faster through JSON data when it accesses data via objects and dot-notation and slower when array searching and iteration are done. This execution difference is exacerbated with large datasets, nested arrays or lists, and complex policies.

The Rego behavior is not unique. When we write algorithms, we strive for as close to constant time complexity, denoted by O(1) in Big O notation, as we can get. In other words, the execution time of an algorithm should remain constant regardless of the size of the input data. Generally, accessing data via object keys, map keys or array indexes helps us stay close to O(1). Iterating through a collection is usually slower and is compounded by the size of the collection and any comparisons we perform on the elements.

When I looked more closely at the data and policies with which I was asked to help, I realized that the policy authors were not following one of the most prominent rules of policy performance from the OPA documentation: use objects over arrays. They were performing multiple (nested) array operations over a large dataset. I missed this, and it prompted me to revisit Rego performance tuning.

What follows is an example of a data-intensive use case that shows how Rego policy performance is substantially improved through data structure and policy optimizations, switching from array traversal operations to object dot-notation.

The following use case uses OPA Rego policies to build risk profiles from software bills of material (SBOM) data, in CycloneDX format, that contains vulnerability information. The SBOMs are created using Anchore Grype.

$ grype <container_id> -o cyclonedx-json > sbom-with-vulns.json

A snippet of the output SBOM with included vulnerabilities is seen in the following listing:

The risk profiles are created using Exploit Prediction Scoring System (EPSS) data. Using EPSS enriches risk data with exploitability predictions, formatted in percentages. It extends the risk-based evaluation of vulnerabilities beyond the Common Vulnerability Scoring System (CVSS) ratings from the National Vulnerability Database.

For this use case, I downloaded the EPSS CSV file and then used ANTLR to generate a Java-based parser to parse the CSV data into JSON data. I built my own parser because I wanted more control over the parsing output, and I am familiar with ANTLR. A snippet of the parsed data file is seen in the following listing:

The generated EPSS JSON uses an array of rows that contain field objects. It’s one of the simplest forms of creating JSON from a CSV object and is modeled after the rows and columns in a CSV file. However, the file is 1.9 million lines long and 46MB, and it is not optimized for processing.

The following Rego policy is used to interleave the SBOM CVE data with the EPSS data and logically create a risk-weighting system that allows organizations to assign risk based on the weight of the CVSS and the EPSS data, using weighted risk-level functions.

In the previous Rego listing, the profiles_epss rule uses a Rego comprehension to create a collection of profile objects. The rule starts by iterating through the array of vulnerabilities in the SBOM. Then the rule calls the build_epss function for each CVE, which also loops through a massive array of EPSS data looking for a match between the supplied CVE ID and CVE field in the selected array element. This is not the best way to handle this data processing scenario with Rego, and we can make data-driven changes to improve processing.

The OPA CLI eval command can be used to evaluate data with Rego policies, and this command has a handy profiler that shows where the policy execution bottlenecks occur. OPA eval is similar to running an OPA server, but it is a one-shot execution, which is a good fit for CLI use cases like automated processes. And I use OPA eval when I am performance-tuning Rego policies.

The OPA eval command also supports collecting metrics about the different steps in the query execution cycle. This helps pinpoint where potential issues are. Finally, you can use the shell time command to get an idea of the execution time of the command. The following shell command runs OPA eval and specifies the --profile and --metrics arguments:

The following listing contains the JSON output from the preceding OPA eval command. The output first indicates 124 profiles were generated, using CVSS and EPSS data, and then lists the first profile in the list with a computed org-specific risk level of high.

Executing the OPA eval command to process the SBOM and EPSS data into risk profiles took approximately 48 seconds, as indicated by the information returned from the shell time command.

47.71s user 0.30s system 180% cpu 26.639 total

If we look at the metrics gathered by the OPA eval command, we can see that it took approximately 26 seconds to evaluate the Rego query.

If we look at the performance profile data returned, including the top two highest-processing-time locations, we can see that lines 30 and 31 of the Rego policy took the longest to run.

Lines 30 and 31 of the Rego policy are listed below. They are where the processing of the 1.9 million-line JSON EPSS data takes place, as you can see by traversing each item in the array and doing a comparison.

We know how long the policy execution took as well as where the potential bottlenecks are, and nested array processing with element comparisons is clearly an issue.

As I said earlier, accessing JSON data via Rego using object dot-notation is faster than traversing arrays. So I first transformed the EPSS JSON data using a jq command seen in the following listing:

$ jq '.rows | map({(.fields.cve): (.fields | del(.cve))}) | add' data.json

The preceding command transformed the EPSS data JSON into the following object-oriented format. This also reduced the file down to 1 million lines and 20MB—a reduction of 900K lines and 26MB.

Next, I modified the Rego policy to take advantage of the new dot-notation used to get the EPSS data, keyed by CVE IDs. I also removed the build_epss function.

Then I reran the risk profile generator command with the optimized data and policy.

0.99s user 0.06s system 160% cpu 0.654 total

As you can see, the new execution time is 0.99 seconds, down from approximately 48 seconds. This comes out to a 98% decrease, approximately. The metrics also indicated a drastic decrease in processing time. The query evaluation time dropped from approximately 26 seconds to 5 milliseconds, a 99% decrease.

Finally, with the nested array processing eliminated, the profiling output no longer indicates huge processing constraints.

The highest code line execution time dropped from more than 12 seconds down to just over 1 millisecond, which is a more than 99% improvement.

If we chart the improvements, we can easily see where we improved most. Overall, loading the OPA bundle that contained the large EPSS dataset and the Rego policy only improved by 34%, while data parsing only improved by 35%. The biggest gains were in the Shell Execution, Policy Eval and Longest Expression times. Here, we saw duration improvements of 98%, 99% and 99%, respectively.

There are potentially other performance tweaks I could make to the Rego policy to improve the performance of the evaluation. However, a 98%-99% improvement is a great start, and it was accomplished by using algorithmic constant time complexity improvements—converting a very large data array to a keyed object—allowing object dot-notation to be used instead of array traversal and subsequent comparisons.

For those of you out there who are using OPA, especially with large datasets, I strongly encourage you to review the OPA performance-tuning documentation and remember your algorithm tuning techniques.