Facebook's C++ 11 component library Folly Futures

Facebook's C++ 11 component library Folly Futures

English original: code.facebook.com/posts/16619...



Futures are a model for expressing asynchronous computing in a natural and composable way. This blog post introduces a C++11 futures implementation we use in Facebook : Folly Futures .

Why use asynchronous?

Imagine a scenario where service A is interacting with service B. If A is locked to B before it can continue to perform other operations after replying, then A is synchronized. At this time, the thread where A is located is idle, and it cannot provide services for other requests. Threads can become very cumbersome-switching threads is inefficient because it consumes a lot of memory, and if you do a lot of these operations, the operating system will get into trouble. The result of this is wasted resources, reduced productivity, and increased waiting time (because requests are waiting in the queue for service).

If service A is made asynchronous, it will become more efficient, which means that when B is busy computing, A can switch in to handle other requests. When B has calculated the result, A gets the result and ends the request.


Comparison of synchronous code and asynchronous code

Let us consider a function fooSync, which uses a completely synchronous way to complete the basic calculation foo, while using another function fooAsync to do the same work asynchronously. fooAsync needs to provide an input and a callback function that can be called when the result is available.

template  < typename  T >  using Callback = std::function<void(T)>; Output fooSync(Input); fooAsync void (the Input, the Callback < the Output > ); duplicated code

This is a traditional way of expressing asynchronous computing. (The old version of C/C++ asynchronous library will provide a function pointer and a void* type context parameter, but now C++11 supports hidden functions, it is no longer necessary to explicitly provide context parameters)


Traditional asynchronous code is more effective than synchronous code, but it is not very readable. Comparing the synchronous and asynchronous versions of the same function, they both implement a multiFoo operation, which performs the foo operation for each element in the input vector (vector):

using std::vector;vector < Output >  multiFooSync(vector < Input >  inputs) {   vector < Output >  outputs;   for (auto input: inputs) {     outputs.push_back(fooSync(input));   }   return outputs;} Copy code
void multiFooAsync(   vector < Input >  inputs,   Callback <Vector < the Output > > the callback) {   struct Context {     vector < Output >  outputs;     std::mutex lock;     size_t remaining;   };   auto context = std::make_shared < Context > ();   context->remaining = inputs.size();        for (auto input: inputs) {     fooAsync(       input,       [=](Output output) {         std::lock_guard<std::mutex> guard(context->lock);         context->outputs->push_back(output);         if (--context->remaining == 0) {           callback(context->outputs);         }       });   }} Copy code

The asynchronous version is much more complicated. It needs to pay attention to many aspects, such as setting a shared context object, thread safety, and bookkeeping, so it must specify when all calculations are completed. What's worse (although it's not obvious in this example) this makes the computation graph of code execution complicated, making it extremely difficult to track the execution path. The programmer needs to establish a set of thinking models for the state machine of the entire service and the different behaviors of the state machine when receiving different inputs, and find a place to check when a certain part of the code cannot reflect the process. This situation is also affectionately called "callback hell."



Future is an object used to represent the result of asynchronous calculation (not necessarily available). When the calculation is complete, the future will hold a value or an exception. E.g:

#include <folly/futures/Future.h>  using folly::Future; //Do foo asynchronously; immediately return a Future for the output Future < Output >  fooFuture(Input); Future < Output >  f = fooFuture(input); //f may not have a value (or exception) yet. But eventually it will. f.isReady();//Maybe, maybe not. f.wait();//You can synchronously wait for futures to become ready. f.isReady();//Now this is guaranteed to be true. Output o = f.value();//If f holds an exception, this will throw that exception. Copy code

So far, we have not done anything that  std::future  cannot do. But a powerful aspect of the future mode is that chain callbacks can be achieved, which is currently not supported by std::future. We  express this function through the method  Future::then :

Future < double >  f =    fooFuture(input)   .then([](Output o) {     return o * M_PI;   })   .onError([](std::exception const& e) {     cerr << "Oh bother, "<< e.what()       << ". Returning pi instead." << endl;     return M_PI;   });//get() first waits, and then returns the valuecout << "Result: "<< f.get() << endl; Copy code

Here we use the connected then like onError to catch any exceptions that may be raised. The ability to connect futures is an important ability that allows us to write serial and parallel calculations, express them in the same place, and provide clear error handling.


Serial function composition

If you want to calculate a, b, c, and d asynchronously in sequence, you will fall into "callback hell" when programming with traditional callback methods-or, if your language has first-class anonymous functions (such as C++11), the result May be the "callback pyramid":

//the callback pyramid is syntactically annoying void asyncA(Output, Callback < OutputA > ); void asyncB(OutputA, Callback < OutputB > ); void asyncC(OutputB, Callback < OutputC > ); void asyncD(OutputC, Callback < OutputD > ); auto result = std::make_shared < double > (); fooAsync(input, [=](Output output) {   //...   asyncA(output, [=](OutputA outputA) {     //...     asyncB(outputA, [=](OutputB outputB) {       //...       asyncC(outputB, [=](OutputC outputC) {         //...         asyncD(outputC, [=](OutputD outputD) {           *result = outputD * M_PI;         });       });     });   }); }); //As an exercise for the masochistic reader, express the same thing without //lambdas. The result is called callback hell. Copy code

With futures, use then to combine them sequentially, and the code will become clean and tidy:

Future < OutputA >  futureA(Output); Future < OutputB >  futureB(OutputA); Future < OutputC >  futureC(OutputB); //then() automatically lifts values (and exceptions) into a Future. OutputD d(OutputC) {   if (somethingExceptional) throw anException;   return OutputD();}Future < double >  fut =   fooFuture(input)   .then(futureA)   .then(futureB)   .then(futureC)   .then(d)   .then([](OutputD outputD) {//lambdas are ok too     return outputD * M_PI;   }); Copy code

Parallel function composition

Let's go back to our multiFoo example. Here is how it looks in the future:

using folly::futures::collect; Future<vector < Output >> multiFooFuture(vector < Input >  inputs) {   Vector <Future < the Output > > Futures;   for (auto input: inputs) {     futures.push_back(fooFuture(input));   }   return collect(futures);} Copy code

Collect is a compositional building block we provide. It takes Future<T> as input and returns a Future<vector<T>>, which will be completed after all futures are completed. (The implementation of collect depends on-you guessed it-then) There are many other building blocks , including: collectAny, collectN, map, and reduce.

Please note why this code looks very similar to the synchronous version of multiFooSync, we don't need to worry about context or thread safety. These problems are solved by the framework, and they are transparent to us.


Execution context

The futures framework in some other languages provides a thread pool for executing callback functions. You don't need to pay attention to any extra details except to know that the context is executed in another thread. But C++ developers tend to write C++ code because they need to control the underlying details to achieve performance optimization, and Facebook is no exception. Therefore, we use a simple  Executor interface to provide a flexible mechanism to clearly control the execution of the callback context:

struct Executor {   using Func = std::function<void()>;   virtual void add(Func) = 0;}; Copy code

You can pass an executor to the then function to instruct its callback to be executed by the executor.

a(input).then(executor, b); Copy code

In this code, b will be executed by the executor, and b may be a specific thread, a thread pool, or something more interesting . A common use case of this method is to free the CPU from the I/O thread to avoid queuing time for other requests in the queue.


Futures means you never forget to say sorry

A common problem with traditional callback code is that it is not easy to track calls for errors or exceptions. The programmer must be disciplined in checking for errors and taking appropriate measures (even Superman must do this), let alone being thrown out by accident. Futures solve this problem by including a value and an exception. These exceptions are integrated with futures as you want, unless it stays in the future unit until it is caught by onErorr, or is synchronized, for example , Assignment or value. This makes it difficult (but not impossible) for us to lose an error that should be caught.

Use Promise

We have seen roughly how to use futures, let s talk about how we can make them. If you need to pass a value to Future, use makeFuture:

using folly::makeFuture; std::runtime_error greatScott("Great Scott!"); Future < double >  future = makeFuture(1.21e9); Future < Double >  Future = makeFuture < Double > (greatScott); duplicated code

But if you want to wrap an asynchronous operation, you need to use Promise:

using folly::Promise; Promise < double >  promise; Future < double >  future = promise.getFuture(); Copy code

When you are ready to assign a value to the promise, use setValue, setException, or setWith:

promise.setValue(1.21e9); promise.setException(greatScott); promise.setWith([]{   if (year == 1955 || year == 1885) throw greatScott;   return 1.21e9; }); Copy code


In short, we generate another thread to convert a long-running synchronous operation into an asynchronous operation, as shown in the following code:

double getEnergySync(int year) {   auto reactor = ReactorFactory::getReactor(year);   if (!reactor)//It must be 1955 or 1885     throw greatScott;   return reactor->getGigawatts(1.21); } Future < double >  getEnergy(int year) {   auto promise = make_shared<Promise < double > >();   std::thread([=]{     promise->setWith(std::bind(getEnergySync, year));   }).detach();      return promise->getFuture(); } Copy code

Normally you don't need promises, even if it looks like you did it at first glance. For example, if you already have an executor in your thread pool or can easily obtain it, then it would be easier to do this:

Future < Double >  Future :: = Folly Via (Executor, the bind STD :: (getEnergySync, year)); duplicated code

Use case learning

We provide two cases to explain how to use futures in Facebook and Instagram to improve latency, robustness, and code readability.

Instagram uses futures to transform the infrastructure of their recommendation service from synchronous to asynchronous to improve their system. The result is a significant reduction in tail latency, and the same throughput can be achieved with less than one-tenth of the server. They recorded the benefits of these changes and related changes, and you can refer to their blog for more details .


The next case is a real service, which is an integral part of Facebook News Feed. This service has a two-stage leaf-aggregate pattern. The request will be broken down into multiple leaf requests and the fragments will be distributed to different leaf servers. We are doing the same thing, but according to the first time As a result of the aggregation, the allocated fragments will become different. In the end, we take two sets of results and reduce them to a single response (response).

Here is a simplified version of the relevant code:

Future <Vector < LeafResponse > > fanout (   const map<Leaf, LeafReq>& leafToReqMap,   chrono::milliseconds timeout) {   Vector <Future < LeafResponse > > leafFutures;   for (const auto& kv: leafToReqMap) {     const auto& leaf = kv.first;     const auto& leafReq = kv.second;     leafFutures.push_back(       //Get the client for this leaf and do the async RPC       getClient(leaf)->futureLeafRPC(leafReq)       //If the request times out, use an empty response and move on.       .onTimeout(timeout, [=] {return LeafResponse(); })       //If there's an error (eg RPC exception),       //use an empty response and move on.       .onError([=](const exception& e) {return LeafResponse(); }));   }   //Collect all the individual leaf requests into one Future   return collect(leafFutures); } //Some sharding function; possibly dependent on previous responses. map<Leaf, LeafReq> buildLeafToReqMap(     const Request& request,     const vector < LeafResponse > & responses); //This function assembles our final response. Response assembleResponse(     const Request& request,     const vector < LeafResponse > & firstFanoutResponses,     const vector < LeafResponse > & secondFanoutResponses); Future < Response >  twoStageFanout(shared_ptr < Request >  request) {   //Stage 1: first fanout   return fanout(buildLeafToReqMap(*request, {}),                 FIRST_FANOUT_TIMEOUT_MS)   //Stage 2: With the first fanout completed, initiate the second fanout.   .then([=](vector < LeafResponse > & responses) {     auto firstFanoutResponses =       std::make_shared<vector < LeafResponse > >(std::move(responses));          //This time, sharding is dependent on the first fanout.     return fanout(buildLeafToReqMap(*request, *firstFanoutResponses),                   SECOND_FANOUT_TIMEOUT_MS)          //Stage 3: Assemble and return the final response.     .then([=](const vector < LeafResponse > & secondFanoutResponses) {       return assembleResponse(*request, *firstFanoutResponses, secondFanoutResponses);     });   }); } Copy code

The historical version of the service used an asynchronous framework that only allowed overall timeouts, and at the same time used the traditional "callback hell" mode. It is Futures that allows this service to naturally express asynchronous calculations and use granular timeouts to take more aggressive actions when certain parts are running too slowly. As a result, the average service delay was reduced by two-thirds, the tail delay was reduced to one-tenth of the original, and the overall timeout error was significantly reduced. The code becomes easier to read and reason about, and as a result, the code becomes easier to maintain.


When developers have tools that help them better understand and express asynchronous operations, they can write low-latency services that are easier to maintain.


Folly Futures brings robust, powerful, and high-performance futures to C++11. We hope you will like it (just like us). If you want to learn more, you can check out related documents , documentation blocks, and the code on GitHub .


The members of the Folly Futures production team include Hans Fugal, Dave Watson, James Sedgwick, Hannes Roth and Blake Mantheny, as well as many other like-minded contributors. We would like to thank Twitter, especially Marius, for his technical lectures on Finagle and Futures on Facebook, which inspired the creation of this project.