Add INTERNALS file
authorDavid Parrish <david@dparrish.com>
Mon, 28 Jun 2004 02:21:20 +0000 (02:21 +0000)
committerDavid Parrish <david@dparrish.com>
Mon, 28 Jun 2004 02:21:20 +0000 (02:21 +0000)
INTERNALS [new file with mode: 0644]

diff --git a/INTERNALS b/INTERNALS
new file mode 100644 (file)
index 0000000..e199981
--- /dev/null
+++ b/INTERNALS
@@ -0,0 +1,180 @@
+Documentation on various internal structures.
+
+Most important structure use an anonymous shared mmap()
+so that child processes can watch them. (All the cli connections
+are handled in child processes).
+
+TODO: Re-investigate threads to see if we can use a thread to handle
+cli connections without killing forwarding performance.
+
+session[]
+       An array of session structures. This is one of the two
+       major data structures that are sync'ed across the cluster.
+
+       This array is statically allocated at startup time to a 
+       compile time size (currently 50k sessions). This sets a
+       hard limit on the number of sessions a cluster can handle.
+
+       There is one element per l2tp session. (I.e. each active user).
+
+       The zero'th session is always invalid.
+
+tunnel[]
+       An array of tunnel structures. This is the other major data structure
+       that's actively sync'ed across the cluster.
+
+       As per sessions, this is statically allocated at startup time
+       to a compile time size limit.
+
+       There is one element per l2tp tunnel. (normally one per BRAS
+       that this cluster talks to).
+
+       The zero'th tunnel is always invalid.
+
+ip_pool[]
+       
+       A table holding all the IP address in the pool. As addresses
+       are used, they are tagged with the username of the session,
+       and the session index.
+
+       When they are free'd the username tag ISN'T cleared. This is
+       to ensure that were possible we re-allocate the same IP
+       address back to the same user.
+
+radius[]
+       A table holding active radius session. Whenever a radius
+       conversation is needed (login, accounting et al), a radius
+       session is allocated.
+
+char **ip_hash
+
+       A mapping of IP address to session structure. This is a
+       tenary tree (each byte of the IP address is used in turn
+       to index that level of the tree).
+
+       If the value is postive, it's considered to be an index
+       into the session table. 
+
+       If it's negative, it's considered to be an index into
+       the ip_pool[] table.
+
+       If it's zero, then there is no associated value.
+       
+
+
+============================================================
+
+Clustering: How it works.
+
+       At a high level, the various members of the cluster elect
+a master. All other machines become slaves. Slaves handle normal
+packet forwarding. Whenever a slave get a 'state changing' packet
+(i.e. tunnel setup/teardown, session setup etc) it _doesn't_ handle
+it, but instead forwards it to the master.
+
+       'State changing' it defined to be "a packet that would cause
+a change in either a session or tunnel structure that isn't just
+updating the idle time or byte counters". In practise, this means
+also all LCP, IPCP, and L2TP control packets.
+
+       The master then handles the packet normally, updating
+the session/tunnel structures. The changed structures are then
+flooded out to the slaves via a multicast packet.
+
+
+Heartbeat'ing:
+       The master sends out a multicast 'heartbeat' packet
+at least once every second. This packet contains a sequence number,
+and any changes to the session/tunnel structures that have
+been queued up. If there is room in the packet, it also sends
+out a number of extra session/tunnel structures.
+
+       The sending out of 'extra' structures means that the
+master will slowly walk the entire session and tunnel tables.
+This allows a new slave to catch-up on cluster state.
+
+
+       Each heartbeat has an in-order sequence number. If a
+slave receives a heartbeat with a sequence number other than 
+the one it was expecting, it drops the unexpected packet and
+unicasts C_LASTSEEN to tell the master the last heartbeast it
+had seen. The master normally than unicasts the missing packets
+to the slave. If the master doesn't have the old packet any more
+(i.e. it's outside the transmission window) then the master
+unicasts C_KILL to the slave asking it to die. (it should then
+restart, and catchup on state via the normal process).
+
+Ping'ing:
+       All slaves send out a 'ping' once per second as a
+multicast packet. This 'ping' contains the slave's ip address,
+and most importantly: The number of seconds from epoch
+that the slave started up. (I.e. the value of time(2) at
+that the process started).
+
+
+Elections:
+
+       All machines start up as slaves.
+
+       Each slave listens for a heartbeat from the master.
+If a slave fails to hear a heartbeat for N seconds then it
+checks to see if it should become master.
+
+       A slave will become master if:
+               * It hasn't heard from a master for N seconds.
+               * It is the oldest of all it's peers (the other slaves).
+               * In the event of a tie, the machine with the
+                       lowest IP address will win.
+
+       A 'peer' is any other slave machine that's send out a
+       ping in the last N seconds. (i.e. we must have seen
+       a recent ping from that slave for it to be considered).
+
+       The upshot of this is that no special communication
+       takes place when a slave becomes a master.
+
+       On initial cluster startup, the process would be (for example)
+
+               * 3 machines startup simultaneously, all as slaves.
+               * each machine sends out a multicast 'ping' every second.
+               * 15 seconds later, the machine with the lowest IP
+                       address becomes master, and starts sending
+                       out heartbeats.
+               * The remaining two machine hear the heartbeat and
+                       set that machine as their master.
+
+Becoming master:
+       
+       When a slave become master, the only structure maintained up
+       to date are the tunnel and session structures. This means
+       the master will rebuild a number of mappings.
+
+       #0. All the session and table structures are marked as
+       defined. (Even if we weren't fully up to date, it's
+       too late now).
+
+       #1. All the token bucket filters are re-build from scratch
+       with the associated session to tbf pointers being re-built.
+
+TODO: These changed tbf pointers aren't flooded to the slave right away!
+Throttled session could take a couple of minutes to start working again
+on master failover!
+
+       #2. The ipcache to session hash is rebuilt. (This isn't
+       strictly needed, but it's a safety measure).
+
+       #3. The mapping from the ippool into the session table
+       (and vice versa) is re-built.
+
+
+Becoming slave:
+
+       At startup the entire session and table structures are
+       marked undefined.
+
+       As it seens updates from the master, the updated structures
+       are marked as defined.
+
+       When there are no undefined tunnel or session structures, the
+       slave marks itself as 'up-to-date' and starts advertising routes
+       (if BGP is enabled).