Locality-Based Least-Connection Scheduling module for nginx

README

Locality-based Least connection scheduling module for nginx.

Based on logic[1] from IPVS lblc module.

[1] http://kb.linuxvirtualserver.org/wiki/Locality-Based_Least-Connection_Scheduling

Configuration directives:

    lblc

        Scope: upstream

        Switches upstream to use lblc connection scheduling

Sample configuration:

    upstream memd {
        server 127.0.0.1:11211;
        server 10.0.0.2:11211;
        lblc;
        keepalive 10;
    }

To compile nginx with lblc module, use "--add-module <path>" option to nginx
configure.

config

ngx_addon_name="ngx_http_upstream_lblc_module"

HTTP_MODULES="$HTTP_MODULES \
	ngx_http_upstream_lblc_module"

NGX_ADDON_SRCS="$NGX_ADDON_SRCS \
	$ngx_addon_dir/ngx_http_upstream_lblc_module.c"

ngx_http_upstream_lblc_module.c

/*
 * Copyright (C) Dropbox
 * Copyright (C) Maxim Dounin
 * Copyright (C) Nginx, Inc.
 */


#include <ngx_config.h>
#include <ngx_core.h>
#include <ngx_http.h>


typedef struct {
    ngx_uint_t                        *conns;
    ngx_int_t                          offset;
} ngx_http_upstream_lblc_conf_t;


typedef struct {
    /* the round robin data must be first */
    ngx_http_upstream_rr_peer_data_t   rrp;

    ngx_uint_t                        *conns;

    ngx_event_get_peer_pt              get_rr_peer;
    ngx_event_free_peer_pt             free_rr_peer;

    ngx_int_t                          offset;
} ngx_http_upstream_lblc_peer_data_t;

static ngx_int_t ngx_http_upstream_init_lblc_peer(ngx_http_request_t *r,
    ngx_http_upstream_srv_conf_t *us);
static ngx_int_t ngx_http_upstream_get_lblc_peer(
    ngx_peer_connection_t *pc, void *data);
static ngx_int_t ngx_http_upstream_get_least_conn_peer(
    ngx_peer_connection_t *pc, void *data);
static void ngx_http_upstream_free_lblc_peer(ngx_peer_connection_t *pc,
    void *data, ngx_uint_t state);
static void *ngx_http_upstream_lblc_create_conf(ngx_conf_t *cf);
static char *ngx_http_upstream_lblc(ngx_conf_t *cf, ngx_command_t *cmd,
    void *conf);


static ngx_command_t  ngx_http_upstream_lblc_commands[] = {

    { ngx_string("lblc"),
      NGX_HTTP_UPS_CONF|NGX_CONF_NOARGS,
      ngx_http_upstream_lblc,
      0,
      0,
      NULL },

      ngx_null_command
};


static ngx_http_module_t  ngx_http_upstream_lblc_module_ctx = {
    NULL,                                  /* preconfiguration */
    NULL,                                  /* postconfiguration */

    NULL,                                  /* create main configuration */
    NULL,                                  /* init main configuration */

    ngx_http_upstream_lblc_create_conf,    /* create server configuration */
    NULL,                                  /* merge server configuration */

    NULL,                                  /* create location configuration */
    NULL                                   /* merge location configuration */
};


ngx_module_t  ngx_http_upstream_lblc_module = {
    NGX_MODULE_V1,
    &ngx_http_upstream_lblc_module_ctx,    /* module context */
    ngx_http_upstream_lblc_commands,       /* module directives */
    NGX_HTTP_MODULE,                       /* module type */
    NULL,                                  /* init master */
    NULL,                                  /* init module */
    NULL,                                  /* init process */
    NULL,                                  /* init thread */
    NULL,                                  /* exit thread */
    NULL,                                  /* exit process */
    NULL,                                  /* exit master */
    NGX_MODULE_V1_PADDING
};


static ngx_int_t
ngx_http_upstream_init_lblc(ngx_conf_t *cf,
    ngx_http_upstream_srv_conf_t *us)
{
    ngx_uint_t                            n;
    ngx_http_upstream_rr_peers_t         *peers;
    ngx_http_upstream_lblc_conf_t        *lcf;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, cf->log, 0,
                   "init lblc");

    if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
        return NGX_ERROR;
    }

    peers = us->peer.data;

    n = peers->number;

    if (peers->next) {
        n += peers->next->number;
    }

    lcf = ngx_http_conf_upstream_srv_conf(us,
                                          ngx_http_upstream_lblc_module);

    lcf->conns = ngx_pcalloc(cf->pool, sizeof(ngx_uint_t) * n);
    if (lcf->conns == NULL) {
        return NGX_ERROR;
    }

    us->peer.init = ngx_http_upstream_init_lblc_peer;
    lcf->offset = ngx_random() % peers->number;

    return NGX_OK;
}


static ngx_int_t
ngx_http_upstream_init_lblc_peer(ngx_http_request_t *r,
    ngx_http_upstream_srv_conf_t *us)
{
    ngx_http_upstream_lblc_peer_data_t     *lcp;
    ngx_http_upstream_lblc_conf_t  *lcf;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
                   "init lblc peer");

    lcf = ngx_http_conf_upstream_srv_conf(us,
                                          ngx_http_upstream_lblc_module);

    lcp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_lblc_peer_data_t));
    if (lcp == NULL) {
        return NGX_ERROR;
    }

    lcp->conns = lcf->conns;
    lcp->offset = lcf->offset;

    r->upstream->peer.data = &lcp->rrp;

    if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
        return NGX_ERROR;
    }

    r->upstream->peer.get = ngx_http_upstream_get_lblc_peer;
    r->upstream->peer.free = ngx_http_upstream_free_lblc_peer;

    lcp->get_rr_peer = ngx_http_upstream_get_round_robin_peer;
    lcp->free_rr_peer = ngx_http_upstream_free_round_robin_peer;

    return NGX_OK;
}

static ngx_int_t
ngx_http_upstream_get_lblc_peer(ngx_peer_connection_t *pc,
    void *data)
{
    ngx_http_upstream_lblc_peer_data_t  *lcp = data;

    time_t                         now;
    ngx_uint_t                     i, j, p;
    ngx_http_upstream_rr_peer_t   *peer, *best;
    ngx_http_upstream_rr_peers_t  *peers;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "get lblc peer");

    if (lcp->rrp.peers->single) {
        return lcp->get_rr_peer(pc, &lcp->rrp);
    }

    pc->cached = 0;
    pc->connection = NULL;

    now = ngx_time();

    peers = lcp->rrp.peers;

    best = NULL;

#if (NGX_SUPPRESS_WARN)
    p = 0;
#endif

    for (i = lcp->offset, j = 0;
         j < peers->number;
         i = (i + 1) % peers->number, j++)
    {

        peer = &peers->peer[i];

        if (peer->down) {
            continue;
        }

        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            continue;
        }

        if ((ngx_int_t)lcp->conns[i] < peer->weight) {
            best = peer;
            p = i;
            break;
        }
    }

    if (best == NULL) {
        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get lblc peer: no peer found");
        return ngx_http_upstream_get_least_conn_peer(pc, lcp);
    }

    if (now - best->checked > best->fail_timeout) {
        best->checked = now;
    }

    pc->sockaddr = best->sockaddr;
    pc->socklen = best->socklen;
    pc->name = &best->name;

    lcp->rrp.current = p;
    lcp->conns[p]++;

    return NGX_OK;
}

static ngx_int_t
ngx_http_upstream_get_least_conn_peer(ngx_peer_connection_t *pc, void *data)
{
    ngx_http_upstream_lblc_peer_data_t  *lcp = data;

    time_t                         now;
    ngx_int_t                      rc, total;
    ngx_uint_t                     i, j, p, many;
    ngx_http_upstream_rr_peer_t   *peer, *best;
    ngx_http_upstream_rr_peers_t  *peers;

    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "get least conn peer, try: %ui", pc->tries);

    if (lcp->rrp.peers->single) {
        return lcp->get_rr_peer(pc, &lcp->rrp);
    }

    pc->cached = 0;
    pc->connection = NULL;

    now = ngx_time();

    peers = lcp->rrp.peers;

    best = NULL;
    total = 0;

#if (NGX_SUPPRESS_WARN)
    many = 0;
    p = 0;
#endif

    for (i = lcp->offset, j = 0;
         j < peers->number;
         i = (i + 1) % peers->number, j++)
    {

        peer = &peers->peer[i];

        if (peer->down) {
            continue;
        }

        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            continue;
        }

        /*
         * select peer with least number of connections; if there are
         * multiple peers with the same number of connections, select
         * based on wlc
         */

        if (best == NULL
            || lcp->conns[i] * best->weight < lcp->conns[p] * peer->weight)
        {
            best = peer;
            many = 0;
            p = i;

        } else if (lcp->conns[i] * best->weight
                   == lcp->conns[p] * peer->weight)
        {
            many = 1;
        }
    }

    if (best == NULL) {
        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get least conn peer, no peer found");

        goto failed;
    }

    if (many) {
        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get least conn peer, many");

            for (i = p, j = 0;
                 j < peers->number;
                 i = (i + 1) % peers->number, j++)
            {

            peer = &peers->peer[i];

            if (peer->down) {
                continue;
            }

            if (lcp->conns[i] * best->weight != lcp->conns[p] * peer->weight) {
                continue;
            }

            if (peer->max_fails
                && peer->fails >= peer->max_fails
                && now - peer->checked <= peer->fail_timeout)
            {
                continue;
            }

            peer->current_weight += peer->effective_weight;
            total += peer->effective_weight;

            if (peer->effective_weight < peer->weight) {
                peer->effective_weight++;
            }

            if (peer->current_weight > best->current_weight) {
                best = peer;
                p = i;
            }
        }
    }

    best->current_weight -= total;

    if (now - best->checked > best->fail_timeout) {
        best->checked = now;
    }

    pc->sockaddr = best->sockaddr;
    pc->socklen = best->socklen;
    pc->name = &best->name;

    lcp->rrp.current = p;
    lcp->conns[p]++;

    return NGX_OK;

failed:

    if (peers->next) {
        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get least conn peer, backup servers");

        lcp->conns += peers->number;

        lcp->rrp.peers = peers->next;
        lcp->offset = 0;

        rc = ngx_http_upstream_get_least_conn_peer(pc, lcp);

        if (rc != NGX_BUSY) {
            return rc;
        }
    }

    /* all peers failed, mark them as live for quick recovery */

    for (i = 0; i < peers->number; i++) {
        peers->peer[i].fails = 0;
    }

    pc->name = peers->name;

    return NGX_BUSY;
}


static void
ngx_http_upstream_free_lblc_peer(ngx_peer_connection_t *pc,
    void *data, ngx_uint_t state)
{
    ngx_http_upstream_lblc_peer_data_t  *lcp = data;

    ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "free lblc peer %ui %ui", pc->tries, state);

    if (lcp->rrp.peers->single) {
        lcp->free_rr_peer(pc, &lcp->rrp, state);
        return;
    }

    lcp->conns[lcp->rrp.current]--;

    lcp->free_rr_peer(pc, &lcp->rrp, state);
}


static void *
ngx_http_upstream_lblc_create_conf(ngx_conf_t *cf)
{
    ngx_http_upstream_lblc_conf_t  *conf;

    conf = ngx_pcalloc(cf->pool,
                       sizeof(ngx_http_upstream_lblc_conf_t));
    if (conf == NULL) {
        return NULL;
    }

    /*
     * set by ngx_pcalloc():
     *
     *     conf->conns = NULL;
     */

    return conf;
}


static char *
ngx_http_upstream_lblc(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{
    ngx_http_upstream_srv_conf_t  *uscf;

    uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);

    if (uscf->peer.init_upstream) {
        ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
                           "load balancing method redefined");
    }

    uscf->peer.init_upstream = ngx_http_upstream_init_lblc;

    uscf->flags = NGX_HTTP_UPSTREAM_CREATE
                  |NGX_HTTP_UPSTREAM_WEIGHT
                  |NGX_HTTP_UPSTREAM_MAX_FAILS
                  |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
                  |NGX_HTTP_UPSTREAM_DOWN
                  |NGX_HTTP_UPSTREAM_BACKUP;

    return NGX_CONF_OK;
}