Disclaimer: this is obviously not legal advice, but I have been involved in similar GDPR adventures at my company.

> Does that mean I should be looking to host my DB with a non US company?

Yes, if you want to isolate yourself from any ramifications in the Safe Harbour/Privacy Shield/Paper Tiger #3 diplomatic processes.

> Does signing a DPA and putting some clause in our privacy terms be enough to be compliant?

Probably not (assuming you're referring to a DPA with a US-based company), but not having a DPA is not an option. In any case, the fallout from a total breakdown of transatlantic data transfers will be sufficiently large that fines will probably not be given without sufficient notice.

> Would I be breaking GDPR laws if a EU user was traveling outside the EU and this triggered a cache into a Redis outside the EU?

No, unless your outside-EU Redis is controlled by a different company than the inside-EU Redis. In which case you should sign a DPA with the outside-EU provider as well, with the same caveat as above.

> What is considered sufficient security to store email addresses of our users? Should I be encrypting email addresses in the database

No, but you will want to set up data access auditing for such fields, and possibly something like dynamic data masking so employees can not easily access the raw data. Normal at-rest data encryption of the entire datastore (and backups!) should be sufficient.

> Yes, if you want to isolate yourself from any ramifications in the Safe Harbour/Privacy Shield/Paper Tiger #3 diplomatic processes.

But if said US hosting company doesn't have the DB password then would this also apply? Do you think it would change anything if the data was encrypted at rest?

Strictly speaking, if said hosting company has access to the unencrypted data store they don't need any passwords. And if said hosting company has access to the encryption keys, any encrypted data store might just as well be considered unencrypted. So your question then becomes: how much effort should we spend on making it hard for our business partners to exfiltrate our data?

The problem with these kinds of questions is that the GDPR does not define any threat models, it only mentions "proper processes" and "adequate safeguards". Whether active subversion (by law or by greed) by your service provider should be included in your data loss exposure/risk assessments is very much an open question. At my company we decided to exclude such questions from the GDPR compliance process, and only include these scenario's in the threat models for our security assessments (note: that's not to say they are treated in isolation -- the results from our security assessments do inform our GDPR decisions like which data can be hosted where, but we do not repeat those same risk assessments in the GDPR survey).

To give a more direct answer to your question: I would consider encryption-at-rest a minimal requirement for a company hosting our internal data. Regardless of whether they're inside or outside the EU, and whether we're looking to host internal data, sales data or customer data; not being able to offer encryption at rest would mean my company won't use your hosting services for non-public data. For us, this specific ability is a supplier maturity test: if you haven't given serious thought about securing your customer's data, maybe we shouldn't be in business together.

But that decision is driven more by a defense-in-depth strategy about overall data security than by a specific GDPR requirement.

Encrypted at rest or not, the hosting company could easily dump the encryption keys out of memory while the server is running. If you're an American citizen, the government can just directly go after you or your company. If American law enforcement can get access to the data (i.e. by plugging the server into a UPS and carting it out of the data center) you're violating the GDPR at the very least; both attempts at skirting around the lack of American privacy guarantees were defeated by the American government refusing to provide sufficient data protection laws for European citizens, after all, choosing to uphold the PATRIOT ACT (and other such laws) over the digital business of EU customers.

Something as simple as a database password definitely doesn't fly as far as I know based on reading through the GDPR. Maybe it's legal if you apply enough tricks, you should consult a lawyer if you want to know your workaround is sufficient.

However, by default, storing PII of EU citizens (+UK citizens, I believe, they've implemented the GDPR before they left) with American companies is not legal. I can see how in theory a remote disk drive with fully end-to-end encrypted traffic (encrypted inside the EU, merely stored abroad, the decryption key never leaving the EU) may be allowed, but if the data gets decrypted on the American end I'm pretty sure you're out of luck. Otherwise, any form of TLS would be enough to avoid the GDPR, and that's definitely not the case.

Encryption at rest doesn't protect you. In fact, may even be legally required, regardless of where you store your data. The GDPR doesn't specify any exact security measures, but you do have to try your hardest to secure any PII you may process or store and encryption at rest is one of the easiest steps you can take to do so. You should make a conscious decision of what data may leak to where, the impact of the leak, and ways to counteract such problems.