Scaling Stateful Services, Strategies Beyond Shared Nothing?

We all know that a 'shared nothing' architecture is the holy grail for scaling stateless services, making horizontal scaling pretty straightforward. But stateful services are a different story. When services need to keep their state across requests or even between different instances, things get way trickier. I'm really curious, what strategies do you all use to scale stateful services well, especially when going completely 'shared-nothing' just isn't realistic or makes things too complicated? Do you like certain patterns, maybe eventual consistency with CRDTs, or do you go for more practical stuff like distributed locking or shared storage? What's been hard and what's worked out well for you?