+1  A: 

I would take a look at the write-through caching options in EHCache. As described in the link, combining a read-through and write-behind cache will provide persistence to a user-defined data store.

What Terracotta gives you is consistency (so you don't have to worry about resolving conflicts among cluster members). You have the option of defining an interface to your own store (through CacheLoader and CacheWriter or just letting Terracotta persist your data, but I have received mixed signals from Terracotta and documentation on whether TC is appropriate for a system-of-record. If your data is transient and can be blown away at any time (like for web sessions) it might be OK.

sehugg
Also to support the use-case you have described, you would need a third component, the user store (or a Terracotta cluster). EHCache does not support key-value backups AFAIK, while something like Hazelcast or Cassandra does rely on peers to redundantly store keys.
sehugg