Skip to content

Instantly share code, notes, and snippets.

@jcsherin
Last active July 25, 2021 09:35
Show Gist options
  • Save jcsherin/5f7d18bfb16ed99cf270b634a906b041 to your computer and use it in GitHub Desktop.
Save jcsherin/5f7d18bfb16ed99cf270b634a906b041 to your computer and use it in GitHub Desktop.
Your Server as a Function
  • Side by side terminology of Future and JS Promises to show similarity. This could be setup earlier when Futures abstraction is introduced. The code examples can then instead use JS Promises which should be familiar to frontend programmers.
  • References to Finagle are ad-hoc at best in the current draft. Make it clear to the reader how Finagle is relevant to the paper under discussion, and the goals of the project.
  • Fix signature difference between Future.t and Js.Promise.t in code examples
  • Add an introduction section which sets the context for this narrative. Building a modern web framework which can apply the principles used in building Finagle. Such a web framework written a statically typed language can provide safety guarantees at compile time. The functional style emphasizing immutability, composition, isolation of side effects etc improves our ability to reason about behaviour.
  • Rewrite conclusion section.
  • Include accidental vs essential complexity quote from out of the tarpit. It is already referenced in many places.
  • Update code examples to use JS promises instead of Future.t.
  • Improve section on andThen combinator to improve comprehension (combine it with composite filters)
  • Rewrite
    • Composite Filter (move this within the filters section)
    • Interrupts
    • Challenges
    • Finagle Ecosystem
  • Check notion notes for material which can improve this writing.
  • Add TOC
  • Remove these sections
    • Interrupts
    • Challenges

Your Server as a Function, Marius Eriksen

TOC

  1. Introduction
  2. Servers & Clients
  3. Abstractions
  4. Finagle Ecosystem
  5. Futures
    1. Dependent Composition
    2. Handling Errors
    3. Composing Multiple Dependencies
    4. Recursive Composition
  6. Services
  7. Filters
    1. Composite Filters
    2. Type Safety
  8. Conclusion

Introduction

Servers & Clients

Essential Complexity is inherent in, and the essence of, the problem (as seen by the users).

Accidental Complexity is all the rest -— complexity with which the development team would not have to deal in the ideal world (e.g. complexity arising from performance issues and from suboptimal language and infrastructure).

Out of the Tar Pit - Ben Moseley, Peter Marks

The simplest possible implementation of a client would be to make a request to a remote endpoint. When the results arrive, the client would parse the response and transform it to fit the users view. From the users point of view this is the essence of the problem, or it's essential complexity. This implementation though easy to understand and modify for another programmer, is not robust by any means. It does not handle network or request failures. It does not emit events for metrics and tracing. All the rest of the complexity you need to deal with is accidental.

The same is true for servers. The essence of the problem is to process a request and dispatch the computed response. But servers are expected to process many requests concurrently. There is an upper limit to the number of requests a server can process. Anything above and the server will be overwhelmed resulting in either slower response times or totally unresponsive to new requests.

Servers need to implement some form of admission control. A concurrency(rate) limit needs to be set so that it can reject or discard requests above the limit in a given time period. A service usually aggregates its response from the cache or database service layer. It is not prudent to wait indefinitely for a response from the upstream service. So a server itself will have to implement timeouts. In a production environment you will also need to log events for tracing, and tracking metrics in real time.

Clients need to respect the rate limit set by the upstream service. It will need to handle timeouts, when the response does not arrive in time. A client can reuse connections by maintaining a connection pool. A circuit breaker is useful the sever all existing connection to a service under certain operating conditions. Sometimes it may need to load balance requests between different replicas of a service. You will also need tracing, and metrics.

Therefore some of the operations of client and servers involve:

  • Rate Limiting
  • Timeouts
  • Retries
  • Circuit Breaker
  • Connection Pooling
  • Load Balancing
  • Tracing
  • Metrics
  • ...etc

Abstractions

The three abstractions which helps you to focus on the essence of the problem when writing server or client software are:

Futures The results of asynchronous operations are represented by futures which compose to express dependencies between operations.

Services Systems boundaries are represented by asynchronous functions called services. They provide a symmetric and uniform API: the same abstraction represents both clients and servers.

Filters Application-agnostic concerns (e.g. timeouts, retries, authentication) are encapsulated by filters which compose to build services from multiple independent modules.

Futures are the same as a Promises in Javascript. Services are transparent as they could be either local or go over the network.

The code examples in the paper are written in Scala. They have been translated to Reason. Reason lets us write type safe code, and has type inference. Values are immutable by default and have an inferred type. Values can be transformed using functions to the same or different types. Functions can be combined to form other higher order functions. Reason allows you to write code which is simple, and easy to reason about.

Finagle Ecosystem

Operations describe what is computed; execution is handled separately. This frees the programmer from attending to the minutiae of setting up threads, ensuring pools and queues are sized correctly, and making sure that resources are properly reclaimed — these concerns are instead handled by our runtime library, Finagle. Relinquishing the programmer from these responsibilities,the runtime is free to adapt to the situation at hand.

Finagle and its accompanying structuring idioms are used throughout the entire Twitter service stack — from frontend web servers to backend data systems.

Written in Scala, and works on the JVM. Solves a ton of problems under the hood which developers realize late after reiventing it by themselves. Support for 15+ protocols including Twitter's own multiplexing protocol Mux. Mux is a subset of HTTP/2. In the recent years it has also been copied to Rust, Kotlin, and Java8.

Twitter wanted to move to Scala, and their systems had to continue to work with memcache, thrift, redis, http etc. They recognized that all RPCs are fundamentally similar. If you implement load balancing for Redis, you can use the same for memcache. So it made sense to build Finagle to be protocol agnostic, and a generic library to support server and client implementations.

It became easier to reason about services which shared abstractions because multiple teams were all writing code in the same style. This really improved the ability to isolate and reason about issues which happened at the boundaries of services, and fix them fast.

Easier to reason about services with shared abstractions because everyone on other teams are writing in a similar style. So it becomes easier to isolate and reason about problems which happens at the boundaries of services, and fix them. Possible to turn on stats for a service which helps with debugging by instrumenting the service. Service itself is transparent as it could be leither local or something which goes over the network.

Futures

When this paper was written Scala did not have a Promise implementation. In fact very few mainstream programming languages had an impelmentation. Today the terms future, promise, delay, deferred and eventual all refer to the same concept in multiple languages.

A future is a container used to hold the result of an asynchronous operation such as a network RPC, a timeout, or a disk I/O operation. A future is either empty -— the result is not yet available; succeeded -— the producer has completed and has populated the future with the result of the operation; or failed -— the producer failed, and the future contains the resulting exception.

Futures

Dependent Composition

This examples demonstrates sequencing two asynchronous operations which have a data dependency. For example a search engine frontend, to provide personalized results will rewrite the query. The type of Futures or a promise in Reason is represented by Js.Promise.t.

There is a data dependency between search and rewrite functions. When the rewrite operation succeeds, the result of is applied to the search function. Both functions returns a promise of a result.

let rewrite(~user: string, ~query: string) => Js.Promise.t(string);

let search(~query: string) => Js.Promise.t(list(string));

To sequentially compose these functions the flatMap combinator is used in Finagle. The Reason equivalent is Js.Promise.then_. The first parameter is a function which takes a value of type 'a and returns a promise of type 'b. The second parameter is the promise of type 'a. The promise of type 'a is transformed to a promise of type 'b by applying the function.

Js.Promise.then_: ('a => Js.Promise.t('b), Js.Promise.t('a)) => Js.Promise.t('b)

This allows us to implement the personalizedSearch function as:

let personalizedSearch = (~user, ~query) =>
    rewrite(~user, ~query) |>
    Js.Promise.then_(query => search(~query));

personalizedSearch(~user="alice", ~query="where is bob?");

Handling Errors

When the outer rewrite in personalizedSearch fails it short circuits computation. The dependent search function is not executed. A failed promise contains an exception. Since the promise contains no value, the Js.Promise.then_ is not executed.

Promise values can be constructed as:

Js.Promise.resolve("success");

Js.Promise.reject(Invalid_argument("failed"));

Often we would need to retry a failed computation or atleast provide a default value. Finagle provides a rescue combinator. The equivalent in Reason is Js.Promise.catch.

Js.Promise.catch: (Js.Promise.error => Js.Promise.t('a), Js.Promise.t('a)) => Js.Promise.t('a)

In case there is an upstream failure in the service which rewrites a user queries, we can degrade and fallback to using the original search query. The personalizedSearch function can be updated to handle this scenario as such:

let personalizedSearch = (~user, ~query) =>
  rewrite(~user, ~query)
  |> within(milliseconds(50))
  |> Js.Promise.catch(exn =>
       switch (exn) {
       | TimeoutError => Js.Promise.resolve(query)
       | _ => Js.Promise.reject(NonRetriable)
       }
     )
  |> Js.Promise.then_(query => search(~query));

If the results of rewrite is not available within 50ms the outer promise will fail. On a TimeoutError we degrade to using the original query parameter for search with Js.Promise.resolve(query).

Composing Multiple Dependencies

When you need to issue multiple requests and aggregate the results, the collect combinator is provided for resolving multiple data dependencies. The Reason equivalent is the Js.Promise.all function.

Js.Promise.all: array(Js.Promise.t('a)) => Js.Promise.t(array('a))

This example is for a search frontend which splits requests to a replica of each segment, and then combines the results. The querySegment function returns an array of search results for segment identified by id.

let querySegment:
  (~id: int, ~query: string) => Js.Promise.t(array(SearchResult.t));

The Js.Promise.all can be used to split queries to a replica of each segment concurrently. If any of the promises fail, the collected future will fail immediately.

let search = (~query) =>
  Js.Promise.all([| 
    querySegment(~id=0, ~query), 
    querySegment(~id=1, ~query), 
    querySegment(~id=2, ~query)|])
  |> Js.Promise.then_(results => 
    results 
    |> Array.flatten 
    |> Js.Promise.resolve)

Recursive Composition

This is an example of searching iteratively until we have the required number of results by permuting the query in some manner in each iteration. Tail call optimization should be implemented to avoid stack size exceeded runtime errors.

let rec rsearch =
    (user, query, results, n: int): Js.Promise.t(array(SearchResult.t)) =>
  if (Array.length(results) >= n) {
    Js.Promise.resolve(results);
  } else {
    let nextQuery = permute(~query);

    personalizedSearch(~user, ~query=nextQuery)
    |> Js.Promise.then_(newResults =>
        if (List.length(newResults) > 0) {
          rsearch(user, nextQuery,(results @ newResults), n);
        } else {
          Js.Promise.resolve(results);
        }
    );
  };

Services

A service represents an endpoint to which requests are dispatched. It is a function which accepts a request parameter and returns a promise of a response. The service type Service.t('req, 'resp) is parametrized by the request type 'req and the response type 'resp.

module Service = {
  type t('req, 'resp) = 'req => Js.Promise.t('resp);
};

Clients and servers are symmetric in their operation. The Services abstraction represents both clients and servers. The next example shows making an HTTP request to the Twitter website.

let client: Service.t(HttpRequest.t, HttpResponse.t) =
  Http.newService("twitter.com:80");

let getIndex: Js.Promise.t(HttpResponse.t) = HttpRequest.make("/") |> client;

These are examples of an echo server and, a primitive HTTP proxy forwarding local traffic from port 8080 to twitter.com.

/* An HTTP Echo server */
Http.serve(":80", (req: HttpRequest.t) =>
  req |> HttpRequest.body |> HttpResponse.make(Status.OK) |> Js.Promise.resolve
);

/* Primitive HTTP proxy */
Http.serve(":8080", Http.newService("twitter.com:80"));

Filters

Filters implement application agnostic concerns such as timeouts, retries, metrics, authentication etc. They are composed with services to modify service behaviour. Its type is a function which accepts a request, and service as its parameters and returns a promise of a response.

module Filter = {
  type t('req, 'resp) = ('req, Service.t('req, 'resp)) => Js.Promise.t('resp);
};

This is an example of a filter which performs a request timeout.

let timeoutFilter = (duration) =>
  (req, service) => req |> service |> within(duration)

Composite Filters

The andThen combinator is useful for combining filters with other filters to produce composite filters. It can also be used with services to produce a new service whose behaviour is modified by the filter. Filters can be applied to both clients and servers.

let httpClient: Service.t(HttpRequest.t, HttpResponse.t) = ...;

let httpClientWithTimeout: Service.t(HttpRequest.t, HttpResponse.t) =
  timeoutFilter(seconds(10)) |> andThen(httpClient)

Filters have held their promise of providing clean, orthogonal, and application independent functionality. They are used universally: Finagle itself uses filters heavily; our frontend web servers—reverse HTTP proxies through which all of our external traffic flows - use a large stack of filters to implement different aspects of its responsibilities. This is an excerpt from its current configuration:

recordHandletime
|> andThen(traceRequest)
|> andThen(collectJvmStats)
|> andThen(parseRequest)
|> andThen(logRequest)
|> andThen(recordClientStats)
|> andThen(sanitize)
|> andThen(respondToHealthCheck)
|> andThen(applyTrafficControl)
|> andThen(virtualHostServer);

Type Safety

Filters transform request and responses. The static typing of the compiler can be used to enforce certain guarantees. For example an HTTP server may use a separate type to indicate authenticated requests. The authReq function authenticates the input request via an auth service, and returns an upgraded request on success, or fails to authenticate.

let authReq = (req: HttpRequest.t) => Js.Promise.t(AuthHttpRequest.t);

The auth filter can be composed with a service to upgrade it to a service which demands authentication. Unauthenticated requests can then be dispatched to this service for authentication.

let auth = (req, service) => authReq(req) |> Js.Promise.then_(service);

Access is denied to authedService if authentication step fails. If you attempt to write code which provides an regular HTTP request type with authedService it is caught as a compilation error. The authedService expects an upgraded request of type AuthHttpRequest.t. You are able to enforce certain guarantees about your code availing the static typing abilities of the compiler. You can rest assured that you will not accidentally mix up between authenticated and unauthenticated requests.

let authedService: Service.t(AuthHttpRequest.t, HttpResponse.t) = ...;

let service: Service.t(HttpRequest.t, HttpResponse.t) =
  auth |> andThen(authedService);

Conclusion

The system is described declaratively using data flow and data dependencies. The data flow resembles a pipeline of functions which is statically type checked. There aren't too many moving parts here. There are just three abstractions - futures, services and filters. Everything is a function, which is easy to reason about in isolation. Services, and filters especially makes it easy for you to write your own middleware.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment