On 2018/5/2 22:56, Willy Tarreau wrote: > On Wed, May 02, 2018 at 04:29:33PM -0400, Patrick Hemmer wrote: >> I think you're misunderstanding my design, as scoring wouldn't work like >> this at all. If you give the gold class a score of 1000 (where higher >> number means higher priority), then the only thing that would get >> processed before gold class would be another class that has a score > >> 1000. If nothing does, and a gold request comes in, it gets processed >> first, no matter how big the queue is. >> Think of scoring as instead having multiple queues. Each queue is only >> processed if the queue before it is empty. > (...) > > OK you convinced me. Not on everything, but on the fact that we're trying > to address different points. My goal is to make it possible to improve > quality of service between good requests, and your goal is to improve the > classification between good, suspicious, and bad requests. Each of us see > how to expand a little bit our respective model to address part of the > other one (though less efficiently). > > I agree that for your goal, multi-queue is better, but I still maintain > that for my goal, the time-based queue gives better control. The good > news is that the two are orthogonal and 100% compatible. > > Basically the queueing system should be redesigned as a list of time-based > trees that are visited in order of priority (or traffic classes, we'll have > to find the proper wording to avoid confusion). If you think you can address > your needs with just a small set of different priorities, probably that we > can implement this with a small array (2-4 queues). If you think you need > more, then we'd rather think about building a composite position value in > the tree made of the priority at the top of the word and the service time > at the bottom of the word. This way, picking the first value will always > find the lowest priority value first. There's one subtlety related to > wrapping time there however, but it can be addressed in two lookups. > > Please let me know if you'd be fine with designing and implementing > something like this. > > Cheers, > Willy
I'm not quite following the need for multiple queues. Why wouldn't you just have one sorted queue, where if multiple pending requests have the same priority, then they're FIFO. I had sent another email which proposed an implementation that would satisfy both designs (https://www.mail-archive.com/haproxy@formilux.org/msg29876.html). Unfortunately I was composing it when you sent your most recent reply, so I didn't see it before I sent. I went ahead and implemented the functionality I had talked about in that other email, and have attached a WIP patch. I've done some testing on it, and it seems to work fine. The syntax is exactly as proposed: # time-based priority http-request set-priority date(20) if LOW_PRIORITY http-request set-priority date(-20) if HIGH_PRIORITY # score-based priority http-request set-priority int(20) if LOW_PRIORITY http-request set-priority int(-20) if HIGH_PRIORITY Some notes on the implementation: I used a `long` for tracking the priority. Obviously this has limitations when used with date(), as the timestamps are fairly large. I can change this to `long long`. The queue was implemented using the existing pendconns code. The only thing that was changed was to insert in sorted order. Obviously this is just a quick and dirty implementation. There are lots of priority queue implementations to choose from, and I don't know which one is best suited to this kind of task. We could keep the existing sorted linked-list, and just do some optimizations for insertion. Or we could switch to some sort of tree. The linked-list has the advantage in that I suspect that the vast majority of additions will append to the end, and pops are always off the front, so well suited to a linked list. A tree might become very unbalanced very fast, and require lots of maintenance. Using the date() fetch obviously doesn't provide good precision. We could add a `datems()`, `datens()`, or `ticks()` (ms since start) sample fetch. But obviously we would need to use `long long` for that, Though ticks could use a `long`, but would wrap at around 16 months. I still plan on adding a sample fetch for obtaining the current priority value, and a lua function for setting it. Not sure if we want a lua function for retrieving, or if using the fetch is good enough. -Patrick
From 4783dccfc869cfb4219d195ba21f896272211c9e Mon Sep 17 00:00:00 2001 From: Patrick Hemmer <hapr...@stormcloud9.net> Date: Fri, 4 May 2018 16:31:16 -0400 Subject: [PATCH] MINOR: add {http,tcp}-request set-priority for queue prioritization This adds the set-priority action to http-request and tcp-request content. The priority value is used when connections are queued to determine which connections should be served first. The lowest integer value is served first (akin to the 'nice' parameter). --- include/types/stream.h | 1 + src/queue.c | 73 +++++++++++++++++++++++++++++++++++++++++++++++--- src/stream.c | 1 + 3 files changed, 72 insertions(+), 3 deletions(-) diff --git a/include/types/stream.h b/include/types/stream.h index 0dbc79f44..8a2eb8beb 100644 --- a/include/types/stream.h +++ b/include/types/stream.h @@ -125,6 +125,7 @@ struct stream { struct server *srv_conn; /* stream already has a slot on a server and is not in queue */ struct pendconn *pend_pos; /* if not NULL, points to the pending position in the pending queue */ + long priority; /* the priority of the stream in the pending queue */ struct http_txn *txn; /* current HTTP transaction being processed. Should become a list. */ diff --git a/src/queue.c b/src/queue.c index 1c730c75c..1a2cea693 100644 --- a/src/queue.c +++ b/src/queue.c @@ -15,11 +15,14 @@ #include <common/time.h> #include <common/hathreads.h> +#include <proto/proto_http.h> #include <proto/queue.h> +#include <proto/sample.h> #include <proto/server.h> #include <proto/stream.h> #include <proto/stream_interface.h> #include <proto/task.h> +#include <proto/tcp_rules.h> struct pool_head *pool_head_pendconn; @@ -195,7 +198,7 @@ void process_srv_queue(struct server *s) */ struct pendconn *pendconn_add(struct stream *strm) { - struct pendconn *p; + struct pendconn *p, *pn; struct proxy *px; struct server *srv; @@ -219,7 +222,10 @@ struct pendconn *pendconn_add(struct stream *strm) strm->logs.srv_queue_size += srv->nbpend; if (srv->nbpend > srv->counters.nbpend_max) srv->counters.nbpend_max = srv->nbpend; - LIST_ADDQ(&srv->pendconns, &p->list); + list_for_each_entry(pn, &srv->pendconns, list) + if (p->strm->priority < pn->strm->priority) + break; + LIST_ADDQ(&pn->list, &p->list); HA_SPIN_UNLOCK(SERVER_LOCK, &srv->lock); } else { @@ -228,7 +234,10 @@ struct pendconn *pendconn_add(struct stream *strm) strm->logs.prx_queue_size += px->nbpend; if (px->nbpend > px->be_counters.nbpend_max) px->be_counters.nbpend_max = px->nbpend; - LIST_ADDQ(&px->pendconns, &p->list); + list_for_each_entry(pn, &px->pendconns, list) + if (p->strm->priority < pn->strm->priority) + break; + LIST_ADDQ(&pn->list, &p->list); HA_SPIN_UNLOCK(PROXY_LOCK, &px->lock); } HA_ATOMIC_ADD(&px->totpend, 1); @@ -392,6 +401,64 @@ void pendconn_free(struct pendconn *p) pool_free(pool_head_pendconn, p); } +static enum act_return action_set_priority(struct act_rule *rule, struct proxy *px, + struct session *sess, struct stream *s, int flags) +{ + struct sample *smp; + + smp = sample_fetch_as_type(px, sess, s, SMP_OPT_DIR_REQ|SMP_OPT_FINAL, rule->arg.expr, SMP_T_SINT); + if (smp) + s->priority = smp->data.u.sint; + + return ACT_RET_CONT; +} + + +static enum act_parse_ret parse_set_priority(const char **args, int *arg, struct proxy *px, + struct act_rule *rule, char **err) +{ + unsigned int where = 0; + + rule->arg.expr = sample_parse_expr((char **)args, arg, px->conf.args.file, + px->conf.args.line, err, &px->conf.args); + if (!rule->arg.expr) + return ACT_RET_PRS_ERR; + + if (px->cap & PR_CAP_FE) + where |= SMP_VAL_FE_HRQ_HDR; + if (px->cap & PR_CAP_BE) + where |= SMP_VAL_BE_HRQ_HDR; + + if (!(rule->arg.expr->fetch->val & where)) { + memprintf(err, + "fetch method '%s' extracts information from '%s', none of which is available here", + args[0], sample_src_names(rule->arg.expr->fetch->use)); + free(rule->arg.expr); + return ACT_RET_PRS_ERR; + } + + rule->action = ACT_CUSTOM; + rule->action_ptr = action_set_priority; + return ACT_RET_PRS_OK; +} + +static struct action_kw_list tcp_cont_kws = {ILH, { + { "set-priority", parse_set_priority }, + { /* END */ } +}}; + +static struct action_kw_list http_req_kws = {ILH, { + { "set-priority", parse_set_priority }, + { /* END */ } +}}; + +__attribute__((constructor)) +static void __queue_init(void) +{ + tcp_req_cont_keywords_register(&tcp_cont_kws); + http_req_keywords_register(&http_req_kws); +} + /* * Local variables: * c-indent-level: 8 diff --git a/src/stream.c b/src/stream.c index 1d0b22ca3..9d4bc0bbb 100644 --- a/src/stream.c +++ b/src/stream.c @@ -220,6 +220,7 @@ struct stream *stream_new(struct session *sess, enum obj_type *origin) s->target = sess->listener ? sess->listener->default_target : NULL; s->pend_pos = NULL; + s->priority = 0; /* init store persistence */ s->store_count = 0; -- 2.16.3