Here's the fix: fork the redis API for your language (nodejs,java,c#, whatever it may be) and remove the .KEYS function completely. Stop your entire dev team from shooting themselves in the foot.
Christ, any sympathy I had for them vanished when I saw they were using keys... The documentation is very clear about query complexity so this should have been an obvious one.