Any topological order is valid though it may not be efficient. A ``Depth-First
Search`` order assignment yields good results. An optimization that we can do
it is for merges, we first assign the branch with least number of merges.

To assign a number for ``x``, check its parents.

* If all parents have numbers, assign the next available number to ``x``.

* Otherwise, pick the parent with less merges. Assign it recursively.

Groups
~~~~~~

Efficiency of ``Segmented Changelog`` requires efficient representation of
sets.  For example, ``ancestors(master)`` is ideally ``0:x``, not ``0:i +
j:x``. To ensure that, ``Segmented Changelog`` reserves a large integer space
for master and tries to avoid assigning master + 1 to non-master nodes. This is
achieved by ``Groups``.

In our ``Changelog`` use case, we have the ``Master`` group and the
``NonMaster`` group. It is generally assumed that the ``Master`` group will
have a lot of commits (and we mostly care about them). ``Master`` commits are
assigned starting from ``0``.  ``NonMaster`` commits are assigned from ``2^56``
onwards.  Local commits are stored in the ``NonMaster`` section. This has the
purpose of preserving efficient ``Segment`` construction for the ``Master``
section as new commits get added of top of this section. This allows the
``Master`` section to have segments with maximum length.

Core Components
~~~~~~~~~~~~~~~

We described 3 concepts in the beginning:

1. graph shape, we may also call ``IdDag``.

2. node identifiers, we may also call ``IdMap``.

3. node information, we may also call ``HgCommits``.

The ``IdDag`` describes all graph algorithms and all operations leverage
segments.  The ``IdMap`` is a bidirectional map from ``Segmented Changelog Id``
to node identifier, in the case of the changelog the ``Sha1`` hash of the
commit.  ``HgCommits`` is a simple key value store from ``Sha1`` commit hash to
commit message.

For the client ``IdDag``, ``IdMap`` and ``HgCommits`` are stored using
``IndexedLog``.

Server implementation
~~~~~~~~~~~~~~~~~~~~~

For the server, ``IdDag`` is stored fully in process for all serving instances.
At startup, a ``IdDag`` is downloaded from the ``Blobstore``, then it is
updated locally as commits come in. Protocols do not depend on "internal"
``Segmented Changelog Ids``, instead they express shape relative to common node
identifiers (commit hashes).

The ``IdMap`` is stored in a ``SQL`` store. For the servers, the ``IdMap``
additionally stores a version. This is done to facilitate regenerating the
whole ``IdMap`` while continuing to serve requests. ``IdMap`` regeneration may
be performed when better algorithms are developed or bugs are uncovered.

``HgCommits`` have their own ``SQL`` storage. For the purpose of ``Segmented
Changelog`` we only care that we can query the respective commit identifier that
is stored in the ``IdMap``.

To construct the ``Segmented Changelog`` from a repository we use the
``Segmented Changelog Seeder``.  The ``Seeder`` will construct a new ``IdMap``
version and an initial ``IdDag``.

We mentioned that at startup an ``IdDag`` has to be loaded from the
``Blobstore`` so we need a process that updates the ``IdMap`` and the
``IdDag``. This process is the ``Segmented Changelog Tailer``. It periodically
checks for new commits and incrementally adds entries to the ``IdMap`` and
reconstructs the ``IdDag``.

The client communicates with the server using ``EdenApi`` endpoints:

* ``/{repo}/commit/revlog_data``: commit content by ``Sha1`` hash in the format
  that verifies the ``Sha1`` hash.

* ``/{repo}/commit/location_to_hash``: used to translate compressed commit info
  (graph location) to hashes.

* ``/{repo}/commit/hash_to_location``:used to translate hashes to compressed
  commit info (graph location).

* ``/{repo}/clone``: downloads ``SegmentedChangelog`` repository data.

* ``/{repo}/full_idmap_clone``: downloads ``SegmentedChangelog`` repository
  data along with all commit hashes in the commit graph.