[PATCH 4 of 4 V2] obsolete: allow cycles

[Jun Wu]

Excerpts from Gregory Szorc's message of 2017-03-26 11:25:28 -0700:
> I have a thought experiment to add.
> 
> The obsolete store is strictly ordered. So for a repo detached from the
> world and not doing any exchange, "date" is strictly metadata and the
> offset of a marker in the store is all that matters for precedence.
> 
> This assumption goes completely out the window once exchange is involved
> because when you do `hg pull` you find all markers from the remote not in
> the local store and append them. So now your local store is unordered and
> we have this problem of needing to reorder markers to establish precedence.
> 
> It seems like we're shooting ourselves in the foot by consolidating all
> markers into a single local store. Have we ever considered having a
> separate store per remote or at least preserving the illusion of a separate
> store (e.g. by recording metadata such as "markers N to M pulled from X")?
> This would preserve properties of strict ordering within each peer. There
> are still problems of figuring out the relative ordering between markers
> produced on different peers (with different clocks). But without online
> coordination at the time of marker generation, this is *impossible* to
> achieve. The best you can do is preserve strict ordering within each source
> and exchange/record generation numbers (e.g. marker number/offset) to
> attempt to resolve relative ordering and to drive "merging."

One property that marmoute wants to maintain (and I agree) is the
information is global. That is to say, if we have information about "how to
resolve between X and Y", the "how to" information needs to be shared to
other peers. So every peer will have a consistent view.

> Of course, the implementation of this is complex and requires the concept
> of a persistent and identifiable peer. But it is more robust than relying
> on clocks alone.
>
> Without an online distributed system coordinating strict ordering, it is
> impossible to automatically resolve marker ordering with 100% accuracy. I

True.

> worry that attempting to use wall clock times to resolve ordering will
> result in silent or non-obvious data loss. That breaks a fundamental
> property of version control: don't lose (or corrupt) my data. Whatever we
> do here, there needs to be an option to manually resolve ambiguous ordering
> without relying on dates. I concede this is a very difficult problem on
> several fronts.

The above idea introduces "local", "remote" concepts and more interestingly,
a new state where conflicted markers co-exist but remain unresolved. Where
the "date" approach does not allow that state.

I'd discuss what do we do if we encounter that unresolved conflict. For
example, there are a local marker "A is replaced by B", and a foreign marker
"B is replaced by A". Options are:

  1. Hide both A and B. It's the current behavior.
  2. Hide none. Inspired by "darcs" - things get canceled out if conflict.
  3. Resolve automatically by something, ex. date.

No doubt 1 is not the right thing to do. Bboth 2 and 3 are reasonable to me.
2 is perfect in theory, but practically it's less user-friendly: it require
users to learn new concepts and force manual actions where using date may be
just 95+% correct.

So I'd prefer 3, not only because it's much simpler to implement, but also
from a user-friendliness perspective.

I agree that "manual resolution" is needed to fix cases when auto resolution
is wrong. Given the current situation, I think that could be implemented as
a non-blocking "post-resolution", instead of a "pre-resolution" that may
block some other workflow. That is, the obsstore always auto resolves
everything without interaction. But we provide a command to examine markers
potentially out-of-order, and allows users to "manual resolve" them, by
writing new markers with newer dates.

Does that sound good?