Add Wangle README.md

[folly.git] / folly / wangle / README.md

# Wangle
Wangle is a framework for expressing asynchronous code in C++ using the Future pattern.

**wan•gle** |ˈwaNGgəl| informal  
*verb*  
Obtain (something that is desired) by persuading others to comply or by manipulating events.

*noun*  
A framework for expressing asynchronous control flow in C++, that is composable and easily translated to/from synchronous code.

*synonyms*  
[Finagle](http://twitter.github.io/finagle/)

Wangle is a futures-based async framework inspired by [Twitter's Finagle](http://twitter.github.io/finagle/) (which is in scala), and (loosely) building upon the existing (but anemic) Futures code found in the C++11 standard ([`std::future`](http://en.cppreference.com/w/cpp/thread/future)) and [`boost::future`](http://www.boost.org/doc/libs/1_53_0/boost/thread/future.hpp) (especially >= 1.53.0). Although inspired by the std::future interface, it is not syntactically drop-in compatible because some ideas didn't translate well enough and we decided to break from the API. But semantically, it should be straightforward to translate from existing std::future code to Wangle.

The primary semantic differences are that Wangle Futures and Promises are not threadsafe; and as does `boost::future`, Wangle supports continuations (`then()`) and there are helper methods `whenAll()` and `whenAny()` which are important compositional building blocks.

## Brief Synopsis

```C++
#include <folly/wangle/Future.h>
using namespace folly::wangle;
using namespace std;

void foo(int x) {
  // do something with x
  cout << "foo(" << x << ")" << endl;
}

// ...

  cout << "making Promise" << endl;
  Promise<int> p;
  Future<int> f = p.getFuture();
  f.then(
    [](Try<int>&& t) {
      foo(t.value());
    });
  cout << "Future chain made" << endl;

// ... now perhaps in another event callback

  cout << "fulfilling Promise" << endl;
  p.setValue(42);
  cout << "Promise fulfilled" << endl;
```

This would print:
  
```
making Promise
Future chain made
fulfilling Promise
foo(42)
Promise fulfilled
```

## User Guide

Let's begin with an example. Consider a simplified Memcache client class with this interface:

```C++
class MemcacheClient {
 public:
  struct GetReply {
    enum class Result {
      FOUND,
      NOT_FOUND,
      SERVER_ERROR,
    };

    Result result;
    // The value when result is FOUND,
    // The error message when result is SERVER_ERROR or CLIENT_ERROR
    // undefined otherwise
    std::string value;
  };

  GetReply get(std::string key);
};
```

This API is synchronous, i.e. when you call `get()` you have to wait for the result. This is very simple, but unfortunately it is also very easy to write very slow code using synchronous APIs.

Now, consider this traditional asynchronous signature for `get()`:

```C++
int get(std::string key, std::function<void(GetReply)> callback);
```

When you call `get()`, your asynchronous operation begins and when it finishes your callback will be called with the result. (Unless something goes drastically wrong and you get an error code from `get()`.) Very performant code can be written with an API like this, but for nontrivial applications the code descends into a special kind of spaghetti code affectionately referred to as "callback hell".

The Future-based API looks like this:

```C++
Future<GetReply> get(std::string key);
```

A `Future<GetReply>` is a placeholder for the `GetReply` that we will eventually get. A Future usually starts life out "unfulfilled", or incomplete, i.e.:

```C++
fut.isReady() == false
fut.value()  // will throw an exception because the Future is not ready
```

At some point in the future, the Future will have been fulfilled, and we can access its value.

```C++
fut.isReady() == true
GetReply& reply = fut.value();
```

Futures support exceptions. If something exceptional happened, your Future may represent an exception instead of a value. In that case:

```C++
fut.isReady() == true
fut.value() // will rethrow the exception
```

Just what is exceptional depends on the API. In our example we have chosen not to raise exceptions for `SERVER_ERROR`, but represent this explicitly in the `GetReply` object. On the other hand, an astute Memcache veteran would notice that we left `CLIENT_ERROR` out of `GetReply::Result`, and perhaps a `CLIENT_ERROR` would have been raised as an exception, because `CLIENT_ERROR` means there's a bug in the library and this would be truly exceptional. These decisions are judgement calls by the API designer. The important thing is that exceptional conditions (including and especially spurious exceptions that nobody expects) get captured and can be handled higher up the "stack".

So far we have described a way to initiate an asynchronous operation via an API that returns a Future, and then sometime later after it is fulfilled, we get its value. This is slightly more useful than a synchronous API, but it's not yet ideal. There are two more very important pieces to the puzzle.

First, we can aggregate Futures, to define a new Future that completes after some or all of the aggregated Futures complete.  Consider two examples: fetching a batch of requests and waiting for all of them, and fetching a group of requests and waiting for only one of them.

```C++
vector<Future<GetReply>> futs;
for (auto& key : keys) {
  futs.push_back(mc.get(key));
}
auto all = whenAll(futs.begin(), futs.end());

vector<Future<GetReply>> futs;
for (auto& key : keys) {
  futs.push_back(mc.get(key));
}
auto any = whenAny(futs.begin(), futs.end());
```

`all` and `any` are Futures (for the exact type and usage see the header files).  They will be complete when all/one of `futs` are complete, respectively. (There is also `whenN()` for when you need *some*.)

Second, we can attach continuations (aka callbacks) to a Future, and chain them together monadically. An example will clarify:

```C++
Future<GetReply> fut1 = mc.get("foo");

Future<string> fut2 = fut1.then(
  [](Try<GetReply>&& t) {
    if (t.value().result == MemcacheClient::GetReply::Result::FOUND)
      return t.value().value;
    throw SomeException("No value");
  });

Future<void> fut3 = fut2.then(
  [](Try<string>&& t) {
    try {
      cout << t.value() << endl;
    } catch (std::exception const& e) {
      cerr << e.what() << endl;
    }
  });
```

That example is a little contrived but the idea is that you can transform a result from one type to another, potentially in a chain, and unhandled errors propagate. Of course, the intermediate variables are optional. `Try<T>` is the object wrapper that supports both value and exception.

Using `then` to add continuations is idiomatic. It brings all the code into one place, which avoids callback hell.

Up to this point we have skirted around the matter of waiting for Futures. You may never need to wait for a Future, because your code is event-driven and all follow-up action happens in a then-block. But if want to have a batch workflow, where you initiate a batch of asynchronous operations and then wait for them all to finish at a synchronization point, then you will want to wait for a Future.

Other future frameworks like Finagle and std::future/boost::future, give you the ability to wait directly on a Future, by calling `fut.wait()` (naturally enough). Wangle has diverged from this pattern for performance reasons. It turns out, making things threadsafe slows them down.  Whodathunkit? So Wangle Futures (and Promises, for you API developers) are not threadsafe. Yes, you heard right, and it should give you pause—what good is an *asynchronous* framework that isn't threadsafe? Well, actually, in an event-driven architecture there's still quite a bit of value, but that doesn't really answer the question. Wangle is, indeed, meant to be used in multithreaded environments. It's just that we move synchronization out of the Future/Promise pair and instead require explicit synchronization or (preferably) crossing thread boundaries with a form of message passing. It turns out that `then()` chaining is really handy and there are often many Futures chained together. But there is often only one thread boundary to cross.  We choose to pay the threadsafety overhead only at that thread boundary.

Wangle provides a mechanism to make this easy, called a `ThreadGate`. ThreadGates stand between two threads and pass messages (actually, functors) back and forth in a threadsafe manner. Let's work an example. Assume that `MemcacheClient::get()` is not thread-aware. It registers with libevent and tries to send a request, and then later in your event loop when it has successfully sent and received a reply it will complete the Future. But it doesn't even consider that there might be other threads in your program.  Now consider that `get()` calls should happen in an IO thread (the *east* thread) and user code is happening in a user thread (the *west* thread).  A ThreadGate will allow us to do this:

```C++
Future<GetReply> threadsafeGet(std::string key) {
  std::function<Future<GetReply>()> doEast = [=]() {
    return mc_->get(key);
  };
  auto westFuture = gate_.add(doEast);
  return westFuture;
}
```

Think of the ThreadGate as a pair of queues: from west to east we queue some functor that returns a Future, and then the ThreadGate conveys the result back from east to west and eventually fulfils the west Future. But when? The ThreadGate has to be *driven* from both sides—the IO thread has to pull work off the west-to-east queue, and the user thread has to drive the east-to-west queue. Sometimes this happens in the course of an event loop, as it would in a libevent architecture. Other times it has to be explicit, in which case you would call the gate's `makeProgress()` method. Or, if you know which Future you want to wait for you can use:

```C++
gate_.waitFor(fut);
```

The ThreadGate interface is simple, so any kind of threadsafe functor conveyance you can dream up that is perfect for your application can be implemented. Or, you can use `GenericThreadGate` and `Executor`s to make one out of existing pieces. The `ManualThreadGate` is worth a look as well, especially for unit tests.

In practice, the API will probably do the gating for you, e.g. `MemcacheClient::get()` would return an already-gated Future and provide a `waitFor()` proxy that lets you wait for Futures it has returned. Then as a user you never have to worry about it. But this exposition was to explain the probably-surprising design decision to make Futures not threadsafe and not support direct waiting.

`Later` is another approach to crossing thread boundaries that can be more flexible than ThreadGates.
(TODO document `Later` here.)

## You make me Promises, Promises

If you are wrapping an asynchronous operation, or providing an asynchronous API to users, then you will want to make Promises. Every Future has a corresponding Promise (except Futures that spring into existence already completed, with `makeFuture()`). Promises are simple, you make one, you extract the Future, and you fulfil it with a value or an exception. Example:

```C++
Promise<int> p;
Future<int> f = p.getFuture();

f.isReady() == false

p.setValue(42);

f.isReady() == true
f.value() == 42
```

and an exception example:

```C++
Promise<int> p;
Future<int> f = p.getFuture();

f.isReady() == false

p.setException(std::runtime_error("Fail"));

f.isReady() == true
f.value() // throws the exception
```

It's good practice to use fulfil which takes a function and automatically captures exceptions, e.g.

```C++
Promise<int> p;
p.fulfil([]{
  try {
    // do stuff that may throw
    return 42;
  } catch (MySpecialException const& e) {
    // handle it
    return 7;
  }
  // Any exceptions that we didn't catch, will be caught for us
});
```

## FAQ

### Why not use std::future?
No callback or continuation support.
See also http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3428.pdf

### Why not use boost::future?
- 1.53 is brand new, and not in fbcode
- It's still a bit buggy/bleeding-edge
- They haven't fleshed out the threading model very well yet, e.g. every single `then` currently spawns a new thread unless you explicitly ask it to work on this thread only, and there is no support for executors yet.
- boost::future has locking which isn't necessary in our cooperative-multithreaded use case, and assumed to be very expensive.

### Why use heap-allocated shared state? Why is Promise not a subclass of Future?
C++. It boils down to wanting to return a Future by value for performance (move semantics and compiler optimizations), and programmer sanity, and needing a reference to the shared state by both the user (which holds the Future) and the asynchronous operation (which holds the Promise), and allowing either to go out of scope.

### What about proper continuations? Futures suck.
People mean two things here, they either mean using continuations or they mean using generators which require continuations. It's important to know those are two distinct questions, but in our context the answer is the same because continuations are a prerequisite for generators.

C++ doesn't directly support continuations very well. But there are some ways to do them in C/C++ that rely on some rather low-level facilities like `setjmp` and `longjmp` (among others). So yes, they are possible (cf. [Mordor](https://github.com/ccutrer/mordor)).

The tradeoff is memory. Each continuation has a stack, and that stack is usually fixed-size and has to be big enough to support whatever ordinary computation you might want to do on it. So each living continuation requires a relatively large amount of memory. If you know the number of continuations will be small, this might be a good fit. In particular, it might be faster and the code might read cleaner.

Wangle takes the middle road between callback hell and continuations, one which has been trodden and proved useful in other languages. It doesn't claim to be the best model for all situations. Use your tools wisely.

### It's so @!#?'n hard to get the thread safety right
That's not a question.

Yes, it is hard and so you should use a ThreadGate or Later if you need to do any crossing of thread boundaries. Otherwise you need to be very careful. Especially because in most cases the naïve approach is not threadsafe and naïve testing doesn't expose the race condition.

The careful reader will note that we have only assumed locks to be a terrible performance penalty. We are planning on thoroughly benchmarking locks (and the alternative code patterns that having locks would enable), and if we find locks are Not That Bad™ we might reverse this decision (and fold ThreadGate and Later into Future/Promise).