.. post:: 2013-12-10
   :tags: OCaml, Async, Core
   :author: Rudi Grinberg

Lru Cache With a Memcache-Like Interface
========================================

Lately, I've been messing around with Janestreet's core and async
libraries by reimplementing an old interview question that has been
posed to me before. The problem statement itself is from my memory alone
so this isn't 100% what I've been asked but it should be extremely
close.

Problem
-------

Implement a simple memcache like TCP interface to an Lru cache. All
commands in the server are of the form:

::

    QUIT\r\n
    GET key\r\n
    SET key value\r\n

where ``key``, ``value`` must not contain spaces.

Responses are of the form:

::

    INSERTED\r\n
    OK\r\nvalue\r\n
    NOT_FOUND\r\n

It should be obvious enough to see the request-response correspondence.

Solution
--------

First we'd like to separate the protocol from any particular server
implementation by defining a ``Protocol`` module encapsulating the
definitions above.

.. code-block:: ocaml

    module Protocol = struct
      module Client_message = struct
        type t =
          | Get of string
          | Set of string * string
          | Quit with sexp
        let of_string s =
          Option.try_with @@ fun () ->
            match String.split ~on:' ' s with
            | "QUIT"::[] -> Quit
            | "GET"::k::[] -> Get k
            | "SET"::k::v::[] -> Set (k,v)
            | _ -> failwith "bad command"
      end
      module Server_message = struct
        type t =
          | Ok of string
          | Inserted
          | Not_found with sexp
        let to_string = function
          | Inserted -> "INSERTED\r\n"
          | Ok m -> "OK\r\n" ^ m ^ "\r\n"
          | Not_found -> "NOT_FOUND\r\n"
      end
    end

the particular of the cache itself is immaterial so there's no reason
why our server should depend on it. The only real restrictions we'd like
to have is that the cache must have have a bounded number of elements so
that our server doesn't run out of memory (Note that to achieve this
we'd need restrict the size of the keys and values as well but we'll
skip it). We could functorize our server over the protocol as well if we
include quitting as a return type for ``of_string`` for example. The
following interface is satisfactory:

.. code-block:: ocaml

    module type BoundedCache = sig
      type t
      val create : size:int -> t
      val get : t -> key:string -> string option
      val set : t -> key:string -> data:string -> unit
    end

The ``Cache.Lru`` module in the ``core_extended`` package does not quite
fit our interface but can be very simply adapted with:

.. code-block:: ocaml

    module Lru = struct
      module L = Cache.Lru
      type t = (string, string) L.t
      let create ~size = L.create None size
      let get t ~key = L.find t key
      let set = L.add
    end

Of course, I'm aware that original intent of the interview question was
not to test how well you put together ready made lego blocks to solve
the problem but more of designing the data structure for the Lru cache.
The aim of this blogpost is more to show how well the lego blocks in
core/async fit together.

Finally we can start writing our Cache server module functorized over
the cache signature. We will start with the function ``process`` which
simply processes a request into a response in the context of the
server's state - the cache in our case. We'd expect a type signature
such as:

.. code-block:: ocaml

    module P = Protocol
    val process : Cache.t -> P.Client_message.t -> P.Server_message.t

Functions of this sort are very concisely expressed with OCaml's pattern
matching:

.. code-block:: ocaml

    module CacheServer (Cache : BoundedCache) = struct
      open Protocol
      let process t req =
        let open Client_message in
        match req with
        | Get key ->
          Server_message.(match Cache.get t ~key with
              | None -> Not_found
              | Some x -> Ok x)
        | Set (key, data) ->
          Cache.set t ~key ~data;
          Server_message.Inserted
        | Quit -> assert false
    end

The server runs by simply binding to an address and passing input to the
function above in the main loop. The only special handling we need is
for the quit message and bad input (which we just ignore).

.. code-block:: ocaml

    let run_server ~host ~port ~size =
        let cache = Cache.create ~size in
        Tcp.Server.create (Tcp.on_port port) @@ fun _ reader writer ->
          Deferred.create (fun finished ->
              let rec loop () =
                Reader.read_line reader >>> function
                | `Ok query ->
                  (match Client_message.of_string query with
                   | None -> loop ()
                   | Some Client_message.Quit -> Ivar.fill finished ()
                   | Some req ->
                     let resp = process cache req in
                     resp |> Server_message.to_string |> Writer.write writer;
                     loop ())
                | `Eof -> Ivar.fill finished ()
              in loop ())

Finally, to run the server we must instantiate our functor and run the
async scheduler.

.. code-block:: ocaml

    let server =
      let module CS = CacheServer(Lru) in
      CS.run_server ~host:"127.0.0.1" ~port:12345 ~size:100

    let () = Scheduler.go () |> never_returns

Later versions of core include a wrapper around ``ocamlbuild`` called
``corebuild`` which makes compiling the code much easier. Assuming your
source is named ``tinycache.ml``

::

    $ corebuild tinycache.native -pkg core_extended

Full source as a `gist <https://gist.github.com/rgrinberg/5733256>`__.