ircd-hybrid-7.2/doc/LazyLinks.txt

$Id$
                          Lazy Links
                          ==========
        (Ideas by Dianora and orabidoo; initial spec by orabidoo)

Basic idea: leaf servers don't really need to know everything about
            every single user and channel out there;  connecting a
            new leaf server to the network should be fast, easy and
            cheap, instead of taking ages to exchange information 
            about the state of the whole network.

            The result is that we move, from a loop-less graph 
            topology, to a kind of starfish one, where hubs
            form a core (interconnected by the traditional IRC 
            protocol), and leaves are just appendages on hubs.


In the rest of this text, we assume that the local network configuration
looks like this:

                  
        LLL <---> HUB <---> OH <---> ....
                  ^
                  |
                  v
                 ALL

where LLL and ALL are Lazy Link Leaves, Hub is a Hub, and OH is another
hub.


1) Channels

Hubs, as usual, have full information about all channels, with their
membership, chanop status, TS, etc. This information is authoritative,
which means that they can use it to make decisions such as "should this
user be given ops at this point". This is just the way things are now
already. And, as usual, traditional leaves have all this information
too, and keep having it.

Lazy Leaves, OTOH, depend on their uplinks for much of their
information. They have partial information, meaning that they don't
have the full channel list. However, when they have something about a
channel, they do have *everything* about it, and their information is
authoritative, so they can decide locally on chanop matters.

For this, hubs need to know which channels each of its Lazy Leaves has.
This is necessarily a double-ended map; it can't be just a single flag
on each channel. For efficiency, it could be implemented on the hub by
adding a 32-bit int to the server-link structure, and assigning a
bitmask (one of 1, 2, 4, ... up to 0x80000000) to each of its Lazy Leaf
links.  That would support up to 32 Lazy Leaves per hub, and make it
really easy and cheap to keep this information. (The only slight
downside being that, when a Lazy Leaf link breaks, you need to clear a
bit on every single channel.)


1.1) Joining

When a client on a LLL sends a "JOIN #channel", LLL does as usual: if it
has the channel locally, it just joins the user, sends an SJOIN to HUB,
and all is well; if it doesn't have the channel, it creates it, sends a
SJOIN to HUB with the current time as the TS. LLL tells the user that it
has joined the channel, but it doesn't tell it that it has ops yet. So
LLL sends

[LLL -> HUB]     :LLL SJOIN LLL_TS #channel :@LLLuser
[LLL -> LLLuser]  :LLLuser JOIN #channel

When HUB gets a SJOIN from LLL, it needs to do a lot of the deciding that
normally goes into m_join:

     @) if LLL's bit is already set for #channel, then this is not the
        first time LLL is dealing with #channel, so just process it as
        a normal SJOIN.  
        
        otherwise:

     a) if myuser cannot join by can_join rules, send a KICK to LLL:
    [HUB --> LLL] :HUB KICK #channel LLLuser :sorry, the channel was +i
        
        in this case, LLL's bit doesn't get set for #channel on HUB.

     b) if myuser's join is OK and must be given ops (by usual TS
        rules, meaning that either LLL_TS < HUB_TS, or the channel
        is opless or didn't exist on the hub side), then HUB sends
        something back that validates the join:
    [HUB -> LLL] :HUB SJOIN OLDER_TS #channel +modes :@LLLuser +other users

     c) if myuser's join is OK but must not be given ops, the HUB
        sends the same kind of thing back, but without marking ops:
    [HUB --> LLL] :HUB SJOIN OLDER_TS #channel +modes :LLLuser @other +users

        in this case, as in case b), HUB sets LLL's bit for #channel,
        so it knows that that LLL knows about that channel now.

When LLL gets a SJOIN from its hub that includes in the userlist one of
LLL's local users, it interprets that that validates a join. If LLLuser
has ops in that list, then LLL sends:

    [LLL --> LLLuser]  :HUB MODE #channel +o LLLuser

If not, it just skips that nick from the list. In either case, it
processes the rest of the SJOIN information (modes, other nicks) by the
usual SJOIN rules.


1.2) Bursts

The beauty of this is that, with the rules above, channel bursts get
avoided, without the need to do anything more.

When LLL and HUB connect to each other, LLL sends a channel burst as
usual; HUB doesn't. By the rules above, HUB will reply to each first
LLL's SJOIN for a channel with a SJOIN back with its own info. So at the
end of the burst, LLL has been put up to date with all the channels it
needs to know about.


1.3) Parts, Kicks and Modes

When one of LLL's clients (say, LLLuser) leaves a channel, or is kicked
out of it, LLL needs to check if that was the last of its clients for
that channel.  

If that is the case, then LLL needs to inform HUB that it no longer holds
#channel, and destroy its local information about #channel:

        [LLL -> HUB]   :LLL DROP #channel

Upon receiving a "DROP" command from a Lazy Leaf, the Hub just clears
the Lazy Leaf's bit on that channel.

Alternatively, a Lazy Leaf could decide to cache channels even without
having any clients on them. All it has to do is not send the "DROP"
command to its hub.

For MODE commands coming from the rest of the net and related to
#channel, HUB only needs to pass them to LLL if LLL's bit is set for
#channel.

For MODE changes related to #channel and done by local users on LLL, 
LLL just passes them as usual to HUB.

For the special "MODE #channel" query, done on LLL, for a channel that
doesn't exist on LLL, this must be routed through HUB:

[LLL --> HUB]  :LLLuser MODE #channel
[HUB --> LLL]  :HUB (numeric) #channel modes


2) Nicks

Nicks are simpler, because they are atomic, there is no list associated
with them.

Again, the hub needs to know, for each nick, which of its Lazy Leaves
know of it. This can be done with the same 32-bit bitmask as with
servers. For each user, the associated bit is 1, unless a NICK command
has been sent or received for that user, on the given Lazy Leaf link.

Once again too, the connect burst gets reduced to just the smaller side:
the Lazy Leaf dumps its user base on the hub, but not the other way
round.

When a Lazy Leaf gets a request from one of its local clients, that
relates to a nick LLL doesn't have, this must be routed through HUB.


2.1) WHOIS

For simplicity, we could kill multiple-destination WHOIS, if that's not
already done, and all kinds of WHOIS *pattern*.

When LLLuser does "WHOIS somenick", if the nick is known to LLL, it
replies normally. If it isn't, then LLL routes it to HUB:

[LLL --> HUB]   :LLLuser WHOIS Somenick

HUB replies with the usual numeric, and also with a burst-style NICK
introduction, so that from that point on LLL knows about Somenick. HUB
also sets LLL's bit for Somenick.

[HUB --> LLL]   :HUB (numerics) WHOIS info
[HUB --> LLL]   NICK nickTS Somenick HopCount Umode ......


2.2) NOTIFY and USERHOST

These all take lists of users; for a NOTIFY or USERHOST on LLL from one
of its users, the server checks if *all* of the nicks involved are
known. If at least one isn't, then the request must be passed as such
to HUB. HUB then replies to the client, and also sends a NICK
introduction for each client that LLL didn't previously have.

Note: this kind of sucks, because most NOTIFY lines will tend to include
a nick or two that isn't on IRC at the moment, which means they will be
relayed. With almost every client out there having NOTIFY, this might
well nullify the whole advantage of nick laziness. Or maybe not.
Someone needs to do some math on it, or some testing, or both.


2.3) PRIVMSG and NOTICE

When LLLuser sends "PRIVMSG somenick :message", this must be sent to
HUB, even if somenick isn't known locally. HUB will figure it out,
and possibly send a numeric back.

Same for NOTICE.


2.4) Anything else???

We've missed a bunch here... NAMES, WHO, TRACE, and probably others I
can't think of.  

NAMES actually belongs to channels, and might as well not get routed
(just don't reply) if a LLLUser tries a NAMES for a #channel that it
isn't on, and that LLL doesn't have any info on.

for WHO, if there's a pattern, just pass the entire command to HUB and
let it reply to LLLUser through the link  (without introducing any extra
NICKs here).

for TRACE, if the nick is locally unknown, just pass the thing to HUB
and let it deal with it.


4) Avoiding Desyncs

There is one particularly treacherous potential desync: a Lazy Leaf is
convinced that it has authoritative information about a channel, but its
hub is convinced that the leaf doesn't. The hub doesn't keep sending
new information, so the leaf's info grows stale, but it keeps acting on
it, which eventually leads to wrong decisions.

It is important that the protocol ensures that such desyncs are
impossible. There should also be periodic cleanup, whereby a Lazy Leaf
scans its own channel-user list, and deletes its own information about
any channel on which it doesn't have any local users (and complains to
its opers about it, because that should never happen).
Revision:	34
Committed:	Sun Oct 2 21:05:51 2005 UTC (20 years, 10 months ago) by lusky
Content type:	text/plain
File size:	9117 byte(s)
Log Message:	create 7.2 branch, we can move/rename it as needed.
#	Content
1	$Id$
2	Lazy Links
3	==========
4	(Ideas by Dianora and orabidoo; initial spec by orabidoo)
5
6	Basic idea: leaf servers don't really need to know everything about
7	every single user and channel out there; connecting a
8	new leaf server to the network should be fast, easy and
9	cheap, instead of taking ages to exchange information
10	about the state of the whole network.
11
12	The result is that we move, from a loop-less graph
13	topology, to a kind of starfish one, where hubs
14	form a core (interconnected by the traditional IRC
15	protocol), and leaves are just appendages on hubs.
16
17
18	In the rest of this text, we assume that the local network configuration
19	looks like this:
20
21
22	LLL <---> HUB <---> OH <---> ....
23	^
24	\|
25	v
26	ALL
27
28	where LLL and ALL are Lazy Link Leaves, Hub is a Hub, and OH is another
29	hub.
30
31
32	1) Channels
33
34	Hubs, as usual, have full information about all channels, with their
35	membership, chanop status, TS, etc. This information is authoritative,
36	which means that they can use it to make decisions such as "should this
37	user be given ops at this point". This is just the way things are now
38	already. And, as usual, traditional leaves have all this information
39	too, and keep having it.
40
41	Lazy Leaves, OTOH, depend on their uplinks for much of their
42	information. They have partial information, meaning that they don't
43	have the full channel list. However, when they have something about a
44	channel, they do have everything about it, and their information is
45	authoritative, so they can decide locally on chanop matters.
46
47	For this, hubs need to know which channels each of its Lazy Leaves has.
48	This is necessarily a double-ended map; it can't be just a single flag
49	on each channel. For efficiency, it could be implemented on the hub by
50	adding a 32-bit int to the server-link structure, and assigning a
51	bitmask (one of 1, 2, 4, ... up to 0x80000000) to each of its Lazy Leaf
52	links. That would support up to 32 Lazy Leaves per hub, and make it
53	really easy and cheap to keep this information. (The only slight
54	downside being that, when a Lazy Leaf link breaks, you need to clear a
55	bit on every single channel.)
56
57
58	1.1) Joining
59
60	When a client on a LLL sends a "JOIN #channel", LLL does as usual: if it
61	has the channel locally, it just joins the user, sends an SJOIN to HUB,
62	and all is well; if it doesn't have the channel, it creates it, sends a
63	SJOIN to HUB with the current time as the TS. LLL tells the user that it
64	has joined the channel, but it doesn't tell it that it has ops yet. So
65	LLL sends
66
67	[LLL -> HUB] :LLL SJOIN LLL_TS #channel :@LLLuser
68	[LLL -> LLLuser] :LLLuser JOIN #channel
69
70	When HUB gets a SJOIN from LLL, it needs to do a lot of the deciding that
71	normally goes into m_join:
72
73	@) if LLL's bit is already set for #channel, then this is not the
74	first time LLL is dealing with #channel, so just process it as
75	a normal SJOIN.
76
77	otherwise:
78
79	a) if myuser cannot join by can_join rules, send a KICK to LLL:
80	[HUB --> LLL] :HUB KICK #channel LLLuser :sorry, the channel was +i
81
82	in this case, LLL's bit doesn't get set for #channel on HUB.
83
84	b) if myuser's join is OK and must be given ops (by usual TS
85	rules, meaning that either LLL_TS < HUB_TS, or the channel
86	is opless or didn't exist on the hub side), then HUB sends
87	something back that validates the join:
88	[HUB -> LLL] :HUB SJOIN OLDER_TS #channel +modes :@LLLuser +other users
89
90	c) if myuser's join is OK but must not be given ops, the HUB
91	sends the same kind of thing back, but without marking ops:
92	[HUB --> LLL] :HUB SJOIN OLDER_TS #channel +modes :LLLuser @other +users
93
94	in this case, as in case b), HUB sets LLL's bit for #channel,
95	so it knows that that LLL knows about that channel now.
96
97	When LLL gets a SJOIN from its hub that includes in the userlist one of
98	LLL's local users, it interprets that that validates a join. If LLLuser
99	has ops in that list, then LLL sends:
100
101	[LLL --> LLLuser] :HUB MODE #channel +o LLLuser
102
103	If not, it just skips that nick from the list. In either case, it
104	processes the rest of the SJOIN information (modes, other nicks) by the
105	usual SJOIN rules.
106
107
108	1.2) Bursts
109
110	The beauty of this is that, with the rules above, channel bursts get
111	avoided, without the need to do anything more.
112
113	When LLL and HUB connect to each other, LLL sends a channel burst as
114	usual; HUB doesn't. By the rules above, HUB will reply to each first
115	LLL's SJOIN for a channel with a SJOIN back with its own info. So at the
116	end of the burst, LLL has been put up to date with all the channels it
117	needs to know about.
118
119
120	1.3) Parts, Kicks and Modes
121
122	When one of LLL's clients (say, LLLuser) leaves a channel, or is kicked
123	out of it, LLL needs to check if that was the last of its clients for
124	that channel.
125
126	If that is the case, then LLL needs to inform HUB that it no longer holds
127	#channel, and destroy its local information about #channel:
128
129	[LLL -> HUB] :LLL DROP #channel
130
131	Upon receiving a "DROP" command from a Lazy Leaf, the Hub just clears
132	the Lazy Leaf's bit on that channel.
133
134	Alternatively, a Lazy Leaf could decide to cache channels even without
135	having any clients on them. All it has to do is not send the "DROP"
136	command to its hub.
137
138	For MODE commands coming from the rest of the net and related to
139	#channel, HUB only needs to pass them to LLL if LLL's bit is set for
140	#channel.
141
142	For MODE changes related to #channel and done by local users on LLL,
143	LLL just passes them as usual to HUB.
144
145	For the special "MODE #channel" query, done on LLL, for a channel that
146	doesn't exist on LLL, this must be routed through HUB:
147
148	[LLL --> HUB] :LLLuser MODE #channel
149	[HUB --> LLL] :HUB (numeric) #channel modes
150
151
152	2) Nicks
153
154	Nicks are simpler, because they are atomic, there is no list associated
155	with them.
156
157	Again, the hub needs to know, for each nick, which of its Lazy Leaves
158	know of it. This can be done with the same 32-bit bitmask as with
159	servers. For each user, the associated bit is 1, unless a NICK command
160	has been sent or received for that user, on the given Lazy Leaf link.
161
162	Once again too, the connect burst gets reduced to just the smaller side:
163	the Lazy Leaf dumps its user base on the hub, but not the other way
164	round.
165
166	When a Lazy Leaf gets a request from one of its local clients, that
167	relates to a nick LLL doesn't have, this must be routed through HUB.
168
169
170	2.1) WHOIS
171
172	For simplicity, we could kill multiple-destination WHOIS, if that's not
173	already done, and all kinds of WHOIS pattern.
174
175	When LLLuser does "WHOIS somenick", if the nick is known to LLL, it
176	replies normally. If it isn't, then LLL routes it to HUB:
177
178	[LLL --> HUB] :LLLuser WHOIS Somenick
179
180	HUB replies with the usual numeric, and also with a burst-style NICK
181	introduction, so that from that point on LLL knows about Somenick. HUB
182	also sets LLL's bit for Somenick.
183
184	[HUB --> LLL] :HUB (numerics) WHOIS info
185	[HUB --> LLL] NICK nickTS Somenick HopCount Umode ......
186
187
188	2.2) NOTIFY and USERHOST
189
190	These all take lists of users; for a NOTIFY or USERHOST on LLL from one
191	of its users, the server checks if all of the nicks involved are
192	known. If at least one isn't, then the request must be passed as such
193	to HUB. HUB then replies to the client, and also sends a NICK
194	introduction for each client that LLL didn't previously have.
195
196	Note: this kind of sucks, because most NOTIFY lines will tend to include
197	a nick or two that isn't on IRC at the moment, which means they will be
198	relayed. With almost every client out there having NOTIFY, this might
199	well nullify the whole advantage of nick laziness. Or maybe not.
200	Someone needs to do some math on it, or some testing, or both.
201
202
203	2.3) PRIVMSG and NOTICE
204
205	When LLLuser sends "PRIVMSG somenick :message", this must be sent to
206	HUB, even if somenick isn't known locally. HUB will figure it out,
207	and possibly send a numeric back.
208
209	Same for NOTICE.
210
211
212	2.4) Anything else???
213
214	We've missed a bunch here... NAMES, WHO, TRACE, and probably others I
215	can't think of.
216
217	NAMES actually belongs to channels, and might as well not get routed
218	(just don't reply) if a LLLUser tries a NAMES for a #channel that it
219	isn't on, and that LLL doesn't have any info on.
220
221	for WHO, if there's a pattern, just pass the entire command to HUB and
222	let it reply to LLLUser through the link (without introducing any extra
223	NICKs here).
224
225	for TRACE, if the nick is locally unknown, just pass the thing to HUB
226	and let it deal with it.
227
228
229	4) Avoiding Desyncs
230
231	There is one particularly treacherous potential desync: a Lazy Leaf is
232	convinced that it has authoritative information about a channel, but its
233	hub is convinced that the leaf doesn't. The hub doesn't keep sending
234	new information, so the leaf's info grows stale, but it keeps acting on
235	it, which eventually leads to wrong decisions.
236
237	It is important that the protocol ensures that such desyncs are
238	impossible. There should also be periodic cleanup, whereby a Lazy Leaf
239	scans its own channel-user list, and deletes its own information about
240	any channel on which it doesn't have any local users (and complains to
241	its opers about it, because that should never happen).