Erlang libketama driver – Consistent Hashing

All the data I need from memcached is assigned to servers using a consistent hashing mechanism, implemented as libketama – a shared library written in C. We use a php extension to wrap this, and also have a pure java implementation. Rather than port the algorithm to Erlang, I wrote a an Erlang driver.

There are 3 things covered here:

  • A small driver program written in C (using libketama)
  • Some basic testing from the shell using Perl and xxd
  • The Erlang gen_server that calls it

C driver program

  1. /*  Expects a one-byte length header, followed by a key (<255bytes)
  2.  *  Returns an ip:port string with 1 byte len header
  3.  *
  4.  */
  5. #include <ketama.h>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <unistd.h>
  9. #include <string.h>
  10.  
  11. typedef unsigned char byte;
  12.  
  13. int read_exact(byte *buf, int len)
  14. {
  15.     int i, got = 0;
  16.     do {
  17.         if((i=read(0,buf+got, len-got))<=0) return i;
  18.         got += i;
  19.     } while(got<len);
  20.     return len;
  21. }
  22.  
  23. int main(int argc, char **argv)
  24. {
  25.     if(argc==1){
  26.         printf("Usage: %s <ketama.servers file>\n", *argv);
  27.         return 1;
  28.     }
  29.  
  30.     ketama_continuum c;
  31.     ketama_roll( &c, *++argv );
  32.     mcs *m;
  33.  
  34.     byte len;
  35.     byte buffer[256];
  36.     while ( 1 ) {
  37.         if( 1 != read_exact(&len, 1) ) break;
  38.         if( (int)len >= 255 ) break;
  39.         read_exact((byte *)&buffer, (int)len);
  40.         buffer[len] = ‘\0‘;
  41.         m = ketama_get_server( (char *) &buffer, c );
  42.         sprintf((char *)&buffer, "%s",m->ip);
  43.         int respleni = strlen(m->ip);
  44.         char l = (0xff & respleni);
  45.         write(1, &l, 1);
  46.         write(1, (char*)&buffer, respleni);
  47.     }
  48.  
  49.     return 0;
  50. }


Testing the driver with Perl and xxd

Before writing the Erlang bit, it’d be nice to know the driver program does what we expect.  Will send the driver a 1-byte length header followed by the key, and expect a 1-byte length header and the value as a response. Say we’re hashing a memcached key ‘user:123′ to a server, we can do what the Erlang port does with a bit of perl, and the ‘xxd’ command to see output in binary.

perl -e '$key="user:123"; $len=pack("C",length($key)); print $len; print $key;' | xxd -b

0000000: 00001000 01110101 01110011 01100101 01110010 00111010  .user:
0000006: 00110001 00110010 00110011                             123

Note the first byte (00001000) printed before the key is the length of the key, 8. Now let’s send this to the driver program and check the response (provide a valid ketama.servers file):

perl -e '$key="user:123"; $len=pack("C",length($key)); print $len; print $key;' | ./ketama_erlang_driver /var/ketama.servers | xxd -b

0000000: 00010000 00110001 00110000 00101110 00110000 00101110  .10.0.
0000006: 00110001 00101110 00110001 00110001 00111000 00111010  1.118:
000000c: 00110001 00110001 00110010 00110001 00110001           11211

The first byte of the response (00010000) is 16, which is the length of the server address returned by the driver, “10.0.1.118:11211″ – It does what we expect, onwards…

The Erlang bit

  1. -module(ketama).
  2. -behaviour(gen_server).
  3. -export([start_link/0, start_link/1, start_link/2, getserver/1]).
  4. -export([init/1, handle_call/3, handle_cast/2, handle_info/2,
  5.      terminate/2, code_change/3]).
  6.  
  7. -record(state, {port}).
  8.  
  9. start_link() ->
  10.     start_link("/web/site/GLOBAL/ketama.servers").
  11.  
  12. start_link(ServersFile) ->
  13.     start_link(ServersFile, "/usr/bin/ketama_erlang_driver").
  14.  
  15. start_link(ServersFile, BinPath) ->
  16.     gen_server:start_link({local, ?MODULE}, ?MODULE, [ServersFile, BinPath], []).
  17.  
  18. getserver(Key) ->
  19.     gen_server:call(?MODULE, {getserver, Key}).
  20.  
  21. %%
  22.  
  23. init([ServersFile, BinPath]) ->
  24.     Exe = BinPath ++ " " ++ ServersFile,
  25.     Port = open_port({spawn, Exe}, [binary, {packet, 1}, use_stdio]),
  26.     {ok, #state{port=Port}}.
  27.  
  28. handle_call({getserver, Key}, _From, #state{port=Port} = State) ->
  29.     Port ! {self(), {command, Key}},
  30.     receive
  31.         {Port, {data, Data}} ->
  32.             {reply, Data, State}
  33.         after 1000 -> % if it takes this long, you have serious issues.
  34.             {stop, ketama_port_timeout, State}
  35.     end.
  36.  
  37. handle_cast(_Msg, State) ->    {noreply, State}.
  38. handle_info({‘EXIT’, Port, Reason}, #state{port = Port} = State) ->
  39.     {stop, {port_terminated, Reason}, State}.
  40. terminate({port_terminated, _Reason}, _State) ->    ok;
  41. terminate(_Reason, #state{port = Port} = _State) ->     port_close(Port).
  42. code_change(_OldVsn, State, _Extra) ->     {ok, State}.



This code can be found in the erlang directory of the ketama source in svn:
svn://svn.audioscrobbler.net/misc/ketama/

Tags: , , , , ,

Sunday, September 28th, 2008 programming

9 Comments to Erlang libketama driver – Consistent Hashing

  1. [...] – Erlang libketama driver – Consistent Hashing saved by RaikoElric2008-09-26 – We are hashing again on Sunday July 27, 2008 saved by [...]

    2. Websites tagged "hashing" on Postsaver on October 7th, 2008

  2. [...] Erlang libketama driver – Consistent Hashing [...]

    3. A Million-user Comet Application with Mochiweb, Part 3 | Richard Jones, Esq. on November 4th, 2008

  3. [...] consistent hashing butters your muffin, check out libketama – a consistent hashing library and the Erlang libketama driver). Project-Voldemort handles replication and partitioning of data, and appears to be well written [...]

    4. Anti-RDBMS: A list of distributed key-value stores | Richard Jones, Esq. on January 19th, 2009

  4. [...] (看 这个 ，一个Erlang C驱动). [...]

    5. 用Mochiweb打造百万级Comet应用，第三部分 - IDISC的生活 on January 22nd, 2009

  5. [...] – посмотрите на библиотеку libketama включающую также драйвер для Erlang). Проект Voldemort поддерживает репликацию и [...]

    6. Перевод “Anti-RDBMS: A list of distributed key-value stores” « 13 попугаев on February 22nd, 2009

  6. [...] (看 这个 ，一个Erlang C驱动). [...]

    7. 用Mochiweb打造百万级Comet应用，第三部分（续2） | 静庵 on March 3rd, 2009

  7. [...] been tinkering around with linked-in drivers lately. There are several interesting projects using linked-in drivers so I thought I should learn how to write [...]

    8. Hypothetical Labs » Blog Archive » Simplest Linked-In Driver EVAH on March 24th, 2009

  8. Hello everyone!
    This morning I have found a very cool toon about the office workers everyday life.
    I recommend this for all to raise your mood.
    I helped))
    You can watch this toon <a href=http://www.youtube.com/watch?v=ZcmPOwpL9HI
    here

    Dont worry – be happy))

    9. ggstarling on June 18th, 2009

  9. [...] hashing butters your muffin, check out libketama – a consistent hashing library and the Erlang libketama driver). Project-Voldemort handles replication and partitioning of data, and appears to be well written [...]

    10. Anti-RDBMS: A list of distributed key-value stores | Weez.com on March 14th, 2010

Leave a comment

About Me

I'm Richard Jones, I live in London. I designed Audioscrobbler in 2002. I co-founded and was CTO of Last.fm for 6 years. I like programming. On Sundays I drink real ale and play Settlers of Catan in the pub.
 

Email: rj@metabrew.com

Search

 

Link Fodder