Plan Collaboration

[mattdailis]

@Mythicaeda and I have spent some time on our own trying to define what plan collaboration will look like in Aerie, and we'd like to open that discussion up to the community. Below, you'll find our working understanding of what duplicating and merging a plan may look like.

Plan Collaboration Specification

This specification lays out the semantics of plan collaboration. It
tries to focus on observable properties without overly constraining
the implementation. It describes the system behaving as if it were
implemented a certain way, but tries to leave room for alternative
representations and optimizations.

Importantly, this specification is focused on user workflows, and does not
take into consideration tradeoffs associated with implementation efficiency
or performance.

Primary Goals:

• To enable many users to collaborate on a plan.
  • Allow a user to make a copy of the plan and make their own
    edits without seeing other people's edits
  • Users can apply their edits to the original plan when they are ready

Secondary Goals:

• Allow users to work on a subset of the plan

Non-goals:

• Real time collaboration on the same plan - this is enabled by other Aerie features, and does not need special consideration in this specification
• Plan snapshots for simulation
• Undo
• Merging a portion of a plan

First off, we have the following entities:

• An activity version is a tuple of (activity id, type, start time, args)
• An activity is just an id - multiple activity versions can refer
  to the same activity id.
• A plan is a set of activity versions, as well as a start and end
  time. This set may not contain two activity versions with the same
  activity id.
• A plan comparison point represents an immutable version of a plan
  at some point in time. The only operation it is required to support
  is producing a changeset with a current version of a descendant
  plan.
• An merge request is a request to incorporate changes from one plan
  (referred to as the plan providing changes) into another, related plan
  (referred to as the plan receiving changes). A merge request can be:
  • "in progress", in which case no changes have been applied and the merge request is being iterated on
  • "committed", in which case the changes have been applied and this merge request is immutable
  • "aborted", in which case no changes have been applied and this merge request is immutable

We define the following vocabulary, to be used in defining our operations.

• A plan comparison point is in the history of a plan if
  • either it was created when the plan was created via duplicate
  • or it was in the parent plan's history when this plan was duplicated
  • or it was created when this plan provided changes to another plan
  • or it was created when this plan received changes from another plan
  • or it was in the history of the other plan when the other plan provided changes to this plan

We say that a plan comparison point is in the history of another plan
comparison point if the former was in the history of the plan when the
latter was created.

• Two plans are related if the intersection of their histories is not empty.
• A plan comparison point C is a common comparison point of two plans, A and B, if C is in the intersection of the histories of A and B.
• One common comparison point is better than another if the latter is in the history of the former
• A common comparison point that does not have any better common ancestor is a best common comparison point, i.e. a merge base
• A changeset of a plan with respect to a merge base is a partitioning of its activities into one of the following categories:
  • Unchanged
  • Added
  • Modified
  • Deleted
• A change of a plan with respect to a merge base is an activity that would be categorized as "Modified" or "Deleted".
• Two changes form a conflict if they refer to the same activity, and if
  • either one change is a Deletion, while the other is a Modification
  • or both changes are Modifications, and either the start time or the arguments do not match exactly.
• A decision is a choice by the user to resolve a conflict. That decision can be
  • either choosing one of the two activity versions
  • or choosing the version from the plan receiving changes and modifying it by hand (this could be done after the merge is committed, but it may be nice to do it directly as part of the conflict resolution)

A compliant implementation must support the following operations:

create_fresh_plan()

A new plan can be created. This plan will have a fresh id, and contain no activities.

create_activity(plan_id, type, start_time, args)

An activity version can be added to a plan.

update_activity(plan_id, activity_id, start_time, args)

An activity version in a plan can be replaced with another activity version with the same activity id

delete_activity(plan_id, activity_id)

An activity can be removed from a plan.

duplicate_plan(plan_id)

Duplicating a plan creates a new plan, with a fresh id, that contains the same activity versions as the original plan. Duplicating a plan also creates a plan comparison point that will be in the history of both the child and the parent plan.

create_merge_request(plan providing changes, plan receiving changes)

Creating a merge request involves the following steps:

1. A plan comparison point must be created that reflects the
   contents of the plan providing changes. In the event that this
   merge request is committed, this plan comparison point will be in
   the history of both plans going forward
2. Choose a plan comparison point to serve as the merge base, from among the best common comparison points of the two plans. If no such common comparison point exists (i.e. the plans are unrelated), the request should fail to be created.
3. Identify the changeset of the plan providing changes with respect to the merge base
4. Create a "merge request" that contains, at a minimum:
   - the id of the plan receiving changes
   - the id of the plan providing changes
   - the changeset of the plan providing changes
   - an uninitialized set of conflicts
   - an empty set of decisions
   - a status: "in progress"

initiate_merge(plan_id_a, plan_id_b)

Merging plan B (plan providing changes) into plan A (plan receiving changes) follows the following steps:

1. Lock the plan receiving changes from further modification
2. Identify the changesets of plans A and B with respect to the merge base.
3. Identify conflicts between the changesets.
4. Set the "merge request" state to "in progress", and populate the set of conflicts
5. Create a staging plan. This staging plan, which is a copy of the plan receiving changes, contains all of the same things as the original plan, but it does not allow for modifications to be made aside from those that come from resolving conflicts. Importantly, it must allow running constraints, in order to help determine the validity of the merge.

resolve_conflict(merge request id, decision)

Resolving a conflict updates the given merge request with the decision made. It also updates the staging plan to reflect this decision.

abort_merge(merge request id)

Aborting a merge request marks that merge request as aborted, deletes the staging plan, and unlocks the plan receiving changes.

commit_merge(merge request id)

When a merge request is committed, the plan receiving changes is updated to contain:
- All activities that were unique to the plan receiving changes
- All non-conflicting changes from the plan providing changes
- All decisions from this merge request

The staging plan can be deleted, and the plan receiving changes can be unlocked.

delete_plan(plan_id) Deleting a plan does not delete its plan comparison points unless they can never be used in a future merge (see Garbage collecting section below)

Locking plans:

When there is an in-progress merge, no modifications are permitted
to either of the two plans involved in the merge. (Although it could
be possible to allow changes to the plan
being merged).

"Practice" merges:

It may be desirable to initiate a merge without locking both plans,
since that may be disruptive.

Garbage collecting plan comparison points:

The only requirement is to keep all plan comparison points that could
ever be used in a current or future merge. Duplicate and merge both
create new plan comparison points, which can shadow existing plan
comparison points. Deleting a plan can also reduce the set of plan
comparison points that can ever be used in a merge.

Temporal subset duplication:

Conceptually, you have duplicated the whole plan, but are limiting
your view/action to a subset.

A merge proceeds as though you have the whole plan. This means that
conflicts may be created outside of your view, and you will need to
resolve them. It should be possible to just bulk resolve all the
conflicts that are outside of your view to just keep the version in
the plan receiving changes. We can possibly make this choice
implicitly, and never show conflicts outside of your view

After a merge is committed, your filter will be reapplied to the full
set of activities - activities that have been moved out of your view
will no longer be visible, and activities that have been moved into
your view will be visible.

It should be possible to run a simulation containing only the
activities in your view.

Changing the start or end time of a plan

There are two possible semantics of changing the start time of the plan:

1. Leave all activity absolute times as they are, and merely shift the start time of the plan
2. Move all activities in the plan as a unit, leaving their offsets from the plan start the same

Option 1 would be a clean extension of our current duplicate/merge semantics. Option 2
would be considered a change of the start time of the plan followed by a modification
of every single activity.

Duplicating other entities affiliated with plans

This specification does not specify what happens to the scheduling
specification, constraints, and other entities that may be affiliated
with a plan when the plan is duplicated or merged.

[JoelCourtney]

Since duplicating produces a completely new plan_id, instead of adding some sort of branch_id field, each duplicate will no longer be associated with any simulation data. If simulation is expensive, there could be a danger that teams go off to make their edits, everyone needs to see resources or constraint violations, and they collectively slam merlin with many identical expensive simulation requests.

Do you think that's a concern?

[mattdailis]

That's a good thought. We don't currently have any provisions for re-using sim results, but when we do, we should definitely consider sharing sim results across multiple similar versions of the same plan.

I think the door to that remains open as long as we keep track of the relationships between plans, either in a branch_id field as you suggest, or through a series of links between child and parent plans.

[mattdailis]

Updates from our UX workflow meeting just now:

• It would be desirable (though not required for a first cut) to be able to selectively drop changes from a merge request - even if they do not cause conflicts.
• A merge request should start in a "requested" state, rather than an "in-progress" state, since the owner of the plan receiving the changes may not be ready to handle the merge request
• When a merge request is in-progress, we want to create a temporary plan representing the future state of the plan receiving the changes. This is so that users can run constraint checking on the temporary plan before committing the merge.

[mattdailis]

I've updated the python prototype with a candidate implementation using "snapshots" - here is the implementation and here is the test suite.

Still missing: the "staging plan" is not part of this prototype yet - nor is "locking" of the plan receiving changes. It's also missing test cases for modifications to the plan receiving changes after the merge request has been created, as well as to the plan receiving changes between the creation and beginning of the merge request.

Another thought: since "pull" and "merge" are symmetric, it could be worth having the option to go through a lighter weight workflow if you just want to pull changes without running constraints on them.

[mattdailis]

We've sketched out the state machine related to merge requests. Blank circle represents a starting state, and a circle with a dot represents a terminating state.

[JoelCourtney]

What does it mean to withdraw a request that has already been withdrawn?

[Mythicaeda]

Nothing: we stay in the same state, like the graph says. That transition was mainly included after considering the case where n users withdraw the same request. Yeah, we could throw an error for every user after the first one processed, but since

1. the only side-effect of withdraw is to set the state to withdrawn and
2. there's no way out of the withdrawn state once we're in it,

there wasn't really a reason to not allow the transition.

[JoelCourtney]

Are we planning to use snapshots? You say "plan snapshots for simulation" is a non-goal, and I'm not sure what that means.

[Mythicaeda]

We're planning to use snapshots for merge. @mattdailis can confirm this, but I believe what "plan snapshots for simulation" is referring to is that running simulations on snapshots is not part of the scope for Plan Collaboration.

[Mythicaeda]

Plans will be merged following a three way merge algorithm. After beginning a merge, the activities will be placed into one of two areas: a Merge Staging Area (MSA) and a Conflicting Activities table (CA). Where they will go is decided as follows:

Difference btwn Source and MB	Difference btwn Target and MB	Outcome
Add	--	Into MSA as Add
--	Add	Into MSA as None
None	None	Into MSA as None
Modify	None	Into MSA as Modify
Delete	None	Into MSA as Delete
None	Modify	Into MSA as None
Modify (Equal)	Modify (Equal)	Into MSA as None
Modify (Inequal)	Modify (Inequal)	Into CA
Delete	Modify	Into CA
None	Delete	Dropped
Modify	Delete	Into CA
Delete	Delete	Dropped