| 
  • 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!

View
 

29_using_multiple_abstract_database

Page history last edited by Makoto Inoue 14 years ago

複式抽象データベース

ID: 29

creation date: 2009/10/13 22:45

modification date: 2009/10/13 22:45

owner: mikio

 

Using Multiple Abstract Database

 

TCおよびTTの最新版では、「複式抽象データベース(multiple abstract database)」なる機構がサポートされた。これは、抽象データベースAPIのスケルトン機構を用いて実装されていて、ハッシュDBやB+木DBや固定長配列DBやテーブルDBのローカルな水平分散を透過的に行うことを可能とする。いちおうマニュアルにも説明を書いておいた。

 

The latest version of Tokyo Cabinet and Tokyo Tyrant supports multiple abstract database. This is implemented based on skeleton library of abstract database, and it enables you to do run database queries in parallel without distributing datasets to different machines.

 

 

抽象データベースを普通に使った場合、データベースの具象型が何にせよ、レコードは単一のファイルに格納される。一方で、複式抽象データベースを使った場合、データベース名はディレクトリ名として扱われ、その中に複数のデータベースファイルが作られ、レコードはそのキーのハッシュ値で決められたファイルの中に格納される。

 

What is it?

 

When you use abstract database, it store the records into single file, no matter what database type you choose. When you use multiple abstract database, it creates a directory based on the database name, and then creates multiple database files underneath. The record will be stored into files allocated by the hash value of the key.

 

Why do you use it?

 

データベースを分割すると何が嬉しいかというと、データベース操作に要する排他制御の粒度がその分割数に応じて細分化することである。したがって、たとえ下層のデータベースがoptimizeメソッドなどのグローバルなロックを要する操作を行っていたとしても、複式抽象データベースを用いていれば、スレッドがブロックする時間を分割数の逆数にまで下げられる。

 

What's the benefit of splitting database into multiple files? Splitting database allows you to make more fine grained control on locking. When your database operation  requires a global locking (e.g.: optimise method), this will lock only one file of the database at a time.

 

TCはロック区間をできるだけ小さくするように実装しているが、それでもファイルサイズなどのメタデータが更新される際にはロックをかけてしまっている。複式抽象データベースを使うとそのようなロックの粒度をも実質的に細分化することになるので、コア数と同じくらいの数にデータベースファイルを分割するというのはバカっぽいようだが意外に効果的な場合もあるだろう。まあ実際に性能が向上するかどうかは処理系によって違うと思うが。

 

I implemented TC to minimise the locking area, but certain operations which update metadata (e.g.: file size) will require global locking.  By utilising multiple abstract database, you can run parallel locking to the same number of your CPU cores by splitting the database files. This sounds a bit too naive, but it may work in certain situations, though the extent of efficiency depends on implementation.

 

使い方は簡単で、openメソッドを呼ぶ前に、setskelmultiメソッドを呼ぶだけだ。以下の例では8個に分割したハッシュデータベースをディレクトリとして作成する。相変わらず拡張子で具象データベースの種類を決定するので、ディレクトリ名であっても拡張子は忘れてはいけない。

 

How to use it?

 

How to use multiple abstract database?  It's easy. All you do is to call "setskelmulti" method before calling "open" method. The following example will split database into 8 files. Make sure you put extension name  to the directory as well, because the extension name defines the name of abstract database.

 

TCADB *adb = tcadbnew();

tcadbsetskelmulti(adb, 8);

tcadbopen(adb, "casket.tch");

...

tcadbclose(adb);

tcadbdel(adb);

 

TTから呼ぶ場合には、-mul オプションをつけるだけだ。ちょーかんたん。

 

When you call it from TT, you just use -mul option. It's very easy, isn't it?

 

 

ttserver -mul 8 casket.tch

 

ただし、場当たり的なトリックにはたいてい落とし穴があるのだ。分割の代償として、CPUの負荷が増大してしまう。下層のハッシュ値とは独立したハッシュ値を計算する必要があるのでユーザランドでオーバーヘッドがかかり、複数のファイルのI/Oが錯綜するのでカーネルランドでオーバーヘッドがかかる。おそらく後者の方が深刻で、キャッシュの効率低下とかいろいろ問題が起こるかもしれない。

 

Gotchas.

 

However, you have to be aware that there are certain drawbacks.

 

* Additional CPU overhead (need extra computation to split)

* User land overhead by computing independent hash value for each files.

* Kernel land overhead by performing IO of multiple files

* The User land /Kernel land overhead may lead to decrease cache hit ratio.

 

また、fwmkeysメソッドなどの集合演算の結果の順序が不定になることは覚悟する必要がある。複式抽象データベースに対してmiscメソッドを実行する際には、サブ関数名に "@" か "%" を接頭させて引数毎の操作対象を指定できる。"@" は全ての引数をキーとみなして、引数毎に別々の内部データベースを対象としてサブ関数を実行する。"%" は引数をキーと値のペアのリストとみなして、そのペア毎に別々の内部データベースを対象としてサブ関数を実行する。すなわち、"getlist" は "@getlist" として実行すべきで、"putlist" は "%putlist" として実行すべきである。"@" も "%" もつかない場合には各々の内部データベースに対して全ての引数を渡して該当の操作を実行する。

 

 

The order result of "fwmkeys" may also become inconsistent. 

 

When you execute "misc" method against multiple abstract database, you can add either "@" or "%" prefix at arguments. 

"@" prefix is required to subfunctions which takes keys as argument (eg: @getlist)

"%" prefix is required to subfunctions which takes paris of key and value as argument (eg: @putlist)

If these prefixes are specified, the execution is performed per file.

If not specified, the execution is performed to all files.

 

 

(Notes from the translator: For more example, check this gist.)

 

で、結局実際に動かしてみないと良し悪しはわからんのだ。まずは、単一のハッシュDBに100万レコードを書き込んでみる。バケット数は80%とする。

 

Benchmark

 

Showing is easier than saying. Let's benchmark.

The following example writes 1 million record into single hash database. the number of bucket is 80%

 

tcatest write 'casket.tch#bnum=800000#xmsiz=1g' 1000000

...

time: 0.604

 

 

つぎに、同じく100万レコードを8分割のハッシュDBに書き込んでみる。

 

Next, it will write same 1 million record into a multiple abstract database which are divided into 8 files.

 

tcatest write '%casket-mul.tch#mode=wct#bnum=100000#xmsiz=1g' 1000000

...

time: 0.791

 

 

シングルスレッドの場合は単に性能が低下するだろうことは予見できたが、0.6秒が0.8秒になるのだから、これだけ見るとスループットは75%に落ちていることになるわけで、オーバーヘッドは結構でかいなと実感する。

 

I knew that Multiple Abstract Database on single thread has some overhead against normal database. The speed is down from 0.6 second to 0.8 second, which means that the throughput was decreased to 75%, which is quite a difference.

 

じゃあマルチスレッドだとどうなるか。わざわざこのテストのためにtcamttestってコマンドを書き下ろしちゃったさ。まずは10スレッドで単一ファイルに合計100万レコードを書き込む。

 

Then what happens if it's multi threaded? I wrote "tcamttest" command just for this. 

 

Let's try inserting 1 million rows into single file with 10 threads

 

 

tcamttest write 'casket.tch#mode=wct#bnum=800000#xmsiz=1g' 10 100000

...

time: 1.131

 

 

つぎに、同じく10スレッドで合計100万レコードを8分割のハッシュDBに書き込んでみる。

 

Next, let's try inserting same 1 million records with 10 threads, but into a hash db divided into 8 files.

 

tcamttest write '%casket-mul.tch#mode=wct#bnum=100000#xmsiz=100m' 10 100000

...

time: 0.571

 

ということで、マルチスレッドだとスループットが192%ほどに向上していることがわかる。下層のDBの並列性がない全く見込めない場合でもこの例だと並列性が8に近づく(というか俺の環境だとコア数の4に近づく)ことが期待できるわけで、TCのハッシュDBの並列性は多少頑張っているからそこまでの差は出ないにしても、分割の効果はあると言えそうだ。なお、より並列性の低いB+木で試してみたら、単一ファイルで4.647秒、8分割ファイルで1.503秒なので、スループットが約300%に向上することがわかった。まあ予想通りな感じかな。癖は強いが、それなりに実用にはなりそうだ。

 

You can see that the throughput now increases up to 192 %. The number of parallel becomes close to 8 (4 in my local machine environment). I designed Hash DB to be able to run in parallel a way better than other DB types, so there are not that much difference, but it's still worth doing.

When I try similar test using B+tree (which runs in parallel less than Hash DB), then writing to single file takes 4.647 seconds while writing to 8 files takes 1.503. This means that the throughput went up to 300%.  This is almost as I expected. Looks like this is practical , though there are lots of gotchas you have to take into considerations.

 

Sumary

 

繰り返しになるが、この方法で並列性を稼ぐのは、ずるである。こんなのは誰でもできるので、胸を張って主張するような機能じゃない。だけど、単純なkey-valueストレージとして使うんだったら、これで十分なことも多いだろう。

 

To be honest, this is a bit of too naive way to gain concurrency, and a bit of cheat, but this kind of simple solution may fit into simple key-value storage use.

 

 

Comments (0)

You don't have permission to comment on this page.