各種ロックのベンチマークその弐

ID: 45

creation date: 2009/12/03 16:42

modification date: 2009/12/03 16:42

owner: mikio

Benchmarking various locks Part 2

前回に引き続きロックの性能テストを行った。

This is part 2 of the series. The part one is here.

スロットロック

ハッシュDBにおいて個々のバケットに連なるチェーンのレースコンディションを回避するにはその個々のバケットを単位としてロックをかける必要がある。このように集合の個々の要素にロックをかけられる機構をスロットロックと呼ぶことにする。

バケット数は1000万とか1億とかの莫大な数になるので、その全てに対応するロックオブジェクトを作るわけにはいかない。x86_64のLinuxにおいては、sizeof(pthread_mutex_t)は40バイト、sizeof(pthread_rwlock_t）は56バイトであり、1000万個作ると少なくとも400MBものメモリを食ってしまうので現実的ではない。そこで、TCでは、256個のロックオブジェクトを作っておいて、キーのハッシュ値の下位8ビットに該当するオブジェクトをロックする方式を採用している。KCでもそれを踏襲する。

Slot Lock.

Inside hash DB, it needs to lock every single bucket to avoid chained race condition. We call it slot lock when you set lock to each bucket of a group.

The bucket can be as many as 10 million or 100 million, so it's not realistic to make lock object for each single element. Under x86_64 Linux architecture, sizeof(pthread_mutex_t) takes 40 bites、and sizeof(pthread_rowlock_t）takes 56 bytes.  If you make 10 million objects, it will eat up at least 400MB memory, which is not practical.

At TC, it creates 256 objects for locking purpose. Each object  locks only last 8 bit part of hashed key value.  KC also uses the same architecture.

なお、innoDBではビットセットを内部状態としてその変更をmutexで保護する仕組みのスロットロック的な機構を持っているらしい。そうすると自作のrwlockと同じレベルのオーバーヘッドが発生してしまうわけだが、クリティカルセクション内部の処理が比較的重い場合はロックのオーバーヘッドは相対的に軽視できるので、ビットマップでスロット数を増やしてできるだけブロックしないようにするというinnoDBの思想は的を得ていると思う。ただしKVSではクリティカルセクション内の処理は比較的軽いので、そこまでやらなくてもいいだろう。

InnoDB also has some sort of Slot Lock mechanism. Their slot lock holds inner state of bit set and protect the status change via mutex. This will cause as many overhead as my own rwlock(Mikio created his own version of rwlock to promote a locking from read lock to write lock. See the part one of this article). However, When the critical session has CPU intensive job, its locking overhead is relatively low. Therefore, it makes sense for InnoDB to avoid number of blocking by increasing the number of slot at BitMap. On the other hand, KVS tends to have less CPU intensive jobs, so it does not need to do the same as InnoDB.

スロットロックの性能

さて、256個に分けたスロットロックの性能を図るべく、単一のロックとの性能比較をしてみた。例によって合計100万回のループを回して、ロックとアンロックを繰り替えした。

Performance of Slot Lock.

In this case study, I compare one single lock against slot lock which is divided into 256 objects.  The test script executes 1 million loops. It locks at the beginning of the loop and unlock at the end of the loop, and don't do anything between. This simulates the situation where critical section finishes instantly that there is virtually no blocking (as I tried in previous post).

クリティカルセクションの中で何もしない場合にはどのロックも大して時間を食わないわけだが、スロットロックでも問題ないことがわかる。この実験は個々の試行が早すぎて誤差の方が大きいくらいなので、ロックをかけて外すということ自体の負荷は無視できる程度だということだけがわかればよい。

さて、ループ内でyieldした場合にはどうなるか。この条件は比較的に実際のユースケースに近いと考えられる。

When there is no activity during critical section, none of the locking mechanism take much time (including slot lock).  This is rather a test that overhead of locking/unlocking work itself is not a big issue.

The next test "yield" inside the loop. This case is closer to actual use case.

mutexでもspin lockでもrwlockでも、総じてスロットロックの方が効率的であることがわかる。衝突率が256分の1に緩和されるので、衝突時にビジーループするspin lockや衝突時にpthread_cond_waitに相当するオーバーヘッドがかかるrwlockで特に効果が高い。

This result clearly shows that slot lock is more effective in all 3 cases (mutex, spin lock, rwlock). You can see significant performance improvement on spin lock and rwlock.　This is because the two has more overhead when blocking happen, so the blocking ratio decreased to 1/256 will help them more.

まとめ

単一のロックをスロット化することによるコストは無視できるほど小さいわりに、その効果は極めて大きい。よって、スロットロックが使える場合には積極的に使うとよい。TCではハッシュバケットの保護にrwlockのスロットロックを使っているが、KCでもそれを踏襲する。

Summary.

There is small overhead to put locks into slot, but there is significant performance gain, so it's better to use slot lock wherever possible. TC uses rwlock slot lock to protect hash bucket and I am going to use the same approach to KC.