e19998108929dc6c10b091681b040faa933135de
[l2tpns.git] / INTERNALS
1 Documentation on various internal structures.
2
3 Most important structure use an anonymous shared mmap()
4 so that child processes can watch them. (All the cli connections
5 are handled in child processes).
6
7 TODO: Re-investigate threads to see if we can use a thread to handle
8 cli connections without killing forwarding performance.
9
10 session[]
11         An array of session structures. This is one of the two
12         major data structures that are sync'ed across the cluster.
13
14         This array is statically allocated at startup time to a 
15         compile time size (currently 50k sessions). This sets a
16         hard limit on the number of sessions a cluster can handle.
17
18         There is one element per l2tp session. (I.e. each active user).
19
20         The zero'th session is always invalid.
21
22 tunnel[]
23         An array of tunnel structures. This is the other major data structure
24         that's actively sync'ed across the cluster.
25
26         As per sessions, this is statically allocated at startup time
27         to a compile time size limit.
28
29         There is one element per l2tp tunnel. (normally one per BRAS
30         that this cluster talks to).
31
32         The zero'th tunnel is always invalid.
33
34 ip_pool[]
35         
36         A table holding all the IP address in the pool. As addresses
37         are used, they are tagged with the username of the session,
38         and the session index.
39
40         When they are free'd the username tag ISN'T cleared. This is
41         to ensure that were possible we re-allocate the same IP
42         address back to the same user.
43
44 radius[]
45         A table holding active radius session. Whenever a radius
46         conversation is needed (login, accounting et al), a radius
47         session is allocated.
48
49 char **ip_hash
50
51         A mapping of IP address to session structure. This is a
52         tenary tree (each byte of the IP address is used in turn
53         to index that level of the tree).
54
55         If the value is postive, it's considered to be an index
56         into the session table. 
57
58         If it's negative, it's considered to be an index into
59         the ip_pool[] table.
60
61         If it's zero, then there is no associated value.
62         
63
64
65 ============================================================
66
67 Clustering: How it works.
68
69         At a high level, the various members of the cluster elect
70 a master. All other machines become slaves. Slaves handle normal
71 packet forwarding. Whenever a slave get a 'state changing' packet
72 (i.e. tunnel setup/teardown, session setup etc) it _doesn't_ handle
73 it, but instead forwards it to the master.
74
75         'State changing' it defined to be "a packet that would cause
76 a change in either a session or tunnel structure that isn't just
77 updating the idle time or byte counters". In practise, this means
78 also all LCP, IPCP, and L2TP control packets.
79
80         The master then handles the packet normally, updating
81 the session/tunnel structures. The changed structures are then
82 flooded out to the slaves via a multicast packet.
83
84
85 Heartbeat'ing:
86         The master sends out a multicast 'heartbeat' packet
87 at least once every second. This packet contains a sequence number,
88 and any changes to the session/tunnel structures that have
89 been queued up. If there is room in the packet, it also sends
90 out a number of extra session/tunnel structures.
91
92         The sending out of 'extra' structures means that the
93 master will slowly walk the entire session and tunnel tables.
94 This allows a new slave to catch-up on cluster state.
95
96
97         Each heartbeat has an in-order sequence number. If a
98 slave receives a heartbeat with a sequence number other than 
99 the one it was expecting, it drops the unexpected packet and
100 unicasts C_LASTSEEN to tell the master the last heartbeast it
101 had seen. The master normally than unicasts the missing packets
102 to the slave. If the master doesn't have the old packet any more
103 (i.e. it's outside the transmission window) then the master
104 unicasts C_KILL to the slave asking it to die. (it should then
105 restart, and catchup on state via the normal process).
106
107 Ping'ing:
108         All slaves send out a 'ping' once per second as a
109 multicast packet. This 'ping' contains the slave's ip address,
110 and most importantly: The number of seconds from epoch
111 that the slave started up. (I.e. the value of time(2) at
112 that the process started).
113
114
115 Elections:
116
117         All machines start up as slaves.
118
119         Each slave listens for a heartbeat from the master.
120 If a slave fails to hear a heartbeat for N seconds then it
121 checks to see if it should become master.
122
123         A slave will become master if:
124                 * It hasn't heard from a master for N seconds.
125                 * It is the oldest of all it's peers (the other slaves).
126                 * In the event of a tie, the machine with the
127                         lowest IP address will win.
128
129         A 'peer' is any other slave machine that's send out a
130         ping in the last N seconds. (i.e. we must have seen
131         a recent ping from that slave for it to be considered).
132
133         The upshot of this is that no special communication
134         takes place when a slave becomes a master.
135
136         On initial cluster startup, the process would be (for example)
137
138                 * 3 machines startup simultaneously, all as slaves.
139                 * each machine sends out a multicast 'ping' every second.
140                 * 15 seconds later, the machine with the lowest IP
141                         address becomes master, and starts sending
142                         out heartbeats.
143                 * The remaining two machine hear the heartbeat and
144                         set that machine as their master.
145
146 Becoming master:
147         
148         When a slave become master, the only structure maintained up
149         to date are the tunnel and session structures. This means
150         the master will rebuild a number of mappings.
151
152         #0. All the session and table structures are marked as
153         defined. (Even if we weren't fully up to date, it's
154         too late now).
155
156         #1. All the token bucket filters are re-build from scratch
157         with the associated session to tbf pointers being re-built.
158
159 TODO: These changed tbf pointers aren't flooded to the slave right away!
160 Throttled session could take a couple of minutes to start working again
161 on master failover!
162
163         #2. The ipcache to session hash is rebuilt. (This isn't
164         strictly needed, but it's a safety measure).
165
166         #3. The mapping from the ippool into the session table
167         (and vice versa) is re-built.
168
169
170 Becoming slave:
171
172         At startup the entire session and table structures are
173         marked undefined.
174
175         As it seens updates from the master, the updated structures
176         are marked as defined.
177
178         When there are no undefined tunnel or session structures, the
179         slave marks itself as 'up-to-date' and starts advertising routes
180         (if BGP is enabled).