carto
/
grpc


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
							<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.17"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>GRPC Core: Combiner Explanation</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">GRPC Core
   &#160;<span id="projectnumber">15.0.0</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.17 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search');
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
/* @license-end */</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

</div><!-- top -->
<div class="PageDoc"><div class="header">
  <div class="headertitle">
<div class="title">Combiner Explanation </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h1><a class="anchor" id="autotoc_md82"></a>
Talk by ctiller, notes by vjpai</h1>
<p>Typical way of doing critical section</p>
<div class="fragment"><div class="line">mu.lock()</div>
<div class="line">do_stuff()</div>
<div class="line">mu.unlock()</div>
</div><!-- fragment --><p>An alternative way of doing it is</p>
<div class="fragment"><div class="line">class combiner {</div>
<div class="line">  run(f) {</div>
<div class="line">    mu.lock()</div>
<div class="line">    f()</div>
<div class="line">    mu.unlock()</div>
<div class="line">  }</div>
<div class="line">  mutex mu;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line">combiner.run(do_stuff)</div>
</div><!-- fragment --><p>If you have two threads calling combiner, there will be some kind of queuing in place. It's called <code>combiner</code> because you can pass in more than one do_stuff at once and they will run under a common <code>mu</code>.</p>
<p>The implementation described above has the issue that you're blocking a thread for a period of time, and this is considered harmful because it's an application thread that you're blocking.</p>
<p>Instead, get a new property:</p><ul>
<li>Keep things running in serial execution</li>
<li>Don't ever sleep the thread</li>
<li>But maybe allow things to end up running on a different thread from where they were started</li>
<li>This means that <code>do_stuff</code> doesn't necessarily run to completion when <code>combiner.run</code> is invoked</li>
</ul>
<div class="fragment"><div class="line">class combiner {</div>
<div class="line">  mpscq q; // multi-producer single-consumer queue can be made non-blocking</div>
<div class="line">  state s; // is it empty or executing</div>
<div class="line"> </div>
<div class="line">  run(f) {</div>
<div class="line">    if (q.push(f)) {</div>
<div class="line">      // q.push returns true if it&#39;s the first thing</div>
<div class="line">      while (q.pop(&amp;f)) { // modulo some extra work to avoid races</div>
<div class="line">        f();</div>
<div class="line">      }</div>
<div class="line">    }</div>
<div class="line">  }</div>
<div class="line">}</div>
</div><!-- fragment --><p>The basic idea is that the first one to push onto the combiner executes the work and then keeps executing functions from the queue until the combiner is drained.</p>
<p>Our combiner does some additional work, with the motivation of write-batching.</p>
<p>We have a second tier of <code>run</code> called <code>run_finally</code>. Anything queued onto <code>run_finally</code> runs after we have drained the queue. That means that there is essentially a finally-queue. This is not guaranteed to be final, but it's best-effort. In the process of running the finally item, we might put something onto the main combiner queue and so we'll need to re-enter.</p>
<p><code>chttp2</code> 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.</p>
<div class="fragment"><div class="line">class combiner {</div>
<div class="line">  mpscq q; // multi-producer single-consumer queue can be made non-blocking</div>
<div class="line">  state s; // is it empty or executing</div>
<div class="line">  queue finally; // you can only do run_finally when you are already running something from the combiner</div>
<div class="line"> </div>
<div class="line">  run(f) {</div>
<div class="line">    if (q.push(f)) {</div>
<div class="line">      // q.push returns true if it&#39;s the first thing</div>
<div class="line">      loop:</div>
<div class="line">      while (q.pop(&amp;f)) { // modulo some extra work to avoid races</div>
<div class="line">        f();</div>
<div class="line">      }</div>
<div class="line">      while (finally.pop(&amp;f)) {</div>
<div class="line">        f();</div>
<div class="line">      }</div>
<div class="line">      goto loop;</div>
<div class="line">    }</div>
<div class="line">  }</div>
<div class="line">}</div>
</div><!-- fragment --><p>So that explains how combiners work in general. In gRPC, there is <code>start_batch(..., tag)</code> and then work only gets activated by somebody calling <code>cq::next</code> which returns a tag. This gives an API-level guarantee that there will be a thread doing polling to actually make work happen. However, some operations are not covered by a poller thread, such as cancellation that doesn't have a completion. Other callbacks that don't have a completion are the internal work that gets done before the batch gets completed. We need a condition called <code>covered_by_poller</code> that means that the item will definitely need some thread at some point to call <code>cq::next</code> . This includes those callbacks that directly cause a completion but also those that are indirectly required before getting a completion. If we can't tell for sure for a specific path, we have to assumed it is not covered by poller.</p>
<p>The above combiner has the problem that it keeps draining for a potentially infinite amount of time and that can lead to a huge tail latency for some operations. So we can tweak it by returning to the application if we know that it is valid to do so:</p>
<div class="fragment"><div class="line">while (q.pop(&amp;f)) {</div>
<div class="line">  f();</div>
<div class="line">  if (control_can_be_returned &amp;&amp; some_still_queued_thing_is_covered_by_poller) {</div>
<div class="line">    offload_combiner_work_to_some_other_thread();</div>
<div class="line">  }</div>
<div class="line">}</div>
</div><!-- fragment --><p><code>offload</code> is more than <code>break</code>; it does <code>break</code> but also causes some other thread that is currently waiting on a poll to break out of its poll. This is done by setting up a per-polling-island work-queue (distributor) wakeup FD. The work-queue is the converse of the combiner; it tries to spray events onto as many threads as possible to get as much concurrency as possible.</p>
<p>So <code>offload</code> really does:</p>
<div class="fragment"><div class="line">workqueue.run(continue_from_while_loop);</div>
<div class="line">break;</div>
</div><!-- fragment --><p>This needs us to add another class variable for a <code>workqueue</code> (which is really conceptually a distributor).</p>
<div class="fragment"><div class="line">workqueue::run(f) {</div>
<div class="line">  q.push(f)</div>
<div class="line">  eventfd.wakeup()</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line">workqueue::readable() {</div>
<div class="line">  eventfd.consume();</div>
<div class="line">  q.pop(&amp;f);</div>
<div class="line">  f();</div>
<div class="line">  if (!q.empty()) {</div>
<div class="line">    eventfd.wakeup(); // spray across as many threads as are waiting on this workqueue</div>
<div class="line">  }</div>
<div class="line">}</div>
</div><!-- fragment --><p>In principle, <code>run_finally</code> could get starved, but this hasn't happened in practice. If we were concerned about this, we could put a limit on how many things come off the regular <code>q</code> before the <code>finally</code> queue gets processed. </p>
</div></div><!-- contents -->
</div><!-- PageDoc -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Wed Mar 3 2021 19:17:11 for GRPC Core by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.17
</small></address>
</body>
</html>