database sharding, when is it time to split?

Our system is growing like crazy, and our single database is starting to creak. Reads are sluggish, and writes are a real bottleneck. We've tweaked indexes and thought about read replicas, but now I'm wondering about sharding. For those of you who've actually done it, what were the big signs that told you sharding was the way to go? What methods did you try, like hash-based or range-based sharding, and what was the hardest part of making the switch?