Debian Codegraph @

doc/source/modules/dagpool.rst

raw
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: