I'm having the same error right now, with Bitcoin-qt 0.9.3. After downloading and processing several weeks of new blocks, it crashed, and now it doesn't start anymore:
$ bitcoin-qt -wallet=empty.dat -debug
bitcoin-qt: table/table_builder.cc:97: void leveldb::TableBuilder::Add(const leveldb::Slice&, const leveldb::Slice&): Controletest 'r->options.comparator->Compare(key, Slice(r->last_key)) > 0' faalt.
Afgebroken
$
debug.log:
2015-06-20 11:27:40 Bitcoin version v0.9.3.0-b146f97-dirty-beta (2015-01-11 22:25:06 +0100)
2015-06-20 11:27:40 Using OpenSSL version OpenSSL 1.0.1e 11 Feb 2013
2015-06-20 11:27:40 Using BerkeleyDB version Berkeley DB 5.1.29: (October 25, 2011)
2015-06-20 11:27:40 Default data directory /home/cjp/.bitcoin
2015-06-20 11:27:40 Using data directory /home/cjp/.bitcoin
2015-06-20 11:27:40 Using at most 125 connections (1024 file descriptors available)
2015-06-20 11:27:40 Using 3 threads for script verification
2015-06-20 11:27:40 Using wallet empty.dat
2015-06-20 11:27:40 init message: Portemonnee aan het controleren...
2015-06-20 11:27:40 CDBEnv::Open : LogDir=/home/cjp/.bitcoin/database ErrorFile=/home/cjp/.bitcoin/db.log
2015-06-20 11:27:40 Bound to [::]:8333
2015-06-20 11:27:40 Bound to 0.0.0.0:8333
2015-06-20 11:27:40 init message: Blokindex aan het laden...
2015-06-20 11:27:40 Opening LevelDB in /home/cjp/.bitcoin/blocks/index
2015-06-20 11:27:40 Opened LevelDB successfully
2015-06-20 11:27:40 Opening LevelDB in /home/cjp/.bitcoin/chainstate
2015-06-20 11:27:41 Opened LevelDB successfully
I don't think I have bad RAM, but guess it doesn't hurt to do a RAM test. Anyway, the error now happens consistently a few seconds after start-up of bitcoin-qt, and I think it's unlikely it would hit the same RAM error each time in the same way. So, even if it was initially caused by a RAM error, right now it seems something is wrong with the state of the (block chain?) data on my disk, which is blocking me from re-starting bitcoin-qt.
Can I draw the conclusion, based on the log lines "Opened LevelDB successfully", that the error is NOT in .bitcoin/blocks/index and NOT in .bitcoin/chainstate? Based on the source file that reported the error, I'd say it has to be in something LevelDB-related. What does Bitcoin do AFTER successfully opening .bitcoin/chainstate?
I'll see if I can make a core dump and examine the function call stack. In the mean time, please reply if you know something that could help. My objective right now is to try to repair the files on my disk (e.g. removing the last ones that might be corrupt), in the hope that I can recover from this situation without re-processing the entire block chain again.