Begin adding implementing room chunks by erikjohnston · Pull Request #3226 · matrix-org/synapse

erikjohnston · 2018-05-17T11:03:35Z

This commit adds the necessary tables and columns, as well as an
implementation of an online topological sorting algorithm to maintain an
absolute ordering of the room chunks.

Note: This is the start of a series of PRs. I'm landing them on a separate branch as we should probably land the full set onto develop at once, but want to make separate PRs to make review easier

This commit adds the necessary tables and columns, as well as an implementation of an online topological sorting algorithm to maintain an absolute ordering of the room chunks.

richvdh · 2018-05-17T11:12:41Z

synapse/storage/events.py

            psql_only=True,
        )

+        self.register_background_index_update(


this is going to be expensive. Might want to warn users about it somewhere.

richvdh · 2018-05-17T11:14:13Z

synapse/util/katriel_bodlaender.py

+"""This module contains an implementation of the Katriel-Bodlaender algorithm,
+which is used to do online topological ordering of graphs.
+
+Note that the ordering derived from the graph has the first node one with no


"the first node one"?

richvdh · 2018-05-17T11:17:05Z

synapse/util/katriel_bodlaender.py

+
+class OrderedListStore(object):
+    """An abstract base class that is used to store a topological ordering of
+    a graph. Suitable for use with the Katriel-Bodlaender algorithm.


I'm confused: "Suitable for use with" or "Implements" ?

richvdh · 2018-05-17T11:17:50Z

synapse/util/katriel_bodlaender.py

+class OrderedListStore(object):
+    """An abstract base class that is used to store a topological ordering of
+    a graph. Suitable for use with the Katriel-Bodlaender algorithm.
+    """


I think some more words about the assumptions being made here would be useful. Likewise re the interface being exposed, to save me having to go and grok the paper.

For example:

Looks like this assumes nodes are identified by unique strings?

How do edges and ordering interact?

does adding a node before/after another imply an edge between those nodes?

richvdh · 2018-05-17T11:27:25Z

synapse/storage/chunk_ordered_table.py

+    in the database.
+
+    Internally the ordering is implemented using floats, and the average is
+    taken when a node is inserted inbetween other nodes. To avoid presicion


s/inbetween/between/

richvdh · 2018-05-17T11:27:32Z

synapse/storage/chunk_ordered_table.py

+    in the database.
+
+    Internally the ordering is implemented using floats, and the average is
+    taken when a node is inserted inbetween other nodes. To avoid presicion


richvdh · 2018-05-17T11:30:34Z

synapse/storage/chunk_ordered_table.py

+            in a range around the node, where the bounds are rounded to this
+            number of digits.
+        min_difference (int): A rebalance is triggered when the difference
+            between two successive orderings are less than the reverse of


s/reverse/reciprocal/ ?

s/are/is/. Two orderings, one difference.

richvdh · 2018-05-17T11:34:04Z

synapse/storage/chunk_ordered_table.py

+logger = logging.getLogger(__name__)
+
+
+class ChunkDBOrderedListStore(OrderedListStore):


I think it would be worth noting what a room chunk actually is, as well as noting that we are storing them in an ordered graph

richvdh · 2018-05-17T11:44:24Z

synapse/storage/chunk_ordered_table.py

+        with Measure(self.clock, "chunk_rebalance"):
+            # We pick the interval to try and minimise the number of decimal
+            # places, i.e. we round to nearest float with `rebalance_digits` and
+            # use that as the middle of the interval


looks like we use it as the end of the interval to me

…unk_base

This both simplifies the code, and ensures that the target node is roughly in the center of the range rather than at an end.

This makes it clearer what the public interface is vs what subclasses need to implement.

richvdh · 2018-05-17T14:47:05Z

CHANGES.rst

+=======================
+
+This release adds an index to the events table. This means that on first
+startup there will be an inceased amount of IO until the index is created.


... and it will use up a bunch of disk space

richvdh · 2018-05-17T14:49:30Z

synapse/storage/chunk_ordered_table.py

+
+    A room chunk is a connected portion of the room events DAG. As such it
+    inherits a DAG, i.e. if an event in one chunk references an event in a
+    second chunk, then we say that the first chunk references the second, and


should probably explain how we get into this situation, rather than the events just being in the same chunk.

richvdh · 2018-05-17T14:51:26Z

synapse/util/katriel_bodlaender.py

+the room DAG, as newer messages would be added to the start rather than the
+end.
+
+***We therefore invert the direction of edges when using the algorithm***


s/we/ChunkDBOrderedListStore/ ?

richvdh · 2018-05-17T14:52:33Z

synapse/util/katriel_bodlaender.py

+        self._insert_before(node_id, None)
+
+    def add_edge(self, source, target):
+        """Adds a new edge is added to the graph and updates the ordering.


s/is added//

richvdh · 2018-05-17T14:53:33Z

synapse/util/katriel_bodlaender.py

+
+
+class InMemoryOrderedListStore(OrderedListStore):
+    """An in memory OrderedListStore


are you planning to use this outside the tests? if not I'd move it to the tests heirarchy

Yes, there's a few cases where we want to order events by depth where this would be useful. Though admittedly I'm not 100% sure that it'll be needed in the end.

richvdh · 2018-05-17T15:01:00Z

synapse/storage/chunk_ordered_table.py

+    """Used as the list store for room chunks, efficiently maintaining them in
+    topological order on updates.
+
+    A room chunk is a connected portion of the room events DAG. As such it


"it" -> the set of chunks in a room?

richvdh · 2018-05-17T15:07:29Z

synapse/storage/chunk_ordered_table.py

+    A room chunk is a connected portion of the room events DAG. As such it
+    inherits a DAG, i.e. if an event in one chunk references an event in a
+    second chunk, then we say that the first chunk references the second, and
+    thus forming a DAG.


right, but potentially a disconnected DAG. How does the ordering happen in that case?

richvdh · 2018-05-17T15:12:02Z

synapse/storage/chunk_ordered_table.py


+    The server may only have a subset of all events in a room, in which case
+    its possible for the server to have chunks that are unconnected from each
+    other. The ordering between unconnected chunks is arbitrary.


If I have four chunks, with two connected parts (A->B , C->D), so we know that A<B and C<D, is it also the case that either B<C (so A<B<C<D) or D<A (so C<D<A<B) ? or could we end up with B in the middle of C and D or something?

I don't think there is anything stopping B being in the middle, since theoretically if you inserted the chunks in the order A, C, B, D, then that obeys all the constraints and so the KB algorithm will leave things alone (I think).

fair enough

richvdh

generally this lgtm and I am now quibbling about words which can easily be updated in the future

richvdh · 2018-05-18T11:10:37Z

synapse/storage/chunk_ordered_table.py

+    an event in a second chunk, then we say that the first chunk references the
+    second, and thus forming a DAG.
+
+    Chunks are constructed so that they have the aditional property that for all


richvdh · 2018-05-18T11:12:54Z

synapse/storage/chunk_ordered_table.py

+    reference an event in the chunk and be referenced by an event in the chunk
+    (assuming no cycles).
+
+    Multiple chunks can therefore happen when the server misses some events,


"We can therefore end up with multiple chunks in a room when..."

richvdh · 2018-05-18T11:19:21Z

synapse/storage/chunk_ordered_table.py

-    inherits a DAG, i.e. if an event in one chunk references an event in a
-    second chunk, then we say that the first chunk references the second, and
-    thus forming a DAG.
+    A room chunk is a connected portion of the room events DAG. As such the set


suggest moving "As such" to after the explanation about how they are constructed

richvdh · 2018-05-18T11:26:05Z

synapse/storage/chunk_ordered_table.py

+    an event in a second chunk, then we say that the first chunk references the
+    second, and thus forming a DAG.
+
+    Chunks are constructed so that they have the aditional property that for all


probably worth noting somewhere here that chunks start out disconnected, and then get connected later when we receive events that, uh, connect them.

erikjohnston assigned richvdh May 17, 2018

Begin adding implementing room chunks

943f102

This commit adds the necessary tables and columns, as well as an implementation of an online topological sorting algorithm to maintain an absolute ordering of the room chunks.

erikjohnston force-pushed the erikj/chunk_base branch from c7be1f5 to 943f102 Compare May 17, 2018 11:05

richvdh reviewed May 17, 2018

View reviewed changes

erikjohnston added 2 commits May 17, 2018 14:00

Merge branch 'develop' of github.com:matrix-org/synapse into erikj/ch…

3b505a8

…unk_base

Add note about index in changelog

3369354

richvdh assigned erikjohnston and unassigned richvdh May 17, 2018

erikjohnston added 3 commits May 17, 2018 15:09

Improve documentation and comments

c771c12

Increase range of rebalance interval

d4e4a73

This both simplifies the code, and ensures that the target node is roughly in the center of the range rather than at an end.

Make insert_* functions internal and reorder funcs

a638649

This makes it clearer what the public interface is vs what subclasses need to implement.

erikjohnston assigned richvdh and unassigned erikjohnston May 17, 2018

richvdh reviewed May 17, 2018

View reviewed changes

Document case of unconnected chunks

12fd6d7

richvdh reviewed May 17, 2018

View reviewed changes

More comments

0504d80

erikjohnston force-pushed the erikj/chunk_base branch from 829cde0 to 0504d80 Compare May 17, 2018 16:08

richvdh approved these changes May 18, 2018

View reviewed changes

Comments

b725e12

erikjohnston merged commit 0a325e5 into erikj/room_chunks May 18, 2018

hawkowl deleted the erikj/chunk_base branch September 20, 2018 13:59

ara4n mentioned this pull request Jun 3, 2019

Proposal: mitigate extremities accumulation using lazy-transmitted dummy events #5319

Closed

		logger = logging.getLogger(__name__)


		class ChunkDBOrderedListStore(OrderedListStore):



		class InMemoryOrderedListStore(OrderedListStore):
		"""An in memory OrderedListStore

Uh oh!

Conversation

erikjohnston commented May 17, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

richvdh left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants