Homec4science

Allow edges to be configured to prevent cycles

Authored by epriestley <git@epriestley.com> on Jul 9 2012, 19:39.

Description

Allow edges to be configured to prevent cycles

Summary:
Certain types of things we should be storing in edges (notably, Task X depends on Task Y) should always be acyclic. Allow PhabricatorEdgeEditor to enforce this, since we can't correctly enforce it outside of the editor without being vulnerable to races.

Each edge type can be marked acyclic. If an edge type is acyclic, we perform additional steps when writing new edges of that type:

  • We acquire a global lock on the edge type before performing any reads or writes. This ensures we can't produce a cycle as a result of a race where two edits add edges which independently do not produce a cycle, but do produce a cycle when combined.
  • After performing writes but before committing transactions, we load the edge graph for each acyclic type and verify that it is, in fact, acyclic. If we detect cycles, we abort the edit.
  • When we're done, we release the edge type locks.

This is a relatively high-complexity change, but gives us a simple way to flag an edge type as acyclic in a robust way.

Test Plan: Ran unit tests.

Reviewers: btrahan

Reviewed By: btrahan

CC: aran

Maniphest Tasks: T1162

Differential Revision: https://secure.phabricator.com/D2940

Details

Committed
epriestley <git@epriestley.com>Jul 9 2012, 19:39
Pushed
aubortJan 31 2017, 17:16
Parents
rPHbf8cbf55b1f5: Namespace GlobalLocks to storage namespaces
Branches
Unknown
Tags
Unknown

Event Timeline

epriestley <git@epriestley.com> committed rPH1089a48d4a66: Allow edges to be configured to prevent cycles (authored by epriestley <git@epriestley.com>).Jul 9 2012, 19:39