<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto">This [1] :: <div><br></div><div>[1] Midori’s Asynchronous Everything :: <a href="http://joeduffyblog.com/2015/11/19/asynchronous-everything/">http://joeduffyblog.com/2015/11/19/asynchronous-everything/</a><br><div><br></div><div><h2 id="message-passing" style="margin: 0px 0px 10px; padding: 0px; border: 0px; font-size: 18px; font-family: "open sans", sans-serif; vertical-align: baseline; color: rgb(24, 24, 24); line-height: 24px; -webkit-text-size-adjust: 100%;"><i>Message Passing</i></h2><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>A fundamental part of the system has been missing from the conversation: message passing.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>Not only were processes ultra-lightweight, they were single-threaded in nature. Each one ran an <a href="https://en.wikipedia.org/wiki/Event-driven_programming" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">event loop</a> and that event loop couldn’t be blocked, thanks to the non-blocking nature of the system. Its job was to execute a piece of non-blocking work until it finished or awaited, and then to fetch the next piece of work, and so on. An await that was previously waiting and became satisfied was simply scheduled as another turn of the crank.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>Each such turn of the crank was called, fittingly, a “turn.”</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>This meant that turns could happen between asynchronous activities and at await points, nowhere else. As a result, concurrent interleaving only occurred at well-defined points. This was a giant boon to reasoning about state in the face of concurrency, however it comes with some gotchas, as we explore later.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>The nicest part of this, however, was that processes suffered no shared memory race conditions.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>We did have a task and data parallel framework. It leveraged the concurrency safety features of the languge I’ve mentioned previously – <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=170528" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">immutability, isolation, and readonly annotations</a>– to ensure that this data race freedom was not violated. This was used for fine-grained computations that could use the extra compute power. Most of the system, however, gained its parallel execution through the decomposition into processes connected by message passing.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>Each process could export an asynchronous interface. It looked something like this:</i></p><div class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><div class="highlight" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline;"><pre class="highlight" style="margin-top: 0px; margin-bottom: 0px; padding: 8px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline; white-space: pre; overflow: auto;"><code style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;"><i>async interface ICalculator {
async int Add(int x, int y);
async int Multiply(int x, int y);
// Etc...
}
</i></code></pre></div></div><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>As with most asynchronous RPC systems, from this interface was generated a server stub and client-side proxy. On the server, we would implement the interface:</i></p><div class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><div class="highlight" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline;"><pre class="highlight" style="margin-top: 0px; margin-bottom: 0px; padding: 8px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline; white-space: pre; overflow: auto;"><code style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;"><i>class MyCalculator : ICalculator {
async int Add(int x, int y) { return x + y; }
async int Multiply(int x, int y) { return x * y; }
// Etc...
}
</i></code></pre></div></div><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>Each server-side object could also request <a href="https://en.wikipedia.org/wiki/Capability-based_security" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">capabilities</a> simply by exposing a constructor, much like the program’s main entrypoint could, as I described in <a href="http://joeduffyblog.com/2015/11/10/objects-as-secure-capabilities/" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">the prior post</a>. Our application model took care of activating and wiring up the server’s programs and services.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>A server could also return references to other objects, either in its own process, or a distant one. The system managed the object lifetime state in coordination with the garbage collector. So, for example, a tree:</i></p><div class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><div class="highlight" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline;"><pre class="highlight" style="margin-top: 0px; margin-bottom: 0px; padding: 8px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline; white-space: pre; overflow: auto;"><code style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;"><i>class MyTree : ITree {
async ITree Left() { ... }
async ITree Right() { ... }
}
</i></code></pre></div></div><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>As you might guess, the client-side would then get its hands on a proxy object, connected to this server object running in a process. It’s possible the server would be in the same process as the client, however typically the object was distant, because this is how processes communicated with one another:</i></p><div class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><div class="highlight" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline;"><pre class="highlight" style="margin-top: 0px; margin-bottom: 0px; padding: 8px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline; white-space: pre; overflow: auto;"><code style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;"><i>class MyProgram {
async void Main(IConsole console, ICalculator calc) {
var result = await calc.Add(2, 2);
await console.WriteLine(result);
}
}
</i></code></pre></div></div><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>Imagining for a moment that the calculator was a system service, this program would communicate with that system service to add two numbers, and then print the result to the console (which itself also could be a different service).</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>A few key aspects of the system made message passing very efficient. First, all of the data structures necessary to talk cross-process were in user-mode, so no kernel-mode transitions were needed. In fact, they were mostly lock-free. Second, the system used a technique called “<a href="https://en.wikipedia.org/wiki/Futures_and_promises#Promise_pipelining" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">pipelining</a>” to remove round-trips and synchronization ping-ponging. Batches of messages could be stuffed into channels before they filled up. They were delivered in chunks at-a-time. Finally, a novel technique called “three-party handoff” was used to shorten the communication paths between parties engaging in a message passing dialogue. This cut out middle-men whose jobs in a normal system would have been to simply bucket brigade the messages, adding no value, other than latency and wasted work.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><img src="cid:B4A790E0-0DD2-4524-A559-8A3DF5B10BFE" alt="Message Passing Diagram" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; display: block;"></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>The only types marshalable across message passing boundaries were:</i></p><ul style="margin: 4px 0px 5px 1.35em; padding: 0px; border: 0px; font-size: 12.6px; font-family: "open sans", sans-serif; vertical-align: baseline; list-style-position: initial; list-style-image: initial; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><li style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: inherit; vertical-align: baseline; line-height: 22px;"><i>Primitive types (<code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">int</code>, <code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">string</code>, etc).</i></li><li style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: inherit; vertical-align: baseline; line-height: 22px;"><i>Custom PODs that didn’t contain pointers (explicitly labeled marshalable).</i></li><li style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: inherit; vertical-align: baseline; line-height: 22px;"><i>References to streams (see below).</i></li><li style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: inherit; vertical-align: baseline; line-height: 22px;"><i>References to other async objects (e.g., our <code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">ICalculator</code>above).</i></li><li style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: inherit; vertical-align: baseline; line-height: 22px;"><i>A special <code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">SharedData</code> object, which requires a bit more explanation.</i></li></ul><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>Most of these are obvious. The <code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">SharedData</code> thing is a little subtle, however. Midori had a fundamental philosophy of “zero-copy” woven throughout its fabric. This will be the topic of a future post. It’s the secret sauce that let us out-perform many classical systems on some key benchmarks. The idea is, however, no byte should be copied if it can be avoided. So we don’t want to marshal a <code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">byte[]</code> by copy when sending a message between processes, for example. The <code class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;">SharedData</code>was a automatic ref-counted pointer to some immutable data in a heap shared between processes. The OS kernel managed this heap memory and reclaimed it when all references dropped to zero. Because the ref-counts were automatic, programs couldn’t get it wrong. This leveraged some new features in our language, like destructors.</i></p><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>We also had the notion of “near objects,” which went an extra step and let you marshal references to immutable data within the same process heap. This let you marshal rich objects by-reference. For example:</i></p><div class="highlighter-rouge" style="margin: 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><div class="highlight" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline;"><pre class="highlight" style="margin-top: 0px; margin-bottom: 0px; padding: 8px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline; white-space: pre; overflow: auto;"><code style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; vertical-align: baseline;"><i>// An asynchronous object in my heap:
ISpellChecker checker = ...;
// A complex immutable Document in my heap,
// perhaps using piece tables:
immutable Document doc = ...;
// Check the document by sending messages within
// my own process; no copies are necessary:
var results = await checker.Check(doc);
</i></code></pre></div></div><p style="margin: 14px 0px; padding: 0px; border: 0px; font-size: 14px; font-family: "open sans", sans-serif; vertical-align: baseline; line-height: 21px; caret-color: rgb(34, 34, 34); color: rgb(34, 34, 34); -webkit-text-size-adjust: 100%;"><i>As you can guess, all of this was built upon a more fundamental notion of a “channel.” This is similar to what you’ll see in <a href="https://en.wikipedia.org/wiki/Occam_(programming_language)" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">Occam</a>, <a href="https://en.wikipedia.org/wiki/Go_(programming_language)" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">Go</a> and related <a href="https://en.wikipedia.org/wiki/Communicating_sequential_processes" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">CSP</a> languages. I personally found the structure and associated checking around how messages float around the system more comfortable than coding straight to the channels themselves, but your mileage may vary. The result felt similar to programming with <a href="https://en.wikipedia.org/wiki/Actor_model" style="margin: 0px; padding: 0px; border: 0px; font-family: inherit; vertical-align: baseline; color: rgb(0, 172, 242); text-decoration: none; outline: 0px; line-height: inherit;">actors</a>, with some key differences around the relationship between process and object identity.</i></p><br><div dir="ltr"><div dir="ltr"><span style="background-color: rgba(255, 255, 255, 0);">•••<br>𝙄𝙛 𝙮𝙤𝙪 𝙖𝙧𝙚 𝙙𝙧𝙞𝙫𝙞𝙣𝙜 𝙖 𝙋𝙤𝙧𝙨𝙘𝙝𝙚, 𝙩𝙝𝙖𝙣𝙠 𝙮𝙤𝙪 𝙛𝙤𝙧 </span></div><div dir="ltr"><span style="background-color: rgba(255, 255, 255, 0);">𝙢𝙤𝙫𝙞𝙣𝙜 𝙤𝙫𝙚𝙧, 𝙨𝙤 𝙩𝙝𝙖𝙩 𝙄 𝙘𝙤𝙪𝙡𝙙 𝙨𝙖𝙛𝙚𝙡𝙮 𝙥𝙖𝙨𝙨! </span></div><div dir="ltr"><span style="background-color: rgba(255, 255, 255, 0);">𝘼𝙧𝙧𝙞𝙫𝙚𝙙𝙚𝙧𝙘𝙞, 𝙧𝙖𝙗𝙗𝙞𝙩 • </span><span style="font-size: 17pt; background-color: rgba(255, 255, 255, 0);">𝘿𝙖𝙩𝙨𝙪𝙣 </span><span style="font-size: 17pt; background-color: rgba(255, 255, 255, 0);">𝟮𝟰𝟬</span><span style="font-size: 17pt; background-color: rgba(255, 255, 255, 0);">𝙕 • </span><span style="font-size: 17pt; background-color: rgba(255, 255, 255, 0);">🐰</span></div></div></div></div></body></html>