Most of the decent providers will help you improve failure independence. I know first hand that Linode is very accommodating for this.
I mention independent failures because f=3 is sufficient for this scenario for most. If there is correlation between failures and you cannot move servers around then you can compensate with a higher f.
In a future release (within the next six months), we'll be adding support for consistent snapshots that guarantee that HyperDex can withstand more than f failures with a bounded amount of data loss.
It's always possible to retrieve all data with an empty search and manually dump it into another form.
I didn't see anything in the documentation about backups...what are the options?