Pulp

mhrivnak wrote:

We can add an extra field to the model that is a unique ID, in addition to the PK, and use that as the “to_field” on the ForeignKey field. Let’s call it “willing_parent_id” to signify that a node is willing to be a parent if the field is populated. If that field is null, we are guaranteed that there are no children. That’s half the battle.

The second half is enforcing that either “willing_parent_id” or “distribution” must be null. We can do that at the DB level using the “constraints” feature of our relational database. Django doesn’t fully expose that, but we can use the technique described here:

How is willing_parent_id managed?

There is a design that was suggested in #postgresql that I wanted to at least share. It doesn't use constraints so that is not as great, but it is easy to maintain and should be pretty fast because the foreign keys can all be indexed.

class DistributionPath(models.Model):
    path_segment = models.CharField()
    parent = models.ForeignKey('self', null=True, to_field='id')
    distribution = models.ForeignKey(Distribution, null=True)

Then you would run it by searching through the tree to see if there is one that you cannot find one that corresponds with your path segment so far. If you can't find one then it's safe to add. If you get to the end of the segments and you found one all along the way it is not safe to add.

segments = ['a', 'b', 'c']  # this is /a/b/c/
qs = DistributionPath.objects
for index, segment in enumerate(segments):
    try:
        node = qs.get(path_segment=segment)
    except DoesNotExist:
        break  # We know this path is safe
    else:
        qs = DistributionPath.objects.filter(parent=node)
        if index == len(segments):
            raise Exception('this path is not safe')

Adding a Distribution causes these records to be added, probably along with the search. Removing is a similar process. All of this should happen in one table-level transaction which should make this race condition free. This would linearize concurrent distribution additions/removals at the db level.

This kind of a structure could also provide a more efficient lookup of the base paths probably also. That is the purpose of the 'distribution' foreign key.

Added checklist item to remove warning from https://pulp.plan.io/issues/3448

I wanted to write an idea for an algorithmic solution here. It would use a model like this one (totally untested):

class BasePath(Model):
    parent_path = ForeignKey('BasePath', null=True, backref='subpaths')
    distribution = ForeignKey('Distribution', null=True)
    subpath = CharField(max_length=128)
    distribution_count = IntegerField(default=1)

Then have an algorithm similar to this loose code:

def add_path(path, distribution):
    """
    Takes the path as a string and the models.Distribution instance this path is for.
    """
    list_of_path_subcomponents = os.split(os.sep, path)
    # start db transaction
    parent = None
    for i, subpath in enumerate(list_of_path_subcomponents):
        try:
            parent = BasePath.objects.filter(parent=parent, subpath=subpath).get()
        except DoesNotExist:
            distribution_kwargs = {}
            if i == len(list_of_path_subcomponents) - 1:
                # The next BasePath needs to have the Distribution set so that the data model is correct
                distribution_kwargs['distribution'] = distribution
            parent = BasePath.objects.create(parent=parent, subpath=subpath, **distribution_kwargs)
        continue:
            if parent.distribution != None:
                # This path is already in use by a distribution so raise an exception
                raise Exception('The path overlaps! Revert all changes by raising an exception')
            if i == len(list_of_path_subcomponents) - 1:
                # This is expected to be the distribution for this path, but it's already in use. Raise an exception
                raise Exception('The path overlaps! Revert all changes by raising an exception')
            parent.distribution_count = parent.distribution_count + 1
            parent.save()
    # commit db transaction

def remove_path(path):
    """
    Takes the path as a string to be removed
    """
    list_of_path_subcomponents = os.split(os.sep, path)
    # start db transaction
    parent = None
    for i, subpath in enumerate(list_of_path_subcomponents):
        parent = BasePath.objects.filter(parent=parent, subpath=subpath).get()
        if parent.distribution_count == 1:
           parent.delete()
           parent = None  # This causes the next loop to find those entries whose ForeignKeys were set to None when the delete() ran above
        else:
            parent.distribution_count = parent.distribution_count - 1
            parent.distribution_count.save()
    # commit db transaction

The idea is that this would run quickly due to the indexed foreign keys that Django will create. It really restricts the number of records searched at each level of the search. I don't see how we can not search each level for overlap independently so searching efficiently level-by-level is as good as we can do.

Also the transactions make adding easy because you can modify records until you find a problem and then bail with an exception, and the record writes are all ignored which is what you want. Similarly for removing a base path. Say you have a path that is partially right in the first parts, but not accurate in the later parts. You can start removing it in the transaction, and then when you later learn it's invalid you can bail with the exception.

The transaction also ensures safety even with concurrency. In practice I think these transactions will be held for a very small amount of time.

I'm thinking this would not be used by the content app, but would allow us to facilitate this requirement using the database and the algorithm. I'm not sure what the content app looks like currently in terms of how it resolves the base_path and how this is similar (or not) to that.

Another option is to use the tasking system. Currently tasks lock on the 'resource' field[0] which is just a string (e.g. /api/v3/distributions/abc123/). The reservation system relies on the uniqueness constraint of this field to prevent two tasks from reserving the same resource. We could lock on all distributions by using /api/v3/distributions/ when we create/update distributions. We would have to be careful though not to lock on individual distributions in other places in the code.

[0] https://git.io/vpIEq

I really hope that we don't do a task lock for distribution updates.

One of the big values for the current non-locking distribution update design was that "promotion" would be instant. IMO, this feature is really important, it might even outweigh the relatively unlikely race condition.

To elaborate, I'll tell a user story.

The user has a "testing" and "production" distribution, and "testing" is currently serving a newer publication than "production". The tests all pass, and they set "production" to distribute the newer publication. Unfortunately, their tests missed something, and they need to roll back. The situation is made even worse, Pulp is currently doing the regular syncs of many repositories at once and all the workers are busy.

Either:
The user makes a synchronous call, rolling back "production" to the old publication. Solved! The admin can go home.
of
The user makes an asynchronous call, but it is low on the task queue. "production" is still serving the incorrect content until the task queue dies down, so the user cancels all the current tasks out of desperation. The distribution is updated, whew! Then the user queues up all the tasks they canceled and goes home.

@asmacdo, I mention the task option because it requires very little change to our code today—perhaps only a few lines. All these other solutions are complex and require db changes that can be hard to grok. A synchronous call to updating base_path on distribution is better for users for sure.