ircd-hybrid-7.2.0/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:	306
Committed:	Fri Dec 9 05:53:03 2005 UTC (20 years, 8 months ago) by lusky
Content type:	text/plain
File size:	9117 byte(s)
Log Message:	RELEASE TAG ircd-hybrid-7.2.0
#	User	Rev	Content
1	knight	31	$Id$
2	adx	30	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).