Develop a Memcached Client (4) - BZLIB/DBD-MEMCACHED

This is the "dramatic" conclusion of the memcached client development. You can find additional details in the previous posts:

1. network development overview
2. memcached client - storage API
3. memcached client - retrieval and deletion API, and the rest
4. distributed hash table frontend for memcached

Allright - it's not that dramatic, but I've made the memcached client available as a DBI driver via planet, so you can use it with the DBI interface.

The nicest thing about DBI is the ease for extension. You can - say - create your own driver to wrap around the memcached driver and the postgresql driver, so you do not have to sprinkle your code with calls to both drivers everywhere.

You'll find the tutorial of using bzlib/dbd-memcached after the integration section.

Integrate with DBI

The last stop is to integrate both the single instance and the distributed hashtable instance into DBI, so we can use it with the DBI interface.

As you remember from the create a DBI driver series, we basically have to create the following functions and register them as a driver with DBI:

• connect - wrap around the creation of the connection
• disconnect - disconnect the underlying connection
• prepare - for memcached it's a NOOP
• query - the majority of work is here
• begin-trans (optional) - for memcached it's a NOOP
• commit (optional) - for memcached it's a NOOP
• rollback (optional) - for memcached it's a NOOP

Below is the code that registers the single instance memcached client - integration of memcached/dht is left as an exercise:

(define (m-connect driver host port)
  (make-handle driver (memcached-connect host port) (make-immutable-hash-registry) 0))

(define (m-disconnect handle)
  (memcached-disconnect (handle-conn handle)))

(define (m-prepare handle stmt)
  (void)) 

(define (make-query set! add! replace! append! prepend! cas! get gets delete! incr! decr! flush-all!)
  (lambda (handle stmt (args '()))
    (let ((client (handle-conn handle)))
      (case stmt 
        ((set! add! replace! append! prepend!)
         (let/assert! ((key (assoc/cdr 'key args))
                       (value (assoc/cdr 'value args))
                       (flags (assoc/cdr 'flags args 0))
                       (exp-time (assoc/cdr 'exp-time args 0)))
                      ((case stmt
                         ((set!) set!)
                         ((add!) add!)
                         ((replace!) replace!)
                         ((append!) append!)
                         ((prepend!) prepend!))
                       client key value 
                       #:exp-time exp-time #:flags flags 
                       #:noreply? (assoc/cdr 'noreply? args))))
        ((cas!)
         (let/assert! ((key (assoc/cdr 'key args))
                       (value (assoc/cdr 'value args))
                       (cas (assoc/cdr 'cas args))
                       (flags (assoc/cdr 'flags args 0))
                       (exp-time (assoc/cdr 'exp-time args 0)))
                      (cas! client key value cas
                                      #:exp-time exp-time #:flags flags #:noreply? (assoc/cdr 'noreply? args))))
        ((get gets)
         (cons (list "key" "value" "flags" "cas")
               (apply (case stmt
                        ((get) get)
                        ((gets) gets))
                      client (map cdr (filter (lambda (kv)
                                                (equal? (car kv) 'key))
                                              args)))))
        ((delete!)
         (let/assert! ((key (assoc/cdr 'key args))
                       (delay (assoc/cdr 'delay args 0)))
                      (delete! client key delay (assoc/cdr 'noreply? args))))
        ((incr! decr!)
         (let/assert! ((key (assoc/cdr 'key args))
                       (value (assoc/cdr 'value args)))
                      ((case stmt
                         ((incr!) incr!)
                         ((decr!) decr!))
                       client key value (assoc/cdr 'noreply? args))))
        ((flush-all!) 
         (let/assert! ((delay (assoc/cdr 'key args 10)))
                      (flush-all! client delay (assoc/cdr 'noreply? args))))
        (else
         (error 'query "invalid stmt: ~a" stmt))))))

Develop a Memcached Client (3) - Distributed Hash Table

This is continuation of the network development in PLT post. You can see the previous posts for more details:

1. network development overview
2. memcached client - storage API
3. memcached client - retrieval and deletion API, and the rest

At this point we have a functional memcached client, but since people generally use memcached like a distributed hash table, what we have is not yet sufficient - we need a frontend to multiple instances of memcached.

The idea is simple - have a structure holding multiple memcached clients:

(define-struct memcached/dht-client (clients)) ;; clients is a vector of memcached clients.

Then we need to ensure that the key gets consistently mapped to the client that holds the data, and ensure the keys are distributed uniformly.

Uniform Hash Distribution

While the concept is pretty straight forward, the algorithm behind hashing is non-trivial. A good string hash function that I found is djb2, with the below as the scheme implementation:

(define (djb2-hash key)
  (define (convert key)
    (cond ((string? key) (convert (string->bytes/utf-8 key)))
          ((bytes? key) (bytes->list key))
          ((symbol? key) (convert (symbol->string key)))))
  (define (helper bytes hash)
    (cond ((null? bytes) hash)
          (else
           (helper (cdr bytes) (+ (* hash 33) (car bytes))))))
  (helper (convert key) 5381))

Once we convert the key into a hash code, we just need to take the remainder against the number of available memcached instances:

;; get the hash code 
(define (memcached/dht-hash client key)
  (remainder (djb2-hash key) (vector-length (memcached/dhs-client-clients client))))

As long as the count and the order of the clients remain the same, we will hash the key to the same client:

;; return the particular client by the key 
(define (memcached/dht-target client key)
  (vector-ref (memcached/dht-client-clients client)
              (memcached/dht-hash client key)))

With them, we can now wrap around all of our API's - we basically maintain the same interface as the single instance API, except that we are passing in the dhs client:

Develop a Memcached Client (2) - Filling Out the API

This is the continuation of the network programming series - see the previous installments for more details:

• overview of network development in PLT
• developing memcached client (1) - storage 

Now we have the ability to store data into memcached, we want to retrieve the stored data.

Generating Requests

Memcached offers two API for such purpose:

• get - return the data 
• gets - return the data along with the cas id 

(yes - it's only one character difference... oh well)


Let's take a look at the details of the API:

get <key>*\r\n
gets <key>*\r\n

The <key>* means there can be multiple keys, separated by space. We can represent the generation with the following:

(define (cmd-get out type keys) 
  (define (keys-helper)
    (let ((out (format "~a" keys)))
      (substring out 1 (sub1 (string-length out)))))
  (display-line out "~a ~a" (case type
                              ((get gets) type)
                              (else (error 'cmd-get "unknown get type: ~a" type)))
                (keys-helper)))

The next step is to parse the input.

Parse Response

The response is a bit harder, and it takes the following forms:

• there can be multiple values returned (one for each key found), and the ending is marked by END\r\n
  
• each value starts with a line of VALUE <key> <flags> <bytes-length> [<cas-unique>]\r\n
  
  • <cas-unique> is a 64-bit integer that uniquely identifies the object; and it is only returned if you use gets instead of get



• then the value is followed by the data block, terminated by \r\n. The data block should have the same length as indicated by <bytes-length>

The following algorithm will handle the above responses:

Developing a Memcached Client (1) - Storage

[This is a continuation of the network development in PLT post]

Memcached is all the rage these days with the high scalability guys.  Legends have it that as soon as you slap a couple of memcached in between your web app and your database server, all of your scalability issues go away.  Even if that's glossing over of details, memcached certainly offers advantages over accessing the discs all the time, and we want it in PLT.

Let's try to build a memcached client.

Steps to Build a Client (or a Server)

The steps to build either a client or a server is pretty straight forward (independent of the complexity of the protocol):

1. study the protocol 
2. write the "output functions" that sends the info to the other party 
3. write the "input functions" that parses the input from the other party 
4. combine the input & output functions, and manage the states of the connection (if applicable)

You are likely to mix the steps up instead of doing them in the order prescribed above and that's okay.  The steps are numbered to help us to think of them as an orderly process, but the process is likely more iterative.

Allright - let's get started.

Study the Protocol 

The key to build a network interface is to understand the protocols.  It is best if the protocol is open and published, so you have something written that you can study (hopefully in a language you understand).  The next best option is to reverse engineer from an open source implementation, and the worst is to reverse engineer from sniffing the network interactions between the clients and the server.  I am glad such memcached's protocol is already published so we do not have to go down the other routes.

Please refer to the memcached protocols throughout this process as the official reference.  We'll sprinkle information from the official doc in the posts as necessary.

First a quick overview of the memcached protocol.

• request/response protocol - there are no unexpected responses that the client has to handle 
• multiple requests and responses within a single session 
• *mostly* line-based protocol - the commands are single lines that are terminated by CRLF; the data is also terminated by CRLF, but it is actually determined by length parameter
• can store, retrieve, and delete the content (as well as flush) 
• there are also statistics that can be retrieved, but the protocol appears in flux for the stats (so it'll be out of scope for now) 
• the protocol itself is *stateless* as each of the requests and responses are independent from each other (each request is atomic) 

Overall the protocol is simple yet non-trivial, which gives us a great example for network development.  We'll start with the storage part of the protocol.

Storage API

Memcached has multiple storage commands for different situations: