When does a basic in-memory cache start slowing things down? And what should you do after that?

We've been using a basic in-memory cache, kind of like a HashMap, in our backend service. It's been great for speeding up common reads. But our traffic is picking up, and I'm wondering when this simple setup will start causing headaches instead of helping. Is it a memory thing, or maybe cache invalidation gets too messy, or is there something else I should worry about? When do you usually decide to jump to a bigger solution like Redis or Memcached? And what tells you it's time?