Google Suggestのようなものを高速に実現するサーバsuggested

libevent senna

Google Suggestのようなものを高速に実現するサーバsuggestedというものを書いてみた。
が、しばらく放置していた。とりあえず公開してみる。

特徴

  • epollやkqueueを使っていてネットワーク部分が速い
  • Sennaを使っていてSuggest部分が速い
  • Sennaを使って正規化している。「トン」とか「ミリバール」(組み文字)とか「Ｗｉｋｉ」(全角)とかでも検索可能

置き場

CodeResosに置いてあります。

一応、2008/01/17バージョンの全ソースコードを貼っておこう。

#include <sys/types.h>
#include <sys/time.h>
#include <stdlib.h>
#include <err.h>

#include <sys/queue.h>
#ifndef TAILQ_FOREACH
#define TAILQ_FOREACH(var, head, field) \
  for ((var) = ((head)->tqh_first); \
    (var); \
    (var) = ((var)->field.tqe_next))
#endif /* LIST_FOREACH */
#include <event.h>
#include <evhttp.h>

#include <senna/senna.h>
/* copy from senna/str.h */
typedef struct {
  const char *orig;
  size_t orig_blen;
  char *norm;
  size_t norm_blen;
  uint_least8_t *ctypes;
  int16_t *checks;
  size_t length;
  int flags;
  sen_ctx *ctx;
  /* sen_encoding encoding; */
} sen_nstr;
sen_nstr *sen_nstr_open(const char *str, size_t str_len,
                        sen_encoding encoding, int flags);

#include <stdio.h>
#include <string.h>

#define PORT 8000 /* port number listened */

sen_sym *tags;
char gbuf[SEN_SYM_MAX_KEY_SIZE];

static char *
chomp(char *string)
{
  int l = strlen(string);
  if (l) {
    char *p = string + l - 1;
    if (*p == '\n') { *p = '\0'; }
  }
  return string;
}

static int
do_insert(const char *filename)
{
  if (!(tags = sen_sym_create(filename, 0, 0, sen_enc_utf8))) {
    fprintf(stderr, "sym create failed\n");
    return -1;
  }
  while (!feof(stdin)) {
    char *cstr;
    sen_nstr *s;
    if (!fgets(gbuf, SEN_SYM_MAX_KEY_SIZE, stdin)) { break; }
    cstr = chomp(gbuf);
    s = sen_nstr_open(cstr, strlen(cstr), sen_enc_utf8, 0);
    sen_sym_get(tags, s->norm);
  }
  return 0;
}

void
generic_handler(struct evhttp_request *req, void *arg)
{
  const char *s;
  sen_nstr *prefix;
  struct evbuffer *buf;
  if (!(buf = evbuffer_new())) {
    err(1, "failed to create response buffer");
  }
  evhttp_add_header(req->output_headers, "Content-Type",
                    "text/plain; charset=UTF-8");
  /* get parameter */
  s = evhttp_decode_uri(evhttp_request_uri(req)) + 1;
  prefix = sen_nstr_open(s, strlen(s), sen_enc_utf8, 0);
  if (!prefix->norm_blen) {
    goto exit;
  }
  /* return tags */
  {
    sen_set *s;
    sen_id *tid;
    sen_set_cursor *c;
    if (!(s = sen_sym_prefix_search(tags, prefix->norm))) {
      /* no entry found */
      goto exit;
    }
    if (!(c = sen_set_cursor_open(s))) {
      err(1, "failed to sen_set_cursor_open");
    }
    {
      unsigned int nent;
      sen_set_info(s, NULL, NULL, &nent);
      evbuffer_add_printf(buf, "%u\n", nent);
    }
    while (sen_set_cursor_next(c, (void **)&tid, NULL)) {
      int tag_len = sen_sym_key(tags, *tid,
                                gbuf, SEN_SYM_MAX_KEY_SIZE);
      evbuffer_add(buf, gbuf, tag_len - 1);
      evbuffer_add(buf, "\n", 1);
    }
    sen_set_cursor_close(c);
    sen_set_close(s);
  }
  evhttp_send_reply(req, HTTP_OK, "OK", buf);
  return;
exit:
  evbuffer_add(buf, "0\n", 2);
  evhttp_send_reply(req, HTTP_OK, "OK", buf);
}

int
main(int argc, char **argv)
{
  struct evhttp *httpd;

  if (argc < 2) {
    puts("usage: suggested tag-dic");
    return 1;
  }

  sen_init();
  if (!(tags = sen_sym_open(argv[1]))) {
    fprintf(stderr, "create dictionary...\n");
    do_insert(argv[1]);
    fprintf(stderr, "dictionary created !!\n");
  }
  event_init();
  if (httpd = evhttp_start("0.0.0.0", PORT)) {
    evhttp_set_gencb(httpd, generic_handler, NULL);

    event_dispatch();

    evhttp_free(httpd);
  } else {
    fprintf(stderr, "cannot bind port %d", PORT);
  }
  sen_sym_close(tags);

  sen_fin();
  return 0;
}

ビルド

Sennaとlibeventが必要です。インストールしておきましょう。

make

でsuggestedというものができます。

使い方

UTF-8で、Suggest対象にしたい文字列が改行区切りで入っているファイルwordlistを準備します。
以下のようにして初回起動を行います。

./suggested dictonary < wordlist

一回辞書を作成すれば、二度目以降は辞書名のみを指定して起動できます。

./suggested dictonary

suggestedは、ポート8000をLISTENしています。
以下のようなURLにアクセスすると、

http://サーバのIPアドレス(ホスト名):8000/文字列

パスに指定された文字列をキーに、
単語リストからの前方一致検索を行った結果を返します。
１行目は総件数、それ以外は結果の単語です。
パスに指定する文字列は、UTF-8でエンコードしてください。


ためしに、Wikipediaの単語一覧を辞書としたサーバを立ててみました。
遊んでみてください。

落ちていても気にするな。

ToDo

  • encodingをutf-8以外にも対応
  • forkくらいする
  • JavaScriptによるクライアント側のコードを書く
  • コマンドラインでポート番号くらい指定できるようにする
  • 付加情報の保持
  • 付加情報によるソート

まとめ

CodeReposに置いてあるのでどんどん手を入れてください！！