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:

Network Development in PLT: Overview

One of the nice thing about PLT Scheme is that you can write native scheme network apps, rather than having to use FFI to interface with C libraries for the network apps. The nice thing about using native scheme approach is that it works with PLT's threads, unlike FFI, which blocks all PLT threads (and effectively synchronizes the network access). And according to Geoffrey, FFI also have the disadvantage of having to worry about whether it expects 32-bit or 64-bit pointers.

The challenge with network development though is that we seldom have to do it, so it's hard to know all of the ins and outs of network development. This series of posts will provide a tutorial of doing networking development. The goal is to keep the principles as general as possible so it applies toward other programming languages, but obviously this is a scheme blog.

General Concept

We'll quickly go over the basic network architecture concept for the sake of completeness.

In general, networking involves clients and servers interacting with each other by sending information to each other and (if necessary) wait for responses from the other party.

Clients are programs that sends out the requests, and servers are programs that "fulfill" the requests (and possibly send back a response).  A program can be both a client and a server at the same time.

The information they send each other are serialized to bytes, which will be reconstructed by the receivers into meaningful representations that they can interpret.

Depending on the nature of the work, clients and servers might only need to send information to each other once and be done (HTTP is one such protocol), but sometimes they need to communicate back and forth to accomplish the task (SMTP is one such protocol), and such situation it might be necessary for the client and the server to keep track of the state in order to manage the work.

So, at a high level architecture, we need to focus on the following in order to do network development:

• manage the connection (initiation, termination, etc) 
• serialize and send information to the other party 
• receive information from the other party and interpret the meaning (and act accordingly)
• track and manage the state if the protocol requires it 

The above applies to all network developments.  The specific details and the associated complexity comes down to the specific protocols you are developing.

Let's take a look at what PLT offers to help us handle each of the needs.

Network Connection Management 

By default PLT offers network programming in TCP, UDP, and SSL.  You can require them into your module:

(require scheme/tcp scheme/udp openssl)

We'll focus on just TCP network development in this tutorial since most network protocols will be TCP-based.

Initiate Connections 

If you are developing a client, you can initiate a client connection with: