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.

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:

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:

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:

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:

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).

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.

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.

  Document Search Using Cosine Similarity In Haskell Using Linear

Comments

comments powered by Disqus