diff options
author | GitLab Bot <gitlab-bot@gitlab.com> | 2021-03-20 00:08:58 +0300 |
---|---|---|
committer | GitLab Bot <gitlab-bot@gitlab.com> | 2021-03-20 00:08:58 +0300 |
commit | 90a27483f1a8f6f3069f19e23c3ce4c57821b7f3 (patch) | |
tree | 9a2ca8255fcf5f6c59f4d17e6990d2101c95187b /app/models | |
parent | 7aa96ff172a36b79d763fcc6643d7ea95ce293c0 (diff) |
Add latest changes from gitlab-org/gitlab@master
Diffstat (limited to 'app/models')
-rw-r--r-- | app/models/namespace.rb | 1 | ||||
-rw-r--r-- | app/models/namespace/traversal_hierarchy.rb | 26 | ||||
-rw-r--r-- | app/models/namespaces/traversal/linear.rb | 63 | ||||
-rw-r--r-- | app/models/namespaces/traversal/recursive.rb | 10 |
4 files changed, 91 insertions, 9 deletions
diff --git a/app/models/namespace.rb b/app/models/namespace.rb index 3f7ccdb977e..6f6c8b387a1 100644 --- a/app/models/namespace.rb +++ b/app/models/namespace.rb @@ -13,6 +13,7 @@ class Namespace < ApplicationRecord include Gitlab::Utils::StrongMemoize include IgnorableColumns include Namespaces::Traversal::Recursive + include Namespaces::Traversal::Linear # Prevent users from creating unreasonably deep level of nesting. # The number 20 was taken based on maximum nesting level of diff --git a/app/models/namespace/traversal_hierarchy.rb b/app/models/namespace/traversal_hierarchy.rb index cfb6cfdde74..28cf55f7486 100644 --- a/app/models/namespace/traversal_hierarchy.rb +++ b/app/models/namespace/traversal_hierarchy.rb @@ -34,17 +34,20 @@ class Namespace sql = """ UPDATE namespaces SET traversal_ids = cte.traversal_ids - FROM (#{recursive_traversal_ids}) as cte + FROM (#{recursive_traversal_ids(lock: true)}) as cte WHERE namespaces.id = cte.id AND namespaces.traversal_ids <> cte.traversal_ids """ Namespace.connection.exec_query(sql) + rescue ActiveRecord::Deadlocked + db_deadlock_counter.increment(source: 'Namespace#sync_traversal_ids!') + raise end # Identify all incorrect traversal_ids in the current namespace hierarchy. - def incorrect_traversal_ids + def incorrect_traversal_ids(lock: false) Namespace - .joins("INNER JOIN (#{recursive_traversal_ids}) as cte ON namespaces.id = cte.id") + .joins("INNER JOIN (#{recursive_traversal_ids(lock: lock)}) as cte ON namespaces.id = cte.id") .where('namespaces.traversal_ids <> cte.traversal_ids') end @@ -55,10 +58,13 @@ class Namespace # # Note that the traversal_ids represent a calculated traversal path for the # namespace and not the value stored within the traversal_ids attribute. - def recursive_traversal_ids + # + # Optionally locked with FOR UPDATE to ensure isolation between concurrent + # updates of the heirarchy. + def recursive_traversal_ids(lock: false) root_id = Integer(@root.id) - """ + sql = <<~SQL WITH RECURSIVE cte(id, traversal_ids, cycle) AS ( VALUES(#{root_id}, ARRAY[#{root_id}], false) UNION ALL @@ -67,7 +73,11 @@ class Namespace WHERE n.parent_id = cte.id AND NOT cycle ) SELECT id, traversal_ids FROM cte - """ + SQL + + sql += ' FOR UPDATE' if lock + + sql end # This is essentially Namespace#root_ancestor which will soon be rewritten @@ -80,5 +90,9 @@ class Namespace .reorder(nil) .find_by(parent_id: nil) end + + def db_deadlock_counter + Gitlab::Metrics.counter(:db_deadlock, 'Counts the times we have deadlocked in the database') + end end end diff --git a/app/models/namespaces/traversal/linear.rb b/app/models/namespaces/traversal/linear.rb new file mode 100644 index 00000000000..8c042e5409d --- /dev/null +++ b/app/models/namespaces/traversal/linear.rb @@ -0,0 +1,63 @@ +# frozen_string_literal: true +# +# Query a recursively defined namespace hierarchy using linear methods through +# the traversal_ids attribute. +# +# Namespace is a nested hierarchy of one parent to many children. A search +# using only the parent-child relationships is a slow operation. This process +# was previously optimized using Postgresql recursive common table expressions +# (CTE) with acceptable performance. However, it lead to slower than possible +# performance, and resulted in complicated queries that were difficult to make +# performant. +# +# Instead of searching the hierarchy recursively, we store a `traversal_ids` +# attribute on each node. The `traversal_ids` is an ordered array of Namespace +# IDs that define the traversal path from the root Namespace to the current +# Namespace. +# +# For example, suppose we have the following Namespaces: +# +# GitLab (id: 1) > Engineering (id: 2) > Manage (id: 3) > Access (id: 4) +# +# Then `traversal_ids` for group "Access" is [1, 2, 3, 4] +# +# And we can match against other Namespace `traversal_ids` such that: +# +# - Ancestors are [1], [1, 2], [1, 2, 3] +# - Descendants are [1, 2, 3, 4, *] +# - Root is [1] +# - Hierarchy is [1, *] +# +# Note that this search method works so long as the IDs are unique and the +# traversal path is ordered from root to leaf nodes. +# +# We implement this in the database using Postgresql arrays, indexed by a +# generalized inverted index (gin). +module Namespaces + module Traversal + module Linear + extend ActiveSupport::Concern + + included do + after_create :sync_traversal_ids, if: -> { sync_traversal_ids? } + after_update :sync_traversal_ids, if: -> { sync_traversal_ids? && saved_change_to_parent_id? } + end + + def sync_traversal_ids? + Feature.enabled?(:sync_traversal_ids, root_ancestor, default_enabled: :yaml) + end + + private + + # Update the traversal_ids for the full hierarchy. + # + # NOTE: self.traversal_ids will be stale. Reload for a fresh record. + def sync_traversal_ids + # Clear any previously memoized root_ancestor as our ancestors have changed. + clear_memoization(:root_ancestor) + + Namespace::TraversalHierarchy.for_namespace(root_ancestor).sync_traversal_ids! + end + end + end +end diff --git a/app/models/namespaces/traversal/recursive.rb b/app/models/namespaces/traversal/recursive.rb index d74b7883830..aac70a1a0a9 100644 --- a/app/models/namespaces/traversal/recursive.rb +++ b/app/models/namespaces/traversal/recursive.rb @@ -6,10 +6,14 @@ module Namespaces extend ActiveSupport::Concern def root_ancestor - return self if persisted? && parent_id.nil? + return self if parent.nil? - strong_memoize(:root_ancestor) do - self_and_ancestors.reorder(nil).find_by(parent_id: nil) + if persisted? + strong_memoize(:root_ancestor) do + self_and_ancestors.reorder(nil).find_by(parent_id: nil) + end + else + parent.root_ancestor end end |