doAddLeaf & doRemoveLeaf: timestamp bug and scalability

@lind101 In my tests I noticed that the left and right values for the revisions were not updated. Tables {group_revision__subgroup_left} and {group_revision__subgroup_right}. Is that on purpose or just an oversight?

Revisions in combination with the subgroup module can lead to broken trees. I just did the following test:

• Update a subgroup and create a new revision
• Add a subsubgroup to an earlier branch which changes the left/right values of the subgroup with a revision.
• Revert the revision.
• The left/right values will also be reverted to the earlier values and your tree structure is corrupted.

The same will happen if you have revisions enabled, delete a 'early' subgroup and revert to a revision of a newer subgroup.

The best way to solve this probably is to update the left/right values of all revisions of a subgroup. In my own patches for this issue I only updated the latest revision, which clearly is not enough.

We will have to invoke getAllFieldTableNames to get all the tables that would need to be updated.

I am testing the attached patch now. This patch returns an array of \Drupal\Core\Database\Query\Update in buildLeftValueUpdateQuery and buildRightValueUpdateQuery. If revisions are enabled 4 tables are updated. On a doAddLeaf:

UPDATE {group__subgroup_left} SET "subgroup_left_value"=IF(subgroup_left_value > :right_value, subgroup_left_value + 2, subgroup_left_value) WHERE "entity_id" IN $ids_to_update;

UPDATE {group_revision__subgroup_left} SET "subgroup_left_value"=IF(subgroup_left_value > :right_value, subgroup_left_value + 2, subgroup_left_value) WHERE "entity_id" IN $ids_to_update;

UPDATE {group__subgroup_right} SET "subgroup_right_value"=subgroup_right_value + 2 WHERE "entity_id" IN $ids_to_update;

UPDATE {group_revision__subgroup_right} SET "subgroup_right_value"=subgroup_right_value + 2 WHERE "entity_id" IN $ids_to_update;

All revisions of a group are updated as well, which is the desired action.

The essential parts of SubgroupHandlerBase.php are as follow now:

  /**
   * Attempt to get the lock used to allow tree value editing
   *
   * @return bool
   */
  public function getTreeLock(): bool {
    return $this->lockBackend->acquire(self::TREE_LOCK);
  }

  /**
   * Release the lock used to allow tree value editing
   */
  public function releaseTreeLock() {
    $this->lockBackend->release(self::TREE_LOCK);
  }

  /**
   * See it the tree value editing lock is available to be acquired
   *
   * @return bool
   */
  public function isTreeLockAvailable(): bool {
    return $this->lockBackend->lockMayBeAvailable(self::TREE_LOCK);
  }

  /**
   * Helper method to get the table name for subgroup fields
   *
   * @param string $field_name
   *
   * @return string
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function getTableName(string $field_name) {
    if ($this->storage instanceof SqlEntityStorageInterface) {
      return $this->storage->getTableMapping()->getFieldTableName($field_name);
    }

    throw new SqlContentEntityStorageException('Unknown storage');
  }

  /**
   * Helper method to get all table names for subgroup fields
   *
   * @param string $field_name
   *
   * @return array of strings
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function getTableNames(string $field_name) {
    if ($this->storage instanceof SqlEntityStorageInterface) {
      return $this->storage->getTableMapping()->getAllFieldTableNames($field_name);
    }

    throw new SqlContentEntityStorageException('Unknown storage');
  }

  /**
   * Helper method to get the value column name for subgroup fields
   *
   * @param string $field_name
   *
   * @return string
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function getValueColumnName(string $field_name) {
    $field_storage = $this->fieldManager->getFieldStorageDefinitions($this->storage->getEntityTypeId());
    if (isset($field_storage[$field_name]) && $this->storage instanceof SqlEntityStorageInterface) {
      return $this->storage->getTableMapping()->getFieldColumnName($field_storage[$field_name], 'value');
    }

    throw new SqlContentEntityStorageException('Unknown value column');
  }

  /**
   * Build an update query to update the right values of affected entities when a leaf is added or removed
   *
   * @param array $ids_to_update
   *  the entity id's affected by the leaf addition/removal
   * @param string $action
   *  the action being taken, leaf added or leaf removed
   *
   * @return array of \Drupal\Core\Database\Query\Update
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function buildRightValueUpdateQuery(array $ids_to_update, string $action) {
    $column_name = $this->getValueColumnName(SUBGROUP_RIGHT_FIELD);

    switch ($action) {
      case self::LEAF_ADD:
        $expression = "$column_name + 2";
        break;

      case self::LEAF_REMOVE:
        $expression = "$column_name - 2";
        break;

      default:
        throw new InvalidArgumentException('Invalid left query amend action supplied');
    }

    $tablenames = $this->getTableNames(SUBGROUP_RIGHT_FIELD);
    $updates = Array();
    foreach ($tablenames as $tablename) {
      $update = $this->database->update($tablename)
      ->expression($column_name, $expression)
      ->condition('entity_id', $ids_to_update, 'IN');
      //\Drupal::logger('writeLeafData')->notice("buildRightValueUpdateQuery {$update}");
      $updates[] = $update;
    }
    return $updates;
  }

  /**
   * Build an update query to update the right values of affected entities when a leaf is
   * added to the tree
   *
   * @param array $ids_to_update
   *  the entity id's affected by the leaf removal
   *
   * @return array of \Drupal\Core\Database\Query\Update
   */
  public function getAddLeafRightUpdate($ids_to_update) {
    return $this->buildRightValueUpdateQuery($ids_to_update, self::LEAF_ADD);
  }

  /**
   * Build an update query to update the right values of affected entities when a leaf is
   * removed from the tree
   *
   * @param array $ids_to_update
   *  the entity id's affected by the leaf removal
   *
   * @return array of \Drupal\Core\Database\Query\Update
   */
  public function getRemoveLeafRightUpdate($ids_to_update) {
    return $this->buildRightValueUpdateQuery($ids_to_update, self::LEAF_REMOVE);
  }

  /**
   * Build an update query to update the left values of affected entities when a leaf is added or removed
   *
   * @param array $ids_to_update
   *  the entity id's affected by the leaf addition/removal
   * @param int $right_value
   *  the right value to base the expression on
   * @param string $action
   *  the action being taken, leaf added or leaf removed
   *
   * @return array of \Drupal\Core\Database\Query\Update
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function buildLeftValueUpdateQuery(array $ids_to_update, int $right_value, string $action) {
    $column_name = $this->getValueColumnName(SUBGROUP_LEFT_FIELD);

    switch ($action) {
      case self::LEAF_ADD:
        $expression = "IF($column_name > :right_value, $column_name + 2, $column_name)";
        break;

      case self::LEAF_REMOVE:
        $expression = "IF($column_name > :right_value, $column_name - 2, $column_name)";
        break;

      default:
        throw new InvalidArgumentException('Invalid left query amend action supplied');
    }

    $tablenames = $this->getTableNames(SUBGROUP_LEFT_FIELD);
    $updates = Array();
    foreach ($tablenames as $tablename) {
      $update = $this->database->update($tablename)
      ->expression($column_name, $expression, [':right_value' => $right_value])
      ->condition('entity_id', $ids_to_update, 'IN');
      //\Drupal::logger('writeLeafData')->notice("buildLeftValueUpdateQuery {$update}");
      $updates[] = $update;
    }
    return $updates;
  }

  /**
   * Build an update query to update the left values of affected entities when a leaf is
   * added to the tree
   *
   * @param array $ids_to_update
   *  the entity id's affected by the leaf addition
   * @param int $right_value
   *  the right value of the parent that the leaf is being added to
   *
   * @return array of \Drupal\Core\Database\Query\Update
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function getAddLeafLeftUpdate($ids_to_update, $right_value) {
    return $this->buildLeftValueUpdateQuery($ids_to_update, $right_value, self::LEAF_ADD);
  }

  /**
   * Build an update query to update the left values of affected entities when a leaf is
   * removed from the tree
   *
   * @param array $ids_to_update
   *  the entity id's affected by the leaf removal
   * @param int $right_value
   *  the right value of the leaf being removed
   *
   * @return array of \Drupal\Core\Database\Query\Update
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function getRemoveLeafLeftUpdate(array $ids_to_update, int $right_value) {
    return $this->buildLeftValueUpdateQuery($ids_to_update, $right_value, self::LEAF_REMOVE);
  }

  /**
   * Retrieve tree values for an entity direct from the database to avoid issues with out-dated values
   * during race conditions
   *
   * @param \Drupal\Core\Entity\EntityInterface $entity
   *
   * @return object|null
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function getLiveTreeValues(EntityInterface $entity) {
    $query = $this->database->select($this->getTableName(SUBGROUP_RIGHT_FIELD), 'r')
      ->fields('r', [$this->getValueColumnName(SUBGROUP_RIGHT_FIELD)])
      ->fields('l', [$this->getValueColumnName(SUBGROUP_LEFT_FIELD)])
      ->fields('d', [$this->getValueColumnName(SUBGROUP_DEPTH_FIELD)])
      ->fields('t', [$this->getValueColumnName(SUBGROUP_TREE_FIELD)]);
    $query->innerJoin($this->getTableName(SUBGROUP_LEFT_FIELD), 'l', 'l.entity_id = r.entity_id');
    $query->innerJoin($this->getTableName(SUBGROUP_DEPTH_FIELD), 'd', 'd.entity_id = r.entity_id');
    $query->innerJoin($this->getTableName(SUBGROUP_TREE_FIELD), 't', 't.entity_id = r.entity_id');
    $results = $query->condition('r.entity_id', $entity->id())
      ->execute()->fetchAll();

    $values = NULL;
    if (!empty($results)) {
      $values = (array) reset($results);
      $keys = array_map(function ($value) {
        return explode('_', $value)[1];
      }, array_keys($values));

      $values = array_combine($keys, array_values($values));

      $values = (object) array_map(function ($value) {
        return (int) $value;
      }, $values);
    }

    return $values;
  }

  /**
   * {@inheritdoc}
   */
  public function addLeaf(EntityInterface $parent, EntityInterface $child) {
    $this->verify($parent);
    $this->verify($child);

    if (!$this->isLeaf($parent)) {
      throw new InvalidParentException('The entity to use as the parent is not a leaf.');
    }
    if ($child->isNew()) {
      throw new InvalidLeafException('Cannot use an unsaved entity as a leaf.');
    }
    if ($this->isLeaf($child)) {
      throw new InvalidLeafException('The entity to add as the leaf is already a leaf.');
    }

    $this->doAddLeaf($parent, $child);
  }

  /**
   * Actually adds a leaf to a tree.
   *
   * This is called after a few sanity checks and can be easily overwritten by
   * the extending classes.
   *
   * @param \Drupal\Core\Entity\EntityInterface $parent
   *   The entity to use as the parent.
   * @param \Drupal\Core\Entity\EntityInterface $child
   *   The entity to use as the new leaf.
   */
  protected function doAddLeaf(EntityInterface $parent, EntityInterface $child) {
    // This is a better implementation of the 60 second stuff
    /* @see \Drupal\subgroup\Entity\GroupSubgroupHandler::doAddLeaf() */
    if ($this->isLeaf($child)) {
      throw new InvalidLeafException('The provided entity is already a leaf, cannot add again.');
    }

    if ($this->groupTypeHandler->getParent($child->getGroupType())->id() !== $parent->bundle()) {
      throw new InvalidParentException('Provided group cannot be added as a leaf to the parent (incompatible group types).');
    }

    /**
     * If two subgroups are created/removed at the same time we run the risk of race conditions to update leaf values here
     * which can lead to invalid left and right values.
     *
     * To mitigate this we lock this process down so only one process can amend tree values at any given time
     */
    $blocked = TRUE;
    $logged = FALSE;
    do {
      // Try to obtain the tree lock, otherwise wait until it is free (Max 30 sec)
      if ($this->isTreeLockAvailable() && $this->getTreeLock()) {
        $blocked = FALSE;
      } else {
        if (!$logged) {
          \Drupal::logger('pipelyft_subgroup')->debug($this->t('Subgroup lock hit for parent: %id - %label. Child: %child_id - %child_label', [
            '%id' => $parent->id(),
            '%label' => $parent->label(),
            '%child_id' => $child->id(),
            '%child_label' => $child->label(),
          ]));
          $logged = TRUE;
        }
      }
    } while ($blocked);

    $transaction = NULL;
    try {
      // Load the values directly from the database to avoid any caching issues when in a race condition
      $parentValues = $this->getLiveTreeValues($parent);

      if (is_null($parentValues)) {
        throw new InvalidArgumentException('Supplied parent has no tree values.');
      }

      /**
       * Find all the entities that we need to update: this is any entries that have the same or higher right value
       * than the parent, are part of the same tree and are not the parent themselves
       */
      $ids_to_update = $this->storage->getQuery()
        ->condition($this->getRightPropertyName(), $parentValues->right, '>=')
        ->condition($this->getTreePropertyName(), $parentValues->tree)
        // We deal with the passed in parent, rather than a freshly loaded copy so
        // that any code calling this method does not have an out of sync entity
        // for the rest of its runtime.
        ->condition($this->entityType->getKey('id'), $parent->id(), '<>')
        ->accessCheck(FALSE)
        ->execute();

      // Start a transaction to encompass the following update queries in-case we run into an error half-way
      // through and need to rollback
      $transaction = $this->database->startTransaction('subgroup_tree_update');

      // If we have bits of the tree that need moving, lets do it
      if (!empty($ids_to_update)) {

        /**
         * First we are going to update the left values of the affected entities, the aim of this is to
         * make sure we have enough space to grow the current parent.
         *
         * With this query we only want to update siblings (and their subgroups) to give us room to add a
         * new leaf (2 units) to the current parent (I.e. Update the parents right value by 2).
         *
         * To do this only increase the left value of entities whos left value is currently greater than the
         * right value of the parent.
         */
        $updates = $this->getAddLeafLeftUpdate($ids_to_update, $parentValues->right);
        foreach ($updates as $update) {
          $update->execute();
        }

        /**
         * Now we need to update the right values. The aim of this is to make sure that sibling groups
         * (and their children) are still the same size as when we started the update, and that we grow
         * any parents of the current parent to accommodate the new leaf new are about to add.
         *
         * This is easier, we just need to update all the right values by 2 units
         */
        $updates = $this->getAddLeafRightUpdate($ids_to_update);
        foreach ($updates as $update) {
          $update->execute();
        }
      }

      // Now that we have made room in the tree we can expand the parent
      $this->writeLeafData(
        $parent,
        $parentValues->depth,
        $parentValues->left,
        $parentValues->right + 2,
        $parentValues->tree
      );

      // And finally add the new leaf (Using the original right value to work out a 2 unit span)
      $this->writeLeafData(
        $child,
        $parentValues->depth + 1,
        $parentValues->right,
        $parentValues->right + 1,
        $parentValues->tree
      );

      // All the affected entities need their memory cache entries cleared
      // (So they reflect the new tree values on their next load)
      $this->storage->resetCache($ids_to_update);
    } catch (Exception $e) {
      // If something goes wrong during the update, roll everything back and release the tree lock
      if ($transaction instanceof Transaction) {
        $transaction->rollBack();
      }
      $this->releaseTreeLock();

      throw $e;
    }

    // Once everything has run successfully, commit the transaction by unsetting it and release the tree lock
    unset($transaction);
    $this->releaseTreeLock();
  }

  /**
   * {@inheritdoc}
   */
  public function removeLeaf(EntityInterface $entity, $save = TRUE) {
    $this->verify($entity);

    if (!$this->isLeaf($entity)) {
      throw new InvalidLeafException('The entity to remove is not a leaf.');
    }
    if ($this->hasDescendants($entity)) {
      throw new InvalidLeafException('Cannot remove a leaf that still has descendants.');
    }

    $this->doRemoveLeaf($entity, $save);
  }

  /**
   * Actually removes a leaf from a tree.
   *
   * This is called after a few sanity checks and can be easily overwritten by
   * the extending classes.
   *
   * @param \Drupal\Core\Entity\EntityInterface $entity
   *   The entity to remove from the tree.
   * @param bool $save
   *   Whether the entity should be saved.
   */
  protected function doRemoveLeaf(EntityInterface $entity, $save) {
    /**
     * If two subgroups are created/removed at the same time we run the risk of race conditions to update leaf values here
     * which can lead to invalid left and right values.
     *
     * To mitigate this we lock this process down so only one process can amend tree values at any given time
     */
    $blocked = TRUE;
    do {
      // Try to obtain the tree lock, otherwise wait until it is free (Max 30 sec)
      if ($this->isTreeLockAvailable() && $this->getTreeLock()) {
        $blocked = FALSE;
      }
    } while ($blocked);

    $transaction = NULL;
    try {
      // We have to use the values stored on the Entity object rather than going to the database when deleting groups
      // because by this point in the delete transaction the field values have already been removed from the database
      // The easiest way to do this is to use the leaf wrapper.
      $leaf = $this->wrapLeaf($entity);

      $leafValues = new stdClass();
      $leafValues->left = $leaf->getLeft();
      $leafValues->right = $leaf->getRight();
      $leafValues->depth = $leaf->getDepth();
      $leafValues->tree = $leaf->getTree();

      // If the left and right values are 2 and 3 respectively it means we might
      // be removing the last child of a tree root. In this case, we unset the
      // tree altogether.
      if ($leafValues->left === 2 && $leafValues->right === 3 && $this->getDescendantCount($root = $this->storage->load($leafValues->tree)) === 1) {
        $this->clearLeafData($root, TRUE);
      }
      // Otherwise, we need to shrink the surrounding tree
      else {
        $ids_to_update = $this->storage->getQuery()
          ->condition($this->getRightPropertyName(), $leafValues->right, '>')
          ->condition($this->getTreePropertyName(), $leafValues->tree)
          ->accessCheck(FALSE)
          ->execute();

        // If we have bits of the tree that need moving, lets do it
        if (!empty($ids_to_update)) {
          $transaction = $this->database->startTransaction('subgroup_tree_update');

          /**
           * First we are going to update the left values of the affected entities, the aim of this is to
           * make sure we shrink the tree to prepare for a removal of a leaf from the parent.
           *
           * With this query we only want to update siblings (and their subgroups) to shrink back 2 values each in
           * anticipation of removing a leaf (2 units) from the current parent (I.e. Decrease the parents right value by 2).
           *
           * To do this only decrease the left value of entities whos left value is currently greater than the
           * right value of the parent.
           */
          $updates = $this->getRemoveLeafLeftUpdate($ids_to_update, $leafValues->right);
          foreach ($updates as $update) {
            $update->execute();
          }

          /**
           * Now we need to update the right values. The aim of this is to make sure that sibling groups
           * (and their children) are still the same size as when we started the update, and that we shrink
           * any parents of the current parent to accommodate the removal of leaf.
           *
           * This is easier, we just need to decrease all the right values by 2 units
           */
          $updates = $this->getRemoveLeafRightUpdate($ids_to_update);
          foreach ($updates as $update) {
            $update->execute();
          }

          // All the affected entities need their memory cache entries cleared
          // (So they reflect the new tree values on their next load)
          $this->storage->resetCache($ids_to_update);
        }
      }

      // We can now remove the leaf from the tree
      $this->clearLeafData($entity, $save);

    } catch (Exception $e) {
      // If something goes wrong during the update, roll everything back and release the tree lock
      if ($transaction instanceof Transaction) {
        $transaction->rollBack();
      }
      $this->releaseTreeLock();

      throw $e;
    }

    // Once everything has run successfully, commit the transaction by unsetting it and release the tree lock
    unset($transaction);
    $this->releaseTreeLock();
  }

Hey @Jan-E, I'm gald you found the code useful!

Yea apologies, the revisions were a bit of an afterthought I must admit as we don't use revisions for groups on the project this work was for, so only focused on what we needed.

Glad to see that you have managed to retro fit them! Revision may be a little challenging with this approach because we are bypassing the standard revision creation logic by updating the tree values directly in the database. Has the new revision already created by the time we get to this code? If so I'm surprised that just updating the latest revision wasn't enough.

Hey @lind101,

The point is that reverting to an earlier revision also reverted the left/right values to those of the earlier revision. That is why we have to update all revisions with the new left/right values.

I do not know if the new revision has already been inserted into the database before we reach the code and, if so, with which values. What I do know is that a group is already deleted from the database before we reach doRemoveLeaf. Which means that we have got a corrupted tree when doRemoveLeaf is not executed somehow. I would not know how to solve that.

Did you already have a chance to test the latest patch in your situation, without revisions? I have put that patch in production last night, with some additional logging. Initial experiences are OK. But the cache-out-of-sync cases happened only every couple of weeks. That piece of code is still there, so if it happens it will be logged.

BTW: querying for the ids_to_update and afterwards building a query with a condition if the entity_id is IN the ids_to_update array seems a bit redundant. That can probably be done in one query. See #13 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed .

The point is that reverting to an earlier revision also reverted the left/right values to those of the earlier revision. That is why we have to update all revisions with the new left/right values.

Right yea makes sense, because the new leaf will still exist even if you are reverting the current Group to an older version.

What I do know is that a group is already deleted from the database before we reach doRemoveLeaf. Which means that we have got a corrupted tree when doRemoveLeaf is not executed somehow.

Yea this is why I reverted to using the wrapLeaf method when deleting Groups because the tree values at that point are no longer in the database, but are still stroed in momory on the Group object so can be accessed that way. Is the below not working for you then?

// We have to use the values stored on the Entity object rather than going to the database when deleting groups
      // because by this point in the delete transaction the field values have already been removed from the database
      // The easiest way to do this is to use the leaf wrapper.
      $leaf = $this->wrapLeaf($entity);

Did you already have a chance to test the latest patch in your situation, without revisions? I have put that patch in production last night, with some additional logging. Initial experiences are OK. But the cache-out-of-sync cases happened only every couple of weeks. That piece of code is still there, so if it happens it will be logged.

I have not tried it yet, the lead time on changes like that my end are quite involved. It looks like it would work fine though from taking a look at it. I will try to test it locally when I get round to looking at it again, but unfortuantly my focus is on other things at the moment!

querying for the ids_to_update and afterwards building a query with a condition if the entity_id is IN the ids_to_update array seems a bit redundant. That can probably be done in one query

Yea my thinking behind doing this first was that it would prevent any potential issues with updating the wrong values if the left/right values had changed in the time that we ran the two queries. I.e in that current setup both queries know exactly what they need to update, regardless of the left/right values. However your probably right the chances of that happening are slim to none I would have thought.

Cheers!

doRemoveLeaf normally works OK, but there are 2 transactions: 1 for deleting/adding the entity (core) and 1 for updating the leaf values (subgroup). A disruption between the 2 or while executing the 2nd might mean you haven’t updated the leaf values of the higher groups (doRemoveLeaf) or have a group without left/right values (doAddLeaf). The latter happened to me once: #35 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed .

Might be an edge case, but I am not really sure thet the cache of the parent is updated after an doAddLeaf. So after

      // Now that we have made room in the tree we can expand the parent
      $this->writeLeafData(
        $parent,
        $parentValues->depth,
        $parentValues->left,
        $parentValues->right + 2,
        $parentValues->tree
      );

I added

      // Clear the memory cache of the parent
      // (So it reflects the new tree values on their next load by any user)
      $this->storage->resetCache($parent->id());

Better safe than sorry.

querying for the ids_to_update and afterwards building a query with a condition if the entity_id is IN the ids_to_update array seems a bit redundant. That can probably be done in one query.

Yea my thinking behind doing this first was that it would prevent any potential issues with updating the wrong values if the left/right values had changed in the time that we ran the two queries. I.e in that current setup both queries know exactly what they need to update, regardless of the left/right values. However your probably right the chances of that happening are slim to none I would have thought.

My main objection against using the $ids_to_update array in the query is that there might be scalability issues. There is a chance that I will be migrating a site with over 80,000 groups from plain old PHP to Drupal with the subgroup module. So the query might contain a check for entity_id in an array of 80,000 values. A query like

UPDATE {group__subgroup_left} SET "subgroup_left_value"=IF(subgroup_left_value > :right_value, subgroup_left_value + 2, subgroup_left_value) WHERE "entity_id" IN $ids_to_update;

does not feel good when actually you need something like

UPDATE {group__subgroup_left} SET "subgroup_left_value" = subgroup_left_value + 2 WHERE "subgroup_tree_value" = :tree_value AND "subgroup_left_value" > :right_value;

Of course, this query needs a JOIN for getting the subgroup_tree_value but you will get the idea. And we still need the $ids_to_update for the resetCache.

I am refactoring the complete patch now to make that possible.

I am testing the attached patch now. The direct queries are not generated by \Drupal\Core\Database\Query\Update, but written als 'raw' queries. Examples of the queries, while adding a leaf:

UPDATE {group__subgroup_left} l
JOIN {group__subgroup_right} r ON r.entity_id = l.entity_id
JOIN {group__subgroup_tree} t ON t.entity_id = l.entity_id
SET subgroup_left_value = (subgroup_left_value + 2)
WHERE l.subgroup_left_value > 12125
AND r.subgroup_right_value >= 12125
AND t.subgroup_tree_value = 2
AND l.entity_id != 7237
		  
UPDATE {group_revision__subgroup_left} l
JOIN {group__subgroup_right} r ON r.entity_id = l.entity_id
JOIN {group__subgroup_tree} t ON t.entity_id = l.entity_id
SET subgroup_left_value = (subgroup_left_value + 2)
WHERE l.subgroup_left_value > 12125
AND r.subgroup_right_value >= 12125
AND t.subgroup_tree_value = 2
AND l.entity_id != 7237

UPDATE {group__subgroup_right} r
JOIN {group__subgroup_tree} t ON t.entity_id = r.entity_id
SET subgroup_right_value = (subgroup_right_value + 2)
WHERE r.subgroup_right_value >= 12125
AND t.subgroup_tree_value = 2
AND r.entity_id != 7237

UPDATE {group_revision__subgroup_right} r
JOIN {group__subgroup_tree} t ON t.entity_id = r.entity_id
SET subgroup_right_value = (subgroup_right_value + 2)
WHERE r.subgroup_right_value >= 12125
AND t.subgroup_tree_value = 2
AND r.entity_id != 7237

I really would not know how to generate these queries using \Drupal\Core\Database\Query\Update, but they are more efficient than using WHERE entity_id IN $ids_to_update, with $ids_to_update possibly a large array of ids.

The essential parts of SubgroupHandlerBase.php after the latest patch:

  /**
   * Build update queries to update the left and right values of affected entities when a leaf is added or removed
   *
   * @param EntityInterface $entity
   *  if $action == LEAF_ADD: the parent of the leaf being added
   *  if $action == LEAF_REMOVE: the cache of the leaf being removed
   * @param string $action
   *  the action being taken, leaf added or leaf removed
   *
   * @return array of strings with the queries
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function buildValuesUpdateQueries(EntityInterface $entity, string $action) {
    $updates = array();
    $ids_to_update = array();

    switch ($action) {
      case self::LEAF_ADD:
        // Load the values directly from the database to avoid any caching issues when in a race condition
        $parentValues = $this->getLiveTreeValues($entity);
        $parent_id = $entity->id();
        $parent_right = $parentValues->right;
        $parent_tree = $parentValues->tree;

        /**
         * First we are going to update the left values of the affected entities, the aim of this is to
         * make sure we have enough space to grow the current parent.
         *
         * With this query we only want to update siblings (and their subgroups) to give us room to add a
         * new leaf (2 units) to the current parent (I.e. Update the parents right value by 2).
         *
         * To do this only increase the left value of entities whos left value is currently greater than the
         * right value of the parent.
         */

        // If the leaf is a direct path up (i.e.: its left bound was lower than
        // the parent's right value), then we only need to update the right bound.
        // Otherwise, we need to increment the left bound by 2 as well.
        $tablenames = $this->getTableNames(SUBGROUP_LEFT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {".$tablename."} l
          JOIN {group__subgroup_right} r ON r.entity_id = l.entity_id
          JOIN {group__subgroup_tree} t ON t.entity_id = l.entity_id
          SET subgroup_left_value = (subgroup_left_value + 2)
          WHERE l.subgroup_left_value > {$parent_right}
          AND r.subgroup_right_value >= {$parent_right}
          AND t.subgroup_tree_value = {$parent_tree}
          AND l.entity_id != {$parent_id}";
          $updates[] = $update;
        }

        /**
         * Then we need to update the right values. The aim of this is to make sure that sibling groups
         * (and their children) are still the same size as when we started the update, and that we grow
         * any parents of the current parent to accommodate the new leaf new are about to add.
         *
         * This is easy, we just need to update all the right values by 2 units
         */
        $tablenames = $this->getTableNames(SUBGROUP_RIGHT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {".$tablename."} r
          JOIN {group__subgroup_tree} t ON t.entity_id = r.entity_id
          SET subgroup_right_value = (subgroup_right_value + 2)
          WHERE r.subgroup_right_value >= {$parent_right}
          AND t.subgroup_tree_value = {$parent_tree}
          AND r.entity_id != {$parent_id}";
          $updates[] = $update;
        }

        break;

      case self::LEAF_REMOVE:
        // We have to use the values stored on the Entity object rather than going to the database when deleting groups
        // because by this point in the delete transaction the field values have already been removed from the database
        // The easiest way to do this is to use the leaf wrapper.
        $leaf = $this->wrapLeaf($entity);

        $leafValues = new stdClass();
        $leafValues->left = $leaf->getLeft();
        $leafValues->right = $leaf->getRight();
        $leafValues->depth = $leaf->getDepth();
        $leafValues->tree = $leaf->getTree();

        $leaf_right = $leafValues->right;
        $leaf_tree = $leafValues->tree;

        /**
         * First we are going to update the left values of the affected entities, the aim of this is to
         * make sure we shrink the tree to prepare for a removal of a leaf from the parent.
         *
         * With this query we only want to update siblings (and their subgroups) to shrink back 2 values each in
         * anticipation of removing a leaf (2 units) from the current parent (I.e. Decrease the parents right value by 2).
         *
         * To do this only decrease the left value of entities whos left value is currently greater than the
         * right value of the parent.
         */

        // If the leaf is a direct path up (i.e.: its left bound was lower than
        // the parent's right value), then we only need to update the right
        // bound. Otherwise, we need to decrease the left bound by 2 as well.
        $tablenames = $this->getTableNames(SUBGROUP_LEFT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {".$tablename."} l
          JOIN {group__subgroup_right} r ON r.entity_id = l.entity_id
          JOIN {group__subgroup_tree} t ON t.entity_id = l.entity_id
          SET subgroup_left_value = (subgroup_left_value - 2)
          WHERE l.subgroup_left_value > {$leaf_right}
          AND r.subgroup_right_value > {$leaf_right}
          AND t.subgroup_tree_value = {$leaf_tree}";
          $updates[] = $update;
        }

        /**
         * Then we need to update the right values. The aim of this is to make sure that sibling groups
         * (and their children) are still the same size as when we started the update, and that we shrink
         * any parents of the current parent to accommodate the removal of leaf.
         *
         * This is easy, we just need to decrease all the right values by 2 units
         */
        $tablenames = $this->getTableNames(SUBGROUP_RIGHT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {".$tablename."} r
          JOIN {group__subgroup_tree} t ON t.entity_id = r.entity_id
          SET subgroup_right_value = (subgroup_right_value - 2)
          WHERE r.subgroup_right_value > {$leaf_right}
          AND t.subgroup_tree_value = {$leaf_tree}";
          $updates[] = $update;
        }

        break;

      default:
        throw new InvalidArgumentException('Invalid query amend action supplied');
    }

    return $updates;
  }

  /**
   * {@inheritdoc}
   */
  public function addLeaf(EntityInterface $parent, EntityInterface $child) {
    $this->verify($parent);
    $this->verify($child);

    if (!$this->isLeaf($parent)) {
      throw new InvalidParentException('The entity to use as the parent is not a leaf.');
    }
    if ($child->isNew()) {
      throw new InvalidLeafException('Cannot use an unsaved entity as a leaf.');
    }
    if ($this->isLeaf($child)) {
      throw new InvalidLeafException('The entity to add as the leaf is already a leaf.');
    }

    $this->doAddLeaf($parent, $child);
  }

  /**
   * Actually adds a leaf to a tree.
   *
   * This is called after a few sanity checks and can be easily overwritten by
   * the extending classes.
   *
   * @param \Drupal\Core\Entity\EntityInterface $parent
   *   The entity to use as the parent.
   * @param \Drupal\Core\Entity\EntityInterface $child
   *   The entity to use as the new leaf.
   */
  protected function doAddLeaf(EntityInterface $parent, EntityInterface $child) {
    // This is a better implementation of the 60 second stuff
    if ($this->isLeaf($child)) {
      throw new InvalidLeafException('The provided entity is already a leaf, cannot add again.');
    }

    if ($this->groupTypeHandler->getParent($child->getGroupType())->id() !== $parent->bundle()) {
      throw new InvalidParentException('Provided group cannot be added as a leaf to the parent (incompatible group types).');
    }

    /**
     * If two subgroups are created/removed at the same time we run the risk of race conditions to update leaf values here
     * which can lead to invalid left and right values.
     *
     * To mitigate this we lock this process down so only one process can amend tree values at any given time
     */
    $blocked = TRUE;
    $logged = FALSE;
    do {
      // Try to obtain the tree lock, otherwise wait until it is free (Max 30 sec)
      if ($this->isTreeLockAvailable() && $this->getTreeLock()) {
        $blocked = FALSE;
      } else {
        if (!$logged) {
          \Drupal::logger('pipelyft_subgroup')->debug($this->t('Subgroup lock hit for parent: %id - %label. Child: %child_id - %child_label', [
            '%id' => $parent->id(),
            '%label' => $parent->label(),
            '%child_id' => $child->id(),
            '%child_label' => $child->label(),
          ]));
          $logged = TRUE;
        }
      }
    } while ($blocked);

    $transaction = NULL;
    try {
      // Load the values directly from the database to avoid any caching issues when in a race condition
      $parentValues = $this->getLiveTreeValues($parent);

      if (is_null($parentValues)) {
        throw new InvalidArgumentException('Supplied parent has no tree values.');
      }

      // Start a transaction to encompass the following update queries in-case we run into an error half-way
      // through and need to rollback
      $transaction = $this->database->startTransaction('subgroup_tree_update');

      /**
       * Find all the entities that we need to update: this is any entries that have the same or higher right value
       * than the parent, are part of the same tree and are not the parent themselves
       */
      $ids_to_update = $this->storage->getQuery()
        ->condition($this->getRightPropertyName(), $parentValues->right, '>=')
        ->condition($this->getTreePropertyName(), $parentValues->tree)
        // We deal with the passed in parent, rather than a freshly loaded copy so
        // that any code calling this method does not have an out of sync entity
        // for the rest of its runtime.
        ->condition($this->entityType->getKey('id'), $child->id(), '<>')
        ->accessCheck(FALSE)
        ->execute();

      if (!empty($ids_to_update)) {
        $updates = $this->buildValuesUpdateQueries($parent, self::LEAF_ADD);
        foreach ($updates as $update) {
          if (is_string($update)) \Drupal::database()->query($update);
          else $update->execute();
        }
        // All the affected entities need their memory cache entries cleared
        // (So they reflect the new tree values on their next load)
        $this->storage->resetCache($ids_to_update);
      }

      // Now that we have made room in the tree we can expand the parent
      $this->writeLeafData(
        $parent,
        $parentValues->depth,
        $parentValues->left,
        $parentValues->right + 2,
        $parentValues->tree
      );
      // Clear the memory cache of the parent
      // (So it reflects the new tree values on their next load by any user)
      $this->storage->resetCache(array($parent->id()));

      // And finally add the new leaf (Using the original right value to work out a 2 unit span)
      $this->writeLeafData(
        $child,
        $parentValues->depth + 1,
        $parentValues->right,
        $parentValues->right + 1,
        $parentValues->tree
      );
    } catch (Exception $e) {
      // If something goes wrong during the update, roll everything back and release the tree lock
      if ($transaction instanceof Transaction) {
        $transaction->rollBack();
      }
      $this->releaseTreeLock();

      throw $e;
    }

    // Once everything has run successfully, commit the transaction by unsetting it and release the tree lock
    unset($transaction);
    $this->releaseTreeLock();
  }

  /**
   * {@inheritdoc}
   */
  public function removeLeaf(EntityInterface $entity, $save = TRUE) {
    $this->verify($entity);

    if (!$this->isLeaf($entity)) {
      throw new InvalidLeafException('The entity to remove is not a leaf.');
    }
    if ($this->hasDescendants($entity)) {
      throw new InvalidLeafException('Cannot remove a leaf that still has descendants.');
    }

    $this->doRemoveLeaf($entity, $save);
  }

  /**
   * Actually removes a leaf from a tree.
   *
   * This is called after a few sanity checks and can be easily overwritten by
   * the extending classes.
   *
   * @param \Drupal\Core\Entity\EntityInterface $entity
   *   The entity to remove from the tree.
   * @param bool $save
   *   Whether the entity should be saved.
   */
  protected function doRemoveLeaf(EntityInterface $entity, $save) {
    /**
     * If two subgroups are created/removed at the same time we run the risk of race conditions to update leaf values here
     * which can lead to invalid left and right values.
     *
     * To mitigate this we lock this process down so only one process can amend tree values at any given time
     */
    $blocked = TRUE;
    do {
      // Try to obtain the tree lock, otherwise wait until it is free (Max 30 sec)
      if ($this->isTreeLockAvailable() && $this->getTreeLock()) {
        $blocked = FALSE;
      }
    } while ($blocked);

    $transaction = NULL;
    try {
      // We have to use the values stored on the Entity object rather than going to the database when deleting groups
      // because by this point in the delete transaction the field values have already been removed from the database
      // The easiest way to do this is to use the leaf wrapper.
      $leaf = $this->wrapLeaf($entity);

      $leafValues = new stdClass();
      $leafValues->left = $leaf->getLeft();
      $leafValues->right = $leaf->getRight();
      $leafValues->depth = $leaf->getDepth();
      $leafValues->tree = $leaf->getTree();

      // If the left and right values are 2 and 3 respectively it means we might
      // be removing the last child of a tree root. In this case, we unset the
      // tree altogether.
      if ($leafValues->left === 2 && $leafValues->right === 3 && $this->getDescendantCount($root = $this->storage->load($leafValues->tree)) === 1) {
        $this->clearLeafData($root, TRUE);
      }
      // Otherwise, we need to shrink the surrounding tree
      else {
        $ids_to_update = $this->storage->getQuery()
          ->condition($this->getRightPropertyName(), $leafValues->right, '>')
          ->condition($this->getTreePropertyName(), $leafValues->tree)
          ->accessCheck(FALSE)
          ->execute();

        if (!empty($ids_to_update)) {
          $transaction = $this->database->startTransaction('subgroup_tree_update');
          $updates = $this->buildValuesUpdateQueries($entity, self::LEAF_REMOVE);
          foreach ($updates as $update) {
            if (is_string($update)) \Drupal::database()->query($update);
            else $update->execute();
          }
          // All the affected entities need their memory cache entries cleared
          // (So they reflect the new tree values on their next load)
          $this->storage->resetCache($ids_to_update);
        }
      }

      // We can now remove the leaf from the tree
      $this->clearLeafData($entity, $save);

    } catch (Exception $e) {
      // If something goes wrong during the update, roll everything back and release the tree lock
      if ($transaction instanceof Transaction) {
        $transaction->rollBack();
      }
      $this->releaseTreeLock();

      throw $e;
    }

    // Once everything has run successfully, commit the transaction by unsetting it and release the tree lock
    unset($transaction);
    $this->releaseTreeLock();
  }

@lind101 Comment in your code:

// Try to obtain the tree lock, otherwise wait until it is free (Max 30 sec)

How are those 30 seconds implemented? I cannot find the code that limits the time available.

I have put #75 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed in production now. After a busy day on the site with #67 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed in place. 25 new groups, ids_to_update varying from 0 (a new subgroup) to 1030 (4 new subsubgroups to an older subgroup.

1.0.x: PHP 7.3 & MySQL 5.7, D9.5 Build Successful
PHP 8.1 & MySQL 5.7, D9.5.2 Build Successful

Tests of #75 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed were successful! I will address the coding standards later.

Testing the attached patch now. This patch should solve a lot of coding standards issues.

More coding standards fixed.

2 more coding standards issues fixed.

Essential part of SubgroupHandlerBase.php now:

   /**
   * Build update queries for left/right values when leaf is added or removed.
   *
   * @param \Drupal\Core\Entity\EntityInterface $entity
   *   ADD: parent of the added leaf, REMOVE: cache of the removed leaf.
   * @param string $action
   *   The action being taken, leaf added or leaf removed.
   *
   * @return array
   *   Array with SQL queries as string.
   *
   * @throws \Drupal\Core\Entity\Sql\SqlContentEntityStorageException
   */
  public function buildValuesUpdateQueries(EntityInterface $entity, string $action) {
    $updates = [];
    $ids_to_update = [];

    switch ($action) {
      case self::LEAF_ADD:
        // Load the values directly from the database to avoid any caching
        // issues when in a race condition.
        $parentValues = $this->getLiveTreeValues($entity);
        $parent_id = $entity->id();
        $parent_right = $parentValues->right;
        $parent_tree = $parentValues->tree;

        // First we are going to update the left values of the affected
        // entities, the aim of this is to make sure we have enough space
        // to grow the current parent.
        //
        // With this query we only want to update siblings (and their
        // subgroups) to give us room to add a new leaf (2 units) to the
        // current parent (i.e. Update the parents right value by 2).
        //
        // To do this only increase the left value of entities whos left value
        // is currently greater than the right value of the parent.
        //
        // If the leaf is a direct path up (i.e.: its left bound was lower than
        // the parent's right value), then we only need to update the right
        // bound. Otherwise, we need to increment the left bound by 2 as well.
        $tablenames = $this->getTableNames(SUBGROUP_LEFT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {" . $tablename . "} l
          JOIN {group__subgroup_right} r ON r.entity_id = l.entity_id
          JOIN {group__subgroup_tree} t ON t.entity_id = l.entity_id
          SET subgroup_left_value = (subgroup_left_value + 2)
          WHERE l.subgroup_left_value > {$parent_right}
          AND r.subgroup_right_value >= {$parent_right}
          AND t.subgroup_tree_value = {$parent_tree}
          AND l.entity_id != {$parent_id}";
          \Drupal::logger('writeLeafData')->notice("updateLeftQuery <pre>{$update}</pre>");
          $updates[] = $update;
        }

        // Then we need to update the right values. The aim of this is to make
        // sure that sibling groups (and their children) are still the same
        // size as when we started the update, and that we grow any parents of
        // the current parent to accommodate the new leaf new are about to add.
        //
        // This is easy, we just need to update all right values by 2 units.
        $tablenames = $this->getTableNames(SUBGROUP_RIGHT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {" . $tablename . "} r
          JOIN {group__subgroup_tree} t ON t.entity_id = r.entity_id
          SET subgroup_right_value = (subgroup_right_value + 2)
          WHERE r.subgroup_right_value >= {$parent_right}
          AND t.subgroup_tree_value = {$parent_tree}
          AND r.entity_id != {$parent_id}";
          \Drupal::logger('writeLeafData')->notice("updateRightQuery <pre>{$update}</pre>");
          $updates[] = $update;
        }

        break;

      case self::LEAF_REMOVE:
        // We have to use the values stored on the Entity object rather than
        // going to the database when deleting groups because by this point in
        // the delete transaction the field values have already been removed
        // from the database.
        // The easiest way to do this is to use the leaf wrapper.
        $leaf = $this->wrapLeaf($entity);

        $leafValues = new stdClass();
        $leafValues->left = $leaf->getLeft();
        $leafValues->right = $leaf->getRight();
        $leafValues->depth = $leaf->getDepth();
        $leafValues->tree = $leaf->getTree();

        $leaf_right = $leafValues->right;
        $leaf_tree = $leafValues->tree;

        // First we are going to update the left values of the affected
        // entities, the aim of this is to make sure we shrink the tree to
        // prepare for a removal of a leaf from the parent.
        //
        // With this query we only want to update siblings (and their
        // subgroups) to shrink back 2 values each in anticipation of
        // removing a leaf (2 units) from the current parent (i.e. decrease
        // the parents right value by 2).
        //
        // To do this only decrease the left value of entities whos left value
        // is currently greater than the right value of the parent.
        //
        // If the leaf is a direct path up (i.e.: its left bound was lower than
        // the parent's right value), then we only need to update the right
        // bound. Otherwise, we need to decrease the left bound by 2 as well.
        $tablenames = $this->getTableNames(SUBGROUP_LEFT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {" . $tablename . "} l
          JOIN {group__subgroup_right} r ON r.entity_id = l.entity_id
          JOIN {group__subgroup_tree} t ON t.entity_id = l.entity_id
          SET subgroup_left_value = (subgroup_left_value - 2)
          WHERE l.subgroup_left_value > {$leaf_right}
          AND r.subgroup_right_value > {$leaf_right}
          AND t.subgroup_tree_value = {$leaf_tree}";
          \Drupal::logger('writeLeafData')->notice("updateLeftQuery <pre>{$update}</pre>");
          $updates[] = $update;
        }

        // Then we need to update the right values. The aim of this is to make
        // sure that sibling groups (and their children) are still the same
        // size as when we started the update, and that we shrink any parents
        // of the current parent to accommodate the removal of leaf.
        //
        // This is easy, we just need to decrease all right values by 2 units.
        $tablenames = $this->getTableNames(SUBGROUP_RIGHT_FIELD);
        foreach ($tablenames as $tablename) {
          $update = "
          UPDATE {" . $tablename . "} r
          JOIN {group__subgroup_tree} t ON t.entity_id = r.entity_id
          SET subgroup_right_value = (subgroup_right_value - 2)
          WHERE r.subgroup_right_value > {$leaf_right}
          AND t.subgroup_tree_value = {$leaf_tree}";
          \Drupal::logger('writeLeafData')->notice("updateRightQuery <pre>{$update}</pre>");
          $updates[] = $update;
        }

        break;

      default:
        throw new InvalidArgumentException('Invalid query amend action supplied');
    }

    return $updates;
  }

  /**
   * {@inheritdoc}
   */
  public function addLeaf(EntityInterface $parent, EntityInterface $child) {
    $this->verify($parent);
    $this->verify($child);

    if (!$this->isLeaf($parent)) {
      throw new InvalidParentException('The entity to use as the parent is not a leaf.');
    }
    if ($child->isNew()) {
      throw new InvalidLeafException('Cannot use an unsaved entity as a leaf.');
    }
    if ($this->isLeaf($child)) {
      throw new InvalidLeafException('The entity to add as the leaf is already a leaf.');
    }

    $this->doAddLeaf($parent, $child);
  }

  /**
   * Actually adds a leaf to a tree.
   *
   * This is called after a few sanity checks and can be easily overwritten by
   * the extending classes.
   *
   * @param \Drupal\Core\Entity\EntityInterface $parent
   *   The entity to use as the parent.
   * @param \Drupal\Core\Entity\EntityInterface $child
   *   The entity to use as the new leaf.
   */
  protected function doAddLeaf(EntityInterface $parent, EntityInterface $child) {
    $parent_leaf = $this->wrapLeaf($parent);
    $parent_tree = $parent_leaf->getTree();
    $parent_left = $parent_leaf->getLeft();
    $parent_right = $parent_leaf->getRight();
    $parent_id = $parent->id();
    $parent_revision_id = $parent->getRevisionId();
    $connection = \Drupal\Core\Database\Database::getConnection();
    $dbquery = "SELECT subgroup_left_value FROM {group__subgroup_left} WHERE entity_id = {$parent_id} AND revision_id = {$parent_revision_id}";
    $query = \Drupal::database()->query($dbquery);
    $results = $query->fetchAll();
    foreach ($results as $result) {
      $parent_left = $result->subgroup_left_value;
    }
    $dbquery = "SELECT subgroup_right_value FROM {group__subgroup_right} WHERE entity_id = {$parent_id} AND revision_id = {$parent_revision_id}";
    $query = \Drupal::database()->query($dbquery);
    $results = $query->fetchAll();
    foreach ($results as $result) {
      $parent_right = $result->subgroup_right_value;
    }
    \Drupal::logger('writeLeafData')->notice("parent = ".$parent_leaf->getLeft()." => {$parent_left}, ".$parent_leaf->getRight()." => {$parent_right}");
    // This is a better implementation of the 60 second stuff.
    if ($this->isLeaf($child)) {
      throw new InvalidLeafException('The provided entity is already a leaf, cannot add again.');
    }

    if ($this->groupTypeHandler->getParent($child->getGroupType())->id() !== $parent->bundle()) {
      throw new InvalidParentException('Provided group cannot be added as a leaf to the parent (incompatible group types).');
    }

    // If two subgroups are created/removed at the same time we run the risk of
    // race conditions to update leaf values here which can lead to invalid
    // left and right values.
    //
    // To mitigate this we lock this process down so only one process can amend
    // tree values at any given time.
    $blocked = TRUE;
    $logged = FALSE;
    do {
      // Try to obtain the tree lock, otherwise wait until it is free
      // (max 30 sec).
      if ($this->isTreeLockAvailable() && $this->getTreeLock()) {
        $blocked = FALSE;
      }
      else {
        if (!$logged) {
          \Drupal::logger('pipelyft_subgroup')->debug($this->t('Subgroup lock hit for parent: %id - %label. Child: %child_id - %child_label', [
            '%id' => $parent->id(),
            '%label' => $parent->label(),
            '%child_id' => $child->id(),
            '%child_label' => $child->label(),
          ]));
          $logged = TRUE;
        }
      }
    } while ($blocked);

    $transaction = NULL;
    try {
      // Load the values directly from the database to avoid any caching issues
      // when in a race condition.
      $parentValues = $this->getLiveTreeValues($parent);

      if (is_null($parentValues)) {
        throw new InvalidArgumentException('Supplied parent has no tree values.');
      }

      // Start a transaction to encompass the following update queries in-case
      // we run into an error half-way through and need to rollback.
      $transaction = $this->database->startTransaction('subgroup_tree_update');

      // Find all the entities that we need to update: this is any entries that
      // have the same or higher right value than the parent, are part of the
      // same tree and are not the parent themselves.
      $ids_to_update = $this->storage->getQuery()
        ->condition($this->getRightPropertyName(), $parentValues->right, '>=')
        ->condition($this->getTreePropertyName(), $parentValues->tree)
        // We deal with the passed in parent, rather than a freshly loaded copy
        // so that any code calling this method does not have an out of sync
        // entity for the rest of its runtime.
        ->condition($this->entityType->getKey('id'), $child->id(), '<>')
        ->accessCheck(FALSE)
        ->execute();
      \Drupal::logger('writeLeafData')->notice("add leaf ".$child->id().", ids_to_update ".count($ids_to_update));

      if (!empty($ids_to_update)) {
        $updates = $this->buildValuesUpdateQueries($parent, self::LEAF_ADD);
        foreach ($updates as $update) {
          \Drupal::database()->query($update);
        }
        // All the affected entities need their memory cache entries cleared
        // (so they reflect the new tree values on their next load).
        $this->storage->resetCache($ids_to_update);
      }

      // Now that we have made room in the tree we can expand the parent.
      $this->writeLeafData(
        $parent,
        $parentValues->depth,
        $parentValues->left,
        $parentValues->right + 2,
        $parentValues->tree
      );
      // Clear the memory cache of the parent.
      // (So it reflects the new tree values on their next load by any user).
      $parent_id_array[] = $parent->id();
      $this->storage->resetCache($parent_id_array);

      // And finally add the new leaf (Using the original right value to work
      // out a 2 unit span).
      $this->writeLeafData(
        $child,
        $parentValues->depth + 1,
        $parentValues->right,
        $parentValues->right + 1,
        $parentValues->tree
      );
    }
    catch (\Exception $e) {
      // If something goes wrong during the update,
      // roll everything back and release the tree lock.
      if ($transaction instanceof Transaction) {
        $transaction->rollBack();
      }
      $this->releaseTreeLock();

      throw $e;
    }

    // Once everything has run successfully, commit the transaction by
    // unsetting it and release the tree lock.
    unset($transaction);
    $this->releaseTreeLock();
  }

  /**
   * {@inheritdoc}
   */
  public function removeLeaf(EntityInterface $entity, $save = TRUE) {
    $this->verify($entity);

    if (!$this->isLeaf($entity)) {
      throw new InvalidLeafException('The entity to remove is not a leaf.');
    }
    if ($this->hasDescendants($entity)) {
      throw new InvalidLeafException('Cannot remove a leaf that still has descendants.');
    }

    $this->doRemoveLeaf($entity, $save);
  }

  /**
   * Actually removes a leaf from a tree.
   *
   * This is called after a few sanity checks and can be easily overwritten by
   * the extending classes.
   *
   * @param \Drupal\Core\Entity\EntityInterface $entity
   *   The entity to remove from the tree.
   * @param bool $save
   *   Whether the entity should be saved.
   */
  protected function doRemoveLeaf(EntityInterface $entity, $save) {
    // If two subgroups are created/removed at the same time we run the risk of
    // race conditions to update leaf values here which can lead to invalid
    // left and right values.
    //
    // To mitigate this we lock this process down so only one process can amend
    // tree values at any given time.
    $blocked = TRUE;
    do {
      // Try to obtain the tree lock, otherwise wait until it is free
      // (max 30 sec).
      if ($this->isTreeLockAvailable() && $this->getTreeLock()) {
        $blocked = FALSE;
      }
    } while ($blocked);

    $transaction = NULL;
    try {
      // We have to use the values stored on the Entity object rather than
      // going to the database when deleting groups because by this point in
      // the delete transaction the field values have already been removed
      // from the database.
      // The easiest way to do this is to use the leaf wrapper.
      $leaf = $this->wrapLeaf($entity);

      $leafValues = new stdClass();
      $leafValues->left = $leaf->getLeft();
      $leafValues->right = $leaf->getRight();
      $leafValues->depth = $leaf->getDepth();
      $leafValues->tree = $leaf->getTree();

      // If the left and right values are 2 and 3 respectively it means we might
      // be removing the last child of a tree root. In this case, we unset the
      // tree altogether.
      if ($leafValues->left === 2 && $leafValues->right === 3 && $this->getDescendantCount($root = $this->storage->load($leafValues->tree)) === 1) {
        $this->clearLeafData($root, TRUE);
      }
      // Otherwise, we need to shrink the surrounding tree.
      else {
        $ids_to_update = $this->storage->getQuery()
          ->condition($this->getRightPropertyName(), $leafValues->right, '>')
          ->condition($this->getTreePropertyName(), $leafValues->tree)
          ->accessCheck(FALSE)
          ->execute();
        \Drupal::logger('writeLeafData')->notice("remove leaf ".$entity->id().", ids_to_update ".count($ids_to_update));

        if (!empty($ids_to_update)) {
          $transaction = $this->database->startTransaction('subgroup_tree_update');
          $updates = $this->buildValuesUpdateQueries($entity, self::LEAF_REMOVE);
          foreach ($updates as $update) {
            \Drupal::database()->query($update);
          }
          // All the affected entities need their memory cache entries cleared
          // (so they reflect the new tree values on their next load).
          $this->storage->resetCache($ids_to_update);
        }
      }

      // We can now remove the leaf from the tree.
      $this->clearLeafData($entity, $save);

    }
    catch (Exception $e) {
      // If something goes wrong during the update, roll everything back and
      // release the tree lock.
      if ($transaction instanceof Transaction) {
        $transaction->rollBack();
      }
      $this->releaseTreeLock();

      throw $e;
    }

    // Once everything has run successfully, commit the transaction by
    // unsetting it and release the tree lock.
    unset($transaction);
    $this->releaseTreeLock();
  }

#82 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed Is in production now, with some additional logging (not included in the patch).

getLiveTreeValues() gave me the idea how to drupalize the drirect queries. Another patch will follow.

Simplify the queries. There is no need to check for both the left and the right value > some right value, because the left value is always smaller than the right value.

Todo: update the issue summary.

Spelling, coding standards

Remaining Coding standards issues

Coding standards for using "native" PHP classes like stdClass
https://www.drupal.org/project/drupal/issues/1614186#comment-6475044 →
Classes and interfaces without a backslash \ inside their fully-qualified
name (for example, the built-in PHP Exception class) must be fully
qualified when used in a namespaced file: for example \Exception.

The patch in #90 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed Is running in production for a week now. No issues detected.

The comments in the patch might need an update, depending on the fix for Leaf lifetime exceeds 60s in large migrations 📌 Leaf lifetime exceeds 60s in large migrations Fixed .

Excellent, thanks for that. Will look into this as soon as Group has new stable releases. We're at release candidates already now so hopefully it won't be much longer.

Nice work Jan-E, thanks for improving that code and patchifiying it.

+        if (!$logged) {
+          \Drupal::logger('pipelyft_subgroup')->debug($this->t('Subgroup lock hit for parent: %id - %label. Child: %child_id - %child_label', [
+            '%id' => $parent->id(),
+            '%label' => $parent->label(),
+            '%child_id' => $child->id(),
+            '%child_label' => $child->label(),
+          ]));
+          $logged = TRUE;
+        }

Just a quick note, you might what remove this bit as it's got specific logging references to the project that I'm working on. Apologies I must have missed that when I posted the initial code.

I was already wondering what the logging was meant to do. I will remove it and upload a new patch.

Or rather I was wondering what 'pipelyft' was doing there. Logging a lock hit would not be a bad idea. Anyway, I have removed it now. New patch attached. I will update the contents of #83 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed with the latest code after the patch.

Corrected 2 typos: "entities whose left value".

This patch has been in production for 5 weeks now. No issues detected at all. In the mean time the system has grown to

• 9 projects (groups)
• 945 cases (subgroups) below the projects
• 6570 sessions (subsubgroups) below the cases
• 5477 group content nodes, mostly related to a subsubgroup

This should clean things up a bit.

Thanks. i will review that later this week and report back.

Are you considering a mitigation against a fatal error after storing a new group in the database, but before the leaf values are updated? So we can avoid things like #35 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed . That would require starting a transaction before adding the group. You were considering adding a flag for “Created during this request” in https://www.drupal.org/project/subgroup/issues/3163044#comment-14912931 📌 Leaf lifetime exceeds 60s in large migrations Fixed Could that be the start of a transaction in stead of adding a flag?

This patch was created against the 3.x branch, my bad.

Also naming things correctly might help.

The last submitted patch, 103: subgroup-3281672-103.patch, failed testing. View results →
- codesniffer_fixes.patch Interdiff of automated coding standards fixes only.

Glad to see you are working on porting the patch to 3.0.x-dev. As a BTW: the 3.0.x-dev patch introduced 7 new coding standard messages, which should be avoided.

Re #101 I'm thinking of doing away with that assert altogether.

One the one hand, it's just a completely harmless assert. On the other hand, it makes no sense. The permissions do not allow to add existing groups as subgroups so maybe just stick with that and if someone does do it through code, that's their fault (or intent).

Not sure if I can help with the core issue.

Seeing some significant fails, do not use the patch yet.

New query approach led to stale entities, this should fix it.

You might be right about removing the 60 seconds assert. While doing my initial import of 6000+ groups I temporarily removed it. During the importing process I also ran a couple of times into the core issue, even while running it with a single user. Never happened again after the one reported in this issue. Fingers crossed.

The last submitted patch, 108: subgroup-3281672-108.patch, failed testing. View results →
- codesniffer_fixes.patch Interdiff of automated coding standards fixes only.

I jumped the gun a bit... also incremented left value like an idiot :D

Did I see it right that you do not update the direct parent anymore on adding a leaf, but only update the right value? My users are getting used to the fact that a case (subgroup) gets an updated timestamp when a new session (subsubgroup) is added to that case. Also comes in handy on views with only subgroups. If so, I will have to add it to my own module.

Yeah, I update as much using queries now because the whole reason we're changing this code is performance reasons. If you want to keep the updating of timestamps you'll need to trigger a save yourself indeed.

Fixing coding standards issues

Fixing coding standards issues - take 2

I have put this patch for subgroup version 1.0.2 in production now. The patch is almost identical as the one for subgroup 3.0.x-dev. My own tests all were successful.

The patch in #115 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed applies unchanged to subgroup 2.0.x-dev as well. Tests pass. I do not have a site with subgroup 2.0.x, but am quite confident that it will fix the issue for that version as well.

The patch in #116 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed is in production now for a couple of days. No flaws at all.

I wanted to update the parent subgroup (case) when a new subsubgroup (session) was added and used hook_ENTITY_TYPE_insert() to achieve that:

/**
 * Implements hook_ENTITY_TYPE_insert().
 */
function pcs_module_group_insert(GroupInterface $group) {
  if ($group instanceof GroupInterface) {
    $parent_id = 0;
    $group_type = $group->bundle();
    $group_id = $group->id();
    if ($group_type == 'session') {
      $parent_id = 0;
      // add:  /group/76/content/create/subgroup:session
      // Retrieve an array which contains the path pieces.
      $current_path = \Drupal::service('path.current')->getPath();
      $path_args = explode('/', $current_path);
      if (isset($path_args[2]) && intval($path_args[2])) $parent_id = intval($path_args[2]);
    }
    if ($parent_id) {
      $parent = \Drupal\group\Entity\Group::load($parent_id);
      $parent->changed = time();
      $parent->save();
    }
  }
}

Please be aware that hook_group_insert() is called before the addition of the tree values to the new group. Be really sure that you do not cause PHP errors in that piece of code. Otherwise you will end up with a subgroup that was born as an orphan.

There is not anything of a real community here, but I am changing the status to RTBC anyway.

Thanks for the work and the super patch, I myself still use Group 1.x & Subgroup 1.x, Drupal 9.5.x, PHP 8.1. with me in the system are about 9000 Groups and 9500 Subgroups. The patch in #116 applied successfully and without error. How can I see if everything is ok with the patch and what exactly does it do? Can I measure this somehow so that my tests are more successful?

The real difference is being made if you have groups with multiple subgroups. There must be some in your system because you have 9500 subgroups and 'only' 9000 groups. Try this as a test:

• Create a new group
• Add a lot (say 20) subgroups under that new group
• Delete the 1st subgroup under the new group

Without the patch subgroup will cycle to all newer subgroups and save them one by one. If you do not have one yet, Create a view with the 'Changed on'

Changed on	Group	The time that the group was last edited.

You will notice that newer subgroups will seem 'edited' after removal of the first one.

With the patch the tree values (left and right) of all the newer groups and of the parent group will be updated with a direct query to the database. No more cycling through all newer subgroups.

In my case I have got only 9 groups. One of those 9 groups has in total 6360 subgroups If I remove one of the first subgroups it will take more than 3 minutes to cycle through all the affected subgroups. With the patch the update is done in about 0.4 seconds.

Great, thanks for the explanation. Then I like to test it locally in my project, but sounds like a super performance patch for subgroups :)

The core issue in #35 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed is still getting updates. When I followed the links to the related issues I noticed https://www.drupal.org/project/drupal/issues/2347867#comment-14606651 🐛 Race conditions with lock/cache using non-database storage - add a non-transactional database connection Needs work . Which included the phrase:

I believe #44 is correct: cache operations should not happen inside a transaction.

This made me think. Is there a real reason to put the resetCache($ids_to_update) inside the transaction? No, there seems to be no reason. All statements for the resetCache should be in between the acquireLock() and releaseLock(), but not inside the transaction. It might even be preferable to have the resetCache after the transaction, so resetCache($ids_to_update) will be even be executed when the transaction fails.

New patches attached. I will put the status back again to 'Needs review' until the modified patch is tested for some time on my production server.

The odd thing is that every patch since #111 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed still contains the old (and buggy) code for doAddlLeaf() and doRemoveLeaf() in SubgroupHandlerBase.php. A brief excerpt of classes and functions follows below.

SubgroupHandlerBase.php
abstract class SubgroupHandlerBase extends EntityHandlerBase implements SubgroupHandlerInterface { ... }
contains old doAddlLeaf() and doRemoveLeaf() and
abstract protected function writeLeafData(EntityInterface $entity, $depth, $left, $right, $tree);

GroupSubgroupHandler.php
class GroupSubgroupHandler extends SubgroupHandlerBase { ... }
contains new doAddlLeaf() and doRemoveLeaf()

GroupTypeSubgroupHandler.php
class GroupTypeSubgroupHandler extends SubgroupHandlerBase { ... } contains
protected function writeLeafData(EntityInterface $entity, $depth, $left, $right, $tree) { ... }

@kristiaanvandeneynde Should not doAddlLeaf() and doRemoveLeaf() in SubgroupHandlerBase.php be abstract protected functions, just like writeLeafData()?

@kristiaanvandeneynde Should not doAddlLeaf() and doRemoveLeaf() in SubgroupHandlerBase.php be abstract protected functions, just like writeLeafData()?

New patches with abstract functions in SubgroupHandlerBase.php. Tested in production for some time now.

I do not know (yet) why the tests in #125 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed fail. The tests with the patches in #123 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed still pass. Also note that the patches in #135 have a coding standard issue (line too long).

Removing the old code for doAddlLeaf() and doRemoveLeaf() in SubgroupHandlerBase.php stikk needs some work.

Trying to solve the test failure and the coding standards issue.

Tests should never test the base class unless they are specifically named as such. We have separate tests for Group and GroupType handlers. GroupType entities cannot be updated using queries as config entities aren't stored in normalized database tables. So we really need to keep both versions of the code.

Ok, then the patches at #123 🐛 doAddLeaf & doRemoveLeaf: timestamp bug and scalability Fixed are the final ones.

Okay, looking good.

Nice work guys! 👍

Automatically closed - issue fixed for 2 weeks with no activity.

I had some budget left from a Subgroup D10 support sponsorship, so I committed the 1.x fix.