Add latest changes from gitlab-org/gitlab@master

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