Toru Maesaka

As pointed out by Jay Pipes, I thought it would be nice to test and publish how BlitzLock performs against what I was originally intending on using for BlitzDB (pthread’s rwlock). So, I asked my colleagues in the operations group at Mixi to test BlitzLock on nice hardware that I don’t have access to. They kindly accepted and ran the BlitzLock sandbox on a 16 core machine running Fedora.

If you haven’t read my previous entry on BlitzLock and why I started writing it, you should. This entry won’t make sense otherwise.

Disclaimer

Before I step any further, please remember that I’m not trying to say BlitzLock is better than pthread’s rwlock. My interest is to write a lock mechanism that is optimized for Tokyo Cabinet (TC). What I wanted to gain from this test was to see if BlitzLock has enough potential for me to keep working on it.

Method

There were three kinds of workloads: “Read Oriented”, “Write Oriented” and “Neutral”. Read Oriented test has a 70% probability that each thread will call a read routine, whereas Write Oriented is the opposite where there is a 70% chance that the table state will be changed. In the Neutral test, both read and update calls have an even chance of being called. The seed value for the random number generator was identical for all tests.

Each worker sleeps for 10 milliseconds in the critical section and another 10 milliseconds right after it releases the lock. This was done to help cause context switching. Each test ran for 60 seconds.

You can obtain the standalone BlitzLock sandbox from here. I’ll upload a test friendly version that can accept startup options soon (I _really_ need to tidy it up).

Results

Below is a result from a load emulation where there was significantly more read calls than updates.

As seen above, BlitzLock is nicely scaling the workload without exhausting update threads. This is important since one of the concerns involved in the current implementation of BlitzLock is starvation (covered later). I think the read/write ratio above is the sort of ratio that is typically seen in the web industry and something I’m mostly concerned with. So how about a write intensive application? Next graph is a result of when there is significantly more update operations than read.

As seen above, BlitzLock is nicely scaling update tasks without neglecting readers. Compared to the first graph, we’re seeing an opposite result between update and scanner threads which is expected due to the nature of BlitzLock. This is exactly what I was hoping to gain. Next graph is a result from when there is an even chance of read and update operations to occur.

As seen above, the throughput evens out for both read and update operations. I was expecting pthread’s rwlock to show noticeably lower update throughput than read (since it’s a single writer lock) but it turned out to even out. I’m not quite sure how I should interpret this but I guess the writer’s lock had a greater priority than reader’s lock in the environment that the test was run in. Nevertheless, this “even out” characteristic is something I’d like to welcome.

From Here and Weaknesses

I’m convinced to keep working on BlitzLock and use it as the default locking mechanism for BlitzDB. Ideally I should code BlitzDB to be able to switch between various locking mechanisms. This would make my life much easier when someone decides to write a locking mechanism that is better than BlitzLock for my use-case.

Thanks to Paul McCullagh‘s feedback, I’ve come to realize that BlitzLock was broadcasting more often than it needs to. Functionally it still works but I should be able to save CPU usage by applying Paul’s feedback (thanks Paul!). There is also the potential lock starvation problem (when certain types of threads hog the lock) that I need to further investigate. If it’s going to cause noticeable issues, I’ll have to add a condition to BlitzLock saying “certain number of threads can obtain a certain lock at once”.

There is still another minor scheduling logic that I need to throw into BlitzLock but once I get that done (along with testing), I can integrate BlitzLock into BlitzDB and see how it performs (I can then hack on indexing!).

Yep, there’s still quite a bit to do but I’m having fun :)

Toru Maesaka drizzle, oss blitzdb, concurrency, locking, parallelism, pthread

Yesterday I sat in front of a whiteboard for few hours with Mikio, the author of Tokyo Cabinet discussing/debating what the optimal concurrency model would be for BlitzDB. I think we came to a pretty good conclusion so I’m going to note it on this entry. But before I step any further, allow me to go over Tokyo Cabinet’s concurrency model.

Tokyo Cabinet’s Concurrency Model

Tokyo Cabinet is often quoted as “single writer, multi reader” but this is not quite true. At the time of this blog entry, this statement holds true for TC’s B+Tree database but TC’s hash database can actually allow multiple writers to update and/or delete records concurrently.

If you look at the entry point of tchdbput(), you will notice that it is actually obtaining a reader’s lock (in terms of rwlock). TCHDB then hashes the provided key and obtains the bucket index number where the record of interest belongs to. Given the bucket/block to work on, TC then looks at the 8 most significant bits of the hash value and attempts to obtain a granular update lock from slots of 256 mutexes (2 ^ 8 = 256). So, things are still concurrent at this stage though there are some chances of collision that would block a thread.

If a record already exists, TC will go on and happily update that block but if the record is new (as in the key doesn’t exist), TC will lock the tail block of the database and write the new record there. So, only writing a new record is treated as a single writer and the rest can be processed concurrently. This is why I said it’s not quite true.

BlitzDB’s Concurrency Model

Taken the above into mind, this is what BlitzDB’s concurrency model looks like:

1. SELECT queries can run concurrently.
2. SELECT queries are blocked when UPDATE and/or REPLACE queries are being processed.
3. UPDATE, REPLACE, DELETE queries can run concurrently.
4. INSERT is never disrupted by BlitzDB and scheduled by TC.

In an ideal world, I would allow Drizzle’s worker threads to _directly_ interact with TC and let TC handle thread synchronization. This would make my life fantastically easy but unfortunately life isn’t so easy.

For example, if a record is deleted while BlitzDB’s table scan is occurring, the table scanner will stop scanning at the position where the deleted key existed. I would not have this problem if I used TC’s native iterator but my table scan implementation uses TC’s hidden API that won’t babysit me in this regard. In return I can gain maximum concurrent read throughput from TC which was a tradeoff I happily accepted.

So, there are several little gotchas like this which forces me to implement concurrency control in BlitzDB. Here’s how I’m planning on doing it (with demo code!).

Implementation (with demo code)

In the past I’ve gone through several experimental stages with BlitzDB where I used pthread’s rwlock to control concurrency. Short answer to the result is, “IT WORKS!”. However it was not taking full advantage of TC’s concurrency model.

For example I did not want to protect UPDATE queries with a writer’s lock since it would block other UPDATE/DELETE queries. So why not protect it with a reader’s lock? The issue here is that any query that can change the state of the table cannot be processed while a scanner is running (which btw is protected by a reader’s lock). Furthermore, a non-index based update/delete means that the scanner _is_ running so there’s a problem there too.

What I need is a scheduler that can allow multiple INSERT/UPDATE/REPLACE/DELETE queries to run when the scanner is not running. On the other hand the scheduler must allow multiple scanners to run when an UPDATE/REPLACE/DELETE queries aren’t being processed _BUT_ let INSERT queries come through to TC.

Implementing the above is probably possible by using multiple mutexes but it would bring complexity to the codebase and possible deadlocks that can be difficult to debug. So we decided to learn from pthread’s rwlock implementation and write an original lock mechanism similar to rwlock but something that allows us to write our own rules for scheduling.

Here’s my first attempt at a standalone sandbox of the model:

• http://torum.net/code/cc/blitzlock.cc

You can compile and run it to get a grasp of how threads are coordinated:

$ wget http://torum.net/code/cc/blitzlock.cc
$ g++ -Wall -pedantic blitzlock.cc -lpthread && ./a.out

If you got the program running and wondering what the output means, think of the “updater” as a thread that performs either UPDATE, REPLACE or DELETE.

There are much more that I’d love to go on about but I think I’ve bloated this entry enough so I will save my urge for another day :)

Toru Maesaka drizzle, oss blitzdb, concurrency, locking, parallelism, pthread, tokyocabinet