Re: Priority based queuing
On 2018/5/5 01:29, Willy Tarreau wrote: > On Fri, May 04, 2018 at 06:49:00PM -0400, Patrick Hemmer wrote: >> 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. > That's what the time-ordered queue does. I proposed this so that you can > ensure that lower priorities are always processed first until there is no > more of the same level. Ah, I was considering the 2 solutions as an either-or choice. Not that you'd use both in the same configuration, or at least in the same backend. >> 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. > No, trees are quite cheap, we use them absolutely everywhere now. Just > take a look at wake_expired_tasks() to get an idea. In fact every single > time we've been relying on lists doing linear lookups, we've got several > bug reports about haproxy eating all the CPU because some people were > using it in a way that wasn't initially considered as reasonable but > which made a lot of sense to them. This is why I liked the idea of a single implementation. It gave the flexibility to the user to do whatever they wanted (time or class based). Granted I was only thinking of doing one or the other, but the user could still do both, they would just have to manage dedicating a range to the date/class. Maybe someone would want to consider date before class. > In this case you'd be better of with the principle consisting in using > a larger integer with the priority at the top and the date at the bottom. > But that's where I said that it would require two lookups to deal with > wrapping date so I'm not sure it's any better than using multiple queues. > Well, at least it's less maintenance burden. The detailed principle is > the following : > >uint64_t priority : > > 6332 31 0 > [ hard priority | date ] > >next = lookup_first(queue); >if (!next) > return; > >=> next is the lowest value of both priority and date > > Then you perform a second lookup with the oldest past date for the same > priority level : > >key = (next->key & 0xULL) | (now_ms - TIMER_LOOK_BACK); >next2 = lookup_ge(queue, key); >if (next2 && !((next2->value ^ next->value) >> 32)) > next=next2 > > Then you dequeue next which is always the next one. > > That's where I thought that using two distinct levels was simpler, but > if we factor in the fact that it would limit the number of priority > classes and would require more maintenance code, it's probably not > worth the hassle to save the 4 extra lines we have above to respect > the wrapping date. > > Also I'm thinking that we can even use 32-bit by putting the frontier > between the date and the fixed priority (let's call it class) somewhere > else : > - 8 bit class + 24 bit offset => 256 classes and +/- 2.3 hours offsets > - 12 bit class + 20 bit offset => 4096 classes and +/- 8 minutes offsets > - 16 bit class + 16 bit offset => 64k classes and +/- 32 second offsets What's the benefit to using 32-bit over 64-bit, and is that benefit worth the cost of the added code complexity and processing time? If we used 64-bit, we could do a 16/48 bit split and have an absolute timestamp out to year 10889 at millisecond precision. > I'm pretty sure that the two first options are way enough to cover almost > everyone's needs. For me a 12-bit class should work. My intention is to implement something similar to email spam filtering, where you generate a score based on the rules that match, and some rules are worth more than others. 8 bits might be a bit difficult to work within. I also suspect the 16-bit option (32 second offset) is too small for date based. > Let's say for a moment that we'd use the second option > (12+20 bits), the queue insertion code becomes this : > >pendconn->node.key = (stream->prio_class << 20) + > (now_ms + stream->prio_offset) & 0xF; >if (srv) > eb32_insert(&srv->pendconns, &pendconn->node); >else > eb32_insert(&px->pendconns, &pendconn->node); > > > And the dequeuing code in pendconn_process_next_strm() which takes care > both of the backend's and server's queues while still respecting thei
Re: Priority based queuing
On Sat, May 05, 2018 at 01:33:51PM -0400, Patrick Hemmer wrote: > > Also I'm thinking that we can even use 32-bit by putting the frontier > > between the date and the fixed priority (let's call it class) somewhere > > else : > > - 8 bit class + 24 bit offset => 256 classes and +/- 2.3 hours offsets > > - 12 bit class + 20 bit offset => 4096 classes and +/- 8 minutes offsets > > - 16 bit class + 16 bit offset => 64k classes and +/- 32 second offsets > What's the benefit to using 32-bit over 64-bit, and is that benefit > worth the cost of the added code complexity and processing time? Slightly smaller memory footprint (doesn't count much), but more importantly much smaller processing time especially on 32-bit systems. > If we > used 64-bit, we could do a 16/48 bit split and have an absolute > timestamp out to year 10889 at millisecond precision. Not really because that would force us to implement yet another clock and then to have two distinct set of clocks for queues and for all other internal events and timeouts (including the queue timeout!). That would really be the beginning of a mess. We've been running with 32-bit millisecond-precise ticks for over a decade without ever a complain that it was not enough nor that the wrapping at 49.7 days was an issue. If one day we'd decide to change this, it would be to support finer-grained timestamps (eg: nanoseconds or CPU cycles) which would not necessarily protect us from wrapping either. > > I'm pretty sure that the two first options are way enough to cover almost > > everyone's needs. > For me a 12-bit class should work. My intention is to implement > something similar to email spam filtering, where you generate a score > based on the rules that match, and some rules are worth more than > others. 8 bits might be a bit difficult to work within. Makes sense. > I also suspect the 16-bit option (32 second offset) is too small for > date based. Yes I agree. I'm pretty sure that for some TCP connections certain users will want to have a long delay (eg: wait a minute before your FTP transfer starts). > The rest of this all seems fine. I've got no other thoughts to add. Great, thanks! > So the question is, which route do we go? > 1. 32-bit int (12/20 split) > 2. 64-bit int (32/32 split) I think you can start with the 12/20 split first, knowing that if anybody ever requests an extension of either time or classes we can switch to 64 without much effort. Until this happens we'll be more efficient on small systems. Conversely we can't do it the other way around because we could break some setups :-) > 3. 64-bit int (16/48 split) with absolute timestamps I don't like it much for the reasons above. > 4. 64-bit int with a single `set-priority` action. Let the user use the > a new`ms()` fetch for time based. The user does the bit shifting if they > want to use both (using the `mul()` converter, or we can add a `shift()`). I think this level of complexity ought to be done once in the code and not each and every time for all users. It would only be manageable for a number of the people on this list, but newcomers would call us words for this :-) Thanks, Willy
[PATCH] BUG/MINOR: lua: schedule socket task when lua connect() is called
Hi List, Thierry, Willy, Created another little patch. Hope this one fits all submission criteria. Regards, PiBa-NL (Pieter) From cc4adb62c55f268e9e74853f4a4893e2a3734aec Mon Sep 17 00:00:00 2001 From: PiBa-NL Date: Sat, 5 May 2018 23:51:42 +0200 Subject: [PATCH] BUG/MINOR: lua: schedule socket task upon lua connect() The parameters like server-address, port and timeout should be set before process_stream task is called to avoid the stream being 'closed' before it got initialized properly. This is most clearly visible when running with tune.lua.forced-yield=1.. So scheduling the task should not be done when creating the lua socket, but when connect is called. The error "socket: not yet initialised, you can't set timeouts." would then appear. Below code for example also shows this issue, as the sleep will yield the lua code: local con = core.tcp() core.sleep(1) con:settimeout(10) --- src/hlua.c | 6 -- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/hlua.c b/src/hlua.c index 4c56409..07366af 100644 --- a/src/hlua.c +++ b/src/hlua.c @@ -2423,6 +2423,10 @@ __LJMP static int hlua_socket_connect(struct lua_State *L) WILL_LJMP(luaL_error(L, "out of memory")); } xref_unlock(&socket->xref, peer); + + task_wakeup(s->task, TASK_WOKEN_INIT); + /* Return yield waiting for connection. */ + WILL_LJMP(hlua_yieldk(L, 0, 0, hlua_socket_connect_yield, TICK_ETERNITY, 0)); return 0; @@ -2582,8 +2586,6 @@ __LJMP static int hlua_socket_new(lua_State *L) strm->flags |= SF_DIRECT | SF_ASSIGNED | SF_ADDR_SET | SF_BE_ASSIGNED; strm->target = &socket_tcp.obj_type; - task_wakeup(strm->task, TASK_WOKEN_INIT); - /* Return yield waiting for connection. */ return 1; out_fail_stream: -- 2.10.1.windows.1
Re: stable-bot: NOTICE: 7 bug fixes in queue for next release
On Tue, May 01, 2018 at 02:23:37PM +0200, Aleksandar Lazic wrote: > Hi. > > Am 30.04.2018 um 18:24 schrieb stable-...@haproxy.com: > > Hi, > > > > This is a friendly bot that watches fixes pending for the next > > haproxy-stable release! One such e-mail is sent every week once patches > > are waiting in the last maintenance branch, and an ideal release date is > > computed based on the severity of these fixes and their merge date. > > Responses to this mail must be sent to the mailing list. > > That's cool ;-) Thanks Aleks! We thought about doing it for all stable branches but I don't think it would work well for older ones, since they depend on the backports to be done first on the latest branches. However and idea was proposed, to at least enumerate the pending patches for these branches. Overall the purpose of this bot is to remind us stable maintainers about the need to issue a release soon and at the same time to help everyone else synchronise with this. We'll see how it goes, suggestions will be welcome. Cheers, Willy
Re: [PATCH] Make sure all the pollers get fd updates
Hi Olivier, On Fri, May 04, 2018 at 05:32:24PM +0200, Olivier Houchard wrote: > This can't be applied to 1.8, as it uses code that was not, and probably won't > be, backported, so a different patch, similar in spirit, will be developed. Thanks for these patches. Now applied. I mentioned the point above in the second patch's commit message to help stable maintainers know what to do with it. Now you'll have fun figuring a solution suitable for 1.8 :-) Willy
Re: [PATCH] BUG/MINOR: lua: schedule socket task when lua connect() is called
Hi Pieter, On Sun, May 06, 2018 at 12:00:14AM +0200, PiBa-NL wrote: > The parameters like server-address, port and timeout should be set before > process_stream task is called to avoid the stream being 'closed' before it > got initialized properly. This is most clearly visible when running with > tune.lua.forced-yield=1.. So scheduling the task should not be done when > creating the lua socket, but when connect is called. The error > "socket: not yet initialised, you can't set timeouts." would then appear. > > Below code for example also shows this issue, as the sleep will > yield the lua code: > local con = core.tcp() > core.sleep(1) > con:settimeout(10) It seems to make sense indeed. I'll let Thierry check as he's the one who really knows if there's a possible impact behind this. Thanks, Willy