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

66_designing_transaction

Page history last edited by Makoto Inoue 13 years, 10 months ago

トランザクションの設計

ID: 66

creation date: 2009/12/10 15:47

modification date: 2009/12/10 15:47

owner: mikio

 

Designing Transaction

 

KCのトランザクション機構をどうしようかと思い悩んだ結果、結局TCと同じモデルにしたよという話。

 

This is my experience of designing KC transaction model (which ended up same with TC).

 

Berkeley DB風だとどうか

 

トランザクションでは例によってwrite ahead loggingでロールバック可能性を確保するのだが、TCではその対象が1ファイルに限られていた。つまり複数のデータベースファイルにまたがったトランザクションができないのである。複数のデータベースにまたがったトランザクションをしたい場合にそれだと困る。Berkeley DBはTCと違ってそれができるので、ちょっと引け目を感じている。

複数のファイルにまたがったトランザクションをしたいなら、個々のログがどのファイルを対象としているかをIDで管理する必要がある。また、IDとファイルの対応関係はアプリ側から教えてもらうことにする。つまりこんな感じのユースケースになる

 

How Berkeley DB handles?

 

TC also enables you to perform rollback with "write ahead logging", but you can only set transaction against one file, not multiple files. This will be inconvenient if you want to set transaction across multiple database files.  I kept feeling jealous towards Berkeley DB because it can handle multiple db transaction.

 

If you want to ensure transaction across multiple files, you need to manage which log is for which file (by assigning ID, for example). You also need to specify relationship between id and file from application level. If I write the logic in code, it will look like this.

 

Environment env;

env.open("user.wal");

 

HashDB db_nickname;

db_nickname.set_transaction(&env, 1);

db_nickname.open("user_nickname.kch");

 

HashDB db_intro;

db_intro.set_transaction(&env, 2);

db_intro.open("user_intro.kch");

 

env.begin();

 

db_nickname.set("123", "mikio");

db_intro.set("123", "I'm a programmer.");

 

env.commit();

 

上記はBekeley DBとほぼ同じようなセマンティクスになっているわけだが、ちょっと煩雑な感が否めない。Environmentオブジェクトの寿命とHashDBオブジェクトの寿命は前者が後者をラップする形になっていないといけないわけだが、それを保証できていない。

 

The above code has almost same semantic as Bekeley DB, but the code looks a bit clumsy. The code assumes that the HashDB object depends on Environment object, but there is no way to guarantee that (unless you control it manually).

 

環境をデータベースとして仮想化

 

どうせなら環境をデータベースに見立てて、個々のファイルを名前空間として扱う方がよいのではないか。

 

Virtualise environment as database.

 

Then I thought about treating an environment as a database, and map each file name as namespace.

 

 

HashDB db;

db.open("user");

 

db.begin_transaction();

 

db.set("nickname", "123", "mikio");

db.set("intro", "123", "I'm a programmer.");

 

db.commit_transaction();

 

 

setメソッドの第1引数が名前空間の指定である。「user」データベースの「nickname」名前空間のレコードは、「username.nickname.kch」というデータベースファイルに保存される。そのファイルの内部は通常のハッシュデータベースと同じである。こうしておけばWALファイルの名前を明示する必要はないし、環境とデータベースが別個にならないので楽だ。

もちろん単純化には副作用があるわけで、例えば名前空間毎にハッシュとB+木を使い分けたいみたいな場合に面倒になる。でもそれは db.set_type("nickname", BTREE) とかやって指定するのでもできるだろう。

 

 

The first variable of "set" method argument is a namespace.  The record under "nickname" namespace of "user" database will be stored under "username.nickname.kch" filename. The internal of the file is same as that of hash database.

 

By doing this, you do not need to specify WAL(http://en.wikipedia.org/wiki/Write-ahead_logging) file name and also don't need to trek environment name and database separately.

 

This simplification will cause some side effects. For example, this naming convention does not fit well if you want to allocate different db engine(e.g.: hashed, Btree) per namespace. In such scenario, I can work around by setting something like " db.set_type("nickname", BTREE) "

 

 

ていうか、キーに接頭辞つければよくね?

 

ミニマリストの俺としては、さらに、名前空間に接頭辞つければいいじゃんと言ってしまうわけだ。つまりQDBMやTCと同じモデルで、トランザクションは単一ファイルを対象に単純化して、キーの接頭辞で名前空間を分ければいい。

 

How about just adding prefix at a key?

 

Since I am a minimalist, I took this approach further by just adding prefix namespacing on keys.  By doing so, I can still keep "transaction per one file" mechanism, but let people have namespace by using key prefix. This is actually how you do with QDBM and TC.

 

HashDB db;

 

db.open("user.kch");

 

db.begin_transaction();

 

db.set("n:123", "mikio");

db.set("i:123", "I'm a programmer.");

 

db.commit_transaction();

 

面倒なこと何もしなくてよくて楽だな。空間を節約するために「n:」みたいな略記法でなくて長い名前をつけたいとしても、エイリアスと実名との対応関係をどっかに書いておけばいい。それを透過的にやるラッパーを書けばいい。

複雑なことをやろうとするとダークサイドに落ちるというか、俺の性格に向かないことになって挫折する可能性が高い。それに、複雑なユースケースはBekeley DBやembeded InnoDBに任せておけばいいのだ。TCやKCはあくまで単純さを第一にすべきだ。

 

This will be much simpler, as it will take out any complexities. If you don't like short namespace like "n:", then you can have some relationship table to store the alias and real name relationship and access through some sort of wrapper.

I have a tendency to give up implementing complex stuffs. I will leave these complex stuffs to Bekeley DB or embedded InnoDB.  Simplicity is the top priority for TC and KC

 

B+木データベースの扱い

 

TCにおいてB+木データベースはハッシュデータベースの上に実装されているが、KCでB+木を実装する場合にもそれを踏襲することになるだろう。ただし、B+木として利用できるとともに、ハッシュとしても利用できるようにする。B+木のノードを保存する際の接頭辞とハッシュDBのレコードを保存する際には別々の接頭辞をキーに割り振ればいい。接頭辞を1バイトにするなら、256種類の名前空間を切れる、そのうちひとつB+木のノード群に割り当て、残りは任意の使い方ができるようにする。

まて、これをさらに発展させると、テーブルデータベースを単一ファイルに乗せられるじゃん。レコード本体は「\0」を接頭辞にしてハッシュのレコードとして格納する。インデックスはID番号を振って、それを接頭させたノード群として格納する。インデックスIDとコラム名の対応関係を始めとする各種メタデータは「\xFF」を接頭させた空間に格納する。

 

Handling B+tree database.

 

TC implements B+tree database on top of Hash DB. KC will have same implementation, but it will let you use as both B+tree and Hash DB at the same time. I will allocate different prefix to Hash and B+tree nodes. If I assign 1 byte for prefix, it means I can have 256 different namespaces for the single byte. I will assign one of the to B+Tree and let the rest to be able to use for other purposes.

 

By extending this approach further, I  can put table database into one file. I will store record value as hash by assigning "\0" prefix to the key. I will allocate ID to each index and save them as group of node by prefixing the ID number. Other metadata (such as a table to keep relationship between index id and column id) will be stored with prefix "\xFF". 

 

まとめ

 

いろいろ考えたら面倒なんで複数ファイルのトランザクションはやめて、ハッシュデータベースの上にすべてを作ることにした。参照の局所性の観点などからよろしくない点をいろいろ列挙できるだろうが、B+木のキャッシュ機構を工夫すれば局所性を向上させることは可能だし、どっちみちファイルシステムに依存している時点で細かく制御する努力は酬われないので、これでよしとする

 

Summary

 

The more I think about implementing multi database transaction, the more it looks too complicating, and I ended up creating everything on top of hash database. 

There may be certain disadvantage such as "Locality of Reference"(http://en.wikipedia.org/wiki/Locality_of_reference), but I can improve the performance by utilising B+tree cache mechanisms. 

 

 

Comments (0)

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