User functions in Arakoon
Posted: February 1, 2013 Filed under: Arakoon, Baardskeerder, OCaml, Programming, Uncategorized | Tags: arakoon, baardskeerder, key value store, OCaml, user functions 1 CommentMahomet cald the Hill to come to him. And when the Hill stood still, he was neuer a whit abashed, but said;
If the Hill will not come to Mahomet, Mahomet wil go to the hill.
Francis Bacon
Introduction
Arakoon tries to be a simple distributed key value store that favours consistency over availability.
From time to time, we get feature requests for additional commands like:
- assert_exists: assert a value exists for the key without caring what the value actually is
- increment_counter: increment (or create) a counter and return the new value.
- queue operations : add an element to the front/back of a double ended queue or pop an element
- set_and_update_X: insert a key value pair and update some non-trivial counter X (think averages, variances,…)
- …
The list is semi-infinite and the common thing here is that they are too complex/specific/weird/… to do them in one step using the provided interface. Of course, you can do all of this on the client side, but it will cost extra network round-trips. In distributed systems, you really want to keep the number of round-trips low, which pushes you towards these kind of feature requests.
Once you decided (performance bottlenecks probably) that you need extra functionality there are two things you can do. First, you can try to force or entice us into adding them to the core interface or alternatively, you can get by using Arakoon’s “user functions”. For some reason people fear them but there’s no real technical reason to do so.
This blog post will cover two things. First we’ll go in to the nitty gritty of coding and deploying user functions and then we’ll look at some of the strategic/architectural challenges of user functions.
How do user functions work?
The high level view is this: you build a user function, and register it to an Arakoon cluster before you start it. Then, at runtime, you can call it, using any client, with a parameter (a string option) and get back a result (string option). On the server side, the master will log this in its transaction log, try to reach consensus with the slave(s) and once that is the case, the user function will be executed inside a transaction. The result of that call will be sent to the client. If an exception occurs, the transaction will be aborted. Since Arakoon logs transactions it can replay them in case of calamities. This has a very important impact: since Arakoon needs to be able to replay the execution of a user function, you cannot do side effects, use random values or read the system clock.
Running Example
We’re going to try to build a simple queue API.
It will offer named queues with 2 operations: push and pop. Also, it’s a first-in-first-out thingy.
Arakoon 1
Client side API
Arakoon 1 offers the following API for user functions.
def userFunction(self, name, argument): '''Call a user-defined function on the server @param name: Name of user function @type name: string @param argument: Optional function argument @type argument: string option @return: Function result @rtype: string option '''
Let’s take a look at it. A userFunction call needs the name, which is a string, and an argument which is a string option and returns a result of type string option. So what exactly is a string option in Python? Well, it’s either a string or None. This allows a user function to not take input or to not yield a result.
Server side API
The server side API is in OCaml, and looks like this:
class type user_db = object method set : string -> string -> unit method get : string -> string method delete: string -> unit method test_and_set: string -> string option -> string option -> string option method range_entries: string option -> bool -> string option -> bool -> int -> (string * string) list end
User functions on server side match the client’s opaque signature.
user_db -> string option -> string option
Queue’s client side
Let’s create the client side in python. We’ll create a class that uses an Arakoon client and acts as a queue. The problem with push is that we need to fit both the name and the value into the one paramater we have available. We need to do our own serialization. Let’s just be lazy (smart?) and use Arakoon’s serialization. The code is shown below.
from arakoon import Arakoon
from arakoon import ArakoonProtocol as P
class ArakoonQueue:
def __init__(self, name, client):
self._name = name
self._client = client
def push(self, value):
input = P._packString(self._name)
input += P._packString(value)
self._client.userFunction("QDemo.push", input)
def pop(self):
value = self._client.userFunction("QDemo.pop", self._name)
return value
That wasn’t too hard now was it?
Queue, server side
The whole idea is that the operations happen on server side, so this will be a tat more complex.
We need to model a queue using a key value store. Code-wise, that’s not too difficult.
For each queue, we’ll keep 2 counters that keep track of both ends of the queue.
A push is merely getting the qname and the value out of the input, calculating the place where we need to store it, store the value there and update the counter for the back end of the queue. A pop is similar but when the queue becomes empty, we use the opportunity to reset the counters (maybe_reset_counters). The counter representation is a bit weird but Arakoon stores things in lexicographical order and we want to take advantage of this to keep our queue fifo. Hence, we need to make the counter in such a way the counter’s order is the same as a string’s order. The code is shown below.
(* file: plugin_qdemo.ml *)
open Registry
let zero = ""
let begin_name qname = qname ^ "/@begin"
let end_name qname = qname ^ "/@end"
let qprefix qname key = qname ^ "/" ^ key
let next_counter = function
| "" -> "A"
| s ->
begin
let length = String.length s in
let last = length - 1 in
let c = s.[last] in
if c = 'H'
then s ^ "A"
else let () = s.[last] <- Char.chr(Char.code c + 1) in
s
end
let log x=
let k s = let s' = "[plugin_qdemo]:" ^ s in
Lwt.ignore_result (Lwt_log.debug s')
in
Printf.ksprintf k x
let maybe_reset_counters user_db qname b1 =
let e_key = end_name qname in
let exists =
try let _ = user_db # get e_key in true with Not_found -> false
in
if exists
then
let ev = user_db # get e_key in
if ev = b1 then
let b_key = begin_name qname in
let () = user_db # set b_key zero in
let () = user_db # set e_key zero in
()
else
()
else ()
let push user_db vo =
match vo with
| None -> invalid_arg "push None"
| Some v ->
let qname, p1 = Llio.string_from v 0 in
let value, _ = Llio.string_from v p1 in
let e_key = end_name qname in
let b0 =
try user_db # get (end_name qname)
with Not_found -> zero
in
let b1 = next_counter b0 in
let () = user_db # set (qprefix qname b1) value in
let () = user_db # set e_key b1 in
None
let pop user_db vo =
match vo with
| None -> invalid_arg "pop None"
| Some qname ->
let b_key = begin_name qname in
let b0 =
try user_db # get (begin_name qname)
with Not_found -> zero
in
let b1 = next_counter b0 in
try
let k = qprefix qname b1 in
let v = user_db # get k in
let () = user_db # set b_key b1 in
let () = user_db # delete k in
let () = maybe_reset_counters user_db qname b1 in
Some v
with
Not_found ->
let e_key = end_name qname in
let () = user_db # set b_key zero in
let () = user_db # set e_key zero in
None
let () = Registry.register "QDemo.push" push
let () = Registry.register "QDemo.pop" pop
The last two lines register the functions to the Arakoon cluster when the module is loaded.
Compilation
So how do you deploy your user function module into an Arakoon cluster?
First need to compile your module into something that can be dynamically loaded.
To compile the plugin_qdemo.ml I persuade ocamlbuild like this:
ocamlbuild -use-ocamlfind -tag 'package(arakoon_client)' \ -cflag -thread -lflag -thread \ plugin_qdemo.cmxs
It’s not too difficult to write your own testcase for your functionality, so you can run it outside of Arakoon and concentrate on getting the code right.
Deployment
First, you need put your compilation unit into the Arakoon home directory on all your nodes of the cluster. And second, you need to add the name to the global section of your cluster configuration. Below, I show the configuration file for my simple, single node cluster called ricky.
[global] cluster = arakoon_0 cluster_id = ricky ### THIS REGISTERS THE USER FUNCTION: plugins = plugin_qdemo [arakoon_0] ip = 127.0.0.1 client_port = 4000 messaging_port = 4010 home = /tmp/arakoon/arakoon_0
All right, that’s it. Just a big warning about user functions here.
Once a user function is installed, it needs to remain available, with the same functionality for as long as user function calls are stored inside the transaction logs, as they need to be re-evaluated when one replays a transaction log to a store (for example when a node crashed, leaving a corrupt database behind). It’s not a bad idea to include a version in the name of a user function to cater for evolution.
Demo
Let’s use it in a simple python script.
def make_client():
clusterId = 'ricky'
config = Arakoon.ArakoonClientConfig(clusterId,
{"arakoon_0":("127.0.0.1", 4000)})
client = Arakoon.ArakoonClient(config)
return client
if __name__ == '__main__':
client = make_client()
q = ArakoonQueue("qdemo", client)
q.push("bla bla bla")
q.push("some more bla")
q.push("3")
q.push("4")
q.push("5")
print q.pop()
print q.pop()
print q.pop()
print q.pop()
with expected results.
Arakoon 2
With Arakoon 2 we moved to Baardskeerder as a database backend, replacing the combination of transaction logs and Tokyo Cabinet. Since the backend is Lwt-aware, this means that the server side API has become too:
module UserDB : sig type tx = Core.BS.tx type k = string type v = string val set : tx -> k -> v -> unit Lwt.t val get : tx -> k -> (v, k) Baardskeerder.result Lwt.t val delete : tx -> k -> (unit, Baardskeerder.k) Baardskeerder.result Lwt.t end module Registry: sig type f = UserDB.tx -> string option -> (string option) Lwt.t val register: string -> f -> unit val lookup: string -> f end
The major changes are that
- the api now uses Lwt
- we have (‘a,’b) Baardskeerder.result types, which we favour over the use of exceptions for normal cases.
Rewriting the queue implementation to Arakoon 2 yields something like:
(* file: plugin_qdemo2.ml *)
open Userdb
open Lwt
open Baardskeerder
let zero = ""
let begin_name qname = qname ^ "/@begin"
let end_name qname = qname ^ "/@end"
let qprefix qname key = qname ^ "/" ^ key
let next_counter = function
| "" -> "A"
| s ->
begin
let length = String.length s in
let last = length - 1 in
let c = s.[last] in
if c = 'H'
then s ^ "A"
else let () = s.[last] <- Char.chr(Char.code c + 1) in
s
end
let reset_counters tx qname =
let b_key = begin_name qname in
let e_key = end_name qname in
UserDB.set tx b_key zero >>= fun () ->
UserDB.set tx e_key zero
let maybe_reset_counters tx qname (b1:string) =
let e_key = end_name qname in
begin
UserDB.get tx e_key >>= function
| OK _ -> Lwt.return true
| NOK _ -> Lwt.return false
end >>= function
| true ->
begin
UserDB.get tx e_key >>= function
| OK ev ->
if ev = b1
then reset_counters tx qname
else Lwt.return ()
| NOK _ -> Lwt.return ()
end
| false -> Lwt.return ()
let push tx vo =
match vo with
| None -> Lwt.fail (invalid_arg "push None")
| Some v ->
let qname, p1 = Llio.string_from v 0 in
let value, _ = Llio.string_from v p1 in
Lwt_log.debug_f "push:qname=%S;value=%S" qname value >>= fun ()->
let e_key = end_name qname in
UserDB.get tx (end_name qname) >>= fun b0r ->
let b0 = match b0r with
| OK b0 -> b0
| _ -> zero
in
let b1 = next_counter b0 in
UserDB.set tx (qprefix qname b1) value >>= fun () ->
UserDB.set tx e_key b1 >>= fun () ->
Lwt.return None
let pop tx = function
| None -> Lwt.fail (invalid_arg "pop None")
| Some qname ->
begin
let b_key = begin_name qname in
UserDB.get tx (begin_name qname) >>= fun b0r ->
begin
match b0r with
| OK b0 -> Lwt.return b0
| NOK _ -> Lwt.return zero
end
>>= fun b0 ->
let b1 = next_counter b0 in
let k = qprefix qname b1 in
UserDB.get tx k >>= fun vr ->
begin
match vr with
| OK value ->
begin
UserDB.set tx b_key b1 >>= fun () ->
UserDB.delete tx k >>= function
| OK () ->
begin
maybe_reset_counters tx qname b1 >>= fun () ->
Lwt.return (Some value)
end
| NOK e -> Lwt.fail (Failure e)
end
| NOK _ ->
reset_counters tx qname >>= fun () ->
Lwt.return None
end
end
let () = Userdb.Registry.register "QDemo.push" push
let () = Userdb.Registry.register "QDemo.pop" pop
Both client side and deployment remain the same.
Questions asked
Ain’t there something wrong with this Queue?
Yes! Glad you noticed. This queue concept is fundamentally broken. The problem is the pop.
Follow this scenario:
- the client calls the QDemo.pop function
- the cluster pops the value from the queue and its master sends it to the client.
- the client dies before it can read the popped value
Now what? We’ve lost that value. Bloody network, how dare you!
Ok, I admit this was naughty, but it’s a good example of a simple local concept that doesn’t really amount to the same thing when tried in a distributed context. When confronted with this hole, people immediately try to fix this with “Right!, so we need an extra call to …”. To which I note: “But wasn’t this extra call just the thing you were trying to avoid in the first place?”
Why don’t you allow user functions to be written in <INSERT YOUR FAVOURITE LANGUAGE HERE>?
This is a good question, and there are several answers, most of them wrong. For example, anything along the lines of “I don’t like your stinkin’ language” needs to be rejected because a language’s cuteness is irrelevant.
There are several difficulties with the idea of offering user functions to be written in another programming language. For scripting languages like Python, Lua, PHP ,… we can either implement our own interpreter and offer a subset of the language, which is a lot of work with low return on investment, or integrate an existing interpreter/runtime which will probably not play nice with Lwt, or with the OCaml runtime (garbage collector). For compiled languages we might go via the ffi but it’s still way more complex for us. So for now you’re stuck with OCaml for user functions. There are worse languages.
Wouldn’t it be better if you apply the result of the user function to the transaction log iso the arguments?
Well, we’ve been thinking about that a lot before we started with user functions. The alternative is that we record and log the effect of the user function so that we can always replay that effect later, even when the code is no longer available. It’s an intriguing alternative, but it’s not a clear improvement. It all depends on the size of the arguments versus the size of the effect.
Some user functions have a small argument set and a big effect, while for other user functions it’s the other way around.
Closing words
Technically, it’s not too difficult to hook in your own functionality into Arakoon. Just make sure the thing you want to hook in does not have major flaws.
have fun,
Romain.
Incubaid Research 