Squid load-balancing and failover, way-prototype

From: <richard@dont-contact.us>
Date: Mon, 9 Oct 2000 04:40:34 +1100 (EST)

Ok, been workin away down here. Warning: this is hacked up code, it is not
even beta quality, however it does work (beta functionality, pre-alpha
style :) Patch is against squid-2.3.STABLE4

The reason for this posting is to aquire ideas and comments on the
direction implementation should go from here, now that we have proof of
concept. A run-down of the code follows.

Tasks:

1. To load-balance incoming requests across a set of defined servers while
   in accelerator mode.

2. To detect obvious failure within those servers and seamlessly move the
   server out of the balance group until it has recovered.

Implementation:

A new file, balance.c, contains the bulk of the code, three functions, an
initialiser, which initialises a single-headed, doubly linked list with
the contents, one per node, of the wordlist pulled from the configuration
file option (added) "httpd_accel_balance_targets", used as shown:

httpd_accel_balance_targets 192.168.1.1 192.168.1.2 192.168.1.3

The second function, balance_get_target(), is called from
fwdConnectStart() in forward.c and returns the hostname of the next
available target that does not have a dead_until field greater than
squid_curtime. In more advanced balancing scenarios, this would do more
calculations than its current round-robin implementation.

The third function, balance_mark_fail() is called from fwdFail(), and
marks the given host as dead_until 60 seconds from squid_curtime.

Result:

When any request is made that cannot be satisfied by the cache, the next
hostname in the balance list is pulled from balance_get_target(). A
connection is then made via the standard squid methods to that host (note
that because of its late entry point, this does not affect virtual host
engines etc, it will work fine with systems requiring the browser-supplied
HTTP Host: field). Should that connection succeed, squid proceeds as
normal, and the next connection requested will go to the next host etc.

Should the connection fail for any reason, the host targeted in that
request (as specified in fwdState->request->hier.host for lack of anywhere
else that seemed to have the information) is marked dead. fwdFail then
proceeds on its normal handling, in the cases tested so far, this is
normally to retry the request once more, thus pulling a new hostname from
balance_get_target() and, in the case of individual server failure,
successfully retrieving the requested url from a new, unaffected system.

Code is in place to return a supposedly dead server in cases where all
servers have been marked dead, it can't hurt and we might be lucky :)

A server -HUP will correctly reload the balancing list from the
configuration file.

Questions:

- Does the prototype seem appropriate in the location of its hooks
  (forward.c) ?

- Is fwdState->request->hier.host reliable? remembering that this is only
  intended to run when in accelerator mode (this may well break when the
  host is in non-accelerator or dual mode at this stage).

- I have included my own linked list code out of laziness, I will
  investigate using the dnode functions in the next revision.

- Will fwdFail always retry a second time, if not, what are the conditions
  under which it will currently not retry? Some of these conditions, in a
  failover operation, would be better tried again, since a connection
  refused or similar may recover if a seperate backend server is connected
  to.

- I have used statically defined structures within balance.c to avoid
  having to extend structures in struct.h to provide storage. This will
  cause difficulties should any part of balance.c be called from another
  thread. From what I can tell, squid is explictly single-threaded except
  for the IO threading, if this is not the case please let me know :)

- Are there any further issues I should be aware of?

- Are there any other questions I forgot to ask? :)

Style issues:

My programming style seems to fit in ok with that currently in squid,
except for the fact that I use underscores as opposed to multiple-case in
function and variable names, and I do not typedef structs. For the most
part the results of this are confined to balance.c, however I will
endevour in the next revision to match the style in the rest of the code.

Richard.

diff -C 4 -N /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/balance.c ./balance.c
*** /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/balance.c Thu Jan 1 10:00:00 1970
--- ./balance.c Mon Oct 9 03:32:55 2000
***************
*** 0 ****
--- 1,87 ----
+ #include "squid.h"
+ #include "list.h"
+
+ #define STATE_OK 0
+ #define STATE_DEAD 1
+ /* Delay in seconds until next target access attempt */
+ #define DEFAULT_DELAY 60
+
+ struct bnode;
+ struct balance;
+
+ struct balance {
+ list_head_struct(balance,bnode);
+ struct bnode *previous; /* Last bnode to be returned */
+ } bal;
+
+ struct balance *b = &bal;
+
+ struct bnode {
+ list_node_struct(balance,bnode);
+ char *target;
+ int dead_until;
+ };
+
+ /* Initialise the balancing stuff */
+ void balance_init(void) {
+ struct bnode *bn;
+ wordlist *targets = Config.Accel.targets;
+ if (!targets)
+ return; /* No targets, no work, nothing to do, go away */
+ list_init(b);
+ debug(32, 1) ("balance_init: Kicking up round-robin acceleration balance engine. Phoar!\n");
+ while(targets) {
+ debug(32, 1) ("balance_init: Adding %s to balance list\n", targets->key);
+ bn = xmalloc(sizeof(struct bnode));
+ bn->dead_until = 0;
+ bn->target = xstrdup(targets->key);
+ list_append(b,bn);
+ targets = targets->next;
+ }
+ b->previous = list_first(b);
+ return;
+ };
+
+ /* Get the next target for the balance */
+ char *balance_get_target(void) {
+ struct bnode *bn;
+ bn = b->previous;
+ if (list_count(b)==1) return bn->target; /* Special case, odd use, no balancing, nothing to failover to */
+ if (node_next(bn)) { bn = node_next(bn); } else { bn=list_first(b); }
+ while (bn->dead_until>squid_curtime) {
+ if (node_next(bn)) { bn = node_next(bn); } else { bn=list_first(b); }
+ if (bn==b->previous) {
+ /* If we've gone a full loop, well, we're pretty screwed,
+ this basically means that we ran around our list of
+ hosts looking for one that is OK (dead<current time), and didn't find
+ any. Sucks to be us. We don't wanna spin tho, we'll just
+ OK the next one in the list and use it anyway, can hardly
+ do any worse :)
+ */
+ debug(32, 1) ("balance_get_target: In trouble, all nodes reported down\n");
+ if (node_next(bn)) { bn = node_next(bn); } else { bn=list_first(b); }
+ bn->dead_until = 0;
+ break;
+ }
+ }
+ debug(32, 1) ("balance_get_target: selected %s as target this time\n",bn->target);
+ b->previous = bn;
+ return bn->target; /* return a pointer to the target we selected */
+ };
+
+ /* Mark a target as having failed, setting a delay upon its reselection */
+ void balance_mark_failed(char *target) {
+ struct bnode *bn = NULL;
+ debug(32, 1) ("balance_mark_failed: Setting %s as dead\n", target);
+ /* Iterate the list looking for a bnode that has a target matching the one given */
+ list_run(b,if (!strcmp(b->op->target,target)) { bn = b->op; break; });
+ if (!bn) /* Odd, we were supplied with a target not in our list. real weird */
+ return;
+ /* Set the node dead until now+60 seconds */
+ bn->dead_until = squid_curtime+DEFAULT_DELAY;
+ };
+
+ void balance_destroy(void) {
+ /* run the list in safe mode (copy next pointer) and free all the nodes */
+ list_run_safe(b,xfree(b->op));
+ };
diff -C 4 -N /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/cf.data.pre ./cf.data.pre
*** /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/cf.data.pre Wed Jun 14 00:19:57 2000
--- ./cf.data.pre Mon Oct 9 01:41:49 2000
***************
*** 2048,2055 ****
--- 2048,2066 ----
          require the Host: header will not be properly cached.
  httpd_accel_uses_host_header off
  DOC_END
  
+ NAME: httpd_accel_balance_targets
+ TYPE: wordlist
+ LOC: Config.Accel.targets
+ DEFAULT: none
+ DOC_START
+ A list of servers that all requests will be balanced across. This
+ is a hack. Use at your own risk. Noony noony.
+
+ httpd_accel_balance_targets web1.dmz web2.dmz web3.dmz
+ DOC_END
+
  COMMENT_START
   MISCELLANEOUS
   -----------------------------------------------------------------------------
  COMMENT_END
diff -C 4 -N /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/forward.c ./forward.c
*** /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/forward.c Wed Feb 23 18:13:23 2000
--- ./forward.c Mon Oct 9 04:00:45 2000
***************
*** 232,241 ****
          port = fs->peer->http_port;
          ctimeout = fs->peer->connect_timeout > 0 ? fs->peer->connect_timeout
              : Config.Timeout.peer_connect;
      } else {
! host = fwdState->request->host;
! port = fwdState->request->port;
          ctimeout = Config.Timeout.connect;
      }
      hierarchyNote(&fwdState->request->hier, fs->code, host);
      if ((fd = pconnPop(host, port)) >= 0) {
--- 232,248 ----
          port = fs->peer->http_port;
          ctimeout = fs->peer->connect_timeout > 0 ? fs->peer->connect_timeout
              : Config.Timeout.peer_connect;
      } else {
! /* PHI balance here */
! if (Config.Accel.targets) {
! host = balance_get_target();
! /* host = Config.Accel.targets->key; */
! port = Config.Accel.port;
! } else {
! host = fwdState->request->host;
! port = fwdState->request->port;
! }
          ctimeout = Config.Timeout.connect;
      }
      hierarchyNote(&fwdState->request->hier, fs->code, host);
      if ((fd = pconnPop(host, port)) >= 0) {
***************
*** 512,519 ****
--- 519,528 ----
  void
  fwdFail(FwdState * fwdState, ErrorState * errorState)
  {
      assert(EBIT_TEST(fwdState->entry->flags, ENTRY_FWD_HDR_WAIT));
+ /* PHI */
+ balance_mark_failed(fwdState->request->hier.host);
      debug(17, 3) ("fwdFail: %s \"%s\"\n\t%s\n",
          err_type_str[errorState->type],
          httpStatusString(errorState->http_status),
          storeUrl(fwdState->entry));
diff -C 4 -N /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/list.h ./list.h
*** /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/list.h Thu Jan 1 10:00:00 1970
--- ./list.h Mon Oct 9 03:24:54 2000
***************
*** 0 ****
--- 1,27 ----
+ /***
+ *
+ * Rather strange linked list implementation :)
+ *
+ */
+
+ #define list_node_struct(ht, t) struct t *next; struct t *prev; struct ht *head;
+ #define list_head_struct(ht, t) struct t *first; struct t *last; struct t *op; struct t *op2; unsigned long count;
+
+ #define node_next(n) n->next
+ #define node_prev(n) n->prev
+ #define node_head(n) n->head
+ #define list_first(h) h->first
+ #define list_last(h) h->last
+ #define list_count(h) h->count
+ #define list_append(h, n) if (h->last) { h->last->next=n; } n->prev=h->last; n->next=NULL; h->last=n; n->head=h; if (!(h->first)) { h->first=n; n->prev=NULL; }
+ #define list_prepend(h, n) if (h->first) { h->first->prev=n; } n->next=h->first; n->prev=NULL; h->first=n; n->head=h; if (!(h->last)) { h->last=n; n->next=NULL; }
+ #define list_init(h) h->first=NULL; h->last=NULL;h->op = NULL; h->count = 0;
+
+ /* List_run is for iteration, *however* if you're doing a free(); run, you *must* use _safe, slightly
+ less efficient, but it saves the next() pointer so you don't segfault :)
+ */
+
+ #define list_run(h, c...) h->op = h->first; while (h->op) { c; h->op = h->op->next; }
+ #define list_run_safe(h, c...) h->op = h->first; while (h->op) { h->op2 = h->op->next; c; h->op = h->op2; }
+
+
diff -C 4 -N /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/main.c ./main.c
*** /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/main.c Thu Feb 10 10:29:58 2000
--- ./main.c Mon Oct 9 03:06:40 2000
***************
*** 340,347 ****
--- 340,348 ----
  #endif
      redirectShutdown();
      authenticateShutdown();
      storeDirCloseSwapLogs();
+ balance_destroy(); /* Clean up balancer */
      errorClean();
      mimeFreeMemory();
      parseConfigFile(ConfigFile);
      _db_init(Config.Log.log, Config.debugOptions);
***************
*** 351,358 ****
--- 352,360 ----
      dnsInit();
  #if !USE_DNSSERVERS
      idnsInit();
  #endif
+ balance_init(); /* Initialise balancer */
      redirectInit();
      authenticateInit();
  #if USE_WCCP
      wccpInit();
***************
*** 466,473 ****
--- 468,476 ----
      dnsInit();
  #if !USE_DNSSERVERS
      idnsInit();
  #endif
+ balance_init(); /* Initialise balancer */
      redirectInit();
      authenticateInit();
      useragentOpenLog();
      httpHeaderInitModule(); /* must go before any header processing (e.g. the one in errorInitialize) */
diff -C 4 -N /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/structs.h ./structs.h
*** /home/phirate/temp/squid/src/squid-2.3.STABLE4/src/structs.h Thu Mar 30 08:56:57 2000
--- ./structs.h Mon Oct 9 01:41:49 2000
***************
*** 326,333 ****
--- 326,334 ----
      int authenticateIpTTL;
      struct {
          char *host;
          u_short port;
+ wordlist *targets;
      } Accel;
      char *appendDomain;
      size_t appendDomainLen;
      char *debugOptions;
Received on Sun Oct 08 2000 - 11:39:08 MDT

This archive was generated by hypermail pre-2.1.9 : Tue Dec 09 2003 - 16:12:41 MST