Is there a key-time-value database?
russell: What you want is a database that supports the equivalent of a multiple column key.  You can fake it by concatenating your key with a time stamp.  Tokyo cabinet supports this with its btree+ store.  You can select a range like thiskey-00000000 to thiskey-99999999.  The latest is the last returned. Or give the latest the key thiskey-00000000 and rekey it when you do an update.