memcachedバイナリプロトコルは同期プロトコルを禁止するべき

現状のmemcachedのバイナリプロトコルのクライアント（=libmemcached）は、リクエストの順番通りにレスポンスが返ってくることを期待しており、これはmemcachedバイナリプロトコルを「汎用的なkey-valueベースの分散ストレージのためのプロトコル」として考えると、ひどい実装である。
そのような実装は最適化の余地を大幅に制限してしまい、性能とスケーラビリティが悪化する。memcachedの仕様書は、そのようなクライアントの実装はバグであると明示するべきである。
現状のmemcachedクライアントの実装の問題点と、その解決策について述べる。

同期プロトコルと非同期プロトコル

ネットワークプロトコルは以下の2つの種類に分けられる：

同期プロトコル

リクエストの順番通りにレスポンスを返す（リクエストの順番とレスポンスの順番が同期している）

非同期プロトコル

リクエストした順番通りにレスポンスが返ってくるとは限らない（リクエストの順番とレスポンスの順番が同期していない）

libmemcachedはmemcachedのバイナリプロトコルを同期プロトコルとして扱っており、リクエストした順番通りにレスポンスが返ってくることを期待している。同期プロトコルを採用するとクライアント・サーバーのどちらもその実装方法が制限されてしまい、最適化の余地を減らしてしまう。

同期・非同期の違いは、リクエストをパイプライン化したときに発現する。

パイプライン化とは、リクエストを送ったあと、そのレスポンスを待たずに立て続けに次のリクエストを送ってしまうことである。複数のリクエストを送りたいとき、レスポンスを待たずに一度に送ることできるので、性能が向上する。

以下のようにクライアントがリクエストをパイプライン化して送信するとき、同期プロトコルではレスポンスはリクエストを送った順番通りに返ってくるが、非同期プロトコルでは順不同になる。

Synchronized protocol:                          Asynchronized protocol:

   send request 1                                     send request 1
   send request 2                                     send request 2
   send request 3                                     send request 3
   receive response for request 1             receive response for request 2
   receive response for request 2             receive response for request 3
   receive response for request 3             receive response for request 1

The order of the responses is                The order of the responses is NOT
syncnhronized with the requests.          synchronized with the requests.

この例で、request 1の処理は非常に時間のかかるもので、request 2の処理はすぐに終わるものだったとしよう。

同期プロトコルでパイプライン化を使ってrequest 1とrequest 2を送信したとき、request 1の応答が返ってくるまでrequest 2の応答を得ることができない。つまりアプリケーションはrequest 1の処理が終わるまで長い時間待たないと、request 2に関する処理を継続することができない。
同期プロトコルでこの問題を回避するためには、パイプライン化を使わずに、request 1とrequest 2を別々のコネクションで送れば良い。しかしコネクションを増やすとサーバーの負荷が増加してしまうため、結果としてスケーラビリティを悪化させる。

非同期プロトコルでは、パイプライン化してrequest 1とrequest 2を送信しても、request 1にかかる処理時間にかかわらず、すぐにrequest 2の応答を得ることができる。

次にサーバーを実装することを考えてみる。

マルチコアCPUが当然となっている現在では、マルチスレッドを使って複数のリクエストを同時に処理しなければ性能が向上しない。また1台のサーバーだけでは性能が不足するときは、複数のサーバーを使って複数のリクエストを同時に処理しなければ性能が向上しない。memcachedのバイナリプロトコルを汎用的なストレージプロトコルとして捉えると、memcachedを実装するのに十分であれば良いのではなく、そのような用途にも対応できる拡張性を備えているべきである。

リクエストの内容によってその処理にかかる時間は異なるため、先に受け取ったリクエストよりも、後に受け取ったリクエストの方が（別のスレッド・サーバーで処理された結果）先に終了することは大いに有り得る。

しかし同期プロトコルでは、request 1とrequest 2がパイプライン化されて送られてきたとき、request 2の処理が先に終わったとしても、サーバーはrequest 2に対する応答をrequest 1の処理が終わるまで保留させておかなければならない。これはサーバーの実装を複雑化させる原因となり、結果として性能を悪化させる。

非同期プロトコルでは、単に処理が終わった順に応答を返せばよい。

現状のmemcachedバイナリプロトコルの仕様書では非同期プロトコルであることが示されていないため、クライアント・サーバーの両方で最適化の余地を減らしてしまい、性能が悪くなる。

memcachedバイナリプロトコルは、同期プロトコルを禁止するべきである。

プロトコルの改善案

非同期プロトコルを実装するためには、サーバーから返ってきたレスポンスが、どのリクエストに対するものなのかが分からなければならない。通常はリクエストとレスポンスの双方にシーケンス番号を含めることで実現する。
それを意図したものだと思うが、memcachedのバイナリプロトコルのopaqueフィールドをこの用途に使うことができる。サーバーはこのフィールドに入っている32ビットの整数を、クライアントにそのまま返すことが要求されている。
リクエストをパイプライン化して送信するクライアントは、opaqueフィールドにシーケンス番号を入れて送信すればよい。

非同期プロトコルの実装

同期プロトコルに対応したサーバーは同時に非同期プロトコルに対応したサーバーになるので、既存のサーバーのアーキテクチャを変更する必要はない。ここでは非同期プロトコルに対応したクライアントの実装について述べる。

非同期プロトコルはサーバーで行っていた処理を部分的にクライアントで行うことになるため、クライアントの実装が複雑になることがあるが、通常通り実装可能である。

非同期プロトコルを実装するには、以下に示すような4つの基本的なインタフェイスを実装し、それらを使って様々なコマンドを実装すればよい：

/* リクエストを送信し、そのレスポンスを待つ */
void send_request_sync(connection_type* con, const request_type* req,
    response_type* result_res);

/* リクエスト送信するが、そのレスポンスは受け取ったとしても捨てる */
int send_request_notify(connection_type* con, const request_type* req);

/* リクエスト送信し、そのレスポンスが受信されたらcallback関数を呼ぶようにする */
void send_request_async(connection_type* con, const request_type* req,
    void (*callback)(void* data, response_type* res), void* callback_data,
    request_id* result_reqid);

/* reqidが示すリクエストに対するレスポンスに関するcallback関数が呼び出されるまで待ち合わせる */
void synchronize_response(connection_type* con, request_id reqid);

getやget_multi などのコマンドは、これらのインタフェイスを使って実装することができる。

void get(connection_type* con, const char* key, size_t keylen, response_type* res)
{
    /* send_request_syncで送信して、応答を待ち合わせる */
    request_type req;
    create_get_request(&req, key, keylen);
    send_request_sync(con, &req, res);
}

void get_multi(connection_type* con, const char** keys, const size_t* keylens,
    response_type* ress, size_t num)
{
    request_type req;
    size_t i;
    request_id reqids* = malloc(sizeof(request_id) * num);
    /* 立て続けにリクエストを送信する */
    for(i=0; i < num; ++i) {
        create_get_request(&req, keys[i], keylens[i], ress[i]);
        send_request_async(con, &req, set_response, &ress[i], &reqids[i]);
    }
    /* 応答を待ち受ける */
    for(i=0; i < num; ++i) {
        synchronize_resopnse(reqids[i]);
    }
    free(reqids);
}

4つの基本的なインタフェイスと書いたが、実際にはsend_request_asyncとsynchronize_responseの2つだけを実装すればよい。なぜならsend_request_syncとsend_request_notifyは先の2つを使って実装できる：

static void set_response(void* data, response_type* res)
{
    *(response_type**)data = res;
}

void send_request_sync(connection_type* con, const request_type* req,
    response_type* result_res)
{
    request_id reqid;
    send_request_async(con, req, set_response, &result_res, &reqid);
    synchronize_response(con, reqid);
}

static void ignore_response(void* data, response_type* res)
{ }

void send_request_notify(connection_type* con, const request_type* req)
{
    request_id reqid;
    send_request_async(con, req, ignore_response, NULL, &reqid);
}

send_request_asyncとsynchroinze_responseは、send_requestとreceive_messageという簡単な関数を実装しさえすれば、すぐに作ることができる。

/* reqとreqidをパックしてソケットに書き込む */
void send_request(connection_type* con, const request_type* req, request_id reqid);

/* ソケットから応答を読み込んで返す */
void receive_message(connection_type* con, response_type* result_res, request_id* result_reqid);

/* リクエスト送信し、そのレスポンスが受信されたらcallback関数を呼ぶようにする */
void send_request_async(connection_type* con, const request_type* req,
    void (*callback)(void* data, response_type* res), void* callback_data,
    request_id* result_reqid)
{
    *reqid = con->next_id++;
    set_key_value(con->request_table, *reqid, callback, callback_data);
    send_request(con, req, *reqid);
}

/* reqidが示すリクエストに対するレスポンスに関するcallback関数が呼び出されるまで待ち合わせる */
void synchronize_response(connection_type* con, request_id reqid)
{
    request_id reqid;
    response_type res;
    void (*callbak)(void* data, response_type* res);
    void* callback_data;

    receive_message(con, &res, &reqid);
    get_key_value(con->request_table, reqid, &callback, &callback_data);
    if(callback) {
        (*callback)(callback_data, res);
    }
}

以上のように非同期プロトコルは実装できる。
memcachedのバイナリプロトコルを汎用的なkey-value型の分散ストレージのためのプロトコルとして利用できるようにするためには、仕様書で非同期プロトコルであることを明示するべきである。