Trond Norbye's Weblog

memcapable, part two

Today I added support for the ASCII protocol into memcapable so that it may be used to test both the binary and the ASCII protocol. By running it on the example server I added with the protocol parser in libmemcached I discovered that it failed all tests (mostly due to incorrect handling of noreply, but that is another story). It is not merged into trunk yet, so if you want to play with it today you need to branch lp:~trond-norbye/libmemcached/bugparade.

This is the result from running it on the server in my sandbox:

trond@storm> ./memcapable
ascii quit                              [pass]
ascii version                           [pass]
ascii verbosity                         [pass]
ascii set                               [pass]
ascii set noreply                       [pass]
ascii get                               [pass]
ascii gets                              [pass]
ascii mget                              [pass]
ascii flush                             [pass]
ascii flush noreply                     [pass]
ascii add                               [pass]
ascii add noreply                       [pass]
ascii replace                           [pass]
ascii replace noreply                   [pass]
ascii cas                               [pass]
ascii cas noreply                       [pass]
ascii delete                            [pass]
ascii delete noreply                    [pass]
ascii incr                              [pass]
ascii incr noreply                      [pass]
ascii decr                              [pass]
ascii decr noreply                      [pass]
ascii append                            [pass]
ascii append noreply                    [pass]
ascii prepend                           [pass]
ascii prepend noreply                   [pass]
ascii stat                              [pass]
binary noop                             [pass]
binary quit                             [pass]
binary quitq                            [pass]
binary set                              [pass]
binary setq                             [pass]
binary flush                            [pass]
binary flushq                           [pass]
binary add                              [pass]
binary addq                             [pass]
binary replace                          [pass]
binary replaceq                         [pass]
binary delete                           [pass]
binary deleteq                          [pass]
binary get                              [pass]
binary getq                             [pass]
binary getk                             [pass]
binary getkq                            [pass]
binary incr                             [pass]
binary incrq                            [pass]
binary decr                             [pass]
binary decrq                            [pass]
binary version                          [pass]
binary append                           [pass]
binary appendq                          [pass]
binary prepend                          [pass]
binary prependq                         [pass]
binary stat                             [pass]
binary illegal                          [pass]
All tests passed

I just discovered while reading the spec one more time today that some of the tests are not according to the spec, so I am going to submit bug reports on the community server and fix the tests:

• verbosity should always return OK, but does not if it encounter illegal number of options
• flush_all does not fail for illegal options
• delete a b does not fail, but assumes that the second option "noreply"

Do you see any other bugs in the ASCII protocol handling in the community server?

Posted at 03:40PM Oct 07, 2009 by trond in Memcached  |  Comments[0]

memcapable

Earlier today Matt Ingenthron blogged about the new tool memcapable I wrote a while back. In his blog Matt mentions some of the reasons why we want such a tool, but he didn't actually mention the reason for why I actually sat down to create the tool.

If you follow my blog you might remember my entry "Callback based protocol parser in libmemcached?". Before I could start implementing the parser, I really needed a tool to:

1. send all of the defined packet structures to the server
2. verify the response packet generated from the server

I didn't have the need for the textual protocol at the time I wrote the initial version of memcapable, so right now memcapable can only be used to test the binary protocol (not all variants of all commands are implemented in the initial version).

So how does it work? In it's simplest form you can use it to test the memcached server running on the default port on the same computer:

trond@storm> ./memcapable
noop		[pass]
quit		[pass]
quitq		[pass]
set		[pass]
setq		[pass]
flush		[pass]
flushq		[pass]
add		[pass]
addq		[pass]
replace		[pass]
replaceq		[pass]
delete		[pass]
deleteq		[pass]
get		[pass]
getq		[pass]
getk		[pass]
getkq		[pass]
incr		[pass]
incrq		[pass]
decr		[pass]
decrq		[pass]
version		[pass]
append		[pass]
appendq		[pass]
prepend		[pass]
prependq		[pass]
stat		[pass]
illegal		[pass]
All tests passed

Now this looks really nice doesn't it, but let's try to run it on a 1.2.8 version:

trond@storm> ./memcapable
noop		[FAIL]
quit		[FAIL]
quitq		[FAIL]
set		[FAIL]
setq		[FAIL]
flush		[FAIL]
flushq		[FAIL]
add		[FAIL]
addq		[FAIL]
replace		[FAIL]
replaceq		[FAIL]
delete		[FAIL]
deleteq		[FAIL]
get		[FAIL]
getq		[FAIL]
getk		[FAIL]
getkq		[FAIL]
incr		[FAIL]
incrq		[FAIL]
decr		[FAIL]
decrq		[FAIL]
version		[FAIL]
append		[FAIL]
appendq		[FAIL]
prepend		[FAIL]
prependq		[FAIL]
stat		[FAIL]
illegal		[FAIL]
28 of 28 tests failed

This shouldn't come as a big surprise, because the binary protocol isn't implemented in 1.2.8. Getting [FAIL] isn't really that informative, because it doesn't help you as a developer to figure out what's wrong. I have added a couple of options to the program that may help you to track down the real problem: -v and -c.

-v

Print out the assertion that failed

-c

Create a coredump when an assertion fails

Let's start the memcached server and disable the use of CAS and re-run memcapable with -v -c

trond@storm> ./memcapable -v -c
noop		[pass]
quit		[pass]
quitq		[pass]
set		memcapable.c:493: rsp->plain.message.header.response.cas != 0
zsh: IOT instruction (core dumped)  ./memcapable -v -c

As you can see it expects the response packet to have a CAS value set for the operation. If you would like to inspect the response packet you could load it into your debugger and poke around:

trond@storm> dbx - core
Corefile specified executable: "/source/libmemcached/memcapable/clients/memcapable"
Reading memcapable
core file header read successfully
Reading ld.so.1
Reading libm.so.2
Reading libnsl.so.1
Reading libsocket.so.1
Reading libpthread.so.1
Reading libthread.so.1
Reading libc.so.1
t@1 (l@1) program terminated by signal ABRT (Abort)
0xfffffd7fff2842aa: _lwp_kill+0x000a:	jae      _lwp_kill+0x18	[ 0xfffffd7fff2842b8, .+0xe ]
Current function is ensure
  212         abort();
(dbx) where
current thread: t@1
  [1] _lwp_kill(0x1, 0x6, 0xffffff01cdf92ae0, 0xfffffd7fff284c0e, 0x12, 0x0), at 0xfffffd7fff2842aa 
  [2] thr_kill(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff2788cd 
  [3] raise(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff227511 
  [4] abort(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff1fda41 
=>[5] ensure(val = 0, expression = 0x408498 "rsp->plain.message.header.response.cas != 0", file = 0x408198 "memcapable.c", line = 493), line 212 in "memcapable.c"
  [6] do_validate_response_header(rsp = 0xfffffd7fffdfeed8, cc = '\001', status = 0), line 493 in "memcapable.c"
  [7] test_binary_set_impl(key = 0x4087b0 "test_binary_set", cc = '\001'), line 621 in "memcapable.c"
  [8] test_binary_set(), line 651 in "memcapable.c"
  [9] main(argc = 3, argv = 0xfffffd7fffdff798), line 1196 in "memcapable.c"
(dbx) frame 6
Current function is do_validate_response_header
  493         verify(rsp->plain.message.header.response.cas != 0);
(dbx) print rsp->plain.message.header.response
rsp->plain.message.header.response = {
    magic    = '�'
    opcode   = '\001'
    keylen   = 0
    extlen   = '\0'
    datatype = '\0'
    status   = 0
    bodylen  = 0
    opaque   = 3735928559U
    cas      = 0
}

I noticed earlier today that there are some issues with the -v flag if you don't include -c (it just prints out the assertion and reports everything back up as success ;-)). I'll try to address that in the next release.

Posted at 11:39PM Sep 21, 2009 by trond in Memcached  |  Comments[0]

Callback based protocol parser in libmemcached?

I have been working on designing a small library for memcached protocol handling. The intention of the library is to parse the memcached protocol for you, and create callbacks to your application so that you can implement the function. By using this library you should be able to add support for the memcached binary protocol to your application. Please note that the intention of this library is not to create a replacement / yet another fork of memcached!

Before I'm going ahead and spend time implementing the stuff I would like to agree upon an API. I don't care much about the ASCII protocol, so I added _binary_ in all the function nimes if anyone wants to implement something similar for the ASCII protocol.

So how does it look? Instead of just throwing my proposal for the API to you, I'll try to describe when and how each function is used. Please note that the current API proposal doesn't contain any factory methods where you can specify the memory area to use (to avoid calling malloc). Why? well I don't want waste the best function names for such methods because I don't see using that version of the factory methods as being the main usage of the library.

The first thing you need to do in your application is to create a handle to the protocol handler. To avoid locking inside the library you can _only_ access the protocol handler from one thread at a time (unless you add synchronization yourself). If you want to run with multiple threads you should let each thread have its own instance of the protocol handler instead. The function looks like:

/**
* Create and initialize an instance of the protocol handler.
* Please note that the library does not copy the
* callback structure, and you may use the same callback structure
* for all of your instances of the library. You must
* ensure that the memory is valid throughout the use of the instances.
*
* @param callback The callbacks to use from this protocol handler.
* @return NULL if allocation of an instance fails
*/
LIBMEMCACHED_API
struct memcached_binary_protocol_st *memcached_binary_protocol_create_instance(struct memcached_binary_protocol_callback_st *callback);

We will get back to a description of the callback structure later on. You release the instance when you are done using the library with the following function:

/**
* Destroy an instance of the protocol handler
*
* @param instance The instance to destroy
*/
LIBMEMCACHED_API
void memcached_binary_protocol_destroy_instance(struct memcached_binary_protocol_st *instance);

With a handle to the protocol library you can listen to a server socket and accept new clients. When a new client connects to the socket, you need to create a client structure and associate it with the socket:

/**
* Create a new client instance and associate it with a socket
* @param instance the protocol instance to bind the client to
* @param sock the client socket
* @return NULL if allocation fails, otherwise an instance
*/
LIBMEMCACHED_API
struct memcached_binary_protocol_client_st *memcached_binary_protocol_create_client(struct memcached_binary_protocol_st *instance, int sock);

With the client connection in hand, we can tell the protocol library to start to work on the client by calling:

enum MEMCACHED_BINARY_PROTOCOL_EVENT { ERROR_EVENT, READ_EVENT, WRITE_EVENT, READ_WRITE_EVENT };

/**
* Let the client do some work. This might involve reading / sending data
* to/from the client, or perform callbacks to execute a command.
* @param client the client structure to work on
* @return The next event the protocol handler will be notified for
*/
LIBMEMCACHED_API
enum MEMCACHED_BINARY_PROTOCOL_EVENT memcached_binary_protocol_client_work(struct memcached_binary_protocol_client_st *client);

This function will try to read data from the network and fire the callbacks with the given commands, and return the events it is interested of being notified on. If ERROR_EVENT is returned you should close the socket and destroy the client handle with:

/**
* Destroy a client handle.
* The caller needs to close the socket accociated with the client
* before calling this function. This function invalidates the
* client memory area.
*
* @param client the client to destroy
*/
LIBMEMCACHED_API
void memcached_binary_protocol_client_destroy(struct memcached_binary_protocol_client_st *client);

That's all you _need_ to know, but there is also some utility functions:

/**
* Get the socket attached to a client handle
* @param client the client to query
* @return the socket handle
*/
LIBMEMCACHED_API
int memcached_binary_protocol_client_get_socket(struct memcached_binary_protocol_client_st *client);

/**
* Get the error id socket attached to a client handle
* @param client the client to query for an error code
* @return the OS error code from the client
*/
LIBMEMCACHED_API
int memcached_binary_protocol_client_get_errno(struct memcached_binary_protocol_client_st *client);

Earlier I told you that I would come back to the callback structures, so let's start describing them. The memcached_binary_protocol_callback_st is the _only_ structure in the protocol handler library you are allowed to touch the internals of, and it is used to specify the callbacks you are interested in:

struct memcached_binary_protocol_callback_st {
 /**
  * The interface version used (set to 0 if you don't have any specialized
  * command handlers).
  */
 uint64_t interface_version;

 /**
  * Callback fired just before the command will be executed.
  *
  * @param cookie id of the client receiving the command
  * @param header the command header as received on the wire. If you look
  *               at the content you must ensure that you don't
  *               try to access beyond the end of the message.
  */
 void (*pre_execute)(const void *cookie,
                     protocol_binary_request_header *header);
 /**
  * Callback fired just after the command was exected (please note
  * that the data transfer back to the client is not finished at this
  * time).
  *
  * @param cookie id of the client receiving the command
  * @param header the command header as received on the wire. If you look
  *               at the content you must ensure that you don't
  *               try to access beyond the end of the message.
  */
 void (*post_execute)(const void *cookie,
                      protocol_binary_request_header *header);

 /**
  * Callback fired if no specialized callback is registered for this
  * specific command code.
  *
  * @param cookie id of the client receiving the command
  * @param header the command header as received on the wire. You must
  *               ensure that you don't try to access beyond the end of the
  *               message.
  * @param response_handler The response handler to send data back.
  */
 protocol_binary_response_status (*unknown)(const void *cookie,
                                            protocol_binary_request_header *header,
                                            memcached_binary_protocol_response_handler response_handler);

 /**
  * The different interface levels we support. A pointer is used so the
  * size of the structure is fixed. You must ensure that the memory area
  * passed as the pointer is valid as long as you use the protocol handler.
  */
 union {
    /**
     * The first version of the callback struct containing all of the
     * documented commands in the initial release of the binary protocol
     * (aka. memcached 1.4.0).
     */
    struct memcached_binary_protocol_callback_v1_st *v1;
 } interface;
};

The memcached_binary_protocol_response_handler is a function you need to call to send data back to the client:

/**
* Each command-callback will supply a response-handler so that you can
* send data back to the client.
*
* @param cookie Just pass along the cookie supplied in the callback
* @param status The status code for your reply (see protocol_binary.h)
*               for legal values.
* @param key What to insert as key in the reply (may be NIL)
* @param keylen The length of the key (should be 0 if key is NIL)
* @param body What to store in the body of the package (may be NIL)
* @param bodylen The number of bytes of the body (should be 0 if
*                body is NIL)
* @param cas The CAS value to insert into the response (should be 0
*            if you don't care)
* @param datatype Should be PROTOCOL_BINARY_RAW_BYTES
*
*/
typedef void (*memcached_binary_protocol_response_handler)(const void *cookie,
                                                         protocol_binary_response_status status,
                                                         const void *key,
                                                         uint16_t keylen,
                                                         const void *body,
                                                         uint32_t bodylen,
                                                         uint64_t cas,
                                                         protocol_binary_datatypes datatype);

So the simplest example for you would be:

static struct memcached_binary_protocol_callback_st callback= { .unknown= my_function_callback; };

struct memcached_binary_protocol_st *handle;
handle= memcached_binary_protocol_create_instance(&callback);

It wouldn't help you much if you had to read the spec to get all the juicy details on how the protocol looks for all of the different commands, and thats what the interface-union is used for. My proposal for v1 looks like:

/**
* The first version of the callback struct containing all of the
* documented commands in the initial release of the binary protocol
* (aka. memcached 1.4.0).
*
* You might miss the Q commands (addq etc) but the response function
* knows how to deal with them so you don't need to worry about that :-)
*/
struct memcached_binary_protocol_callback_v1_st {
 /**
  * Add an item to the cache
  * @param cookie id of the client receiving the command
  * @param key the key to add
  * @param len the length of the key
  * @param val the value to store for the key (may be NIL)
  * @param vallen the length of the data
  * @param flags the flags to store with the key
  * @param exptime the expiry time for the key-value pair
  * @param response_handler to send the result back to the client.
  */
 protocol_binary_response_status (*add)(const void *cookie,
                                        const void *key,
                                        uint16_t keylen,
                                        const void* val,
                                        uint32_t vallen,
                                        uint32_t flags,
                                        uint32_t exptime,
                                        memcached_binary_protocol_response_handler response_handler);

 /**
  * Append data to an existing key-value pair.
  *
  * @param cookie id of the client receiving the command
  * @param key the key to add data to
  * @param len the length of the key
  * @param val the value to append to the value
  * @param vallen the length of the data
  * @param cas the CAS in the request
  * @param response_handler to send the result back to the client
  *
  */
 protocol_binary_response_status (*append)(const void *cookie,
                                           const void *key,
                                           uint16_t keylen,
                                           const void* val,
                                           uint32_t vallen,
                                           uint64_t cas,
                                           memcached_binary_protocol_response_handler response_handler);

 /**
  * Decrement the value for a key
  *
  * @param cookie id of the client receiving the command
  * @param key the key to decrement the value for
  * @param len the length of the key
  * @param delta the amount to decrement
  * @param initial initial value to store (if the key doesn't exist)
  * @param expiration expiration time for the object (if the key doesn't exist)
  * @param cas the CAS in the request
  * @param response_handler to send the result back to the client
  *
  */
 protocol_binary_response_status (*decrement)(const void *cookie,
                                              const void *key,
                                              uint16_t keylen,
                                              uint64_t delta,
                                              uint64_t initial,
                                              uint32_t expiration,
                                              memcached_binary_protocol_response_handler response_handler);

 /**
  * Delete an existing key
  *
  * @param cookie id of the client receiving the command
  * @param key the key to delete
  * @param len the length of the key
  * @param cas the CAS in the request
  * @param response_handler to send the result back to the client
  */
 protocol_binary_response_status (*delete)(const void *cookie,
                                           const void *key,
                                           uint16_t keylen,
                                           uint64_t cas,
                                           memcached_binary_protocol_response_handler response_handler);


 /**
  * Flush the cache
  *
  * @param cookie id of the client receiving the command
  * @param when when the cache should be flushed (0 == immediately)
  * @param response_handler to send the result back to the client
  */
 protocol_binary_response_status (*flush)(const void *cookie,
                                          uint32_t when,
                                          memcached_binary_protocol_response_handler response_handler);



 /**
  * Get a key-value pair
  *
  * @param cookie id of the client receiving the command
  * @param key the key to get
  * @param len the length of the key
  * @param response_handler to send the result back to the client
  */
 protocol_binary_response_status (*get)(const void *cookie,
                                        const void *key,
                                        uint16_t keylen,
                                        memcached_binary_protocol_response_handler response_handler);

 /**
  * Increment the value for a key
  *
  * @param cookie id of the client receiving the command
  * @param key the key to increment the value on
  * @param len the length of the key
  * @param delta the amount to increment
  * @param initial initial value to store (if the key doesn't exist)
  * @param expiration expiration time for the object (if the key doesn't exist)
  * @param cas the CAS in the request
  * @param response_handler to send the result back to the client
  *
  */
 protocol_binary_response_status (*increment)(const void *cookie,
                                              const void *key,
                                              uint16_t keylen,
                                              uint64_t delta,
                                              uint64_t initial,
                                              uint32_t expiration,
                                              memcached_binary_protocol_response_handler response_handler);

 /**
  * The noop command was received. This is just a notification callback (the
  * response is automatically created).
  *
  * @param cookie id of the client receiving the command
  */
 protocol_binary_response_status (*noop)(const void *cookie);

 /**
  * Prepend data to an existing key-value pair.
  *
  * @param cookie id of the client receiving the command
  * @param key the key to prepend data to
  * @param len the length of the key
  * @param val the value to prepend to the value
  * @param vallen the length of the data
  * @param cas the CAS in the request
  * @param response_handler to send the result back to the client
  *
  */
 protocol_binary_response_status (*prepend)(const void *cookie,
                                            const void *key,
                                            uint16_t keylen,
                                            const void* val,
                                            uint32_t vallen,
                                            uint64_t cas,
                                            memcached_binary_protocol_response_handler response_handler);

 /**
  * The quit command was received. This is just a notification callback (the
  * response is automatically created).
  *
  * @param cookie id of the client receiving the command
  */
 protocol_binary_response_status (*quit)(const void *cookie);


 /**
  * Replace an existing item to the cache
  *
  * @param cookie id of the client receiving the command
  * @param key the key to replace the content for
  * @param len the length of the key
  * @param val the value to store for the key (may be NIL)
  * @param vallen the length of the data
  * @param flags the flags to store with the key
  * @param exptime the expiry time for the key-value pair
  * @param cas the cas id in the request
  * @param response_handler to send the result back to the client.
  */
 protocol_binary_response_status (*replace)(const void *cookie,
                                            const void *key,
                                            uint16_t keylen,
                                            const void* val,
                                            uint32_t vallen,
                                            uint32_t flags,
                                            uint32_t exptime,
                                            uint64_t cas,
                                            memcached_binary_protocol_response_handler response_handler);


 /**
  * Set a key-value pair in the cache
  *
  * @param cookie id of the client receiving the command
  * @param key the key to insert
  * @param len the length of the key
  * @param val the value to store for the key (may be NIL)
  * @param vallen the length of the data
  * @param flags the flags to store with the key
  * @param exptime the expiry time for the key-value pair
  * @param response_handler to send the result back to the client.
  */
 protocol_binary_response_status (*set)(const void *cookie,
                                        const void *key,
                                        uint16_t keylen,
                                        const void* val,
                                        uint32_t vallen,
                                        uint32_t flags,
                                        uint32_t exptime,
                                        memcached_binary_protocol_response_handler response_handler);

 /**
  * Get status information
  *
  * @param cookie id of the client receiving the command
  * @param key the key to get status for (or NIL to request all status).
  *            Remember to insert the terminating packet if multiple
  *            packets should be returned.
  * @param keylen the length of the key
  * @param response_handler to send the result back to the client, but
  *                         don't send reply on success!
  *
  */
 protocol_binary_response_status (*stat)(const void *cookie,
                                         const void *key,
                                         uint16_t keylen,
                                         memcached_binary_protocol_response_handler response_handler);

 /**
  * Get the version information
  *
  * @param cookie id of the client receiving the command
  * @param response_handler to send the result back to the client, but
  *                         don't send reply on success!
  *
  */
 protocol_binary_response_status (*version)(const void *cookie,
                                            memcached_binary_protocol_response_handler response_handler);
};

Comments?

Posted at 03:08PM Aug 10, 2009 by trond in Memcached  |  Comments[0]

Memcached 1.4.0 released!

We released memcached 1.4.0 earlier today! It is more than two years since we started the work on one of the most important part of this release, the binary protocol. I guess a lot of users doesn't really care about the binary protocol, but it makes the implementation of other features easier (the replication in libmemcached is only available if you use the binary protocol).

Other highlights in 1.4.0:

• Performance improvements (removed lock contention)
• Run without privileges on Solaris
• More statistics information

Check out the full release notes at http://code.google.com/p/memcached/wiki/ReleaseNotes140.

Posted at 12:18PM Jul 10, 2009 by trond in Memcached  |  Comments[3]

Scale beyond 8 cores?

If you try to benchmark a memcached server, you will see that it scales relatively good up to 4 threads, and if you go beyond 8 threads the throughput will start to drop. People have been talking about the scalability problems of the memcached server on the mailing lists, IRC and on the hackathons with various solutions to the problems. If you look at the implementation of the memcached server, you will see that it use only a limited set of locks:

If you look at the implementation of the memcached server, it stores all of the items in one large hash map. Every time we need to insert, delete or search the hash table, we will try to get exclusive access to the entire hash table. And this is pretty much all that memcached does ;-) (You send a request, it looks up the item, and sends it back to you).

So how can we easily fix this problem without rewriting everyting? Well we could partition up the hash into multiple partitions and only lock down a subset of the hash instead of the complete hash. To avoid extra locking to update the LRU (if it spans two partitions) list I decided to let each partition have it's own LRU list. This sounded like a pretty easy fix to implement, so I just grabbed my laptop and implemented it while watching C.S.I on TV with my girlfriend one night :-)

So how did it scale? Zoran Radovic wrote the following blog entry: Scaling Memcached: 500,000+ Operations/Second with a Single-Socket UltraSPARC T2. If you are interested in the code, you can get it from http://github.com/trondn/memcached/tree/partition.

Posted at 01:10PM Jul 06, 2009 by trond in Memcached  |  Comments[5]