SCHEDULER_README.html revision 1.1.1.3
1 1.1 tron <!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN" 2 1.1.1.3 tron "http://www.w3.org/TR/html4/loose.dtd"> 3 1.1 tron 4 1.1 tron <html> 5 1.1 tron 6 1.1 tron <head> 7 1.1 tron 8 1.1 tron <title>Postfix Queue Scheduler</title> 9 1.1 tron 10 1.1 tron <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> 11 1.1 tron 12 1.1 tron </head> 13 1.1 tron 14 1.1 tron <body> 15 1.1 tron 16 1.1 tron <h1><img src="postfix-logo.jpg" width="203" height="98" ALT="">Postfix 17 1.1 tron Queue Scheduler</h1> 18 1.1 tron 19 1.1 tron <hr> 20 1.1 tron 21 1.1.1.2 tron <h2> Disclaimer </h2> 22 1.1.1.2 tron 23 1.1.1.2 tron <p> Many of the <i>transport</i>-specific configuration parameters 24 1.1.1.2 tron discussed in this document will not show up in "postconf" command 25 1.1.1.2 tron output before Postfix version 2.9. This limitation applies to many 26 1.1.1.2 tron parameters whose name is a combination of a <a href="master.5.html">master.cf</a> service name 27 1.1.1.2 tron such as "relay" and a built-in suffix such as 28 1.1.1.2 tron "_destination_concurrency_limit". </p> 29 1.1.1.2 tron 30 1.1 tron <h2> Overview </h2> 31 1.1 tron 32 1.1 tron <p> The queue manager is by far the most complex part of the Postfix 33 1.1 tron mail system. It schedules delivery of new mail, retries failed 34 1.1 tron deliveries at specific times, and removes mail from the queue after 35 1.1 tron the last delivery attempt. There are two major classes of mechanisms 36 1.1 tron that control the operation of the queue manager. </p> 37 1.1 tron 38 1.1 tron <p> Topics covered by this document: </p> 39 1.1 tron 40 1.1 tron <ul> 41 1.1 tron 42 1.1 tron <li> <a href="#concurrency"> Concurrency scheduling</a>, concerned 43 1.1 tron with the number of concurrent deliveries to a specific destination, 44 1.1 tron including decisions on when to suspend deliveries after persistent 45 1.1 tron failures. 46 1.1 tron 47 1.1 tron <li> <a href="#jobs"> Preemptive scheduling</a>, concerned with 48 1.1 tron the selection of email messages and recipients for a given destination. 49 1.1 tron 50 1.1 tron <li> <a href="#credits"> Credits</a>, something this document would not be 51 1.1 tron complete without. 52 1.1 tron 53 1.1 tron </ul> 54 1.1 tron 55 1.1 tron <!-- 56 1.1 tron 57 1.1 tron <p> Once started, the <a href="qmgr.8.html">qmgr(8)</a> process runs until "postfix reload" 58 1.1 tron or "postfix stop". As a persistent process, the queue manager has 59 1.1 tron to meet strict requirements with respect to code correctness and 60 1.1 tron robustness. Unlike non-persistent daemon processes, the queue manager 61 1.1 tron cannot benefit from Postfix's process rejuvenation mechanism that 62 1.1 tron limit the impact from resource leaks and other coding errors 63 1.1 tron (translation: replacing a process after a short time covers up bugs 64 1.1 tron before they can become a problem). </p> 65 1.1 tron 66 1.1 tron --> 67 1.1 tron 68 1.1 tron <h2> <a name="concurrency"> Concurrency scheduling </a> </h2> 69 1.1 tron 70 1.1 tron <p> The following sections document the Postfix 2.5 concurrency 71 1.1.1.3 tron scheduler, after a discussion of the limitations of the earlier 72 1.1 tron concurrency scheduler. This is followed by results of medium-concurrency 73 1.1 tron experiments, and a discussion of trade-offs between performance and 74 1.1 tron robustness. </p> 75 1.1 tron 76 1.1 tron <p> The material is organized as follows: </p> 77 1.1 tron 78 1.1 tron <ul> 79 1.1 tron 80 1.1 tron <li> <a href="#concurrency_drawbacks"> Drawbacks of the existing 81 1.1 tron concurrency scheduler </a> 82 1.1 tron 83 1.1 tron <li> <a href="#concurrency_summary_2_5"> Summary of the Postfix 2.5 84 1.1 tron concurrency feedback algorithm </a> 85 1.1 tron 86 1.1 tron <li> <a href="#dead_summary_2_5"> Summary of the Postfix 2.5 "dead 87 1.1 tron destination" detection algorithm </a> 88 1.1 tron 89 1.1 tron <li> <a href="#pseudo_code_2_5"> Pseudocode for the Postfix 2.5 90 1.1 tron concurrency scheduler </a> 91 1.1 tron 92 1.1 tron <li> <a href="#concurrency_results"> Results for delivery to 93 1.1 tron concurrency limited servers </a> 94 1.1 tron 95 1.1 tron <li> <a href="#concurrency_discussion"> Discussion of concurrency 96 1.1 tron limited server results </a> 97 1.1 tron 98 1.1 tron <li> <a href="#concurrency_limitations"> Limitations of less-than-1 99 1.1 tron per delivery feedback </a> 100 1.1 tron 101 1.1 tron <li> <a href="#concurrency_config"> Concurrency configuration 102 1.1 tron parameters </a> 103 1.1 tron 104 1.1 tron </ul> 105 1.1 tron 106 1.1 tron <h3> <a name="concurrency_drawbacks"> Drawbacks of the existing 107 1.1 tron concurrency scheduler </a> </h3> 108 1.1 tron 109 1.1 tron <p> From the start, Postfix has used a simple but robust algorithm 110 1.1 tron where the per-destination delivery concurrency is decremented by 1 111 1.1 tron after delivery failed due to connection or handshake failure, and 112 1.1 tron incremented by 1 otherwise. Of course the concurrency is never 113 1.1 tron allowed to exceed the maximum per-destination concurrency limit. 114 1.1 tron And when a destination's concurrency level drops to zero, the 115 1.1 tron destination is declared "dead" and delivery is suspended. </p> 116 1.1 tron 117 1.1 tron <p> Drawbacks of +/-1 concurrency feedback per delivery are: <p> 118 1.1 tron 119 1.1 tron <ul> 120 1.1 tron 121 1.1 tron <li> <p> Overshoot due to exponential delivery concurrency growth 122 1.1 tron with each pseudo-cohort(*). This can be an issue with high-concurrency 123 1.1 tron channels. For example, with the default initial concurrency of 5, 124 1.1 tron concurrency would proceed over time as (5-10-20). </p> 125 1.1 tron 126 1.1 tron <li> <p> Throttling down to zero concurrency after a single 127 1.1 tron pseudo-cohort(*) failure. This was especially an issue with 128 1.1 tron low-concurrency channels where a single failure could be sufficient 129 1.1 tron to mark a destination as "dead", causing the suspension of further 130 1.1 tron deliveries to the affected destination. </p> 131 1.1 tron 132 1.1 tron </ul> 133 1.1 tron 134 1.1 tron <p> (*) A pseudo-cohort is a number of delivery requests equal to 135 1.1 tron a destination's delivery concurrency. </p> 136 1.1 tron 137 1.1 tron <p> The revised concurrency scheduler has a highly modular structure. 138 1.1 tron It uses separate mechanisms for per-destination concurrency control 139 1.1 tron and for "dead destination" detection. The concurrency control in 140 1.1 tron turn is built from two separate mechanisms: it supports less-than-1 141 1.1 tron feedback per delivery to allow for more gradual concurrency 142 1.1 tron adjustments, and it uses feedback hysteresis to suppress concurrency 143 1.1 tron oscillations. And instead of waiting for delivery concurrency to 144 1.1 tron throttle down to zero, a destination is declared "dead" after a 145 1.1 tron configurable number of pseudo-cohorts reports connection or handshake 146 1.1 tron failure. </p> 147 1.1 tron 148 1.1 tron <h3> <a name="concurrency_summary_2_5"> Summary of the Postfix 2.5 149 1.1 tron concurrency feedback algorithm </a> </h3> 150 1.1 tron 151 1.1 tron <p> We want to increment a destination's delivery concurrency when 152 1.1 tron some (not necessarily consecutive) number of deliveries complete 153 1.1 tron without connection or handshake failure. This is implemented with 154 1.1 tron positive feedback g(N) where N is the destination's delivery 155 1.1 tron concurrency. With g(N)=1 feedback per delivery, concurrency increases 156 1.1 tron by 1 after each positive feedback event; this gives us the old 157 1.1 tron scheduler's exponential growth in time. With g(N)=1/N feedback per 158 1.1 tron delivery, concurrency increases by 1 after an entire pseudo-cohort 159 1.1 tron N of positive feedback reports; this gives us linear growth in time. 160 1.1 tron Less-than-1 feedback per delivery and integer truncation naturally 161 1.1 tron give us hysteresis, so that transitions to larger concurrency happen 162 1.1 tron every 1/g(N) positive feedback events. </p> 163 1.1 tron 164 1.1 tron <p> We want to decrement a destination's delivery concurrency when 165 1.1 tron some (not necessarily consecutive) number of deliveries complete 166 1.1 tron after connection or handshake failure. This is implemented with 167 1.1 tron negative feedback f(N) where N is the destination's delivery 168 1.1 tron concurrency. With f(N)=1 feedback per delivery, concurrency decreases 169 1.1 tron by 1 after each negative feedback event; this gives us the old 170 1.1 tron scheduler's behavior where concurrency is throttled down dramatically 171 1.1 tron after a single pseudo-cohort failure. With f(N)=1/N feedback per 172 1.1 tron delivery, concurrency backs off more gently. Again, less-than-1 173 1.1 tron feedback per delivery and integer truncation naturally give us 174 1.1 tron hysteresis, so that transitions to lower concurrency happen every 175 1.1 tron 1/f(N) negative feedback events. </p> 176 1.1 tron 177 1.1 tron <p> However, with negative feedback we introduce a subtle twist. 178 1.1 tron We "reverse" the negative hysteresis cycle so that the transition 179 1.1 tron to lower concurrency happens at the <b>beginning</b> of a sequence 180 1.1 tron of 1/f(N) negative feedback events. Otherwise, a correction for 181 1.1 tron overload would be made too late. This makes the choice of f(N) 182 1.1 tron relatively unimportant, as borne out by measurements later in this 183 1.1 tron document. </p> 184 1.1 tron 185 1.1 tron <p> In summary, the main ingredients for the Postfix 2.5 concurrency 186 1.1 tron feedback algorithm are a) the option of less-than-1 positive feedback 187 1.1 tron per delivery to avoid overwhelming servers, b) the option of 188 1.1 tron less-than-1 negative feedback per delivery to avoid giving up too 189 1.1 tron fast, c) feedback hysteresis to avoid rapid oscillation, and d) a 190 1.1 tron "reverse" hysteresis cycle for negative feedback, so that it can 191 1.1 tron correct for overload quickly. </p> 192 1.1 tron 193 1.1 tron <h3> <a name="dead_summary_2_5"> Summary of the Postfix 2.5 "dead destination" detection algorithm </a> </h3> 194 1.1 tron 195 1.1 tron <p> We want to suspend deliveries to a specific destination after 196 1.1 tron some number of deliveries suffers connection or handshake failure. 197 1.1 tron The old scheduler declares a destination "dead" when negative (-1) 198 1.1 tron feedback throttles the delivery concurrency down to zero. With 199 1.1 tron less-than-1 feedback per delivery, this throttling down would 200 1.1 tron obviously take too long. We therefore have to separate "dead 201 1.1 tron destination" detection from concurrency feedback. This is implemented 202 1.1 tron by introducing the concept of pseudo-cohort failure. The Postfix 203 1.1 tron 2.5 concurrency scheduler declares a destination "dead" after a 204 1.1 tron configurable number of pseudo-cohorts suffers from connection or 205 1.1 tron handshake failures. The old scheduler corresponds to the special 206 1.1 tron case where the pseudo-cohort failure limit is equal to 1. </p> 207 1.1 tron 208 1.1 tron <h3> <a name="pseudo_code_2_5"> Pseudocode for the Postfix 2.5 concurrency scheduler </a> </h3> 209 1.1 tron 210 1.1 tron <p> The pseudo code shows how the ideas behind new concurrency 211 1.1 tron scheduler are implemented as of November 2007. The actual code can 212 1.1 tron be found in the module qmgr/qmgr_queue.c. </p> 213 1.1 tron 214 1.1 tron <pre> 215 1.1 tron Types: 216 1.1 tron Each destination has one set of the following variables 217 1.1 tron int concurrency 218 1.1 tron double success 219 1.1 tron double failure 220 1.1 tron double fail_cohorts 221 1.1 tron 222 1.1 tron Feedback functions: 223 1.1 tron N is concurrency; x, y are arbitrary numbers in [0..1] inclusive 224 1.1 tron positive feedback: g(N) = x/N | x/sqrt(N) | x 225 1.1 tron negative feedback: f(N) = y/N | y/sqrt(N) | y 226 1.1 tron 227 1.1 tron Initialization: 228 1.1 tron concurrency = initial_concurrency 229 1.1 tron success = 0 230 1.1 tron failure = 0 231 1.1 tron fail_cohorts = 0 232 1.1 tron 233 1.1 tron After success: 234 1.1 tron fail_cohorts = 0 235 1.1 tron Be prepared for feedback > hysteresis, or rounding error 236 1.1 tron success += g(concurrency) 237 1.1 tron while (success >= 1) Hysteresis 1 238 1.1 tron concurrency += 1 Hysteresis 1 239 1.1 tron failure = 0 240 1.1 tron success -= 1 Hysteresis 1 241 1.1 tron Be prepared for overshoot 242 1.1 tron if (concurrency > concurrency limit) 243 1.1 tron concurrency = concurrency limit 244 1.1 tron 245 1.1 tron Safety: 246 1.1 tron Don't apply positive feedback unless 247 1.1 tron concurrency < busy_refcount + init_dest_concurrency 248 1.1 tron otherwise negative feedback effect could be delayed 249 1.1 tron 250 1.1 tron After failure: 251 1.1 tron if (concurrency > 0) 252 1.1 tron fail_cohorts += 1.0 / concurrency 253 1.1 tron if (fail_cohorts > cohort_failure_limit) 254 1.1 tron concurrency = 0 255 1.1 tron if (concurrency > 0) 256 1.1 tron Be prepared for feedback > hysteresis, rounding errors 257 1.1 tron failure -= f(concurrency) 258 1.1 tron while (failure < 0) 259 1.1 tron concurrency -= 1 Hysteresis 1 260 1.1 tron failure += 1 Hysteresis 1 261 1.1 tron success = 0 262 1.1 tron Be prepared for overshoot 263 1.1 tron if (concurrency < 1) 264 1.1 tron concurrency = 1 265 1.1 tron </pre> 266 1.1 tron 267 1.1 tron <h3> <a name="concurrency_results"> Results for delivery to concurrency-limited servers </a> </h3> 268 1.1 tron 269 1.1 tron <p> Discussions about the concurrency scheduler redesign started 270 1.1 tron early 2004, when the primary goal was to find alternatives that did 271 1.1 tron not exhibit exponential growth or rapid concurrency throttling. No 272 1.1 tron code was implemented until late 2007, when the primary concern had 273 1.1 tron shifted towards better handling of server concurrency limits. For 274 1.1 tron this reason we measure how well the new scheduler does this 275 1.1 tron job. The table below compares mail delivery performance of the old 276 1.1 tron +/-1 feedback per delivery with several less-than-1 feedback 277 1.1 tron functions, for different limited-concurrency server scenarios. 278 1.1 tron Measurements were done with a FreeBSD 6.2 client and with FreeBSD 279 1.1 tron 6.2 and various Linux servers. </p> 280 1.1 tron 281 1.1 tron <p> Server configuration: </p> 282 1.1 tron 283 1.1 tron <ul> <li> The mail flow was slowed down with 1 second latency per 284 1.1 tron recipient ("<a href="postconf.5.html#smtpd_client_restrictions">smtpd_client_restrictions</a> = sleep 1"). The purpose was 285 1.1 tron to make results less dependent on hardware details, by avoiding 286 1.1 tron slow-downs by queue file I/O, logging I/O, and network I/O. 287 1.1 tron 288 1.1 tron <li> Concurrency was limited by the server process limit 289 1.1 tron ("<a href="postconf.5.html#default_process_limit">default_process_limit</a> = 5" and "<a href="postconf.5.html#smtpd_client_event_limit_exceptions">smtpd_client_event_limit_exceptions</a> 290 1.1.1.2 tron = <a href="DATABASE_README.html#types">static</a>:all"). Postfix was stopped and started after changing the 291 1.1 tron process limit, because the same number is also used as the backlog 292 1.1 tron argument to the listen(2) system call, and "postfix reload" does 293 1.1 tron not re-issue this call. 294 1.1 tron 295 1.1.1.2 tron <li> Mail was discarded with "<a href="postconf.5.html#local_recipient_maps">local_recipient_maps</a> = <a href="DATABASE_README.html#types">static</a>:all" and 296 1.1 tron "<a href="postconf.5.html#local_transport">local_transport</a> = discard". The discard action in access maps or 297 1.1 tron header/body checks 298 1.1 tron could not be used as it fails to update the <a href="postconf.5.html#in_flow_delay">in_flow_delay</a> counters. 299 1.1 tron 300 1.1 tron </ul> 301 1.1 tron 302 1.1 tron <p> Client configuration: </p> 303 1.1 tron 304 1.1 tron <ul> 305 1.1 tron 306 1.1 tron <li> Queue file overhead was minimized by sending one message to a 307 1.1 tron virtual alias that expanded into 2000 different remote recipients. 308 1.1 tron All recipients were accounted for according to the maillog file. 309 1.1 tron The <a href="postconf.5.html#virtual_alias_expansion_limit">virtual_alias_expansion_limit</a> setting was increased to avoid 310 1.1 tron complaints from the <a href="cleanup.8.html">cleanup(8)</a> server. 311 1.1 tron 312 1.1 tron <li> The number of deliveries was maximized with 313 1.1 tron "<a href="postconf.5.html#smtp_destination_recipient_limit">smtp_destination_recipient_limit</a> = 2". A smaller limit would cause 314 1.1 tron Postfix to schedule the concurrency per recipient instead of domain, 315 1.1 tron which is not what we want. 316 1.1 tron 317 1.1 tron <li> Maximum concurrency was limited with 318 1.1 tron "<a href="postconf.5.html#smtp_destination_concurrency_limit">smtp_destination_concurrency_limit</a> = 20", and 319 1.1 tron <a href="postconf.5.html#initial_destination_concurrency">initial_destination_concurrency</a> was set to the same value. 320 1.1 tron 321 1.1 tron <li> The positive and negative concurrency feedback hysteresis was 322 1.1 tron 1. Concurrency was incremented by 1 at the END of 1/feedback steps 323 1.1 tron of positive feedback, and was decremented by 1 at the START of 324 1.1 tron 1/feedback steps of negative feedback. 325 1.1 tron 326 1.1 tron <li> The SMTP client used the default 30s SMTP connect timeout and 327 1.1 tron 300s SMTP greeting timeout. 328 1.1 tron 329 1.1 tron </ul> 330 1.1 tron 331 1.1 tron <h4> Impact of the 30s SMTP connect timeout </h4> 332 1.1 tron 333 1.1 tron <p> The first results are for a FreeBSD 6.2 server, where our 334 1.1 tron artificially low listen(2) backlog results in a very short kernel 335 1.1 tron queue for established connections. The table shows that all deferred 336 1.1 tron deliveries failed due to a 30s connection timeout, and none failed 337 1.1 tron due to a server greeting timeout. This measurement simulates what 338 1.1 tron happens when the server's connection queue is completely full under 339 1.1 tron load, and the TCP engine drops new connections. </p> 340 1.1 tron 341 1.1 tron <blockquote> 342 1.1 tron 343 1.1 tron <table> 344 1.1 tron 345 1.1 tron <tr> <th>client<br> limit</th> <th>server<br> limit</th> <th>feedback<br> 346 1.1 tron style</th> <th>connection<br> caching</th> <th>percentage<br> 347 1.1 tron deferred</th> <th colspan="2">client concurrency<br> average/stddev</th> 348 1.1 tron <th colspan=2>timed-out in<br> connect/greeting </th> </tr> 349 1.1 tron 350 1.1 tron <tr> <td align="center" colspan="9"> <hr> </td> </tr> 351 1.1 tron 352 1.1 tron <tr><td align="center">20</td> <td align="center">5</td> <td 353 1.1 tron align="center">1/N</td> <td align="center">no</td> <td 354 1.1 tron align="center">9.9</td> <td align="center">19.4</td> <td 355 1.1 tron align="center">0.49</td> <td align="center">198</td> <td 356 1.1 tron align="center">-</td> </tr> 357 1.1 tron 358 1.1 tron <tr><td align="center">20</td> <td align="center">5</td> <td 359 1.1 tron align="center">1/N</td> <td align="center">yes</td> <td 360 1.1 tron align="center">10.3</td> <td align="center">19.4</td> <td 361 1.1 tron align="center">0.49</td> <td align="center">206</td> <td 362 1.1 tron align="center">-</td> </tr> 363 1.1 tron 364 1.1 tron <tr><td align="center">20</td> <td align="center">5</td> <td 365 1.1 tron align="center">1/sqrt(N)</td> <td align="center">no</td> 366 1.1 tron <td align="center">10.4</td> <td align="center">19.6</td> <td 367 1.1 tron align="center">0.59</td> <td align="center">208</td> <td 368 1.1 tron align="center">-</td> </tr> 369 1.1 tron 370 1.1 tron <tr><td align="center">20</td> <td align="center">5</td> <td 371 1.1 tron align="center">1/sqrt(N)</td> <td align="center">yes</td> 372 1.1 tron <td align="center">10.6</td> <td align="center">19.6</td> <td 373 1.1 tron align="center">0.61</td> <td align="center">212</td> <td 374 1.1 tron align="center">-</td> </tr> 375 1.1 tron 376 1.1 tron <tr><td align="center">20</td> <td align="center">5</td> <td 377 1.1 tron align="center">1</td> <td align="center">no</td> <td 378 1.1 tron align="center">10.1</td> <td align="center">19.5</td> <td 379 1.1 tron align="center">1.29</td> <td align="center">202</td> <td 380 1.1 tron align="center">-</td> </tr> 381 1.1 tron 382 1.1 tron <tr><td align="center">20</td> <td align="center">5</td> <td 383 1.1 tron align="center">1</td> <td align="center">yes</td> <td 384 1.1 tron align="center">10.8</td> <td align="center">19.3</td> <td 385 1.1 tron align="center">1.57</td> <td align="center">216</td> <td 386 1.1 tron align="center">-</td> </tr> 387 1.1 tron 388 1.1 tron <tr> <td align="center" colspan="9"> <hr> </td> </tr> 389 1.1 tron 390 1.1 tron </table> 391 1.1 tron 392 1.1 tron <p> A busy server with a completely full connection queue. N is 393 1.1 tron the client delivery concurrency. Failed deliveries time out after 394 1.1 tron 30s without completing the TCP handshake. See text for a discussion 395 1.1 tron of results. </p> 396 1.1 tron 397 1.1 tron </blockquote> 398 1.1 tron 399 1.1 tron <h4> Impact of the 300s SMTP greeting timeout </h4> 400 1.1 tron 401 1.1 tron <p> The next table shows results for a Fedora Core 8 server (results 402 1.1 tron for RedHat 7.3 are identical). In this case, the artificially small 403 1.1 tron listen(2) backlog argument does not impact our measurement. The 404 1.1 tron table shows that practically all deferred deliveries fail after the 405 1.1 tron 300s SMTP greeting timeout. As these timeouts were 10x longer than 406 1.1 tron with the first measurement, we increased the recipient count (and 407 1.1 tron thus the running time) by a factor of 10 to keep the results 408 1.1 tron comparable. The deferred mail percentages are a factor 10 lower 409 1.1 tron than with the first measurement, because the 1s per-recipient delay 410 1.1 tron was 1/300th of the greeting timeout instead of 1/30th of the 411 1.1 tron connection timeout. </p> 412 1.1 tron 413 1.1 tron <blockquote> 414 1.1 tron 415 1.1 tron <table> 416 1.1 tron 417 1.1 tron <tr> <th>client<br> limit</th> <th>server<br> limit</th> <th>feedback<br> 418 1.1 tron style</th> <th>connection<br> caching</th> <th>percentage<br> 419 1.1 tron deferred</th> <th colspan="2">client concurrency<br> average/stddev</th> 420 1.1 tron <th colspan=2>timed-out in<br> connect/greeting </th> </tr> 421 1.1 tron 422 1.1 tron <tr> <td align="center" colspan="9"> <hr> </td> </tr> 423 1.1 tron 424 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 425 1.1 tron align="center">1/N</td> <td align="center">no</td> <td 426 1.1 tron align="center">1.16</td> <td align="center">19.8</td> <td 427 1.1 tron align="center">0.37</td> <td align="center">-</td> <td 428 1.1 tron align="center">230</td> </tr> 429 1.1 tron 430 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 431 1.1 tron align="center">1/N</td> <td align="center">yes</td> <td 432 1.1 tron align="center">1.36</td> <td align="center">19.8</td> <td 433 1.1 tron align="center">0.36</td> <td align="center">-</td> <td 434 1.1 tron align="center">272</td> </tr> 435 1.1 tron 436 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 437 1.1 tron align="center">1/sqrt(N)</td> <td align="center">no</td> 438 1.1 tron <td align="center">1.21</td> <td align="center">19.9</td> <td 439 1.1 tron align="center">0.23</td> <td align="center">4</td> <td 440 1.1 tron align="center">238</td> </tr> 441 1.1 tron 442 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 443 1.1 tron align="center">1/sqrt(N)</td> <td align="center">yes</td> 444 1.1 tron <td align="center">1.36</td> <td align="center">20.0</td> <td 445 1.1 tron align="center">0.23</td> <td align="center">-</td> <td 446 1.1 tron align="center">272</td> </tr> 447 1.1 tron 448 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 449 1.1 tron align="center">1</td> <td align="center">no</td> <td 450 1.1 tron align="center">1.18</td> <td align="center">20.0</td> <td 451 1.1 tron align="center">0.16</td> <td align="center">-</td> <td 452 1.1 tron align="center">236</td> </tr> 453 1.1 tron 454 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 455 1.1 tron align="center">1</td> <td align="center">yes</td> <td 456 1.1 tron align="center">1.39</td> <td align="center">20.0</td> <td 457 1.1 tron align="center">0.16</td> <td align="center">-</td> <td 458 1.1 tron align="center">278</td> </tr> 459 1.1 tron 460 1.1 tron <tr> <td align="center" colspan="9"> <hr> </td> </tr> 461 1.1 tron 462 1.1 tron </table> 463 1.1 tron 464 1.1 tron <p> A busy server with a non-full connection queue. N is the client 465 1.1 tron delivery concurrency. Failed deliveries complete at the TCP level, 466 1.1 tron but time out after 300s while waiting for the SMTP greeting. See 467 1.1 tron text for a discussion of results. </p> 468 1.1 tron 469 1.1 tron </blockquote> 470 1.1 tron 471 1.1 tron <h4> Impact of active server concurrency limiter </h4> 472 1.1 tron 473 1.1 tron <p> The final concurrency-limited result shows what happens when 474 1.1 tron SMTP connections don't time out, but are rejected immediately with 475 1.1 tron the Postfix server's <a href="postconf.5.html#smtpd_client_connection_count_limit">smtpd_client_connection_count_limit</a> feature 476 1.1 tron (the server replies with a 421 status and disconnects immediately). 477 1.1 tron Similar results can be expected with concurrency limiting features 478 1.1 tron built into other MTAs or firewalls. For this measurement we specified 479 1.1 tron a server concurrency limit and a client initial destination concurrency 480 1.1 tron of 5, and a server process limit of 10; all other conditions were 481 1.1 tron the same as with the first measurement. The same result would be 482 1.1 tron obtained with a FreeBSD or Linux server, because the "pushing back" 483 1.1 tron is done entirely by the receiving side. </p> 484 1.1 tron 485 1.1 tron <blockquote> 486 1.1 tron 487 1.1 tron <table> 488 1.1 tron 489 1.1 tron <tr> <th>client<br> limit</th> <th>server<br> limit</th> <th>feedback<br> 490 1.1 tron style</th> <th>connection<br> caching</th> <th>percentage<br> 491 1.1 tron deferred</th> <th colspan="2">client concurrency<br> average/stddev</th> 492 1.1 tron <th>theoretical<br>defer rate</th> </tr> 493 1.1 tron 494 1.1 tron <tr> <td align="center" colspan="9"> <hr> </td> </tr> 495 1.1 tron 496 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 497 1.1 tron align="center">1/N</td> <td align="center">no</td> <td 498 1.1 tron align="center">16.5</td> <td align="center">5.17</td> <td 499 1.1 tron align="center">0.38</td> <td align="center">1/6</td> </tr> 500 1.1 tron 501 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 502 1.1 tron align="center">1/N</td> <td align="center">yes</td> <td 503 1.1 tron align="center">16.5</td> <td align="center">5.17</td> <td 504 1.1 tron align="center">0.38</td> <td align="center">1/6</td> </tr> 505 1.1 tron 506 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 507 1.1 tron align="center">1/sqrt(N)</td> <td align="center">no</td> 508 1.1 tron <td align="center">24.5</td> <td align="center">5.28</td> <td 509 1.1 tron align="center">0.45</td> <td align="center">1/4</td> </tr> 510 1.1 tron 511 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 512 1.1 tron align="center">1/sqrt(N)</td> <td align="center">yes</td> 513 1.1 tron <td align="center">24.3</td> <td align="center">5.28</td> <td 514 1.1 tron align="center">0.46</td> <td align="center">1/4</td> </tr> 515 1.1 tron 516 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 517 1.1 tron align="center">1</td> <td align="center">no</td> <td 518 1.1 tron align="center">49.7</td> <td align="center">5.63</td> <td 519 1.1 tron align="center">0.67</td> <td align="center">1/2</td> </tr> 520 1.1 tron 521 1.1 tron <tr> <td align="center">20</td> <td align="center">5</td> <td 522 1.1 tron align="center">1</td> <td align="center">yes</td> <td 523 1.1 tron align="center">49.7</td> <td align="center">5.68</td> <td 524 1.1 tron align="center">0.70</td> <td align="center">1/2</td> </tr> 525 1.1 tron 526 1.1 tron <tr> <td align="center" colspan="9"> <hr> </td> </tr> 527 1.1 tron 528 1.1 tron </table> 529 1.1 tron 530 1.1 tron <p> A server with active per-client concurrency limiter that replies 531 1.1 tron with 421 and disconnects. N is the client delivery concurrency. 532 1.1 tron The theoretical defer rate is 1/(1+roundup(1/feedback)). This is 533 1.1 tron always 1/2 with the fixed +/-1 feedback per delivery; with the 534 1.1 tron concurrency-dependent feedback variants, the defer rate decreases 535 1.1 tron with increasing concurrency. See text for a discussion of results. 536 1.1 tron </p> 537 1.1 tron 538 1.1 tron </blockquote> 539 1.1 tron 540 1.1 tron <h3> <a name="concurrency_discussion"> Discussion of concurrency-limited server results </a> </h3> 541 1.1 tron 542 1.1 tron <p> All results in the previous sections are based on the first 543 1.1 tron delivery runs only; they do not include any second etc. delivery 544 1.1 tron attempts. It's also worth noting that the measurements look at 545 1.1 tron steady-state behavior only. They don't show what happens when the 546 1.1 tron client starts sending at a much higher or lower concurrency. 547 1.1 tron </p> 548 1.1 tron 549 1.1 tron <p> The first two examples show that the effect of feedback 550 1.1 tron is negligible when concurrency is limited due to congestion. This 551 1.1 tron is because the initial concurrency is already at the client's 552 1.1 tron concurrency maximum, and because there is 10-100 times more positive 553 1.1 tron than negative feedback. Under these conditions, it is no surprise 554 1.1 tron that the contribution from SMTP connection caching is also negligible. 555 1.1 tron </p> 556 1.1 tron 557 1.1 tron <p> In the last example, the old +/-1 feedback per delivery will 558 1.1 tron defer 50% of the mail when confronted with an active (anvil-style) 559 1.1 tron server concurrency limit, where the server hangs up immediately 560 1.1 tron with a 421 status (a TCP-level RST would have the same result). 561 1.1 tron Less aggressive feedback mechanisms fare better than more aggressive 562 1.1 tron ones. Concurrency-dependent feedback fares even better at higher 563 1.1 tron concurrencies than shown here, but has limitations as discussed in 564 1.1 tron the next section. </p> 565 1.1 tron 566 1.1 tron <h3> <a name="concurrency_limitations"> Limitations of less-than-1 per delivery feedback </a> </h3> 567 1.1 tron 568 1.1 tron <p> Less-than-1 feedback is of interest primarily when sending large 569 1.1 tron amounts of mail to destinations with active concurrency limiters 570 1.1 tron (servers that reply with 421, or firewalls that send RST). When 571 1.1 tron sending small amounts of mail per destination, less-than-1 per-delivery 572 1.1 tron feedback won't have a noticeable effect on the per-destination 573 1.1 tron concurrency, because the number of deliveries to the same destination 574 1.1 tron is too small. You might just as well use zero per-delivery feedback 575 1.1 tron and stay with the initial per-destination concurrency. And when 576 1.1 tron mail deliveries fail due to congestion instead of active concurrency 577 1.1 tron limiters, the measurements above show that per-delivery feedback 578 1.1 tron has no effect. With large amounts of mail you might just as well 579 1.1 tron use zero per-delivery feedback and start with the maximal per-destination 580 1.1 tron concurrency. </p> 581 1.1 tron 582 1.1 tron <p> The scheduler with less-than-1 concurrency 583 1.1 tron feedback per delivery solves a problem with servers that have active 584 1.1 tron concurrency limiters. This works only because feedback is handled 585 1.1 tron in a peculiar manner: positive feedback will increment the concurrency 586 1.1 tron by 1 at the <b>end</b> of a sequence of events of length 1/feedback, 587 1.1 tron while negative feedback will decrement concurrency by 1 at the 588 1.1 tron <b>beginning</b> of such a sequence. This is how Postfix adjusts 589 1.1 tron quickly for overshoot without causing lots of mail to be deferred. 590 1.1 tron Without this difference in feedback treatment, less-than-1 feedback 591 1.1 tron per delivery would defer 50% of the mail, and would be no better 592 1.1 tron in this respect than the old +/-1 feedback per delivery. </p> 593 1.1 tron 594 1.1 tron <p> Unfortunately, the same feature that corrects quickly for 595 1.1 tron concurrency overshoot also makes the scheduler more sensitive for 596 1.1 tron noisy negative feedback. The reason is that one lonely negative 597 1.1 tron feedback event has the same effect as a complete sequence of length 598 1.1 tron 1/feedback: in both cases delivery concurrency is dropped by 1 599 1.1 tron immediately. As a worst-case scenario, consider multiple servers 600 1.1 tron behind a load balancer on a single IP address, and no backup MX 601 1.1 tron address. When 1 out of K servers fails to complete the SMTP handshake 602 1.1 tron or drops the connection, a scheduler with 1/N (N = concurrency) 603 1.1 tron feedback stops increasing its concurrency once it reaches a concurrency 604 1.1 tron level of about K, even though the good servers behind the load 605 1.1 tron balancer are perfectly capable of handling more traffic. </p> 606 1.1 tron 607 1.1 tron <p> This noise problem gets worse as the amount of positive feedback 608 1.1 tron per delivery gets smaller. A compromise is to use fixed less-than-1 609 1.1 tron positive feedback values instead of concurrency-dependent positive 610 1.1 tron feedback. For example, to tolerate 1 of 4 bad servers in the above 611 1.1 tron load balancer scenario, use positive feedback of 1/4 per "good" 612 1.1 tron delivery (no connect or handshake error), and use an equal or smaller 613 1.1 tron amount of negative feedback per "bad" delivery. The downside of 614 1.1 tron using concurrency-independent feedback is that some of the old +/-1 615 1.1 tron feedback problems will return at large concurrencies. Sites that 616 1.1 tron must deliver mail at non-trivial per-destination concurrencies will 617 1.1 tron require special configuration. </p> 618 1.1 tron 619 1.1 tron <h3> <a name="concurrency_config"> Concurrency configuration parameters </a> </h3> 620 1.1 tron 621 1.1 tron <p> The Postfix 2.5 concurrency scheduler is controlled with the 622 1.1 tron following configuration parameters, where "<i>transport</i>_foo" 623 1.1 tron provides a transport-specific parameter override. All parameter 624 1.1 tron default settings are compatible with earlier Postfix versions. </p> 625 1.1 tron 626 1.1 tron <blockquote> 627 1.1 tron 628 1.1 tron <table border="0"> 629 1.1 tron 630 1.1 tron <tr> <th> Parameter name </th> <th> Postfix version </th> <th> 631 1.1 tron Description </th> </tr> 632 1.1 tron 633 1.1 tron <tr> <td colspan="3"> <hr> </td> </tr> 634 1.1 tron 635 1.1 tron <tr> <td> <a href="postconf.5.html#initial_destination_concurrency">initial_destination_concurrency</a><br> 636 1.1 tron <a href="postconf.5.html#transport_initial_destination_concurrency"><i>transport</i>_initial_destination_concurrency</a> </td> <td 637 1.1 tron align="center"> all<br> 2.5 </td> <td> Initial per-destination 638 1.1 tron delivery concurrency </td> </tr> 639 1.1 tron 640 1.1 tron <tr> <td> <a href="postconf.5.html#default_destination_concurrency_limit">default_destination_concurrency_limit</a><br> 641 1.1 tron <a href="postconf.5.html#transport_destination_concurrency_limit"><i>transport</i>_destination_concurrency_limit</a> </td> <td align="center"> 642 1.1 tron all<br> all </td> <td> Maximum per-destination delivery concurrency 643 1.1 tron </td> </tr> 644 1.1 tron 645 1.1 tron <tr> <td> <a href="postconf.5.html#default_destination_concurrency_positive_feedback">default_destination_concurrency_positive_feedback</a><br> 646 1.1 tron <a href="postconf.5.html#transport_destination_concurrency_positive_feedback"><i>transport</i>_destination_concurrency_positive_feedback</a> </td> 647 1.1 tron <td align="center"> 2.5<br> 2.5 </td> <td> Per-destination positive 648 1.1 tron feedback amount, per delivery that does not fail with connection 649 1.1 tron or handshake failure </td> </tr> 650 1.1 tron 651 1.1 tron <tr> <td> <a href="postconf.5.html#default_destination_concurrency_negative_feedback">default_destination_concurrency_negative_feedback</a><br> 652 1.1 tron <a href="postconf.5.html#transport_destination_concurrency_negative_feedback"><i>transport</i>_destination_concurrency_negative_feedback</a> </td> 653 1.1 tron <td align="center"> 2.5<br> 2.5 </td> <td> Per-destination negative 654 1.1 tron feedback amount, per delivery that fails with connection or handshake 655 1.1 tron failure </td> </tr> 656 1.1 tron 657 1.1 tron <tr> <td> <a href="postconf.5.html#default_destination_concurrency_failed_cohort_limit">default_destination_concurrency_failed_cohort_limit</a><br> 658 1.1 tron <a href="postconf.5.html#transport_destination_concurrency_failed_cohort_limit"><i>transport</i>_destination_concurrency_failed_cohort_limit</a> </td> 659 1.1 tron <td align="center"> 2.5<br> 2.5 </td> <td> Number of failed 660 1.1 tron pseudo-cohorts after which a destination is declared "dead" and 661 1.1 tron delivery is suspended </td> </tr> 662 1.1 tron 663 1.1 tron <tr> <td> <a href="postconf.5.html#destination_concurrency_feedback_debug">destination_concurrency_feedback_debug</a></td> <td align="center"> 664 1.1 tron 2.5 </td> <td> Enable verbose logging of concurrency scheduler 665 1.1 tron activity </td> </tr> 666 1.1 tron 667 1.1 tron <tr> <td colspan="3"> <hr> </td> </tr> 668 1.1 tron 669 1.1 tron </table> 670 1.1 tron 671 1.1 tron </blockquote> 672 1.1 tron 673 1.1 tron <h2> <a name="jobs"> Preemptive scheduling </a> </h2> 674 1.1 tron 675 1.1 tron <p> 676 1.1 tron 677 1.1 tron The following sections describe the new queue manager and its 678 1.1 tron preemptive scheduler algorithm. Note that the document was originally 679 1.1 tron written to describe the changes between the new queue manager (in 680 1.1 tron this text referred to as <tt>nqmgr</tt>, the name it was known by 681 1.1 tron before it became the default queue manager) and the old queue manager 682 1.1 tron (referred to as <tt>oqmgr</tt>). This is why it refers to <tt>oqmgr</tt> 683 1.1 tron every so often. 684 1.1 tron 685 1.1 tron </p> 686 1.1 tron 687 1.1 tron <p> 688 1.1 tron 689 1.1 tron This document is divided into sections as follows: 690 1.1 tron 691 1.1 tron </p> 692 1.1 tron 693 1.1 tron <ul> 694 1.1 tron 695 1.1 tron <li> <a href="#<tt>nqmgr</tt>_structures"> The structures used by 696 1.1 tron nqmgr </a> 697 1.1 tron 698 1.1 tron <li> <a href="#<tt>nqmgr</tt>_pickup"> What happens when nqmgr picks 699 1.1 tron up the message </a> - how it is assigned to transports, jobs, peers, 700 1.1 tron entries 701 1.1 tron 702 1.1 tron <li> <a href="#<tt>nqmgr</tt>_selection"> How the entry selection 703 1.1 tron works </a> 704 1.1 tron 705 1.1 tron <li> <a href="#<tt>nqmgr</tt>_preemption"> How the preemption 706 1.1 tron works </a> - what messages may be preempted and how and what messages 707 1.1 tron are chosen to preempt them 708 1.1 tron 709 1.1 tron <li> <a href="#<tt>nqmgr</tt>_concurrency"> How destination concurrency 710 1.1 tron limits affect the scheduling algorithm </a> 711 1.1 tron 712 1.1 tron <li> <a href="#<tt>nqmgr</tt>_memory"> Dealing with memory resource 713 1.1 tron limits </a> 714 1.1 tron 715 1.1 tron </ul> 716 1.1 tron 717 1.1 tron <h3> <a name="<tt>nqmgr</tt>_structures"> The structures used by 718 1.1 tron nqmgr </a> </h3> 719 1.1 tron 720 1.1 tron <p> 721 1.1 tron 722 1.1 tron Let's start by recapitulating the structures and terms used when 723 1.1 tron referring to queue manager and how it operates. Many of these are 724 1.1 tron partially described elsewhere, but it is nice to have a coherent 725 1.1 tron overview in one place: 726 1.1 tron 727 1.1 tron </p> 728 1.1 tron 729 1.1 tron <ul> 730 1.1 tron 731 1.1 tron <li> <p> Each message structure represents one mail message which 732 1.1 tron Postfix is to deliver. The message recipients specify to what 733 1.1 tron destinations is the message to be delivered and what transports are 734 1.1 tron going to be used for the delivery. </p> 735 1.1 tron 736 1.1 tron <li> <p> Each recipient entry groups a batch of recipients of one 737 1.1.1.3 tron message which are all going to be delivered to the same destination 738 1.1.1.3 tron (and over the same transport). 739 1.1 tron </p> 740 1.1 tron 741 1.1 tron <li> <p> Each transport structure groups everything what is going 742 1.1 tron to be delivered by delivery agents dedicated for that transport. 743 1.1 tron Each transport maintains a set of queues (describing the destinations 744 1.1 tron it shall talk to) and jobs (referencing the messages it shall 745 1.1 tron deliver). </p> 746 1.1 tron 747 1.1 tron <li> <p> Each transport queue (not to be confused with the on-disk 748 1.1 tron <a href="QSHAPE_README.html#active_queue">active queue</a> or <a href="QSHAPE_README.html#incoming_queue">incoming queue</a>) groups everything what is going be 749 1.1 tron delivered to given destination (aka nexthop) by its transport. Each 750 1.1 tron queue belongs to one transport, so each destination may be referred 751 1.1 tron to by several queues, one for each transport. Each queue maintains 752 1.1 tron a list of all recipient entries (batches of message recipients) 753 1.1 tron which shall be delivered to given destination (the todo list), and 754 1.1 tron a list of recipient entries already being delivered by the delivery 755 1.1 tron agents (the busy list). </p> 756 1.1 tron 757 1.1 tron <li> <p> Each queue corresponds to multiple peer structures. Each 758 1.1 tron peer structure is like the queue structure, belonging to one transport 759 1.1 tron and referencing one destination. The difference is that it lists 760 1.1 tron only the recipient entries which all originate from the same message, 761 1.1 tron unlike the queue structure, whose entries may originate from various 762 1.1 tron messages. For messages with few recipients, there is usually just 763 1.1 tron one recipient entry for each destination, resulting in one recipient 764 1.1 tron entry per peer. But for large mailing list messages the recipients 765 1.1 tron may need to be split to multiple recipient entries, in which case 766 1.1 tron the peer structure may list many entries for single destination. 767 1.1 tron </p> 768 1.1 tron 769 1.1 tron <li> <p> Each transport job groups everything it takes to deliver 770 1.1 tron one message via its transport. Each job represents one message 771 1.1 tron within the context of the transport. The job belongs to one transport 772 1.1 tron and message, so each message may have multiple jobs, one for each 773 1.1 tron transport. The job groups all the peer structures, which describe 774 1.1 tron the destinations the job's message has to be delivered to. </p> 775 1.1 tron 776 1.1 tron </ul> 777 1.1 tron 778 1.1 tron <p> 779 1.1 tron 780 1.1 tron The first four structures are common to both <tt>nqmgr</tt> and 781 1.1 tron <tt>oqmgr</tt>, the latter two were introduced by <tt>nqmgr</tt>. 782 1.1 tron 783 1.1 tron </p> 784 1.1 tron 785 1.1 tron <p> 786 1.1 tron 787 1.1 tron These terms are used extensively in the text below, feel free to 788 1.1 tron look up the description above anytime you'll feel you have lost a 789 1.1 tron sense what is what. 790 1.1 tron 791 1.1 tron </p> 792 1.1 tron 793 1.1 tron <h3> <a name="<tt>nqmgr</tt>_pickup"> What happens when nqmgr picks 794 1.1 tron up the message </a> </h3> 795 1.1 tron 796 1.1 tron <p> 797 1.1 tron 798 1.1 tron Whenever <tt>nqmgr</tt> moves a queue file into the <a href="QSHAPE_README.html#active_queue">active queue</a>, 799 1.1 tron the following happens: It reads all necessary information from the 800 1.1 tron queue file as <tt>oqmgr</tt> does, and also reads as many recipients 801 1.1 tron as possible - more on that later, for now let's just pretend it 802 1.1 tron always reads all recipients. 803 1.1 tron 804 1.1 tron </p> 805 1.1 tron 806 1.1 tron <p> 807 1.1 tron 808 1.1 tron Then it resolves the recipients as <tt>oqmgr</tt> does, which 809 1.1 tron means obtaining (address, nexthop, transport) triple for each 810 1.1 tron recipient. For each triple, it finds the transport; if it does not 811 1.1 tron exist yet, it instantiates it (unless it's dead). Within the 812 1.1 tron transport, it finds the destination queue for given nexthop; if it 813 1.1 tron does not exist yet, it instantiates it (unless it's dead). The 814 1.1 tron triple is then bound to given destination queue. This happens in 815 1.1 tron qmgr_resolve() and is basically the same as in <tt>oqmgr</tt>. 816 1.1 tron 817 1.1 tron </p> 818 1.1 tron 819 1.1 tron <p> 820 1.1 tron 821 1.1 tron Then for each triple which was bound to some queue (and thus 822 1.1 tron transport), the program finds the job which represents the message 823 1.1 tron within that transport's context; if it does not exist yet, it 824 1.1 tron instantiates it. Within the job, it finds the peer which represents 825 1.1 tron the bound destination queue within this jobs context; if it does 826 1.1 tron not exist yet, it instantiates it. Finally, it stores the address 827 1.1 tron from the resolved triple to the recipient entry which is appended 828 1.1 tron to both the queue entry list and the peer entry list. The addresses 829 1.1 tron for same nexthop are batched in the entries up to recipient_concurrency 830 1.1 tron limit for that transport. This happens in qmgr_assign() and apart 831 1.1 tron from that it operates with job and peer structures it is basically the 832 1.1 tron same as in <tt>oqmgr</tt>. 833 1.1 tron 834 1.1 tron </p> 835 1.1 tron 836 1.1 tron <p> 837 1.1 tron 838 1.1 tron When the job is instantiated, it is enqueued on the transport's job 839 1.1 tron list based on the time its message was picked up by <tt>nqmgr</tt>. 840 1.1 tron For first batch of recipients this means it is appended to the end 841 1.1 tron of the job list, but the ordering of the job list by the enqueue 842 1.1 tron time is important as we will see shortly. 843 1.1 tron 844 1.1 tron </p> 845 1.1 tron 846 1.1 tron <p> 847 1.1 tron 848 1.1 tron [Now you should have pretty good idea what is the state of the 849 1.1 tron <tt>nqmgr</tt> after couple of messages was picked up, what is the 850 1.1 tron relation between all those job, peer, queue and entry structures.] 851 1.1 tron 852 1.1 tron </p> 853 1.1 tron 854 1.1 tron <h3> <a name="<tt>nqmgr</tt>_selection"> How the entry selection 855 1.1 tron works </a> </h3> 856 1.1 tron 857 1.1 tron <p> 858 1.1 tron 859 1.1 tron Having prepared all those above mentioned structures, the task of 860 1.1 tron the <tt>nqmgr</tt>'s scheduler is to choose the recipient entries 861 1.1 tron one at a time and pass them to the delivery agent for corresponding 862 1.1 tron transport. Now how does this work? 863 1.1 tron 864 1.1 tron </p> 865 1.1 tron 866 1.1 tron <p> 867 1.1 tron 868 1.1 tron The first approximation of the new scheduling algorithm is like this: 869 1.1 tron 870 1.1 tron </p> 871 1.1 tron 872 1.1 tron <blockquote> 873 1.1 tron <pre> 874 1.1 tron foreach transport (round-robin-by-transport) 875 1.1 tron do 876 1.1 tron if transport busy continue 877 1.1 tron if transport process limit reached continue 878 1.1 tron foreach transport's job (in the order of the transport's job list) 879 1.1 tron do 880 1.1.1.3 tron foreach job's peer (round-robin-by-destination) 881 1.1.1.3 tron if peer->queue->concurrency < peer->queue->window 882 1.1.1.3 tron return next peer entry. 883 1.1.1.3 tron done 884 1.1 tron done 885 1.1 tron done 886 1.1 tron </pre> 887 1.1 tron </blockquote> 888 1.1 tron 889 1.1 tron <p> 890 1.1 tron 891 1.1 tron Now what is the "order of the transport's job list"? As we know 892 1.1 tron already, the job list is by default kept in the order the message 893 1.1 tron was picked up by the <tt>nqmgr</tt>. So by default we get the 894 1.1 tron top-level round-robin transport, and within each transport we get 895 1.1 tron the FIFO message delivery. The round-robin of the peers by the 896 1.1 tron destination is perhaps of little importance in most real-life cases 897 1.1 tron (unless the recipient_concurrency limit is reached, in one job there 898 1.1 tron is only one peer structure for each destination), but theoretically 899 1.1 tron it makes sure that even within single jobs, destinations are treated 900 1.1 tron fairly. 901 1.1 tron 902 1.1 tron </p> 903 1.1 tron 904 1.1 tron <p> 905 1.1 tron 906 1.1 tron [By now you should have a feeling you really know how the scheduler 907 1.1 tron works, except for the preemption, under ideal conditions - that is, 908 1.1 tron no recipient resource limits and no destination concurrency problems.] 909 1.1 tron 910 1.1 tron </p> 911 1.1 tron 912 1.1 tron <h3> <a name="<tt>nqmgr</tt>_preemption"> How the preemption 913 1.1 tron works </a> </h3> 914 1.1 tron 915 1.1 tron <p> 916 1.1 tron 917 1.1 tron As you might perhaps expect by now, the transport's job list does 918 1.1 tron not remain sorted by the job's message enqueue time all the time. 919 1.1 tron The most cool thing about <tt>nqmgr</tt> is not the simple FIFO 920 1.1 tron delivery, but that it is able to slip mail with little recipients 921 1.1 tron past the mailing-list bulk mail. This is what the job preemption 922 1.1 tron is about - shuffling the jobs on the transport's job list to get 923 1.1 tron the best message delivery rates. Now how is it achieved? 924 1.1 tron 925 1.1 tron </p> 926 1.1 tron 927 1.1 tron <p> 928 1.1 tron 929 1.1 tron First I have to tell you that there are in fact two job lists in 930 1.1 tron each transport. One is the scheduler's job list, which the scheduler 931 1.1 tron is free to play with, while the other one keeps the jobs always 932 1.1 tron listed in the order of the enqueue time and is used for recipient 933 1.1 tron pool management we will discuss later. For now, we will deal with 934 1.1 tron the scheduler's job list only. 935 1.1 tron 936 1.1 tron </p> 937 1.1 tron 938 1.1 tron <p> 939 1.1 tron 940 1.1 tron So, we have the job list, which is first ordered by the time the 941 1.1 tron jobs' messages were enqueued, oldest messages first, the most recently 942 1.1 tron picked one at the end. For now, let's assume that there are no 943 1.1 tron destination concurrency problems. Without preemption, we pick some 944 1.1 tron entry of the first (oldest) job on the queue, assign it to delivery 945 1.1 tron agent, pick another one from the same job, assign it again, and so 946 1.1 tron on, until all the entries are used and the job is delivered. We 947 1.1 tron would then move onto the next job and so on and on. Now how do we 948 1.1 tron manage to sneak in some entries from the recently added jobs when 949 1.1 tron the first job on the job list belongs to a message going to the 950 1.1 tron mailing-list and has thousands of recipient entries? 951 1.1 tron 952 1.1 tron </p> 953 1.1 tron 954 1.1 tron <p> 955 1.1 tron 956 1.1 tron The <tt>nqmgr</tt>'s answer is that we can artificially "inflate" 957 1.1 tron the delivery time of that first job by some constant for free - it 958 1.1 tron is basically the same trick you might remember as "accumulation of 959 1.1 tron potential" from the amortized complexity lessons. For example, 960 1.1 tron instead of delivering the entries of the first job on the job list 961 1.1 tron every time a delivery agent becomes available, we can do it only 962 1.1 tron every second time. If you view the moments the delivery agent becomes 963 1.1 tron available on a timeline as "delivery slots", then instead of using 964 1.1 tron every delivery slot for the first job, we can use only every other 965 1.1 tron slot, and still the overall delivery efficiency of the first job 966 1.1 tron remains the same. So the delivery <tt>11112222</tt> becomes 967 1.1 tron <tt>1.1.1.1.2.2.2.2</tt> (1 and 2 are the imaginary job numbers, . 968 1.1 tron denotes the free slot). Now what do we do with free slots? 969 1.1 tron 970 1.1 tron </p> 971 1.1 tron 972 1.1 tron <p> 973 1.1 tron 974 1.1 tron As you might have guessed, we will use them for sneaking the mail 975 1.1 tron with little recipients in. For example, if we have one four-recipient 976 1.1 tron mail followed by four one recipients mail, the delivery sequence 977 1.1 tron (that is, the sequence in which the jobs are assigned to the 978 1.1 tron delivery slots) might look like this: <tt>12131415</tt>. Hmm, fine 979 1.1 tron for sneaking in the single recipient mail, but how do we sneak in 980 1.1 tron the mail with more than one recipient? Say if we have one four-recipient 981 1.1 tron mail followed by two two-recipient mails? 982 1.1 tron 983 1.1 tron </p> 984 1.1 tron 985 1.1 tron <p> 986 1.1 tron 987 1.1 tron The simple answer would be to use delivery sequence <tt>12121313</tt>. 988 1.1 tron But the problem is that this does not scale well. Imagine you have 989 1.1 tron mail with thousand recipients followed by mail with hundred recipients. 990 1.1 tron It is tempting to suggest the delivery sequence like <tt>121212....</tt>, 991 1.1 tron but alas! Imagine there arrives another mail with say ten recipients. 992 1.1 tron But there are no free slots anymore, so it can't slip by, not even 993 1.1 tron if it had just only one recipients. It will be stuck until the 994 1.1 tron hundred-recipient mail is delivered, which really sucks. 995 1.1 tron 996 1.1 tron </p> 997 1.1 tron 998 1.1 tron <p> 999 1.1 tron 1000 1.1 tron So, it becomes obvious that while inflating the message to get 1001 1.1 tron free slots is great idea, one has to be really careful of how the 1002 1.1 tron free slots are assigned, otherwise one might corner himself. So, 1003 1.1 tron how does <tt>nqmgr</tt> really use the free slots? 1004 1.1 tron 1005 1.1 tron </p> 1006 1.1 tron 1007 1.1 tron <p> 1008 1.1 tron 1009 1.1 tron The key idea is that one does not have to generate the free slots 1010 1.1 tron in a uniform way. The delivery sequence <tt>111...1</tt> is no 1011 1.1 tron worse than <tt>1.1.1.1</tt>, in fact, it is even better as some 1012 1.1 tron entries are in the first case selected earlier than in the second 1013 1.1 tron case, and none is selected later! So it is possible to first 1014 1.1 tron "accumulate" the free delivery slots and then use them all at once. 1015 1.1 tron It is even possible to accumulate some, then use them, then accumulate 1016 1.1 tron some more and use them again, as in <tt>11..1.1</tt> . 1017 1.1 tron 1018 1.1 tron </p> 1019 1.1 tron 1020 1.1 tron <p> 1021 1.1 tron 1022 1.1 tron Let's get back to the one hundred recipient example. We now know 1023 1.1 tron that we could first accumulate one hundred free slots, and only 1024 1.1 tron after then to preempt the first job and sneak the one hundred 1025 1.1 tron recipient mail in. Applying the algorithm recursively, we see the 1026 1.1 tron hundred recipient job can accumulate ten free delivery slots, and 1027 1.1 tron then we could preempt it and sneak in the ten-recipient mail... 1028 1.1 tron Wait wait wait! Could we? Aren't we overinflating the original one 1029 1.1 tron thousand recipient mail? 1030 1.1 tron 1031 1.1 tron </p> 1032 1.1 tron 1033 1.1 tron <p> 1034 1.1 tron 1035 1.1 tron Well, despite it looks so at the first glance, another trick will 1036 1.1 tron allow us to answer "no, we are not!". If we had said that we will 1037 1.1 tron inflate the delivery time twice at maximum, and then we consider 1038 1.1 tron every other slot as a free slot, then we would overinflate in case 1039 1.1 tron of the recursive preemption. BUT! The trick is that if we use only 1040 1.1 tron every n-th slot as a free slot for n>2, there is always some worst 1041 1.1 tron inflation factor which we can guarantee not to be breached, even 1042 1.1 tron if we apply the algorithm recursively. To be precise, if for every 1043 1.1 tron k>1 normally used slots we accumulate one free delivery slot, than 1044 1.1 tron the inflation factor is not worse than k/(k-1) no matter how many 1045 1.1 tron recursive preemptions happen. And it's not worse than (k+1)/k if 1046 1.1 tron only non-recursive preemption happens. Now, having got through the 1047 1.1 tron theory and the related math, let's see how <tt>nqmgr</tt> implements 1048 1.1 tron this. 1049 1.1 tron 1050 1.1 tron </p> 1051 1.1 tron 1052 1.1 tron <p> 1053 1.1 tron 1054 1.1 tron Each job has so called "available delivery slot" counter. Each 1055 1.1 tron transport has a <a href="postconf.5.html#transport_delivery_slot_cost"><i>transport</i>_delivery_slot_cost</a> parameter, which 1056 1.1 tron defaults to <a href="postconf.5.html#default_delivery_slot_cost">default_delivery_slot_cost</a> parameter which is set to 5 1057 1.1 tron by default. This is the k from the paragraph above. Each time k 1058 1.1 tron entries of the job are selected for delivery, this counter is 1059 1.1 tron incremented by one. Once there are some slots accumulated, job which 1060 1.1 tron requires no more than that number of slots to be fully delivered 1061 1.1 tron can preempt this job. 1062 1.1 tron 1063 1.1 tron </p> 1064 1.1 tron 1065 1.1 tron <p> 1066 1.1 tron 1067 1.1 tron [Well, the truth is, the counter is incremented every time an entry 1068 1.1.1.3 tron is selected and it is divided by k when it is used. 1069 1.1.1.3 tron But for the understanding it's good enough to use 1070 1.1 tron the above approximation of the truth.] 1071 1.1 tron 1072 1.1 tron </p> 1073 1.1 tron 1074 1.1 tron <p> 1075 1.1 tron 1076 1.1 tron OK, so now we know the conditions which must be satisfied so one 1077 1.1 tron job can preempt another one. But what job gets preempted, how do 1078 1.1 tron we choose what job preempts it if there are several valid candidates, 1079 1.1 tron and when does all this exactly happen? 1080 1.1 tron 1081 1.1 tron </p> 1082 1.1 tron 1083 1.1 tron <p> 1084 1.1 tron 1085 1.1 tron The answer for the first part is simple. The job whose entry was 1086 1.1 tron selected the last time is so called current job. Normally, it is 1087 1.1 tron the first job on the scheduler's job list, but destination concurrency 1088 1.1 tron limits may change this as we will see later. It is always only the 1089 1.1 tron current job which may get preempted. 1090 1.1 tron 1091 1.1 tron </p> 1092 1.1 tron 1093 1.1 tron <p> 1094 1.1 tron 1095 1.1 tron Now for the second part. The current job has certain amount of 1096 1.1 tron recipient entries, and as such may accumulate at maximum some amount 1097 1.1 tron of available delivery slots. It might have already accumulated some, 1098 1.1 tron and perhaps even already used some when it was preempted before 1099 1.1 tron (remember a job can be preempted several times). In either case, 1100 1.1 tron we know how many are accumulated and how many are left to deliver, 1101 1.1 tron so we know how many it may yet accumulate at maximum. Every other 1102 1.1 tron job which may be delivered by less than that number of slots is a 1103 1.1 tron valid candidate for preemption. How do we choose among them? 1104 1.1 tron 1105 1.1 tron </p> 1106 1.1 tron 1107 1.1 tron <p> 1108 1.1 tron 1109 1.1 tron The answer is - the one with maximum enqueue_time/recipient_entry_count. 1110 1.1 tron That is, the older the job is, the more we should try to deliver 1111 1.1 tron it in order to get best message delivery rates. These rates are of 1112 1.1 tron course subject to how many recipients the message has, therefore 1113 1.1 tron the division by the recipient (entry) count. No one shall be surprised 1114 1.1 tron that message with n recipients takes n times longer to deliver than 1115 1.1 tron message with one recipient. 1116 1.1 tron 1117 1.1 tron </p> 1118 1.1 tron 1119 1.1 tron <p> 1120 1.1 tron 1121 1.1 tron Now let's recap the previous two paragraphs. Isn't it too complicated? 1122 1.1 tron Why don't the candidates come only among the jobs which can be 1123 1.1 tron delivered within the number of slots the current job already 1124 1.1 tron accumulated? Why do we need to estimate how much it has yet to 1125 1.1 tron accumulate? If you found out the answer, congratulate yourself. If 1126 1.1 tron we did it this simple way, we would always choose the candidate 1127 1.1 tron with least recipient entries. If there were enough single recipient 1128 1.1 tron mails coming in, they would always slip by the bulk mail as soon 1129 1.1 tron as possible, and the two and more recipients mail would never get 1130 1.1 tron a chance, no matter how long they have been sitting around in the 1131 1.1 tron job list. 1132 1.1 tron 1133 1.1 tron </p> 1134 1.1 tron 1135 1.1 tron <p> 1136 1.1 tron 1137 1.1 tron This candidate selection has interesting implication - that when 1138 1.1 tron we choose the best candidate for preemption (this is done in 1139 1.1 tron qmgr_choose_candidate()), it may happen that we may not use it for 1140 1.1 tron preemption immediately. This leads to an answer to the last part 1141 1.1 tron of the original question - when does the preemption happen? 1142 1.1 tron 1143 1.1 tron </p> 1144 1.1 tron 1145 1.1 tron <p> 1146 1.1 tron 1147 1.1 tron The preemption attempt happens every time next transport's recipient 1148 1.1 tron entry is to be chosen for delivery. To avoid needless overhead, the 1149 1.1 tron preemption is not attempted if the current job could never accumulate 1150 1.1 tron more than <a href="postconf.5.html#transport_minimum_delivery_slots"><i>transport</i>_minimum_delivery_slots</a> (defaults to 1151 1.1 tron <a href="postconf.5.html#default_minimum_delivery_slots">default_minimum_delivery_slots</a> which defaults to 3). If there is 1152 1.1 tron already enough accumulated slots to preempt the current job by the 1153 1.1 tron chosen best candidate, it is done immediately. This basically means 1154 1.1 tron that the candidate is moved in front of the current job on the 1155 1.1 tron scheduler's job list and decreasing the accumulated slot counter 1156 1.1 tron by the amount used by the candidate. If there is not enough slots... 1157 1.1 tron well, I could say that nothing happens and the another preemption 1158 1.1 tron is attempted the next time. But that's not the complete truth. 1159 1.1 tron 1160 1.1 tron </p> 1161 1.1 tron 1162 1.1 tron <p> 1163 1.1 tron 1164 1.1 tron The truth is that it turns out that it is not really necessary to 1165 1.1 tron wait until the jobs counter accumulates all the delivery slots in 1166 1.1 tron advance. Say we have ten-recipient mail followed by two two-recipient 1167 1.1 tron mails. If the preemption happened when enough delivery slot accumulate 1168 1.1 tron (assuming slot cost 2), the delivery sequence becomes 1169 1.1 tron <tt>11112211113311</tt>. Now what would we get if we would wait 1170 1.1 tron only for 50% of the necessary slots to accumulate and we promise 1171 1.1 tron we would wait for the remaining 50% later, after we get back 1172 1.1 tron to the preempted job? If we use such slot loan, the delivery sequence 1173 1.1 tron becomes <tt>11221111331111</tt>. As we can see, it makes it no 1174 1.1 tron considerably worse for the delivery of the ten-recipient mail, but 1175 1.1 tron it allows the small messages to be delivered sooner. 1176 1.1 tron 1177 1.1 tron </p> 1178 1.1 tron 1179 1.1 tron <p> 1180 1.1 tron 1181 1.1 tron The concept of these slot loans is where the 1182 1.1 tron <a href="postconf.5.html#transport_delivery_slot_discount"><i>transport</i>_delivery_slot_discount</a> and 1183 1.1 tron <a href="postconf.5.html#transport_delivery_slot_loan"><i>transport</i>_delivery_slot_loan</a> come from (they default to 1184 1.1 tron <a href="postconf.5.html#default_delivery_slot_discount">default_delivery_slot_discount</a> and <a href="postconf.5.html#default_delivery_slot_loan">default_delivery_slot_loan</a>, whose 1185 1.1 tron values are by default 50 and 3, respectively). The discount (resp. 1186 1.1 tron loan) specifies how many percent (resp. how many slots) one "gets 1187 1.1 tron in advance", when the number of slots required to deliver the best 1188 1.1 tron candidate is compared with the number of slots the current slot had 1189 1.1 tron accumulated so far. 1190 1.1 tron 1191 1.1 tron </p> 1192 1.1 tron 1193 1.1 tron <p> 1194 1.1 tron 1195 1.1 tron And it pretty much concludes this chapter. 1196 1.1 tron 1197 1.1 tron </p> 1198 1.1 tron 1199 1.1 tron <p> 1200 1.1 tron 1201 1.1 tron [Now you should have a feeling that you pretty much understand the 1202 1.1 tron scheduler and the preemption, or at least that you will have it 1203 1.1 tron after you read the last chapter couple more times. You shall clearly 1204 1.1 tron see the job list and the preemption happening at its head, in ideal 1205 1.1 tron delivery conditions. The feeling of understanding shall last until 1206 1.1 tron you start wondering what happens if some of the jobs are blocked, 1207 1.1 tron which you might eventually figure out correctly from what had been 1208 1.1 tron said already. But I would be surprised if your mental image of the 1209 1.1 tron scheduler's functionality is not completely shattered once you 1210 1.1 tron start wondering how it works when not all recipients may be read 1211 1.1 tron in-core. More on that later.] 1212 1.1 tron 1213 1.1 tron </p> 1214 1.1 tron 1215 1.1 tron <h3> <a name="<tt>nqmgr</tt>_concurrency"> How destination concurrency 1216 1.1 tron limits affect the scheduling algorithm </a> </h3> 1217 1.1 tron 1218 1.1 tron <p> 1219 1.1 tron 1220 1.1 tron The <tt>nqmgr</tt> uses the same algorithm for destination concurrency 1221 1.1 tron control as <tt>oqmgr</tt>. Now what happens when the destination 1222 1.1 tron limits are reached and no more entries for that destination may be 1223 1.1 tron selected by the scheduler? 1224 1.1 tron 1225 1.1 tron </p> 1226 1.1 tron 1227 1.1 tron <p> 1228 1.1 tron 1229 1.1 tron From user's point of view it is all simple. If some of the peers 1230 1.1 tron of a job can't be selected, those peers are simply skipped by the 1231 1.1 tron entry selection algorithm (the pseudo-code described before) and 1232 1.1 tron only the selectable ones are used. If none of the peers may be 1233 1.1 tron selected, the job is declared a "blocker job". Blocker jobs are 1234 1.1 tron skipped by the entry selection algorithm and they are also excluded 1235 1.1 tron from the candidates for preemption of current job. Thus the scheduler 1236 1.1 tron effectively behaves as if the blocker jobs didn't exist on the job 1237 1.1 tron list at all. As soon as at least one of the peers of a blocker job 1238 1.1 tron becomes unblocked (that is, the delivery agent handling the delivery 1239 1.1 tron of the recipient entry for given destination successfully finishes), 1240 1.1 tron the job's blocker status is removed and the job again participates 1241 1.1 tron in all further scheduler actions normally. 1242 1.1 tron 1243 1.1 tron </p> 1244 1.1 tron 1245 1.1 tron <p> 1246 1.1 tron 1247 1.1 tron So the summary is that the users don't really have to be concerned 1248 1.1 tron about the interaction of the destination limits and scheduling 1249 1.1 tron algorithm. It works well on its own and there are no knobs they 1250 1.1 tron would need to control it. 1251 1.1 tron 1252 1.1 tron </p> 1253 1.1 tron 1254 1.1 tron <p> 1255 1.1 tron 1256 1.1 tron From a programmer's point of view, the blocker jobs complicate the 1257 1.1 tron scheduler quite a lot. Without them, the jobs on the job list would 1258 1.1 tron be normally delivered in strict FIFO order. If the current job is 1259 1.1 tron preempted, the job preempting it is completely delivered unless it 1260 1.1 tron is preempted itself. Without blockers, the current job is thus 1261 1.1 tron always either the first job on the job list, or the top of the stack 1262 1.1 tron of jobs preempting the first job on the job list. 1263 1.1 tron 1264 1.1 tron </p> 1265 1.1 tron 1266 1.1 tron <p> 1267 1.1 tron 1268 1.1 tron The visualization of the job list and the preemption stack without 1269 1.1 tron blockers would be like this: 1270 1.1 tron 1271 1.1 tron </p> 1272 1.1 tron 1273 1.1 tron <blockquote> 1274 1.1 tron <pre> 1275 1.1 tron first job-> 1--2--3--5--6--8--... <- job list 1276 1.1 tron on job list | 1277 1.1 tron 4 <- preemption stack 1278 1.1 tron | 1279 1.1 tron current job-> 7 1280 1.1 tron </pre> 1281 1.1 tron </blockquote> 1282 1.1 tron 1283 1.1 tron <p> 1284 1.1 tron 1285 1.1 tron In the example above we see that job 1 was preempted by job 4 and 1286 1.1 tron then job 4 was preempted by job 7. After job 7 is completed, remaining 1287 1.1 tron entries of job 4 are selected, and once they are all selected, job 1288 1.1 tron 1 continues. 1289 1.1 tron 1290 1.1 tron </p> 1291 1.1 tron 1292 1.1 tron <p> 1293 1.1 tron 1294 1.1 tron As we see, it's all very clean and straightforward. Now how does 1295 1.1 tron this change because of blockers? 1296 1.1 tron 1297 1.1 tron </p> 1298 1.1 tron 1299 1.1 tron <p> 1300 1.1 tron 1301 1.1 tron The answer is: a lot. Any job may become blocker job at any time, 1302 1.1 tron and also become normal job again at any time. This has several 1303 1.1 tron important implications: 1304 1.1 tron 1305 1.1 tron </p> 1306 1.1 tron 1307 1.1 tron <ol> 1308 1.1 tron 1309 1.1 tron <li> <p> 1310 1.1 tron 1311 1.1 tron The jobs may be completed in arbitrary order. For example, in the 1312 1.1 tron example above, if the current job 7 becomes blocked, the next job 1313 1.1 tron 4 may complete before the job 7 becomes unblocked again. Or if both 1314 1.1 tron 7 and 4 are blocked, then 1 is completed, then 7 becomes unblocked 1315 1.1 tron and is completed, then 2 is completed and only after that 4 becomes 1316 1.1 tron unblocked and is completed... You get the idea. 1317 1.1 tron 1318 1.1 tron </p> 1319 1.1 tron 1320 1.1 tron <p> 1321 1.1 tron 1322 1.1 tron [Interesting side note: even when jobs are delivered out of order, 1323 1.1 tron from single destination's point of view the jobs are still delivered 1324 1.1 tron in the expected order (that is, FIFO unless there was some preemption 1325 1.1 tron involved). This is because whenever a destination queue becomes 1326 1.1 tron unblocked (the destination limit allows selection of more recipient 1327 1.1 tron entries for that destination), all jobs which have peers for that 1328 1.1 tron destination are unblocked at once.] 1329 1.1 tron 1330 1.1 tron </p> 1331 1.1 tron 1332 1.1 tron <li> <p> 1333 1.1 tron 1334 1.1 tron The idea of the preemption stack at the head of the job list is 1335 1.1 tron gone. That is, it must be possible to preempt any job on the job 1336 1.1 tron list. For example, if the jobs 7, 4, 1 and 2 in the example above 1337 1.1 tron become all blocked, job 3 becomes the current job. And of course 1338 1.1 tron we do not want the preemption to be affected by the fact that there 1339 1.1 tron are some blocked jobs or not. Therefore, if it turns out that job 1340 1.1 tron 3 might be preempted by job 6, the implementation shall make it 1341 1.1 tron possible. 1342 1.1 tron 1343 1.1 tron </p> 1344 1.1 tron 1345 1.1 tron <li> <p> 1346 1.1 tron 1347 1.1 tron The idea of the linear preemption stack itself is gone. It's no 1348 1.1 tron longer true that one job is always preempted by only one job at one 1349 1.1 tron time (that is directly preempted, not counting the recursively 1350 1.1 tron nested jobs). For example, in the example above, job 1 is directly 1351 1.1 tron preempted by only job 4, and job 4 by job 7. Now assume job 7 becomes 1352 1.1 tron blocked, and job 4 is being delivered. If it accumulates enough 1353 1.1 tron delivery slots, it is natural that it might be preempted for example 1354 1.1 tron by job 8. Now job 4 is preempted by both job 7 AND job 8 at the 1355 1.1 tron same time. 1356 1.1 tron 1357 1.1 tron </p> 1358 1.1 tron 1359 1.1 tron </ol> 1360 1.1 tron 1361 1.1 tron <p> 1362 1.1 tron 1363 1.1 tron Now combine the points 2) and 3) with point 1) again and you realize 1364 1.1 tron that the relations on the once linear job list became pretty 1365 1.1 tron complicated. If we extend the point 3) example: jobs 7 and 8 preempt 1366 1.1 tron job 4, now job 8 becomes blocked too, then job 4 completes. Tricky, 1367 1.1 tron huh? 1368 1.1 tron 1369 1.1 tron </p> 1370 1.1 tron 1371 1.1 tron <p> 1372 1.1 tron 1373 1.1 tron If I illustrate the relations after the above mentioned examples 1374 1.1 tron (but those in point 1)), the situation would look like this: 1375 1.1 tron 1376 1.1 tron </p> 1377 1.1 tron 1378 1.1 tron <blockquote> 1379 1.1 tron <pre> 1380 1.1 tron v- parent 1381 1.1 tron 1382 1.1 tron adoptive parent -> 1--2--3--5--... <- "stack" level 0 1383 1.1 tron | | 1384 1.1 tron parent gone -> ? 6 <- "stack" level 1 1385 1.1 tron / \ 1386 1.1 tron children -> 7 8 ^- child <- "stack" level 2 1387 1.1 tron 1388 1.1 tron ^- siblings 1389 1.1 tron </pre> 1390 1.1 tron </blockquote> 1391 1.1 tron 1392 1.1 tron <p> 1393 1.1 tron 1394 1.1 tron Now how does <tt>nqmgr</tt> deal with all these complicated relations? 1395 1.1 tron 1396 1.1 tron </p> 1397 1.1 tron 1398 1.1 tron <p> 1399 1.1 tron 1400 1.1 tron Well, it maintains them all as described, but fortunately, all these 1401 1.1 tron relations are necessary only for purposes of proper counting of 1402 1.1 tron available delivery slots. For purposes of ordering the jobs for 1403 1.1 tron entry selection, the original rule still applies: "the job preempting 1404 1.1 tron the current job is moved in front of the current job on the job 1405 1.1 tron list". So for entry selection purposes, the job relations remain 1406 1.1 tron as simple as this: 1407 1.1 tron 1408 1.1 tron </p> 1409 1.1 tron 1410 1.1 tron <blockquote> 1411 1.1 tron <pre> 1412 1.1 tron 7--8--1--2--6--3--5--.. <- scheduler's job list order 1413 1.1 tron </pre> 1414 1.1 tron </blockquote> 1415 1.1 tron 1416 1.1 tron <p> 1417 1.1 tron 1418 1.1 tron The job list order and the preemption parent/child/siblings relations 1419 1.1 tron are maintained separately. And because the selection works only 1420 1.1 tron with the job list, you can happily forget about those complicated 1421 1.1 tron relations unless you want to study the <tt>nqmgr</tt> sources. In 1422 1.1 tron that case the text above might provide some helpful introduction 1423 1.1 tron to the problem domain. Otherwise I suggest you just forget about 1424 1.1 tron all this and stick with the user's point of view: the blocker jobs 1425 1.1 tron are simply ignored. 1426 1.1 tron 1427 1.1 tron </p> 1428 1.1 tron 1429 1.1 tron <p> 1430 1.1 tron 1431 1.1 tron [By now, you should have a feeling that there is more things going 1432 1.1 tron under the hood than you ever wanted to know. You decide that 1433 1.1 tron forgetting about this chapter is the best you can do for the sake 1434 1.1 tron of your mind's health and you basically stick with the idea how the 1435 1.1 tron scheduler works in ideal conditions, when there are no blockers, 1436 1.1 tron which is good enough.] 1437 1.1 tron 1438 1.1 tron </p> 1439 1.1 tron 1440 1.1 tron <h3> <a name="<tt>nqmgr</tt>_memory"> Dealing with memory resource 1441 1.1 tron limits </a> </h3> 1442 1.1 tron 1443 1.1 tron <p> 1444 1.1 tron 1445 1.1 tron When discussing the <tt>nqmgr</tt> scheduler, we have so far assumed 1446 1.1 tron that all recipients of all messages in the <a href="QSHAPE_README.html#active_queue">active queue</a> are completely 1447 1.1 tron read into the memory. This is simply not true. There is an upper 1448 1.1 tron bound on the amount of memory the <tt>nqmgr</tt> may use, and 1449 1.1 tron therefore it must impose some limits on the information it may store 1450 1.1 tron in the memory at any given time. 1451 1.1 tron 1452 1.1 tron </p> 1453 1.1 tron 1454 1.1 tron <p> 1455 1.1 tron 1456 1.1 tron First of all, not all messages may be read in-core at once. At any 1457 1.1 tron time, only <a href="postconf.5.html#qmgr_message_active_limit">qmgr_message_active_limit</a> messages may be read in-core 1458 1.1 tron at maximum. When read into memory, the messages are picked from the 1459 1.1 tron <a href="QSHAPE_README.html#incoming_queue">incoming</a> and deferred message queues and moved to the <a href="QSHAPE_README.html#active_queue">active queue</a> 1460 1.1 tron (incoming having priority), so if there is more than 1461 1.1 tron <a href="postconf.5.html#qmgr_message_active_limit">qmgr_message_active_limit</a> messages queued in the <a href="QSHAPE_README.html#active_queue">active queue</a>, the 1462 1.1 tron rest will have to wait until (some of) the messages in the active 1463 1.1 tron queue are completely delivered (or deferred). 1464 1.1 tron 1465 1.1 tron </p> 1466 1.1 tron 1467 1.1 tron <p> 1468 1.1 tron 1469 1.1 tron Even with the limited amount of in-core messages, there is another 1470 1.1 tron limit which must be imposed in order to avoid memory exhaustion. 1471 1.1 tron Each message may contain huge amount of recipients (tens or hundreds 1472 1.1 tron of thousands are not uncommon), so if <tt>nqmgr</tt> read all 1473 1.1 tron recipients of all messages in the <a href="QSHAPE_README.html#active_queue">active queue</a>, it may easily run 1474 1.1 tron out of memory. Therefore there must be some upper bound on the 1475 1.1 tron amount of message recipients which are read into the memory at the 1476 1.1 tron same time. 1477 1.1 tron 1478 1.1 tron </p> 1479 1.1 tron 1480 1.1 tron <p> 1481 1.1 tron 1482 1.1 tron Before discussing how exactly <tt>nqmgr</tt> implements the recipient 1483 1.1 tron limits, let's see how the sole existence of the limits themselves 1484 1.1 tron affects the <tt>nqmgr</tt> and its scheduler. 1485 1.1 tron 1486 1.1 tron </p> 1487 1.1 tron 1488 1.1 tron <p> 1489 1.1 tron 1490 1.1 tron The message limit is straightforward - it just limits the size of 1491 1.1 tron the 1492 1.1 tron lookahead the <tt>nqmgr</tt>'s scheduler has when choosing which 1493 1.1 tron message can preempt the current one. Messages not in the active 1494 1.1 tron queue simply are not considered at all. 1495 1.1 tron 1496 1.1 tron </p> 1497 1.1 tron 1498 1.1 tron <p> 1499 1.1 tron 1500 1.1 tron The recipient limit complicates more things. First of all, the 1501 1.1 tron message reading code must support reading the recipients in batches, 1502 1.1 tron which among other things means accessing the queue file several 1503 1.1 tron times and continuing where the last recipient batch ended. This is 1504 1.1 tron invoked by the scheduler whenever the current job has space for more 1505 1.1 tron recipients, subject to transport's refill_limit and refill_delay parameters. 1506 1.1 tron It is also done any time when all 1507 1.1 tron in-core recipients of the message are dealt with (which may also 1508 1.1 tron mean they were deferred) but there are still more in the queue file. 1509 1.1 tron 1510 1.1 tron </p> 1511 1.1 tron 1512 1.1 tron <p> 1513 1.1 tron 1514 1.1 tron The second complication is that with some recipients left unread 1515 1.1 tron in the queue file, the scheduler can't operate with exact counts 1516 1.1 tron of recipient entries. With unread recipients, it is not clear how 1517 1.1 tron many recipient entries there will be, as they are subject to 1518 1.1 tron per-destination grouping. It is not even clear to what transports 1519 1.1 tron (and thus jobs) the recipients will be assigned. And with messages 1520 1.1 tron coming from the <a href="QSHAPE_README.html#deferred_queue">deferred queue</a>, it is not even clear how many unread 1521 1.1 tron recipients are still to be delivered. This all means that the 1522 1.1 tron scheduler must use only estimates of how many recipients entries 1523 1.1 tron there will be. Fortunately, it is possible to estimate the minimum 1524 1.1 tron and maximum correctly, so the scheduler can always err on the safe 1525 1.1 tron side. Obviously, the better the estimates, the better results, so 1526 1.1 tron it is best when we are able to read all recipients in-core and turn 1527 1.1 tron the estimates into exact counts, or at least try to read as many 1528 1.1 tron as possible to make the estimates as accurate as possible. 1529 1.1 tron 1530 1.1 tron </p> 1531 1.1 tron 1532 1.1 tron <p> 1533 1.1 tron 1534 1.1 tron The third complication is that it is no longer true that the scheduler 1535 1.1 tron is done with a job once all of its in-core recipients are delivered. 1536 1.1 tron It is possible that the job will be revived later, when another 1537 1.1 tron batch of recipients is read in core. It is also possible that some 1538 1.1 tron jobs will be created for the first time long after the first batch 1539 1.1 tron of recipients was read in core. The <tt>nqmgr</tt> code must be 1540 1.1 tron ready to handle all such situations. 1541 1.1 tron 1542 1.1 tron </p> 1543 1.1 tron 1544 1.1 tron <p> 1545 1.1 tron 1546 1.1 tron And finally, the fourth complication is that the <tt>nqmgr</tt> 1547 1.1 tron code must somehow impose the recipient limit itself. Now how does 1548 1.1 tron it achieve it? 1549 1.1 tron 1550 1.1 tron </p> 1551 1.1 tron 1552 1.1 tron <p> 1553 1.1 tron 1554 1.1 tron Perhaps the easiest solution would be to say that each message may 1555 1.1 tron have at maximum X recipients stored in-core, but such solution would 1556 1.1 tron be poor for several reasons. With reasonable <a href="postconf.5.html#qmgr_message_active_limit">qmgr_message_active_limit</a> 1557 1.1 tron values, the X would have to be quite low to maintain reasonable 1558 1.1 tron memory footprint. And with low X lots of things would not work well. 1559 1.1 tron The <tt>nqmgr</tt> would have problems to use the 1560 1.1 tron <a href="postconf.5.html#transport_destination_recipient_limit"><i>transport</i>_destination_recipient_limit</a> efficiently. The 1561 1.1 tron scheduler's preemption would be suboptimal as the recipient count 1562 1.1 tron estimates would be inaccurate. The message queue file would have 1563 1.1 tron to be accessed many times to read in more recipients again and 1564 1.1 tron again. 1565 1.1 tron 1566 1.1 tron </p> 1567 1.1 tron 1568 1.1 tron <p> 1569 1.1 tron 1570 1.1 tron Therefore it seems reasonable to have a solution which does not use 1571 1.1 tron a limit imposed on per-message basis, but which maintains a pool 1572 1.1 tron of available recipient slots, which can be shared among all messages 1573 1.1 tron in the most efficient manner. And as we do not want separate 1574 1.1 tron transports to compete for resources whenever possible, it seems 1575 1.1 tron appropriate to maintain such recipient pool for each transport 1576 1.1 tron separately. This is the general idea, now how does it work in 1577 1.1 tron practice? 1578 1.1 tron 1579 1.1 tron </p> 1580 1.1 tron 1581 1.1 tron <p> 1582 1.1 tron 1583 1.1 tron First we have to solve little chicken-and-egg problem. If we want 1584 1.1 tron to use the per-transport recipient pools, we first need to know to 1585 1.1 tron what transport(s) is the message assigned. But we will find that 1586 1.1 tron out only after we read in the recipients first. So it is obvious 1587 1.1 tron that we first have to read in some recipients, use them to find out 1588 1.1 tron to what transports is the message to be assigned, and only after 1589 1.1 tron that we can use the per-transport recipient pools. 1590 1.1 tron 1591 1.1 tron </p> 1592 1.1 tron 1593 1.1 tron <p> 1594 1.1 tron 1595 1.1 tron Now how many recipients shall we read for the first time? This is 1596 1.1 tron what <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> and <a href="postconf.5.html#qmgr_message_recipient_limit">qmgr_message_recipient_limit</a> 1597 1.1 tron values control. The <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> value specifies 1598 1.1 tron how many recipients of each message we will read for the first time, 1599 1.1 tron no matter what. It is necessary to read at least one recipient 1600 1.1 tron before we can assign the message to a transport and create the first 1601 1.1 tron job. However, reading only <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> recipients 1602 1.1 tron even if there are only few messages with few recipients in-core would 1603 1.1 tron be wasteful. Therefore if there is less than <a href="postconf.5.html#qmgr_message_recipient_limit">qmgr_message_recipient_limit</a> 1604 1.1 tron recipients in-core so far, the first batch of recipients may be 1605 1.1 tron larger than <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> - as large as is required 1606 1.1 tron to reach the <a href="postconf.5.html#qmgr_message_recipient_limit">qmgr_message_recipient_limit</a> limit. 1607 1.1 tron 1608 1.1 tron </p> 1609 1.1 tron 1610 1.1 tron <p> 1611 1.1 tron 1612 1.1 tron Once the first batch of recipients was read in core and the message 1613 1.1 tron jobs were created, the size of the subsequent recipient batches (if 1614 1.1 tron any - of course it's best when all recipients are read in one batch) 1615 1.1 tron is based solely on the position of the message jobs on their 1616 1.1 tron corresponding transports' job lists. Each transport has a pool of 1617 1.1 tron <a href="postconf.5.html#transport_recipient_limit"><i>transport</i>_recipient_limit</a> recipient slots which it can 1618 1.1 tron distribute among its jobs (how this is done is described later). 1619 1.1 tron The subsequent recipient batch may be as large as the sum of all 1620 1.1 tron recipient slots of all jobs of the message permits (plus the 1621 1.1 tron <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> amount which always applies). 1622 1.1 tron 1623 1.1 tron </p> 1624 1.1 tron 1625 1.1 tron <p> 1626 1.1 tron 1627 1.1 tron For example, if a message has three jobs, first with 1 recipient 1628 1.1 tron still in-core and 4 recipient slots, second with 5 recipient in-core 1629 1.1 tron and 5 recipient slots, and third with 2 recipients in-core and 0 1630 1.1 tron recipient slots, it has 1+5+2=7 recipients in-core and 4+5+0=9 jobs' 1631 1.1 tron recipients slots in total. This means that we could immediately 1632 1.1 tron read 2+<a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> more recipients of that message 1633 1.1 tron in core. 1634 1.1 tron 1635 1.1 tron </p> 1636 1.1 tron 1637 1.1 tron <p> 1638 1.1 tron 1639 1.1 tron The above example illustrates several things which might be worth 1640 1.1 tron mentioning explicitly: first, note that although the per-transport 1641 1.1 tron slots are assigned to particular jobs, we can't guarantee that once 1642 1.1 tron the next batch of recipients is read in core, that the corresponding 1643 1.1 tron amounts of recipients will be assigned to those jobs. The jobs lend 1644 1.1 tron its slots to the message as a whole, so it is possible that some 1645 1.1 tron jobs end up sponsoring other jobs of their message. For example, 1646 1.1 tron if in the example above the 2 newly read recipients were assigned 1647 1.1 tron to the second job, the first job sponsored the second job with 2 1648 1.1 tron slots. The second notable thing is the third job, which has more 1649 1.1 tron recipients in-core than it has slots. Apart from sponsoring by other 1650 1.1 tron job we just saw it can be result of the first recipient batch, which 1651 1.1 tron is sponsored from global recipient pool of <a href="postconf.5.html#qmgr_message_recipient_limit">qmgr_message_recipient_limit</a> 1652 1.1 tron recipients. It can be also sponsored from the message recipient 1653 1.1 tron pool of <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> recipients. 1654 1.1 tron 1655 1.1 tron </p> 1656 1.1 tron 1657 1.1 tron <p> 1658 1.1 tron 1659 1.1 tron Now how does each transport distribute the recipient slots among 1660 1.1 tron its jobs? The strategy is quite simple. As most scheduler activity 1661 1.1 tron happens on the head of the job list, it is our intention to make 1662 1.1 tron sure that the scheduler has the best estimates of the recipient 1663 1.1 tron counts for those jobs. As we mentioned above, this means that we 1664 1.1 tron want to try to make sure that the messages of those jobs have all 1665 1.1 tron recipients read in-core. Therefore the transport distributes the 1666 1.1 tron slots "along" the job list from start to end. In this case the job 1667 1.1 tron list sorted by message enqueue time is used, because it doesn't 1668 1.1 tron change over time as the scheduler's job list does. 1669 1.1 tron 1670 1.1 tron </p> 1671 1.1 tron 1672 1.1 tron <p> 1673 1.1 tron 1674 1.1 tron More specifically, each time a job is created and appended to the 1675 1.1 tron job list, it gets all unused recipient slots from its transport's 1676 1.1 tron pool. It keeps them until all recipients of its message are read. 1677 1.1 tron When this happens, all unused recipient slots are transferred to 1678 1.1 tron the next job (which is now in fact now first such job) on the job 1679 1.1 tron list which still has some recipients unread, or eventually back to 1680 1.1 tron the transport pool if there is no such job. Such transfer then also 1681 1.1 tron happens whenever a recipient entry of that job is delivered. 1682 1.1 tron 1683 1.1 tron </p> 1684 1.1 tron 1685 1.1 tron <p> 1686 1.1 tron 1687 1.1 tron There is also a scenario when a job is not appended to the end of 1688 1.1 tron the job list (for example it was created as a result of second or 1689 1.1 tron later recipient batch). Then it works exactly as above, except that 1690 1.1 tron if it was put in front of the first unread job (that is, the job 1691 1.1 tron of a message which still has some unread recipients in queue file), 1692 1.1 tron that job is first forced to return all of its unused recipient slots 1693 1.1 tron to the transport pool. 1694 1.1 tron 1695 1.1 tron </p> 1696 1.1 tron 1697 1.1 tron <p> 1698 1.1 tron 1699 1.1 tron The algorithm just described leads to the following state: The first 1700 1.1 tron unread job on the job list always gets all the remaining recipient 1701 1.1 tron slots of that transport (if there are any). The jobs queued before 1702 1.1 tron this job are completely read (that is, all recipients of their 1703 1.1 tron message were already read in core) and have at maximum as many slots 1704 1.1 tron as they still have recipients in-core (the maximum is there because 1705 1.1 tron of the sponsoring mentioned before) and the jobs after this job get 1706 1.1 tron nothing from the transport recipient pool (unless they got something 1707 1.1 tron before and then the first unread job was created and enqueued in 1708 1.1 tron front of them later - in such case the also get at maximum as many 1709 1.1 tron slots as they have recipients in-core). 1710 1.1 tron 1711 1.1 tron </p> 1712 1.1 tron 1713 1.1 tron <p> 1714 1.1 tron 1715 1.1 tron Things work fine in such state for most of the time, because the 1716 1.1 tron current job is either completely read in-core or has as much recipient 1717 1.1 tron slots as there are, but there is one situation which we still have 1718 1.1 tron to take care of specially. Imagine if the current job is preempted 1719 1.1 tron by some unread job from the job list and there are no more recipient 1720 1.1 tron slots available, so this new current job could read only batches 1721 1.1 tron of <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> recipients at a time. This would 1722 1.1 tron really degrade performance. For this reason, each transport has 1723 1.1 tron extra pool of <a href="postconf.5.html#transport_extra_recipient_limit"><i>transport</i>_extra_recipient_limit</a> recipient 1724 1.1 tron slots, dedicated exactly for this situation. Each time an unread 1725 1.1 tron job preempts the current job, it gets half of the remaining recipient 1726 1.1 tron slots from the normal pool and this extra pool. 1727 1.1 tron 1728 1.1 tron </p> 1729 1.1 tron 1730 1.1 tron <p> 1731 1.1 tron 1732 1.1 tron And that's it. It sure does sound pretty complicated, but fortunately 1733 1.1 tron most people don't really have to care how exactly it works as long 1734 1.1 tron as it works. Perhaps the only important things to know for most 1735 1.1 tron people are the following upper bound formulas: 1736 1.1 tron 1737 1.1 tron </p> 1738 1.1 tron 1739 1.1 tron <p> 1740 1.1 tron 1741 1.1 tron Each transport has at maximum 1742 1.1 tron 1743 1.1 tron </p> 1744 1.1 tron 1745 1.1 tron <blockquote> 1746 1.1 tron <pre> 1747 1.1 tron max( 1748 1.1 tron <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> * <a href="postconf.5.html#qmgr_message_active_limit">qmgr_message_active_limit</a> 1749 1.1 tron + *_recipient_limit + *_extra_recipient_limit, 1750 1.1 tron <a href="postconf.5.html#qmgr_message_recipient_limit">qmgr_message_recipient_limit</a> 1751 1.1 tron ) 1752 1.1 tron </pre> 1753 1.1 tron </blockquote> 1754 1.1 tron 1755 1.1 tron <p> 1756 1.1 tron 1757 1.1 tron recipients in core. 1758 1.1 tron 1759 1.1 tron </p> 1760 1.1 tron 1761 1.1 tron <p> 1762 1.1 tron 1763 1.1 tron The total amount of recipients in core is 1764 1.1 tron 1765 1.1 tron </p> 1766 1.1 tron 1767 1.1 tron <blockquote> 1768 1.1 tron <pre> 1769 1.1 tron max( 1770 1.1 tron <a href="postconf.5.html#qmgr_message_recipient_minimum">qmgr_message_recipient_minimum</a> * <a href="postconf.5.html#qmgr_message_active_limit">qmgr_message_active_limit</a> 1771 1.1 tron + sum( *_recipient_limit + *_extra_recipient_limit ), 1772 1.1 tron <a href="postconf.5.html#qmgr_message_recipient_limit">qmgr_message_recipient_limit</a> 1773 1.1 tron ) 1774 1.1 tron </pre> 1775 1.1 tron </blockquote> 1776 1.1 tron 1777 1.1 tron <p> 1778 1.1 tron 1779 1.1 tron where the sum is over all used transports. 1780 1.1 tron 1781 1.1 tron </p> 1782 1.1 tron 1783 1.1 tron <p> 1784 1.1 tron 1785 1.1 tron And this terribly complicated chapter concludes the documentation 1786 1.1 tron of <tt>nqmgr</tt> scheduler. 1787 1.1 tron 1788 1.1 tron </p> 1789 1.1 tron 1790 1.1 tron <p> 1791 1.1 tron 1792 1.1 tron [By now you should theoretically know the <tt>nqmgr</tt> scheduler 1793 1.1 tron inside out. In practice, you still hope that you will never have 1794 1.1 tron to really understand the last or last two chapters completely, and 1795 1.1 tron fortunately most people really won't. Understanding how the scheduler 1796 1.1 tron works in ideal conditions is more than good enough for vast majority 1797 1.1 tron of users.] 1798 1.1 tron 1799 1.1 tron </p> 1800 1.1 tron 1801 1.1 tron <h2> <a name="credits"> Credits </a> </h2> 1802 1.1 tron 1803 1.1 tron <ul> 1804 1.1 tron 1805 1.1 tron <li> Wietse Venema designed and implemented the initial queue manager 1806 1.1 tron with per-domain FIFO scheduling, and per-delivery +/-1 concurrency 1807 1.1 tron feedback. 1808 1.1 tron 1809 1.1 tron <li> Patrik Rak designed and implemented preemption where mail with 1810 1.1 tron fewer recipients can slip past mail with more recipients in a 1811 1.1 tron controlled manner, and wrote up its documentation. 1812 1.1 tron 1813 1.1 tron <li> Wietse Venema initiated a discussion with Patrik Rak and Victor 1814 1.1 tron Duchovni on alternatives for the +/-1 feedback scheduler's aggressive 1815 1.1 tron behavior. This is when K/N feedback was reviewed (N = concurrency). 1816 1.1 tron The discussion ended without a good solution for both negative 1817 1.1 tron feedback and dead site detection. 1818 1.1 tron 1819 1.1 tron <li> Victor Duchovni resumed work on concurrency feedback in the 1820 1.1 tron context of concurrency-limited servers. 1821 1.1 tron 1822 1.1 tron <li> Wietse Venema then re-designed the concurrency scheduler in 1823 1.1 tron terms of the simplest possible concepts: less-than-1 concurrency 1824 1.1 tron feedback per delivery, forward and reverse concurrency feedback 1825 1.1 tron hysteresis, and pseudo-cohort failure. At this same time, concurrency 1826 1.1 tron feedback was separated from dead site detection. 1827 1.1 tron 1828 1.1 tron <li> These simplifications, and their modular implementation, helped 1829 1.1 tron to develop further insights into the different roles that positive 1830 1.1 tron and negative concurrency feedback play, and helped to identify some 1831 1.1 tron worst-case scenarios. 1832 1.1 tron 1833 1.1 tron </ul> 1834 1.1 tron 1835 1.1 tron </body> 1836 1.1 tron 1837 1.1 tron </html> 1838
Indexes created Mon Sep 28 00:25:45 UTC 2026