Refactor state group lookup to reduce DB hits #4011

erikjohnston · 2018-10-05T16:14:10Z

Currently when fetching state groups from the data store we make two
hits two the database: once for members and once for non-members (unless
request is filtered to one or the other). This adds needless load to the
datbase, so this PR refactors the lookup to make only a single database
hit.

Currently when fetching state groups from the data store we make two hits two the database: once for members and once for non-members (unless request is filtered to one or the other). This adds needless load to the datbase, so this PR refactors the lookup to make only a single database hit.

richvdh

I think I'm going to stop now. Suffice it to say that this stuff is fiddly.

I do wonder if we're massively over-complicating this by trying to find a general solution. It might be informative to audit how types and filtered_types are actually used, and consider if we ought to be caching at a different level, or something.

richvdh · 2018-10-09T17:19:38Z

synapse/storage/state.py

@@ -749,6 +749,9 @@ def _get_state_for_groups(self, groups, types=None, filtered_types=None):
            Deferred[dict[int, dict[tuple[str, str], str]]]:
                dict of state_group_id -> (dict of (type, state_key) -> event id)
        """
+
+        # First, lets split up the types and filtered types into non-member vs


s/filtered types/filtered_types/

this if statement currently does not split up filtered_types into non-member vs member. (It maybe should, to save problems further down)

richvdh · 2018-10-09T17:22:45Z

synapse/storage/state.py

            groups, self._state_group_cache, non_member_types, filtered_types,
        )
-        # XXX: we could skip this entirely if member_types is []
-        member_state = yield self._get_state_for_groups_using_cache(
+        non_member_state, missing_groups_nm, = r_nm


can you not inline this, for less ugliness and fewer random locals?

non_member_state, missing_groups_nm = ( yield self._get_state_for_groups_using_cache( groups, self._state_group_cache, non_member_types, filtered_types, ) )

also, I think incomplete_groups might be a more appropriate name than missing_groups

richvdh · 2018-10-09T17:24:26Z

synapse/storage/state.py

@@ -802,13 +870,14 @@ def _get_state_for_groups_using_cache(
                If None, `types` filtering is applied to all events.

        Returns:
-            Deferred[dict[int, dict[tuple[str, str], str]]]:
-                dict of state_group_id -> (dict of (type, state_key) -> event id)
+            tuple[dict[int, dict[tuple[str, str], str]], set[dict]]: Tuple of


s/set[dict]/set[int]/ afaict

richvdh · 2018-10-09T17:26:17Z

synapse/storage/state.py

-                dict of state_group_id -> (dict of (type, state_key) -> event id)
+            tuple[dict[int, dict[tuple[str, str], str]], set[dict]]: Tuple of
+            dict of state_group_id -> (dict of (type, state_key) -> event id)
+            of entries in the cache, and the state groups missing from the cache


s/state groups/state_group ids I think

worth noting that said state groups might not be entirely missing - we may just have incomplete data for them.

richvdh · 2018-10-09T17:33:33Z

synapse/storage/state.py

+
+        missing_groups = missing_groups_m | missing_groups_nm
+
+        if missing_groups:


opinions vary on the desirability of this, so up to you, but I prefer an early bail-out than 100 lines of indent which I have to scroll through to find out if there's an else clause:

if not missing_groups: defer.returnValue(state)

(or better yet, factor out a separate function)

richvdh · 2018-10-09T17:55:38Z

synapse/storage/state.py

+            else:
+                types_to_fetch = types
+
+                non_member_types_fetched = [


isn't this the same as non_member_types above? (except that types might be None, in which case this will explode)

[I'm surprised this isn't making the UTs fail tbh]

Hilariously it appears we never hit the non-cached code path, presumably because we insert into the cache on write...

richvdh · 2018-10-09T17:56:01Z

synapse/storage/state.py

+                non_member_types_fetched = [
+                    t for t in types if t[0] != EventTypes.Member
+                ]
+                member_types_fetched = [


likewise, the same as member_types?

synapse/storage/state.py

richvdh · 2018-10-09T18:06:41Z

synapse/storage/state.py

+            else:
+                state_dict.update(group_state_dict)
+
+            # update the cache with all the things we fetched from the


this is a bit redundant now

richvdh · 2018-10-09T18:11:25Z

synapse/storage/state.py

+                    if k in types_fetched or (typ, None) in types_fetched:
+                        state_dict[k] = v
+            else:
+                state_dict.update(group_state_dict)


does this not need splitting by membership/non-membership?

also: I'm not sure there's any point in updating the existing dict, rather than just overwriting it

erikjohnston · 2018-10-10T11:03:15Z

I do wonder if we're massively over-complicating this by trying to find a general solution. It might be informative to audit how types and filtered_types are actually used, and consider if we ought to be caching at a different level, or something.

Absolutely we are over-complicating this, filtered_types is only ever None or [EventTypes.Member] afaict, but I'd quite like to avoid rewriting all the layers right now.

erikjohnston · 2018-10-12T09:17:28Z

I've changed a bunch of the code to bundle a lot of the logic in handling types/filtered_types into a StateFilter type. I haven't changed the public interfaces to use it, but that might be the logical conclusion in making this a bit nicer.

One problem here is that currently the unit tests do not test these code paths very well, since we prefill our state caches on insertion. Commenting out the prefill will test the code correctly. The question is, how do we want to ensure the code is tested while keeping the behaviour the same in production? We can explicitly clear the caches after insertion in our storage state caches, or have a parameter that turns off prefilling?

@erikjohnston

@erikjohnston has changed things

richvdh

oh gosh. I'd hoped that if we refactored all this to use a separate Filter object, we could avoid the whole headfuck of the types/filtered_types thing.

There are multiple ways to do this (one option would be an interface which could be implemented by various implementations like a AllMembersStateFilter or a LazyLoadMembersStateFilter), but
I think a more practical impl would be to make the attributes member_types and non_member_types and provide some helper functions to construct the objects.

And yeah, I know that means rewriting a lot more stuff :/

richvdh · 2018-10-23T16:24:43Z

synapse/storage/state.py

+        """Split the filter into member vs non-member types.
+
+        Returns:
+            tuple[Iterable[str, str|None]|None]: Returns a tuple of member,


this type suggests it is a 1-tuple. Also, it returns lists and I think you should say so:

tuple[List[str, str|None]|None, List[str, str|None]|None]

... yeah, I know.

having said that: why not just split it into get_member_types (which could return just a list[str]|None for the state_keys) and get_non_member_types?

having said having said that: I think we should do this during construction, as per the above.

richvdh · 2018-10-23T16:26:59Z

synapse/storage/state.py

+            non-member types in the same format as `types`.
+        """
+        if self.types is not None:
+            non_member_types = [t for t in self.types if t[0] != EventTypes.Member]


this needs to check filtered_types, I think

richvdh · 2018-10-23T16:35:45Z

synapse/storage/state.py

-                        types is not None and
-                        not wildcard_types and
-                        len(results[group]) == len(types)
+                        max_entries_returned and


this is missing an is not None

richvdh · 2018-10-23T17:00:17Z

synapse/storage/state.py

+    The default, `StateFilter()`, is equivalent to no filter.
+
+    Attributes:
+        types (Iterable[str, str|None]|None): list of 2-tuples of the form


afaict we iterate over this stuff multiple times, so a plain iterable won't do. s/Iterable/list/, possibly.

synapse/storage/state.py

richvdh · 2018-10-23T17:09:58Z

synapse/storage/state.py

+                # We want to return everything.
+                return StateFilter()
+            else:
+                # We want to return all members, but only the specified types


s/specified types/specified non-member types/

richvdh · 2018-10-23T17:16:55Z

synapse/storage/state.py

+        if self.types is None:
+            return where_clause, where_args
+
+        types = set(self.types)


this seems a bit redundant. We know self.types is going to be a list.

richvdh · 2018-10-23T17:27:36Z

synapse/storage/state.py

@@ -391,62 +563,17 @@ def _get_state_groups_from_groups_txn(
                %s


can we just do """..."""" + where_clause rather than interpolating the where clause later?

This changes the internal representation of `StateFilter` to remove the concept of `filtered_types` in favour of a `types` dict and a flag to indicate whether or not to fetch types not in the `types` dict. Ideally in the future we should be able to rewrite our caching so that we cache the filter used when fetching state from the DB. Then when we go fetch more state we can compare the given filter with the filter of the cached result to see if the given is a subset of the cached filter. This would avoid the convolutions of maintaining separate caches.

…ate_state_single_db_lookup

erikjohnston · 2018-10-24T15:49:40Z

synapse/handlers/sync.py

+                    # (if we are) to fix https://github.com/vector-im/riot-web/issues/7209
+                    # We only need apply this on full state syncs given we disabled
+                    # LL for incr syncs in #3840.
+                    members_to_fetch.add(sync_config.user.to_string())


(Note this has been moved up from just below so we can work out members_to_fetch in a single place)

erikjohnston · 2018-10-24T16:03:23Z

Right, first off, I'm so sorry I regret ever setting eyes on filtered_types 😢

On the other hand, filtered_types no longer appear anywhere in the code base 🎉

In the end I didn't change StateFilter to internally store the split of member vs non member stuff, as it turned out to be quite fiddly. Instead it has a types dict mapping from event type to set of state keys (or None) that indicates specifically which types/state_keys to include/exclude, and a flag to indicate whether to fetch types that don't appear in the types dict.

Ideally we could then easily change the cache to store the StateFilter used when fetching state, which would mean on look up we could simply compare the given state filter with the one stored in the cache. (I believe checking if one state filter is a subset of another is easy enough to implement). This would allows us to rip out all the special casing for membership events in the state store.

Everything would then be fine and lovely and we should never touch the state store ever again.

Co-Authored-By: erikjohnston <[email protected]>

erikjohnston · 2018-10-25T14:52:53Z

I think that should have addressed all the comments :)

richvdh

lgtm otherwise. please fix up and merge

synapse/storage/state.py

richvdh · 2018-10-25T16:28:05Z

synapse/storage/state.py

@@ -328,6 +350,15 @@ def get_member_split(self):

        return member_filter, non_member_filter

+    def __attrs_post_init__(self):


could this go at the top, where __init__ would normally go?

erikjohnston mentioned this pull request Oct 5, 2018

Don't ask DB twice for state groups #4009

Closed

erikjohnston added 2 commits October 8, 2018 10:11

Newsfile

0a94c2f

erikjohnston force-pushed the erikj/state_state_single_db_lookup branch from bb62702 to 0a94c2f Compare October 8, 2018 09:12

erikjohnston requested a review from a team October 8, 2018 12:09

richvdh previously requested changes Oct 9, 2018

View reviewed changes

richvdh assigned erikjohnston Oct 9, 2018

Fix up docs, variable names and style

24ac0f7

Rewrite to use new StateFilter internally

63f944d

erikjohnston force-pushed the erikj/state_state_single_db_lookup branch from 5361ca9 to 63f944d Compare October 11, 2018 15:02

Move filtering logic to StateFilter

a0f966b

erikjohnston requested a review from a team October 12, 2018 09:02

erikjohnston removed their assignment Oct 15, 2018

richvdh suggested changes Oct 23, 2018

View reviewed changes

richvdh assigned erikjohnston Oct 23, 2018

erikjohnston added 8 commits October 24, 2018 10:29

Fix up comment

e8d92e9

Just use normal string concatenation

4f1b299

Add missing 'is not None'

aa251f9

Refactor to use StateFilter everywhere

93265c8

User StateFilter for fetching from caches

f1480c6

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

6033ff5

…ate_state_single_db_lookup

Remove debug logging

c189b72

erikjohnston commented Oct 24, 2018

View reviewed changes

Move comment

9518712

erikjohnston requested a review from richvdh October 24, 2018 16:13

richvdh and others added 20 commits October 25, 2018 13:56

Fix up docstring

245e22f

Co-Authored-By: erikjohnston <[email protected]>

Fix up docstring

9afdb13

Co-Authored-By: erikjohnston <[email protected]>

Fix up docstring

85fcd82

Co-Authored-By: erikjohnston <[email protected]>

Fix up docstring

b3e4493

Co-Authored-By: erikjohnston <[email protected]>

Fix up docstring

1362505

Co-Authored-By: erikjohnston <[email protected]>

Fix using sum rather than len

f29af2d

Co-Authored-By: erikjohnston <[email protected]>

Add docstring

780960c

Canonicalise types dict when include_others=True

36edf79

Fix up overzealous iteration

315e75d

Fix up comment

75bd67e

Don't needlessly copy

ddbe779

Drop default

bb6bc6e

Clarify by moving blank line

7f7f7ae

Clean up comment

9055583

Neaten up adding where clause to sql

630dc7c

Use from_types helper func

eb6d3c9

Add from_lazy_load_member_list

cf984c0

Correctly handle empty filters in make_sql_filter_clause

2bdee39

Tidy up return_expanded

283e021

Always use helper functions rather than init

36408bc

erikjohnston requested a review from richvdh October 25, 2018 14:48

richvdh approved these changes Oct 25, 2018

View reviewed changes

erikjohnston added 2 commits October 25, 2018 17:31

Move __attrs_post_init__ to top

d701ef6

Doc when an empty SQL string means in make_sql_filter_clause

f189fd4

erikjohnston merged commit cb53ce9 into develop Oct 25, 2018

erikjohnston mentioned this pull request Oct 29, 2018

TypeError on /search #4112

Closed

erikjohnston deleted the erikj/state_state_single_db_lookup branch December 12, 2018 15:44


		missing_groups = missing_groups_m \| missing_groups_nm

		if missing_groups:

		@@ -391,62 +563,17 @@ def _get_state_groups_from_groups_txn(
		%s

		@@ -328,6 +350,15 @@ def get_member_split(self):

		return member_filter, non_member_filter

		def __attrs_post_init__(self):

Refactor state group lookup to reduce DB hits #4011

Refactor state group lookup to reduce DB hits #4011

Conversation

erikjohnston commented Oct 5, 2018

richvdh left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

erikjohnston commented Oct 10, 2018

erikjohnston commented Oct 12, 2018

richvdh left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

erikjohnston commented Oct 24, 2018

erikjohnston commented Oct 25, 2018

richvdh left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment