Today's Question:  What does your personal desk look like?        GIVE A SHOUT

In-memory key-value store in C, Go and Python

  graham        2012-03-21 09:21:51       4,404        0    

Subtitle: Wow Go’s net library is fast

On paternity leave for my second child, I found myself writing an in-memory hashmap (a poor-man’s memcached), in Go, Python and C. I was wondering how hard it would be to replace memcached, if we wanted to do something unusual with our key-value store. I also wanted to compare the languages, and, well, I get bored easily!

The code is on github as Key-Value-Polyglot.

Each version implements enough of the get and set commands from the memcached protocol that we can test them with a memcached client.

If you write a version in a different language (see Spec at bottom), please send it to me, either directly or as a pull-request on github. I’ll add it to the repo.

Performance

The C and Python versions perform similarly. They are spending all their time in the recv system call.

The Go version is many times faster than the C and Python version. It is the same speed as memcached. Internally, Go sets the socket to be non-blocking and uses epoll and futex to wait for data. Memcached does the same thing, via libevent.

The wonderful part is I had no idea Go did this. I wrote each version as simply as I could, and the Go version just turned out amazingly fast. You could definitely use epoll in C and Python, and get the same speed as the Go version. What I enjoyed is that Go did that for me.

To time the different versions on your machine run: time python test.py. That script requires python 2 and pylibmc (pip install pylibmc or sudo apt-get install python-pylibmc).

Try test.py against memcached too.

Writing it

The socket part was easy. Our languages are wrapping POSIX socket system calls. C maps the calls exactly, and Python maps the C calls very closely. Go does a bit more work for us, replacing socket-bind-listen-accept with just listen-accept.

Accepting multiple concurrent requests was straighforward too. Go has the magic go statement, Python has the threading library, and C has pthread_create. None of my implementations are thread safe (thanks timtadh on HN).

The tricky part is managing the data you get from the socket. Sockets are just streams of data, it’s up to the protocol to say when a message starts and ends. For the memcached protocol, we need to be able to read until \r\n, and also read a specific amount of bytes (which might include \r\n).

Go makes that easy, with the bufio package. Python makes it easy too, once you figure out you can turn a socket into a file via socket.makefile. In C you’re on your own.

The C version took the longest to write, and is the least legible. Partly that is because my C was rusty, partly C is just quite verbose, but the biggest part is because I had to implement buffering around the socket ‘recv’ call.

The Python version took me a while to get right, and that’s mostly my fault. I knew Python wouldn’t make me write my own buffering code, and I spent too long playing with timeout and non-blocking setups. Once I realized I could treat the socket as a file (‘makefile’) things got easier.

Python 3′s universal newline support kindly normalizes \r\n to \n, but we’re disabling it here to preserve python 2 compatibility.

The Go version was the easiest to write because I had already used the bufio package, which solves our stream buffering problem.

Read on for how to build and profile the different versions yourself.


Build

  • Go version: You’ll need a recent weekly snapshot of Go (hg update weekly), or Go v1 if it is released by the time you read this. Build it with: go build memg.go and run the memg executable it makes.

  • Python version: Uses Python 2.7 or Python 3, just run the script.

  • C version: Build with gcc -std=gnu99 -g -W -Wall -pedantic -pthread -o memg memg.c. There should be no warnings.

Profiling

To make profiling easier, each version accepts a --single command line parameter, so that it exits after a single connection.

Python

Start it in single mode, under the profiler:

python -m cProfile -o stats memg.py --single

Run test.py in a different window. View the output with pstats:

$ python
> import pstats
> p = pstats.Stats("stats")
> p.strip_dirs().sort_stats("cumulative").print_stats(20)

Go

Go has a sampling profiling, but because it is so fast we need more iterations. Edit test.py and increase to 10000 or more.

Run memg under prof, with --single so that it exits after the test connection closes:

go tool prof memg --single

See: prof command

You can get more detail using the runtime/pprof package and go tool pprof to examine the created file.

C

I couldn’t find a C profiler that would include I/O wait times (please let me know in the comments!), and as we’re heavily I/O bound, profiling without it doesn’t make much sense.

The most useful tool in this situation was strace. Run the following for a summary of the system calls issued, and run test.py in a different window. The output shows that it spends ~95% of the time in a recv call.

strace -c ./memg --single

If you still want to profile it, despite the lack of I/O wait information, start it in single mode under valgrind’s callgrind

valgrind --tool=callgrind ./memg --single

Run test.py in a different window. View the output with kcachegrind:

kcachegrind callgrind.out.<num>

Spec

If you’re interested in trying it in a different language, or a different approach, here’s the short spec.

The key-value stores are an in-memory hash map. The listen on port 11211, and accept set and get commands, so that you can reproduce the following telnet interaction:

telnet 127.0.0.1 11211

set greeting 0 0 11     # User
Hello World             # User, 11 bytes
STORED                  # Server response
get greeting            # User
VALUE greeting 0 11     # Server response
Hello World             # Server response
END                     # Server response

You type the ‘set’, ‘Hello World’ and ‘get’ lines. The rest are replies. In the ‘set’ line, the ’11′ is the length of the value (‘Hello World’) in bytes. The two zero’s are ignored. All lines terminate with \r\n.

The repo has a test.py script which uses pylibmc. To get pylibmc:

  • sudo pip install pylibmc
  • OR sudo apt-get install python-pylibmc

If you make a version in a different language, please send it to me on github, or link it in the comments.

Source:http://www.darkcoding.net/software/in-memory-key-value-store-in-c-go-and-python/

MEMORY  C  PYTHON  GO  KEY-VALUE 

Share on Facebook  Share on Twitter  Share on Weibo  Share on Reddit 

  RELATED


  0 COMMENT


No comment for this article.