<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">чт, 5 окт. 2023 г. в 03:51, Yusuke Nojima <<a href="mailto:nojima@ynojima.com">nojima@ynojima.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Thank you for your comment!<br>
<br>
> Could you please provide some more details about the use case,<br>
> such as how locations are used, and what is the approximate number<br>
> of locations being used?<br>
<br>
Our team provides development environments to our company's engineers and QA.<br>
In this environment, engineers and QA can freely create VMs and deploy<br>
applications on them.<br>
<br>
Our nginx has the role of routing requests from the internet to all<br>
applications deployed in this environment.<br>
Additionally, it allows setting IP address restrictions, BASIC<br>
authentication, TLS client authentication, and other configurations<br>
for each application.<br></blockquote><div><br></div><div>BASIC auth is known to be CPU consuming as well, hash is calculated on every http request.</div><div>what is a ratio of authenticated requests ? do you see high CPU consumption ?</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
To implement these requirements, we generate a location for each application.<br>
Currently, there are approximately 40,000 locations in our environment.<br>
<br>
> Further, since each location contains configuration for<br>
> all modules, such configurations are expected to require a lot of<br>
> memory<br>
<br>
Each of our nginx processes was consuming 5GB of memory in terms of<br>
resident size.<br>
This is not a problem as our servers have sufficient memory.<br>
<br>
> Rather, I would suggest recursive top-bottom merge sort implementation<br>
> instead, which is much simpler and uses stack as temporary storage<br>
> (so it'll naturally die if there will be a queue which requires<br>
> more space for sorting than we have).<br>
><br>
> Please take a look if it works for you:<br>
<br>
I think this implementation is simple and easy to understand.<br>
Although the number of traversals of the list will increase compared<br>
to bottom-up, it will not affect the order.<br>
I believe this will provide sufficient optimization in terms of speed.<br>
<br>
<br>
2023年9月30日(土) 12:38 Maxim Dounin <<a href="mailto:mdounin@mdounin.ru" target="_blank">mdounin@mdounin.ru</a>>:<br>
><br>
> Hello!<br>
><br>
> On Fri, Sep 22, 2023 at 03:58:41PM +0900, Yusuke Nojima wrote:<br>
><br>
> > # HG changeset patch<br>
> > # User Yusuke Nojima <<a href="mailto:nojima@ynojima.com" target="_blank">nojima@ynojima.com</a>><br>
> > # Date 1679555707 -32400<br>
> > # Thu Mar 23 16:15:07 2023 +0900<br>
> > # Node ID 6aac98fb135e47ca9cf7ad7d780cf4a10e9aa55c<br>
> > # Parent 8771d35d55d0a2b1cefaab04401d6f837f5a05a2<br>
> > Improve performance when starting nginx with a lot of locations<br>
> ><br>
> > Our team has a configuration file with a very large number of<br>
> > locations, and we found that starting nginx with this file takes an<br>
> > unacceptable amount of time. After investigating the issue, we<br>
> > discovered that the root cause of the long startup time is the sorting<br>
> > of the location list.<br>
><br>
> Interesting.<br>
><br>
> Could you please provide some more details about the use case,<br>
> such as how locations are used, and what is the approximate number<br>
> of locations being used?<br>
><br>
> In my practice, it is extremely uncommon to use more than 1k-10k<br>
> prefix locations (and even these numbers are huge for normal<br>
> setups). Further, since each location contains configuration for<br>
> all modules, such configurations are expected to require a lot of<br>
> memory (currently about 5-10KB per empty location, so about<br>
> 50-100MB per 10k locations, and 0.5-1G per 100k locations).<br>
> Accordingly, using other approaches such as map (assuming exact<br>
> match is actually needed) might be beneficial regardless of the<br>
> sorting costs.<br>
><br>
> Nevertheless, swapping the sorting algorithm to a faster one looks<br>
> like an obvious improvement.<br>
><br>
> ><br>
> > Currently, the sorting algorithm used in nginx is insertion sort,<br>
> > which requires O(n^2) time for n locations. We have modified the<br>
> > sorting algorithm to use merge sort instead, which has a time<br>
> > complexity of O(n log n).<br>
> ><br>
> > We have tested the modified code using micro-benchmarks and confirmed<br>
> > that the new algorithm improves nginx startup time significantly<br>
> > (shown below). We believe that this change would be valuable for other<br>
> > users who are experiencing similar issues.<br>
> ><br>
> ><br>
> > Table: nginx startup time in seconds<br>
> ><br>
> > n current patched<br>
> > 2000 0.033 0.018<br>
> > 4000 0.047 0.028<br>
> > 6000 0.062 0.038<br>
> > 8000 0.079 0.050<br>
> > 10000 0.091 0.065<br>
> > 12000 0.367 0.081<br>
> > 14000 0.683 0.086<br>
> > 16000 0.899 0.097<br>
> > 18000 1.145 0.110<br>
> > 20000 1.449 0.122<br>
> > 22000 1.650 0.137<br>
> > 24000 2.155 0.151<br>
> > 26000 3.096 0.155<br>
> > 28000 3.711 0.168<br>
> > 30000 3.539 0.184<br>
> > 32000 3.980 0.193<br>
> > 34000 4.543 0.208<br>
> > 36000 4.349 0.217<br>
> > 38000 5.021 0.229<br>
> > 40000 4.918 0.245<br>
> > 42000 4.835 0.256<br>
> > 44000 5.159 0.262<br>
> > 46000 5.802 0.331<br>
> > 48000 6.205 0.295<br>
> > 50000 5.701 0.308<br>
> > 52000 5.992 0.335<br>
> > 54000 6.561 0.323<br>
> > 56000 6.856 0.333<br>
> > 58000 6.515 0.347<br>
> > 60000 7.051 0.359<br>
> > 62000 6.956 0.377<br>
> > 64000 7.376 0.376<br>
> > 66000 7.506 0.404<br>
> > 68000 7.292 0.407<br>
> > 70000 7.422 0.461<br>
> > 72000 10.090 0.443<br>
> > 74000 18.505 0.463<br>
> > 76000 11.857 0.462<br>
> > 78000 9.752 0.470<br>
> > 80000 12.485 0.481<br>
> > 82000 11.027 0.498<br>
> > 84000 9.804 0.523<br>
> > 86000 8.482 0.515<br>
> > 88000 9.838 0.560<br>
> > 90000 12.341 0.546<br>
> > 92000 13.881 0.648<br>
> > 94000 8.309 0.635<br>
> > 96000 8.854 0.650<br>
> > 98000 12.871 0.674<br>
> > 100000 8.261 0.698<br>
><br>
> This probably can be reduced to something like 3-5 data points.<br>
><br>
> ><br>
> > diff -r 8771d35d55d0 -r 6aac98fb135e src/core/ngx_queue.c<br>
> > --- a/src/core/ngx_queue.c Fri Mar 10 07:43:50 2023 +0300<br>
> > +++ b/src/core/ngx_queue.c Thu Mar 23 16:15:07 2023 +0900<br>
> > @@ -45,36 +45,103 @@<br>
> > }<br>
> ><br>
> ><br>
> > -/* the stable insertion sort */<br>
> > +/* merge queue2 into queue1. queue2 becomes empty after merge. */<br>
> > +<br>
> > +static void<br>
> > +ngx_queue_merge(ngx_queue_t *queue1, ngx_queue_t *queue2,<br>
> > + ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))<br>
> > +{<br>
> > + ngx_queue_t *p1, *p2;<br>
><br>
> Nitpicking: there are various style issues here and in other places.<br>
><br>
> > +<br>
> > + p1 = ngx_queue_head(queue1);<br>
> > + p2 = ngx_queue_head(queue2);<br>
> > +<br>
> > + while (p1 != ngx_queue_sentinel(queue1)<br>
> > + && p2 != ngx_queue_sentinel(queue2)) {<br>
> > +<br>
> > + if (cmp(p1, p2) > 0) {<br>
> > + ngx_queue_t *next, *prev;<br>
> > +<br>
> > + next = ngx_queue_next(p2);<br>
> > + ngx_queue_remove(p2);<br>
> > + prev = ngx_queue_prev(p1);<br>
> > + ngx_queue_insert_after(prev, p2);<br>
> > + p2 = next;<br>
><br>
> Nitpicking: there is no need to preserve "next" here, since p2 is<br>
> always the head of queue2 and, and the next element can be<br>
> obtained by ngx_queue_head(queue2).<br>
><br>
> Also, instead of obtaining "prev" and using<br>
> ngx_queue_insert_after() it would be easier to use<br>
> ngx_queue_insert_before(). It is not currently defined, but it is<br>
> trivial to define one: it is an alias to ngx_queue_insert_tail(),<br>
> much like ngx_queue_insert_after() is an alias to<br>
> ngx_queue_insert_head().<br>
><br>
> > + } else {<br>
> > + p1 = ngx_queue_next(p1);<br>
> > + }<br>
> > + }<br>
> > + if (p2 != ngx_queue_sentinel(queue2)) {<br>
> > + ngx_queue_add(queue1, queue2);<br>
> > + ngx_queue_init(queue2);<br>
> > + }<br>
> > +}<br>
> > +<br>
> > +<br>
> > +/* move all elements from src to dest. dest should be empty before call. */<br>
> > +<br>
> > +static void<br>
> > +ngx_queue_move(ngx_queue_t *dest, ngx_queue_t *src)<br>
> > +{<br>
> > + *dest = *src;<br>
> > + ngx_queue_init(src);<br>
> > +<br>
> > + if (dest->next == src) {<br>
> > + dest->next = dest;<br>
> > + } else {<br>
> > + dest->next->prev = dest;<br>
> > + }<br>
> > + if (dest->prev == src) {<br>
> > + dest->prev = dest;<br>
> > + } else {<br>
> > + dest->prev->next = dest;<br>
> > + }<br>
> > +}<br>
><br>
> This function looks strange to me. There is the ngx_queue_add()<br>
> macro, which probably should be used instead (if needed).<br>
><br>
> > +<br>
> > +<br>
> > +/* the stable merge sort */<br>
> ><br>
> > void<br>
> > ngx_queue_sort(ngx_queue_t *queue,<br>
> > ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))<br>
> > {<br>
> > - ngx_queue_t *q, *prev, *next;<br>
> > + ngx_queue_t merged[64], *p, *last;<br>
> ><br>
> > - q = ngx_queue_head(queue);<br>
> > -<br>
> > - if (q == ngx_queue_last(queue)) {<br>
> > + if (ngx_queue_head(queue) == ngx_queue_last(queue)) {<br>
> > return;<br>
> > }<br>
> ><br>
> > - for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {<br>
> > + last = merged;<br>
> ><br>
> > - prev = ngx_queue_prev(q);<br>
> > - next = ngx_queue_next(q);<br>
> > + while (!ngx_queue_empty(queue)) {<br>
> > + /*<br>
> > + * Loop invariant:<br>
> > + * merged[i] must have exactly 0 or 2^i elements in sorted order.<br>
> > + * For each iteration, we take one element from the given queue and<br>
> > + * insert it into merged without violating the invariant condition.<br>
> > + */<br>
> ><br>
> > - ngx_queue_remove(q);<br>
> > + ngx_queue_t carry, *h;<br>
> > +<br>
> > + h = ngx_queue_head(queue);<br>
> > + ngx_queue_remove(h);<br>
> > + ngx_queue_init(&carry);<br>
> > + ngx_queue_insert_head(&carry, h);<br>
> ><br>
> > - do {<br>
> > - if (cmp(prev, q) <= 0) {<br>
> > - break;<br>
> > - }<br>
> > + for (p = merged; p != last && !ngx_queue_empty(p); p++) {<br>
> > + ngx_queue_merge(p, &carry, cmp);<br>
> > + ngx_queue_move(&carry, p);<br>
> > + }<br>
> > + if (p == last) {<br>
> > + ngx_queue_init(last);<br>
> > + last++;<br>
> > + }<br>
> > + ngx_queue_move(p, &carry);<br>
> > + }<br>
> ><br>
> > - prev = ngx_queue_prev(prev);<br>
> > -<br>
> > - } while (prev != ngx_queue_sentinel(queue));<br>
> > -<br>
> > - ngx_queue_insert_after(prev, q);<br>
> > + /* Merge all queues into one queue */<br>
> > + for (p = merged + 1; p != last; p++) {<br>
> > + ngx_queue_merge(p, p-1, cmp);<br>
> > }<br>
> > + ngx_queue_move(queue, last-1);<br>
> > }<br>
><br>
> While bottom-up merge sort implementation might be more efficient,<br>
> I find it disturbing to use fixed array of queues without any<br>
> checks if we are within the array bounds.<br>
><br>
> Rather, I would suggest recursive top-bottom merge sort implementation<br>
> instead, which is much simpler and uses stack as temporary storage<br>
> (so it'll naturally die if there will be a queue which requires<br>
> more space for sorting than we have).<br>
><br>
> Please take a look if it works for you:<br>
><br>
> diff --git a/src/core/ngx_queue.c b/src/core/ngx_queue.c<br>
> --- a/src/core/ngx_queue.c<br>
> +++ b/src/core/ngx_queue.c<br>
> @@ -9,6 +9,10 @@<br>
> #include <ngx_core.h><br>
><br>
><br>
> +static void ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,<br>
> + ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));<br>
> +<br>
> +<br>
> /*<br>
> * find the middle queue element if the queue has odd number of elements<br>
> * or the first element of the queue's second part otherwise<br>
> @@ -45,13 +49,13 @@ ngx_queue_middle(ngx_queue_t *queue)<br>
> }<br>
><br>
><br>
> -/* the stable insertion sort */<br>
> +/* the stable merge sort */<br>
><br>
> void<br>
> ngx_queue_sort(ngx_queue_t *queue,<br>
> ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))<br>
> {<br>
> - ngx_queue_t *q, *prev, *next;<br>
> + ngx_queue_t *q, tail;<br>
><br>
> q = ngx_queue_head(queue);<br>
><br>
> @@ -59,22 +63,44 @@ ngx_queue_sort(ngx_queue_t *queue,<br>
> return;<br>
> }<br>
><br>
> - for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {<br>
> + q = ngx_queue_middle(queue);<br>
> +<br>
> + ngx_queue_split(queue, q, &tail);<br>
> +<br>
> + ngx_queue_sort(queue, cmp);<br>
> + ngx_queue_sort(&tail, cmp);<br>
> +<br>
> + ngx_queue_merge(queue, &tail, cmp);<br>
> +}<br>
><br>
> - prev = ngx_queue_prev(q);<br>
> - next = ngx_queue_next(q);<br>
><br>
> - ngx_queue_remove(q);<br>
> +static void<br>
> +ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,<br>
> + ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))<br>
> +{<br>
> + ngx_queue_t *q1, *q2;<br>
> +<br>
> + q1 = ngx_queue_head(queue);<br>
> + q2 = ngx_queue_head(tail);<br>
><br>
> - do {<br>
> - if (cmp(prev, q) <= 0) {<br>
> - break;<br>
> - }<br>
> + for ( ;; ) {<br>
> + if (q1 == ngx_queue_sentinel(queue)) {<br>
> + ngx_queue_add(queue, tail);<br>
> + break;<br>
> + }<br>
> +<br>
> + if (q2 == ngx_queue_sentinel(tail)) {<br>
> + break;<br>
> + }<br>
><br>
> - prev = ngx_queue_prev(prev);<br>
> + if (cmp(q1, q2) <= 0) {<br>
> + q1 = ngx_queue_next(q1);<br>
> + continue;<br>
> + }<br>
><br>
> - } while (prev != ngx_queue_sentinel(queue));<br>
> + ngx_queue_remove(q2);<br>
> + ngx_queue_insert_before(q1, q2);<br>
><br>
> - ngx_queue_insert_after(prev, q);<br>
> + q2 = ngx_queue_head(tail);<br>
> }<br>
> }<br>
> diff --git a/src/core/ngx_queue.h b/src/core/ngx_queue.h<br>
> --- a/src/core/ngx_queue.h<br>
> +++ b/src/core/ngx_queue.h<br>
> @@ -47,6 +47,9 @@ struct ngx_queue_s {<br>
> (h)->prev = x<br>
><br>
><br>
> +#define ngx_queue_insert_before ngx_queue_insert_tail<br>
> +<br>
> +<br>
> #define ngx_queue_head(h) \<br>
> (h)->next<br>
><br>
><br>
><br>
> --<br>
> Maxim Dounin<br>
> <a href="http://mdounin.ru/" rel="noreferrer" target="_blank">http://mdounin.ru/</a><br>
> _______________________________________________<br>
> nginx-devel mailing list<br>
> <a href="mailto:nginx-devel@nginx.org" target="_blank">nginx-devel@nginx.org</a><br>
> <a href="https://mailman.nginx.org/mailman/listinfo/nginx-devel" rel="noreferrer" target="_blank">https://mailman.nginx.org/mailman/listinfo/nginx-devel</a><br>
_______________________________________________<br>
nginx-devel mailing list<br>
<a href="mailto:nginx-devel@nginx.org" target="_blank">nginx-devel@nginx.org</a><br>
<a href="https://mailman.nginx.org/mailman/listinfo/nginx-devel" rel="noreferrer" target="_blank">https://mailman.nginx.org/mailman/listinfo/nginx-devel</a><br>
</blockquote></div></div>