1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
|
<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Faster remote joins - Synapse</title>
<!-- Custom HTML head -->
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff" />
<link rel="icon" href="../../favicon.svg">
<link rel="shortcut icon" href="../../favicon.png">
<link rel="stylesheet" href="../../css/variables.css">
<link rel="stylesheet" href="../../css/general.css">
<link rel="stylesheet" href="../../css/chrome.css">
<link rel="stylesheet" href="../../css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="../../fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" href="../../highlight.css">
<link rel="stylesheet" href="../../tomorrow-night.css">
<link rel="stylesheet" href="../../ayu-highlight.css">
<!-- Custom theme stylesheets -->
<link rel="stylesheet" href="../../docs/website_files/table-of-contents.css">
<link rel="stylesheet" href="../../docs/website_files/remove-nav-buttons.css">
<link rel="stylesheet" href="../../docs/website_files/indent-section-headers.css">
<link rel="stylesheet" href="../../docs/website_files/version-picker.css">
</head>
<body>
<!-- Provide site root to javascript -->
<script type="text/javascript">
var path_to_root = "../../";
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
</script>
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script type="text/javascript">
try {
var theme = localStorage.getItem('mdbook-theme');
var sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script type="text/javascript">
var theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
var html = document.querySelector('html');
html.classList.remove('no-js')
html.classList.remove('light')
html.classList.add(theme);
html.classList.add('js');
</script>
<!-- Hide / unhide sidebar before it is displayed -->
<script type="text/javascript">
var html = document.querySelector('html');
var sidebar = 'hidden';
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
}
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<div class="sidebar-scrollbox">
<ol class="chapter"><li class="chapter-item expanded affix "><li class="part-title">Introduction</li><li class="chapter-item expanded "><a href="../../welcome_and_overview.html">Welcome and Overview</a></li><li class="chapter-item expanded affix "><li class="part-title">Setup</li><li class="chapter-item expanded "><a href="../../setup/installation.html">Installation</a></li><li class="chapter-item expanded "><a href="../../postgres.html">Using Postgres</a></li><li class="chapter-item expanded "><a href="../../reverse_proxy.html">Configuring a Reverse Proxy</a></li><li class="chapter-item expanded "><a href="../../setup/forward_proxy.html">Configuring a Forward/Outbound Proxy</a></li><li class="chapter-item expanded "><a href="../../turn-howto.html">Configuring a Turn Server</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../setup/turn/coturn.html">coturn TURN server</a></li><li class="chapter-item expanded "><a href="../../setup/turn/eturnal.html">eturnal TURN server</a></li></ol></li><li class="chapter-item expanded "><a href="../../delegate.html">Delegation</a></li><li class="chapter-item expanded affix "><li class="part-title">Upgrading</li><li class="chapter-item expanded "><a href="../../upgrade.html">Upgrading between Synapse Versions</a></li><li class="chapter-item expanded affix "><li class="part-title">Usage</li><li class="chapter-item expanded "><a href="../../federate.html">Federation</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/index.html">Configuration</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../usage/configuration/config_documentation.html">Configuration Manual</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/homeserver_sample_config.html">Homeserver Sample Config File</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/logging_sample_config.html">Logging Sample Config File</a></li><li class="chapter-item expanded "><a href="../../structured_logging.html">Structured Logging</a></li><li class="chapter-item expanded "><a href="../../templates.html">Templates</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/user_authentication/index.html">User Authentication</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../usage/configuration/user_authentication/single_sign_on/index.html">Single-Sign On</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../openid.html">OpenID Connect</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/user_authentication/single_sign_on/saml.html">SAML</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/user_authentication/single_sign_on/cas.html">CAS</a></li><li class="chapter-item expanded "><a href="../../sso_mapping_providers.html">SSO Mapping Providers</a></li></ol></li><li class="chapter-item expanded "><a href="../../password_auth_providers.html">Password Auth Providers</a></li><li class="chapter-item expanded "><a href="../../jwt.html">JSON Web Tokens</a></li><li class="chapter-item expanded "><a href="../../usage/configuration/user_authentication/refresh_tokens.html">Refresh Tokens</a></li></ol></li><li class="chapter-item expanded "><a href="../../CAPTCHA_SETUP.html">Registration Captcha</a></li><li class="chapter-item expanded "><a href="../../application_services.html">Application Services</a></li><li class="chapter-item expanded "><a href="../../server_notices.html">Server Notices</a></li><li class="chapter-item expanded "><a href="../../consent_tracking.html">Consent Tracking</a></li><li class="chapter-item expanded "><a href="../../user_directory.html">User Directory</a></li><li class="chapter-item expanded "><a href="../../message_retention_policies.html">Message Retention Policies</a></li><li class="chapter-item expanded "><a href="../../modules/index.html">Pluggable Modules</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../modules/writing_a_module.html">Writing a module</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../modules/spam_checker_callbacks.html">Spam checker callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/third_party_rules_callbacks.html">Third-party rules callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/presence_router_callbacks.html">Presence router callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/account_validity_callbacks.html">Account validity callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/password_auth_provider_callbacks.html">Password auth provider callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/background_update_controller_callbacks.html">Background update controller callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/account_data_callbacks.html">Account data callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/add_extra_fields_to_client_events_unsigned.html">Add extra fields to client events unsigned section callbacks</a></li><li class="chapter-item expanded "><a href="../../modules/porting_legacy_module.html">Porting a legacy module to the new interface</a></li></ol></li></ol></li><li class="chapter-item expanded "><a href="../../workers.html">Workers</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../synctl_workers.html">Using synctl with Workers</a></li><li class="chapter-item expanded "><a href="../../systemd-with-workers/index.html">Systemd</a></li></ol></li></ol></li><li class="chapter-item expanded "><a href="../../usage/administration/index.html">Administration</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../usage/administration/admin_api/index.html">Admin API</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../admin_api/account_validity.html">Account Validity</a></li><li class="chapter-item expanded "><a href="../../usage/administration/admin_api/background_updates.html">Background Updates</a></li><li class="chapter-item expanded "><a href="../../admin_api/event_reports.html">Event Reports</a></li><li class="chapter-item expanded "><a href="../../admin_api/experimental_features.html">Experimental Features</a></li><li class="chapter-item expanded "><a href="../../admin_api/media_admin_api.html">Media</a></li><li class="chapter-item expanded "><a href="../../admin_api/purge_history_api.html">Purge History</a></li><li class="chapter-item expanded "><a href="../../admin_api/register_api.html">Register Users</a></li><li class="chapter-item expanded "><a href="../../usage/administration/admin_api/registration_tokens.html">Registration Tokens</a></li><li class="chapter-item expanded "><a href="../../admin_api/room_membership.html">Manipulate Room Membership</a></li><li class="chapter-item expanded "><a href="../../admin_api/rooms.html">Rooms</a></li><li class="chapter-item expanded "><a href="../../admin_api/server_notices.html">Server Notices</a></li><li class="chapter-item expanded "><a href="../../admin_api/statistics.html">Statistics</a></li><li class="chapter-item expanded "><a href="../../admin_api/user_admin_api.html">Users</a></li><li class="chapter-item expanded "><a href="../../admin_api/version_api.html">Server Version</a></li><li class="chapter-item expanded "><a href="../../usage/administration/admin_api/federation.html">Federation</a></li></ol></li><li class="chapter-item expanded "><a href="../../manhole.html">Manhole</a></li><li class="chapter-item expanded "><a href="../../metrics-howto.html">Monitoring</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../usage/administration/monitoring/reporting_homeserver_usage_statistics.html">Reporting Homeserver Usage Statistics</a></li></ol></li><li class="chapter-item expanded "><a href="../../usage/administration/monthly_active_users.html">Monthly Active Users</a></li><li class="chapter-item expanded "><a href="../../usage/administration/understanding_synapse_through_grafana_graphs.html">Understanding Synapse Through Grafana Graphs</a></li><li class="chapter-item expanded "><a href="../../usage/administration/useful_sql_for_admins.html">Useful SQL for Admins</a></li><li class="chapter-item expanded "><a href="../../usage/administration/database_maintenance_tools.html">Database Maintenance Tools</a></li><li class="chapter-item expanded "><a href="../../usage/administration/state_groups.html">State Groups</a></li><li class="chapter-item expanded "><a href="../../usage/administration/request_log.html">Request log format</a></li><li class="chapter-item expanded "><a href="../../usage/administration/admin_faq.html">Admin FAQ</a></li><li class="chapter-item expanded "><div>Scripts</div></li></ol></li><li class="chapter-item expanded "><li class="part-title">Development</li><li class="chapter-item expanded "><a href="../../development/contributing_guide.html">Contributing Guide</a></li><li class="chapter-item expanded "><a href="../../code_style.html">Code Style</a></li><li class="chapter-item expanded "><a href="../../development/reviews.html">Reviewing Code</a></li><li class="chapter-item expanded "><a href="../../development/releases.html">Release Cycle</a></li><li class="chapter-item expanded "><a href="../../development/git.html">Git Usage</a></li><li class="chapter-item expanded "><div>Testing</div></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../development/demo.html">Demo scripts</a></li></ol></li><li class="chapter-item expanded "><a href="../../opentracing.html">OpenTracing</a></li><li class="chapter-item expanded "><a href="../../development/database_schema.html">Database Schemas</a></li><li class="chapter-item expanded "><a href="../../development/experimental_features.html">Experimental features</a></li><li class="chapter-item expanded "><a href="../../development/dependencies.html">Dependency management</a></li><li class="chapter-item expanded "><div>Synapse Architecture</div></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../development/synapse_architecture/cancellation.html">Cancellation</a></li><li class="chapter-item expanded "><a href="../../log_contexts.html">Log Contexts</a></li><li class="chapter-item expanded "><a href="../../replication.html">Replication</a></li><li class="chapter-item expanded "><a href="../../development/synapse_architecture/streams.html">Streams</a></li><li class="chapter-item expanded "><a href="../../tcp_replication.html">TCP Replication</a></li><li class="chapter-item expanded "><a href="../../development/synapse_architecture/faster_joins.html" class="active">Faster remote joins</a></li></ol></li><li class="chapter-item expanded "><a href="../../development/internal_documentation/index.html">Internal Documentation</a></li><li><ol class="section"><li class="chapter-item expanded "><div>Single Sign-On</div></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../development/saml.html">SAML</a></li><li class="chapter-item expanded "><a href="../../development/cas.html">CAS</a></li></ol></li><li class="chapter-item expanded "><a href="../../development/room-dag-concepts.html">Room DAG concepts</a></li><li class="chapter-item expanded "><div>State Resolution</div></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../auth_chain_difference_algorithm.html">The Auth Chain Difference Algorithm</a></li></ol></li><li class="chapter-item expanded "><a href="../../media_repository.html">Media Repository</a></li><li class="chapter-item expanded "><a href="../../room_and_user_statistics.html">Room and User Statistics</a></li></ol></li><li class="chapter-item expanded "><div>Scripts</div></li><li class="chapter-item expanded affix "><li class="part-title">Other</li><li class="chapter-item expanded "><a href="../../deprecation_policy.html">Dependency Deprecation Policy</a></li><li class="chapter-item expanded "><a href="../../other/running_synapse_on_single_board_computers.html">Running Synapse on a Single-Board Computer</a></li></ol>
</div>
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky bordered">
<div class="left-buttons">
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</button>
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
<i class="fa fa-search"></i>
</button>
<div class="version-picker">
<div class="dropdown">
<div class="select">
<span></span>
<i class="fa fa-chevron-down"></i>
</div>
<input type="hidden" name="version">
<ul class="dropdown-menu">
<!-- Versions will be added dynamically in version-picker.js -->
</ul>
</div>
</div>
</div>
<h1 class="menu-title">Synapse</h1>
<div class="right-buttons">
<a href="../../print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
<a href="https://github.com/element-hq/synapse" title="Git repository" aria-label="Git repository">
<i id="git-repository-button" class="fa fa-github"></i>
</a>
<a href="https://github.com/element-hq/synapse/edit/develop/docs/development/synapse_architecture/faster_joins.md" title="Suggest an edit" aria-label="Suggest an edit">
<i id="git-edit-button" class="fa fa-edit"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script type="text/javascript">
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<!-- Page table of contents -->
<div class="sidetoc">
<nav class="pagetoc"></nav>
</div>
<h1 id="how-do-faster-joins-work"><a class="header" href="#how-do-faster-joins-work">How do faster joins work?</a></h1>
<p>This is a work-in-progress set of notes with two goals:</p>
<ul>
<li>act as a reference, explaining how Synapse implements faster joins; and</li>
<li>record the rationale behind our choices.</li>
</ul>
<p>See also <a href="https://github.com/matrix-org/matrix-spec-proposals/pull/3902">MSC3902</a>.</p>
<p>The key idea is described by <a href="https://github.com/matrix-org/matrix-spec-proposals/pull/3706">MSC3706</a>. This allows servers to
request a lightweight response to the federation <code>/send_join</code> endpoint.
This is called a <strong>faster join</strong>, also known as a <strong>partial join</strong>. In these
notes we'll usually use the word "partial" as it matches the database schema.</p>
<h2 id="overview-processing-events-in-a-partially-joined-room"><a class="header" href="#overview-processing-events-in-a-partially-joined-room">Overview: processing events in a partially-joined room</a></h2>
<p>The response to a partial join consists of</p>
<ul>
<li>the requested join event <code>J</code>,</li>
<li>a list of the servers in the room (according to the state before <code>J</code>),</li>
<li>a subset of the state of the room before <code>J</code>,</li>
<li>the full auth chain of that state subset.</li>
</ul>
<p>Synapse marks the room as partially joined by adding a row to the database table
<code>partial_state_rooms</code>. It also marks the join event <code>J</code> as "partially stated",
meaning that we have neither received nor computed the full state before/after
<code>J</code>. This is done by adding a row to <code>partial_state_events</code>.</p>
<details><summary>DB schema</summary>
<pre><code>matrix=> \d partial_state_events
Table "matrix.partial_state_events"
Column │ Type │ Collation │ Nullable │ Default
══════════╪══════╪═══════════╪══════════╪═════════
room_id │ text │ │ not null │
event_id │ text │ │ not null │
matrix=> \d partial_state_rooms
Table "matrix.partial_state_rooms"
Column │ Type │ Collation │ Nullable │ Default
════════════════════════╪════════╪═══════════╪══════════╪═════════
room_id │ text │ │ not null │
device_lists_stream_id │ bigint │ │ not null │ 0
join_event_id │ text │ │ │
joined_via │ text │ │ │
matrix=> \d partial_state_rooms_servers
Table "matrix.partial_state_rooms_servers"
Column │ Type │ Collation │ Nullable │ Default
═════════════╪══════╪═══════════╪══════════╪═════════
room_id │ text │ │ not null │
server_name │ text │ │ not null │
</code></pre>
<p>Indices, foreign-keys and check constraints are omitted for brevity.</p>
</details>
<p>While partially joined to a room, Synapse receives events <code>E</code> from remote
homeservers as normal, and can create events at the request of its local users.
However, we run into trouble when we enforce the <a href="https://spec.matrix.org/v1.5/server-server-api/#checks-performed-on-receipt-of-a-pdu">checks on an event</a>.</p>
<blockquote>
<ol>
<li>Is a valid event, otherwise it is dropped. For an event to be valid, it
must contain a room_id, and it must comply with the event format of that
room version.</li>
<li>Passes signature checks, otherwise it is dropped.</li>
<li>Passes hash checks, otherwise it is redacted before being processed further.</li>
<li>Passes authorization rules based on the event’s auth events, otherwise it
is rejected.</li>
<li><strong>Passes authorization rules based on the state before the event, otherwise
it is rejected.</strong></li>
<li><strong>Passes authorization rules based on the current state of the room,
otherwise it is “soft failed”.</strong></li>
</ol>
</blockquote>
<p>We can enforce checks 1--4 without any problems.
But we cannot enforce checks 5 or 6 with complete certainty, since Synapse does
not know the full state before <code>E</code>, nor that of the room.</p>
<h3 id="partial-state"><a class="header" href="#partial-state">Partial state</a></h3>
<p>Instead, we make a best-effort approximation.
While the room is considered partially joined, Synapse tracks the "partial
state" before events.
This works in a similar way as regular state:</p>
<ul>
<li>The partial state before <code>J</code> is that given to us by the partial join response.</li>
<li>The partial state before an event <code>E</code> is the resolution of the partial states
after each of <code>E</code>'s <code>prev_event</code>s.</li>
<li>If <code>E</code> is rejected or a message event, the partial state after <code>E</code> is the
partial state before <code>E</code>.</li>
<li>Otherwise, the partial state after <code>E</code> is the partial state before <code>E</code>, plus
<code>E</code> itself.</li>
</ul>
<p>More concisely, partial state propagates just like full state; the only
difference is that we "seed" it with an incomplete initial state.
Synapse records that we have only calculated partial state for this event with
a row in <code>partial_state_events</code>.</p>
<p>While the room remains partially stated, check 5 on incoming events to that
room becomes:</p>
<blockquote>
<ol start="5">
<li>Passes authorization rules based on <strong>the resolution between the partial
state before <code>E</code> and <code>E</code>'s auth events.</strong> If the event fails to pass
authorization rules, it is rejected.</li>
</ol>
</blockquote>
<p>Additionally, check 6 is deleted: no soft-failures are enforced.</p>
<p>While partially joined, the current partial state of the room is defined as the
resolution across the partial states after all forward extremities in the room.</p>
<p><em>Remark.</em> Events with partial state are <em>not</em> considered
<a href="../room-dag-concepts.html#outliers">outliers</a>.</p>
<h3 id="approximation-error"><a class="header" href="#approximation-error">Approximation error</a></h3>
<p>Using partial state means the auth checks can fail in a few different ways<sup class="footnote-reference"><a href="#2">1</a></sup>.</p>
<div class="footnote-definition" id="2"><sup class="footnote-definition-label">1</sup>
<p>Is this exhaustive?</p>
</div>
<ul>
<li>We may erroneously accept an incoming event in check 5 based on partial state
when it would have been rejected based on full state, or vice versa.</li>
<li>This means that an event could erroneously be added to the current partial
state of the room when it would not be present in the full state of the room,
or vice versa.</li>
<li>Additionally, we may have skipped soft-failing an event that would have been
soft-failed based on full state.</li>
</ul>
<p>(Note that the discrepancies described in the last two bullets are user-visible.)</p>
<p>This means that we have to be very careful when we want to lookup pieces of room
state in a partially-joined room. Our approximation of the state may be
incorrect or missing. But we can make some educated guesses. If</p>
<ul>
<li>our partial state is likely to be correct, or</li>
<li>the consequences of our partial state being incorrect are minor,</li>
</ul>
<p>then we proceed as normal, and let the resync process fix up any mistakes (see
below).</p>
<p>When is our partial state likely to be correct?</p>
<ul>
<li>It's more accurate the closer we are to the partial join event. (So we should
ideally complete the resync as soon as possible.)</li>
<li>Non-member events: we will have received them as part of the partial join
response, if they were part of the room state at that point. We may
incorrectly accept or reject updates to that state (at first because we lack
remote membership information; later because of compounding errors), so these
can become incorrect over time.</li>
<li>Local members' memberships: we are the only ones who can create join and
knock events for our users. We can't be completely confident in the
correctness of bans, invites and kicks from other homeservers, but the resync
process should correct any mistakes.</li>
<li>Remote members' memberships: we did not receive these in the /send_join
response, so we have essentially no idea if these are correct or not.</li>
</ul>
<p>In short, we deem it acceptable to trust the partial state for non-membership
and local membership events. For remote membership events, we wait for the
resync to complete, at which point we have the full state of the room and can
proceed as normal.</p>
<h3 id="fixing-the-approximation-with-a-resync"><a class="header" href="#fixing-the-approximation-with-a-resync">Fixing the approximation with a resync</a></h3>
<p>The partial-state approximation is only a temporary affair. In the background,
synapse beings a "resync" process. This is a continuous loop, starting at the
partial join event and proceeding downwards through the event graph. For each
<code>E</code> seen in the room since partial join, Synapse will fetch </p>
<ul>
<li>the event ids in the state of the room before <code>E</code>, via
<a href="https://spec.matrix.org/v1.5/server-server-api/#get_matrixfederationv1state_idsroomid"><code>/state_ids</code></a>;</li>
<li>the event ids in the full auth chain of <code>E</code>, included in the <code>/state_ids</code>
response; and</li>
<li>any events from the previous two bullets that Synapse hasn't persisted, via
<a href="https://spec.matrix.org/v1.5/server-server-api/#get_matrixfederationv1stateroomid">`/state</a>.</li>
</ul>
<p>This means Synapse has (or can compute) the full state before <code>E</code>, which allows
Synapse to properly authorise or reject <code>E</code>. At this point ,the event
is considered to have "full state" rather than "partial state". We record this
by removing <code>E</code> from the <code>partial_state_events</code> table.</p>
<p>[<strong>TODO:</strong> Does Synapse persist a new state group for the full state
before <code>E</code>, or do we alter the (partial-)state group in-place? Are state groups
ever marked as partially-stated? ]</p>
<p>This scheme means it is possible for us to have accepted and sent an event to
clients, only to reject it during the resync. From a client's perspective, the
effect is similar to a retroactive
state change due to state resolution---i.e. a "state reset".<sup class="footnote-reference"><a href="#3">2</a></sup></p>
<div class="footnote-definition" id="3"><sup class="footnote-definition-label">2</sup>
<p>Clients should refresh caches to detect such a change. Rumour has it that
sliding sync will fix this.</p>
</div>
<p>When all events since the join <code>J</code> have been fully-stated, the room resync
process is complete. We record this by removing the room from
<code>partial_state_rooms</code>.</p>
<h2 id="faster-joins-on-workers"><a class="header" href="#faster-joins-on-workers">Faster joins on workers</a></h2>
<p>For the time being, the resync process happens on the master worker.
A new replication stream <code>un_partial_stated_room</code> is added. Whenever a resync
completes and a partial-state room becomes fully stated, a new message is sent
into that stream containing the room ID.</p>
<h2 id="notes-on-specific-cases"><a class="header" href="#notes-on-specific-cases">Notes on specific cases</a></h2>
<blockquote>
<p><strong>NB.</strong> The notes below are rough. Some of them are hidden under <code><details></code>
disclosures because they have yet to be implemented in mainline Synapse.</p>
</blockquote>
<h3 id="creating-events-during-a-partial-join"><a class="header" href="#creating-events-during-a-partial-join">Creating events during a partial join</a></h3>
<p>When sending out messages during a partial join, we assume our partial state is
accurate and proceed as normal. For this to have any hope of succeeding at all,
our partial state must contain an entry for each of the (type, state key) pairs
<a href="https://spec.matrix.org/v1.3/rooms/v10/#authorization-rules">specified by the auth rules</a>:</p>
<ul>
<li><code>m.room.create</code></li>
<li><code>m.room.join_rules</code></li>
<li><code>m.room.power_levels</code></li>
<li><code>m.room.third_party_invite</code></li>
<li><code>m.room.member</code></li>
</ul>
<p>The first four of these should be present in the state before <code>J</code> that is given
to us in the partial join response; only membership events are omitted. In order
for us to consider the user joined, we must have their membership event. That
means the only possible omission is the target's membership in an invite, kick
or ban.</p>
<p>The worst possibility is that we locally invite someone who is banned according to
the full state, because we lack their ban in our current partial state. The rest
of the federation---at least, those who are fully joined---should correctly
enforce the <a href="https://spec.matrix.org/v1.3/client-server-api/#room-membership">membership transition constraints</a>. So any the erroneous invite should be ignored by fully-joined
homeservers and resolved by the resync for partially-joined homeservers.</p>
<p>In more generality, there are two problems we're worrying about here:</p>
<ul>
<li>We might create an event that is valid under our partial state, only to later
find out that is actually invalid according to the full state.</li>
<li>Or: we might refuse to create an event that is invalid under our partial
state, even though it would be perfectly valid under the full state.</li>
</ul>
<p>However we expect such problems to be unlikely in practise, because</p>
<ul>
<li>We trust that the room has sensible power levels, e.g. that bad actors with
high power levels are demoted before their ban.</li>
<li>We trust that the resident server provides us up-to-date power levels, join
rules, etc.</li>
<li>State changes in rooms are relatively infrequent, and the resync period is
relatively quick.</li>
</ul>
<h4 id="sending-out-the-event-over-federation"><a class="header" href="#sending-out-the-event-over-federation">Sending out the event over federation</a></h4>
<p><strong>TODO:</strong> needs prose fleshing out.</p>
<p>Normally: send out in a fed txn to all HSes in the room.
We only know that some HSes were in the room at some point. Wat do.
Send it out to the list of servers from the first join.
<strong>TODO</strong> what do we do here if we have full state?
If the prev event was created by us, we can risk sending it to the wrong HS. (Motivation: privacy concern of the content. Not such a big deal for a public room or an encrypted room. But non-encrypted invite-only...)
But don't want to send out sensitive data in other HS's events in this way.</p>
<p>Suppose we discover after resync that we shouldn't have sent out one our events (not a prev_event) to a target HS. Not much we can do.
What about if we didn't send them an event but shouldn't've?
E.g. what if someone joined from a new HS shortly after you did? We wouldn't talk to them.
Could imagine sending out the "Missed" events after the resync but... painful to work out what they should have seen if they joined/left.
Instead, just send them the latest event (if they're still in the room after resync) and let them backfill.(?)</p>
<ul>
<li>Don't do this currently.</li>
<li>If anyone who has received our messages sends a message to a HS we missed, they can backfill our messages</li>
<li>Gap: rooms which are infrequently used and take a long time to resync.</li>
</ul>
<h3 id="joining-after-a-partial-join"><a class="header" href="#joining-after-a-partial-join">Joining after a partial join</a></h3>
<p><strong>NB.</strong> Not yet implemented.</p>
<details>
<p><strong>TODO:</strong> needs prose fleshing out. Liase with Matthieu. Explain why /send_join
(Rich was surprised we didn't just create it locally. Answer: to try and avoid
a join which then gets rejected after resync.)</p>
<p>We don't know for sure that any join we create would be accepted.
E.g. the joined user might have been banned; the join rules might have changed in a way that we didn't realise... some way in which the partial state was mistaken.
Instead, do another partial make-join/send-join handshake to confirm that the join works.</p>
<ul>
<li>Probably going to get a bunch of duplicate state events and auth events.... but the point of partial joins is that these should be small. Many are already persisted = good.</li>
<li>What if the second send_join response includes a different list of reisdent HSes? Could ignore it.
<ul>
<li>Could even have a special flag that says "just make me a join", i.e. don't bother giving me state or servers in room. Deffo want the auth chain tho.</li>
</ul>
</li>
<li>SQ: wrt device lists it's a lot safer to ignore it!!!!!</li>
<li>What if the state at the second join is inconsistent with what we have? Ignore it?</li>
</ul>
</details>
<h3 id="leaving-and-kicks-and-bans-after-a-partial-join"><a class="header" href="#leaving-and-kicks-and-bans-after-a-partial-join">Leaving (and kicks and bans) after a partial join</a></h3>
<p><strong>NB.</strong> Not yet implemented.</p>
<details>
<p>When you're fully joined to a room, to have <code>U</code> leave a room their homeserver
needs to</p>
<ul>
<li>create a new leave event for <code>U</code> which will be accepted by other homeservers,
and</li>
<li>send that event <code>U</code> out to the homeservers in the federation.</li>
</ul>
<p>When is a leave event accepted? See
<a href="https://spec.matrix.org/v1.5/rooms/v10/#authorization-rules">v10 auth rules</a>:</p>
<blockquote>
<ol start="4">
<li>If type is m.room.member: [...]
>
> 5. If membership is leave:
>
> 1. If the sender matches state_key, allow if and only if that user’s current membership state is invite, join, or knock.
2. [...]</li>
</ol>
</blockquote>
<p>I think this means that (well-formed!) self-leaves are governed entirely by
4.5.1. This means that if we correctly calculate state which says that <code>U</code> is
invited, joined or knocked and include it in the leave's auth events, our event
is accepted by checks 4 and 5 on incoming events.</p>
<blockquote>
<ol start="4">
<li>Passes authorization rules based on the event’s auth events, otherwise
> it is rejected.</li>
<li>Passes authorization rules based on the state before the event, otherwise
> it is rejected.</li>
</ol>
</blockquote>
<p>The only way to fail check 6 is if the receiving server's current state of the
room says that <code>U</code> is banned, has left, or has no membership event. But this is
fine: the receiving server already thinks that <code>U</code> isn't in the room.</p>
<blockquote>
<ol start="6">
<li>Passes authorization rules based on the current state of the room,
> otherwise it is “soft failed”.</li>
</ol>
</blockquote>
<p>For the second point (publishing the leave event), the best thing we can do is
to is publish to all HSes we know to be currently in the room. If they miss that
event, they might send us traffic in the room that we don't care about. This is
a problem with leaving after a "full" join; we don't seek to fix this with
partial joins.</p>
<p>(With that said: there's nothing machine-readable in the /send response. I don't
think we can deduce "destination has left the room" from a failure to /send an
event into that room?)</p>
<h4 id="can-we-still-do-this-during-a-partial-join"><a class="header" href="#can-we-still-do-this-during-a-partial-join">Can we still do this during a partial join?</a></h4>
<p>We can create leave events and can choose what gets included in our auth events,
so we can be sure that we pass check 4 on incoming events. For check 5, we might
have an incorrect view of the state before an event.
The only way we might erroneously think a leave is valid is if</p>
<ul>
<li>the partial state before the leave has <code>U</code> joined, invited or knocked, but</li>
<li>the full state before the leave has <code>U</code> banned, left or not present,</li>
</ul>
<p>in which case the leave doesn't make anything worse: other HSes already consider
us as not in the room, and will continue to do so after seeing the leave.</p>
<p>The remaining obstacle is then: can we safely broadcast the leave event? We may
miss servers or incorrectly think that a server is in the room. Or the
destination server may be offline and miss the transaction containing our leave
event.This should self-heal when they see an event whose <code>prev_events</code> descends
from our leave.</p>
<p>Another option we considered was to use federation <code>/send_leave</code> to ask a
fully-joined server to send out the event on our behalf. But that introduces
complexity without much benefit. Besides, as Rich put it,</p>
<blockquote>
<p>sending out leaves is pretty best-effort currently</p>
</blockquote>
<p>so this is probably good enough as-is.</p>
<h4 id="cleanup-after-the-last-leave"><a class="header" href="#cleanup-after-the-last-leave">Cleanup after the last leave</a></h4>
<p><strong>TODO</strong>: what cleanup is necessary? Is it all just nice-to-have to save unused
work?</p>
</details>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="../../tcp_replication.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="../../development/internal_documentation/index.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="../../tcp_replication.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="../../development/internal_documentation/index.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
</nav>
</div>
<script type="text/javascript">
window.playground_copyable = true;
</script>
<script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
<script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
<script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>
<script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
<script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
<script src="../../book.js" type="text/javascript" charset="utf-8"></script>
<!-- Custom JS scripts -->
<script type="text/javascript" src="../../docs/website_files/table-of-contents.js"></script>
<script type="text/javascript" src="../../docs/website_files/version-picker.js"></script>
<script type="text/javascript" src="../../docs/website_files/version.js"></script>
</body>
</html>
|
