carto
/
grpc


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124
							<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://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.6"/>
<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/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</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 style="padding-left: 0.5em;">
   <div id="projectname">GRPC Core
   &#160;<span id="projectnumber">4.0.0</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.6 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="modules.html"><span>Modules</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Data Structures</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Macros</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Groups</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Pages</a></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="header">
  <div class="headertitle">
<div class="title">Combiner Explanation </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h2>Talk by ctiller, notes by vjpai</h2>
<p>Typical way of doing critical section</p>
<p>``` mu.lock() do_stuff() mu.unlock() ```</p>
<p>An alternative way of doing it is</p>
<p>``` class combiner { run(f) { mu.lock() f() mu.unlock() } mutex mu; }</p>
<p>combiner.run(do_stuff) ```</p>
<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>
<p>``` class combiner { mpscq q; // multi-producer single-consumer queue can be made non-blocking state s; // is it empty or executing</p>
<p>run(f) { if (q.push(f)) { // q.push returns true if it's the first thing while (q.pop(&amp;f)) { // modulo some extra work to avoid races f(); } } } } ```</p>
<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>
<p>``` class combiner { mpscq q; // multi-producer single-consumer queue can be made non-blocking state s; // is it empty or executing queue finally; // you can only do run_finally when you are already running something from the combiner</p>
<p>run(f) { if (q.push(f)) { // q.push returns true if it's the first thing loop: while (q.pop(&amp;f)) { // modulo some extra work to avoid races f(); } while (finally.pop(&amp;f)) { f(); } goto loop; } } } ```</p>
<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>
<p>``` while (q.pop(&amp;f)) { f(); if (control_can_be_returned &amp;&amp; some_still_queued_thing_is_covered_by_poller) { offload_combiner_work_to_some_other_thread(); } } ```</p>
<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>
<p>``` workqueue.run(continue_from_while_loop); break; ```</p>
<p>This needs us to add another class variable for a <code>workqueue</code> (which is really conceptually a distributor).</p>
<p>``` workqueue::run(f) { q.push(f) eventfd.wakeup() }</p>
<p>workqueue::readable() { eventfd.consume(); q.pop(&amp;f); f(); if (!q.empty()) { eventfd.wakeup(); // spray across as many threads as are waiting on this workqueue } } ```</p>
<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 -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Wed Jun 21 2017 14:13:07 for GRPC Core by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.6
</small></address>
</body>
</html>