Cut the per-check cost of running a policy

Michael Angelo Riverarequested to merge
michaelangeloio/cut-per-check-cost into main

Description

This MR stacks on !85 (merged). It makes one permission check cheaper after !85 (merged) lands.

How a check runs

A short walk through policy.allowed?(:read_code):

  1. The policy asks its class for the rules of :read_code. This is configuration_for.
  2. It turns each rule into a Step and gives the steps to a Runner.
  3. The runner picks the cheapest step, runs it, and repeats until it has an answer.
  4. Each step reads conditions. Each condition result is cached under a string key, for example /dp/condition/ProjectPolicy/public_project/Project:7.

!85 (merged) made the class-level maps cheap. Steps 1, 3 and 4 still did work that repeats for every subject. This MR removes that work in three commits.

1. Cache the rules of each ability

Before, every call joined the ability's rules with the global prevent_all rules:

def configuration_for(ability)
  applicable_globals = global_actions.filter_map do |(action, rule, exceptions)|
    next if exceptions&.include?(ability)

    [action, rule]
  end

  ability_map.actions(ability) + applicable_globals
end

Now the result is cached next to the other class maps:

def configuration_for(ability)
  return build_configuration_for(ability) unless ability_map.key?(ability)

  configurations = memoized_definition(:configurations) { {} }
  configurations[ability] ||= build_configuration_for(ability)
end
  • The cache uses the same generation counter as !85 (merged), so a new rule clears it.
  • Only abilities that some rule declares go in the cache. An ability name from user input cannot grow it.
  • The result is a frozen array.

2. Build cache keys once per policy

Every condition built its key from the user key and the subject key. A policy that reads 20 conditions built the strings User:42 and Project:7 20 times. Now the policy builds them once:

def user_cache_key
  @user_cache_key ||= Cache.user_key(@user)
end

Condition#key was also rebuilt on every read. Now the condition freezes it when you declare it:

@key = "#{@context_key}/#{@name}".freeze

3. Run steps without rebuilding sets

Before, each run built three sets and a new pair on every round:

remaining_steps = Set.new(@steps)
remaining_enablers, remaining_preventers = remaining_steps.partition(&:enable?).map { |s| Set.new(s) }
next_step, lowest_score = next_step_and_score(remaining_steps)
[remaining_steps, remaining_enablers, remaining_preventers].each { |set| set.delete(next_step) }

Now it works on one array and a counter:

remaining = @steps.uniq
enablers_left = remaining.count(&:enable?)
lowest_index, lowest_score = cheapest_step(remaining)
step = remaining.delete_at(lowest_index)
enablers_left -= 1 if step.enable?
  • The order of steps, the scores and the early exits are the same as before.
  • uniq removes a step object that appears twice. The old set did the same.

The runner state records the cache key of every condition it reads. It keeps them as keys of a Hash, so a condition that checks can? over many subjects still costs one lookup per key. Cache keys are frozen, so the Hash does not copy them. benchmarks/fan_out.rb measures that case.

Numbers

We ran GitLab's Orbit redaction batch: 1000 projects, ability read_code, one user. The table shows thread CPU and allocated memory per project.

Gem CPU per project Memory per project
2.1.0 3.0 ms 2514 KB
!85 (merged) 0.60 ms 67 KB
!85 (merged) and this MR 0.47 ms 53 KB
  • A second run on a busy host gave 0.69 ms and 66 KB for !85 (merged), and 0.58 ms and 55 KB for this MR.
  • The rest of the batch cost is record loading and preloaders in GitLab. The gem is no longer the main cost.

Correctness

  • We compared 50,778 decisions: 3 users, 7 subject types, every ability of each policy class. All of them match !85 (merged).
  • The gem suite passes on MRI 3.0 to 3.4 and on JRuby. Rubocop is clean.
  • rspec:truffleruby and brakeman-sast fail in the same way on the !85 (merged) pipeline. Both are allowed to fail.

Public changes

  • configuration_for returns a frozen, shared array. Code that appends to it now raises FrozenError.
  • Runner::State#called_conditions returns a new Set on each call.
  • Policies have two new public methods: user_cache_key and subject_cache_key.

Related Issues

See: gitlab-org/gitlab#630828

Suggested version bump

  • Major (backwards incompatible changes)
  • Minor (backwards compatible changes)
  • Patch (API compatible changes)

Checklist

  • Tests have been added or updated to cover any changes in behavior
  • This does not change the API to consume this library, or a suggested version bump has been provided
  • Add git trailer Changelog: <category>
  • No new runtime dependencies have been introduced

References

Edited by Michael Angelo Rivera

Merge request reports