| 1 |
:mod:`dagpool` -- Dependency-Driven Greenthreads |
| 2 |
================================================ |
| 3 |
|
| 4 |
Rationale |
| 5 |
********* |
| 6 |
|
| 7 |
The dagpool module provides the :class:`DAGPool <eventlet.dagpool.DAGPool>` |
| 8 |
class, which addresses situations in which the value produced by one |
| 9 |
greenthread might be consumed by several others -- while at the same time a |
| 10 |
consuming greenthread might depend on the output from several different |
| 11 |
greenthreads. |
| 12 |
|
| 13 |
If you have a tree with strict many-to-one dependencies -- each producer |
| 14 |
greenthread provides results to exactly one consumer, though a given consumer |
| 15 |
may depend on multiple producers -- that could be addressed by recursively |
| 16 |
constructing a :class:`GreenPool <eventlet.greenpool.GreenPool>` of producers |
| 17 |
for each consumer, then :meth:`waiting <eventlet.greenpool.GreenPool.waitall>` |
| 18 |
for all producers. |
| 19 |
|
| 20 |
If you have a tree with strict one-to-many dependencies -- each consumer |
| 21 |
greenthread depends on exactly one producer, though a given producer may |
| 22 |
provide results to multiple consumers -- that could be addressed by causing |
| 23 |
each producer to finish by launching a :class:`GreenPool |
| 24 |
<eventlet.greenpool.GreenPool>` of consumers. |
| 25 |
|
| 26 |
But when you have many-to-many dependencies, a tree doesn't suffice. This is |
| 27 |
known as a |
| 28 |
`Directed Acyclic Graph <https://en.wikipedia.org/wiki/Directed_acyclic_graph>`_, |
| 29 |
or DAG. |
| 30 |
|
| 31 |
You might consider sorting the greenthreads into dependency order |
| 32 |
(`topological sort <https://en.wikipedia.org/wiki/Topological_sorting>`_) and |
| 33 |
launching them in a GreenPool. But the concurrency of the GreenPool must be |
| 34 |
strictly constrained to ensure that no greenthread is launched before all its |
| 35 |
upstream producers have completed -- and the appropriate pool size is |
| 36 |
data-dependent. Only a pool of size 1 (serializing all the greenthreads) |
| 37 |
guarantees that a topological sort will produce correct results. |
| 38 |
|
| 39 |
Even if you do serialize all the greenthreads, how do you pass results from |
| 40 |
each producer to all its consumers, which might start at very different points |
| 41 |
in time? |
| 42 |
|
| 43 |
One answer is to associate each greenthread with a distinct key, and store its |
| 44 |
result in a common dict. Then each consumer greenthread can identify its |
| 45 |
direct upstream producers by their keys, and find their results in that dict. |
| 46 |
|
| 47 |
This is the essence of DAGPool. |
| 48 |
|
| 49 |
A DAGPool instance owns a dict, and stores greenthread results in that dict. |
| 50 |
You :meth:`spawn <eventlet.dagpool.DAGPool.spawn>` *all* greenthreads in the |
| 51 |
DAG, specifying for each its own key -- the key with which its result will be |
| 52 |
stored on completion -- plus the keys of the upstream producer greenthreads on |
| 53 |
whose results it directly depends. |
| 54 |
|
| 55 |
Keys need only be unique within the DAGPool instance; they need not be UUIDs. |
| 56 |
A key can be any type that can be used as a dict key. String keys make it |
| 57 |
easier to reason about a DAGPool's behavior, but are by no means required. |
| 58 |
|
| 59 |
The DAGPool passes to each greenthread an iterable of (key, value) pairs. |
| 60 |
The key in each pair is the key of one of the greenthread's specified upstream |
| 61 |
producers; the value is the value returned by that producer greenthread. Pairs |
| 62 |
are delivered in the order results become available; the consuming greenthread |
| 63 |
blocks until the next result can be delivered. |
| 64 |
|
| 65 |
Tutorial |
| 66 |
******** |
| 67 |
|
| 68 |
Example |
| 69 |
------- |
| 70 |
|
| 71 |
Consider a couple of programs in some compiled language that depend on a set |
| 72 |
of precompiled libraries. Suppose every such build requires as input the |
| 73 |
specific set of library builds on which it directly depends. |
| 74 |
|
| 75 |
:: |
| 76 |
|
| 77 |
a zlib |
| 78 |
| / | |
| 79 |
|/ | |
| 80 |
b c |
| 81 |
| /| |
| 82 |
| / | |
| 83 |
| / | |
| 84 |
|/ | |
| 85 |
d e |
| 86 |
|
| 87 |
We can't run the build for program d until we have the build results for both |
| 88 |
b and c. We can't run the build for library b until we have build results for |
| 89 |
a and zlib. We can, however, immediately run the builds for a and zlib. |
| 90 |
|
| 91 |
So we can use a DAGPool instance to spawn greenthreads running a function such |
| 92 |
as this: |
| 93 |
|
| 94 |
:: |
| 95 |
|
| 96 |
def builder(key, upstream): |
| 97 |
for libname, product in upstream: |
| 98 |
# ... configure build for 'key' to use 'product' for 'libname' |
| 99 |
# all upstream builds have completed |
| 100 |
# ... run build for 'key' |
| 101 |
return build_product_for_key |
| 102 |
|
| 103 |
:meth:`spawn <eventlet.dagpool.DAGPool.spawn>` all these greenthreads: |
| 104 |
|
| 105 |
:: |
| 106 |
|
| 107 |
pool = DAGPool() |
| 108 |
# the upstream producer keys passed to spawn() can be from any iterable, |
| 109 |
# including a generator |
| 110 |
pool.spawn("d", ("b", "c"), builder) |
| 111 |
pool.spawn("e", ["c"], builder) |
| 112 |
pool.spawn("b", ("a", "zlib"), builder) |
| 113 |
pool.spawn("c", ["zlib"], builder) |
| 114 |
pool.spawn("a", (), builder) |
| 115 |
|
| 116 |
As with :func:`eventlet.spawn() <eventlet.spawn>`, if you need to pass special |
| 117 |
build flags to some set of builds, these can be passed as either positional or |
| 118 |
keyword arguments: |
| 119 |
|
| 120 |
:: |
| 121 |
|
| 122 |
def builder(key, upstream, cflags="", linkflags=""): |
| 123 |
... |
| 124 |
|
| 125 |
pool.spawn("d", ("b", "c"), builder, "-o2") |
| 126 |
pool.spawn("e", ["c"], builder, linkflags="-pie") |
| 127 |
|
| 128 |
However, if the arguments to each builder() call are uniform (as in the |
| 129 |
original example), you could alternatively build a dict of the dependencies |
| 130 |
and call :meth:`spawn_many() <eventlet.dagpool.DAGPool.spawn_many>`: |
| 131 |
|
| 132 |
:: |
| 133 |
|
| 134 |
deps = dict(d=("b", "c"), |
| 135 |
e=["c"], |
| 136 |
b=("a", "zlib"), |
| 137 |
c=["zlib"], |
| 138 |
a=()) |
| 139 |
pool.spawn_many(deps, builder) |
| 140 |
|
| 141 |
From outside the DAGPool, you can obtain the results for d and e (or in fact |
| 142 |
for any of the build greenthreads) in any of several ways. |
| 143 |
|
| 144 |
:meth:`pool.waitall() <eventlet.dagpool.DAGPool.waitall>` waits until the last of the spawned |
| 145 |
greenthreads has completed, and returns a dict containing results for *all* of |
| 146 |
them: |
| 147 |
|
| 148 |
:: |
| 149 |
|
| 150 |
final = pool.waitall() |
| 151 |
print("for d: {0}".format(final["d"])) |
| 152 |
print("for e: {0}".format(final["e"])) |
| 153 |
|
| 154 |
waitall() is an alias for :meth:`wait() <eventlet.dagpool.DAGPool.wait>` with no arguments: |
| 155 |
|
| 156 |
:: |
| 157 |
|
| 158 |
final = pool.wait() |
| 159 |
print("for d: {0}".format(final["d"])) |
| 160 |
print("for e: {0}".format(final["e"])) |
| 161 |
|
| 162 |
Or you can specifically wait for only the final programs: |
| 163 |
|
| 164 |
:: |
| 165 |
|
| 166 |
final = pool.wait(["d", "e"]) |
| 167 |
|
| 168 |
The returned dict will contain only the specified keys. The keys may be passed |
| 169 |
into wait() from any iterable, including a generator. |
| 170 |
|
| 171 |
You can wait for any specified set of greenthreads; they need not be |
| 172 |
topologically last: |
| 173 |
|
| 174 |
:: |
| 175 |
|
| 176 |
# returns as soon as both a and zlib have returned results, regardless of |
| 177 |
# what else is still running |
| 178 |
leaves = pool.wait(["a", "zlib"]) |
| 179 |
|
| 180 |
Suppose you want to wait specifically for just *one* of the final programs: |
| 181 |
|
| 182 |
:: |
| 183 |
|
| 184 |
final = pool.wait(["d"]) |
| 185 |
dprog = final["d"] |
| 186 |
|
| 187 |
The above wait() call will return as soon as greenthread d returns a result -- |
| 188 |
regardless of whether greenthread e has finished. |
| 189 |
|
| 190 |
:meth:`__getitem()__ <eventlet.dagpool.DAGPool.__getitem__>` is shorthand for |
| 191 |
obtaining a single result: |
| 192 |
|
| 193 |
:: |
| 194 |
|
| 195 |
# waits until greenthread d returns its result |
| 196 |
dprog = pool["d"] |
| 197 |
|
| 198 |
In contrast, :meth:`get() <eventlet.dagpool.DAGPool.get>` returns immediately, |
| 199 |
whether or not a result is ready: |
| 200 |
|
| 201 |
:: |
| 202 |
|
| 203 |
# returns immediately |
| 204 |
if pool.get("d") is None: |
| 205 |
... |
| 206 |
|
| 207 |
Of course, your greenthread might not include an explicit return statement and |
| 208 |
hence might implicitly return None. You might have to test some other value. |
| 209 |
|
| 210 |
:: |
| 211 |
|
| 212 |
# returns immediately |
| 213 |
if pool.get("d", "notdone") == "notdone": |
| 214 |
... |
| 215 |
|
| 216 |
Suppose you want to process each of the final programs in some way (upload |
| 217 |
it?), but you don't want to have to wait until they've both finished. You |
| 218 |
don't have to poll get() calls -- use :meth:`wait_each() |
| 219 |
<eventlet.dagpool.DAGPool.wait_each>`: |
| 220 |
|
| 221 |
:: |
| 222 |
|
| 223 |
for key, result in pool.wait_each(["d", "e"]): |
| 224 |
# key will be d or e, in completion order |
| 225 |
# process result... |
| 226 |
|
| 227 |
As with :meth:`wait() <eventlet.dagpool.DAGPool.wait>`, if you omit the |
| 228 |
argument to wait_each(), it delivers results for all the greenthreads of which |
| 229 |
it's aware: |
| 230 |
|
| 231 |
:: |
| 232 |
|
| 233 |
for key, result in pool.wait_each(): |
| 234 |
# key will be a, zlib, b, c, d, e, in whatever order each completes |
| 235 |
# process its result... |
| 236 |
|
| 237 |
Introspection |
| 238 |
------------- |
| 239 |
|
| 240 |
Let's say you have set up a :class:`DAGPool <eventlet.dagpool.DAGPool>` with |
| 241 |
the dependencies shown above. To your consternation, your :meth:`waitall() |
| 242 |
<eventlet.dagpool.DAGPool.waitall>` call does not return! The DAGPool instance |
| 243 |
is stuck! |
| 244 |
|
| 245 |
You could change waitall() to :meth:`wait_each() |
| 246 |
<eventlet.dagpool.DAGPool.wait_each>`, and print each key as it becomes |
| 247 |
available: |
| 248 |
|
| 249 |
:: |
| 250 |
|
| 251 |
for key, result in pool.wait_each(): |
| 252 |
print("got result for {0}".format(key)) |
| 253 |
# ... process ... |
| 254 |
|
| 255 |
Once the build for a has completed, this produces: |
| 256 |
|
| 257 |
:: |
| 258 |
|
| 259 |
got result for a |
| 260 |
|
| 261 |
and then stops. Hmm! |
| 262 |
|
| 263 |
You can check the number of :meth:`running <eventlet.dagpool.DAGPool.running>` |
| 264 |
greenthreads: |
| 265 |
|
| 266 |
:: |
| 267 |
|
| 268 |
>>> print(pool.running()) |
| 269 |
4 |
| 270 |
|
| 271 |
and the number of :meth:`waiting <eventlet.dagpool.DAGPool.waiting>` |
| 272 |
greenthreads: |
| 273 |
|
| 274 |
:: |
| 275 |
|
| 276 |
>>> print(pool.waiting()) |
| 277 |
4 |
| 278 |
|
| 279 |
It's often more informative to ask *which* greenthreads are :meth:`still |
| 280 |
running <eventlet.dagpool.DAGPool.running_keys>`: |
| 281 |
|
| 282 |
:: |
| 283 |
|
| 284 |
>>> print(pool.running_keys()) |
| 285 |
('c', 'b', 'e', 'd') |
| 286 |
|
| 287 |
but in this case, we already know a has completed. |
| 288 |
|
| 289 |
We can ask for all available results: |
| 290 |
|
| 291 |
:: |
| 292 |
|
| 293 |
>>> print(pool.keys()) |
| 294 |
('a',) |
| 295 |
>>> print(pool.items()) |
| 296 |
(('a', result_from_a),) |
| 297 |
|
| 298 |
The :meth:`keys() <eventlet.dagpool.DAGPool.keys>` and :meth:`items() |
| 299 |
<eventlet.dagpool.DAGPool.items>` methods only return keys and items for |
| 300 |
which results are actually available, reflecting the underlying dict. |
| 301 |
|
| 302 |
But what's blocking the works? What are we :meth:`waiting for |
| 303 |
<eventlet.dagpool.DAGPool.waiting_for>`? |
| 304 |
|
| 305 |
:: |
| 306 |
|
| 307 |
>>> print(pool.waiting_for("d")) |
| 308 |
set(['c', 'b']) |
| 309 |
|
| 310 |
(waiting_for()'s optional argument is a *single* key.) |
| 311 |
|
| 312 |
That doesn't help much yet... |
| 313 |
|
| 314 |
:: |
| 315 |
|
| 316 |
>>> print(pool.waiting_for("b")) |
| 317 |
set(['zlib']) |
| 318 |
>>> print(pool.waiting_for("zlib")) |
| 319 |
KeyError: 'zlib' |
| 320 |
|
| 321 |
Aha! We forgot to even include the zlib build when we were originally |
| 322 |
configuring this DAGPool! |
| 323 |
|
| 324 |
(For non-interactive use, it would be more informative to omit waiting_for()'s |
| 325 |
argument. This usage returns a dict indicating, for each greenthread key, |
| 326 |
which other keys it's waiting for.) |
| 327 |
|
| 328 |
:: |
| 329 |
|
| 330 |
from pprint import pprint |
| 331 |
pprint(pool.waiting_for()) |
| 332 |
|
| 333 |
{'b': set(['zlib']), 'c': set(['zlib']), 'd': set(['b', 'c']), 'e': set(['c'])} |
| 334 |
|
| 335 |
In this case, a reasonable fix would be to spawn the zlib greenthread: |
| 336 |
|
| 337 |
:: |
| 338 |
|
| 339 |
pool.spawn("zlib", (), builder) |
| 340 |
|
| 341 |
Even if this is the last method call on this DAGPool instance, it should |
| 342 |
unblock all the rest of the DAGPool greenthreads. |
| 343 |
|
| 344 |
Posting |
| 345 |
------- |
| 346 |
|
| 347 |
If we happen to have zlib build results in hand already, though, we could |
| 348 |
instead :meth:`post() <eventlet.dagpool.DAGPool.post>` that result instead of |
| 349 |
rebuilding the library: |
| 350 |
|
| 351 |
:: |
| 352 |
|
| 353 |
pool.post("zlib", result_from_zlib) |
| 354 |
|
| 355 |
This, too, should unblock the rest of the DAGPool greenthreads. |
| 356 |
|
| 357 |
Preloading |
| 358 |
---------- |
| 359 |
|
| 360 |
If rebuilding takes nontrivial realtime, it might be useful to record partial |
| 361 |
results, so that in case of interruption you can restart from where you left |
| 362 |
off rather than having to rebuild everything prior to that point. |
| 363 |
|
| 364 |
You could iteratively :meth:`post() <eventlet.dagpool.DAGPool.post>` those |
| 365 |
prior results into a new DAGPool instance; alternatively you can |
| 366 |
:meth:`preload <eventlet.dagpool.DAGPool.__init__>` the :class:`DAGPool |
| 367 |
<eventlet.dagpool.DAGPool>` from an existing dict: |
| 368 |
|
| 369 |
:: |
| 370 |
|
| 371 |
pool = DAGPool(dict(a=result_from_a, zlib=result_from_zlib)) |
| 372 |
|
| 373 |
Any DAGPool greenthreads that depend on either a or zlib can immediately |
| 374 |
consume those results. |
| 375 |
|
| 376 |
It also works to construct DAGPool with an iterable of (key, result) pairs. |
| 377 |
|
| 378 |
Exception Propagation |
| 379 |
--------------------- |
| 380 |
|
| 381 |
But what if we spawn a zlib build that fails? Suppose the zlib greenthread |
| 382 |
terminates with an exception? In that case none of b, c, d or e can proceed! |
| 383 |
Nor do we want to wait forever for them. |
| 384 |
|
| 385 |
:: |
| 386 |
|
| 387 |
dprog = pool["d"] |
| 388 |
eventlet.dagpool.PropagateError: PropagateError(d): PropagateError: PropagateError(c): PropagateError: PropagateError(zlib): OriginalError |
| 389 |
|
| 390 |
DAGPool provides a :class:`PropagateError <eventlet.dagpool.PropagateError>` |
| 391 |
exception specifically to wrap such failures. If a DAGPool greenthread |
| 392 |
terminates with an Exception subclass, the DAGPool wraps that exception in a |
| 393 |
PropagateError instance whose *key* attribute is the key of the failing |
| 394 |
greenthread and whose *exc* attribute is the exception that terminated it. |
| 395 |
This PropagateError is stored as the result from that greenthread. |
| 396 |
|
| 397 |
Attempting to consume the result from a greenthread for which a PropagateError |
| 398 |
was stored raises that PropagateError. |
| 399 |
|
| 400 |
:: |
| 401 |
|
| 402 |
pool["zlib"] |
| 403 |
eventlet.dagpool.PropagateError: PropagateError(zlib): OriginalError |
| 404 |
|
| 405 |
Thus, when greenthread c attempts to consume the result from zlib, the |
| 406 |
PropagateError for zlib is raised. Unless the builder function for greenthread |
| 407 |
c handles that PropagateError exception, that greenthread will itself |
| 408 |
terminate. That PropagateError will be wrapped in another PropagateError whose |
| 409 |
*key* attribute is c and whose *exc* attribute is the PropagateError for zlib. |
| 410 |
|
| 411 |
Similarly, when greenthread d attempts to consume the result from c, the |
| 412 |
PropagateError for c is raised. This in turn is wrapped in a PropagateError |
| 413 |
whose *key* is d and whose *exc* is the PropagateError for c. |
| 414 |
|
| 415 |
When someone attempts to consume the result from d, as shown above, the |
| 416 |
PropagateError for d is raised. |
| 417 |
|
| 418 |
You can programmatically chase the failure path to determine the original |
| 419 |
failure if desired: |
| 420 |
|
| 421 |
:: |
| 422 |
|
| 423 |
orig_err = err |
| 424 |
key = "unknown" |
| 425 |
while isinstance(orig_err, PropagateError): |
| 426 |
key = orig_err.key |
| 427 |
orig_err = orig_err.exc |
| 428 |
|
| 429 |
Scanning for Success / Exceptions |
| 430 |
--------------------------------- |
| 431 |
|
| 432 |
Exception propagation means that we neither perform useless builds nor wait for |
| 433 |
results that will never arrive. |
| 434 |
|
| 435 |
However, it does make it difficult to obtain *partial* results for builds that |
| 436 |
*did* succeed. |
| 437 |
|
| 438 |
For that you can call :meth:`wait_each_success() |
| 439 |
<eventlet.dagpool.DAGPool.wait_each_success>`: |
| 440 |
|
| 441 |
:: |
| 442 |
|
| 443 |
for key, result in pool.wait_each_success(): |
| 444 |
print("{0} succeeded".format(key)) |
| 445 |
# ... process result ... |
| 446 |
|
| 447 |
a succeeded |
| 448 |
|
| 449 |
Another problem is that although five different greenthreads failed in the |
| 450 |
example, we only see one chain of failures. You can enumerate the bad news |
| 451 |
with :meth:`wait_each_exception() <eventlet.dagpool.DAGPool.wait_each_exception>`: |
| 452 |
|
| 453 |
:: |
| 454 |
|
| 455 |
for key, err in pool.wait_each_exception(): |
| 456 |
print("{0} failed with {1}".format(key, err.exc.__class__.__name__)) |
| 457 |
|
| 458 |
c failed with PropagateError |
| 459 |
b failed with PropagateError |
| 460 |
e failed with PropagateError |
| 461 |
d failed with PropagateError |
| 462 |
zlib failed with OriginalError |
| 463 |
|
| 464 |
wait_each_exception() yields each PropagateError wrapper as if it were the |
| 465 |
result, rather than raising it as an exception. |
| 466 |
|
| 467 |
Notice that we print :code:`err.exc.__class__.__name__` because |
| 468 |
:code:`err.__class__.__name__` is always PropagateError. |
| 469 |
|
| 470 |
Both wait_each_success() and wait_each_exception() can accept an iterable of |
| 471 |
keys to report: |
| 472 |
|
| 473 |
:: |
| 474 |
|
| 475 |
for key, result in pool.wait_each_success(["d", "e"]): |
| 476 |
print("{0} succeeded".format(key)) |
| 477 |
|
| 478 |
(no output) |
| 479 |
|
| 480 |
for key, err in pool.wait_each_exception(["d", "e"]): |
| 481 |
print("{0} failed with {1}".format(key, err.exc.__class__.__name__)) |
| 482 |
|
| 483 |
e failed with PropagateError |
| 484 |
d failed with PropagateError |
| 485 |
|
| 486 |
Both wait_each_success() and wait_each_exception() must wait until the |
| 487 |
greenthreads for all specified keys (or all keys) have terminated, one way or |
| 488 |
the other, because of course we can't know until then how to categorize each. |
| 489 |
|
| 490 |
Module Contents |
| 491 |
=============== |
| 492 |
|
| 493 |
.. automodule:: eventlet.dagpool |
| 494 |
:members: |