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.
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
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.
First we’d like to separate the protocol from any particular server
implementation by defining a
Protocol module encapsulating the
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
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
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
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
corebuild which makes compiling the code much easier. Assuming your
source is named
$ corebuild tinycache.native -pkg core_extended
Full source as a gist.