If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.
You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

38_DesiginingKyotoCabinet

Page history last edited by Makoto Inoue 14 years, 1 month ago

DBMのオブジェクト指向設計

ID: 38

creation date: 2009/11/11 01:32

modification date: 2009/11/11 01:32

owner: mikio

Designing DBM in OO (Desigining Kyoto Cabinet)

俺がオブジェクト指向言語であるC++でDBMを実装するならこんなインターフェイスになるよという話。

This is a story about how I would make interface of DBM if I create it with C++ in OO way.

Tokyo Cabinetの場合

Tokyo Cabinetやその他のTokyoシリーズは全て純粋なC言語（C99標準）で書かれているが、抽象データ型などの技法を駆使してできるだけオブジェクト指向風味の設計にしている。C言語を選んだのには、既に俺がそれに習熟しているという理由とともに、ライブラリの依存関係を少なくしたい（libstdc++に依存したくない）という理由や、バイナリ配布の際の取り回しを考えるとC++特有のマングリングの問題を回避したいという理由や、できるだけ低レイヤな思考を自分に強制したいという理由などなどがある。C言語でもオブジェクト指向の考え方に基づいたプログラミングは可能であり、抽象データベースやそのスケルトン機構に至っては多相化や継承っぽいこともできるようになっている。そのおかげで、TTやそのLua拡張でTCを操作する際には、単純なインターフェイスでありながら、非常に幅広い機能群を利用することができる。

TCの設計思想技術選択はそこそこ的を得ていて、だからこそそれなりに機能と性能を獲得して、多くのユーザに愛される製品に成長できたと思っている。ただ、並列化を推し進めていくほどに内部のリソース管理（特に排他制御）が厄介になってきているのも事実だ。なので、そろそろオブジェクト指向言語の力を借りてプログラミングする時期だと思っている。ミクロ視点の最適化よりもマクロ視点の最適化をしていきたい。多少のオーバーヘッドがあってもメンテナンス性を重視していきたい。

Tokyo Cabinet Design

Tokyo Cabinet and other Tokyo series are all written in pure C, although I made it OO style by using technics such as Abstract Data Type. I chose C not only because it is the language I am proficient the most, but also because there are other reasons, such as I wanted to make less dependency between libraries(e.g.: libstdc++) , I wanted to avoid name mangling issues specific to C++, and I wanted to force myself to think at very lower layer. It is possible to programme C in OO way(such as polymorphism and inheritance) by using ADT and skeleton libraries. Thanks to C, I can provide very wide variety of functionalities with simple interface, when you operate TC via TT or its Lua extensions.

I think this design philosophy helped me achieving the performance and functionalities of TC as is now and it gained certain popularity. However, it is getting more difficult to manage internal resources (especially lock management) as I start pursuing the more concurrency of the system. I think it is about time to make use of OO orientated language. I am going to prioritise macro level optimisation rather than micro level optimisation of the system. Maintainability is becoming more important than the optimal performance.

C++をやり直す

前職（某OA機器メーカー）に勤めていた頃は案件でC++を使っていたし、その際にC++の一通りの機能は覚えたつもりではあるのだが、おそらくその理解はかなり浅いものだし、そしてそれすらも忘れてしまっているのが現状である。カニハン先生らの「プログラミング言語C」でC言語を覚えた俺なので、もちろんC++言語はスッポスッポ先生の「プログラミング言語C++」で学習したわけであるが、またあの分厚い本を学習してみようと思う。まだ昨日今日で会社の本棚から引っ張り出してきて前半をちょろっと読み直しただけだが。

コーディングスタイルに関しては、Google C++ Style Guideが非常に参考になった。定数にkを接頭させるのがちょっと気持ち悪いという以外は、全面的に同意できる内容だった。ということで、C++の全機能を使うというより、俺の目的に合った機能だけを使って、かつ一般的に通用している技法に合わせて、設計および実装をすすめていこうと思う。

Learning C++ again.

I used to use C++ when I was working in my previous company. I used to know basic of C++, but did not have full understanding of the language (and probably I forgot most of them by now). I am going to learn C++ with "The C++ Programming Language"by Bjarne Stroustrup , as I used to master C with "C Programming Language" by Brian W. Kernighan. Having said that, I just brought back the book from office and skimmed through a bit.

In terms of learning coding style, Google C++ Style Guide was very useful and agreeable, though the rule of adding "k" as prefix of constant looked weird. So, I am going to design and implement DBM by cherry picking the functionality and technics I like about C++

DBMクラス

さて、ここからが本題である。UNIXの文脈で言うところのDBMや、最近のトレンドでいうところのKVSは、簡単に言えば、連想配列を永続化する装置である。つまり、キーと値のペアを、キーを識別子として、格納したり、削除したり、取得したりするインターフェイスを持ち、そしてその内部状態をファイル等に直列化して記録する機能を備える。で、まずはインターフェイスの部分にのみ着目して、クラスの設計を行ってみる。Tokyo Cabinetのメソッド名に倣うとこんな感じになるだろうか。

DBM Class

OK, here becomes the meat of this article. Let's define what DBM is.

DBM (and currently popular Key Value System) concept is basically a system to persist associative arrays.

DBM's main functionalities are to

have an interface to store, delete, and obtain key value pair, using key as identifier.
serialise its inner state and record into files.

Let's start designing class by defining interfaces.

class DBM {

public:

virtual bool put(const std::string& key, const std::string& value) = 0;

virtual bool put_keep(const std::string& key, const std::string& value) = 0;

virtual bool put_cat(const std::string& key, const std::string& value) = 0;

virtual bool out(const std::string& key) = 0;

virtual std::string *get(const std::string& key) = 0;

};

putは、keyとvalueを受け取り、keyに関連づけてvalueを格納する。keyに一致するレコードが既にDB内にある場合には新しいvalueで上書きする。put_keepはputと同じだが既存値を上書きせずに操作を諦める。put_catはputと同じだが既存値の後に新たな値を連結する。outはkeyを受け取ってそのレコードを削除する。getはkeyを受け取ってそれに対応する値は、なければNULLを返す。

getの戻り値がstringオブジェクトそのものでなくポインタになっているのは、該当がない場合に例外やデフォルト値返却でなくNULL返却で対処するためと、コピーを抑制して性能を稼ぐためである。戻り値を呼び出し側でdeleteしなきゃならないのがちょっとダサいけど、STLみたいにイテレータを返してゴニョゴニョさせるのも好きじゃないので、このくらいが落としどころだろう。

"put" receives key & value, and store the value related to the key. If there is a matching key in the system, "put" will overwrite the value, "put_keep" cancels the operation, and "put_keep" will append the value. "out" receives the key and delete the record. "get" receives a key and return the matching value, or returns NULL if nothing matches.

There are 2 reasons why "get" return a pointer rather than a string object. The first reason is to return NULL rather than raising exception or returning default value when no matching value is. The second is to optimise the performance by avoiding object copy. Yes, it's a bit ugly that you have to delete the response value at application level, but I didn't like returning iterator like STL.

Visitorパターン

ところで、TCにはputprocという素晴らしいメソッドがある。keyとvalueを受け取り、keyに対応するレコードがなければそのペアをそのまま格納し、対応するレコードがあれば、引数のコールバック関数を呼び出してそのレコードのキーと値を渡し、処理結果を受け取って、NULLならそのレコードを削除し、そうでなければ新しい値として格納するというものだ。要は、該当のレコードを渡して任意のコールバック関数を呼ぶ機能である。

putprocを実装したところで気づいたのは、putもput_keepもput_catもoutもgetも、putprocだけで実装できるということである。デザインパターンの用語はあんまり使わない主義なのだが、Visitorパターンである。DBMを究極に抽象化すると、keyでリソースを識別してVisitorを呼び出し、その出力履歴を1世代以上保存する装置ということになるのだ。それを素直に表現してみると以下のようになる。

Visitor pattern.

BTW, TC has a wonderful method called "putproc".

"putproc" does

Receives key&value
Stores the value if there is no matching value
Calls callback function specified at the argument if matching record.
Deletes the record if the callback function returns NULL
Stores the new value if the callback function returns non NULL

While implementing putproc, I realised that "putproc" can be used to implement "put", "put_keep", "put_cat", "out", and "get". Yes, this is the "Visitor" pattern (I don' usually use design pattern vocabularies though). If I abstract DBM to the extreme, DBM does the following

Identifies resource by key
Call "Visitor "
Stores the output for more than one generation.

Here is my simple implementation of what I just described.

class RecordVisitor {

public:

virtual ~RecordVisitor() {}

virtual const std::string* visit_full(const std::string& value) = 0;

virtual const std::string* visit_empty() = 0;

static const std::string* nop;

static const std::string* out;

};

const std::string* RecordVisitor::nop = (const std::string*)0;

const std::string* RecordVisitor::out = (const std::string*)1;

class DBM {

public:

virtual bool accept(const std::string& key, RecordVisitor* visitor) = 0;

}

DBMのメソッドはたった一つになってしまった。acceptメソッドは、keyとvisitorを受け取って、該当のレコードがあれば、visitorのvisit_fullメソッドを呼び出し、なければvisit_emptyを呼び出す。いずれのメソッドも戻り値としてstringのポインタを返すことができ、その場合にはそれを値として新たなレコードを格納する。何もしたくない場合は定数nopを返し、既存のレコードを消したい場合は定数outを返す。visitorはRecordVisitorインターフェイスを継承した具象クラスのインスタンスを任意に実装して、いくらでも好きな事をやればいい。

Wow, now I only have one method inside DBM class. "accept" method does the following

Receives a key and a visitor object
Calls visit_full if there is a matching record
Calls visit_empty if there is no matching record
Both visit_full and visit_empty returns a string pointer
If the string pointer is returned, record new record.
If you do not want to do anything, then return "nop" constant.
If you want to delete the record, then return "out" constant.

"visitor" can create and extend as many instances which inherits RecordVisitor interface.

ユーティリティ実装の継承

素晴らしい。エレガントだ。Rubyだったらイテレータを使ってvisitorを表現すると恰好いい感じだ。ただ、唐突にacceptとか言われても初級者は困ってしまうので、やはりputやoutやgetも用意してあげたい。そこで、ヘルパーとして実装を挿入してあげよう。

Inheritance of the utility implementation.

Nice. So elegant!! If I had written this in Ruby, I would have created individual visitor objects using iterator pattern. Having said that, "accept" method would be too confusing for beginners, so let's put "put", "out", and "get" as helper methods.

class RecordVisitorPut : public RecordVisitor {

public:

RecordVisitorPut(const std::string& value) : value_(value) {}

virtual ~RecordVisitorPut() {}

virtual const std::string* visit_full(const std::string& value){

return &value_;

}

virtual const std::string* visit_empty(){

return &value_;

}

private:

std::string value_;

};

class RecordVisitorPutKeep : public RecordVisitor {

public:

RecordVisitorPutKeep(const std::string& value) : value_(value), ok_(false) {}

virtual ~RecordVisitorPutKeep() {}

virtual const std::string* visit_full(const std::string& value){

return nop;

}

virtual const std::string* visit_empty(){

ok_ = true;

return &value_;

}

virtual bool ok(){

return ok_;

}

private:

std::string value_;

bool ok_;

};

class RecordVisitorPutCat : public RecordVisitor {

public:

RecordVisitorPutCat(const std::string& value) : value_(value) {}

virtual ~RecordVisitorPutCat() {}

virtual const std::string* visit_full(const std::string& value){

value_.replace(0, 0, value);

return &value_;

}

virtual const std::string* visit_empty(){

return &value_;

}

private:

std::string value_;

};

class RecordVisitorOut : public RecordVisitor {

public:

RecordVisitorOut() : ok_(false) {}

virtual ~RecordVisitorOut() {}

virtual const std::string* visit_full(const std::string& value){

ok_ = true;

return out;

}

virtual const std::string* visit_empty(){

return nop;

}

virtual bool ok(){

return ok_;

}

private:

bool ok_;

};

class RecordVisitorGet : public RecordVisitor {

public:

RecordVisitorGet() : value_(0) {}

virtual ~RecordVisitorGet() {}

virtual const std::string* visit_full(const std::string& value){

value_ = new std::string(value);

return nop;

}

virtual const std::string* visit_empty(){

return nop;

}

virtual std::string *pop(){

return value_;

}

private:

std::string *value_;

};

class DBM {

public:

virtual ~DBM() {}

virtual bool accept(const std::string& key, RecordVisitor* visitor) = 0;

virtual bool put(const std::string& key, const std::string& value){

RecordVisitorPut visitor(value);