Compare-And-Swap; lockless paradigm with CouchDB/Cloudant

I’m currently working on a matchmaking implementation using database back-end provided by Cloudant (which is built on CouchDB).

The algorithm requires me to be able to take ownership of records in a database in a fast, first-come-first-serve, way which locks these records out of subsequent requests until they are released.

In lockless, concurrent, programming there is the concept of “CAS” (compare-and-swap) which is an atomic operation with signature;

compareAndSwap(target, testValue,newValue) : boolean

The function tests the value of “target” and sets it to “newValue” if it is equal to “testValue”. If the swap succeeds the function returns true, if not it returns false. All of this is done atomically and on most modern hardware (and JVMs) this is implemented as a single instruction.

The idea behind this function is that a thread which wants to obtain or change a resource tries to do so with minimal overhead and no global locking required. If the swap fails the thread is responsible for either trying again or giving up; the key here is that the caller (the thread) is the only part which might block or wait, all other threads accessing the resource can continue uninterrupted. Contrast this to a global lock or synchronisation approach where the thread effectively locks out everybody else when accessing the resource. Using a CAS approach turns the locking problem on its head, so to speak. You can implement very effective concurrent collections, such as queues and linked lists, using a CAS approach where link pointers and indexes are the only things changed.

For the matchmaking problem an algorithm that locks out records using a CAS-function would check if the current record is “available” and then try to set it to “unavailable”. If it fails it continues to the next available record (in my case; it could also wait.)

With CouchDB and Cloudant you can implement this behaviour at a database record level;

Whenever a record (or “document”) is changed in these database implementations they get a new unique revision number (see for example: http://wiki.apache.org/couchdb/HTTP_Document_API) and whenever you want to update to a document you also need to provide the revision number for the document you want to change. The key here is that if the document currently in the database is at a different revision number the update fails (returning a 409 error.)

This is all we need to implement an atomic document CAS for these databases;

 docCAS(targetDocumentId, revisionNumber, newDocumentContents)

The “testValue” is now the expected revision number of the document which we want to change to “newDocumentContents”. The PUT call to the database will return a 409 error if the revision number is different from what we expected it to be. Otherwise the document is changed to the new contents (and the revision number is updated.)

There is nothing particularly clever or strange about all this but I thought it was quite nice that the CAS idea from lockless programming – usually confined to the domain of atomic single-instruction environments – was so easily and completely transferrable to a big, comparatively non-atomic, database.

And the matchmaking algorithm became a breeze to implement after this realisation had sunk in…

UPDATE

Cloudant pointed out that there is a problem with this implementation (as I put in my comment earlier) since a distributed database solution like Cloudant (or big couch) has a “propagation speed limit” (my term, can’t help drawing on physics parallels) such that two docCAS requests might apparently succeed at the same time and quietly cause a conflict. Internally Cloudant will resolve it and pick a “winner” but the writers won’t know that until they explicitly ask for conflicts from the database.

In my case the matchmaking can handle this because matches are played out asynchronously (i.e. while one player is online and the other is offline) so we have a little bit of leeway to manage the conflict. Even if these situations might arise infrequently they can arise and the matchmaker would be incomplete (and fragile) if it didn’t handle them.

For my case there are two situations where conflicts can arise;

  1. An offline player picked for a match is picked by more than one online player at the same time (because all of their docCAS requests overlap and cause a quiet conflict)
  2. An offline player picked for a match comes online the exact same moment as they are matched against and the docCAS succeeds for both

To resolve this I’m introducing a “begin/end” -match semantics (i.e. consider a match like a transaction); when a match between an attacker and a defender is over (and this might happen on a number of different clients since we are assuming a conflict happened) my code issues an GET on the defender’s document used for matchmaking with the ?conflicts=true flag in the query (more about this here: http://docs.cloudant.com/guides/mvcc.html). If this results in a list of conflicts I check if the current match was the winning one (i.e. if the revision of the matchmaking document for the defender was the one Cloudant picked as the winner); if it is I can go ahead and update the defender’s stats (and the attacker). If not I don’t (and I can decide to update the attacker depending on game design.) This way the defender will only ever lose once (and not have their resources stripped by several attackers at once.) Conversely, and depending on the game design, multiple attackers might benefit from the same attack but this is less of an issue.

For the second case the situation is a wee bit more involved (but not much); I have to check each revision in the conflict set (including the winning one) to find which one was the one corresponding to the defender coming online (knowing this requires a little bit more information in the matchmaking table) and determine if I update the defender and/or attacker based on this. I.e. it requires that a bit more information persists and that some more information is processed (the entire conflict set as opposed to just the winning one.)

So far, at least, it looks good on paper and in a test framework. The proof will be in the proverbial eating of the pud…

Update 2

It works but it can be simplified a lot; conflict resolution as I outlined it above is not needed because it only really affects the “match document” which are used to hold the lock. Once a match is over the defender’s state documents will be updated regardless – there is even no need to check if the revision number is the same as it was when the match started; one document will be the final word regardless what happens. However (!) this depends on the state of the defender not being updated accumulatively; i.e. if the defender’s state is cached at the beginning of a match and then updated from that cache at the end, as opposed to reloading the defender’s state fresh from the DB and then doing the update, the update will never be accumulative (i.e. it won’t be added to an update done by another attack at the same time.)

The end result is that only one document (state) is left as the final one, regardless of how many attacks happened. If a conflict happens (i.e. the replication issue outlined above) then Cloudant will pick a winner and we’re back to a single state update again. The defender is only penalised once.

That simplifies things….

Update 3

We’ve had this running for a while now without simultaneous requests generating any conflicts or issues. That doesn’t mean that they can’t happen (and we’re watching it carefully as the peak numbers grow) but as far as both reliability and performance is concerned the approach is working well and Cloudant serves this type of match making very well indeed.

Zeppelin and AirPlay setup problems…not quite so trivial

“Anyone who has a problem setting up AirPlay with the B&W Zeppelin is an idiot” some say on B&W’s support forums. Well, I don’t consider myself the dullest tool in the shed but I certainly had issues getting my swanky new Zeppelin to do what it was supposed to and get AirPlay up and running. Never listen to advice from people who haven’t had to walk a few miles in your shoes I say! And no; reading the the manual does not provide much help.

I followed the instructions to the letter but I only once, and only very briefly, got to see the “purple light of truth” and the Zeppelin setup wireless network. I reset the box using a pin, I followed the process on three different machines (including a Linux box) and with different network cables. All to no avail…

So, why would it be so damned difficult for me and a few others and so “obvious and easy” to others?

The answer, it seems, is the need for firmware updates! Those for whom it all “just worked” have probably had their box delivered with the latest firmware….

Btw you can ignore the B&W printed or PDF docs; they are clearly not kept up to date with the firmware so you will just frustrate yourself to the point of breaking. I ended up using the Mac Zeppelin set up app and others have had success with the iPad/iPhone variants too. The whole “connect to. 169.254.1.1” business is a non-starter.

Also there’s no point messing about with an Ethernet cable; with the latest and greatest firmware the box deals with it entirely over wifi.

Here’s what I think you must do, at least this did it for me after many dud attempts;

  1. update firmware to latest version using the B&W updater and application and an (ancient) printer USB cable…NOTE: I had to do this twice as the first update triggered the need for yet another one
  2. Then install one of the B&W setup apps
  3. re-power up the Zeppelin (and don’t bother with the Ethernet cable, I.e. I relied on the wireless entirely for the setup).
  4. make sure your PC/Mac is in the same network as the Zeppelin; I messed this up at least once when I tried to connect to the Zeppelin setup (temporary) network
  5. follow the instructions from whatever setup app you’re trying it with; Mac, PC, iDevice…
  6. be patient…don’t give up and try again

Basically that was “all there was to it” and rubbish documentation and unhelpful forum posts aside I am now enjoying the full power of the Zeppelin in my home and I sincerely hope that you will too.

Oh xdebug, where art thou?

I don’t have a stable development environment. I change hardware and software frequently so whenever my wife’s web site needs a revision I usually have to set everything up from scratch. I always develop on a Linux box (I am a Fedora user) and I’ll usually set up an apache server with MySQL running. For development I prefer NetBeans but I’ll use Eclipse if I have to.
For debugging I use XDebug and this is where the fun starts…

It never seems to be a smooth ride getting XDebug up and running, no matter what I do and judging from the many desperate cries for help on various forum threads I am not alone.

This blog post will not solve all your problems with getting xdebug working but I hope it might help you and give you a better set of tools to solve the problem.

The “problem” here manifests itself in NetBeans or Eclipse failing to connect to the debugger.

Firstly, if you have installed xdebug using any of the normal methods and phpinfo() shows an xdebug section then, at least in my experience, you’re good to go and any amount of hacks and fiddling in ini files is unlikely to fix your problem.
It is much more likely then that the problem is external and here is my simple check list of culprits that always seem to be behind my woes, either individually or together;

  • is your firewall allowing port 9000? (the default xdebug port, yours might be different but try not to fiddle with it too much)
  • is SELinux blocking you?

Run your firewall tool of choice (I just run system-config-firewall on Fedora) and check, or add, port 9000. Now try again…if working be happy, else…
Check if SELinux is barking about blocking a “name_connect” and see if port 9000 isn’t mentioned as well. If it is then you need to allow connections, obviously, and since I am not running my Linux box in an environment where I need to be too concerned about paranoid security I just blanket allow httpd (the apache server service I’m running on Fedora) to do whatever it wants;

#setsebool -P httpd_can_network_connect 1

If that doesn’t fix it then I sympathise because nothing is quite as frustrating as struggling with tools when all you want is to get the job done. But, in my humble experience at least, it seems to always end up being something like the above, I.e. something external is blocking xdebug from working. My point is that, unless you have a very peculiar set up, a plain vanilla install of xdebug with the standard ini file entries is fine and you should avoid fiddling with it before you’ve checked the external conditions – even though forum threads out there are quick to suggest it.

Good luck and happy debugging!

Stumbling through getting an OpenMPI app compiling and linking with (and without) NetBeans on Fedora

System

Fedora 14
Netbeans 6.9 + g++ 4.5.1 and MPICH2

Problem

I wanted to play around with OpenMP and C++ and I wanted to use the NetBeans IDE but had no luck compiling and/or linking.

Naively I did this:

  • installed MPICH2 packages using the package manager (I tried first with yum but that didn’t work at all…could be a red herring but be warned, see end notes.) 
  • openend up NetBeans, created a C++ app project and wrote a little Hello World program with a simple #pragma omp parallel section
  • I hit compile and…naturally, it just compiles a standard single-threaded app (ignoring the unrecognized pragma)
  • So, I tried to compile the program on the command line using the mpic++ compiler/linker wrapper which is installed with openmpi-devel
    • It failed with the errors about not finding -lmpichcxx, -lpmipch and -lopa (again, see end notes)

Solution

  1. mpic++ for some reason or other produces the wrong (???) command line;
    1. it typically looks like this: 
      1. c++ -m32 -O2 -Wl,-z,noexecstack -I/usr/include/mpich2-i386 -L/usr/lib/mpich2/lib -L/usr/lib/mpich2/lib -lmpichcxx -lmpich -lopa -lpthread -lrt
    2. but it should look like this (highlighting changes from above only):
      1. c++ -fopenmp -m32 -O2 -Wl,-z,noexecstack -I/usr/include/mpich2-i386 -L/usr/lib/mpich2/lib -L/usr/lib/mpich2/lib -lmpichcxx -lmpich -lgomp -lpthread -lrt
  2. Therefore, in the properties of your NetBeans project, under C++ Compiler::Additional Options you set the command line to
    1.  -fopenmp -m32 -O2 -Wl,-z,noexecstack -I/usr/include/mpich2-i386 -L/usr/lib/mpich2/lib -L/usr/lib/mpich2/lib -lmpichcxx -lmpich -lgomp -lpthread -lrt
    2. Alternatively you can of course use that as-is on the command line
  3. ..and compile…and it runs, and according to my perf monitor it uses more than one thread. Perfect.

Notes

libgomp is the GNU OpenMP library and it is part of the gcc 4.5.x install (and possibly earlier, but I haven’t checked/tested this). I don’t know what “libopa” was/is (can’t find anything about it) so it might even be a typo (although this would be horrendous and hopefully not the case) – If anybody reading this can shed some light….?

I tried with c++ and g++ both in the project settings in NetBeans but it doesn’t matter which one you use, as long as the command line is correct as in step 2 above.

The issue alluded to concerning installing OpenMPI using Yum; I did this first #yum install openmpi openmpi-devel but it seems that this, although it installed the libraries, did not create appropriate symlinks to them so that ld could find them (see note about ld failing at the top of this post.) I therefore manually created these and it fixed the linking, but as I subsequently did an install of MPICH2 using the package manager before I got the app running properly I can’t verify exactly if this had a positive effect overall or if it was a red herring. If anybody can recreate this and confirm then that would be great.

Btw, here are some great links for some OpenMP examples and tutorials:

http://www.codeproject.com/KB/library/Parallel_Processing.aspx

http://bisqwit.iki.fi/story/howto/openmp/#ExampleCalculatingTheMandelbrotFractalInParallel

https://computing.llnl.gov/tutorials/openMP/#CFormat

Growing a VirtualBox VDI is easy…

I use VirtualBox for lots of things, not the least to be able to use Microsoft Office for Windows on my work laptop, which is a Mac. Bless Office for the Mac but it sucks and I really need Excel to work with VB and the Data Analysis add-on…

However, I digress. As I installed more and more apps into my Win7 Virtual Machine I started running out of disk space so here follows a brief explanation of what I did (and do) when I need it (the VDI…) to grow. (Note that I didn’t originally create it using the  “dynamically expanding storage” option in VBox and if I had I might not be in this predicament but there you go.)

So;

  1. Create a new harddrive using the Virtual Media Manager in VBox and make sure it’s the size you want
    1. NOTE: Again I didn’t create the new disk as dynamic, but rather as static…I don’t know if the following steps would work if it was dynamic (somehow I doubt it but if you try then please let me know how it went…)
  2. Release and Remove your old harddrive from VBox’ grasp using the Virtual Media Manager;
    1. You have to do this otherwise the next step will fail. All you need to do is to release it, then remove it and REMEMBER to “Keep” the hard disk image when you do that!
  3. Clone your old (and smaller) VDI into the new (and larger) one like so using the VBox command line tool:
VBoxManage clonehd --existing OLD.vdi NEW.vdi
  1. Now go back into Virtual Media Manager and add the NEW.vdi drive
  2. In the settings for your virtual machine (the one that previously used the OLD.vdi) you change it to use NEW.vdi
  3. Downloadsystemrescuecd.iso (or any LiveCD with a Linux Distro and GParted on it. The remaining steps assume you can run GParted)
  4. Attach the LiveCD to your virtual machine so that it will be booted when it starts
  5. Boot your virtual machine…
  6. Run GParted;
    1. The virtual machine’s hard disk will be allocated into the “old” partition (which is the smaller size) and an extra, unallocated, partition which is whatever extra space you now have in your new and (larger) hard disk
  7. Resize the smaller partition (old) to take up all of the (new) disk
    1. NOTE: this assumes your guest OS uses a file system that GParted understands. In my case this was NTFS (Windows) but if you are attempting this to grow something else, and utterly esoteric, I can’t guarantee it will work. However, it would have to be very esoteric…
  8. Shut down the virtual machine
  9. Release the ISO (sysrescd.iso in my example)
  10. Reboot….
  11. Presto, you’re done! The machine should boot up happily and Windows will tell you that the C: drive is whatever size NEW.VDI was created as

Certainly beats using CloneZilla to try and save off the old image and restore it. I tried that too and it didn’t work but even if it did this method seems simpler.

Fixing “Client ‘foo’ can only be used from host ‘bar.local’ problem on Mac

Quick problem fix; there are some strange problems with P4V on Mac OS X which causes a spurious change to the host name in client specifications; everything works fine until one day you fire up P4v and get the error “Client ‘foo’ can only be used from host ‘bar.local”….I’ve found a couple of references to this on various fora but nothing that seems to solve it directly. NOTE: I run P4 locally on my machine and only use it for my own (local) revision control. As I mention below I doubt if this problem occurs if you’re running P4 on a proper networked server….

Anyway, I have a fix that works for me and it’s simple; run p4 to edit your client spec (‘foo’ in my example) and remove the line containing ‘Host‘…That line restricts access to a given host and is the one that seems to get “creatively altered” somehow to add a “.local” extension to it. Remove this restriction and all works.

HOWEVER: this fix assumes you don’t need host restriction which you might, of course. I suspect it might not be a problem for you anyway then since you’ll be using something like a properly resolved IP or network name…so there.

installing msttcorefonts on Fedora 13 (fixing Wine problem)

I had to install msttcorefonts (the Microsoft TTF fonts used by most windows programs) to be able to run Wine in my Fedora 13 install. It was pretty clear that the fonts were missing; all Windows apps I tried to run, including the Wine config tool, were unusable with all text garbled.
To fix this I had to install the core fonts and as this was a (somewhat) non-trivial task I have decided to document it here:
Fundamentally I followed the steps on Benprove.com but had to do make some modifications to make it work.
Firstly I “su -“‘ed to get root access.
Then;
  1. cd /tmp or somewhere else convenient…
  2. Download font spec file for the rpm build process (2.0-1 at the time of writing):
    1. wget http://corefonts.sourceforge.net/msttcorefonts-2.0-1.spec
  3. Install rpm-build and cabextract:
    1. yum install rpm-build cabextract
  4. Install ttmkfdir (required to build usable font files from TTF files):
    1. yum install ttmkfdir
  5. Now build the RPM package from the spec file:
    1. rpmbuild -ba msttcorefonts-2.0-1.spec
  6. Install chkfontpath (a util to configure X server font paths apparently)…and xfs which is a deamon that serves fonts to X server clients:
    1. Get chkfontpath (look for latest version if you do this):
      1. wget ftp://ftp.pbone.net/mirror/atrpms.net/f13-i386/atrpms/stable/chkfontpath-1.10.1-2.fc13.i686.rpm
    2. Get xfs:
      1. yum install xfs
    3. Build chkfontpath:
      1. rpm -ivh chkfontpath-1.10.1-2.fc13.i686.rpm
  7. Disable GPG (signature) checking in the yum config file so open /etc/yum.conf in your favourite editor, look for the line “gpgcheck=1” in the “[main]” section and change it to “gpgcheck=0”. Save the file.
  8. Now you can FINALLY install the fonts themselves from the RPM:
    1. yum localinstall  /usr/src/redhat/RPMS/noarch/msttcorefonts-2.0-1.noarch.rpm
  9. Clean up by re-enabling gpg check in /etc/yum.conf (DON’T FORGET THIS!)
  10. Log-out and log back in…

And that was it; Wine is now usable.