ViewVC logotype

Contents of /ircd-hybrid/doc/LazyLinks.txt

Parent Directory Parent Directory | Revision Log Revision Log

Revision 30 - (show annotations)
Sun Oct 2 20:03:27 2005 UTC (14 years, 2 months ago) by adx
File MIME type: text/plain
File size: 9173 byte(s)
- imported sources
- can be moved later according to the directory/branching scheme,
  but we need the svn up

1 $Id: LazyLinks.txt,v 1.3 2003/10/13 02:15:18 metalrock Exp $
2 Lazy Links
3 ==========
4 (Ideas by Dianora and orabidoo; initial spec by orabidoo)
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.
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.
18 In the rest of this text, we assume that the local network configuration
19 looks like this:
22 LLL <---> HUB <---> OH <---> ....
23 ^
24 |
25 v
26 ALL
28 where LLL and ALL are Lazy Link Leaves, Hub is a Hub, and OH is another
29 hub.
32 1) Channels
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.
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.
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.)
58 1.1) Joining
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
67 [LLL -> HUB] :LLL SJOIN LLL_TS #channel :@LLLuser
68 [LLL -> LLLuser] :LLLuser JOIN #channel
70 When HUB gets a SJOIN from LLL, it needs to do a lot of the deciding that
71 normally goes into m_join:
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.
77 otherwise:
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
82 in this case, LLL's bit doesn't get set for #channel on HUB.
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
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
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.
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:
101 [LLL --> LLLuser] :HUB MODE #channel +o LLLuser
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.
108 1.2) Bursts
110 The beauty of this is that, with the rules above, channel bursts get
111 avoided, without the need to do anything more.
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.
120 1.3) Parts, Kicks and Modes
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.
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:
129 [LLL -> HUB] :LLL DROP #channel
131 Upon receiving a "DROP" command from a Lazy Leaf, the Hub just clears
132 the Lazy Leaf's bit on that channel.
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.
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.
142 For MODE changes related to #channel and done by local users on LLL,
143 LLL just passes them as usual to HUB.
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:
148 [LLL --> HUB] :LLLuser MODE #channel
149 [HUB --> LLL] :HUB (numeric) #channel modes
152 2) Nicks
154 Nicks are simpler, because they are atomic, there is no list associated
155 with them.
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.
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.
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.
170 2.1) WHOIS
172 For simplicity, we could kill multiple-destination WHOIS, if that's not
173 already done, and all kinds of WHOIS *pattern*.
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:
178 [LLL --> HUB] :LLLuser WHOIS Somenick
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.
184 [HUB --> LLL] :HUB (numerics) WHOIS info
185 [HUB --> LLL] NICK nickTS Somenick HopCount Umode ......
188 2.2) NOTIFY and USERHOST
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.
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.
203 2.3) PRIVMSG and NOTICE
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.
209 Same for NOTICE.
212 2.4) Anything else???
214 We've missed a bunch here... NAMES, WHO, TRACE, and probably others I
215 can't think of.
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.
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).
225 for TRACE, if the nick is locally unknown, just pass the thing to HUB
226 and let it deal with it.
229 4) Avoiding Desyncs
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.
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).


Name Value
svn:eol-style native
svn:keywords "Id Revision"

ViewVC Help
Powered by ViewVC 1.1.26