## File: 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. --- ## File: 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 ``` --- ## File: 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).