From ac382b5682dc2d5eea750313c59fb2581af13326 Mon Sep 17 00:00:00 2001 From: Yorick Peterse Date: Mon, 24 Apr 2017 17:19:22 +0200 Subject: Use CTEs for nested groups and authorizations This commit introduces the usage of Common Table Expressions (CTEs) to efficiently retrieve nested group hierarchies, without having to rely on the "routes" table (which is an _incredibly_ inefficient way of getting the data). This requires a patch to ActiveRecord (found in the added initializer) to work properly as ActiveRecord doesn't support WITH statements properly out of the box. Unfortunately MySQL provides no efficient way of getting nested groups. For example, the old routes setup could easily take 5-10 seconds depending on the amount of "routes" in a database. Providing vastly different logic for both MySQL and PostgreSQL will negatively impact the development process. Because of this the various nested groups related methods return empty relations when used in combination with MySQL. For project authorizations the logic is split up into two classes: * Gitlab::ProjectAuthorizations::WithNestedGroups * Gitlab::ProjectAuthorizations::WithoutNestedGroups Both classes get the fresh project authorizations (= as they should be in the "project_authorizations" table), including nested groups if PostgreSQL is used. The logic of these two classes is quite different apart from their public interface. This complicates development a bit, but unfortunately there is no way around this. This commit also introduces Gitlab::GroupHierarchy. This class can be used to get the ancestors and descendants of a base relation, or both by using a UNION. This in turn is used by methods such as: * Namespace#ancestors * Namespace#descendants * User#all_expanded_groups Again this class relies on CTEs and thus only works on PostgreSQL. The Namespace methods will return an empty relation when MySQL is used, while User#all_expanded_groups will return only the groups a user is a direct member of. Performance wise the impact is quite large. For example, on GitLab.com Namespace#descendants used to take around 580 ms to retrieve data for a particular user. Using CTEs we are able to reduce this down to roughly 1 millisecond, returning the exact same data. == On The Fly Refreshing Refreshing of authorizations on the fly (= when users.authorized_projects_populated was not set) is removed with this commit. This simplifies the code, and ensures any queries used for authorizations are not mutated because they are executed in a Rails scope (e.g. Project.visible_to_user). This commit includes a migration to schedule refreshing authorizations for all users, ensuring all of them have their authorizations in place. Said migration schedules users in batches of 5000, with 5 minutes between every batch to smear the load around a bit. == Spec Changes This commit also introduces some changes to various specs. For example, some specs for ProjectTeam assumed that creating a personal project would _not_ lead to the owner having access, which is incorrect. Because we also no longer refresh authorizations on the fly for new users some code had to be added to the "empty_project" factory. This chunk of code ensures that the owner's permissions are refreshed after creating the project, something that is normally done in Projects::CreateService. --- ...0503140201_reschedule_project_authorizations.rb | 44 ++++++++++++++++++++++ ...0_remove_users_authorized_projects_populated.rb | 15 ++++++++ db/schema.rb | 1 - 3 files changed, 59 insertions(+), 1 deletion(-) create mode 100644 db/migrate/20170503140201_reschedule_project_authorizations.rb create mode 100644 db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb (limited to 'db') diff --git a/db/migrate/20170503140201_reschedule_project_authorizations.rb b/db/migrate/20170503140201_reschedule_project_authorizations.rb new file mode 100644 index 00000000000..fa45adadbae --- /dev/null +++ b/db/migrate/20170503140201_reschedule_project_authorizations.rb @@ -0,0 +1,44 @@ +# See http://doc.gitlab.com/ce/development/migration_style_guide.html +# for more information on how to write migrations for GitLab. + +class RescheduleProjectAuthorizations < ActiveRecord::Migration + include Gitlab::Database::MigrationHelpers + + DOWNTIME = false + + disable_ddl_transaction! + + class User < ActiveRecord::Base + self.table_name = 'users' + end + + def up + offset = 0 + batch = 5000 + start = Time.now + + loop do + relation = User.where('id > ?', offset) + user_ids = relation.limit(batch).reorder(id: :asc).pluck(:id) + + break if user_ids.empty? + + offset = user_ids.last + + # This will schedule each batch 5 minutes after the previous batch was + # scheduled. This smears out the load over time, instead of immediately + # scheduling a million jobs. + Sidekiq::Client.push_bulk( + 'queue' => 'authorized_projects', + 'args' => user_ids.zip, + 'class' => 'AuthorizedProjectsWorker', + 'at' => start.to_i + ) + + start += 5.minutes + end + end + + def down + end +end diff --git a/db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb b/db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb new file mode 100644 index 00000000000..1b44334395f --- /dev/null +++ b/db/post_migrate/20170503120310_remove_users_authorized_projects_populated.rb @@ -0,0 +1,15 @@ +# See http://doc.gitlab.com/ce/development/migration_style_guide.html +# for more information on how to write migrations for GitLab. + +class RemoveUsersAuthorizedProjectsPopulated < ActiveRecord::Migration + include Gitlab::Database::MigrationHelpers + + # Set this constant to true if this migration requires downtime. + DOWNTIME = false + + disable_ddl_transaction! + + def change + remove_column :users, :authorized_projects_populated, :boolean + end +end diff --git a/db/schema.rb b/db/schema.rb index 65eaccf766a..9773203e9cd 100644 --- a/db/schema.rb +++ b/db/schema.rb @@ -1352,7 +1352,6 @@ ActiveRecord::Schema.define(version: 20170508190732) do t.boolean "external", default: false t.string "incoming_email_token" t.string "organization" - t.boolean "authorized_projects_populated" t.boolean "require_two_factor_authentication_from_group", default: false, null: false t.integer "two_factor_grace_period", default: 48, null: false t.boolean "ghost" -- cgit v1.2.3 From 53250d6d8a7f016e8a7f503509e489b444859429 Mon Sep 17 00:00:00 2001 From: Yorick Peterse Date: Wed, 3 May 2017 18:08:27 +0200 Subject: Convert nested groups to regular ones for MySQL This migration will take all nested groups and convert them into regular groups, ensuring that members of any parent groups still have access to the child group. This migration relies on code external to it as copying all of this over involves hundreds of lines of code depending on all sorts of methods, making this practically impossible to do right. --- ..._nested_groups_into_regular_groups_for_mysql.rb | 123 +++++++++++++++++++++ 1 file changed, 123 insertions(+) create mode 100644 db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb (limited to 'db') diff --git a/db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb b/db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb new file mode 100644 index 00000000000..c67690642c9 --- /dev/null +++ b/db/migrate/20170503140202_turn_nested_groups_into_regular_groups_for_mysql.rb @@ -0,0 +1,123 @@ +# See http://doc.gitlab.com/ce/development/migration_style_guide.html +# for more information on how to write migrations for GitLab. + +# This migration depends on code external to it. For example, it relies on +# updating a namespace to also rename directories (uploads, GitLab pages, etc). +# The alternative is to copy hundreds of lines of code into this migration, +# adjust them where needed, etc; something which doesn't work well at all. +class TurnNestedGroupsIntoRegularGroupsForMysql < ActiveRecord::Migration + include Gitlab::Database::MigrationHelpers + + # Set this constant to true if this migration requires downtime. + DOWNTIME = false + + def run_migration? + Gitlab::Database.mysql? + end + + def up + return unless run_migration? + + # For all sub-groups we need to give the right people access. We do this as + # follows: + # + # 1. Get all the ancestors for the current namespace + # 2. Get all the members of these namespaces, along with their higher access + # level + # 3. Give these members access to the current namespace + Namespace.unscoped.where('parent_id IS NOT NULL').find_each do |namespace| + rows = [] + existing = namespace.members.pluck(:user_id) + + all_members_for(namespace).each do |member| + next if existing.include?(member[:user_id]) + + rows << { + access_level: member[:access_level], + source_id: namespace.id, + source_type: 'Namespace', + user_id: member[:user_id], + notification_level: 3, # global + type: 'GroupMember', + created_at: Time.current, + updated_at: Time.current + } + end + + bulk_insert_members(rows) + + # This method relies on the parent to determine the proper path. + # Because we reset "parent_id" this method will not return the right path + # when moving namespaces. + full_path_was = namespace.send(:full_path_was) + + namespace.define_singleton_method(:full_path_was) { full_path_was } + + namespace.update!(parent_id: nil, path: new_path_for(namespace)) + end + end + + def down + # There is no way to go back from regular groups to nested groups. + end + + # Generates a new (unique) path for a namespace. + def new_path_for(namespace) + counter = 1 + base = namespace.full_path.tr('/', '-') + new_path = base + + while Namespace.unscoped.where(path: new_path).exists? + new_path = base + "-#{counter}" + counter += 1 + end + + new_path + end + + # Returns an Array containing all the ancestors of the current namespace. + # + # This method is not particularly efficient, but it's probably still faster + # than using the "routes" table. Most importantly of all, it _only_ depends + # on the namespaces table and the "parent_id" column. + def ancestors_for(namespace) + ancestors = [] + current = namespace + + while current&.parent_id + # We're using find_by(id: ...) here to deal with cases where the + # parent_id may point to a missing row. + current = Namespace.unscoped.select([:id, :parent_id]). + find_by(id: current.parent_id) + + ancestors << current.id if current + end + + ancestors + end + + # Returns a relation containing all the members that have access to any of + # the current namespace's parent namespaces. + def all_members_for(namespace) + Member. + unscoped. + select(['user_id', 'MAX(access_level) AS access_level']). + where(source_type: 'Namespace', source_id: ancestors_for(namespace)). + group(:user_id) + end + + def bulk_insert_members(rows) + return if rows.empty? + + keys = rows.first.keys + + tuples = rows.map do |row| + row.map { |(_, value)| connection.quote(value) } + end + + execute <<-EOF.strip_heredoc + INSERT INTO members (#{keys.join(', ')}) + VALUES #{tuples.map { |tuple| "(#{tuple.join(', ')})" }.join(', ')} + EOF + end +end -- cgit v1.2.3 From 91c971bf987824df0e066c20ac341bb5e7485e95 Mon Sep 17 00:00:00 2001 From: Yorick Peterse Date: Thu, 4 May 2017 20:43:46 +0200 Subject: Index project_group_links.group_id This column is used when refreshing authorizations and without the index leads to a sequence scan being performed on this table. --- ...04182103_add_index_project_group_links_group_id.rb | 19 +++++++++++++++++++ db/schema.rb | 2 ++ 2 files changed, 21 insertions(+) create mode 100644 db/migrate/20170504182103_add_index_project_group_links_group_id.rb (limited to 'db') diff --git a/db/migrate/20170504182103_add_index_project_group_links_group_id.rb b/db/migrate/20170504182103_add_index_project_group_links_group_id.rb new file mode 100644 index 00000000000..62bf641daa6 --- /dev/null +++ b/db/migrate/20170504182103_add_index_project_group_links_group_id.rb @@ -0,0 +1,19 @@ +# See http://doc.gitlab.com/ce/development/migration_style_guide.html +# for more information on how to write migrations for GitLab. + +class AddIndexProjectGroupLinksGroupId < ActiveRecord::Migration + include Gitlab::Database::MigrationHelpers + + # Set this constant to true if this migration requires downtime. + DOWNTIME = false + + disable_ddl_transaction! + + def up + add_concurrent_index :project_group_links, :group_id + end + + def down + remove_concurrent_index :project_group_links, :group_id + end +end diff --git a/db/schema.rb b/db/schema.rb index 9773203e9cd..2567dda0edc 100644 --- a/db/schema.rb +++ b/db/schema.rb @@ -925,6 +925,8 @@ ActiveRecord::Schema.define(version: 20170508190732) do t.date "expires_at" end + add_index "project_group_links", ["group_id"], name: "index_project_group_links_on_group_id", using: :btree + create_table "project_import_data", force: :cascade do |t| t.integer "project_id" t.text "data" -- cgit v1.2.3