Debian Codegraph @

doc/core/combiner-explainer.md

raw
1 # Combiner Explanation
2 ## Talk by ctiller, notes by vjpai
3
4 Typical way of doing critical section
5
6 ```
7 mu.lock()
8 do_stuff()
9 mu.unlock()
10 ```
11
12 An alternative way of doing it is
13
14 ```
15 class combiner {
16 run(f) {
17 mu.lock()
18 f()
19 mu.unlock()
20 }
21 mutex mu;
22 }
23
24 combiner.run(do_stuff)
25 ```
26
27 If you have two threads calling combiner, there will be some kind of
28 queuing in place. It's called `combiner` because you can pass in more
29 than one do_stuff at once and they will run under a common `mu`.
30
31 The implementation described above has the issue that you're blocking a thread
32 for a period of time, and this is considered harmful because it's an application thread that you're blocking.
33
34 Instead, get a new property:
35 * Keep things running in serial execution
36 * Don't ever sleep the thread
37 * But maybe allow things to end up running on a different thread from where they were started
38 * This means that `do_stuff` doesn't necessarily run to completion when `combiner.run` is invoked
39
40 ```
41 class combiner {
42 mpscq q; // multi-producer single-consumer queue can be made non-blocking
43 state s; // is it empty or executing
44
45 run(f) {
46 if (q.push(f)) {
47 // q.push returns true if it's the first thing
48 while (q.pop(&f)) { // modulo some extra work to avoid races
49 f();
50 }
51 }
52 }
53 }
54 ```
55
56 The basic idea is that the first one to push onto the combiner
57 executes the work and then keeps executing functions from the queue
58 until the combiner is drained.
59
60 Our combiner does some additional work, with the motivation of write-batching.
61
62 We have a second tier of `run` called `run_finally`. Anything queued
63 onto `run_finally` runs after we have drained the queue. That means
64 that there is essentially a finally-queue. This is not guaranteed to
65 be final, but it's best-effort. In the process of running the finally
66 item, we might put something onto the main combiner queue and so we'll
67 need to re-enter.
68
69 `chttp2` runs all ops in the run state except if it sees a write it puts that into a finally. That way anything else that gets put into the combiner can add to that write.
70
71 ```
72 class combiner {
73 mpscq q; // multi-producer single-consumer queue can be made non-blocking
74 state s; // is it empty or executing
75 queue finally; // you can only do run_finally when you are already running something from the combiner
76
77 run(f) {
78 if (q.push(f)) {
79 // q.push returns true if it's the first thing
80 loop:
81 while (q.pop(&f)) { // modulo some extra work to avoid races
82 f();
83 }
84 while (finally.pop(&f)) {
85 f();
86 }
87 goto loop;
88 }
89 }
90 }
91 ```
92
93 So that explains how combiners work in general. In gRPC, there is
94 `start_batch(..., tag)` and then work only gets activated by somebody
95 calling `cq::next` which returns a tag. This gives an API-level
96 guarantee that there will be a thread doing polling to actually make
97 work happen. However, some operations are not covered by a poller
98 thread, such as cancellation that doesn't have a completion. Other
99 callbacks that don't have a completion are the internal work that gets
100 done before the batch gets completed. We need a condition called
101 `covered_by_poller` that means that the item will definitely need some
102 thread at some point to call `cq::next` . This includes those
103 callbacks that directly cause a completion but also those that are
104 indirectly required before getting a completion. If we can't tell for
105 sure for a specific path, we have to assumed it is not covered by
106 poller.
107
108 The above combiner has the problem that it keeps draining for a
109 potentially infinite amount of time and that can lead to a huge tail
110 latency for some operations. So we can tweak it by returning to the application
111 if we know that it is valid to do so:
112
113 ```
114 while (q.pop(&f)) {
115 f();
116 if (control_can_be_returned && some_still_queued_thing_is_covered_by_poller) {
117 offload_combiner_work_to_some_other_thread();
118 }
119 }
120 ```
121
122 `offload` is more than `break`; it does `break` but also causes some
123 other thread that is currently waiting on a poll to break out of its
124 poll. This is done by setting up a per-polling-island work-queue
125 (distributor) wakeup FD. The work-queue is the converse of the combiner; it
126 tries to spray events onto as many threads as possible to get as much concurrency as possible.
127
128 So `offload` really does:
129
130 ```
131 workqueue.run(continue_from_while_loop);
132 break;
133 ```
134
135 This needs us to add another class variable for a `workqueue`
136 (which is really conceptually a distributor).
137
138 ```
139 workqueue::run(f) {
140 q.push(f)
141 eventfd.wakeup()
142 }
143
144 workqueue::readable() {
145 eventfd.consume();
146 q.pop(&f);
147 f();
148 if (!q.empty()) {
149 eventfd.wakeup(); // spray across as many threads as are waiting on this workqueue
150 }
151 }
152 ```
153
154 In principle, `run_finally` could get starved, but this hasn't
155 happened in practice. If we were concerned about this, we could put a
156 limit on how many things come off the regular `q` before the `finally`
157 queue gets processed.
158