# Technical Documentation: facebook/Haxl

> ℹ️ **Provenance:** Multi-Tier Ingestion · [CodeWiki Reference](https://codewiki.google/github.com/facebook/Haxl)

### Overview (`readme.md`)

# Haxl

[](https://travis-ci.org/facebook/Haxl)

Haxl is a Haskell library that simplifies access to remote data, such
as databases or web-based services. Haxl can automatically

 * batch multiple requests to the same data source,
 * request data from multiple data sources concurrently,
 * cache previous requests,
 * memoize computations.

Having all this handled for you behind the scenes means that your
data-fetching code can be much cleaner and clearer than it would
otherwise be if it had to worry about optimizing data-fetching. We'll
give some examples of how this works in the pages linked below.

There are two Haskell packages here:

 * `haxl`: The core Haxl framework
 * `haxl-facebook` (in [https://github.com/facebook/Haxl/tree/master/example/facebook](example/facebook)): An (incomplete) example data source for accessing the Facebook Graph API

To use Haxl in your own application, you will likely need to build one or more
*data sources*: the thin layer between Haxl and the data that you want
to fetch, be it a database, a web API, a cloud service, or whatever.

There is a generic datasource in "Haxl.DataSource.ConcurrentIO" that
can be used for performing arbitrary IO operations concurrently, given
a bit of boilerplate to define the IO operations you want to perform.

The `haxl-facebook` package shows how we might build a Haxl data
source based on the existing `fb` package for talking to the Facebook
Graph API.

## Where to go next?

 * [The Story of Haxl](https://code.facebook.com/posts/302060973291128/open-sourcing-haxl-a-library-for-haskell/)
   explains how Haxl came about at Facebook, and discusses our
   particular use case.

 * [An example Facebook data source](https://github.com/facebook/Haxl/blob/master/example/facebook/readme.md) walks
   through building an example data source that queries the Facebook
   Graph API concurrently.

 * [Fun with Haxl (part 1)](https://simonmar.github.io/posts/2015-10-20-Fun-With-Haxl-1.html)
   Walks through using Haxl from scratch for a simple SQLite-backed
   blog engine.

 * [The N+1 Selects Problem](https://github.com/facebook/Haxl/blob/master/example/sql/readme.md) explains how Haxl
   can address a common performance problem with SQL queries by
   automatically batching multiple queries into a single query,
   without the programmer having to specify this behavior.

 * [Haxl Documentation](http://hackage.haskell.org/package/haxl) on
   Hackage.

 * [There is no Fork: An Abstraction for Efficient, Concurrent, and Concise Data Access](http://simonmar.github.io/bib/papers/haxl-icfp14.pdf), our paper on Haxl, accepted for publication at ICFP'14.

## Contributing

We welcome contributions! See [CONTRIBUTING](https://github.com/facebook/Haxl/blob/master/CONTRIBUTING.md) for details on how to get started, and our [Code of Conduct](https://github.com/facebook/Haxl/blob/master/CODE_OF_CONDUCT.md).

## License

Haxl uses the BSD 3-clause License, as found in the [LICENSE](https://github.com/facebook/Haxl/blob/master/LICENSE) file.

---

### Overview (`example/facebook/readme.md`)

# An example data source for accessing the Facebook Graph API

The [Facebook Graph
API](https://developers.facebook.com/docs/graph-api) allows
third-party applications to access Facebook data for users that have
explicitly indicated that they want the app to be able to access their
data.

We're going to build a Haxl data source for the Facebook Graph API, by
wrapping the existing [fb](http://hackage.haskell.org/package/fb)
package in a Haxl data source API.  Once we've done this, Haxl will
transparently

 * Perform multiple requests to the API concurrently,
   and concurrently with requests to other data sources.

 * Cache previous requests, so that different parts of our code can
   request the same data without having to worry about whether it gets
   fetched twice.

A data source consists of two parts:

 * The *data source API*, which allows the data source to be
   initialized.  In our example, this is the module [FB.DataSource](FB/DataSource.hs).

 * The *user API*, which exports a set of data-fetching functions in the `Haxl` monad.  In our example, this is the module [FB](FB.hs).

## The Data Source API: `FB.DataSource`

First, let's look at the data source API.  The most important part of
a data source is the set of requests that it supports.  A data source
must define its requests as a GADT:

```haskell
data FacebookReq a where
   GetObject      :: Id -> FacebookReq Object
   GetUser        :: UserId -> FacebookReq User
   GetUserFriends :: UserId -> FacebookReq [Friend]
  deriving Typeable
```

We have three requests: retrieve an arbitrary object, retrieve a user,
and retrieve a user's friends.  In reality there are a lot more request
types that we could add here, but these will suffice for the example.

Note that the `FacebookReq` type has a type parameter: this is the
result type of the request.  Each of our requests instantiates this by
the appropriate return type: `Object` for `GetObject`, `User` for
`GetUser`, and `[Friend]` for `GetUserFriends`.

There is some necessary boilerplate that goes along with a data source:

```haskell
deriving instance Eq (FacebookReq a)
deriving instance Show (FacebookReq a)

instance ShowP FacebookReq where showp = show

instance Hashable (FacebookReq a) where
  hashWithSalt s (GetObject (Id id))      = hashWithSalt s (0::Int,id)
  hashWithSalt s (GetUser (Id id))        = hashWithSalt s (1::Int,id)
  hashWithSalt s (GetUserFriends (Id id)) = hashWithSalt s (2::Int,id)
```

Requests are required to be instances of various classes, so that the
Haxl framework can store them in a cache, and print them out.

Next, a data source can have associated state.  Haxl keeps track of
each data source's state, and provides the state when data needs to be
fetched, as we'll see in a moment.  The state for a data source is
defined by giving an instance of the `StateKey` class:

```haskell
instance StateKey FacebookReq where
  data State FacebookReq =
    FacebookState
       { credentials :: Credentials
       , userAccessToken :: UserAccessToken
       , manager :: Manager
       , semaphore :: QSem
       }
```

The `StateKey` class has an associated data type `State`,
parameterised by the request type (here `FacebookReq`).  For the
Facebook data source, we need several things:

 * The app credentials and an access token.  These are the keys
   required to access the Facebook API, and will be passed in when we
   initialize the data source.

 * The `Manager`; this comes from `Network.HTTP.Client`, and it
   maintains a set of open connections to `HTTP` servers.

 * `semaphore`, which will be used to limit the number of concurrent
   requests we make to the Facebook API.

A data source should provide a way to initialize its state.  To
initialize our data source we need to create a new `Manager`, and
store the credentials and other info in the `FacebookState` record:

```haskell
initGlobalState
  :: Int
  -> Credentials
  -> UserAccessToken
  -> IO (State FacebookReq)

initGlobalState threads creds token = do
  manager <- newManager tlsManagerSettings
  sem <- newQSem threads
  return FacebookState
    { credentials = creds
    , manager = manager
    , userAccessToken = token
    , semaphore = sem
    }
```

Next, we give instances for the `DataSourceName` and `DataSource` classes:

```haskell
instance DataSourceName FacebookReq where
  dataSourceName _ = "Facebook"

instance DataSource u FacebookReq where
  fetch = facebookFetch
```

There are two methods:

 * `dataSourceName` is used by the framework to identify this data
   source when producing statistics about fetches, for example.

 * `fetch` is the operation for fetching data, which we'll implement
   next.

The `fetch` implementation has this type:

```haskell
facebookFetch
  :: State FacebookReq
  -> Flags
  -> u
  -> PerformFetch FacebookReq
```

That is, it takes the current state for this data source, some `Flags`
defined by Haxl, a "user state" (in our case we won't need any user
state, so this is `()`), and returns a value of type `PerformFetch`
which will tell Haxl how to fetch requests for this datasource.

We're going to fetch these requests concurrently.  We'll use the
[async](http://hackage.haskell.org/package/async) package together
with a `QSem` to control the degree of concurrency.

The fetch function returns a value of type `PerformFetch`, defined like this:

```haskell
data PerformFetch
  = SyncFetch  ([BlockedFetch req] -> IO ())
  | AsyncFetch ([BlockedFetch req] -> IO () -> IO ())
  | BackgroundFetch ([BlockedFetch req] -> IO ())
```

A data source can fetch either synchronously (`SyncFetch`),
asynchronously (`AsyncFetch`), or in the background
(`BackgroundFetch`).  The `BackgroundFetch` option is the most
flexible because it allows fetching to proceed concurrently with
computation.

The argument to `Background` is a function that takes the list of
`BlockedRequest`s, and should return immediately while the requests
are performed in the background.

```haskell
facebookFetch FacebookState{..} _flags _user =
  BackgroundFetch $
    mapM_ (fetchAsync credentials manager userAccessToken semaphore)
```

Issuing each request is done by `fetchAsync`:

```haskell
fetchAsync
  :: Credentials -> Manager -> UserAccessToken -> QSem
  -> BlockedFetch FacebookReq
  -> IO ()
fetchAsync creds manager tok sem (BlockedFetch req rvar) =
  void $ async $ bracket_ (waitQSem sem) (signalQSem sem) $ do
    e <- Control.Exception.try $
           runResourceT $ runFacebookT creds manager $ fetchFBReq tok req
    case e of
      Left ex -> putFailure rvar (ex :: SomeException)
      Right a -> putSuccess rvar a
```

This function does several things:

 * it does everything in `async`, which performs the operation
   asynchronously and returns a handle that can be waited on later (we
   ignore the returned handle here).

 * it obtains a token from the `QSem`, which is used to control the
   degree of concurrency,

 * it performs the fetch inside a `try`, which catches exceptions.
   This is very important: a data source should never throw
   exceptions, instead it should store the exception inside the
   `ResultVar` (here bound to `rvar`) using `putFailure`.  This
   exception will then be propagated by the Haxl framework to the
   computation that initiated the fetch.

 * it calls `fetchFBReq` to perform the actual fetch.

`fetchFBReq` is the application-specific code to fetch data from
Facebook.  Here is where we would add support for more types of
request:

```haskell
fetchFBReq
  :: UserAccessToken
  -> FacebookReq a
  -> FacebookT Auth (ResourceT IO) a

fetchFBReq tok (GetObject (Id id)) =
  getObject ("/" <> id) [] (Just tok)

fetchFBReq _tok (GetUser id) =
  getUser id [] Nothing

fetchFBReq tok (GetUserFriends id) = do
  f <- getUserFriends id [] tok
  source <- fetchAllNextPages f
  source $$ consume
```

## The User API: `FB`

The job of the user API is to wrap the request type in some nice
functions that we can call from the `Haxl` monad.  Each function is a
call to Haxl's `dataFetch` operation, passing the appropriate request:

```haskell
module FB
  ( getObject
  , getUser
  , getUserFriends
  , Id(..), Friend(..), User(..)
  ) where

import FB.DataSource
import Data.Aeson
import Facebook (Id(..), Friend(..), User(..))

import Haxl.Core

getObject :: Id -> GenHaxl u w Object
getObject id = dataFetch (GetObject id)

getUser :: Id -> GenHaxl u w User
getUser id = dataFetch (GetUser id)

getUserFriends :: Id -> GenHaxl u w [Friend]
getUserFriends id = dataFetch (GetUserFriends id)
```

And that's it.  The whole data source is less than 150 lines, with a lot
of it being standard boilerplate that most data sources need.

Most users of Haxl will want to define a `Haxl` type instantiating the
`GenHaxl` type, something like this:

```haskell
type Haxl a = GenHaxl () a
```

The point of the `GenHaxl` type is that you can pass some
application-specific data through the computation and to the data
sources by instantiating the first paramter (here just `()`) with your
own type.

In the file [TestFB.hs](./TestFB.hs) you can find a simple example
program that uses this data source.  The `main` function looks like this:

```haskell
main :: IO ()
main = do
  (creds, access_token) <- getCredentials
  facebookState <- initGlobalState 10 creds access_token
  env <- initEnv (stateSet facebookState stateEmpty) ()
  r <- runHaxl env $ do
    likes <- getObject "me/likes"
    mapM getObject (likeIds likes) -- these happen concurrently
  print r
```

Once we have some credentials (obtained from the environment), we
initialize the Facebook data source with a maximum of 10 threads, and
then call `initEnv` to initialize Haxl's `Env`: think of this as the
container for Haxl's cache, amongst other things.  Each time we create
an `Env` with `initEnv`, it has an empty cache.

Then we call `runHaxl`, passing the `Env`.  Inside `runHaxl` we do two
fetches: first `getObject "me/likes"` which fetches the set of pages
liked by the user identified by the access token.  Then, we fetch the
objects associated with each of those pages.  This will result in two
round of fetches: one fetch in the first round, and then *N* fetches
in the second round, where *N* is the number of pages we need to
fetch.  The fetches in the second round will be performed
concurrently, using at most 10 threads. Note that the `mapM` function is
imported from [`Haxl.Prelude`](http://hackage.haskell.org/package/haxl-0.1.0.0/docs/Haxl-Prelude.html).

---

### Overview (`example/sql/readme.md`)

# Solving the "N+1 Selects Problem" with Haxl

The so-called “[N+1 selects problem](http://ocharles.org.uk/blog/posts/2014-03-24-queries-in-loops-without-a-care-in-the-world.html)” is characterized by a set of queries in a loop. To ape the example from Ollie Charles:

```haskell
getAllUsernames = do
  userIds <- getAllUserIds
  for userIds $ \userId -> do
    getUsernameById userId
```

The `IO` version of this code would perform one data fetch for `getAllUserIds`, then another for each call to `getUsernameById`; assuming each one is implemented with something like the SQL `select` statement, that means “N+1 selects”.

But Haxl does not suffer from this problem. Using *this very code*, the Haxl implementation will perform *exactly two* data fetches: one to `getAllUserIds` and one with all the `getUsernameById` calls batched together.

First, a dash of boilerplate:

```haskell
{-# LANGUAGE DeriveDataTypeable,
             GADTs,
             MultiParamTypeClasses,
             StandaloneDeriving,
             TypeFamilies #-}

import Data.Typeable
import Haxl.Core
```

## The Request Type

First we make a data type with a constructor for each type of request.

```haskell
data UserReq a where
  GetAllIds   :: UserReq [Id]
  GetNameById :: Id -> UserReq Name
  deriving (Typeable)

type Id = Int
type Name = String

deriving instance Eq (UserReq a)
instance Hashable (UserReq a) where
   hashWithSalt s GetAllIds       = hashWithSalt s (0::Int)
   hashWithSalt s (GetNameById a) = hashWithSalt s (1::Int, a)

deriving instance Show (UserReq a)
instance ShowP UserReq where showp = show
```

This type is parameterized so that each request can indicate which type of result it returns. It is `Typeable` so that Haxl can safely store requests to multiple data sources at once, as well as `Eq` and `Hashable` for caching and `Show` for debug output.

## Making a Data Source from a Request Type

Now we make this an instance of Haxl’s `StateKey` and `DataSource` classes. `StateKey` lets us associate a data source with its global state, to be initialized once. (We won’t take advantage of this here.)

```haskell
instance StateKey UserReq where
  data State UserReq = UserState {}
```

Every data source needs to tell Haxl its name, by giving an instance for
the `DataSourceName` class:

```haskell
instance DataSourceName UserReq where
  dataSourceName _ = "UserDataSource"
```

Next, `DataSource` lets us specify how a set of blocked requests are to be fetched. It is parameterized by the type of a *user environment* of cross–data source global data, as well as a request type that is an instance of `StateKey`. It is defined as follows:

```haskell
class (DataSourceName, StateKey req, ShowP req) => DataSource u req where
  fetch
    :: State req           -- Data source state.
    -> Flags               -- Flags, containing tracing verbosity level, etc.
    -> u                   -- User environment for cross–data source globals.
    -> [BlockedFetch req]  -- Set of blocked fetches to perform.
    -> PerformFetch        -- An action to perform the fetching.
```

We are mainly concerned with implementing the `fetch` method, and in this case we can ignore many of its parameters, which are to support more complex data sources than ours. The key point is that Haxl gives us a list of *all* the requests that are currently waiting to be fetched, which means we can batch them together however we please.

Taking a look at the definition of `BlockedFetch` informs us how to implement the `fetch` method:

```haskell
data BlockedFetch r = forall a. BlockedFetch (r a) (ResultVar a)
type ResultVar a = MVar (Either SomeException a)
```

Here we have that a `BlockedFetch` consists of a pair of a request (of type `r a`) and a `MVar` containing `Either SomeException` (if fetching failed) or the result of the request. The role of `fetch` is to fill these `MVar`s.

## Implementing the `fetch` Method

Now, a data source can fetch data in one of two ways:

  * **Synchronously:** the fetching operation is an `IO ()` that fetches all the
    data and then returns.

  * **Asynchronously:** we can do something else while the data is being
    fetched. The fetching operation takes an `IO ()` as an argument, which is
    the operation to perform while the data is being fetched.

These are represented by the constructors of the `PerformFetch` type that `fetch` returns:

```haskell
data PerformFetch
  = SyncFetch  (IO ())
  | AsyncFetch (IO () -> IO ())
```

We will use `SyncFetch` here for simplicity. (Haxl also includes `syncFetch` and `asyncFetch` helper functions for implementing common `fetch` patterns.) Now, in the implementation of `fetch`, assuming we have some function `sql` for running SQL queries, we can do something like this:

```haskell
-- We have no user environment, so we use ().
type Haxl = GenHaxl ()

instance DataSource u UserReq where
  fetch _state _flags _userEnv blockedFetches = SyncFetch $ do

    unless (null allIdVars) $ do
      allIds <- sql "select id from ids"
      mapM_ (\r -> putSuccess r allIds) allIdVars

    unless (null ids) $ do
      names <- sql $ unwords
        [ "select name from names where"
        , intercalate " or " $ map ("id = " ++) idStrings
        , "order by find_in_set(id, '" ++ intercalate "," idStrings ++ "')"
        ]
      mapM_ (uncurry putSuccess) (zip vars names)

    where
    allIdVars :: [ResultVar [Id]]
    allIdVars = [r | BlockedFetch GetAllIds r <- blockedFetches]

    idStrings :: [String]
    idStrings = map show ids

    ids :: [Id]
    vars :: [ResultVar Name]
    (ids, vars) = unzip
      [(userId, r) | BlockedFetch (GetNameById userId) r <- blockedFetches]
```

## Tying it All Together

All that remains to make the original example work is to define `getAllUserIds` and `getUserById` using Haxl’s `dataFetch` function.

```haskell
getAllUserIds :: Haxl [Id]
getAllUserIds = dataFetch GetAllIds

getUsernameById :: Id -> Haxl Name
getUsernameById userId = dataFetch (GetNameById userId)
```

`dataFetch` simply takes a request to a data source and returns a
`GenHaxl` action to fetch it concurrently with others.

```haskell
dataFetch :: (DataSource u r, Request r a) => r a -> GenHaxl u w a
```

Like magic, the naïve code that *looks* like it will do N+1 fetches will now do just two.

```haskell
getAllUsernames :: Haxl [Name]
getAllUsernames = do
  userIds <- getAllUserIds       -- Round 1
  for userIds $ \userId -> do    -- Round 2
    getUsernameById userId
```

The only change is that its type signature is now `Haxl` instead of `IO`, and at the top level we have to place a call to `runHaxl`:

```haskell
main :: IO ()
main = do

  -- Initialize Haxl state.
  let stateStore = stateSet UserState{} stateEmpty

  -- Initialize Haxl environment.
  env0 <- initEnv stateStore ()

  -- Run action.
  names <- runHaxl env0 getAllUsernames

  print names
```

---

--- METRICS ---
- Files Extracted: 3
- Estimated Token Budget: ~5130 tokens
- Canonical Reference: https://codewiki.google/github.com/facebook/Haxl